[FOM] Decidability of Diophantine equations

[Martin Davis]

Andrej Bauer asked:


 >1) Is it decidable whether a single quadratic Diophantine equation has a
 >solution? Has a solution in non-negative integers?


Siegel has shown that there is an algorithm for 
deciding whether a given second degree 
Diophantine equation is solvable. The reference is:

Carl Ludwig Siegel, “Zur Theorie der quadratische 
Formen”. Nachr. Akad. Wiss. Göttingen MTH.-Phys. Kl. II (1972), 21-46.



 >2) If a system has a small number of variables, say two or three, is its
 >solvability decidable?


Yuri Matiyasevich and Julia Robinson showed that 
the problem is already unsolvable for 13 
unknowns.  This was improved to 9 by Matiyasevich 
although he never published the proof. Though 
there has been much work on the case of two 
unknowns, that question is still open.

In the 1920s, Skolem showed that every 
Diophantine equation is equivalent to one of 
degree no larger than 4. This is by an easy 
trick: by introducing new unknowns any equation 
is equivalent to a system of second degree 
equations. Then, summing the squares to get a single equation yields degree 4.

The case of degree 3 remains open so far as I know.


The interesting paper

James Jones,  “Universal Diophantine Equation” J. 
Symb. Logic, 47(1982), 549-571
has a full proof of Matiyasevich's 9 variable theorem.

There is a trade-off between degree and number of 
unknowns. To get the 9 unknowns result requires 
at present an astronomically huge degree. The 
cited Jones paper has a collection of pairs 
<number of unknowns, degree> for which 
unsolvability can be proved, Here are some samples from the list:
<58,4>  <38,8> <28,20> <21,96> <19,2668> <13,6.6 x 10^43> <9,1.6 x 10^45>

In all those case there is a "universal" 
Diophantine equation with that data; universal in 
the sense of enumerating all r.e. sets.

Martin








                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com