Polynomials all of whose roots are rational - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T03:15:14Z http://mathoverflow.net/feeds/question/97307 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational Polynomials all of whose roots are rational Joseph O'Rourke 2012-05-18T13:17:23Z 2012-05-19T07:55:34Z <p>I have two questions about the class of integer-coefficient polynomials all of whose roots are rational. I asked <a href="http://math.stackexchange.com/questions/146288/" rel="nofollow">this at MSE</a>, but it attracted little interest (perhaps because it is not interesting!)</p> <p><b>Q1</b>. Is there some way to recognize such a polynomial from its coefficients $a_0, a_1, \ldots, a_n$?</p> <p>I am aware of the <a href="http://en.wikipedia.org/wiki/Rational_root_theorem" rel="nofollow">rational-root theorem</a>, 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$.</p> <p><em>Example</em>. 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$.</p> <p>As Mark Bennet commented at MSE, perhaps an analog of <a href="http://en.wikipedia.org/wiki/Sturm%27s_theorem" rel="nofollow">Sturm's theorem</a> would serve.</p> <p><b>Q2</b>. Has this class of polynomials been studied in its own right?</p> <p>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.</p> <p>These are naive questions, well out of my expertise. Thanks in advance for educating me!</p> http://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational/97310#97310 Answer by Felix Goldberg for Polynomials all of whose roots are rational Felix Goldberg 2012-05-18T13:48:05Z 2012-05-18T14:42:20Z <p>Maybe this book has pertinent information:</p> <p><a href="http://www.springer.com/mathematics/algebra/book/978-3-540-40714-0?otherVersion=978-3-642-03979-9" rel="nofollow">http://www.springer.com/mathematics/algebra/book/978-3-540-40714-0?otherVersion=978-3-642-03979-9</a></p> <p>Alas, I have no access to a copy now.</p> <p>ALSO, MathSciNet has this paper:</p> <p>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</p> <p>Alas, the paper was not reviewed, so I have no idea what it contained and if it was valid.</p> http://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational/97326#97326 Answer by Robert Israel for Polynomials all of whose roots are rational Robert Israel 2012-05-18T17:33:19Z 2012-05-18T17:33:19Z <p>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.</p> http://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational/97331#97331 Answer by Daniel m3 for Polynomials all of whose roots are rational Daniel m3 2012-05-18T17:52:06Z 2012-05-18T18:13:03Z <p>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.</p> <p>Instead, I believe the following algorithm based on <a href="http://en.wikipedia.org/wiki/Hensel%27s_lemma" rel="nofollow">Hensel's lifting lemma</a> is more suited here.</p> <p>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.</p> http://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational/97351#97351 Answer by Aaron Meyerowitz for Polynomials all of whose roots are rational Aaron Meyerowitz 2012-05-18T20:45:25Z 2012-05-18T20:45:25Z <p>Random comments:</p> <p>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}$.</p> <p>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)$</p> <p>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}$</p> <p>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$</p> <p>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.</p> <p>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.)</p> <p>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.</p> http://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational/97379#97379 Answer by Brendan McKay for Polynomials all of whose roots are rational Brendan McKay 2012-05-19T07:55:34Z 2012-05-19T07:55:34Z <p>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$.</p>