Getting a bound on the coefficients of the factor polynomial

Question

Suppose $f(x):=a_0+a_1x+\cdots+a_nx^n$ is a polynomial in $\mathbb{Z}[x]$ and $|a_i|\leq M$ for each $i=0,\ldots ,n.$ Now suppose $g(x)$ is a factor of $f(x)$ in $\mathbb{Z}[x]$, then is it possible to get a bound on the coefficients of $g(x)$ in terms of $M$ i.e. if $g(x)=\sum_{i=0}^mb_ix^i$ then does there exist some $M^\prime $, which depends only on $M,n$ and $m$, such that $|b_i|\leq M^\prime$ for all $i=0,\ldots ,m$ ?

Answer 1

Gelfond's inequality is probably what you want here; see for example my book with Hindry, Diophantine Geometry: An Introduction, Proposition B.7.3. I'll state it for polynomials in $\mathbb{Z}[X_1,\ldots,X_m]$, although there's a version that's true over $\overline{\mathbb{Q}}$. The statement uses the projective height, so for a polynomial $f$ with coefficients $a_i\in\mathbb{Z}$, we let $$H(f) = \frac{\max|a_i|}{\gcd(a_i)}.$$ Then

Proposition B.7.3 (Gelfond's inequality) Let $f_1,\ldots,f_r\in \mathbb{Z}[X_1,\ldots,X_m]$, and for $1\le i\le m$, let $d_i$ denote the $X_i$ degree of $f_1f_2\cdots f_r$. Then $$ H(f_1)H(f_2)\cdots H(f_r) \le e^{d_1+\cdots+d_m}H(f_1f_2\cdots f_r). $$

For the OP's question, we have $f$ is divisible by $g$, say $f=gg'$, so $$ H(g) \le H(g)H(g') \le e^{\deg f}H(gg') = e^{\deg f}H(f). $$

Answer 2

Completely explicit bounds are given by Granville (bounding the coefficients of the divisor of a given polynomial, 1990, Monat. Math).

Answer 3

Define the height of a polynomial $f$ as $h(f)$, the max of the absolute values of its coefficients. Then (see e.g. Bombieri-Gubler Thm 1.7.2) $h(fg) \ge c(\deg f, \deg g)h(f)h(g)$, for some function $c(.,.)$ of the degrees. This gives what you want, except that $c$ is not very explicit.

Answer 4

Any such bound must depend on $n$ or $m$, not just $M$, since once can take for instance $f(x) = x^n-1$ (so $M = 1$). Then depending on $n$, the cyclotomic factor $\Phi_n(x)$ has coefficients as large as you like: for example $\Phi_{105}(x)$ has coefficients of modulus $2$, $\Phi_{385}(x)$ has coefficients of modulus $3$, for further references see OEIS sequence A013594 (http://oeis.org/A013594).

Answer 5

I do not see clearly how to use the information that the coefficients be integer numbers, apart the fact that $1\le |b_m|\le |a_n|$; therefore the following estimate is possibly non-optimal. However, it gives a simple and explicit bound, that also holds for complex coefficients.

By a classic estimate on the zeros of a polynomial, all (complex) roots of $f$ are bounded in modulus by $$1+\max_{0\le i < n}\frac{|a_i|}{|a_n|}\le M+1\, ,$$ because $|a_m|\ge1$. Since $b_i$ is the $i$-th elementary symmetric polynomial of some $m$ of the roots of $f$, times $b_m$, which is less that $M$ is size, we have

$$|b_i|\le M {m \choose i}(M+1)^i\, ,$$ so for instance $$\sum_{i=0}^m|b_i|\le M':=M(M+2)^m\, .$$

Answer 6

Obviously yes, since there are only finitely many such $f,g$ for each $M,n,m$.

Answer 7

The review Bounds on Factors of $\mathbb{Z}[x]$ by John Abbott gives various such bounds and shows that none of them is strictly better than the others.