Encoding every accepting computation by exactly one Diophantine witness

← All digests

Family 242 · Mathematical logic
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-21

1. The question

A polynomial equation with integer coefficients can encode a computer program. Given an input, the equation can have a natural-number solution exactly when the program eventually accepts that input. This is the arithmetic universality behind the negative solution of Hilbert’s tenth problem.

But the encoding usually permits many solutions for one accepting computation. Extra variables may describe the same rational number in different ways, choose different arithmetic certificates, or use different bases to store the run.

Can all that redundancy be removed? Family 242 contains a manuscript dated 24 September 2026 claiming that every computably enumerable relation has a polynomial representation with exactly one complete auxiliary tuple for each member. This is the single-fold conjecture, and it implies the weaker finite-fold conjecture.

2. Background and essential definitions

Enumerable does not mean decidable

Throughout, $\mathbb N=\{0,1,2,\ldots\}$. A set $S\subseteq\mathbb N^n$ is computably enumerable, also called recursively enumerable, if a deterministic machine accepts exactly its members. On a nonmember, the machine may run forever.

A decidable set has an algorithm that halts on every input and answers both yes and no correctly. The halting problem is a standard example of a computably enumerable set that is not decidable.

A Diophantine representation of $S$ is a polynomial with integer coefficients,

$$P(A_1,\ldots,A_n,W_1,\ldots,W_m),$$

such that an input $a$ belongs to $S$ precisely when some auxiliary tuple $w\in\mathbb N^m$ satisfies $P(a,w)=0$. The input variables are fixed; only the witness variables are searched over.

Counting the whole witness

The representation is single-fold if there is exactly one witness tuple for every member and none for every nonmember. It is finite-fold if each input has only finitely many witnesses.

“Complete tuple” includes every variable introduced inside the construction. A unique accepting run is not enough if a subsidiary equation allows several quotient choices, rational-coordinate encodings or inactive branch variables.

For example, the inequality $u\geq v$ can be encoded by $u-v=s$ with $s\in\mathbb N$. Once $u,v$ are fixed, this slack variable is unique. Division by a positive integer can be encoded by

$$a=dq+r,\qquad 0\leq r<d,$$

which fixes both quotient and remainder. By contrast, an unrestricted equation expressing coprimality through Bézout coefficients usually has many solutions, so it requires normalization.

A finite list of polynomial equations can be replaced over $\mathbb N$ by one equation:

$$F_1^2+\cdots+F_s^2=0.$$

This introduces no new variables and preserves the entire solution set. The difficult issue is therefore unique polynomial systems, not the final conversion from a system to one polynomial.

3. Development history and previous partial results

Julia Robinson developed a route from sufficiently strong Diophantine growth conditions to exponentiation. Davis, Putnam and Robinson proved that every recursively enumerable relation has an exponential Diophantine representation, permitting exponentiation in addition to ordinary polynomial operations.

Matiyasevich’s 1970 construction supplied the growth needed to replace exponentiation and complete the polynomial representation theorem. Together these results solved Hilbert’s tenth problem negatively: an algorithm deciding polynomial solvability would decide every computably enumerable set, including undecidable ones.

That theorem does not control the number of witnesses. In 1974, Matiyasevich proved a stronger uniqueness theorem for exponential representations: every recursively enumerable relation has an exponential representation with one complete auxiliary tuple. The same work identified single-fold binary exponentiation as the crucial remaining polynomial problem.

The single-fold and finite-fold conjectures ask whether uniqueness, or at least finiteness, survives after exponentiation has been eliminated. This is not merely a reformulation of the original representation theorem. Replacing a concise operation by an existential polynomial construction can introduce many internal witnesses.

There are important positive results in other domains. Miller and Shlapentokh obtained single-fold definitions using witnesses in characteristic-zero polynomial rings, and finite-fold definitions over related rings of functions. Those results do not give the natural-number witness theorem claimed here.

