Hilbert's tenth problem is the tenth on thelist of mathematical problems that the German mathematicianDavid Hilbert posed in 1900. It is the challenge to provide a generalalgorithm that, for any givenDiophantine equation (apolynomial equation withinteger 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${\displaystyle 3x^2-2xy-y^{2}z-7=0}$ has an integer solution:${\displaystyle x=1,y=2,z=-2}$. By contrast, the Diophantine equation${\displaystyle x^2+y^2+1=0}$ has no such solution.

Hilbert's tenth problem has been solved, and it has a negative answer: such a general algorithm cannot exist. This is the result of combined work ofMartin Davis,Yuri Matiyasevich,Hilary Putnam andJulia Robinson that spans 21 years, with Matiyasevich completing the theorem in 1970.^[1][2][3] The theorem is now known asMatiyasevich's theorem 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 bepositive integers, the related problem ofpolynomial identity testing becomes a decidable (exponentiation-free) variation ofTarski's high school algebra problem, sometimes denoted${\displaystyle \overline{HSI}.}$^[4]

Hilbert formulated the problem as follows:^[5]

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 analgorithm. The term "rational integral" 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 polynomialDiophantine equation 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 anundecidable problem.

In a Diophantine equation, there are two kinds of variables: the parameters and the unknowns. TheDiophantine set consists of the parameter assignments for which the Diophantine equation is solvable. A typical example is the linear Diophantine equation in two unknowns,

${\displaystyle a_{1}x+a_{2}y=a_3,}$

where the equation is solvable if and only if thegreatest common divisor${\displaystyle gcd(a_1,a_2)}$ evenly divides${\displaystyle a_3}$. The set of all ordered triples${\displaystyle (a_1,a_2,a_3)}$ satisfying this restriction is called theDiophantine set defined by${\displaystyle a_{1}x+a_{2}y=a_3}$.In these terms, Hilbert's tenth problem asks whether there is an algorithm to determine if the Diophantine set corresponding to an arbitrary polynomial is non-empty.

The problem is generally understood in terms of thenatural numbers (that is, the non-negative integers) rather than arbitrary integers. However, 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. ByLagrange's four-square theorem, every natural number is the sum of the squares of four integers, so we could rewrite every natural-valued parameter in terms of the sum of the squares of four new integer-valued parameters. Similarly, since every integer is the difference of two natural numbers, we could rewrite every integer parameter as the difference of two natural parameters.^[3] Furthermore, we can always rewrite a system of simultaneous equations${\displaystyle p_1=0,\dots ,p_k=0}$ (where each${\displaystyle p_i}$ is a polynomial) as a single equation${\displaystyle p_1^2+\cdots +p_k^2=0}$.

