The Setting
Take a relation on tuples of natural numbers. A Diophantine representation of is a polynomial with integer coefficients such that exactly when for some auxiliary tuple of natural numbers; by the theorem of Davis, Putnam, Robinson and Matiyasevich, the relations that have one are exactly the recursively enumerable relations.
A representation can have many auxiliary tuples at one input: represents the composite numbers with one tuple for each ordered factorization with . The question is which recursively enumerable relations have a representation whose auxiliary tuple, whenever it exists, is unique. The same question is asked of the graph of a map from to , for a set of output variables, that is, of the relation on pairs of an input tuple and an output tuple , and of a relation together with its complement.
The Definition
Definition 1. A single-fold representation of a relation is a polynomial with integer coefficients in the input variables and finitely many auxiliary variables such that, for every , (1)✦
A relation is single-fold, written , when it has a single-fold representation: $$\mathrm{SF}(R) \iff \exists\, k \in \mathbb{N}\ \exists\, P \in \mathbb{Z}[a, w_1, \dots, w_k] \text{ satisfying } \eqref{eq:claim1}.$$(2)✦
A total map , with a set of output variables, has a single-fold graph when its graph is a single-fold relation on : (3)✦
A function is a single-fold scalar function when the map sending to the one-entry tuple has a single-fold graph, that is, when is a single-fold relation: (4)✦
A relation is two-sided single-fold when both and its complement are single-fold: (5)✦
In the paper, the definition reads: a single-fold polynomial system for is a finite list of polynomial equations with integer coefficients whose set of complete tuples , those satisfying all the equations , is a singleton for and empty otherwise, and a single-fold graph of , for , is such a system for , the paper’s being the page’s .
Here a system is one polynomial, and a map with a single-fold graph is defined on all of .
What Is Checked
The definitions are stated over relations and total maps , for any sets and of input and output variables, with representing polynomials over in finitely many auxiliary variables ranging over .