OctoInformBeta

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

Lemma 2.2: So are intersections over a finite index set, projections forgetting finitely many variables the rest determines, and pullbacks along single-fold maps, which compose

Intersections and disjoint unions of single-fold relations are single-fold.

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

Diophantine representations of complicated relations are assembled from representations of simpler ones: two relations are intersected or joined, a variable is eliminated by an existential quantifier, a function is substituted into a relation. For a single-fold representation each of these steps has to keep the auxiliary tuple unique, and two of them can break it. A tuple lying in both relations of a union gets an auxiliary tuple from each side; eliminating a variable yy from a relation RR makes every yy with (a,y)∈R(a, y) \in R part of a separate auxiliary tuple for the tuple aa. The question is which steps keep single-fold representations single-fold, and under which hypotheses.

Single-fold Representations

Here ℕ={0,1,2,…}\mathbb{N} = \{0, 1, 2, \dots\}. For a set AA, a tuple indexed by AA is an element a=(ai)i∈Aa = (a_i)_{i \in A} of ℕA\mathbb{N}^A, and a relation on ℕA\mathbb{N}^A is a subset of ℕA\mathbb{N}^A; for A={1,…,d}A = \{1, \dots, d\} these are the tuples in ℕd\mathbb{N}^d and the relations on them. A tuple indexed by a disjoint union A⊔BA \sqcup B is written (a,y)(a, y), with a∈ℕAa \in \mathbb{N}^A and y∈ℕBy \in \mathbb{N}^B.

A single-fold representation of a relation R⊆ℕAR \subseteq \mathbb{N}^A is a polynomial PP with integer coefficients in the variables aa and finitely many auxiliary variables w=(wj)j∈Jw = (w_j)_{j \in J} such that for every a∈ℕAa \in \mathbb{N}^A a∈R⇔∃w∈ℕJP(a,w)=0,P(a,w)=P(a,w′)=0⟹w=w′(w,w′∈ℕJ).a \in R \iff \exists w \in \mathbb{N}^J \; P(a, w) = 0, \qquad P(a, w) = P(a, w') = 0 \implies w = w' \quad (w, w' \in \mathbb{N}^J).(1)✦ We write Rep⁡(R)\operatorname{Rep}(R) for the set of single-fold representations of RR. A relation R⊆ℕAR \subseteq \mathbb{N}^A is single-fold, written R∈SFR \in \mathrm{SF}, when Rep⁡(R)\operatorname{Rep}(R) is nonempty.✦

A map f:ℕA→ℕBf \colon \mathbb{N}^A \to \mathbb{N}^B is single-fold when its graph Γf={(a,y)∈ℕA⊔B:y=f(a)}\Gamma_f = \{ (a, y) \in \mathbb{N}^{A \sqcup B} : y = f(a) \}(2)✦ is in SF\mathrm{SF}.

The projection ∃BR\exists_B R of a relation R⊆ℕA⊔BR \subseteq \mathbb{N}^{A \sqcup B} and the pullback f−1(S)f^{-1}(S) of a relation S⊆ℕBS \subseteq \mathbb{N}^B along a map f:ℕA→ℕBf \colon \mathbb{N}^A \to \mathbb{N}^B are the relations on ℕA\mathbb{N}^A ∃BR={a:(a,y)∈R for some y∈ℕB},f−1(S)={a:f(a)∈S}.\exists_B R = \{ a : (a, y) \in R \text{ for some } y \in \mathbb{N}^B \}, \qquad f^{-1}(S) = \{ a : f(a) \in S \}.(3)

The Claim

Theorem 1. Let AA and CC be sets and BB and II finite sets.

  1. Let R,S⊆ℕAR, S \subseteq \mathbb{N}^A be relations. There is a map Rep⁡(R)×Rep⁡(S)→Rep⁡(R∩S),\operatorname{Rep}(R) \times \operatorname{Rep}(S) \to \operatorname{Rep}(R \cap S),(4)✦ and if RR and SS are single-fold, then R∩S∈SF.R \cap S \in \mathrm{SF}.(5)✦

  2. Let Ri⊆ℕAR_i \subseteq \mathbb{N}^A, for i∈Ii \in I, be single-fold relations. Then ⋂i∈IRi∈SF.\textstyle\bigcap_{i \in I} R_i \in \mathrm{SF}.(6)✦

  3. Let R,S⊆ℕAR, S \subseteq \mathbb{N}^A be disjoint relations. There is a map Rep⁡(R)×Rep⁡(S)→Rep⁡(R∪S),\operatorname{Rep}(R) \times \operatorname{Rep}(S) \to \operatorname{Rep}(R \cup S),(7)✦ and if RR and SS are single-fold, then R∪S∈SF.R \cup S \in \mathrm{SF}.(8)✦

  4. Let R⊆ℕA⊔BR \subseteq \mathbb{N}^{A \sqcup B} be a relation such that for every a∈ℕAa \in \mathbb{N}^A there is at most one y∈ℕBy \in \mathbb{N}^B with (a,y)∈R(a, y) \in R. There is a map Rep⁡(R)→Rep⁡(∃BR),\operatorname{Rep}(R) \to \operatorname{Rep}(\exists_B R),(9)✦ and if RR is single-fold, then ∃BR∈SF.\exists_B R \in \mathrm{SF}.(10)✦

  5. Let f:ℕA→ℕBf \colon \mathbb{N}^A \to \mathbb{N}^B and g:ℕB→ℕCg \colon \mathbb{N}^B \to \mathbb{N}^C be single-fold maps. Then Γg∘f∈SF,\Gamma_{g \circ f} \in \mathrm{SF},(11)✦ and for every single-fold relation S⊆ℕBS \subseteq \mathbb{N}^B f−1(S)∈SF.f^{-1}(S) \in \mathrm{SF}.(12)✦

In the paper, the result reads: finite conjunctions of single-fold systems, with separate auxiliary tuples for distinct calls, preserve uniqueness for fixed values of all displayed arguments; composition of single-fold graphs preserves uniqueness of outputs and of complete auxiliary tuples; and a finite union of single-fold relations has a single-fold system when their displayed argument sets are pairwise disjoint.

What Is Checked

The claim is stated over single-fold representations (1) by integer polynomials with finitely many auxiliary variables, over the class SF\mathrm{SF} of relations that have one, and over single-fold maps, those whose graph (2) lies in SF\mathrm{SF}.