The new manuscript combines classical Pell-equation methods with rank-one elliptic-curve heights. Poonen’s use of elliptic curves and denominator growth in Diophantine definability is a predecessor, while Jones and Matiyasevich’s register-machine and bit-masking methods supply the computational encoding framework. The advertised new arithmetic step is a uniquely represented growth function strong enough to select exact Pell indices.

4. What the new manuscripts claim

For every $n\geq1$ and every computably enumerable $S\subseteq\mathbb N^n$, the manuscript asserts the existence of $m\geq1$ and an integer polynomial $P$ such that

$$\#\{w\in\mathbb N^m:P(a,w)=0\} =\begin{cases} 1,&a\in S,\\ 0,&a\notin S. \end{cases}$$

All auxiliary variables, including those implementing arithmetic subroutines, count toward this uniqueness. The variables range over nonnegative integers, not arbitrary rational numbers, integer tuples with unrestricted signs, or a polynomial-ring witness domain.

The main undecidability consequence has a strong promise. There exist fixed integers $m,D\geq1$ such that no algorithm can, for every polynomial in $m$ variables of degree at most $D$ known to have at most one natural-number solution, always halt and decide whether a solution exists.

The input is promised to have zero or one solution. The algorithm is not being asked to verify the promise. Nor is this the trivial promise of exactly one solution, under which the answer would already be yes.

The construction uses arithmetic constants fixed independently of the enumerable set and its inputs. The paper establishes their existence but does not supply all their numerical values, the final expanded polynomial coefficients, or a procedure for numerically choosing those constants. Its theorem is an existence result for the polynomial, rather than a displayed practical compiler.

5. Why the advance matters

Importance: 5/5, provisional. The theorem would settle longstanding refinements of the Diophantine representation theorem and show that undecidability persists even when each equation has at most one witness.

This separates difficulty caused by searching a large or redundant solution space from difficulty intrinsic to existence. Removing all multiplicity would still leave an undecidable solvability problem.

Uniqueness also strengthens the correspondence between computation and arithmetic. Every accepting input would determine one arithmetic certificate, with no alternative encodings hidden in the auxiliary variables.

The score concerns that theoretical strengthening. It does not provide an efficient way to find the unique solution, a computable bound on its size, or a decision procedure for the promised class. Indeed, the claimed undecidability consequence rules out the last possibility.

6. The main idea

Normalize every arithmetic choice

The construction begins with a discipline for polynomial encodings. Integers use a unique positive–negative sign code. Rational numbers use reduced numerator–denominator data together with normalized inverse witnesses. Quotients, remainders and inequality slacks are fixed by their arguments.

Case distinctions require special care. A selector chooses one active branch, and every local variable in each inactive branch is forced to zero. Otherwise a branch that contributes no equation could still introduce arbitrarily many witnesses.

These conventions are carried through composition. A subsidiary call contributes its full internal tuple, so uniqueness cannot be lost silently inside an arithmetic abbreviation.

Obtain a uniquely represented growth function

The arithmetic construction uses the elliptic curve

$$E:\quad y^2=x^3-25x.$$

The manuscript supplies a rank-one calculation: its rational points have the form $nP+t$, where $n\in\mathbb Z$, $P$ is a fixed generator of the free part and $t$ belongs to a finite torsion subgroup.

A normalized representative is selected for each positive absolute index. After a fixed scalar multiplication, let $W_j$ be the maximum of the absolute numerator and positive denominator of the reduced x-coordinate. Height theory gives

$$\log W_j=a_Ej^2+O(1),\qquad a_E>0,$$

with a uniformly bounded error. The chosen scalar enlarges the quadratic coefficient enough to separate the integer indices while retaining a controlled error.

The useful comparison is a discrete difference:

$$\log\frac{W_{2k}W_rW_1}{W_k^2W_{r+1}} =2a_E(k^2-r)+O(1).$$

A fixed multiplicative window around the ratio therefore singles out $r=k^2$. The polynomial system uses point additions, products and comparisons; the indices and logarithms appear in the explanatory growth argument, not as extra polynomial operations.

For an input $u$, bracket it uniquely between consecutive heights and output the height at the squared index. The resulting function $g(u)$ has a single-fold polynomial graph and intermediate growth, with bounds of the form

