OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Recursively enumerable sets and single-fold representations: The statement that each recursively enumerable S⊆ℕnS \subseteq \mathbb{N}^n, n≥1n \ge 1, is represented by an integer polynomial with one auxiliary tuple per member

Single-fold Diophantine representations of recursively enumerable sets.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Hilbert’s tenth problem concerns equations P(a,w)=0P(a, w) = 0 with integer coefficients, in which a tuple aa of natural numbers is given and a tuple ww of natural numbers is sought, where ℕ={0,1,2,…}\mathbb{N} = \{0, 1, 2, \dots\} is the set of natural numbers. Such an equation picks out the inputs aa at which it is solvable, and by the Davis-Putnam-Robinson-Matiyasevich theorem every recursively enumerable set arises in this way. The solution over an input need not be unique: a=(w1+2)(w2+2)a = (w_1 + 2)(w_2 + 2) holds for some ww exactly when aa is composite, with one solution for each ordered factorization a=bca = bc with b,c≥2b, c \ge 2, while a=w2a = w^2 has a solution exactly when aa is a square, and then only one.

The question is whether every recursively enumerable set is picked out by an equation of the second kind, with exactly one solution ww over each of its members. Single-fold representability is the statement that every recursively enumerable set is picked out by an equation with exactly one solution ww over each of its members.

Single-fold Representations

For n∈ℕn \in \mathbb{N}, a set S⊆ℕnS \subseteq \mathbb{N}^n is recursively enumerable when some partial recursive function on ℕn\mathbb{N}^n is defined exactly at the members of SS.

For n,m∈ℕn, m \in \mathbb{N}, write ℤ[A1,…,An,W1,…,Wm]\mathbb{Z}[A_1, \dots, A_n, W_1, \dots, W_m] for the ring of polynomials with integer coefficients in the input variables A1,…,AnA_1, \dots, A_n and the auxiliary variables W1,…,WmW_1, \dots, W_m. The value P(a,w)P(a, w) of a polynomial PP in this ring at an input tuple a∈ℕna \in \mathbb{N}^n and an auxiliary tuple w∈ℕmw \in \mathbb{N}^m is the integer obtained by substituting aia_i for AiA_i and wjw_j for WjW_j: P(a,w)=P(a1,…,an,w1,…,wm)∈ℤ.P(a, w) = P(a_1, \dots, a_n, w_1, \dots, w_m) \in \mathbb{Z}.(1)✦

A single-fold Diophantine representation of a set S⊆ℕnS \subseteq \mathbb{N}^n is a polynomial P∈ℤ[A1,…,An,W1,…,Wm]P \in \mathbb{Z}[A_1, \dots, A_n, W_1, \dots, W_m] whose zeros lie over exactly the members of SS, one auxiliary tuple over each: for all a∈ℕna \in \mathbb{N}^n and w,v∈ℕmw, v \in \mathbb{N}^m, a∈S⇔P(a,z)=0 for some z∈ℕm,P(a,w)=P(a,v)=0⟹w=v.a \in S \iff P(a, z) = 0 \text{ for some } z \in \mathbb{N}^m, \qquad P(a, w) = P(a, v) = 0 \implies w = v.(2)✦

The Definition

Definition 1 (Single-fold representability). Single-fold representability is the statement that every recursively enumerable set S⊆ℕnS \subseteq \mathbb{N}^n with n≥1n \ge 1 has a single-fold Diophantine representation in at least one auxiliary variable: for every such nn and SS, $$\exists\, m \ge 1 \;\; \exists\, P \in \mathbb{Z}[A_1, \dots, A_n, W_1, \dots, W_m] \;\text{ satisfying } \eqref{eq:claim2}.$$(3)✦

In the paper, the notions read: over ℕ={0,1,2,…}\mathbb{N} = \{0, 1, 2, \dots\}, a set S⊆ℕnS \subseteq \mathbb{N}^n is recursively enumerable if a deterministic computation accepts exactly its members, a Diophantine representation of SS is a polynomial P∈ℤ[A1,…,An,W1,…,Wm]P \in \mathbb{Z}[A_1, \dots, A_n, W_1, \dots, W_m] with a∈Sa \in S if and only if P(a,w)=0P(a, w) = 0 for some w∈ℕmw \in \mathbb{N}^m, and the representation is single-fold if that complete tuple ww is unique whenever it exists.

What Is Checked

Single-fold representability (3) is stated over recursively enumerable subsets of ℕn\mathbb{N}^n, integer polynomials in input and auxiliary variables with their values (1) at tuples of natural numbers, and single-fold Diophantine representation (2).