11

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.

Max Alekseyev
  • 30,425
  • 1
    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? – Qiaochu Yuan Jul 01 '10 at 16:39
  • 8
    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. – Kevin Buzzard Jul 01 '10 at 16:48
  • 1
    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.

     – Max Alekseyev Jul 01 '10 at 17:06
  • 1
    @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. – Dror Speiser Jul 01 '10 at 18:06
  • @Dror: I read it and then observed that it seemed to say "my method leads to a problem involving factorization" and my example was just to clarify that the question was basically equivalent to factorization. I take your point about being polynomial in degree---but I guess this is already what his method gives. – Kevin Buzzard Jul 01 '10 at 18:31
  • You could change the problem to finding values of m for which [F(x) - m.G(x)]=0 can be factorized. The your question is related to http://mathoverflow.net/questions/30072/ – SandeepJ Jul 01 '10 at 19:27
  • @Kevin: Unfortunately, this method doesn't seem to be polynomial in the degree just yet, since one has to factor numbers exponential in the degree. – Dror Speiser Jul 01 '10 at 20:23
  • Let's not focus on integer factorization - assume that it can be done easily. If so, the remaining bottleneck of my approach is that $m$ typically has huge number of divisors. Is there a way to avoid iterating over each of them? – Max Alekseyev Jul 01 '10 at 20:38
  • @Max: Solve mod each prime divisor, then try to lift combinations using Chinese Remainder Theorem. Also, random numbers don't tend to have huge numbers of divisors. – Dror Speiser Jul 01 '10 at 21:16
  • @Dror: I don't see how to "solve mod each prime divisor" here. And $m$ is far from being a random number. Computational experiments (at least for one particular problem that I was solving) suggest that it is often an integer with huge number of small prime divisors. – Max Alekseyev Jul 02 '10 at 05:02
  • @Max: You can use Berlekamp's algorithm to solve $p | G(n)$, thus restricting $n$ with congruences modulo $p$. I lit up sage and took 100 random polynomials of degree 10 with coefficients between -10 and 10, took the resultant of each pair and factored. The median of the largest prime factor of each resultant turns out to be a 53 bit number. I ran this 5 more times, always getting around the same median. – Dror Speiser Jul 02 '10 at 08:00
  • @Dror: Such congruences are not helpful since they lead to roughly the same number of iterations as brute-forcing the divisors of $m$. Also, $m$ is not the resultant of the polynomials, but a divisor of it. I did similar experiment to yours, and get the average size of the largest divisor about 43.5 bits. – Max Alekseyev Jul 02 '10 at 12:57
  • 1
    cf. also my reply to MO question 66873:http://mathoverflow.net/questions/66873/67202#67202 – Noam D. Elkies Nov 26 '12 at 22:07

1 Answers1

3

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.

Igor Rivin
  • 95,560