Diophantine set

A set consisting of (ordered) -tuples of integers (non-negative integers, positive integers) for which it is possible to write down a Diophantine equation (cf. Diophantine equations)

(*)

which depends on parameters , the permissible values of which are integers (non-negative integers or positive integers, respectively), and which is solvable for if and only if . In this context it is irrelevant whether the solution is understood to be in integers, non-negative integers or positive integers, since equation (*) is solvable in integers, non-negative integers or positive integers if and if only if the equation

is solvable in positive integers (if and only if the equation

is solvable in non-negative integers, or, respectively, if and only if the equation

is solvable in integers), since according to Lagrange's theorem any non-negative integer can be represented as a sum of four squares.

For any Diophantine set it is possible to find a corresponding equation (*) in which the degree of the polynomial is at most 4 (which is attained by increasing the number of unknowns). For each Diophantine set of non-negative integers it is possible to find an equation of the form in addition to the general equation (*); in other words, any Diophantine set of non-negative integers is the set of all non-negative values assumed by some polynomial with integer coefficients, for arbitrary values of the variables. A polynomial of degree at most 6 may be taken as if the variables assume arbitrary integer values.

The class of Diophantine sets is closed with respect to the operations of permutation and identification of arguments, union, intersection, direct product, and projection (the projection of a set consisting of ordered -tuples of numbers is the set ), and also with respect to the operation which transforms a set into the set

The class of Diophantine sets coincides with the class of recursively enumerable sets (cf. Diophantine equations, solvability problem of; Enumerable set), and all the results valid for recursively enumerable sets are applicable to Diophantine sets. In particular, it follows from the theorem of the existence of a universal recursively enumerable set that there exists a number such that for each there exists a polynomial with integer coefficients which is universal in the following sense. For each Diophantine (recursively enumerable) set , consisting of ordered -tuples of numbers, it is possible to find a value of the parameter (an index of the set ) such that the equation

is solvable for if and only if . There also exist polynomials which are universal in other senses (see, for example, [1]).

Many sets of number-theoretic interest are Diophantine sets. These include, for example, the set of all prime numbers, the set of all perfect numbers, and the set of all for which Fermat's equation

is solvable.

The proof of the theorem stating that recursively enumerable sets are Diophantine is effective, i.e. for a recursively enumerable set given in any standard form it is possible to find the corresponding Diophantine equation. This universal method, which does not involve the specific character of the set under consideration, yields fairly cumbersome polynomials, but for certain specific sets it is possible to find fairly simple Diophantine representations by using properties of these sets other than enumerability.

Sets which can be represented as sets of all ordered -tuples of elements of some ring for which an equation of the type (*) (where is a polynomial with integer coefficients or with coefficients from ) is solvable in this ring for may also be considered as Diophantine sets.

References

[1]	Yu. V. Matiyasevich, "Diophantine sets" Russian Math. Surveys , 27 : 5 (1972) pp. 124–164 Uspekhi Mat. Nauk , 27 : 5 (1972) pp. 185–222

Comments

The theorem that every recursively enumerable set is Diophantine is due to Yu.V. Matiyasevich (1970). A detailed proof and historical discussion can be found in [a1]. Various ramifications are discussed in [a2]. As there are recursively enumerable sets which are not recursive it follows that there are Diophantine sets which are not recursive and from that it follows directly that Hilbert's 10th problem is unsolvable. (Hilbert's 10th problem asks for a (universal) algorithm to test for the solvability of a Diophantine equation in integers.)

References

[a1]	M. Davis, "Hilbert's 10-th problem is unsolvable" Amer. Math. Monthly , 80 (1973) pp. 233–269
[a2]	J. Robinson, "Hilbert's 10-th problem. Diophantine equations: positive aspects of a negative solution" F.E. Browder (ed.) , Mathematical developments arising from Hilbert problems , Proc. Symp. Pure Math. , 28 , Amer. Math. Soc. (1976) pp. 223–378