Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:
- Diophantine sets
- Further results
- Extensions of Hilberts tenth problem
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 in a finite number of operations whether the equation is solvable in rational integers.
From the perspective of the theory of computation, Hilbert's 10th problem is concerned with the membership problem for the solutions of a Diophantine equation. The Matiyasevich/MDRP theorem has shown that recursively enumerable sets are equivalent to Diophantine sets. This provides a negative answer to Hilbert's 10th problem because it shows that it is a semi-decidable problem, which is a type of undecidable problem.
The answer to this problem is the combined work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson which spans 21 years, with Yuri Matiyasevich completing the theorem in 1970.
The words "process" and "finite number of operations" have been taken to mean that Hilbert was asking for an algorithm. The term "rational integer" simply refers to the integers, positive, negative or zero: 0, ±1, ±2, ... . So Hilbert was asking for a general algorithm to decide whether a given polynomial Diophantine equation with integer coefficients has a solution in integers.
Such an equation can be put in the form
where p is a polynomial with integer coefficients, the ai are the unknowns that form the solution and the xj the parameters. The polynomial has both unknowns and parameters because it refers to the general form of the diophantine equation. In the case of the linear diophantine equation
solving the equation consists in finding the solutions a1, a2 for given x1, x2, x3.
Hilbert's problem is not concerned with finding the solutions. It only asks whether one or more solutions exist. The answer to this question is negative, in the sense that no "process can be devised" for answering that question. In modern terms, Hilbert's 10th problem is an undecidable problem. Although it is unlikely that Hilbert had conceived of such a possibility, before going on to list the problems, he did presciently remark:
"Occasionally it happens that we seek the solution under insufficient hypotheses or in an incorrect sense, and for this reason do not succeed. The problem then arises: to show the impossibility of the solution under the given hypotheses or in the sense contemplated."
Proving the 10th problem undecidable is then a valid answer even in Hilbert's terms, since it is a proof about "the impossibility of the solution".
The work on the problem has been in terms of solutions in natural numbers (understood as the non-negative integers) rather than arbitrary integers.
The requirement that the solutions are in natural numbers can be expressed with the help of the fact that every natural number is the sum the squares of four integers, by introducing an extra Diophantine equation with 4 extra unknowns for each unknown that must be a natural number. For a version of the linear diophantine equation with solutions in natural numbers, this gives the following system of equations.
If the only consideration is finding whether a solution exists, there is a simple way in which a diophantine equation solvable in natural numbers can be derived from a diophantine equation solvable in integers. The trick is to replace every unknown in integers with the difference of two new unknowns in natural numbers. Using the general equation given above,
These two reducibility relations show that whatever the answer of the problem is for natural numbers so it is for the integers and vice versa.
Sets of natural numbers, of pairs of natural numbers (or even of n-tuples of natural numbers) that have Diophantine definitions are called Diophantine sets. Diophantine definitions can be provided by simultaneous systems of equations as well as by individual equations because the system
is equivalent to the single equation
A recursively enumerable set can be characterized as one for which there exists an algorithm that will ultimately halt when a member of the set is provided as input, but may continue indefinitely when the input is a non member. It was the development of computability theory (also known as recursion theory) that provided a precise explication of the intutitive notion of algorithmic computability, thus making the notion of recursive enumerability perfectly rigorous. It is evident that Diophantine sets are recursively enumerable. This is because one can arrange all possible tuples of values of the unknowns in a sequence and then, for a given value of the parameter(s), test these tuples, one after another, to see whether they are solutions of the corresponding equation. The unsolvability of Hilbert's tenth problem is a consequence of the surprising fact that the converse is true:
Every recursively enumerable set is Diophantine.
This result is variously known as Matiyasevich's theorem (because he provided the crucial step that completed the proof) and the MRDP theorem (for Yuri Matiyasevich, Julia Robinson, Martin Davis, and Hilary Putnam). Because there exists a recursively enumerable set that is not computable, the unsolvability of Hilbert's tenth problem is an immediate consequence. In fact, more can be said: there is a polynomial
with integer coefficients such that the set of values of
has solutions in natural numbers is not computable. So, not only is there no general algorithm for testing Diophantine equations for solvability, even for this one parameter family of equations, there is no algorithm.
The Matiyasevich/MRDP Theorem relates two notions — one from computability theory, the other from number theory — and has some surprising consequences. Perhaps the most surprising is the existence of a universal Diophantine equation:There exists a polynomial
This is true simply because Diophantine sets, being equal to recursively enumerable sets, are also equal to Turing machines. It is a well known property of Turing machines that there exist universal Turing machines, capable of executing any algorithm.
Hilary Putnam has pointed out that for any Diophantine set
range over all natural numbers. This can be seen as follows: If
provides a Diophantine definition of
So, for example, there is a polynomial for which the positive part of its range is exactly the prime numbers. (On the other hand, no polynomial can only take on prime values.)
Other applications concern what logicians refer to as
A particularly striking form of Gödel's incompleteness theorem is also a consequence of the Matiyasevich/MRDP Theorem:
provide a Diophantine definition of a non-computable set. Let
has no solutions in natural numbers. Then there is a number
has no solutions in natural numbers.
To see that the theorem is true, it suffices to notice that if there were no such number
We may associate an algorithm
is generated. Then the theorem tells us that either a false statement of this form is proved or a true one remains unproved in the system in question.
We may speak of the degree of a Diophantine set as being the least degree of a polynomial in an equation defining that set. Similarly, we can call the dimension of such a set the least number of unknowns in a defining equation. Because of the existence of a universal Diophantine equation, it is clear that there are absolute upper bounds to both of these quantities, and there has been much interest in determining these bounds.
Already in the 1920s Thoralf Skolem showed that any Diophantine equation is equivalent to one of degree 4 or less. His trick was to introduce new unknowns by equations setting them equal to the square of an unknown or the product of two unknowns. Repetition of this process results in a system of second degree equations; then an equation of degree 4 is obtained by summing the squares. So every Diophantine set is trivially of degree 4 or less. It is not known whether this result is best possible.
Julia Robinson and Yuri Matiyasevich showed that every Diophantine set has dimension no greater than 13. Later, Matiyasevich sharpened their methods to show that 9 unknowns suffice. Although it may well be that this result is not the best possible, there has been no further progress. So, in particular, there is no algorithm for testing Diophantine equations with 9 or fewer unknowns for solvability in natural numbers. For the case of rational integer solutions (as Hilbert had originally posed it), the 4 squares trick shows that there is no algorithm for equations with no more than 36 unknowns. But Zhi Wei Sun showed that the problem for integers is unsolvable even for equations with no more than 11 unknowns.
Martin Davis studied algorithmic questions involving the number of solutions of a Diophantine equation. Hilbert's tenth problem asks whether or not that number is 0. Let
Extensions of Hilbert's tenth problem
Although Hilbert posed the problem for the rational integers, it can be just as well asked for many rings (in particular, for any ring whose elements are countable). Obvious examples are the rings of integers of algebraic number fields as well as the rational numbers.
There has been much work on Hilbert's tenth problem for the rings of integers of algebraic number fields. Basing themselves on earlier work by Jan Denef and Leonard Lipschitz and using class field theory, Harold N. Shapiro and Alexandra Shlapentokh were able to prove:
Hilbert's tenth problem is unsolvable for the ring of integers of any algebraic number field whose Galois group over the rationals is abelian.
Shlapentokh and Thanases Pheidas (independently of one another) obtained the same result for algebraic number fields admitting exactly one pair of complex conjugate embeddings.
The problem for the ring of integers of algebraic number fields other than those covered by the results above remains open. Likewise, despite much interest, the problem for equations over the rationals remains open. Barry Mazur has conjectured that for any variety over the rationals, the topological closure over the reals of the set of solutions has only finitely many components. This conjecture implies that the integers are not Diophantine over the rationals and so if this conjecture is true a negative answer to Hilbert's Tenth Problem would require a different approach than that used for other rings.