Arecursively enumerable set can be characterized as one for which there exists analgorithm 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 ofcomputability theory (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 (also known as 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 asMatiyasevich's theorem (because he provided the crucial step that completed the proof) and theMRDP theorem (forYuri Matiyasevich,Julia Robinson,Martin Davis, andHilary Putnam). Becausethere 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

${\displaystyle p(a,x_1,\dots ,x_n)}$

with integer coefficients such that the set of values of${\displaystyle a}$ for which the equation

${\displaystyle p(a,x_1,\dots ,x_n)=0}$

has solutions in natural numbers is not computable. So, not only is there no general algorithm for testing Diophantine equations for solvability, but there is none even for this family of single-parameter equations.

Year	Events
1944	Emil Leon Post declares that Hilbert's tenth problem "begs for an unsolvability proof".
1949	Martin Davis usesKurt Gödel's method for applying theChinese remainder theorem as a coding trick to obtain his normal form for recursively enumerable sets: ${\displaystyle \left\{a\mid \mathrm{\exists }y\mathrm{\forall }k⩽y\mathrm{\exists }{x}_1,\dots ,x_n:p\left(a,k,y,x_1,\dots ,x_n\right)=0\right\}}$ where${\displaystyle p}$ is a polynomial with integer coefficients. Purely formally, it is only the bounded universal quantifier that stands in the way of this being a definition of a Diophantine set. Using a non-constructive but easy proof, he derives as a corollary to this normal form that the set of Diophantine sets is not closed under complementation, by showing that there exists a Diophantine set whose complement is not Diophantine. Because the recursively enumerable sets also are not closed under complementation, he conjectures that the two classes are identical.
1950	Julia Robinson, unaware of Davis's work, investigates the connection of the exponential function to the problem, and attempts to prove that EXP, the set of triplets${\displaystyle (a,b,c)}$ for which${\displaystyle a=b^c}$, is Diophantine. Not succeeding, she makes the followinghypothesis (later called J.R.): There is a Diophantine set${\displaystyle D}$of pairs${\displaystyle (a,b)}$such thatand for every positive${\displaystyle k,}$ there exists${\displaystyle (a,b)\in D}$such that${\displaystyle b>a^k.}$ Using properties of the Pell equation, she proves that J.R. implies that EXP is Diophantine, as well as the binomial coefficients, the factorial, and the primes.
1959	Working together, Davis and Putnam studyexponential Diophantine sets: sets definable by Diophantine equations in which some of the exponents may be unknowns. Using the Davis normal form together with Robinson's methods, and assuming the then unproved conjecture thatthere are arbitrarily long arithmetic progressions consisting of prime numbers, they prove that every recursively enumerable set is exponential Diophantine. They also prove as a corollary that J.R. implies that every recursively enumerable set is Diophantine, which in turn implies that Hilbert's tenth problem is unsolvable.
1960	Robinson simplifies the proof of theconditional result for exponential Diophantine sets and makes it independent from the conjecture about primes and thus a formal theorem. This makes the J.R. hypothesis a sufficient condition for the unsolvability of Hilbert's tenth problem. However, many were doubting that J.R. is true.[a]
1961–1969	During this period, Davis and Putnam find various propositions that imply J.R., and Robinson, having previously shown that J.R. implies that the set of primes is a Diophantine set, proves that this is anif and only if condition.Yuri Matiyasevich publishes some reductions of Hilbert's tenth problem.
1970	Drawing from the recently published work ofNikolai Vorob'ev on Fibonacci numbers,[6]Matiyasevich proves that the set${\displaystyle P=\{(a,b)\mid a>0,b=F_{2a}\},}$ where${\displaystyle F_n}$ is thenthFibonacci number, is Diophantine and exhibits exponential growth.[7] This proves the J.R. hypothesis, which by then had been an open question for 20 years. Combining J.R. with the theorem that every recursively enumerable set is exponential Diophantine, proves that recursively enumerable sets are Diophantine. This makes Hilbert's tenth problem unsolvable.

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 auniversal Diophantine equation:

There exists a polynomial${\displaystyle p(a,n,x_1,\dots ,x_k)}$such that, given any Diophantine set${\displaystyle S}$there is a number${\displaystyle n_0}$such that

$${\displaystyle S=\{a\mid \mathrm{\exists }{x}_1,\dots ,x_k[p(a,n_0,x_1,\dots ,x_k)=0]\}.}$$

This is true simply because Diophantine sets, being equal to recursively enumerable sets, are also equal toTuring 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^[8] that for any Diophantine set${\displaystyle S}$ of positive integers, there is a polynomial

${\displaystyle q(x_0,x_1,\dots ,x_n)}$

such that${\displaystyle S}$ consists of exactly the positive numbers among the values assumed by${\displaystyle q}$ asthe variables

${\displaystyle x_0,x_1,\dots ,x_n}$

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

${\displaystyle p(a,y_1,\dots ,y_n)=0}$

provides a Diophantine definition of${\displaystyle S}$, then it suffices to set

$${\displaystyle q(x_0,x_1,\dots ,x_n)=x_0[1-p(x_0,x_1,\dots ,x_n{)}^2].}$$

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${\displaystyle {\mathrm{\Pi }}_1^0}$ propositions, sometimes also called propositions ofGoldbach type.^[b] These are likeGoldbach's conjecture, in stating that all natural numbers possess a certain property that is algorithmically checkable for each particular number.^[c] 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.^[d] A number of important and celebrated problems are of this form: in particular,Fermat's Last Theorem, theRiemann hypothesis, and thefour color theorem. In addition the assertion that particularformal systems such as Peano arithmetic orZFC are consistent can be expressed as${\displaystyle {\mathrm{\Pi }}_1^0}$ sentences. The idea is to followKurt 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.

${\displaystyle {\mathrm{\Pi }}_1^0}$ 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 that can be verified by simple arithmetic. So if a${\displaystyle {\mathrm{\Pi }}_1^0}$ sentence is such that neither it nor its negation is provable in one of these systems, that sentence must be true.^{[citation needed]}

A particularly striking form ofGödel's incompleteness theorem is also a consequence of the Matiyasevich/MRDP theorem:

Let

${\displaystyle p(a,x_1,\dots ,x_k)=0}$

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

${\displaystyle p(n,x_1,\dots ,x_k)=0}$

has no solutions in natural numbers. Then there is a number${\displaystyle n_0}$ that is not output by${\displaystyle A}$ while in fact the equation

${\displaystyle p(n_0,x_1,\dots ,x_k)=0}$

has no solutions in natural numbers.

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

${\displaystyle p(n,x_1,\dots ,x_k)=0}$

and we may associate an algorithm${\displaystyle A}$ with any of the usual formal systems such asPeano arithmetic orZFC by letting it systematically generate consequences of the axioms and then output a number${\displaystyle n}$ whenever a sentence of the form

${\displaystyle \mathrm{\neg }\mathrm{\exists }{x}_1,\dots ,x_k[p(n,x_1,\dots ,x_k)=0]}$

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 thedegree of a Diophantine set as being the least degree of a polynomial in an equation defining that set. Similarly, we can call thedimension of such a set the fewest 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 1920sThoralf 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.^[e] 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. ButZi-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${\displaystyle A=\{0,1,2,3,\dots ,{\mathrm{\aleph }}_0\}}$ and let${\displaystyle C}$ be a proper non-empty subset of${\displaystyle 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${\displaystyle 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.

The proof of the MRDP theorem has been formalized inRocq (previously known asCoq).^[9]

Although Hilbert posed the problem for the rational integers, it can be just as well asked for manyrings (in particular, for any ring whose number of elements iscountable). Obvious examples are the rings of integers ofalgebraic number fields as well as therational 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 byJan Denef and Leonard Lipschitz and using class field theory, Harold N. Shapiro andAlexandra Shlapentokh were able to prove:

Hilbert's tenth problem is unsolvable for the ring of integers of any algebraic number field whoseGalois group over the rationals isabelian.

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 anyvariety over the rationals, the topological closure over the reals of the set of solutions has only finitely many components.^[10] 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.

In 2024, Peter Koymans and Carlo Pagano published a claimed proof that Hilbert’s 10th problem is undecidable for every ring of integers usingadditive combinatorics.^[11][12] Another team of mathematicians subsequently claimed another proof of the same result, using different methods.^[11][13]

• Tarski's high school algebra problem

• Hilbert, David (July 1902)."Mathematical problems".Bull. Amer. Math. Soc.8 (10):437–479.doi:10.1090/S0002-9904-1902-00923-3.
• Matiyasevich, Yuri V. (1993).Hilbert's Tenth Problem. MIT Press.ISBN 9780262132954.OCLC 908983760.

• Hilbert, David (1901). "Mathematische Probleme".Archiv der Mathematik und Physik. 3rd series (in German).1:44–63,213–247.
• Davis, Martin;Matiyasevich, Yuri;Robinson, Julia (1976). "Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a Negative Solution". InFelix E. Browder (ed.).Mathematical Developments Arising from Hilbert Problems.Proceedings of Symposia in Pure Mathematics. Vol. XXVIII.2.American Mathematical Society. pp. 323–378.ISBN 0-8218-1428-1.Zbl 0346.02026. Reprinted inThe 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.
• Davis, Martin;Hersh, Reuben (1973). "Hilbert's 10th Problem".Scientific American.229 (5):84–91.Bibcode:1973SciAm.229e..84D.doi:10.1038/scientificamerican1173-84.
• 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.
• M. Ram Murty and Brandon Fodden: "Hilbert’s Tenth Problem: An Introduction to Logic, Number Theory, and Computability", American Mathematical Society,ISBN 978-1-4704-4399-3 (June, 2019).
• Shlapentokh, Alexandra (2007).Hilbert's tenth problem. Diophantine classes and extensions to global fields. New Mathematical Monographs. Vol. 7. Cambridge:Cambridge University Press.ISBN 978-0-521-83360-8.Zbl 1196.11166.

• Hilbert's Tenth Problem: a History of Mathematical Discovery
• Hilbert's Tenth Problem page!
• Sun, Zhi-Wei (14 April 2000)."On Hilbert's Tenth Problem and Related Topics"(PDF).maths.nju.edu.cn. Retrieved27 September 2025.
• Trailer for Julia Robinson and Hilbert's Tenth Problem onYouTube

• Hilbert's problems
• Diophantine equations
• Undecidable problems

• CS1 Russian-language sources (ru)
• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from September 2025
• All articles with unsourced statements
• Articles with unsourced statements from September 2015
• CS1 German-language sources (de)
• CS1: long volume value