The Setting
A single-fold representation of a relation is a polynomial with integer coefficients in an input tuple and finitely many auxiliary variables such that, for every and all , (1) A relation is single-fold when it has a single-fold representation.
By a theorem of Matiyasevich, every recursively enumerable set has a single-fold exponential Diophantine representation. The relation is the set of triples with and . The question is whether is single-fold, and the route here goes through a function with a single-fold graph and growth bounded on both sides, and through a system of two Pell equations in nine auxiliaries.
Pell Equations and the System
For let . The solutions in natural numbers of the Pell equation are the pairs , , given by (2)
For , the input value of a triple is the natural number (3)✦
For a function and the same and , the Pell system for powers is the relation between a triple and an auxiliary tuple given by the conditions (4)✦ A solution of for a triple is a tuple that satisfies the conditions (4).
The Claim
Theorem 1. Let be a function whose graph is single-fold, let be a real number and a natural number, and write for the natural logarithm. If satisfies the growth condition (5)✦ then is single-fold. Without any hypothesis, (6)✦
Let , and be as in (5), and let . If the Pell system has a solution for , then (7)✦ Any two solutions and of for a triple are equal: (8)✦ If and , then for every there is with (9)✦
For every function whose graph is single-fold and all , the relation on (10)✦
Each real admits a natural number with (11)✦
Every natural number satisfies (12)✦ Let , and be natural numbers with , and . If satisfy and , then (13)✦ Let , and let satisfy . If is the integer quotient of by , then (14)✦
What Is Checked
The claims are stated over the single-fold representations of (1), the relation , the graph of an arbitrary function with its growth condition (5), the Pell values of (2), and the Pell system (4) with its input value (3).