[FOM] Decidability of Diophantine equations
Martin Davis
martin at eipye.com
Thu Dec 14 21:38:45 EST 2006
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
More information about the FOM
mailing list