|
%I #31 Sep 22 2023 11:27:57
%S 1,1,1,2,2,3,3,4,4,5,7,9,9,11,14,16,17,25,33
%N Maximum height of an irreducible factor of any degree-n polynomial of height 1.
%C We consider only polynomials with integer coefficients (Z[x]).
%C The sequence is increasing, since we can always multiply the best degree n-1 polynomial by x. I suspect (but haven't proven) that if we only considered polynomials with nonzero constant term, we'd get the same sequence.
%C Note that if we consider all factors, not just irreducible ones, then the resulting sequence would be bounded below by A114536.
%e We will assume that the coefficient of x^n is 1. (If not, just multiply by -1.) Similarly, we can insist that all the factors will also have high order coefficient 1.
%e For n = 1, all degree 1 polynomials are irreducible, so they are their own irreducible factors, and so all their irreducible factors have the same height as them. Thus a(1) = 1.
%e For n = 2, the height 1 degree 2 polynomials and their factorizations are
%e x^2-x-1 irreducible,
%e x^2-x = (x-1)x,
%e x^2-x+1 irreducible,
%e x^2-1 = (x-1)(x+1),
%e x^2 = x^2,
%e x^2+1 irreducible,
%e x^2+x-1 irreducible,
%e x^2+x = x(x+1),
%e x^2+x+1 irreducible.
%e All the irreducible factors have height 1, so a(2) = 1.
%e For n = 12, we have x^12-x^11+x^10+x^9-x^8+x^7-x^6+x^5+x^4+x^3-x+1 = (x+1)^2*(x^10-3x^9+6x^8-8x^7+9x^6-9x^5+8x^4-6x^3+5x^2-3x+1).
%e The height (maximum absolute value of the coefficients) of the product is 1, while the height of the final irreducible factor is 9.
%e No other height 1 degree 12 polynomial has an irreducible factor with larger height.
%e So a(12) = 9.
%o (Python)
%o from msmath.poly import polynomial as poly
%o def height(p) :
%o """find the height, i.e. max abs coeff, of poly p"""
%o return max(map(abs,p));
%o def height1(n) :
%o """generate all height 1 polys of degree n"""
%o for a in range(3**n) :
%o p = [1];
%o for i in range(n) :
%o a,r = divmod(a,3);
%o p.append(r-1);
%o yield poly(*p);
%o def a(n) :
%o """Return highest height of any irreducible factor of any degree n height 1 poly"""
%o highest = (0,0);
%o for p in height1(n) :
%o f = p.factor();
%o h = max(map(lambda f:(height(f),-f.degree),f));
%o if highest < h:
%o highest = h;
%o best = sorted(f,key=len);
%o best = {x:f[x] for x in best};
%o return highest[0];
%K nonn,hard,more
%O 1,4
%A _Mike Speciner_, Jun 29 2023
|
