Diophantine set


In mathematics, a Diophantine equation is an equation of the form P = 0 where P is a polynomial with integer coefficients. A Diophantine set is a subset S of Nj 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. Note that the use of natural numbers both in S and the existential quantification merely reflects the usual applications in computability and model theory. We can equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers. Also it is 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 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 recursion-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 problem was to find a general algorithm which 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 identification of a decision algorithm with a total computable predicate allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.

Examples

The Pell equation
is an example of a Diophantine equation with a parameter. The equation has a solution in the unknowns precisely when the parameter is 0 or not a perfect square. Namely, this equation provides a Diophantine definition of the set
consisting of 0 and the natural numbers that are not perfect squares.
Other examples of Diophantine definitions are as follows:
Matiyasevich's theorem, also called the Matiyasevich–Robinson–Davis–Putnam or MRDP theorem, says:
A set S of integers is computably enumerable if there is an algorithm such that: For each integer input n, if n is a member of S, 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 of S. A set S is Diophantine precisely if there is some polynomial with integer coefficients f
such that an integer n is in S if and only if there exist some integers
x1,..., xk
such that f = 0.
Conversely, every Diophantine set is computably enumerable:
consider a Diophantine equation f = 0.
Now we make an algorithm which simply tries all possible values for
n, x1,..., xk,
and prints n every time f = 0.
This algorithm will obviously run forever and will list exactly the n
for which f = 0 has a solution
in x1,..., xk.

Proof technique

utilized a method involving Fibonacci numbers, which grow exponentially, in order to show that solutions to Diophantine equations may grow exponentially. Earlier work by Julia Robinson, Martin Davis and Hilary Putnam – hence, MRDP – had shown that this suffices to show that every computably enumerable set is Diophantine.

Application to Hilbert's tenth problem

asks for a general algorithm deciding the solvability of Diophantine equations. The conjunction of Matiyasevich's result with earlier results, collectively now termed the MRDP theorem, implies that a solution to Hilbert's tenth problem is impossible.

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 or 11 integer variables.

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:
According to the incompleteness 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.