Hilbert's tenth problem is the tenth on the
list of mathematical problems that the German mathematician
David Hilbert
David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many a ...
posed in 1900. It is the challenge to provide a general
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
which, for any given
Diophantine equation
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
(a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
equation with
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
coefficients and a finite number of unknowns), can decide whether the equation has a solution with all unknowns taking integer values.
For example, the Diophantine equation
has an integer solution:
. By contrast, the Diophantine equation
has no such solution.
Hilbert's tenth problem has been solved, and it has a negative answer: such a general algorithm does not exist. This is the result of combined work of
Martin Davis,
Yuri Matiyasevich
Yuri Vladimirovich Matiyasevich, (russian: Ю́рий Влади́мирович Матиясе́вич; born 2 March 1947 in Leningrad) is a Russian mathematician and computer scientist. He is best known for his negative solution of Hilbert's t ...
,
Hilary Putnam
Hilary Whitehall Putnam (; July 31, 1926 – March 13, 2016) was an American philosopher, mathematician, and computer scientist, and a major figure in analytic philosophy in the second half of the 20th century. He made significant contributions ...
and
Julia Robinson
Julia Hall Bowman Robinson (December 8, 1919July 30, 1985) was an American mathematician noted for her contributions to the fields of computability theory and computational complexity theory—most notably in decision problems. Her work on Hilbe ...
which spans 21 years, with Matiyasevich completing the theorem in 1970. The theorem is now known as
Matiyasevich's theorem
In mathematics, a Diophantine equation is an equation of the form ''P''(''x''1, ..., ''x'j'', ''y''1, ..., ''y'k'') = 0 (usually abbreviated ''P''(', ') = 0) where ''P''(', ') is a polynomial with integer coefficients, where ''x''1, ..., '' ...
or the MRDP theorem (an initialism for the surnames of the four principal contributors to its solution).
When all coefficients and variables are restricted to be ''positive'' integers, the related problem of
polynomial identity testing In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials are identical. More formally, a PIT algorithm is given an arithmetic circuit that computes a polynomial p in a field, a ...
becomes a decidable (exponentiation-free) variation of
Tarski's high school algebra problem
In mathematical logic, Tarski's high school algebra problem was a question posed by Alfred Tarski. It asks whether there are identities involving addition, multiplication, and exponentiation over the positive integers that cannot be proved usi ...
, sometimes denoted
[Stanley Burris, Simon Lee, ''Tarski's high school identities'', ]American Mathematical Monthly
''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America.
The ''American Mathematical Monthly'' is an e ...
, 100, (1993), no.3, pp. 231–236.
Background
Original formulation
Hilbert formulated the problem as follows:
''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.''
The words "process" and "finite number of operations" have been taken to mean that Hilbert was asking for an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
. 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
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
with integer coefficients has a solution in integers.
Hilbert's problem is not concerned with finding the solutions. It only asks whether, in general, we can decide 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
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
. 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".
Diophantine sets
In a Diophantine equation, there are two kinds of variables: the parameters and the unknowns. The Diophantine set consists of the parameter assignments for which the Diophantine equation is solvable. A typical example is the linear Diophantine equation in two unknowns,
:
,
where the equation is solvable when the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of
divides
. The values for
that satisfy this restriction are a Diophantine set and the equation above is its Diophantine definition.
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
:
Sets of natural numbers, of pairs of natural numbers (or even of ''n''-
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s of natural numbers) that have Diophantine definitions are called ''
Diophantine set
In mathematics, a Diophantine equation is an equation of the form ''P''(''x''1, ..., ''x'j'', ''y''1, ..., ''y'k'') = 0 (usually abbreviated ''P''(', ') = 0) where ''P''(', ') is a polynomial with integer coefficients, where ''x''1, ..., '' ...
s''. In these terms, Hilbert's tenth problem asks whether there is an algorithm to determine if a given Diophantine set is non-empty.
The work on the problem has been in terms of solutions in
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s (understood as the non-negative integers) rather than arbitrary integers. The two problems are equivalent: any general algorithm that can decide whether a given Diophantine equation has an integer solution could be modified into an algorithm that decides whether a given Diophantine equation has a natural number solution, and vice versa. This can be seen as follows: The requirement that solutions be natural numbers can be expressed with the help of
Lagrange's four-square theorem
Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four.
p = a_0^2 + a_1^2 + a_2^2 + a_ ...
: every natural number is the sum of the squares of four integers, so we simply replace every parameter with the sum of squares of four extra parameters. Similarly, since every integer can be written as the difference of two natural numbers, we can replace every parameter that ranges in integers with the difference of two parameters that range in natural numbers.
Recursively enumerable sets
A
recursively enumerable set
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
can be characterized as one for which there exists an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
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
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
(also known as recursion theory) that provided a precise explication of the intuitive notion of algorithmic computability, thus making the notion of recursive enumerability perfectly rigorous. It is evident that Diophantine sets are recursively enumerable (a.k.a. semi-decidable). 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
In mathematics, a Diophantine equation is an equation of the form ''P''(''x''1, ..., ''x'j'', ''y''1, ..., ''y'k'') = 0 (usually abbreviated ''P''(', ') = 0) where ''P''(', ') is a polynomial with integer coefficients, where ''x''1, ..., '' ...
(because he provided the crucial step that completed the proof) and the
MRDP theorem
In mathematics, a Diophantine equation is an equation of the form ''P''(''x''1, ..., ''x'j'', ''y''1, ..., ''y'k'') = 0 (usually abbreviated ''P''(', ') = 0) where ''P''(', ') is a polynomial with integer coefficients, where ''x''1, ..., '' ...
(for
Yuri Matiyasevich
Yuri Vladimirovich Matiyasevich, (russian: Ю́рий Влади́мирович Матиясе́вич; born 2 March 1947 in Leningrad) is a Russian mathematician and computer scientist. He is best known for his negative solution of Hilbert's t ...
,
Julia Robinson
Julia Hall Bowman Robinson (December 8, 1919July 30, 1985) was an American mathematician noted for her contributions to the fields of computability theory and computational complexity theory—most notably in decision problems. Her work on Hilbe ...
,
Martin Davis, and
Hilary Putnam
Hilary Whitehall Putnam (; July 31, 1926 – March 13, 2016) was an American philosopher, mathematician, and computer scientist, and a major figure in analytic philosophy in the second half of the 20th century. He made significant contributions ...
). 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
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 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''
''there is a number''
''such that''
::
This is true simply because Diophantine sets, being equal to recursively enumerable sets, are also equal to
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s. 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
of positive integers, there is a polynomial
:
such that
consists of exactly the positive numbers among the values assumed by
as
the variables
:
range over all natural numbers. This can be seen as follows: If
:
provides a Diophantine definition of
, 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.) The same holds for other recursively enumerable sets of natural numbers: the factorial, the binomial coefficients, the fibonacci numbers, etc.
Other applications concern what logicians refer to as
propositions, sometimes also called propositions of ''Goldbach type''. These are like
Goldbach's conjecture
Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even natural number greater than 2 is the sum of two prime numbers.
The conjecture has been shown to hold ...
, in stating that all natural numbers possess a certain property that is algorithmically checkable for each particular number. 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. A number of important and celebrated problems are of this form: in particular,
Fermat's Last Theorem
In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers , , and satisfy the equation for any integer value of greater than 2. The cases and have been k ...
, the
Riemann hypothesis
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...
, and the
Four color theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...
. In addition the assertion that particular
formal system
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system.
A form ...
s such as Peano arithmetic or
ZFC are consistent can be expressed as
sentences. The idea is to follow
Kurt Gödel
Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an imme ...
in coding proofs by natural numbers in such a way that the property of being the number representing a proof is algorithmically checkable.
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:
Let
:
provide a Diophantine definition of a non-computable set. Let be an algorithm that outputs a sequence of natural numbers such that the corresponding equation
:
has no solutions in natural numbers. Then there is a number which is not output by 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
, one could algorithmically test membership of a number
in this non-computable set by simultaneously running the algorithm
to see whether
is output while also checking all possible
-tuples of natural numbers seeking a solution of the equation
:
and we may associate an algorithm
with any of the usual formal systems such as
Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
or
ZFC by letting it systematically generate consequences of the axioms and then output a number
whenever a sentence of the form
: