MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
I can do it if they're linear – Anthony Quas Jan 22 '13 at 0:31
If only it were that simple! :) – 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.

share|cite|improve this answer
Thanks for the correction! I've deleted the comment. – Qiaochu Yuan Jan 22 '13 at 1:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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