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