$$\delta(\log u)^2<\log g(u)<u\log u$$

for sufficiently large $u$ and a fixed $\delta>0$.

Use growth to pin down powers

Pell equations have recursively ordered families of solutions with rapidly growing coordinates. Congruences can constrain the solution index, but a congruence alone usually identifies only a residue class of indices.

The new growth function supplies a cutoff. Its upper bound forces the relevant indices below a modulus, turning congruence information into exact equality. Its lower bound ensures that the intended solutions are still admitted.

An integer quotient then recovers $c=b^n$, with a unique complete witness for every $b\geq2$ and $n\geq0$. This is the single-fold power graph needed to eliminate exponentiation from the computational encoding.

Pack one deterministic run into integers

A deterministic counter machine has a unique run on each input. The manuscript stores its successive states and counter values as digits of finitely many integers in a large base.

Binary-containment tests, implemented through powers and Lucas’s binomial parity criterion, restrict which digits can be nonzero. Polynomial identities enforce legal transitions and the first accepting halt.

A clock and a dyadic interval select one power-of-two base for the entire run. This prevents the same history from being encoded in many larger bases. Once the run and base are fixed, every displayed integer and every internal arithmetic witness is fixed.

The number of variables depends on the chosen machine and fixed arithmetic constructions, not on the particular input or its halting time. Very long computations are stored in very large integers rather than by introducing a new variable for every step.

Derive the promise result

Apply the representation theorem to one fixed undecidable computably enumerable set. Substituting an input tuple into the parameter variables produces a polynomial in the same fixed number of witness variables, with a fixed degree bound.

Every resulting polynomial has at most one solution. A solver for the promised class would decide membership in the original undecidable set. This establishes the claimed impossibility without requiring a uniform algorithm that constructs representations for all enumerable sets.

7. Scope, limitations, and open questions

The theorem counts solutions over $\mathbb N$, including zero. Passing to other witness domains requires separate uniqueness-preserving translations; it should not be assumed from the statement alone.

The claimed polynomial and the promise parameters $m,D$ exist, but the manuscript does not provide a small explicit universal equation or numerical values for every fixed constant. The result is therefore distinct from optimizing the degree, number of variables or coefficient sizes.

Single-fold representation gives no computable stopping rule for searching a negative instance. On positive instances, exhaustive enumeration eventually finds the unique witness; on negative instances it can continue forever.

A unique witness may also be extraordinarily large. Bounds on solution size would have additional algorithmic consequences, and no general computable bound is claimed here. The finite-fold conclusion follows immediately from uniqueness, but its broader quantitative refinements are separate questions.

8. Sources and further reading

Davis, Putnam and Robinson, The decision problem for exponential Diophantine equations, Annals of Mathematics 74 (1961), 425–436, is the exponential representation theorem. Matiyasevich, The Diophantineness of enumerable sets (1970), completes the polynomial representation route.

Matiyasevich, The existence of non-effectivizable estimates in the theory of exponential Diophantine equations, Zapiski Nauchnykh Seminarov LOMI 40 (1974), 77–93, gives the single-fold exponential theorem. His Towards finite-fold Diophantine representations, Zapiski Nauchnykh Seminarov POMI 377 (2010), 78–90, discusses the finite-fold program.

Jones and Matiyasevich, Register machine proof of the theorem on exponential Diophantine representation of enumerable sets, Journal of Symbolic Logic 49 (1984), 818–829, supplies the computational predecessor. Poonen, Using elliptic curves of rank one towards the undecidability of Hilbert’s tenth problem over rings of algebraic integers, Lecture Notes in Computer Science 2369 (2002), 33–42, provides the elliptic-curve context. Cantone, Cuzziol and Omodeo, On Diophantine singlefold specifications, Le Matematiche 79 (2024), 585–620, discusses the Pell and uniqueness machinery.

Source manuscripts

• M1. OpenAI, Single-fold Diophantine representations (September 24, 2026).

Sources consulted on 21 October 2026 at repository revision 1581d4c. Download the manuscript citations.