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

Offset

1,4

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.

Links

Table of n, a(n) for n=1..19.

Example

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.

Prog

(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];

Crossrefs

Sequence in context: A358151 A152162 A030699 * A366387 A083802 A325691

Adjacent sequences: A363956 A363957 A363958 * A363960 A363961 A363962

Keyword

nonn,hard,more

Author

Mike Speciner, Jun 29 2023

Status

approved