A Story of Hilbert’s Tenth Problem
Laura Elena Morales Guerrero
Abstract I tell a story about Martin Davis’s involvement with Hilbert’s tenth problem, including his attitude, motivations, and what were his main contributions. With respect to Yuri Matiyasevich, I emphasize the fundamental aspects of his work in number theory that produced the needed proof. In addition I provide a glimpse of the social, educational, and cultural environment that created the quality of person and mathematician he is.
Keywords Hilbert’s tenth problem • DPRM-theorem
Hilbert’s tenth problem, one of 23 presented by him in the year 1900, concerns a fundamental question, namely, whether there is an algorithmic method for determining if a given Diophantine equation has a solution. This problem was finally solved in 1970 by Yuri Matiyasevich. His solution was, however, negative: there is no such algorithm. In fact he provided the crucial missing step in the proof of a conjecture that Martin Davis had made twenty years earlier from which the non existence of an algorithm for Hilbert’s problem followed at once.
Davis’s conjecture involved the notion of Diophantine set of natural numbers defined as follows:
A set S of natural numbers is called Diophantine if there is a polynomial P (x, yi, ym)
with integer coefficients such that a given natural number x belongs to S if and only if there exist natural numbers yi,...,ym for which P (x, yi, ym) = 0. If the variables in P are
permitted to also occur in its exponents, the set S is called exponential Diophantine.
The conjecture was that every set of natural numbers that can be listed by an algorithm (such sets are called recursively enumerable, abbreviated r.e.) is Diophantine.
L.E. Morales Guerrero (B)
© Springer International Publishing Switzerland 2016 93
E.G. Omodeo and A. Policriti (eds.), Martin Davis on Computability,
Computational Logic, and Mathematical Foundations,
Outstanding Contributions to Logic 10, DOI 10.1007/978-3-319-41842-1_4
After Matiyasevich’s result, the conjecture became a theorem variously known as Matiyasevich’s Theorem, the MRDP theorem, or the DPRM theorem.1 By now there are a number of proofs available of this theorem. However all of these proofs consist of two separate and independent parts. One part is the proof that the exponential function is Diophantine, the other, that every r.e. set is exponential Diophantine. The first part has been called a “gem of number theory”, which indeed it is, and Yuri Matiyasevich’s contribution was precisely proving this part. He also found a proof (in collaboration with James Jones), using register machines, in a new and simple way, of the other part, namely, the equivalence between the exponential Diophantine and r.e. sets.
A proof that every r.e. set is exponential Diophantine first appeared in a paper  by Martin Davis, Hilary Putnam and Julia Robinson. This result is called the Davis- Putnam-Robinson theorem in the paper by James Jones and Yuri Matiyasevich  in which the register machines proof is presented. Another version of it can be found in . By the way, in this book there is a curious footnote that says that Hilary Putnam and Martin Davis first produced a proof of the Davis-Putnam-Robinson theorem with a serious blemish: they had to assume that there are arbitrarily long sequences of primes such that the difference between consecutive terms of the sequence is constant, that is, in arithmetic progression. I would like to point out the following with respect to that footnote: In 1959 when Davis and Putnam did that, their assumption about primes was believed to be true but seemed far beyond what number theorists could prove. They sent their work to Julia Robinson who quickly showed how to avoid their assumption. It was a real “tour de force”. She used the prime number theorem for arithmetic progressions to get enough primes to push the proof through. Later (before they published) she managed to simplify the proof greatly, essentially putting it in the form presented in . We will speak in more detail about this later. Why am I calling attention to this now? Because just a decade ago (April 2004, cf. ) two young mathematicians proved that there are indeed arbitrarily long arithmetic progressions consisting entirely of prime numbers. So the proof with a blemish that Putnam and Davis produced so many years ago turns out, in retrospect, to have been a genuine proof after all!
Davis introduced the term Diophantine set and began working on them at about the same time that Julia Robinson did as well. (She called them existentially definable.) The proof of the Davis-Putnam-Robinson theorem made use of techniques and results that had been developed by each of them.