12
$\begingroup$

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!

Improve this question
$\endgroup$
15
  • 3
    $\begingroup$ @Joseph: Why is the rational-root theorem not enough? It gives a relatively fast algorithm. What kind of characterization do you want? $\endgroup$
    – user6976
    Commented May 18, 2012 at 13:34
  • 1
    $\begingroup$ Your questions are about rational fully-factorizable polynoms, and I must admit that I don't know more than what you said about them. For question Q2, but for real polynoms, the derivative of a fully-factorizable polynom is also fully-factorizable. Is it the kind of results your after? $\endgroup$
    – Julien Puydt
    Commented May 18, 2012 at 13:54
  • $\begingroup$ @Mark: My understanding is that that theorem gives the form of possible rational roots, but does not tell you that all the roots will be rational... $\endgroup$
    – Joseph O'Rourke
    Commented May 18, 2012 at 13:55
  • $\begingroup$ @Julien: Yes, exactly, structural theorems giving properties of the whole class. $\endgroup$
    – Joseph O'Rourke
    Commented May 18, 2012 at 13:57
  • 1
    $\begingroup$ This is a naive question: is this equivalent to the condition that the Galois group is trivial? $\endgroup$
    – Bruce Westbury
    Commented May 18, 2012 at 15:16

5 Answers 5

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ (I fixed the broken link.) $\endgroup$
    – Joseph O'Rourke
    Commented May 18, 2012 at 18:13
  • $\begingroup$ I am confused. In your first step you either have to factor $a_n$ (to see that $p$ does not divide it), or take $p$ so large that it cannot divide $a_n,$ in which case your $p$ checks will kill you, not to mention finding the requisite large prime. Admittedly, doing something more sensible, like Berlekamp's factoring algorithm will get you back to (probabilistic) polynomial time, but I am guessing this will be be pretty bad in practice. $\endgroup$
    – Igor Rivin
    Commented May 18, 2012 at 18:18
  • 2
    $\begingroup$ I think this will lead to a polynomial time algorithm because that is what LLL do in the paper Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), no. 4, 515–534. $\endgroup$
    – user6976
    Commented May 18, 2012 at 19:13
  • 1
    $\begingroup$ @Igor, if you need a prime that doesn't divide an $N$-digit number, it suffices (for $N>10$) to look among the first $N$ primes. $\endgroup$
    – Barry Cipra
    Commented May 18, 2012 at 22:38
  • 1
    $\begingroup$ It does not take $p$ checks to determine if $f$ has roots in $\mathbb{F}_p$. Compute $GCD(f, t^p-t)$ using the Euclidean algorithm, with the first computation of $t^p-t \bmod f$ done by repeated squaring. This takes something like $(\deg f)^2 \log p$ steps, so it beats $(\deg f) p$ unless $p$ is very small. $\endgroup$
    – David E Speyer
    Commented Dec 16, 2016 at 13:36
9
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @Robert: I already posted a new question mathoverflow.net/questions/97329/… . Your answer seems promising but how are you going to avoid factorization of $a_n$ and $a_0$? $\endgroup$
    – user6976
    Commented May 18, 2012 at 17:48
  • $\begingroup$ The denominator is a factor of $a_n$, so it is at most $a_n$. For any two distinct rationals $p/q$, $p'/q'$ with $|q|, |q'| \le a_n$, $|p/q - p'/q'| \ge 1/(q q') \ge 1/a_n^2$. So you just need an interval of length $< 1/a_n^2$ around each root. $\endgroup$
    – Robert Israel
    Commented May 18, 2012 at 19:22
  • $\begingroup$ Suppose $a_n$ is 1, so we are looking at the integer roots (in fact we can always assume that) how can you avoid factoring $a_0$? $\endgroup$
    – user6976
    Commented May 18, 2012 at 19:40
  • $\begingroup$ I guess you are then localize the roots enough so that there are at most one integer in each interval? Can it be done in polynomial time? $\endgroup$
    – user6976
    Commented May 18, 2012 at 19:41
  • 1
    $\begingroup$ Any integer root is at most $|a_0|$. WLOG we may assume the roots are distinct (otherwise divide by the gcd of the polynomial and its derivative). Construct the Sturm sequence of the polynomial, and bisect the interval ($O(n \log |a_0|)$ times until you isolate all the roots in intervals of length $1$. $\endgroup$
    – Robert Israel
    Commented May 18, 2012 at 21:01
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Felix: That paper title seems quite relevant, although I don't yet see how to access the English summary... $\endgroup$
    – Joseph O'Rourke
    Commented May 18, 2012 at 14:04
  • 2
    $\begingroup$ @Joseph and Felix: This book does not seem to have any relevant information. The book is quite good, though! $\endgroup$
    – user6976
    Commented May 18, 2012 at 15:49
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Aaron: Thanks for your illuminating thoughts. I have to admit that my example was chosen quite randomly, rather than to illustrate a particular point, so I am not surprised that it "is not great for illustrating" $X$. :-) $\endgroup$
    – Joseph O'Rourke
    Commented May 19, 2012 at 1:58
  • 1
    $\begingroup$ I just got a kick out of the fact that exact rational numbers explode: $1/10 \mapsto 133933/2049550 \mapsto 203135852565605401626332803/3249200102395371629529717250$ so I went to middling accuracy reals and got $0.1 \mapsto 0.065347515 \mapsto 0.062518727 \mapsto 0.06250000$ which is a root. $\endgroup$
    – Aaron Meyerowitz
    Commented May 19, 2012 at 4:54
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .