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

1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 9, 9, 11, 14, 16, 17, 25, 33, 39

Offset: 1

Author

Mike Speciner, Jun 29 2023

Keywords

• nonn
• hard
• more

Comments

We consider only polynomials with integer coefficients (Z[x]).

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.

Note that if we consider all factors, not just irreducible ones, then the resulting sequence would be bounded below by A114536.

Examples

			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.
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.
For n = 2, the height 1 degree 2 polynomials and their factorizations are
  x^2-x-1 irreducible,
  x^2-x = (x-1)x,
  x^2-x+1 irreducible,
  x^2-1 = (x-1)(x+1),
  x^2 = x^2,
  x^2+1 irreducible,
  x^2+x-1 irreducible,
  x^2+x = x(x+1),
  x^2+x+1 irreducible.
All the irreducible factors have height 1, so a(2) = 1.
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).
The height (maximum absolute value of the coefficients) of the product is 1, while the height of the final irreducible factor is 9.
No other height 1 degree 12 polynomial has an irreducible factor with larger height.
So a(12) = 9.
		

Links

• Mike Speciner, Corresponding height 1 polynomials

Programs

Python

from msmath.poly import polynomial as poly
def height(p) :
  """find the height, i.e. max abs coeff, of poly p"""
  return max(map(abs,p));
def height1(n) :
  """generate all height 1 polys of degree n"""
  for a in range(3**n) :
    p = [1];
    for i in range(n) :
      a,r = divmod(a,3);
      p.append(r-1);
    yield poly(*p);
def a(n) :
  """Return highest height of any irreducible factor of any degree n height 1 poly"""
  highest = (0,0);
  for p in height1(n) :
    f = p.factor();
    h = max(map(lambda f:(height(f),-f.degree),f));
    if highest < h:
      highest = h;
      best = sorted(f,key=len);
      best = {x:f[x] for x in best};
  return highest[0];

Extensions

a(20) from Mike Speciner, Jul 09 2025