cp's OEIS Frontend

A363959 Maximum height of an irreducible factor of any degree-n polynomial of height 1.

%I A363959 #38 Jul 14 2025 21:18:42
%S A363959 1,1,1,2,2,3,3,4,4,5,7,9,9,11,14,16,17,25,33,39
%N A363959 Maximum height of an irreducible factor of any degree-n polynomial of height 1.
%C A363959 We consider only polynomials with integer coefficients (Z[x]).
%C A363959 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 A363959 Note that if we consider all factors, not just irreducible ones, then the resulting sequence would be bounded below by A114536.
%H A363959 Mike Speciner, <a href="/A363959/a363959.out.txt">Corresponding height 1 polynomials</a>
%e A363959 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 A363959 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 A363959 For n = 2, the height 1 degree 2 polynomials and their factorizations are
%e A363959   x^2-x-1 irreducible,
%e A363959   x^2-x = (x-1)x,
%e A363959   x^2-x+1 irreducible,
%e A363959   x^2-1 = (x-1)(x+1),
%e A363959   x^2 = x^2,
%e A363959   x^2+1 irreducible,
%e A363959   x^2+x-1 irreducible,
%e A363959   x^2+x = x(x+1),
%e A363959   x^2+x+1 irreducible.
%e A363959 All the irreducible factors have height 1, so a(2) = 1.
%e A363959 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 A363959 The height (maximum absolute value of the coefficients) of the product is 1, while the height of the final irreducible factor is 9.
%e A363959 No other height 1 degree 12 polynomial has an irreducible factor with larger height.
%e A363959 So a(12) = 9.
%o A363959 (Python)
%o A363959 from msmath.poly import polynomial as poly
%o A363959 def height(p) :
%o A363959   """find the height, i.e. max abs coeff, of poly p"""
%o A363959   return max(map(abs,p));
%o A363959 def height1(n) :
%o A363959   """generate all height 1 polys of degree n"""
%o A363959   for a in range(3**n) :
%o A363959     p = [1];
%o A363959     for i in range(n) :
%o A363959       a,r = divmod(a,3);
%o A363959       p.append(r-1);
%o A363959     yield poly(*p);
%o A363959 def a(n) :
%o A363959   """Return highest height of any irreducible factor of any degree n height 1 poly"""
%o A363959   highest = (0,0);
%o A363959   for p in height1(n) :
%o A363959     f = p.factor();
%o A363959     h = max(map(lambda f:(height(f),-f.degree),f));
%o A363959     if highest < h:
%o A363959       highest = h;
%o A363959       best = sorted(f,key=len);
%o A363959       best = {x:f[x] for x in best};
%o A363959   return highest[0];
%K A363959 nonn,hard,more
%O A363959 1,4
%A A363959 _Mike Speciner_, Jun 29 2023
%E A363959 a(20) from _Mike Speciner_, Jul 09 2025