OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: An integer polynomial PP with P(a,w)=0P(a, w) = 0 solvable in ww exactly for a∈Sa \in S, and then by one ww only

Every recursively enumerable set has a single-fold Diophantine representation.

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

By the theorem of Davis, Putnam, Robinson and Matiyasevich, for every integer n≥1n \ge 1 every recursively enumerable set S⊆ℕnS \subseteq \mathbb{N}^n is Diophantine: there are an integer m≥1m \ge 1 and a polynomial PP with integer coefficients in variables A1,…,An,W1,…,WmA_1, \dots, A_n, W_1, \dots, W_m such that, for a∈ℕna \in \mathbb{N}^n, a∈Sa \in S exactly when P(a,w)=0P(a, w) = 0 for some w∈ℕmw \in \mathbb{N}^m. One aa may come with many such ww.

The question is whether PP can always be chosen so that each a∈Sa \in S has only one ww.

Single-fold Representations

A single-fold representation of a relation R⊆ℕIR \subseteq \mathbb{N}^I, where II is a set of input variables, is a polynomial QQ with integer coefficients in the variables AiA_i (i∈Ii \in I) and in the auxiliary variables WvW_v of a finite set VV, such that for all a∈ℕIa \in \mathbb{N}^I and w,w′∈ℕVw, w' \in \mathbb{N}^V a∈R⇔Q(a,z)=0 for some z∈ℕV,Q(a,w)=Q(a,w′)=0⟹w=w′.a \in R \iff Q(a, z) = 0 \text{ for some } z \in \mathbb{N}^V, \qquad Q(a, w) = Q(a, w') = 0 \implies w = w'.(1)✦

A relation R⊆ℕIR \subseteq \mathbb{N}^I is single-fold, written R∈SFR \in \mathrm{SF}, when it has a single-fold representation.✦ A polynomial P∈ℤ[A1,…,An,W1,…,Wm]P \in \mathbb{Z}[A_1, \dots, A_n, W_1, \dots, W_m] represents a set S⊆ℕnS \subseteq \mathbb{N}^n single-fold when it is a single-fold representation of SS with the auxiliary variables W1,…,WmW_1, \dots, W_m.✦

The Claim

Theorem 1.

  1. Let n≥1n \ge 1 and let S⊆ℕnS \subseteq \mathbb{N}^n be recursively enumerable. Then for some m≥1m \ge 1 S is represented single-fold by some P∈ℤ[A1,…,An,W1,…,Wm].S \text{ is represented single-fold by some } P \in \mathbb{Z}[A_1, \dots, A_n, W_1, \dots, W_m].(2)✦

  2. Let n∈ℕn \in \mathbb{N} and let R⊆ℕnR \subseteq \mathbb{N}^n be recursively enumerable. Then R∈SF.R \in \mathrm{SF}.(3)✦

  3. Let II be a set and let R⊆ℕIR \subseteq \mathbb{N}^I be single-fold. Then for some m≥1m \ge 1 R has a single-fold representation P∈ℤ[Ai,Wj:i∈I,1≤j≤m].R \text{ has a single-fold representation } P \in \mathbb{Z}[A_i, W_j : i \in I,\ 1 \le j \le m].(4)✦

In the paper, the result reads: for every integer n≥1n \ge 1 and every recursively enumerable S⊆ℕnS \subseteq \mathbb{N}^n there are an integer m≥1m \ge 1 and P∈ℤ[A1,…,An,W1,…,Wm]P \in \mathbb{Z}[A_1, \dots, A_n, W_1, \dots, W_m] such that, for every a∈ℕna \in \mathbb{N}^n, #{w∈ℕm:P(a,w)=0}\#\{w \in \mathbb{N}^m : P(a, w) = 0\} is 11 if a∈Sa \in S and 00 if a∉Sa \notin S.

What Is Checked

The claim is stated over recursively enumerable relations on tuples of natural numbers, polynomials with integer coefficients evaluated at natural numbers, single-fold representations of a relation and the class SF\mathrm{SF} of relations that have one, and polynomials representing a set single-fold.