Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows: Hilberts problems are a list of twenty-three problems in mathematics put forth by German mathematician David Hilbert at the Paris conference of the International Congress of Mathematicians in 1900. ...

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.

Formulation

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: . So Hilbert was asking for a general algorithm to decide whether a given polynomial Diophantine equation with integer coefficients has a solution in integers. The answer to the problem is now known to be in the negative: no such general algorithm can exist. Although it is unlikely that Hilbert had conceived of such a possibility, before going on to list the problems, he did presciently remark: In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... In mathematics, a Diophantine equation is a polynomial equation that only allows the variables to be integers. ...

"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."

The work on the problem has been in terms of solutions in natural numbers^[1] rather than arbitrary integers. But it is easy to see that an algorithm in either case could be used to obtain one for the other. If one possesed an algorithm to determine solvability in natural numbers, it could be used to determine whether an equation in n unknowns,

has an integer solution by applying the supposed algorithm to the 2ⁿ equations

Conversely, an algorithm to test for solvability in arbitrary integers could be used to test a given equation for solvability in natural numbers by applying that supposed algorithm to the equation obtained from the given equation by replacing each unknown by the sum of the squares of four new unknowns. This works because of Lagrange's four-square theorem, to the effect that every natural number can be written as the sum of four squares. Lagranges four-square theorem, also known as Bachets conjecture, was proved in 1770 by Joseph Louis Lagrange. ...

Diophantine sets

Main article: Diophantine set

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 In mathematics, a set S of j-tuples of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n1, ..., nj, x1, ..., xk) such that a tuple (n1, ..., nj) of integers is in S if and only if there exist some integers x1, ..., xk with f(n1... In mathematics, a set S of j-tuples of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n1, ..., nj, x1, ..., xk) such that a tuple (n1, ..., nj) of integers is in S if and only if there exist some integers x1, ..., xk with f(n1...

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 will 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: In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable or provable if: There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S. Or, equivalently, There is... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... Computability theory is the branch of theoretical computer science that studies which problems are computationally solvable using different models of computation. ... Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ...

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 Matiyasevichs theorem, proven in 1970 by Yuri Matiyasevich, implies that Hilberts tenth problem is unsolvable. ... Matiyasevichs theorem, proven in 1970 by Yuri Matiyasevich, implies that Hilberts tenth problem is unsolvable. ... Yuri Matiyasevich born March 2, 1947 in Leningrad, is a Russian mathematician. ... Julia Hall Bowman Robinson (December 8, 1919 - July 30, 1985) was an American mathematician, born in Saint Louis, Missouri. ... Martin Davis, (born 1926, New York City) is an American mathematician, known for his work on Hilberts tenth problem. ... Hilary Whitehall Putnam (born July 31, 1926) is an American philosopher who has been a central figure in Western philosophy since the 1960s, especially in philosophy of mind, philosophy of language, and philosophy of science. ...

with integer coefficients such that the set of values of a for which the equation

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 .

History

Applications

The Matiyasevich/MRDP Theorem 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 such that, given any Diophantine set S there is a number n₀ such that

This can be seen to be true simply because there are universal Turing machines, capable of executing any algorithm. This implication of J.R. had made it seem implausible. The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...

Hilary Putnam has pointed out that for any Diophantine set S of positive integers, there is a polynomial

such that S consists of exactly the positive numbers among the values assumed by q as the variables

range over all natural numbers. This can be seen as follows: If

provides a Diophantine definition of S, then it suffices to set

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 propositions, sometimes also called propositions of Goldbach type.^[4] These are like the Goldbach Conjecture, in stating that all natural numbers possess a certain property that is algorithmically checkable for each particular number.^[5] The Matiyasevich/MRDP Theorem implies that each such proposition is equivalent to a statement that asserts that some particular Diophantine equation has no solutions in natural numbers.^[6] A number of important and celebrated problems are of this form: in particular, Fermat's Last Theorem, the Riemann Hypothesis, and the Four Color Theorem. In addition the assertion that particular formal systems such as Peano Arithmetic or ZFC are consistent can be expressed as sentences. The idea is to follow Kurt Gödel in coding proofs by natural numbers in such a way that the property of being the number representing a proof is algorithmically checkable. In mathematics, Goldbachs conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. ... Pierre de Fermat Problem II.8 in the Arithmetica of Diophantus, annotated with Fermats comment which became Fermats Last Theorem (edition of 1670). ... Unsolved problems in mathematics: Is the real part of a non-trivial zero of the Riemann zeta function always ½? In mathematics, the Riemann hypothesis (also called the Riemann zeta-hypothesis), first formulated by Bernhard Riemann in 1859, is one of the most famous unsolved problems. ... Example of a four-colored map The four color theorem (also known as the four color map theorem) states that given any plane separated into regions, such as a political map of the counties of a state, the regions may be colored using no more than four colors in such... The Zermelo-Fraenkel axioms of set theory (ZF) are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. ... [...]I dont believe in natural science. ...

sentences have the special property that if they are false, that fact will be provable in any of the usual formal systems. This is because the falsity amounts to the existence of a counter-example which can be verified by simple arithmetic. So if a sentence is such that neither it nor its negation is provable in one of these systems, that sentence must be true.

A particularly striking form of Gödel's incompleteness theorem is also a consequence of the Matiyasevich/MRDP Theorem: In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ...

Let

provide a Diophantine definition of a non-computable set. Let A be an algorithm that outputs a sequence of natural numbers n such that the corresponding equation

has no solutions in natural numbers. Then there is a number n₀ which is not output by A while in fact the equation

has no solutions in natural numbers.

To see that the theorem is true, it suffices to notice that if there were no such number n₀, one could algorithmically test membership of a number n in this non-computable set by simultaneously running the algorithm A to see whether n is output while also checking all possible k-tuples of natural numbers seeking a solution of the equation

We may associate an algorithm A with any of the usual formal systems such as Peano Arithmetic or ZFC by letting it systematically generate consequences of the axioms and then output a number n whenever a sentence of the form In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). ... The Zermelo-Fraenkel axioms of set theory (ZF) are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. ...

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.

