OctoInformBeta

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

§2.1 (setting): the initial Hamming-ball family: For nonnegative integers M,dM,d, block indicators supply centers for predicates on M(d+2)M(d+2) Boolean coordinates

Hamming balls form a nested initial family.

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 initial stage of the Boolean function construction uses inputs close to block indicator strings. The distance allowed from a center is the parameter of each predicate.

Let II be a finite coordinate set. A Boolean input xx on II is a function from II to {false,true}\{\mathrm{false},\mathrm{true}\}. The Hamming distance dH(x,y)d_H(x,y) between two inputs is the number of coordinates where they differ, as in (1). dH(x,y)=|{i∈I:x(i)≠y(i)}|.d_H(x,y)=\bigl|\{i\in I:x(i)\ne y(i)\}\bigr|.(1)

For a finite family of centers (zc)c∈C(z_c)_{c\in C} on a finite coordinate set II and an integer R≥0R\ge0, the union BRB_R of Hamming balls of radius RR is the Boolean predicate on II defined by (2). BR(x)={true,if some c∈C satisfies dH(x,zc)≤R,false,otherwise.B_R(x)= \begin{cases} \mathrm{true},&\text{if some }c\in C\text{ satisfies }d_H(x,z_c)\le R,\\ \mathrm{false},&\text{otherwise}. \end{cases}(2) For a nonempty finite family of centers (zc)c∈C(z_c)_{c\in C} on a finite coordinate set II and a Boolean input xx on II, the nearest distance δ(x)\delta(x) from xx to the family is the minimum in (3). δ(x)=minc∈CdH(x,zc).\delta(x)=\min_{c\in C}d_H(x,z_c).(3)✦

For a nonnegative integer hh, a family (Fq)q=1h(F_q)_{q=1}^h of Boolean predicates on a finite coordinate set II is nested if it satisfies (4) at every Boolean input xx on II. 1≤q≤q′≤h,Fq′(x)=true⇒Fq(x)=true.1\le q\le q'\le h,\quad F_{q'}(x)=\mathrm{true} \quad\Longrightarrow\quad F_q(x)=\mathrm{true}.(4)✦ This condition concerns the predicate index rather than the order on input bits.

The Block Construction

Let M,LM,L be nonnegative integers. Use the coordinate set I={1,…,M}×{1,…,L}I=\{1,\ldots,M\}\times\{1,\ldots,L\}. For 1≤j≤M1\le j\le M, the coordinate block BjB_j of II is the subset of coordinates with first coordinate jj, and its block indicator center cjc_j is the Boolean input on II defined in (5). Bj={(j,a):1≤a≤L},cj(j′,a)={true,j′=j,false,j′≠j.B_j=\{(j,a):1\le a\le L\},\qquad c_j(j',a)= \begin{cases} \mathrm{true},&j'=j,\\ \mathrm{false},&j'\ne j. \end{cases}(5) For a nonnegative integer dd, take L=d+2L=d+2. The initial Hamming family (P0,q)q=1d+1(P_{0,q})_{q=1}^{d+1} on II is the family of Boolean predicates in (6), where BRB_R uses the centers (cj)j=1M(c_j)_{j=1}^M. P0,q(x)=Bd+1−q(x),1≤q≤d+1.P_{0,q}(x)=B_{d+1-q}(x),\qquad 1\le q\le d+1.(6)✦

The Claim

Theorem 1. Let M,L≥0M,L\ge0, and take the blocks and centers of (5). For each 1≤j≤M1\le j\le M, the block cardinality is (7). |Bj|=L.|B_j|=L.(7)✦ For distinct i,j∈{1,…,M}i,j\in\{1,\ldots,M\}, the centers satisfy (8). dH(ci,cj)=2L.d_H(c_i,c_j)=2L.(8)✦ For any finite nonempty family of centers on a finite coordinate set and any integer R≥0R\ge0, the predicate in (2) satisfies (9) at every input xx. BR(x)=true⇔δ(x)≤R.B_R(x)=\mathrm{true}\quad\Longleftrightarrow\quad\delta(x)\le R.(9)✦ For d≥0d\ge0, take L=d+2L=d+2 and the initial family in (6). For 1≤q≤q′≤d+11\le q\le q'\le d+1, every input xx accepted by P0,q′P_{0,q'} satisfies (10). P0,q(x)=true.P_{0,q}(x)=\mathrm{true}.(10)✦

In the paper, the result reads: with L=d+2L=d+2, k=2M2+1k=2M^2+1 and r=⌈M⌉r=\lceil\sqrt M\rceil, set Hℓ=d+1−ℓH_\ell=d+1-\ell and Nℓ=LM(kr)ℓN_\ell=LM(kr)^\ell for 0≤ℓ≤d0\le\ell\le d, partition the LMLM coordinates at level zero into MM disjoint blocks EjE_j of size LL, let zjz_j indicate EjE_j, set D(x)=min⁡jdH(x,zj)D(x)=\min_j d_H(x,z_j) and let P0,q(x)P_{0,q}(x) be true exactly when D(x)≤d+1−qD(x)\le d+1-q for 1≤q≤d+11\le q\le d+1; distinct centers have distance 2L2L and the predicates are nested in qq, with radii d,d−1,…,0d,d-1,\ldots,0.

What Is Checked

The statements concern finite Boolean cubes and the block construction on {1,…,M}×{1,…,d+2}\{1,\ldots,M\}\times\{1,\ldots,d+2\}, with a nonempty finite center family for the nearest distance in (3).