The Setting
By the theorem of Davis, Putnam, Robinson and Matiyasevich, for every integer every recursively enumerable set is Diophantine: there are an integer and a polynomial with integer coefficients in variables such that, for , exactly when for some . One may come with many such .
The question is whether can always be chosen so that each has only one .
Single-fold Representations
A single-fold representation of a relation , where is a set of input variables, is a polynomial with integer coefficients in the variables () and in the auxiliary variables of a finite set , such that for all and (1)✦
A relation is single-fold, written , when it has a single-fold representation.✦ A polynomial represents a set single-fold when it is a single-fold representation of with the auxiliary variables .✦
The Claim
Theorem 1.
Let and let be recursively enumerable. Then for some (2)✦
Let and let be recursively enumerable. Then (3)✦
Let be a set and let be single-fold. Then for some (4)✦
In the paper, the result reads: for every integer and every recursively enumerable there are an integer and such that, for every , is if and if .
What Is Checked
The claim is stated over recursively enumerable relations on tuples of natural numbers, polynomials with integer coefficients evaluated at natural numbers, single-fold representations of a relation and the class of relations that have one, and polynomials representing a set single-fold.