Given two arbitrary polynomials $G(x)$ and $H(y)$, with integer coefficents, are there any circumstances in which it is possible to decide whether or not $G(x) = H(y)$ has solutions with $x, y \in \mathbb Z$?

  • $\begingroup$ I can do it if they're linear $\endgroup$ – Anthony Quas Jan 22 '13 at 0:31
  • $\begingroup$ If only it were that simple! :) $\endgroup$ – Jim White Jan 22 '13 at 0:43

Qiaochu's comment is not correct. There is an explicit bound for the height of integral points on elliptic curves (from Baker's method) and so the problem is decidable. Other equations $y^n = G(x)$ are also decidable the same way. See e.g., Lang's book "Elliptic curves: Diophantine Analysis" where he puts some explicit bounds "under duress, at the insistence of Michel Waldschmidt" :-). I don't know if the current results cover the general case of the question.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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