[FOM] Decidability of Diophantine equations

[Harvey Friedman]

On 12/14/06 6:12 AM, "Andrej Bauer" <Andrej.Bauer at fmf.uni-lj.si> wrote:

> Dear FOMers,
> 
> as is well-known, solvability of general Diophantine systems is
> undecidable. But what is known about particular kinds of systems, or
> even single equations? For example:
> 
> 1) Is it decidable whether a single quadratic Diophantine equation has a
> solution? Has a solution in non-negative integers?
> 
> 2) If a system has a small number of variables, say two or three, is its
> solvability decidable?
> 
> 3) What if we combine 1) and 2)?
> 
Here is my recollection.

1. The solvability of a single quadratic Diophantine equation over the
integers, or over the natural numbers, or over the rationals, is decidable.
I have seen Siegel, and the very much alive Grunewald and Segal credited for
various versions.

2. Two variable cubics may or may not be decidable over the integers. Two
variable cubics may or may not be decidable over the rationals. Wide open.

Don't take this as the absolute truth: you may want to use Google or a
number theorist to check on this (whoever is more available).

Harvey