Connection between Hilbert's Tenth Problem and Roth's Theorem.

The following two decision problems seem to be open:

  1. Given a polynomial equation in two variables with integer coefficients, determine whether there are any integer solutions. (The two-variable case of Hilbert's Tenth Problem)

  2. Given a real algebraic number $r$ and given integers $B,N > 0$, determine whether the inequalities $|rx-y| < \frac{1}{x^{1+1/N}}$, $0 < x < B$ are solvable in integers $x$ and $y$. (This is the problem of the effective Roth bound -- Roth proved that for any algebraic $r$ and for any $N > 0 $, inequality $|rx-y| < \frac{1}{x^{1+1/N}}$ has only finitely many solutions in positive integers $x,y$.)

Now I heard once that an effective algorithm for the Roth bound would yield an effective algorithm for the two variable case of Hilbert's Tenth Problem. I can begin to imagine that this might be true for norm-form equations, following the treatment in Schmidt's books, but the general case seems quite opaque.

Can anyone suggest any references along these lines? Also, does anyone know of surveys summarizing what has been done to-date on the of the decidability of the two-variable case of Hilbert's Tenth Problem? Finally, does anyone know any interesting "plausibility arguments" for or against decidability?


An effective Roth's theorem would yield an effective Siegel's theorem by the usual proof. See, e.g. Lang's Fundamentals of Diophantine Geometry.

The case of diophantine equation of two variables is generally believed to be decidable. Poonen has a couple of expository articles on this (check his web page) that you might find useful.

  • $\begingroup$ Thanks -- I'll check Poonen's website. I suppose that the "general belief" that the two-variable problem is decidable must be based on the types of equations of this sort for which the existence of solutions is open. I would love to find a collection or survey of open two-variable problems. $\endgroup$ – Sidney Raffer Apr 15 '10 at 21:05
  • 1
    $\begingroup$ The state of the art today is that two variable problems can in practice be solved and systematically are. We just can't yet prove that we will always succeed. Look, e.g., at the papers of M. Stoll and his collaborators. $\endgroup$ – Felipe Voloch Apr 16 '10 at 0:42

Here is a plausibility argument for decidability.

DISCLAIMER: I am in no way an expert and admittedly an optimist.

The way you show that Hilbert's Tenth Problem has a negative solution is by showing that diophantine equations can "cut out" every recursively enumerable subset of $\Bbb Z.$ The negative solution follows from the fact that there are recursively enumerable subsets which are not recursive. For a quick introduction see Mazur's recent expository lecture notes here.

Moral: Diophantine equations can define sets which are too complicated!

For each recursively enumerable subset $S$ of $\Bbb Z$ we can define the diophantine dimension of $S$ as the smallest such $n$ for which there is a diophantine equation in $n$ variables with integer coefficients which cuts out $S$. (Experts: Is there a better name for this integer?)

For example, this popular MO question of Poonen asks roughly to determine if the diophantine dimension of $\Bbb N$ is 2? This seems to be incredibly hard. It seems plausible that the relatively tame subset $\Bbb N$ of $\Bbb Z$ might have diophantine dimension $ > 2$. So I feel free to hope that the even more complicated sets which lead to undecidability are complicated enough that they have diophantine dimension greater than 2.

  • $\begingroup$ @jamieweigandt: By "cut out" do you mean the minimum number of existential quantifiers necessary to give a diophantine definition of a given set? That would be consistent with the statement "Poonen is asking if the integers has diophantine dimension 2" ..... After all, one would use two quantifiers and a 3-variable polynomial f(x,y)-z in the diophantine definition of N, if the answer to Poonen's question is "yes". The question whether a non-computable set can be defined with just two quantifiers, is interesting by itself. $\endgroup$ – Sidney Raffer Apr 16 '10 at 9:29

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.