In mathematics, a Diophantine equation is an equation of the form P(x1, ..., xj, y1, ..., yk) = 0 (usually abbreviated P(, ) = 0) where P(, ) is a polynomial with integer coefficients, where x1, ..., xj indicate parameters and y1, ..., yk indicate unknowns.
A Diophantine set is a subset S of , the set of all j-tuples of natural numbers, so that for some Diophantine equation P(, ) = 0,
That is, a parameter value is in the Diophantine set S if and only if the associated Diophantine equation is satisfiable under that parameter value. The use of natural numbers both in S and the existential quantification merely reflects the usual applications in computability theory and model theory. It does not matter whether natural numbers refer to the set of nonnegative integers or positive integers since the two definitions for Diophantine sets are equivalent. One can equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers. This is possible because, by Lagrange's four-square theorem, the non-negative integers are exactly the integers that can be written as a sum of four squares, so each quantifier over the natural numbers can be replaced by four quantifiers over the integers. It is also sufficient to assume P is a polynomial over and multiply P by the appropriate denominators to yield integer coefficients. However, whether quantification over rationals can also be substituted for quantification over the integers is a notoriously hard open problem.
The MRDP theorem (so named for the initials of the four principal contributors to its proof) states that a set of integers is Diophantine if and only if it is computably enumerable. A set of integers S is computably enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of S and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging to number theory, can be taken rather in logical or computability-theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work.
Matiyasevich's completion of the MRDP theorem settled Hilbert's tenth problem. Hilbert's tenth problemDavid Hilbert posed the problem in his celebrated list, from his 1900 address to the International Congress of Mathematicians. was to find a general algorithm that can decide whether a given Diophantine equation has a solution among the integers. While Hilbert's tenth problem is not a formal mathematical statement as such, the nearly universal acceptance of the (philosophical) identification of a decision algorithm with a total computable predicate allows the MRDP theorem to be used to conclude that the tenth problem is unsolvable.
Examples In the following examples, the natural numbers refer to the set of positive integers.
The equation
is an example of a Diophantine equation with a parameter x and unknowns y1 and y2. The equation has a solution in y1 and y2 precisely when x can be expressed as a product of two integers greater than 1, in other words x is a composite number. Namely, this equation provides a Diophantine definition of the set
{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...}
consisting of the composite numbers.
Other examples of Diophantine definitions are as follows: The equation with parameter x and unknowns y1, y2 only has solutions in when x is a sum of two perfect squares. The Diophantine set of the equation is {2, 5, 8, 10, 13, 17, 18, 20, 25, 26, ...}. The equation with parameter x and unknowns y1, y2. This is a Pell equation, meaning it only has solutions in when x is not a perfect square. The Diophantine set is {2, 3, 5, 6, 7, 8, 10, 11, 12, 13, ...}. The equation is a Diophantine equation with two parameters x1, x2 and an unknown y, which defines the set of pairs (x1, x2) such that x1 < x2.
Matiyasevich's theorem
Matiyasevich's theorem, also called the Matiyasevich–Robinson–Davis–Putnam or MRDP theorem, says:
Every computably enumerable set is Diophantine, and the converse.
Equivalently to the definition given above, a set S of integers is computably enumerable if there is an algorithm that runs forever and lists the members of S. Working over the integers, a set S is Diophantine precisely if there is some polynomial with integer coefficients f(n, x1, ..., xk) such that an integer n is in S if and only if there exist some integers x1, ..., xk with f(n, x1, ..., xk) = 0.
It is easy to see that every Diophantine set is computably enumerable: given a Diophantine equation f(n, x1, ..., xk) = 0, one can construct an algorithm that tries all possible values for n, x1, ..., xk (in, say, some simple order consistent with the increasing order of the sum of their absolute values), and prints n every time f(n, x1, ..., xk) = 0. This algorithm will run forever and will list exactly the n for which f(n, x1, ..., xk) = 0 has a solution in x1, ..., xk.
Earlier work by Martin Davis, Hilary Putnam and Julia Robinson had shown that every computably enumerable set is exponential Diophantine, that is, definable by an equation in which exponentiation is also allowed, and Robinson had shown that exponentiation is itself Diophantine provided there is a Diophantine relation of roughly exponential growth. In 1970 Yuri Matiyasevich completed the proof by using Fibonacci numbers, which grow exponentially, to construct such a relation: he showed that the relation is Diophantine.
Application to Hilbert's tenth problem Hilbert's tenth problem asks for a general algorithm deciding the solvability of Diophantine equations. Since there exist computably enumerable sets that are not computable, such as the set encoding the halting problem, Matiyasevich's result implies that no such algorithm exists.
Refinements
Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (announced by Matiyasevich in 1975, with details published by James P. Jones in 1982) or 11 integer variables (announced by Sun Zhiwei in 1992, with the full proof published in 2021).
Further applications
Matiyasevich's theorem has since been used to prove that many problems from calculus and differential equations are unsolvable.
One can also derive the following stronger form of Gödel's first incompleteness theorem from Matiyasevich's result:
Corresponding to any given consistent axiomatization of number theory,More precisely, given a -formula representing the set of Gödel numbers of sentences that recursively axiomatize a consistent theory extending Robinson arithmetic. one can explicitly construct a Diophantine equation that has no solutions, but such that this fact cannot be proved within the given axiomatization.
According to the incompleteness theorems, every consistent, recursively axiomatizable theory that is strong enough to express basic arithmetic is incomplete, meaning that some statements in its language can be neither proved nor disproved within it. The statement above shows that such statements can always be taken to assert the unsolvability of a particular Diophantine equation.
Notes
References
English translation in Soviet Mathematics 11 (2), pp. 354–357.
External links Matiyasevich theorem article on Scholarpedia.
he:הבעיה העשירית של הילברט