11
$\begingroup$

Suppose we are given a rational function with numerator and denominator being polynomials with integer coefficients. Is there an efficient algorithm for finding all integers arguments at which the function takes integer values?

In other words, for given polynomials $F(x)$ and $G(x)$ with integer coefficients, how to compute efficiently all such integers $m$ that $G(m)$ divides $F(m)$ ?

I've developed a rather straight forward approach to this problem at http://list.seqfan.eu/pipermail/seqfan/2010-April/004339.html but I suspect it is far from optimal.

$\endgroup$
13
  • 1
    $\begingroup$ The reason this problem is messy is that G(x) need not have leading coefficient a unit, so I think some factorization of integers is unavoidable. Where do you think your approach can be improved? $\endgroup$ Jul 1, 2010 at 16:39
  • 8
    $\begingroup$ I don't know what you mean by "compute efficiently", but if $F(x)$ is a constant $N$, and $G(x)=x$, then you're asking how to compute efficiently all the factors of $N$, and this is pretty tough to do efficiently for most reasonable interpretations of the word, as far as I know. $\endgroup$ Jul 1, 2010 at 16:48
  • 1
    $\begingroup$ Qiaochu, Kevin, good points. Let us assume that there is small number of solutions and the size of $m$ is reasonable so that we know its complete integer factorization. The case of $G(x)=x$ and $F(x)=N$ is too extreme from this perspective. Usually, $m$ is a number with large number of divisors, only a small fraction of which leads to solutions. And I don't like the idea of brute-forcing them all. $\endgroup$ Jul 1, 2010 at 17:06
  • 1
    $\begingroup$ @Kevin, Qiaochu: It is still very interesting to find an algorithm with complexity exponential in coefficients but polynomial in degree. I have not seen something of this sort before. $\endgroup$ Jul 1, 2010 at 18:06
  • 1
    $\begingroup$ cf. also my reply to MO question 66873:mathoverflow.net/questions/66873/67202#67202 $\endgroup$ Nov 26, 2012 at 22:07

1 Answer 1

3
$\begingroup$

Some closely related (but not algorithmic) results are discussed in this paper of Corvaja and Zannier -- they have a number of other papers over the last few years on the same subject.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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