Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Are $n$ and $m$ fixed, or you allow dependence on these parameters? –  Davide Giraudo Oct 3 '12 at 15:38
    
It is quite clear that M' =< M. –  mick Oct 3 '12 at 15:40
    
Yes $M^\prime$ may depend on $n$ and $m$ –  pritam Oct 3 '12 at 15:42
    
If you take x = 1 and factor , what can you conclude ? –  mick Oct 3 '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 3 '12 at 15:50

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.