4

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$ ?

pritam
  • 10,157
  • Are $n$ and $m$ fixed, or you allow dependence on these parameters? – Davide Giraudo Oct 03 '12 at 15:38
  • It is quite clear that M' =< M. – mick Oct 03 '12 at 15:40
  • Yes $M^\prime$ may depend on $n$ and $m$ – pritam Oct 03 '12 at 15:42
  • If you take x = 1 and factor , what can you conclude ? – mick Oct 03 '12 at 15:42
  • @mick: taking $x=1$, absolute value of the sum of the coefficients of $g$ is less than the absolute value of the sum of the coefficients of $f$ which is less than $nM$, then ? – pritam Oct 03 '12 at 15:50
  • @ pritam :

    Assume all coefficients to be positive.

    if you factor f(x) into g(x)h(x) and x=1 then what can you say about the sum of the coefficients of the smallest of g(x) and h(x) ?

    Suppose f(1) = 100 and f(1) = g(1)h(1). If h(1) < g(1) you can conclude something.

     – mick Oct 03 '12 at 15:58
  • @mick: I am not getting you, can you give me the complete answer and why should I assume that all the coefficients are positive ? – pritam Oct 03 '12 at 16:15
  • h(1) is at most 10. As for negative coefficients that makes the problem somewhat harder. – mick Oct 03 '12 at 16:20
  • Simul-posted, without notice, to MathOverflow, http://mathoverflow.net/questions/108726/getting-a-bound-on-the-coefficients-of-the-factor-polynomial --- don't do that. – Gerry Myerson Oct 04 '12 at 08:48

1 Answers1

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.

Andrei Kh
  • 2,569