# How to determine whether a polynomial has integer roots?

A polynomial

$$f(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$$

where $a_{n-1}, a_0$ are known. How to determine whether polynomial $f$ has integer roots? Can we give a bound of $\max\{a_i \mid i=1,\dots,n-2\}$ and $\min\{a_i \mid i=1,\dots,n-2\}$ decide by $n,a_{n-1}$, and $a_0$ such that the polynomial roots are integers.

• See the earlier question, "Polynomials all of whose roots are rational." In particular, see the answer by Daniel m3 using Hensel's Lifting Lemma, and the comment by Mark Sapir suggesting this leads to a polynomial-time algorithm via LLL. – Joseph O'Rourke Dec 16 '16 at 13:21
• Are the $a_i$ integer numbers? – Pietro Majer Dec 16 '16 at 15:11
• @PietroMajer If they are not, the answer is negative. – Emil Jeřábek Dec 16 '16 at 15:28
• I imagine the question may be to get bounds on the coefficients here. – Pat Devlin Dec 16 '16 at 15:36

I'm not sure if I understand just what you're asking, but perhaps it is the following:

Suppose we know $a_0$ and $a_{n-1}$, and we know that $f(x)$ has only integer roots. Can we use this information to meaningfully bound the coefficients?

If that's what you're asking, then the answer is no. Consider for example the polynomial $$g(x) = x (x^2 - c^2)^{k},$$ where $c \in \mathbb{Z}$. Then this has $a_0 = a_{n-1} = 0$. But even for fixed $n$, the other coefficients are unbounded if you let $c$ be large.

## This part added in response to Timothy Chow's comment:

Timothy Chow made the suggestion that allowing $a_{0} = a_{n-1} = 0$ feels like cheating, and on reflection, I agree!

If we allow $a_0 = 0$, then we can't get any bound on the other coefficients

Namely, just consider any monic degree $n-2$ polynomial of the form $p(x) = x^{n-2} + b_{n-4} x^{n-4} + b_{n-5} x^{n-5} + \cdots + b_0$. Then look at the polynomial $x (x+a) p(x) = x^n + a x^{n-1} + a_{n-2} x^{n-2} + \cdots + a_1 x + 0$. This will have integer roots, and the coefficient $a_{n-1}$ is free to be any integer you like. Yet the other coefficients can be wild. For concreteness, consider this $$h(x) = x (x+a)(x^2 - c^2)^k,$$ which, for fixed $a$ and $k$, will have unbounded coefficients if you pick $c$ large enough [e.g., the sum of these coefficients is $h(1)$ which is unbounded].

If we disallow $a_0 = 0$, then we do get a bound

However! If we disallow the case $a_0 = 0$, then yes you can get a bound on the remaining coefficients. Namely, if $f(x)$ factors as $f(x) = \prod_{i} (x +r_i)$, then we know $a_0 = \prod_{i} r_i$. If none of the roots is $0$ (i.e., if $a_0 \neq 0$), then each root is at least $1$ in absolute value, and thus $|a_0|$ is an upper bound on every product of the form $\prod_{i \in S} |r_i|$. Therefore, we have

$$|a_{n-k}| = \left| \sum_{|S| = k} \prod_{i \in S} r_i \right| \leq \sum_{|S| = k} \prod_{i \in S} |r_i| \leq \sum_{|S| = k} |a_0| = {n \choose k} |a_0|.$$ This bound is tight of course by the polynomials $(x+1)^n$ and $(x-1)^n$. (This reminds me of Newton's inequalities, which probably can provide an alternate proof.)

• Somehow allowing $a_0=0$ feels like "cheating" to me. Can you modify your example to avoid that? More generally, is it true that for every choice of $a_{n-1}$ and $a_0$ there exist polynomials with only integer roots with unbounded coefficients? – Timothy Chow Dec 16 '16 at 21:05
• @TimothyChow, that's a really great question. Let me add a note to the above addressing that. – Pat Devlin Dec 16 '16 at 21:10