MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is inspired by this question. Let $f(x)=a_nx^n+...+a_0$ be a polynomial with rational coefficients. The sandard procedure of finding a rational root $p/q$ involves checking all $p$ that divide $a_0$ and all $q$ that divide $a_0$. This is not very complicated but involves factoring $a_0$ and $a_n$. The factoring problem is not known to be in P. If $n\le 4$, then the fact that the group $S_4$ is solvable and the well known formulas for roots of polynomials of degree $\le 4$ give easy polynomial time algorithm of finding rational roots.

Question Is the problem of finding a rational root of $f(x)$ in P for every $n$ (say, for $n=5$)?

Update 1 After I posted the question, I noticed an answer by Robert Israel to the previous question (of Joseph O'Rourke). That could give an answer to my question but I am still not sure how one can avoid factoring numbers $a_0,a_n$.

Update 2 Robert Israel's explanations (see his comment here ) convince me that his algorithm of checking whether a polynomial has a rational root (all roots rational) runs in polynomial time.

I removed Question 2 so that I can accept Michael Stoll's answer. I will post Question 2 as a separate question.

share|cite|improve this question
Some possible answers (by Robert Israel and 'Daniel m3') have appeared under the prior question ("Polynomials all of whose roots are rational") that Mark cites. – Joseph O'Rourke May 18 '12 at 18:12
Yes, and in fact Robert Israel answered Question 1 almost at the same time I posted it here. – Mark Sapir May 18 '12 at 22:05
up vote 8 down vote accepted

Didn't Lenstra, Lenstra and Lovász in their famous LLL paper prove that factorization of polynomials over $\mathbb Q$ can be done in polynomial time? You get a rational root if and only if there is a factor of degree 1, and the polynomial has only rational roots if and only if all factors have degree 1.

Lenstra, A.K.; Lenstra, H.W.jun.; Lovász, László: Factoring polynomials with rational coefficients. (English) Math. Ann. 261, 515-534 (1982).

share|cite|improve this answer
@Michael: I did not know this paper, unfortunately. Thank you! Looks like their algorithm does answer question 1 affirmatively. – Mark Sapir May 18 '12 at 18:29
What about the constant polynomials? – Steve Huntsman May 18 '12 at 19:08
@Steve: What about them? Most constant polynomials do not have roots. – Mark Sapir May 18 '12 at 20:50
[slaps head sheepishly] – Steve Huntsman May 18 '12 at 21:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.