What algorithm can we use to find all integer roots of a polynomial $f(x)$ with integer coefficients?
I observe that Sage can find the roots within a few seconds even when all coefficients of $f(x)$ are very large. How is it able to do that?
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ Are you looking for an algorithm to return an integer root of a given polynomial? If yes, that is undecidable and the question is off-topic here. You can ask it on Computer Science which has a broader scope. $\endgroup$– KavehJul 18, 2013 at 14:13
-
7$\begingroup$ Hold on. Why does being undecidable make the question off-topic? This is a legitimate research-level question. $\endgroup$– JeffεJul 18, 2013 at 14:15
-
2$\begingroup$ So, then, how does Sage do it? Being undecidable—even being well-known to be undecidable—does not make the problem theoretically uninteresting. Theoretical computer scientists solve undecidable problems all the time — see, for example, all of computer-aided verification. $\endgroup$– JeffεJul 18, 2013 at 14:31
-
11$\begingroup$ Kaveh, what you are saying is not true. What is undecidable is solvability of Diophantine equations with many variables (so that there are readily infinitely many real solutions and one is searching for an integer/rational one). But this question is about a uni-variate polynomial $f(x)$, which is of course decidable (if $f(x)$ is of degree $d$, there are up to $d$ roots and one can check which one is an integer). $\endgroup$– Mahdi CheraghchiJul 18, 2013 at 15:04
-
1$\begingroup$ @Pratik You don't need Gröbner bases in the univariate case. $\endgroup$– Yuval FilmusJul 18, 2013 at 17:56
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
4
Assuming that the coefficients of $f$ are integers or rationals and that you want integer roots, the simplest approach is to use the integer or rational root theorem. See http://en.wikipedia.org/wiki/Rational_root_theorem As noted by D.W., this might be problematic if the constant coefficient is hard to factor (see also https://math.stackexchange.com/questions/123018/polynomial-and-integer-roots)
In any case, the Sage documentation clearly explains how they are doing the root search: "The next method, which is used if K is an integral domain, is to attempt to factor the polynomial. If this succeeds, then for every degree-one factor a*x+b, we add -b/a as a root (as long as this quotient is actually in the desired ring)." See http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html.
So your question becomes How do they efficiently factor polynomials with integer coefficients ? Apparently, Sage is calling NTL to do that (see http://www.shoup.net/ntl/doc/ZZXFactoring.txt for NTL details).
If you want an asymptotically efficient method, you could refer to the method of Lenstra, Lenstra and Lovasz (https://openaccess.leidenuniv.nl/handle/1887/3810).
-
1$\begingroup$ Thanks for the helpful hint! Fascinating. Might you be willing to edit your answer to elaborate on how to turn this into an algorithm, and what its running time is? Is the worst-case running time exponential (because it can take subexponential time to factor, and then there might be exponentially many divisors of the leading and trailing coefficient)? If so, are there better algorithms, or is this about the best one can do? Also, doesn't this approach find only the rational roots, but not irrational roots? $\endgroup$– D.W.Jul 18, 2013 at 18:51
-
$\begingroup$ Rereading the question and seeing that you interpret it differently, I am no longer completely sure, but it seemed clear to me and to some commenters that the question asks about integer roots. Don't you read it that way ? $\endgroup$– minarJul 18, 2013 at 18:57
-
$\begingroup$ @minar, you are right. Now that I re-read the question, it does seem that way. I must have read the question too quickly. (I initially misinterpreted the question as implying that we want all roots of a polynomial with integer coefficients, but on re-reading the question, that seems like a misinterpretation.) $\endgroup$– D.W.Jul 19, 2013 at 0:11
-
2