Agnes Scott College

Martin Davis, Hilary Putnam, and Julia Robinson

The Decision Problem for Exponential Diophantine Equations
Annals of Mathematics, Vol. 74, No. 3 (Nov. 1961), 425-436


We prove that every recursively enumerable set can be existentially defined in terms of exponentiation. Hence, there is no general algorithm for deciding whether or not an exponential diophantine equation has a solution in positive integers. We also obtain a general theorem about bounds for solutions of diophantine equations with a finite number of solutions2.

The tenth problem on David Hilbert's famous list is given as follows:

10. Entscheidung der Lösbarkeit einer diophantischen Gleichung.
Eine diophantische Gleichung mit irgendwelchen Unbekannten und mit ganzen rationalen Zahlkoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchen sich mittels einer endlichen Anzahl von Operationen entscheiden lässt, ob die Gleichung in ganzen rationalen Zahlen lösbar ist.

Our result provides a negative answer to a closely related problem.

2 The result that every recursively enumerable set can be existentially defined in terms of exponentiation was obtained by Davis and Putnam...using the unproved number-theoretical hypothesis that there are arbitrarily long arithmetic progressions containing only prime numbers....Julia Robinson showed that the use of this hypothesis can be avoided....Subsequently, she greatly simplified the entire proof. The theorem concerning bounds of solutions of diophantine equations is also due to Julia Robinson.

[Note: English translation of Hilbert's tenth problem:
10. Determination of the solvability of a Diophantine equation.
Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.]