5

Is there an algorithm that, given polynomials $P(x)$ and $Q(y)$ with integer coefficients, decides whether there exists integers $x$ and $y$ such that $\frac{P(x)}{Q(y)}$ is an integer?

This is a special case of a more general question to decide the existence of integer points of a rational function $R(x,y)=\frac{P(x,y)}{Q(x,y)}$. This looks difficult in general, because if $Q=P^2+1$, then $R(x,y)$ is integer only if $P(x,y)=0$, and there is no known algorithm to decide the existence of integer solutions to this equation. However, one may ask a relaxed question: assuming that we can solve equations $P(x,y)=a$ and $Q(x,y)=a$ for every integer $a$, can we then decide whether $\frac{P(x,y)}{Q(x,y)}$ can be an integer? This would surely answer the original question.

Bogdan Grechuk
  • 5,947
  • 1
  • 25
  • 42
  • For the case $x=y$, see https://mathoverflow.net/q/30204 – Max Alekseyev Sep 24 '21 at 17:33
  • Finding all points is definitely hard as solving $\frac{P(x)}{Q(y)}=1$, i.e. $P(x)-Q(y)=0$, include, for example, finding integral points on hyperelliptic curves when $\deg(P)=2$ and $\deg(Q)\geq 4$. I suspect finding one point is not simpler either. – Max Alekseyev Sep 24 '21 at 17:49
  • 2
    My intuition is that the ratio is integer heuristically quite often, hence either there this happens or there should be a reason why it does not happen (like P is always odd and Q is always even, etc.) Then this reason can be used for a proof. In contrast, $P(x)=Q(y)$ is hard because if P and Q have high degree then heuristics suggest that there should be no solutions, hence there may be no solutions even if there is no particular reason for this. – Bogdan Grechuk Sep 24 '21 at 19:54

0 Answers0