The Beginning

It was in his 1950 doctoral dissertation that Davis stated his conjecture, published in his 1953 paper [6], which Yuri Matiyasevich called Davis’s “daring hypothesis”: the Diophantine sets are precisely the recursively enumerable sets, the sets that can 1The letters RDP (DPR) stand for Julia Robinson, Martin Davis, and Hilary Putnam.

be generated by recursive functions or, equivalently, by a Turing machine. Since by then mathematicians already knew there is an r.e. that is not decidable, if Davis’s conjecture was true they would know that there is a Diophantine set that is undecidable. Specifically, there could be no algorithm to decide whether a given member of the parametric family of equations that generates this undecidable set is solvable in natural numbers—much less for the more general question covering all Diophantine equations. What Hilbert had asked for in his tenth problem would be impossible to do. Davis’s idea that the Diophantine equations could define all the recursively enumerable sets, his “daring hypothesis”, was generally regarded as implausible.

The first contribution to this work was by Godel in his celebrated 1931 paper [7]. The main point of Godel’s investigations was the existence of undecidable statements in formal systems. The undecidable statements Godel obtained involved recursive functions and in order to exhibit the simple number theoretic character of those statements, Godel used the Chinese Remainder Theorem to reduce them to “arithmetic” form. However, without techniques for dealing with bounded universal quantifiers (developed much later in [1]), the best result yielded by Godel’s methods is that every recursive function (and indeed every r.e. set) can be defined by a Diophantine equation preceded by a finite number of existential and bounded universal quantifiers. In Davis’s doctoral dissertation [6, 8], he showed that all but one of the bounded universal quantifiers could be eliminated, so that every r.e. set could be defined in the form

where P is a polynomial with integer coefficients.

This representation became known as the Davis normal form. Matiyasevich has shown that we can take m = 2. Whether one can always get m = 1, is open. One cannot always have m = 0.

The fact that Davis had already gotten rid of all universal quantifiers necessary to define recursive functions except for one—and it was bounded—and the fact that each class had certain common features—as sets they were both closed under “and”, “or”, and existential quantification and neither was closed under negation—, might have led him to pose his conjecture.

In Davis’s dissertation he conjectured that two fundamental concepts arising in different areas of mathematics are equivalent. Namely, that the notion of recursive enumerable or semidecidable set of natural numbers from computability theory is equivalent to the purely number theoretic notion of Diophantine sets (his “daring hypothesis”). He saw how to improve Godel’s use of the Chinese Remainder Theorem as a coding device so as to obtain a representation for recursively enumerable sets that formally speaking seemed close to the desired result. The obstacle that remained in the so-called Davis normal form was a single bounded universal quantifier, as shown above.

Independent of his work and about the same time, Julia Robinson was also studying Davis’s Diophantine sets which she called existentially definable. She was attempting to see what kinds of sets of whole numbers she could define using Diophantine equations and existential quantifiers. Her investigations centered about the question: Is the exponential function Diophantine? In “Existential Definability in Arithmetic” [9], Robinson investigated a variety of functions that, like the powers of two, grow rapidly. She discovered that if she could define exponentiation, specifically the relation x = yz, then she could also define a number of other functions including the factorial function and binomial coefficients. More surprisingly, she found she would be able to define the statement “p is a prime” in terms of a Diophantine equation. A truism of number theory had been that there was no formula for the prime numbers. Her Diophantine equation could be regarded as such a formula. She worked hard on exponentiation. Her major result was that if one could define any function that grew sufficiently rapidly, but not too rapidly, one could use this function to define exponentiation itself. She conjectured that finding such a function was possible. This would then show that exponentiation was Diophantine. This hypothesis became known as the Julia Robinson (JR) hypothesis. This was the main result of her work. Her hypothesis has played a key role in work on Hilbert’s tenth problem.

JR statement is simply:

There exists a Diophantine set D of pairs of natural numbers such that

  • 1. (u, v} e D implies v < uu.
  • 2. For each k, there is (u, v} e D such that v > uk.

Her hypothesis remained an open question for about two decades. Once the Davis- Putnam-Robinson theorem was proved, attention was focused on the JR hypothesis since it was plain that it would imply that Hilbert’s tenth problem was unsolvable. However, it seemed extraordinarily difficult to produce such an equation.

