The Setting
Hilbert’s tenth problem concerns equations with integer coefficients, in which a tuple of natural numbers is given and a tuple of natural numbers is sought, where is the set of natural numbers. Such an equation picks out the inputs at which it is solvable, and by the Davis-Putnam-Robinson-Matiyasevich theorem every recursively enumerable set arises in this way. The solution over an input need not be unique: holds for some exactly when is composite, with one solution for each ordered factorization with , while has a solution exactly when is a square, and then only one.
The question is whether every recursively enumerable set is picked out by an equation of the second kind, with exactly one solution over each of its members. Single-fold representability is the statement that every recursively enumerable set is picked out by an equation with exactly one solution over each of its members.
Single-fold Representations
For , a set is recursively enumerable when some partial recursive function on is defined exactly at the members of .
For , write for the ring of polynomials with integer coefficients in the input variables and the auxiliary variables . The value of a polynomial in this ring at an input tuple and an auxiliary tuple is the integer obtained by substituting for and for : (1)✦
A single-fold Diophantine representation of a set is a polynomial whose zeros lie over exactly the members of , one auxiliary tuple over each: for all and , (2)✦
The Definition
Definition 1 (Single-fold representability). Single-fold representability is the statement that every recursively enumerable set with has a single-fold Diophantine representation in at least one auxiliary variable: for every such and , $$\exists\, m \ge 1 \;\; \exists\, P \in \mathbb{Z}[A_1, \dots, A_n, W_1, \dots, W_m] \;\text{ satisfying } \eqref{eq:claim2}.$$(3)✦
In the paper, the notions read: over , a set is recursively enumerable if a deterministic computation accepts exactly its members, a Diophantine representation of is a polynomial with if and only if for some , and the representation is single-fold if that complete tuple is unique whenever it exists.
What Is Checked
Single-fold representability (3) is stated over recursively enumerable subsets of , integer polynomials in input and auxiliary variables with their values (1) at tuples of natural numbers, and single-fold Diophantine representation (2).