CombinatoricsOfPolynomialsV2

4143 days ago by nhanbaoho

Our first order of business will be to define the setting in which we will be working. Since we will be dealing with univariate polynomials over the integers, we will define the ring $R$ to be precisely those univariate polynomials, with the following simple command:
R.<x> = ZZ[] 
       
Next, we let Sage know how to define the family of polynomials we will be working with. Courtesy of an elementary graph theoretic result governing independence polynomials, the following recursively-defined family gives set of independence polynomials of a particular family of path-like graphs:
max_n = 10 b(x) = (3*x+1)*(2*x+1)*(x+1) c(x) = 2*x+1 def p(n): if n == 1: return b(x)+x*c(x) else: if n == 2: return b(x)*p(1)+x*c(x)*b(x) else: return b(x)*(p(n-1)+x*c(x)*p(n-2)) first_few_ps = [p(n).expand() for n in range(1,max_n+1)] first_few_ps 
       
[6*x^3 + 13*x^2 + 7*x + 1, 36*x^6 + 156*x^5 + 249*x^4 + 190*x^3 + 74*x^2
+ 14*x + 1, 216*x^9 + 1404*x^8 + 3750*x^7 + 5437*x^6 + 4739*x^5 +
2586*x^4 + 886*x^3 + 184*x^2 + 21*x + 1, 1296*x^12 + 11232*x^11 +
42120*x^10 + 90696*x^9 + 125273*x^8 + 117236*x^7 + 76391*x^6 + 34980*x^5
+ 11184*x^4 + 2436*x^3 + 343*x^2 + 28*x + 1, 7776*x^15 + 84240*x^14 +
406944*x^13 + 1165464*x^12 + 2217510*x^11 + 2974517*x^10 + 2910455*x^9 +
2118153*x^8 + 1157309*x^7 + 475120*x^6 + 145444*x^5 + 32610*x^4 +
5183*x^3 + 551*x^2 + 35*x + 1, 46656*x^18 + 606528*x^17 + 3586032*x^16 +
12832128*x^15 + 31187484*x^14 + 54742116*x^13 + 72001617*x^12 +
72636802*x^11 + 57028800*x^10 + 35134294*x^9 + 17036279*x^8 +
6489360*x^7 + 1928012*x^6 + 440780*x^5 + 75831*x^4 + 9470*x^3 + 808*x^2
+ 42*x + 1, 279936*x^21 + 4245696*x^20 + 29696544*x^19 + 127545840*x^18
+ 377780760*x^17 + 821378340*x^16 + 1362059958*x^15 + 1766424101*x^14 +
1822159451*x^13 + 1512095096*x^12 + 1016586278*x^11 + 555692267*x^10 +
247071137*x^9 + 89104008*x^8 + 25901436*x^7 + 6005034*x^6 + 1092523*x^5
+ 152215*x^4 + 15640*x^3 + 1114*x^2 + 49*x + 1, 1679616*x^24 +
29113344*x^23 + 235146240*x^22 + 1178779392*x^21 + 4120831584*x^20 +
10699756992*x^19 + 21456340560*x^18 + 34107608784*x^17 +
43766447473*x^16 + 45920266760*x^15 + 39751763957*x^14 +
28564286700*x^13 + 17098498619*x^12 + 8537922228*x^11 + 3553625295*x^10
+ 1229188432*x^9 + 351411440*x^8 + 82335904*x^7 + 15616743*x^6 +
2355900*x^5 + 275531*x^4 + 24036*x^3 + 1469*x^2 + 56*x + 1,
10077696*x^27 + 196515072*x^26 + 1799988480*x^25 + 10317321216*x^24 +
41593497408*x^23 + 125657430624*x^22 + 295948912896*x^21 +
558067106160*x^20 + 858596443590*x^19 + 1092656490781*x^18 +
1161851029831*x^17 + 1039883989923*x^16 + 787483605821*x^15 +
506273144067*x^14 + 276807122085*x^13 + 128741530845*x^12 +
50868169553*x^11 + 17025184608*x^10 + 4803900976*x^9 + 1134865874*x^8 +
222301899*x^7 + 35628943*x^6 + 4586637*x^5 + 461949*x^4 + 35001*x^3 +
1873*x^2 + 63*x + 1, 60466176*x^30 + 1310100480*x^29 + 13418452224*x^28
+ 86568528384*x^27 + 395460455040*x^26 + 1363275722880*x^25 +
3690606097440*x^24 + 8060892550272*x^23 + 14481976421268*x^22 +
21708276510060*x^21 + 27443302559145*x^20 + 29497934795430*x^19 +
27123614349090*x^18 + 21431514661394*x^17 + 14596758942680*x^16 +
8585686849946*x^15 + 4364457989530*x^14 + 1916726751490*x^13 +
726116794399*x^12 + 236633785280*x^11 + 66065671820*x^10 +
15710746100*x^9 + 3157574311*x^8 + 530792050*x^7 + 73594990*x^6 +
8257766*x^5 + 730040*x^4 + 48878*x^3 + 2326*x^2 + 70*x + 1]
[6*x^3 + 13*x^2 + 7*x + 1, 36*x^6 + 156*x^5 + 249*x^4 + 190*x^3 + 74*x^2 + 14*x + 1, 216*x^9 + 1404*x^8 + 3750*x^7 + 5437*x^6 + 4739*x^5 + 2586*x^4 + 886*x^3 + 184*x^2 + 21*x + 1, 1296*x^12 + 11232*x^11 + 42120*x^10 + 90696*x^9 + 125273*x^8 + 117236*x^7 + 76391*x^6 + 34980*x^5 + 11184*x^4 + 2436*x^3 + 343*x^2 + 28*x + 1, 7776*x^15 + 84240*x^14 + 406944*x^13 + 1165464*x^12 + 2217510*x^11 + 2974517*x^10 + 2910455*x^9 + 2118153*x^8 + 1157309*x^7 + 475120*x^6 + 145444*x^5 + 32610*x^4 + 5183*x^3 + 551*x^2 + 35*x + 1, 46656*x^18 + 606528*x^17 + 3586032*x^16 + 12832128*x^15 + 31187484*x^14 + 54742116*x^13 + 72001617*x^12 + 72636802*x^11 + 57028800*x^10 + 35134294*x^9 + 17036279*x^8 + 6489360*x^7 + 1928012*x^6 + 440780*x^5 + 75831*x^4 + 9470*x^3 + 808*x^2 + 42*x + 1, 279936*x^21 + 4245696*x^20 + 29696544*x^19 + 127545840*x^18 + 377780760*x^17 + 821378340*x^16 + 1362059958*x^15 + 1766424101*x^14 + 1822159451*x^13 + 1512095096*x^12 + 1016586278*x^11 + 555692267*x^10 + 247071137*x^9 + 89104008*x^8 + 25901436*x^7 + 6005034*x^6 + 1092523*x^5 + 152215*x^4 + 15640*x^3 + 1114*x^2 + 49*x + 1, 1679616*x^24 + 29113344*x^23 + 235146240*x^22 + 1178779392*x^21 + 4120831584*x^20 + 10699756992*x^19 + 21456340560*x^18 + 34107608784*x^17 + 43766447473*x^16 + 45920266760*x^15 + 39751763957*x^14 + 28564286700*x^13 + 17098498619*x^12 + 8537922228*x^11 + 3553625295*x^10 + 1229188432*x^9 + 351411440*x^8 + 82335904*x^7 + 15616743*x^6 + 2355900*x^5 + 275531*x^4 + 24036*x^3 + 1469*x^2 + 56*x + 1, 10077696*x^27 + 196515072*x^26 + 1799988480*x^25 + 10317321216*x^24 + 41593497408*x^23 + 125657430624*x^22 + 295948912896*x^21 + 558067106160*x^20 + 858596443590*x^19 + 1092656490781*x^18 + 1161851029831*x^17 + 1039883989923*x^16 + 787483605821*x^15 + 506273144067*x^14 + 276807122085*x^13 + 128741530845*x^12 + 50868169553*x^11 + 17025184608*x^10 + 4803900976*x^9 + 1134865874*x^8 + 222301899*x^7 + 35628943*x^6 + 4586637*x^5 + 461949*x^4 + 35001*x^3 + 1873*x^2 + 63*x + 1, 60466176*x^30 + 1310100480*x^29 + 13418452224*x^28 + 86568528384*x^27 + 395460455040*x^26 + 1363275722880*x^25 + 3690606097440*x^24 + 8060892550272*x^23 + 14481976421268*x^22 + 21708276510060*x^21 + 27443302559145*x^20 + 29497934795430*x^19 + 27123614349090*x^18 + 21431514661394*x^17 + 14596758942680*x^16 + 8585686849946*x^15 + 4364457989530*x^14 + 1916726751490*x^13 + 726116794399*x^12 + 236633785280*x^11 + 66065671820*x^10 + 15710746100*x^9 + 3157574311*x^8 + 530792050*x^7 + 73594990*x^6 + 8257766*x^5 + 730040*x^4 + 48878*x^3 + 2326*x^2 + 70*x + 1]
Note the structure of the "if/else" statements in the above block of code, as well as the structure of a method definition. Now that we have our polynomials, let's do something with them! Each of the three blocks of code below defines a test to be performed on an input list of coefficients. The first tests for logarithmic concavity, a condition met if the terms $a_n$ in the input sequence all satisfy $a_n^2 \geq a_{n-1}a_{n+1}$:
def lc_test(L): for n in range(1,len(L)-1): if L[n-1]*L[n+1]>L[n]^2: return False return True 
       