Davis met Julia Robinson at the 1950 International Congress of Mathematicians in Cambridge, Massachusetts, immediately after completing his doctorate. She had approached Hilbert’s tenth from a direction opposite to that of Davis. Where he had tried to simplify the arithmetic representation of arbitrary recursively enumerable sets, she had been trying to produce Diophantine definitions for various specific sets and specially for the exponential function. She had introduced then what was to become her famous “hypothesis” and shown that under that assumption the exponential function is in fact Diophantine.

The luck of Julia’s mathematical journey was holding when Alfred Tarski arrived in California in 1947 and she became a graduate student working under him. Julia, as well as many others ranked Tarski with Godel as a great logician.

She had worked hard and successfully simplifying the definitions for general recursive functions during 1946-47 while in Princeton with her husband Raphael Robinson. Tarski had proposed to Julia a problem that did not interest her and she made little progress. However, one day at lunch with Raphael Robinson, Tarski talked about whether the whole numbers were definable in a formal system for the rational numbers. When Raphael came home he mentioned it to Julia. This problem she found interesting. She did not tell Tarski she would work on it but she did and she solved it. It is typical of her best work. She works with formal systems but introduces a clever idea from number theory, in this case, using the Hasse principle from algebraic number theory in connection with a particular quadratic equation she introduced. Davis described this as “an absolutely brilliant piece of work”. This result was accepted by Tarski as her dissertation and she obtained her PhD in 1948. In the same year Tarski mentioned another problem to Raphael who brought it home. The problem was to show that one could not define the powers of 2

using only existential quantifiers and a Diophantine equation. If this could be accomplished it would have a bearing on Hilbert’s tenth problem; in fact, the eventual negative solution turned out to depend on showing the opposite.

Julia Robinson became entranced with the problem, but not from the direction Tarski had in mind. At first she did not know she was working on Hilbert’s problem. She quickly decided that she did not see how to prove that the powers of two could not be defined in this way. Instead, she decided to see if she could define the powers of two. This expanded to work on defining other sets of whole numbers. She made rapid progress and on September 4,1950, delivered a ten-minute paper at the International Congress of Mathematics at Cambridge, Massachusetts. At the same conference Davis gave a ten-minute talk on his results on the hyperarithmetic hierarchy, his dissertation work. However, he had spoken on his results on the tenth problem the previous winter at a meeting of the Association of Symbolic Logic.

Although Hilary Putnam’s career had been in philosophy, he became fascinated by the tenth problem. During the summer of 1957, there was an intensive five week “Institute for Logic” at Cornell University. The families of the logicians attended as well and Putnam and his family shared a house with Davis and his family. And so they began to talk about Hilbert’s tenth problem. Putnam suggested they try to use Godel’s coding to make that one little bounded universal quantifier in the Davis normal form go away. Davis was skeptical but they worked on the problem and made some progress which resulted in a joint paper, Reductions of Hilbert’s Tenth Problem [10]. They decided to try to get funding to enable them to work together the following summer. They worked together during the summers of 1958, 1959 and 1960. It was during the summer of 1959 that they did their main work together on Hilbert’s tenth problem.

In 1959 Davis and Putnam were again trying to apply Godel coding to deal with the bounded universal quantifier in Davis normal form as they had in their work in 1957. Godel coding uses the Chinese Remainder Theorem which in effect means working with arithmetic congruences. One writes x = y mod m to mean that m is a divisor of x - y. Since congruences are preserved under addition and multiplication, and polynomials are built out of a sequence of additions and multiplications, if P is a polynomial with integer coefficients, then we can conclude that

