[math-fun] more polynomial factor heights
From 19 Aug '05 math-fun: "Apropos the cyclotomic discussion, I assume everybody knows about the 2s in factor(x^105-1). What is the lowest degree polynomial with coeffs in {-1,0,1} with a coeff of 2 in its irreducible factorization? --rwg" From 8 May 09:"rwg>> Puzzle: find a trinomial with maximal |coefficient| < some coefficient of >> a(n irreducible) factor. > Edwin Clark> > x^70-x^35+1 has irreducible factor > > x^48-x^47+x^46+x^43-x^42+2*x^41-x^40+x^39+x^36-x^35+x^34-x^33+x^32 > -x^31-x^28-x^26-x^24-x^22-x^20-x^17+x^16-x^15+x^14-x^13+x^12+x^9 > -x^8+2*x^7-x^6+x^5+x^2-x+1 > > Note the coefficient of x^41 and also of x^7 is 2. Right, equivalently x^70+x^35+1 = (x^(3*5*7)-1)/(x^(5*7)-1). More surprising (to me), your factor/.x->-x, 1+x+x^2-x^5-x^6 -2*x^7 -x^8-x^9+x^12+x^13+x^14+x^15+x^16+x^17-x^20-x^22-x^24-x^26 -x^28+x^31+x^32+x^33+x^34+x^35+x^36-x^39-x^40 -2*x^41 -x^42-x^43+x^46+x^47+x^48, divides x^245 + x^70 + 1. I.e., (x^2+x+1)*(x^5-x^4+x^2-x+1) = x^7+x^2+1. > JamesB> > 2*x^5 - 5*x^2 + 3 = (2*x^3 + 4*x^2 + 6*x + 3)*(x-1)^2 > > 5 < 6. > > Jim Buddenhagen > Wow, I missed that one! --rwg"
My searchware refuses to find Michael Kleber's solution of a related puzzle. 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
On Wed, Jul 6, 2011 at 5:29 AM, Bill Gosper <billgosper@gmail.com> wrote:
From 19 Aug '05 math-fun: "Apropos the cyclotomic discussion, I assume everybody knows about the 2s in factor(x^105-1). What is the lowest degree polynomial with coeffs in {-1,0,1} with a coeff of 2 in its irreducible factorization? --rwg"
In the interest of completeness, my gmail query "from:me to:math-fun cyclotomic" turned up my solution: (1-x)(1+2x+x^2+x^3+x^4+...+x^n) will, of course, only have {-1,0,1} coeffs.
Irreducibility fails for n=2, but the n=3 example x^4+x^2-x-1 works. (I'll let you dispatch degree 3 by hand yourself :-).
--Michael Kleber
From 8 May 09:"rwg>> Puzzle: find a trinomial with maximal |coefficient| < some coefficient of >> a(n irreducible) factor. > Edwin Clark> > x^70-x^35+1 has irreducible factor > > x^48-x^47+x^46+x^43-x^42+2*x^41-x^40+x^39+x^36-x^35+x^34-x^33+x^32 > -x^31-x^28-x^26-x^24-x^22-x^20-x^17+x^16-x^15+x^14-x^13+x^12+x^9 > -x^8+2*x^7-x^6+x^5+x^2-x+1 > > Note the coefficient of x^41 and also of x^7 is 2. Right, equivalently x^70+x^35+1 = (x^(3*5*7)-1)/(x^(5*7)-1). More surprising (to me), your factor/.x->-x, 1+x+x^2-x^5-x^6 -2*x^7 -x^8-x^9+x^12+x^13+x^14+x^15+x^16+x^17-x^20-x^22-x^24-x^26 -x^28+x^31+x^32+x^33+x^34+x^35+x^36-x^39-x^40 -2*x^41 -x^42-x^43+x^46+x^47+x^48, divides x^245 + x^70 + 1. I.e., (x^2+x+1)*(x^5-x^4+x^2-x+1) = x^7+x^2+1. > JamesB> > 2*x^5 - 5*x^2 + 3 = (2*x^3 + 4*x^2 + 6*x + 3)*(x-1)^2 > > 5 < 6. > > Jim Buddenhagen > Wow, I missed that one! --rwg"
My searchware refuses to find Michael Kleber's solution of a related puzzle.
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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
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:
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
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 -- Forewarned is worth an octopus in the bush.
participants (2)
-
Bill Gosper -
Michael Kleber