# 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. Plain-English explainer, Lean status and sources.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-242/
Last updated: 2026-10-14

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

**Trust:** Formal proof listed · **Papers:** 1 · **First paper:** September 24, 2026 · **Field:** Mathematical logic · **Entry:** 242

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

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.

## At a glance

- **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 representation[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 are[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ⁿ[3]. Whether plain polynomials suffice became the single-fold conjecture[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 off[5].

The paper claims every recursively enumerable set has a single-fold polynomial representation[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 index[7]. Then it encodes a machine's whole run as digits of a few huge numbers[8]. The paper also claims a consequence. Deciding solvability stays impossible even when each equation is promised at most one solution[9]. The polynomial's existence is shown, but its coefficients are not displayed[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](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf) - September 24, 2026 · Formal proof listed

- [Lean notes](https://github.com/openai/math/blob/main/lean/docs/242.md)

## Quoted lines from the paper (10)

[1] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> Matiyasevich's 1970 construction of an exponentially growing Diophantine relation completed this route to polynomial representations.

[2] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> It does not bound the number of witnesses.

[3] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> Matiyasevich obtained a different strengthening in 1974: every recursively enumerable relation has an exponential representation with a unique complete auxiliary tuple.

[4] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> This is the single-fold conjecture; allowing finitely many witnesses gives the finite-fold conjecture.

[5] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> Throughout both constructions, uniqueness must include reduced rational coordinates, arithmetic quotients and slacks, and the variables of inactive cases.

[6] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> Every recursively enumerable set of natural-number tuples has a polynomial Diophantine representation with exactly one complete auxiliary tuple for each member.

[7] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> A discrete difference of the quadratic main term makes exact index selection possible.

[8] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> Finally, Section … packs a deterministic counter machine's states and counter values into digits of finitely many integers.

[9] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> 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.

[10] From [Single-fold Diophantine representations](https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf):

> The theorem therefore gives existence of an integer polynomial without displaying its coefficients or a procedure for numerically choosing those constants.

## Other sources

- [openai/math, Lean scope note for family 242](https://github.com/openai/math/blob/main/lean/docs/242.md): “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](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model”

## Related

- [Rigidity of the Turing degrees](https://closedform.nishachay.tech/e/openai-math-2026-241/) - Mathematical logic
- [Separating choiceless counting from polynomial time and witnessed choice](https://closedform.nishachay.tech/e/openai-math-2026-243/) - Mathematical logic
- [Shelah's eventual categoricity and the prescribed-threshold obstruction](https://closedform.nishachay.tech/e/openai-math-2026-240/) - Mathematical logic
- [The Partition Principle does not imply Choice](https://closedform.nishachay.tech/e/openai-math-2026-244/) - Mathematical logic
- [Weak normalization implies strong normalization in pure type systems](https://closedform.nishachay.tech/e/openai-math-2026-245/) - Mathematical logic
- [Mathematical logic](https://closedform.nishachay.tech/science/mathematics/mathematical-logic/) - Field · 6 results
- [Open since the 1970s](https://closedform.nishachay.tech/open-since/1970s/) - Era · 63 results
- [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20242%5D%20)