Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. 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,n$ and $m$, such that $|b_i|\leq M^\prime$ for all $i=0,\ldots ,m$ ?

share|improve this question
1  
Simul-posted, without notice, to MathStackExchange, math.stackexchange.com/questions/206637/… --- don't do that. –  Gerry Myerson Oct 4 '12 at 8:48

6 Answers 6

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). $$

share|improve this answer

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.

share|improve this answer

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}^n|b_i|\le M':=M(M+2)^n\, .$$

share|improve this answer

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

share|improve this answer

Any such bound will depend only on $n$ and $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).

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.