Further results

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. Albert Thoralf Skolem (May 23, 1887 - March 23, 1963) was a Norwegian mathematician. ...

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 no one imagines that this striking result is the best possible, there has been no further progress.^[7] 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. Zhi-Wei Sun (孙智伟, b. ...

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 and let C be a proper non-empty subset of A. Davis proved that there is no algorithm to test a given Diophantine equation to determine whether the number of its solutions is a member of the set C. Thus there is no algorithm to determine whether the number of solutions of a Diophantine equation is finite, odd, a perfect square, a prime, etc.

Extensions of Hilbert's Tenth Problem

Although Hilbert posed the problem for the rational integers, it can obviously be just as well asked for many rings. Obvious examples are the rings of integers of algebraic number fields as well as the rational numbers. As Hilbert was surely aware, an algorithm such as he was requesting could have been extended to cover these other domains. For example, the equation Look up ring in Wiktionary, the free dictionary. ... In mathematics, an algebraic number field (or simply number field) is a finite-dimensional (and therefore algebraic) field extension of the rational numbers Q. That is, it is a field which contains Q and has finite dimension, or degree, when considered as a vector space over Q. The study of...

where p is a polynomial of degree d is solvable in non-negative rational numbers if and only if

is solvable in natural numbers. (If one possesed an algorithm to determine solvability in non-negative rational numbers, it could easily be used to determine solvability in the rationals.) However, knowing that there is no such algorithm as Hilbert had desired says nothing about these other domains.

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: Jan Denef (born September 4, 1951) is a Belgian mathematician. ...

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.

Footnotes

1. ^ Following the tradition in mathematical logic, 0 is considered to be a natural number in this article.
2. ^ That conjecture became the Green-Tao theorem in 2004 with a proof by Ben Green and Terence Tao.
3. ^ A review of the joint publication by Davis, Putnam, and Robinson in Mathematical Reviews (MR0133227) conjectured, in effect, that J.R. was false.
4. ^ sentences are at one of the lowest levels of the so-called arithmetical hierarchy.
5. ^ Thus, the Goldbach Conjecture itself can be expressed as saying that for each natural number n the number 2n + 4 is the sum of two prime numbers. Of course there is a simple algorithm to test a given number for being the sum of two primes.
6. ^ In fact the equivalence is provable in Peano Arithmetic.
7. ^ At this point, even 3 cannot be excluded as an absolute upper bound.

In mathematics, the Green-Tao theorem, proved by Ben Green and Terence Tao in 2004[1], states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. ... Ben Green (born Ben George Christian Green in 1964) was bassist for the industrial/heavy metal band Godflesh. ... Terence Chi-Shen Tao ( 陶哲軒)(born 1975) is an Australian mathematician working primarily on harmonic analysis, partial differential equations, combinatorics, analytic number theory and representation theory. ... Mathematical Reviews is a scientific journal edited by the American Mathematical Society offering reviews of recent mathematical papers. ... Mathematical Reviews is a scientific journal edited by the American Mathematical Society offering reviews of recent mathematical papers. ... In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies the set of arithmetic formulas (or arithmetic sets) according to their degree of solvability. ... In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). ...

References

• Yuri V. Matiyasevich, Hilbert's Tenth Problem, MIT Press, Cambridge, Massachusetts, 1993.
• Martin Davis, Yuri Matiyasevich, and Julia Robinson, "Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a Negative Solution," Proceedings of Symposia in Pure Mathematics, vol.28(1976), pp. 323-378; reprinted in The Collected Works of Julia Robinson, Solomon Feferman, editor, pp.269-378, American Mathematical Society 1996.
• Martin Davis, "Hilbert's Tenth Problem is Unsolvable," American Mathematical Monthly, vol.80(1973), pp. 233-269; reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982.
• Jan Denef, Leonard Lipschitz, Thanases Pheidas, Jan van Geel, editors, "Hilbert's Tenth Problem: Workshop at Ghent University, Belgium, November 2-5, 1999." Contemporary Mathematics vol. 270(2000), American Mathematical Society.

Solomon Feferman is a mathematician and philosopher at Stanford University. ... Jan Denef (born September 4, 1951) is a Belgian mathematician. ...

External links

• Hilbert's Tenth Problem: a History of Mathematical Discovery
• Hilbert's Tenth Problem page!
• Zhi Wei Sun: On Hilbert's Tenth Problem and Related Topics