Re: [math-fun] more polynomial factor heights
MKI> I hope my reposting of a solution to a different problem didn't fool
people into thinking they shouldn't pay attention to this one!
On Wed, Jul 6, 2011 at 5:29 AM, Bill Gosper <billgosper@gmail.com> wrote:
rwg>
Anyway, here's another: Find the height 1 polynomial of least degree d with an irreducible factor of height > d. And >=d?
I'll start the bidding with d = 37, height 41. Whose value I'll sequester for now just to make things harder. --rwg
MK> I've got one that's degree 21, with an irreducible factor of height 23.
I went looking for things of the form P = (irred) * (x-1)^2, since I more-or-less understand how successive-differences-of-coefficients works. The easiest thing to think about was P / (x-1): successive coefficients of that polynomial need to differ by 0, 1, or -1 (to make P height 1), the sum of the coefficients needs to be 0 (to make it divisible by x-1 again), it needs to be short (to keep total degree down), and the sums of the initial subsequences of coefficients needs to get large (to get the irred factor to get high degree).
The best sequence of coefficients for P/(x-1) that I've come up with so far is: 1,2,3,4,4,3,3,2,1,0,-1,-2,-3,-4,-3,-3,-2,-2,-1,-1,-1
Divide by x-1 (i.e. take successive sums of coefficients) and we get coeffs 1,3,6,10,14,17,20,22,23,23,22,20,17,13,10,7,5,3,2,1. Multiply by x-1 (ie take successive differences) and the coefficients are all 0s, 1s, and -1s. The length of my sequence is 21, so the degree of the polynomial is 21 also (since it has 22 coefficients, from x^0 through x^21).
I don't expect this to be minimal, but it seems like a pretty good construction.
--Michael
Whoa, can anybody beat that? Meanwhile, this is sort of interesting: In[1154]:= Factor[-1 + x + x^2 + x^3 - x^4 + x^5 + x^7 + x^8 - x^10 - x^11 - x^12 - x^13 - x^14 - x^15 - x^16 - x^18 - x^19 - x^22 + x^23 + x^24 + x^25 + x^26 + x^27 + x^28 + x^29 + x^30 + x^31 + x^32 + x^33 - x^34 - x^35 - x^36 - x^37 - x^38] Out[1154]= -(-1 + x)^3 (-1 - 2 x - 2 x^2 + 3 x^4 + 8 x^5 + 15 x^6 + 25 x^7 + 39 x^8 + 57 x^9 + 78 x^10 + 101 x^11 + 125 x^12 + 149 x^13 + 172 x^14 + 193 x^15 + 211 x^16 + 226 x^17 + 237 x^18 + 243 x^19 + 244 x^20 + 240 x^21 + 230 x^22 + 215 x^23 + 196 x^24 + 174 x^25 + 150 x^26 + 125 x^27 + 100 x^28 + 76 x^29 + 54 x^30 + 35 x^31 + 20 x^32 + 10 x^33 + 4 x^34 + x^35) --rwg
On Sat, Jul 9, 2011 at 3:21 PM, Bill Gosper <billgosper@gmail.com> wrote:
Meanwhile, this is sort of interesting:
In[1154]:= Factor[-1 + x + x^2 + x^3 - x^4 + x^5 + x^7 + x^8 - x^10 - x^11 - x^12 - x^13 - x^14 - x^15 - x^16 - x^18 - x^19 - x^22 + x^23 + x^24 + x^25 + x^26 + x^27 + x^28 + x^29 + x^30 + x^31 + x^32 + x^33 - x^34 - x^35 - x^36 - x^37 - x^38]
Out[1154]= -(-1 + x)^3 (-1 - 2 x - 2 x^2 + 3 x^4 + 8 x^5 + 15 x^6 + 25 x^7 + 39 x^8 + 57 x^9 + 78 x^10 + 101 x^11 + 125 x^12 + 149 x^13 + 172 x^14 + 193 x^15 + 211 x^16 + 226 x^17 + 237 x^18 + 243 x^19 + 244 x^20 + 240 x^21 + 230 x^22 + 215 x^23 + 196 x^24 + 174 x^25 + 150 x^26 + 125 x^27 + 100 x^28 + 76 x^29 + 54 x^30 + 35 x^31 + 20 x^32 + 10 x^33 + 4 x^34 + x^35) --rwg
Inspired by this example, I wrote some Mma to look for polynomials which become height-1 when multiplied by (x-1)^3. My previous less-than-coherent mail was about doing this by hand for (x-1)^2, where I could just think about what multiplication and division by x-1 would do. For (x-1)^3, brute force seemed the wiser approach. The best results from this approach are two polynomials of degree 18, each of which is (x-1)^3 times a degree-15 polynomial with a coefficient of 25 (!!): -1 - x + x^2 + x^4 + x^5 + x^6 - x^7 + x^8 - x^10 - x^11 - x^13 + x^14 - x^15 + x^18 = (x-1)^3 * (1 + 4*x + 8*x^2 + 13*x^3 + 18*x^4 + 22*x^5 + 24*x^6 + 25*x^7 + 24*x^8 + 21*x^9 + 17*x^10 + 13*x^11 + 9*x^12 + 6*x^13 + 3*x^14 + x^15) -1 - x + x^2 + x^4 + x^5 + x^6 - x^7 + x^8 - x^9 - x^11 + x^12 - x^13 - x^15 - x^16 + x^17 + x^18 = (x-1)^3 * (1 + 4*x + 8*x^2 + 13*x^3 + 18*x^4 + 22*x^5 + 24*x^6 + 25*x^7 + 24*x^8 + 22*x^9 + 19*x^10 + 16*x^11 + 12*x^12 + 8*x^13 + 4*x^14 + x^15) (Well, there are only two genuinely different ones; you could read the coefficient lists backwards also.) I searched for these by recursively extending sequences of coefficients to keep things height-1 after multiplication by (x-1)^3. That is, if the coefficient list begins (1, 4, 8), then the next coefficient must be 12, 13, or 14, in order to make the next coefficient in the product -1, 0, or 1 respectively. This gives you a branching factor of 3 each time you extend the length of the series, and 3^18 is starting to get unpleasantly large. But I only searched out to the 3^10 level, and then used those same sequences forwards and backwards for the high-order and low-order end of the polynomial, hunting for ones that joined up in the middle. So is there any reason to believe that (x-1)^3 is the optimal cofactor? While I was at it, I've also asked Mma to do the exhaustive search, factoring every height-1 polynomial of degree d for d<18. It has finished through 16 so far, and is working on 17 now, without finding anything where an irreducible factor has a coefficient *strictly* larger than the degree of the polynomial. If you're willing to have the coefficient *equal* to the degree, then (aside from degree 1), then the first two examples happen at degree 16: 1 + x + x^2 - x^3 + x^4 - x^5 - x^7 - x^8 - x^9 - x^10 - x^11 - x^12 + x^13 + x^14 + x^15 + x^16 = (x-1)^2 * (1 + 3*x + 6*x^2 + 8*x^3 + 11*x^4 + 13*x^5 + 15*x^6 + 16*x^7 + 16*x^8 + 15*x^9 + 13*x^10 + 10*x^11 + 6*x^12 + 3*x^13 + x^14) 1 + x + x^2 + x^3 - x^4 - x^5 - x^6 - x^7 - x^8 - x^9 - x^11 + x^12 - x^13 + x^14 + x^15 + x^16 = (x-1)^2 * (1 + 3*x + 6*x^2 + 10*x^3 + 13*x^4 + 15*x^5 + 16*x^6 + 16*x^7 + 15*x^8 + 13*x^9 + 11*x^10 + 8*x^11 + 6*x^12 + 3*x^13 + x^14) I'll let you know if the degree-17 search turns anything up. --Michael -- Forewarned is worth an octopus in the bush.
On Mon, Jul 11, 2011 at 4:37 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
On Sat, Jul 9, 2011 at 3:21 PM, Bill Gosper <billgosper@gmail.com> wrote:
Meanwhile, this is sort of interesting:
In[1154]:= Factor[-1 + x + x^2 + x^3 - x^4 + x^5 + x^7 + x^8 - x^10 - x^11 - x^12 - x^13 - x^14 - x^15 - x^16 - x^18 - x^19 - x^22 + x^23 + x^24 + x^25 + x^26 + x^27 + x^28 + x^29 + x^30 + x^31 + x^32 + x^33 - x^34 - x^35 - x^36 - x^37 - x^38]
Out[1154]= -(-1 + x)^3 (-1 - 2 x - 2 x^2 + 3 x^4 + 8 x^5 + 15 x^6 + 25 x^7 + 39 x^8 + 57 x^9 + 78 x^10 + 101 x^11 + 125 x^12 + 149 x^13 + 172 x^14 + 193 x^15 + 211 x^16 + 226 x^17 + 237 x^18 + 243 x^19 + 244 x^20 + 240 x^21 + 230 x^22 + 215 x^23 + 196 x^24 + 174 x^25 + 150 x^26 + 125 x^27 + 100 x^28 + 76 x^29 + 54 x^30 + 35 x^31 + 20 x^32 + 10 x^33 + 4 x^34 + x^35) --rwg
Inspired by this example, I wrote some Mma to look for polynomials which become height-1 when multiplied by (x-1)^3. My previous less-than-coherent mail was about doing this by hand for (x-1)^2, where I could just think about what multiplication and division by x-1 would do. For (x-1)^3, brute force seemed the wiser approach.
The best results from this approach are two polynomials of degree 18, each of which is (x-1)^3 times a degree-15 polynomial with a coefficient of 25 (!!):
-1 - x + x^2 + x^4 + x^5 + x^6 - x^7 + x^8 - x^10 - x^11 - x^13 + x^14 - x^15 + x^18 = (x-1)^3 * (1 + 4*x + 8*x^2 + 13*x^3 + 18*x^4 + 22*x^5 + 24*x^6 + 25*x^7 + 24*x^8 + 21*x^9 + 17*x^10 + 13*x^11 + 9*x^12 + 6*x^13 + 3*x^14 + x^15)
-1 - x + x^2 + x^4 + x^5 + x^6 - x^7 + x^8 - x^9 - x^11 + x^12 - x^13 - x^15 - x^16 + x^17 + x^18 = (x-1)^3 * (1 + 4*x + 8*x^2 + 13*x^3 + 18*x^4 + 22*x^5 + 24*x^6 + 25*x^7 + 24*x^8 + 22*x^9 + 19*x^10 + 16*x^11 + 12*x^12 + 8*x^13 + 4*x^14 + x^15)
(Well, there are only two genuinely different ones; you could read the coefficient lists backwards also.)
I searched for these by recursively extending sequences of coefficients to keep things height-1 after multiplication by (x-1)^3. That is, if the coefficient list begins (1, 4, 8), then the next coefficient must be 12, 13, or 14, in order to make the next coefficient in the product -1, 0, or 1 respectively. This gives you a branching factor of 3 each time you extend the length of the series, and 3^18 is starting to get unpleasantly large. But I only searched out to the 3^10 level, and then used those same sequences forwards and backwards for the high-order and low-order end of the polynomial, hunting for ones that joined up in the middle.
So is there any reason to believe that (x-1)^3 is the optimal cofactor?
While I was at it, I've also asked Mma to do the exhaustive search, factoring every height-1 polynomial of degree d for d<18. It has finished through 16 so far, and is working on 17 now, without finding anything where an irreducible factor has a coefficient *strictly* larger than the degree of the polynomial. If you're willing to have the coefficient *equal* to the degree, then (aside from degree 1), then the first two examples happen at degree 16:
1 + x + x^2 - x^3 + x^4 - x^5 - x^7 - x^8 - x^9 - x^10 - x^11 - x^12 + x^13 + x^14 + x^15 + x^16 = (x-1)^2 * (1 + 3*x + 6*x^2 + 8*x^3 + 11*x^4 + 13*x^5 + 15*x^6 + 16*x^7 + 16*x^8 + 15*x^9 + 13*x^10 + 10*x^11 + 6*x^12 + 3*x^13 + x^14)
1 + x + x^2 + x^3 - x^4 - x^5 - x^6 - x^7 - x^8 - x^9 - x^11 + x^12 - x^13 + x^14 + x^15 + x^16 = (x-1)^2 * (1 + 3*x + 6*x^2 + 10*x^3 + 13*x^4 + 15*x^5 + 16*x^6 + 16*x^7 + 15*x^8 + 13*x^9 + 11*x^10 + 8*x^11 + 6*x^12 + 3*x^13 + x^14)
I'll let you know if the degree-17 search turns anything up.
It finished overnight. I've found a total of nine genuinely different height-1 polynomials of degree 17 that have an irreducible factor of height 17, and none higher. Eight of them have cofactor (x-1)^2, and one has cofactor (x-1)^3. (Well, or (x+1), if you'd prefer, since you can do x->-x.) For the record, here are their coefficients in the natural compressed format: +00-0-+--++-+0+00- +0+++-------+-0+++ ++0+00------0+-+++ +++00-0-----+-0+++ +++0-+-----0-00+++ +++0-+-------+++0+ ++++---0----0+-+++ +++-+0----0---++++ +++-+0------00+0++ The top one on the list is the multiple of (x-1)^3. --Michael -- Forewarned is worth an octopus in the bush.
All right, one last message on this subject. Mma has finished an exhaustive search of the height-1 polynomials of degree 18. The maximal height of an irreducible factor is indeed 25, and it happens only twice -- the two examples I posted earlier, with cofactor (x-1)^3. (Of course you can change p(x) into -p(x) or p(-x) or into x^-18 p(1/x) or any subset, so when I say it happens twice, I really mean it happens 16 times.) In addition to the two height-25 cases there is one with height 23 (also a multiple of (x-1)^3), two of height 20 (one multiple of (x-1)^3 and one of (x-1)^2), and twelve of height 19 (all (x-1)^2). The complete list is below, for posterity. I'll save space by just listing the sequence of coefficients for the irreducible factors. Ye Olde List of Height-One Polynomials of Degree 18 With Irreducible Factors of Large Height, Being the Smallest Degree Having Irreducibles of Height Strictly Greater Than the Degree: Height 25: (x-1)^3 times {1, 3, 6, 9, 13, 17, 21, 24, 25, 24, 22, 18, 13, 8, 4, 1} (x-1)^3 times {1, 4, 8, 12, 16, 19, 22, 24, 25, 24, 22, 18, 13, 8, 4, 1} Height 23: (x-1)^3 times {1, 3, 5, 8, 11, 15, 19, 22, 23, 23, 21, 17, 12, 7, 3, 1} Height 20: (x-1)^3 times {1, 2, 4, 6, 9, 12, 15, 18, 20, 20, 19, 16, 12, 8, 4, 1} (x-1)^2 times {1, 3, 6, 9, 12, 14, 17, 19, 20, 20, 19, 17, 14, 10, 6, 3, 1} Height 19: (x-1)^2 times {1, 2, 4, 6, 9, 13, 16, 18, 19, 19, 18, 16, 13, 9, 6, 3, 1} (x-1)^2 times {1, 3, 4, 6, 9, 13, 16, 18, 19, 19, 18, 16, 13, 10, 6, 3, 1} (x-1)^2 times {1, 3, 5, 8, 10, 13, 16, 18, 19, 19, 18, 16, 13, 10, 6, 3, 1} (x-1)^2 times {1, 3, 5, 8, 11, 13, 16, 18, 19, 19, 18, 16, 13, 9, 6, 3, 1} (x-1)^2 times {1, 3, 5, 8, 11, 14, 16, 18, 19, 19, 18, 16, 13, 10, 6, 3, 1} (x-1)^2 times {1, 3, 6, 10, 13, 15, 16, 18, 19, 19, 18, 16, 13, 10, 6, 3, 1} (x-1)^2 times {1, 3, 6, 10, 13, 16, 18, 19, 19, 19, 18, 16, 13, 10, 6, 3, 1} (*) (x-1)^2 times {1, 3, 6, 8, 10, 13, 16, 18, 19, 19, 18, 16, 13, 9, 6, 3, 1} (x-1)^2 times {1, 3, 6, 8, 11, 13, 16, 18, 19, 19, 18, 16, 13, 10, 6, 3, 1} (x-1)^2 times {1, 3, 6, 8, 11, 14, 16, 18, 19, 19, 18, 16, 13, 9, 6, 3, 1} (x-1)^2 times {1, 3, 6, 9, 11, 13, 16, 18, 19, 19, 18, 16, 13, 9, 6, 3, 1} (x-1)^2 times {1, 3, 6, 9, 13, 16, 18, 19, 19, 18, 17, 15, 13, 10, 6, 3, 1} Note that the height-19 example labeled (*) is left-right symmetric, so fixed under one of the usual symmetries. The multiplied-out height-1 polynomial for that one is the pretty ++++-0---0---0-++++. --Michael On Tue, Jul 12, 2011 at 10:22 AM, Michael Kleber <michael.kleber@gmail.com>wrote:
On Mon, Jul 11, 2011 at 4:37 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
On Sat, Jul 9, 2011 at 3:21 PM, Bill Gosper <billgosper@gmail.com> wrote:
Meanwhile, this is sort of interesting:
In[1154]:= Factor[-1 + x + x^2 + x^3 - x^4 + x^5 + x^7 + x^8 - x^10 - x^11 - x^12 - x^13 - x^14 - x^15 - x^16 - x^18 - x^19 - x^22 + x^23 + x^24 + x^25 + x^26 + x^27 + x^28 + x^29 + x^30 + x^31 + x^32 + x^33 - x^34 - x^35 - x^36 - x^37 - x^38]
Out[1154]= -(-1 + x)^3 (-1 - 2 x - 2 x^2 + 3 x^4 + 8 x^5 + 15 x^6 + 25 x^7 + 39 x^8 + 57 x^9 + 78 x^10 + 101 x^11 + 125 x^12 + 149 x^13 + 172 x^14 + 193 x^15 + 211 x^16 + 226 x^17 + 237 x^18 + 243 x^19 + 244 x^20 + 240 x^21 + 230 x^22 + 215 x^23 + 196 x^24 + 174 x^25 + 150 x^26 + 125 x^27 + 100 x^28 + 76 x^29 + 54 x^30 + 35 x^31 + 20 x^32 + 10 x^33 + 4 x^34 + x^35) --rwg
Inspired by this example, I wrote some Mma to look for polynomials which become height-1 when multiplied by (x-1)^3. My previous less-than-coherent mail was about doing this by hand for (x-1)^2, where I could just think about what multiplication and division by x-1 would do. For (x-1)^3, brute force seemed the wiser approach.
The best results from this approach are two polynomials of degree 18, each of which is (x-1)^3 times a degree-15 polynomial with a coefficient of 25 (!!):
-1 - x + x^2 + x^4 + x^5 + x^6 - x^7 + x^8 - x^10 - x^11 - x^13 + x^14 - x^15 + x^18 = (x-1)^3 * (1 + 4*x + 8*x^2 + 13*x^3 + 18*x^4 + 22*x^5 + 24*x^6 + 25*x^7 + 24*x^8 + 21*x^9 + 17*x^10 + 13*x^11 + 9*x^12 + 6*x^13 + 3*x^14 + x^15)
-1 - x + x^2 + x^4 + x^5 + x^6 - x^7 + x^8 - x^9 - x^11 + x^12 - x^13 - x^15 - x^16 + x^17 + x^18 = (x-1)^3 * (1 + 4*x + 8*x^2 + 13*x^3 + 18*x^4 + 22*x^5 + 24*x^6 + 25*x^7 + 24*x^8 + 22*x^9 + 19*x^10 + 16*x^11 + 12*x^12 + 8*x^13 + 4*x^14 + x^15)
(Well, there are only two genuinely different ones; you could read the coefficient lists backwards also.)
I searched for these by recursively extending sequences of coefficients to keep things height-1 after multiplication by (x-1)^3. That is, if the coefficient list begins (1, 4, 8), then the next coefficient must be 12, 13, or 14, in order to make the next coefficient in the product -1, 0, or 1 respectively. This gives you a branching factor of 3 each time you extend the length of the series, and 3^18 is starting to get unpleasantly large. But I only searched out to the 3^10 level, and then used those same sequences forwards and backwards for the high-order and low-order end of the polynomial, hunting for ones that joined up in the middle.
So is there any reason to believe that (x-1)^3 is the optimal cofactor?
While I was at it, I've also asked Mma to do the exhaustive search, factoring every height-1 polynomial of degree d for d<18. It has finished through 16 so far, and is working on 17 now, without finding anything where an irreducible factor has a coefficient *strictly* larger than the degree of the polynomial. If you're willing to have the coefficient *equal* to the degree, then (aside from degree 1), then the first two examples happen at degree 16:
1 + x + x^2 - x^3 + x^4 - x^5 - x^7 - x^8 - x^9 - x^10 - x^11 - x^12 + x^13 + x^14 + x^15 + x^16 = (x-1)^2 * (1 + 3*x + 6*x^2 + 8*x^3 + 11*x^4 + 13*x^5 + 15*x^6 + 16*x^7 + 16*x^8 + 15*x^9 + 13*x^10 + 10*x^11 + 6*x^12 + 3*x^13 + x^14)
1 + x + x^2 + x^3 - x^4 - x^5 - x^6 - x^7 - x^8 - x^9 - x^11 + x^12 - x^13 + x^14 + x^15 + x^16 = (x-1)^2 * (1 + 3*x + 6*x^2 + 10*x^3 + 13*x^4 + 15*x^5 + 16*x^6 + 16*x^7 + 15*x^8 + 13*x^9 + 11*x^10 + 8*x^11 + 6*x^12 + 3*x^13 + x^14)
I'll let you know if the degree-17 search turns anything up.
It finished overnight. I've found a total of nine genuinely different height-1 polynomials of degree 17 that have an irreducible factor of height 17, and none higher. Eight of them have cofactor (x-1)^2, and one has cofactor (x-1)^3. (Well, or (x+1), if you'd prefer, since you can do x->-x.) For the record, here are their coefficients in the natural compressed format:
+00-0-+--++-+0+00- +0+++-------+-0+++ ++0+00------0+-+++ +++00-0-----+-0+++ +++0-+-----0-00+++ +++0-+-------+++0+ ++++---0----0+-+++ +++-+0----0---++++ +++-+0------00+0++
The top one on the list is the multiple of (x-1)^3.
--Michael
-- Forewarned is worth an octopus in the bush.
-- Forewarned is worth an octopus in the bush.
participants (2)
-
Bill Gosper -
Michael Kleber