OctoInformBeta

OpenAI preprint, September 2026 · §2. The labelled tournament and nested predicates

§2.2 (setting): recursive clauses and nested predicates: Disjoint child inputs support tournament rows and an iterated construction with an explicit coordinate count

Recursive clauses preserve nested predicate families.

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

The construction assembles Boolean predicates from disjoint blocks of input coordinates. A tournament selects the child inputs used by each row, while a predicate index orders the acceptance sets. Write [m]={1,…,m}[m]=\{1,\ldots,m\} and 𝔹={𝖿𝖺𝗅𝗌𝖾,𝗍𝗋𝗎𝖾}\mathbb B=\{\mathsf{false},\mathsf{true}\}. The construction parameters are natural numbers d,Md,M with L=d+2L=d+2, k=2M2+1k=2M^2+1, r=⌈M⌉r=\lceil\sqrt M\rceil, and t=16t=16; the recursive definitions also allow arbitrary natural numbers k,rk,r.

A tournament TT on [k][k] is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices; write i→ji\to j for an edge.✦ A regular tournament TT with parameter MM is a tournament on [k][k] with k=2M2+1k=2M^2+1 vertices and outdegree M2M^2 at every vertex.✦ An rr-labeling λ\lambda on [k][k] is a map λ:[k]×[k]→[r]\lambda:[k]\times[k]\to[r]. A good rr-labeling λ\lambda on [k][k] is a map λ:[k]×[k]→[r]\lambda:[k]\times[k]\to[r] such that, for every set U⊆[k]U\subseteq[k] of size t=16t=16 and every map m:[k]→[r]m:[k]\to[r], there are i,j∈Ui,j\in U with i→ji\to j and λ(i,j)≠m(j)\lambda(i,j)\ne m(j).✦

