7
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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\, .$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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