Inmathematics, aDiophantine equation is an equation of the formP(x1, ...,xj,y1, ...,yk) = 0 (usually abbreviatedP(x,y) = 0) whereP(x,y) is apolynomial with integercoefficients, wherex1, ...,xj indicate parameters andy1, ...,yk indicate unknowns.
ADiophantine set is asubsetS of, the set of allj-tuples of natural numbers, so that for someDiophantine equationP(x,y) = 0,
That is, a parameter value is in the Diophantine setSif and only if the associated Diophantine equation issatisfiable under that parameter value. The use of natural numbers both inS and the existential quantification merely reflects the usual applications incomputability theory andmodel 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. We can also equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers.[1] Also it is sufficient to assumeP is a polynomial over and multiplyP 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.[2]
The MRDP theorem (so named for the initials of the four principal contributors to its solution) states that a set of integers is Diophantine if and only if it iscomputably enumerable.[3] A set of integersS is computably enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member ofS and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging tonumber theory, can be taken rather inlogical 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 settledHilbert's tenth problem.Hilbert's tenth problem[4] was to find a generalalgorithm 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 decisionalgorithm with atotal computable predicate allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.
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 parameterx and unknownsy1 andy2. The equation has a solution iny1 andy2 precisely whenx can be expressed as a product of two integers greater than 1, in other wordsx is acomposite number. Namely, this equation provides aDiophantine definition of the set
consisting of the composite numbers.
Other examples of Diophantine definitions are as follows:
Matiyasevich's theorem, also called theMatiyasevich–Robinson–Davis–Putnam or MRDP theorem, says:
A setS of integers iscomputably enumerable if there is an algorithm such that: For each integer inputn, ifn is a member ofS, then the algorithm eventually halts; otherwise it runs forever. That is equivalent to saying there is an algorithm that runs forever and lists the members ofS. A setS isDiophantine precisely if there is somepolynomial with integer coefficientsf(n,x1, ...,xk)such that an integern is inS if and only if there exist some integersx1, ...,xksuch thatf(n,x1, ...,xk) = 0.
Conversely, every Diophantine set iscomputably enumerable:consider a Diophantine equationf(n,x1, ...,xk) = 0.Now we make an algorithm that simply tries all possible values forn,x1, ...,xk (in, say, some simple order consistent with the increasing order of the sum of their absolute values),and printsn every timef(n,x1, ...,xk) = 0.This algorithm will obviously run forever and will list exactly thenfor whichf(n,x1, ...,xk) = 0 has a solutioninx1, ...,xk.
Yuri Matiyasevich utilized a method involvingFibonacci numbers, whichgrow exponentially, in order to show that solutions to Diophantine equations may grow exponentially. Earlier work byJulia Robinson,Martin Davis andHilary Putnam – hence, MRDP – had shown that this suffices to show that everycomputably enumerable set is Diophantine.
Hilbert's tenth problem asks for a general algorithm deciding the solvability of Diophantine equations. The conjunction of Matiyasevich's result with the fact that mostrecursively enumerable languages are notdecidable implies that a solution to Hilbert's tenth problem is impossible.
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 (Matiyasevich, 1977) or 11 integer variables (Zhi Wei Sun, 1992).
Matiyasevich's theorem has since been used to prove that many problems fromcalculus anddifferential equations are unsolvable.
One can also derive the following stronger form ofGödel's first incompleteness theorem from Matiyasevich's result:
According to theincompleteness theorems, a powerful-enough consistent axiomatic theory is incomplete, meaning the truth of some of its propositions cannot be established within its formalism. The statement above says that this incompleteness must include the solvability of a diophantine equation, assuming that the theory in question is a number theory.