Polynomials all of whose roots are rational - MathOverflow

Polynomials all of whose roots are rational

2012-05-18T13:17:23Z

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!

Answer by Felix Goldberg for Polynomials all of whose roots are rational

2012-05-18T13:48:05Z

Maybe this book has pertinent information:

http://www.springer.com/mathematics/algebra/book/978-3-540-40714-0?otherVersion=978-3-642-03979-9

Alas, I have no access to a copy now.

ALSO, MathSciNet has this paper:

MR1342405 Luo, Yong Chao Some criteria for polynomials with integer coefficients to have rational roots, and their applications. (Chinese. English, Chinese summary) Guizhou Shifan Daxue Xuebao Ziran Kexue Ban 12 (1994), no. 4, 21–30. 12D10

Alas, the paper was not reviewed, so I have no idea what it contained and if it was valid.

Answer by Robert Israel for Polynomials all of whose roots are rational

2012-05-18T17:33:19Z

Given a bound for the possible denominators, small enough intervals containing each root will each contain at most one candidate for a rational root, and it is easy to find that candidate (e.g. using continued fractions) and check whether it really is a root. It seems to me that this should all be possible to do in polynomial time.

Answer by Daniel m3 for Polynomials all of whose roots are rational

2012-05-18T17:52:06Z

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.

Answer by Aaron Meyerowitz for Polynomials all of whose roots are rational

2012-05-18T20:45:25Z

Random comments:

The rational root test might be good for finding all rational roots but less so if one is happy to abort as soon as an irrational root is found (i.e one not of the form $\frac{t}{a_0}$.

If $a_n=1$ then check if $\pm 1$ are roots. If so great! if not then you can factor $a_0$ searching for a factor less than $a_0^{1/n}$. There is some gain from looking further for very small integer divisors, but perhaps not much. If $a_0=1$ then factor $u^nf(1/u)$

This may not be so great if $a_0$ is huge. For example if we replace $f$ by $a_n^{n-1}f(u/a_n)$ to get a monic polynomial with constant term $a_0a_n^{n-1}$

Repeated roots can be tricky for some methods so one might wish to compute $f'$ and find the polynomial gcd since any repeated roots will be roots of that. In your case the gcd of $7x+5$ reveals a double root of $\frac{-5}{7}$ leaving $256x^3+144x^2-826x+51$

Given $f'$, even without bothering with the gcd, one is set to use Newton's method (or some other) to quickly find approximate real roots. Then given a somewhat accurate real root $r,$ one can see if it is close to a rational root. The continued fraction should have a convergent which is remarkably good. Seeing a root near $-0.7$ gives $-.7138457729$ after $5$ iterations. The convergents are $-2/3,-5/7,-227/318, -232/325, -5563/7793$ which gives two reasonable candidates. A couple more iterations would leave no doubt. Your example is not great for illustrating that because the "round off error" quickly gives the exact rational root (as a decimal) if it is of the form $\frac{t}{10^k}$ for $k$ small.

I was excited that Newton's method (although others might be better) returns rationals given rationals, however the denominators grow very quickly. However, the previous observation gives the idea of using Newton's method plus rounding to always get approximants of the form $\frac{t}{a_0}.$ That will quickly get to a root if there is one (I'd think.)

If f is a product of $n$ linear factors the same is true mod $m$ for any $m$. Famously, the converse is not true. However there are algorithms to factor mod $p$ and one failure tells you to stop. I recall methods to lift to factorizations mod $p^k$ but that is back to general integer factorization. Maybe that is easier if you already have linear factors though.

Answer by Brendan McKay for Polynomials all of whose roots are rational

2012-05-19T07:55:34Z

Robert Israel's comment about using Sturm sequences got me thinking about how it could be done using only the original polynomial $f(x)$ (assumed to have distinct rational zeros). If the degree is odd, it is easy to identify an interval in which the sign changes. If the degree is even, it is easy to find three points so that $f(x)$ is least at the middle point of the three, then golden section search will find a point where the polynomial is negative. (Golden section search finds a local minimum, and all local minima have negative $f(x)$ in this case.) Once an interval with a sign change is found, use binary search to find a root. Divide it out and repeat. I think that only a polynomial number of evaluations of $f(x)$ are required altogether, since all of the searches only need to continue to precision $1/a_0$.