Single-fold Diophantine representations and undecidability under an at-most-one-solution promise

Every computably listable set gets a whole-number polynomial test with exactly one solution per member.

1 paper September 24, 2026 Explained by AI

A polynomial test for a set says: a number is in the set exactly when some whole numbers make the polynomial zero. Such tests exist for every set a computer can list, but they may have many solutions. The paper shows a test with exactly one solution for each member always exists. This settles Matiyasevich's single-fold conjecture. A Lean proof checks the main theorem.

First step

1974

Yuri Matiyasevich, single-fold exponential representations

Significance

Major

It settles a conjecture open for about fifty years about the strongest form of Hilbert's tenth problem.

Trust

Formal proof listed

Field

Mathematical logic

1 paper

The explanation

Start with a small test. A number a is composite when a = (w₁ + 2)(w₂ + 2) has a solution in whole numbers w₁ and w₂. Try a = 7. No pair works, so 7 is not composite. Try a = 12. Four pairs work: (0, 4), (1, 2), (2, 1) and (4, 0). For a = 36 there are seven. The test is correct, but the witnesses, the extra unknowns that make it work, are far from unique.

A Diophantine representation of a set is a polynomial with integer coefficients that works like this. A tuple of numbers is in the set exactly when some whole-number witnesses make the polynomial zero. A set is recursively enumerable when a computer program can accept exactly its members. It may run forever on other inputs. In 1970, building on Davis, Putnam and Robinson, Matiyasevich completed the proof that every such set has a representationSource 1. That answered Hilbert's tenth problem: no algorithm decides whether a polynomial equation has whole-number solutions. But the result does not bound how many witnesses there areSource 2.

A representation is single-fold when the witness tuple is unique whenever it exists. In 1974, Matiyasevich got this uniqueness for formulas that may also use exponentiation, like bⁿSource 3. Whether plain polynomials suffice became the single-fold conjectureSource 4. The obstacle is that every step of turning a computation into equations must keep uniqueness. That includes helper variables for quotients, remainders and cases that are switched offSource 5.

The paper claims every recursively enumerable set has a single-fold polynomial representationSource 6. The key new step builds powers bⁿ with a unique witness. For that, it uses rational points on the elliptic curve y² = x³ − 25x. One such point is (−4, 6), since 6² = 36 and (−4)³ + 100 = 36. The sizes of these points grow in a precise quadratic way. That gives a cutoff that picks out exactly one indexSource 7. Then it encodes a machine's whole run as digits of a few huge numbersSource 8. The paper also claims a consequence. Deciding solvability stays impossible even when each equation is promised at most one solutionSource 9. The polynomial's existence is shown, but its coefficients are not displayedSource 10.

How sure is this? A computer proof checker called Lean has a formal proof of the main theorem. It covers every recursively enumerable set of tuples, with exactly one witness tuple for members and none for others. The undecidability corollary is not separately formalized. No specialist review of the paper has been published.

What it doesn't show. This does not give the polynomial's actual coefficients, and the Lean check does not cover the undecidability corollary.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

The main theorem has a Lean proof and settles a known conjecture. The polynomial is shown to exist but is not written down. The undecidability corollary is outside the Lean check. No specialist review is published.

Words used

Diophantine representation: A polynomial with integer coefficients that is zero for some whole-number witnesses exactly when the input is in the set.
Witness: The extra unknowns whose values make the polynomial equal zero for a member.
Recursively enumerable: A set whose members a computer program accepts; the program may run forever on non-members.
Single-fold: Each member has exactly one witness tuple.
Hilbert's tenth problem: The 1900 question asking for an algorithm that decides whether a polynomial equation has whole-number solutions.
Elliptic curve: A curve given by an equation like y² = x³ + ax + b, whose rational points can be added to each other.

The original paper

Single-fold Diophantine representations (PDF, opens in a new tab)
September 24, 2026 Formal proof listed

Lean notes

All quoted lines (10)

Matiyasevich's 1970 construction of an exponentially growing Diophantine relation completed this route to polynomial representations.
Single-fold Diophantine representations Back to text
It does not bound the number of witnesses.
Single-fold Diophantine representations Back to text
Matiyasevich obtained a different strengthening in 1974: every recursively enumerable relation has an exponential representation with a unique complete auxiliary tuple.
Single-fold Diophantine representations Back to text
This is the single-fold conjecture; allowing finitely many witnesses gives the finite-fold conjecture.
Single-fold Diophantine representations Back to text
Throughout both constructions, uniqueness must include reduced rational coordinates, arithmetic quotients and slacks, and the variables of inactive cases.
Single-fold Diophantine representations Back to text
Every recursively enumerable set of natural-number tuples has a polynomial Diophantine representation with exactly one complete auxiliary tuple for each member.
Single-fold Diophantine representations Back to text
A discrete difference of the quadratic main term makes exact index selection possible.
Single-fold Diophantine representations Back to text
Finally, Section … packs a deterministic counter machine's states and counter values into digits of finitely many integers.
Single-fold Diophantine representations Back to text
There exist integers $m,D\ge1$ for which no algorithm has the following property: on every input polynomial $F\in\ZZ[W_1,\ldots,W_m]$ of total degree at most $D$ satisfying the promise $\#\{w\in\NN^m:F(w)=0\}\le1,$ the algorithm halts and correctly decides whether this set is nonempty.
Single-fold Diophantine representations Back to text
The theorem therefore gives existence of an integer polynomial without displaying its coefficients or a procedure for numerically choosing those constants.
Single-fold Diophantine representations Back to text

Other sources

openai/math, Lean scope note for family 242 The formalization establishes this for every recursively enumerable subset of $\mathbb N^n$ , $n\ge1$ : an integer polynomial has exactly one complete natural-number witness tuple for members and none for nonmembers.
openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

241Rigidity of the Turing degreesMathematical logic
243Separating choiceless counting from polynomial time and witnessed choiceMathematical logic
240Shelah's eventual categoricity and the prescribed-threshold obstructionMathematical logic
244The Partition Principle does not imply ChoiceMathematical logic
245Weak normalization implies strong normalization in pure type systemsMathematical logic

Browse Mathematical logic Open since the 1970s Lean-checked results