∑math20

Mathematical logic · Result 242

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

1 paperLean

Every recursively enumerable set of tuples of natural numbers has a Diophantine representation with exactly one auxiliary solution for each member and none for nonmembers. This proves the single-fold conjecture and hence the finite-fold conjecture. Diophantine solvability over the nonnegative integers remains undecidable even with an at-most-one-solution promise.

Watch

▶Introduction: the problem and why it mattersin preparation
▶The presented solutionin preparation

Papers 1

First page of Single-fold Diophantine representations

Single-fold Diophantine representations

OpenAI · September 24, 2026

Every recursively enumerable set of natural-number tuples has a polynomial Diophantine representation with exactly one complete auxiliary tuple for each member. This proves the single-fold conjecture and, consequently, the finite-fold conjecture.

Read PDF Download Source

Cite
@misc{OAI:Single-fold-Diophantine-representations-September-24-2026,
  author = {{OpenAI}},
  title = {{Single-fold Diophantine representations}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Single-fold-Diophantine-representations-September-24-2026/paper.pdf}{OAI:Single-fold-Diophantine-representations-September-24-2026}},
  year = {2026}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

The single-fold Diophantine conjecture asks whether every recursively enumerable set has a polynomial representation with a unique auxiliary witness for each member. 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.

The consequence that solvability remains undecidable under an at-most-one-solution promise is not separately formalized.

Comparator links

ResultComparator statement
Single-fold Diophantine representationsSingleFold.lean

Scope note on GitHub →