I have two questions about the class of integer-coefficient polynomials all of whose roots are rational.
I asked this at MSE, but it attracted little interest (perhaps because it is not interesting!)
Q1. Is there some way to recognize such a polynomial from its coefficients $a_0, a_1, \ldots, a_n$?
I am aware of the rational-root theorem, which says that each rational root is of the form $\pm p/q$, where $p$ is a factor of $a_0$ and $q$ a factor of $a_n$.
Example.
The roots of
$$ 12544 x^5 + 24976 x^4 – 23994 x^3 – 51721 x^2 – 17080 x + 1275 $$
are
$$\lbrace
\frac{3}{2},
-\frac{5}{7},
-\frac{5}{7},
\frac{1}{16},
-\frac{17}{8}
\rbrace \;.
$$
Here $a_0 = 1275 = 3 \cdot 5 \cdot 17$
and $a_5 = 12544 = 2^8 \cdot 7^2$.
As Mark Bennet commented at MSE, perhaps an analog of Sturm's theorem would serve.
Q2. Has this class of polynomials been studied in its own right?
In other words, is this class interesting? I can see it has at least a monoid structure,
as the product of two such polynomials also has all rational roots.
These are naive questions, well out of my expertise. Thanks in advance for educating me!
Best Answer
It seems to me that the obvious algorithm via the rational root theorem is somewhat inefficient in at least two cases: $a_0$ or $a_n$ is BIG (so that we might not even be able to factor it), or they have A LOT of prime factors.
Instead, I believe the following algorithm based on Hensel's lifting lemma is more suited here.
Let $\displaystyle F = \sum_{i=0}^n a_i X^i \in \mathbb{Z}[X]$ be our polynomial, which we may assume to have no multiple root. Now pick a prime $p$ which does not divide $a_n$ and pass to $\mathbb{Z}/p \mathbb{Z}.$ If $F$ has no root over $\mathbb{Z}/p \mathbb{Z}$ (this requires $p$ checks), then $F$ has no rational root. (The fact we assumed $F$ has no multiple root over the integers does not necessarily mean it still has no multiple root over $\mathbb{Z}/p\mathbb{Z},$ but this can easily be circumvented by a suitable choice of $p.$) Otherwise, use Hensel's lemma to lift the roots $r_k$ from $\mathbb{Z}/p^k \mathbb{Z}$ to $\mathbb{Z}/p^{2k} \mathbb{Z},$ where $k$ is to be chosen later. (this works fine since $p \nmid F'(r_k)$) Finally, we need to get back to the integers, from a root $r_k \in \mathbb{Z}/p^k \mathbb{Z}$ (where we may choose $k$). To an element from $\mathbb{Z}/p^k\mathbb{Z}$, we associate the unique integer from its congruence class mod $p$ which is between $-p^k/2$ and $p^k/2.$ If we choose $k$ so large that $p^k$ is greater than $2 |a_n a_0|,$ then $a_nX - a_n/ba$ (which is a factor of $F$ if $bX-a \in \mathbb{Z}[X]$ is) remains unchanged by the above association, but $a_nX - a_n/ba = a_n(X - r_k)$ in $(\mathbb{Z}/p^k \mathbb{Z})[X]$ and $a_n(X - r_k) = a_nX - \rho$ where $\rho$ is obtained by the above association. We are done now: divide $a_nX - \rho$ (which is an integer multiple of $bX - a$) by $\gcd(a_n, \rho)$ and check the divisibility of $F$ by this reduced factor.