6
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented May 18, 2012 at 18:12
  • $\begingroup$ Yes, and in fact Robert Israel answered Question 1 almost at the same time I posted it here. $\endgroup$
    – user6976
    Commented May 18, 2012 at 22:05

2 Answers 2

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ @Michael: I did not know this paper, unfortunately. Thank you! Looks like their algorithm does answer question 1 affirmatively. $\endgroup$
    – user6976
    Commented May 18, 2012 at 18:29
  • 1
    $\begingroup$ What about the constant polynomials? $\endgroup$
    – Steve Huntsman
    Commented May 18, 2012 at 19:08
  • 1
    $\begingroup$ @Steve: What about them? Most constant polynomials do not have roots. $\endgroup$
    – user6976
    Commented May 18, 2012 at 20:50
  • 4
    $\begingroup$ [slaps head sheepishly] $\endgroup$
    – Steve Huntsman
    Commented May 18, 2012 at 21:07
3
$\begingroup$

You do not need the full power of LLL algorithm for finding rational roots. In particular, Berlekamp-Zassenhaus algorithm exponential-time algorithm to compute the irreducible factorization can be used to get a polynomial-time algorithm for finding rational roots: The exponential part of this algorithm is the recombination of different modular factors to build true factors, but no such recombination is needed to build the linear factors.

A complete description and analysis of such an algorithm has been given by Loos in 1983:

Loos, R. Computing Rational Zeros of Integral Polynomials by P-Adic Expansion. SIAM Journal on Computing 12, no. 2 (May 1, 1983): 286–93. doi:10.1137/0212017.

Improve this answer
$\endgroup$

You must log in to answer this question.