Diophantine set

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

$$ \tag{* } P ( a _ {1} \dots a _ {n} , x _ {1} \dots x _ {l} ) = 0 $$

which depends on $ n $ parameters $ a _ {1} \dots a _ {n} $, the permissible values of which are integers (non-negative integers or positive integers, respectively), and which is solvable for $ x _ {1} \dots x _ {l} $ if and only if $ \langle a _ {1} \dots a _ {n} \rangle \in \mathfrak M $. 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

$$ P ( a _ {1} \dots a _ {n} , y _ {1} - z _ {1} \dots y _ {l} - z _ {l} ) = 0 $$

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

$$ P ( a _ {1} \dots a _ {n} , z _ {1} + 1 \dots z _ {l} + 1 ) = 0 $$

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

$$ P ( a _ {1} \dots a _ {n} , p _ {1} ^ {2} + q _ {1} ^ {2} + r _ {1} ^ {2} + s _ {1} ^ {2} \dots p _ {l} ^ {2} + q _ {l} ^ {2} + r _ {l} ^ {2} + s _ {l} ^ {2} ) = 0 $$

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 $ P $ 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 $ P ( x _ {1} \dots x _ {l} ) = a _ {1} $ 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 $ P $ 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 $ \mathfrak M $ consisting of ordered $ n $- tuples of numbers is the set $ \{ {\langle a _ {1} \dots a _ {n-} 1 \rangle } : {\exists b [ \langle a _ {1} \dots a _ {n-} 1 , b \rangle \in \mathfrak M ] } \} $), and also with respect to the operation which transforms a set $ \mathfrak M $ into the set

$$ \{ {\langle a _ {1} \dots a _ {n-} 1, b \rangle } : {\forall c [ c \leq b \Rightarrow < a _ {1} \dots a _ {n-} 1 , c > \in \mathfrak M ] } \} . $$

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 $ l $ such that for each $ n $ there exists a polynomial $ U _ {n} ( a _ {1} \dots a _ {n} , m, x _ {1} \dots x _ {l} ) $ with integer coefficients which is universal in the following sense. For each Diophantine (recursively enumerable) set $ \mathfrak M $, consisting of ordered $ n $- tuples of numbers, it is possible to find a value of the parameter $ m $( an index of the set $ \mathfrak M $) such that the equation

$$ U _ {n} ( a _ {1} \dots a _ {n} , m, x _ {1} \dots x _ {l} ) = 0 $$

is solvable for $ x _ {1} \dots x _ {l} $ if and only if $ \langle a _ {1} \dots a _ {n} \rangle \in \mathfrak M $. 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 $ n $ for which Fermat's equation

$$ x ^ {n} + y ^ {n} = z ^ {n} $$

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 $ n $- tuples of elements of some ring $ K $ for which an equation of the type (*) (where $ P $ is a polynomial with integer coefficients or with coefficients from $ K $) is solvable in this ring for $ x _ {1} \dots x _ {l} $ 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