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$, such that $|b_i|\leq M^\prime$ for all $i=0,\ldots ,m$ ?
Getting a bound on the coefficients of the factor polynomial
4
$\begingroup$
polynomials
-
0Simul-posted, without notice, to MathOverflow, http://mathoverflow.net/questions/108726/getting-a-bound-on-the-coefficients-of-the-factor-polynomial --- don't do that. – 2012-10-04
1 Answers
3
Here is one (but it depends on $M$ and $n$):
$||g(x)||_{\infty} \leq 2^n*\sqrt{n+1}*||f(x)||_{\infty}$
This bound (which is very huge) is often used for factoring polynomials using Hensel lifting. It is called the Mignotte-Bound.
See "Maurice Mignotte. Mathematics for Computer Algebra. Springer- Verlag, New York, 1991" for the discussion of this bound.