To use the Chinese Remainder Theorem to get rid of the universal quantifier (Vk)< y, one needs a sequence of moduli mk with k = 0, 1,..., y each pair of which are relatively prime. Moreover to keep the polynomial form, the function mk should be expressible by a polynomial in k. They also needed to be able to assert that if one of their moduli was a divisor of a product that it had to necessarily divide one of the factors. And this seemed to require that the moduli be not only relatively prime in pairs, but actual prime numbers. These needs could be readily supplied if one could set mk = a + bk where each mk is prime. Thus, in the end they were forced to assume the hypothesis (nowadays proved) that there are arbitrarily long arithmetic progressions of prime numbers. Finally in order to complete their proof that every recursively enumerable set has an exponential Diophantine definition, they found themselves with the need to find exponential Diophantine definitions for the product of the terms of a finite arithmetic progression To deal with this problem they used binomial coefficients with rational numerators, for which they could find exponential Diophantine definitions extending Julia Robinson’s methods, but requiring the binomial theorem with rational exponents, an infinite power series expansion. They wrote up their work in a report to their funding agency [11], and sent a copy to Julia Robinson. She responded saying: “I am very pleased, surprised and impressed with your results on Hilbert’s tenth problem. Quite frankly, I did not think your methods could be pushed further „.I believe I have succeeded in eliminating the need for (the assumption about primes in arithmetic progression) by extending and modifying your proof. I have this written out for my own satisfaction but it is not yet in shape for any one else.”

That was the “tour de force” mentioned above. She avoided the hypothesis about primes in arithmetic progression in an elaborate and very clear argument by making use of the prime number theorem for arithmetic progressions to obtain enough primes to permit the proof to go through. She accepted Davis and Putnam’s proposal that their work (which had already been submitted for publication) be withdrawn in favor of a joint publication by the three of them. Soon afterwards she succeeded in a drastic simplification of the proof: where Putnam and Davis were trying to use Godel’s coding to obtain a logical equivalence, her elegant argument made use of the fact that the primes were only needed for the implication in one direction, and that in that direction one could make do with a prime divisor of each modulus. The joint paper appeared in 1961 [1]. This paper is very efficient, eleven pages long, and the main result—that all recursive sets are exponential Diophantine—is proved in only four pages! The only thing now necessary for a solution of the tenth problem was to prove JR (not at all an easy matter) which would imply that exponentiation is Diophantine.

With the result that every recursively enumerable set has an exponential Diophan- tine definition combined with Robinson’s earlier work on Diophantine definitions of the exponential function, it was now clear that Davis’s “daring hypothesis” of the equivalence of the two notions, recursively enumerable set and Diophantine set, was now entirely equivalent to the much weaker JR hypothesis that Julia Robinson had proposed ten years earlier. What was needed was a single Diophantine equation whose solutions satisfied a simple condition.

In the summer of 1960 Putnam and Davis tried to find a third degree equation to satisfy JR. It turned out once again that they needed information the number theorists were unable to provide, this time about the units in pure cubic extensions of the rational numbers. Although Putnam continued to do important technical work in mathematical logic, he no longer worked on number theory.

During the following years Davis continued trying to prove JR. At that time Julia had became rather pessimistic about her hypothesis, and for a brief period, she actually worked towards a positive solution of Hilbert’s tenth problem. A letter from her dated April 1968, responding to Davis’s report on a certain equation he had found, said: “I have enjoyed studying it, but my faith in JR has not been restored. However, for the first time, I can see how it might be proved. Indeed, maybe your equation works, but it seems to need an infinite amount of good luck!”

However, in 1969, she published a paper [12] that made some progress. In those days, when Davis was asked for his opinion, he would reply in a semi-jocular vein: “I think JR is true and it will be proved by a clever young Russian.” However, the hypothesis seemed implausible to many, especially because it was realized that an immediate and surprising consequence would be the existence of an absolute upper bound for the dimensions of Diophantine sets. Thus Kreisel [13] in his review of the Davis-Putnam-Robinson paper asserted:

It is likely the present result is not closely connected with Hilbert’s tenth problem. Also it is not altogether plausible that all (ordinary) Diophantine problems are uniformly reducible to those in a fixed number of variables of fixed degree.

Early in 1970 a telephone call from his friend and colleague Jack Schwartz informed Davis that the “clever young Russian” he had predicted had actually appeared. Julia Robinson sent Davis a copy of John McCarthy’s notes on a talk that Grigori Tseitin had given in Novosibirsk on the proof of the Julia Robinson hypothesis by the twenty-two-year-old Yuri Matiyasevich. Although the notes were brief, everything important was there enabling Davis and Robinson to each fill in the details and convince themselves that it was correct. Later they were able to use his methods to produce their own variants of Matiyasevich’s proof.

< Prev   CONTENTS   Source   Next >