OctoInformBeta

OpenAI preprint, September 2026 · §2. Polynomial constructions with unique witnesses

Definition 2.1: Single-fold relations SF(R)\mathrm{SF}(R) and graphs of maps, and relations that are single-fold together with their complements

Diophantine representations with a unique auxiliary tuple.

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

Take a relation R⊆ℕdR \subseteq \mathbb{N}^d on tuples a=(ai)i∈da = (a_i)_{i \in d} of natural numbers. A Diophantine representation of RR is a polynomial P(a,w)P(a, w) with integer coefficients such that a∈Ra \in R exactly when P(a,w)=0P(a, w) = 0 for some auxiliary tuple ww of natural numbers; by the theorem of Davis, Putnam, Robinson and Matiyasevich, the relations that have one are exactly the recursively enumerable relations.

A representation can have many auxiliary tuples at one input: a−(w1+2)(w2+2)a - (w_1 + 2)(w_2 + 2) represents the composite numbers with one tuple for each ordered factorization a=uva = uv with u,v≥2u, v \geq 2. The question is which recursively enumerable relations have a representation whose auxiliary tuple, whenever it exists, is unique. The same question is asked of the graph of a map ff from ℕd\mathbb{N}^d to ℕe\mathbb{N}^e, for a set ee of output variables, that is, of the relation b=f(a)b = f(a) on pairs of an input tuple aa and an output tuple bb, and of a relation together with its complement.

The Definition

Definition 1. A single-fold representation of a relation R⊆ℕdR \subseteq \mathbb{N}^d is a polynomial P(a,w)P(a, w) with integer coefficients in the input variables a=(ai)i∈da = (a_i)_{i \in d} and finitely many auxiliary variables w=(w1,…,wk)w = (w_1, \dots, w_k) such that, for every a∈ℕda \in \mathbb{N}^d, a∈R⇔∃w∈ℕk:P(a,w)=0,∀w,w′∈ℕk:P(a,w)=P(a,w′)=0⟹w=w′.a \in R \iff \exists\, w \in \mathbb{N}^k \colon P(a, w) = 0, \qquad \forall\, w, w' \in \mathbb{N}^k \colon\ P(a, w) = P(a, w') = 0 \implies w = w'.(1)✦

A relation R⊆ℕdR \subseteq \mathbb{N}^d is single-fold, written SF(R)\mathrm{SF}(R), when it has a single-fold representation: $$\mathrm{SF}(R) \iff \exists\, k \in \mathbb{N}\ \exists\, P \in \mathbb{Z}[a, w_1, \dots, w_k] \text{ satisfying } \eqref{eq:claim1}.$$(2)✦

A total map f:ℕd→ℕef\colon \mathbb{N}^d \to \mathbb{N}^e, with ee a set of output variables, has a single-fold graph when its graph is a single-fold relation on ℕd×ℕe\mathbb{N}^d \times \mathbb{N}^e: SF({(a,b)∈ℕd×ℕe:b=f(a)}).\mathrm{SF}\bigl(\{(a, b) \in \mathbb{N}^d \times \mathbb{N}^e : b = f(a)\}\bigr).(3)✦

A function f:ℕd→ℕf\colon \mathbb{N}^d \to \mathbb{N} is a single-fold scalar function when the map sending aa to the one-entry tuple (f(a))(f(a)) has a single-fold graph, that is, when {(a,b)∈ℕd×ℕ:b=f(a)}\{(a, b) \in \mathbb{N}^d \times \mathbb{N} : b = f(a)\} is a single-fold relation: SF({(a,b)∈ℕd×ℕ:b=f(a)}).\mathrm{SF}\bigl(\{(a, b) \in \mathbb{N}^d \times \mathbb{N} : b = f(a)\}\bigr).(4)✦

A relation R⊆ℕdR \subseteq \mathbb{N}^d is two-sided single-fold when both RR and its complement are single-fold: SF(R)andSF(ℕd\R).\mathrm{SF}(R) \quad \text{and} \quad \mathrm{SF}(\mathbb{N}^d \setminus R).(5)✦

In the paper, the definition reads: a single-fold polynomial system for R⊆ℕdR \subseteq \mathbb{N}^d is a finite list of polynomial equations Fi(a,z)=0F_i(a, z) = 0 with integer coefficients whose set of complete tuples zz, those satisfying all the equations Fi(a,z)=0F_i(a, z) = 0, is a singleton for a∈Ra \in R and empty otherwise, and a single-fold graph of f:D→ℕef\colon D \to \mathbb{N}^e, for D⊆ℕdD \subseteq \mathbb{N}^d, is such a system for {(a,f(a)):a∈D}\{(a, f(a)) : a \in D\}, the paper’s zz being the page’s ww.

Here a system is one polynomial, and a map with a single-fold graph is defined on all of ℕd\mathbb{N}^d.

What Is Checked

The definitions are stated over relations R⊆ℕdR \subseteq \mathbb{N}^d and total maps f:ℕd→ℕef\colon \mathbb{N}^d \to \mathbb{N}^e, for any sets dd and ee of input and output variables, with representing polynomials over ℤ\mathbb{Z} in finitely many auxiliary variables ranging over ℕ\mathbb{N}.