For a finite coordinate set II, a family F=(F1,…,Fh)F=(F_1,\ldots,F_h) of predicates on 𝔹I\mathbb B^I is nested when its acceptance sets satisfy (1). The ordering is on the predicate indices. {x:Fq′(x)=𝗍𝗋𝗎𝖾}⊆{x:Fq(x)=𝗍𝗋𝗎𝖾}(1≤q≤q′≤h).\{x:F_{q'}(x)=\mathsf{true}\}\subseteq \{x:F_q(x)=\mathsf{true}\} \qquad (1\le q\le q'\le h).(1)✦

The Initial Predicates

The block indicator cjc_j on [M]×[L][M]\times[L], for j∈[M]j\in[M], is the Boolean input specified by (2). cj(a,b)={𝗍𝗋𝗎𝖾,a=j,𝖿𝖺𝗅𝗌𝖾,a≠j.c_j(a,b)= \begin{cases} \mathsf{true},&a=j,\\ \mathsf{false},&a\ne j. \end{cases}(2)✦

For a finite family of centers 𝒞=(zc)c∈C\mathcal C=(z_c)_{c\in C} in 𝔹I\mathbb B^I and a nonnegative integer RR, the union of Hamming balls U𝒞,R:𝔹I→𝔹U_{\mathcal C,R}:\mathbb B^I\to\mathbb B is the predicate defined by (3), where dHd_H denotes Hamming distance. U𝒞,R(x)=𝗍𝗋𝗎𝖾⇔there is c∈C with dH(x,zc)≤R.U_{\mathcal C,R}(x)=\mathsf{true} \quad\Longleftrightarrow\quad \text{there is }c\in C\text{ with }d_H(x,z_c)\le R.(3)✦

The initial family Fd,MF^{d,M} on 𝔹[M]×[L]\mathbb B^{[M]\times[L]} has d+1d+1 predicates, with the radii specified by (4). Fqd,M=U(cj)j∈[M],d+1−q(q∈[d+1]).F^{d,M}_q=U_{(c_j)_{j\in[M]},\,d+1-q} \qquad(q\in[d+1]).(4)✦

The Claim

Definition 1. Let TT be a tournament on [k][k], let λ\lambda be an rr-labeling, and let II be a finite coordinate set. For an input x∈𝔹([k]×[r])×Ix\in\mathbb B^{([k]\times[r])\times I}, its child restriction xj,c∈𝔹Ix_{j,c}\in\mathbb B^I is defined by (5). xj,c(a)=x((j,c),a)(j∈[k],c∈[r],a∈I).x_{j,c}(a)=x((j,c),a) \qquad(j\in[k],\ c\in[r],\ a\in I).(5)✦

For q∈[h]q\in[h], the reversed gate index gh(q)∈[h+1]g_h(q)\in[h+1] is given by (6). gh(q)=h+1−q.g_h(q)=h+1-q.(6)✦

Given a family F=(F1,…,Fh+1)F=(F_1,\ldots,F_{h+1}) on 𝔹I\mathbb B^I, the row clause Rq,iFR^F_{q,i} is the Boolean predicate on 𝔹([k]×[r])×I\mathbb B^{([k]\times[r])\times I} defined by (7). Rq,iF(x)=𝗍𝗋𝗎𝖾⇔(⋀c∈[r]Fh+1(xi,c)=𝗍𝗋𝗎𝖾)∧(⋀j:i→jFgh(q)(xj,λ(i,j))=𝖿𝖺𝗅𝗌𝖾).R^F_{q,i}(x)=\mathsf{true} \quad\Longleftrightarrow\quad \left(\bigwedge_{c\in[r]}F_{h+1}(x_{i,c})=\mathsf{true}\right) \land \left(\bigwedge_{j:\,i\to j} F_{g_h(q)}(x_{j,\lambda(i,j)})=\mathsf{false}\right).(7)✦

The recursive family ℛT,λ(F)\mathcal R_{T,\lambda}(F) is the family of hh predicates on 𝔹([k]×[r])×I\mathbb B^{([k]\times[r])\times I} specified by (8). ℛT,λ(F)q(x)=𝗍𝗋𝗎𝖾⇔there is i∈[k] with Rq,iF(x)=𝗍𝗋𝗎𝖾.\mathcal R_{T,\lambda}(F)_q(x)=\mathsf{true} \quad\Longleftrightarrow\quad \text{there is }i\in[k]\text{ with }R^F_{q,i}(x)=\mathsf{true}.(8)✦

For a family G=(G1,…,GD)G=(G_1,\ldots,G_D) on 𝔹I\mathbb B^I, its extended initial family EG(h)E_G^{(h)} has length hh and is defined by (9). (EG(h))q(x)={Gq(x),h=D,𝖿𝖺𝗅𝗌𝖾,h≠D(q∈[h]).(E_G^{(h)})_q(x)= \begin{cases} G_q(x),&h=D,\\ \mathsf{false},&h\ne D \end{cases} \qquad(q\in[h]).(9)✦

The construction base family ℬd,M(h)\mathcal B_{d,M}^{(h)} is the family of hh Boolean predicates on 𝔹[M]×[L]\mathbb B^{[M]\times[L]} specified by (10). ℬd,M(h)=EFd,M(h).\mathcal B_{d,M}^{(h)}=E_{F^{d,M}}^{(h)}.(10)✦

The tower coordinate sets In(k,r;I)I_n(k,r;I) are the finite sets defined recursively in (11). I0(k,r;I)=I,In+1(k,r;I)=([k]×[r])×In(k,r;I).\begin{aligned} I_0(k,r;I)&=I,\\ I_{n+1}(k,r;I)&=([k]\times[r])\times I_n(k,r;I). \end{aligned}(11)✦

For base families ℬ(h)\mathcal B^{(h)} on 𝔹I\mathbb B^I of every length hh, the tower family 𝒯n,hℬ\mathcal T^{\mathcal B}_{n,h} consists of hh predicates on 𝔹In(k,r;I)\mathbb B^{I_n(k,r;I)} and is defined by (12). 𝒯0,hℬ=ℬ(h),𝒯n+1,hℬ=ℛT,λ(𝒯n,h+1ℬ).\begin{aligned} \mathcal T^{\mathcal B}_{0,h}&=\mathcal B^{(h)},\\ \mathcal T^{\mathcal B}_{n+1,h} &=\mathcal R_{T,\lambda}(\mathcal T^{\mathcal B}_{n,h+1}). \end{aligned}(12)✦

The construction coordinate set KnK_n is the finite set specified by (13). Kn=In(2M2+1,r;[M]×[L]).K_n=I_n(2M^2+1,r;[M]\times[L]).(13)✦

For a regular tournament TT with parameter MM and a good rr-labeling λ\lambda, the terminal predicate fd:𝔹Kd→𝔹f_d:\mathbb B^{K_d}\to\mathbb B is defined by (14). fd(x)=(𝒯d,1ℬd,M)1(x).f_d(x)=(\mathcal T^{\mathcal B_{d,M}}_{d,1})_1(x).(14)✦

In the paper, the result reads: writing Pℓ,qP_{\ell,q} for the predicate of index qq at level ℓ\ell, for 1≤ℓ≤d1\le\ell\le d, partition the parent input into krkr disjoint children xj,cx_{j,c} of dimension Nℓ−1N_{\ell-1}, the preceding input dimension, put H=HℓH=H_\ell for the predicate count and Q=H+1Q=H+1, and let clause ii at index q∈[H]q\in[H] require Pℓ−1,Q(xi,c)=𝗍𝗋𝗎𝖾P_{\ell-1,Q}(x_{i,c})=\mathsf{true} for every cc and Pℓ−1,Q−q(xj,λ(i,j))=𝖿𝖺𝗅𝗌𝖾P_{\ell-1,Q-q}(x_{j,\lambda(i,j)})=\mathsf{false} for every edge i→ji\to j, with Pℓ,qP_{\ell,q} the disjunction of the row clauses, distinct children for the targets and gates of each clause, and a resulting family nested in qq.

What Is Checked

The recursive clauses are stated over finite coordinate sets, an arbitrary tournament and labeling, and Boolean predicate families; the terminal specialization uses a regular tournament and a good labeling.

Theorem 1. Let TT be a tournament on [k][k], let λ\lambda be an rr-labeling, and let II be finite. For a nested child family FF of length h+1h+1, the recursive acceptance sets satisfy (15). {x:ℛT,λ(F)q′(x)=𝗍𝗋𝗎𝖾}⊆{x:ℛT,λ(F)q(x)=𝗍𝗋𝗎𝖾}(1≤q≤q′≤h).\{x:\mathcal R_{T,\lambda}(F)_{q'}(x)=\mathsf{true}\} \subseteq \{x:\mathcal R_{T,\lambda}(F)_q(x)=\mathsf{true}\} \qquad(1\le q\le q'\le h).(15)✦

For arbitrary base families ℬ(h)\mathcal B^{(h)}, if ℬ(h+n)\mathcal B^{(h+n)} is nested, the tower acceptance sets satisfy (16). {x:(𝒯n,hℬ)q′(x)=𝗍𝗋𝗎𝖾}⊆{x:(𝒯n,hℬ)q(x)=𝗍𝗋𝗎𝖾}(1≤q≤q′≤h).\{x:(\mathcal T^{\mathcal B}_{n,h})_{q'}(x)=\mathsf{true}\} \subseteq \{x:(\mathcal T^{\mathcal B}_{n,h})_q(x)=\mathsf{true}\} \qquad(1\le q\le q'\le h).(16)✦

The tower coordinate count is given by (17). |In(k,r;I)|=(kr)n|I|.|I_n(k,r;I)|=(kr)^n|I|.(17)✦