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.