In the above code we've had an encounter with the "for" loop, as it appears in Python and Sage. Just as easy to test is the condition of symmetry:
def symmetry_test(L): for n in range(0,len(L)-1): if L[n]!=L[len(L)-1-n]: return False return True 
       
Checking for unimodality (the presence of a single peak in the input coefficients) is a little trickier, but still elementary. We introduce a third control structure in this block, Sage's version of the "while" loop:
def unimodality_test(L): n = 0 while n<=len(L)-2 and L[n]<=L[n+1]: n = n+1 if n == len(L)-1: return True else: while n<=len(L)-2 and L[n]>=L[n+1]: n = n+1 if n == len(L)-1: return True else: return False 
       
Let's put 'em to a road test! First we'll generate the first so-and-so many members of our family of polynomials. Note how Sage recognizes that the polynomials we're generating are indeed elements of the polynomial ring over the intgers, $\mathbb{Z}[x]$, and therefore we're able to make use of the built-in "coefficients()" method that such objects entail.
firstNpolys = [p(n) for n in range(maxN)] coeffs = [firstNpolys[n].coef ficients() for n in range(maxN)] print firstNpolys print coeffs 
       
Just to show off Sage's intellectual prowess, let's ask it where the first element we generated lives:
firstNpolys[0].parent() 
       
Finally, let's run our combinatorial tests on the polynomials we've generated. Based upon the output, what sort of conjectures would you feel comfortable making at this point?
lc = [lc_test(coeffs[n]) for n in range(max_n)] print lc uni = [unimodality_test(coeffs[n]) for n in range(max_n)] print uni sym = [symmetry_test(coeffs[n]) for n in range(max_n)] print sym 
       
Traceback (click to the left of this block for traceback)
...
NameError: name 'coeffs' is not defined
Traceback (most recent call last):    sym = [symmetry_test(coeffs[n]) for n in range(max_n)]
  File "", line 1, in <module>
    
  File "/tmp/tmp7YJZrE/___code___.py", line 2, in <module>
    lc = [lc_test(coeffs[n]) for n in range(max_n)]
NameError: name 'coeffs' is not defined