In mathematics, a Diophantine set of j-tuples of integers is a set S for which there is some polynomial with integer coefficients
such that a tuple
of integers is in S if and only if there exist some (non-negative)  integers
Such a polynomial equation over the integers is called a Diophantine equation. In other words, a Diophantine set is a set of the form
where f is a polynomial function with integer coefficients. 
Matiyasevich's theorem, published in 1970, states that a set of integers is Diophantine if and only if it is recursively enumerable. A set S is recursively enumerable precisely if there is an algorithm that, when given an integer, eventually halts if that input is a member of S and otherwise runs forever. 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 theorem effectively settled Hilbert's tenth problem. It implies that Hilbert's tenth problem is unsolvable. This problem is the challenge to find a general algorithm which can decide whether a given system of Diophantine equations has a solution among the integers. David Hilbert posed the problem in his celebrated list, from his 1900 address to the International Congress of Mathematicians.
The well known Pell equation
is an example of a Diophantine equation with a parameter. As has long been known, the equation has a solution in the unknowns x,y precisely when the parameter d is 0 or not a perfect square. In the present context, one says that 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:
- The equation a = (2x + 3)y defines the set of numbers that are not powers of 2.
Full article ▸