login
A363959
Maximum height of an irreducible factor of any degree-n polynomial of height 1.
0
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.
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
KEYWORD
nonn,hard,more
AUTHOR
Mike Speciner, Jun 29 2023
STATUS
approved