OctoInformBeta

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

Lemma 2.3 [Common disjoint blocks at zero]: Block sizes and counts at each depth depend on the base blocks and the row and label counts

Predicate towers preserve common accepting blocks.

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 blocks relevant to block sensitivity at the all-false input are sets of coordinates whose simultaneous flip changes the function’s value. For a family of Boolean predicates, the question is whether the same collection of blocks works for every predicate.

Write [m]={1,…,m}[m]=\{1,\ldots,m\}, with [0]=⌀[0]=\varnothing, and let 𝟎\mathbf 0 denote the all-false input on the coordinate set in question. For a Boolean input xx on II and a finite coordinate block D⊆ID\subseteq I, the block flip xDx^D is the input specified by (1). xD(i)={¬x(i),i∈D,x(i),i∉D.x^D(i)= \begin{cases} \neg x(i),&i\in D,\\ x(i),&i\notin D. \end{cases}(1)✦

For nonnegative integers M,aM,a and j∈[M]j\in[M], the base block Bj(a)B_j(a) is the subset of [M]×[a][M]\times[a] consisting of the coordinates with first component jj.✦ The block indicator center cj(a)c_j(a) of Bj(a)B_j(a) is the Boolean input on [M]×[a][M]\times[a] defined in (2). Bj(a)={j}×[a],cj(a)(u,v)={true,u=j,false,u≠j.B_j(a)=\{j\}\times[a],\qquad c_j(a)(u,v)= \begin{cases} \mathrm{true},&u=j,\\ \mathrm{false},&u\ne j. \end{cases}(2)

For a finite family 𝒞=(cu)u∈A\mathcal C=(c_u)_{u\in A} of Boolean centers on a finite coordinate set and a nonnegative integer RR, the union of Hamming balls P𝒞,RP_{\mathcal C,R} is the predicate in (3), where dHd_H counts the coordinates at which two inputs differ. P𝒞,R(x)=true⇔there is u∈A with dH(x,cu)≤R.P_{\mathcal C,R}(x)=\mathrm{true} \quad\Longleftrightarrow\quad \text{there is }u\in A\text{ with }d_H(x,c_u)\le R.(3)✦

Let d,Md,M be nonnegative integers and put L=d+2L=d+2. The initial Hamming family (fq)q∈[d+1](f_q)_{q\in[d+1]} is the family of predicates on [M]×[L][M]\times[L] defined by (4); the predicate index starts at one. fq=P(cj(L))j∈[M],d+1−q,q∈[d+1].f_q=P_{(c_j(L))_{j\in[M]},\,d+1-q},\qquad q\in[d+1].(4)✦

For nonnegative integers k,rk,r, a tournament TT on [k][k] is a directed graph with no loops and exactly one orientation of each pair of distinct vertices.✦ An edge labelling λ:[k]×[k]→[r]\lambda:[k]\times[k]\to[r] assigns one of rr labels to each ordered pair.

For a coordinate set II, a finite block index set KK and each nonnegative depth ℓ\ell, the tower coordinate sets CℓC_\ell and tower block index sets KℓK_\ell are the Cartesian products in (5). C0=I,Cℓ+1=([k]×[r])×Cℓ,K0=K,Kℓ+1=[k]×Kℓ.\begin{aligned} C_0&=I,& C_{\ell+1}&=([k]\times[r])\times C_\ell,\\ K_0&=K,& K_{\ell+1}&=[k]\times K_\ell. \end{aligned}(5)

Given finite base blocks Db⊆ID_b\subseteq I indexed by b∈Kb\in K, the tower block Dℓ,b⊆CℓD_{\ell,b}\subseteq C_\ell is the finite set defined recursively in (6). The row lift in row u∈[k]u\in[k] of a tower block Dℓ,b⊆CℓD_{\ell,b}\subseteq C_\ell is the successor block Dℓ+1,(u,b)D_{\ell+1,(u,b)} defined by (6). D0,b=Db,Dℓ+1,(u,b)=({u}×[r])×Dℓ,b.D_{0,b}=D_b,\qquad D_{\ell+1,(u,b)}=(\{u\}\times[r])\times D_{\ell,b}.(6)✦

Let Gh,qG_{h,q}, for each nonnegative integer hh and q∈[h]q\in[h], be Boolean base predicates on II. The tower family (Fℓ,h,q)q∈[h](F_{\ell,h,q})_{q\in[h]} consists of predicates on CℓC_\ell defined by (7), where ℛT,λ\mathcal R_{T,\lambda} denotes the recursive predicate construction associated with the labelled tournament. F0,h,q=Gh,q,(Fℓ+1,h,q)q∈[h]=ℛT,λ((Fℓ,h+1,q)q∈[h+1]).F_{0,h,q}=G_{h,q},\qquad (F_{\ell+1,h,q})_{q\in[h]} =\mathcal R_{T,\lambda}\bigl((F_{\ell,h+1,q})_{q\in[h+1]}\bigr).(7)✦

The Claim

Theorem 1. For nonnegative integers d,Md,M, the initial family satisfies (8) and (9), for every q∈[d+1]q\in[d+1] and j∈[M]j\in[M]. fq(𝟎)=false.f_q(\mathbf 0)=\mathrm{false}.(8)✦ fq(𝟎Bj(L))=true.f_q\bigl(\mathbf 0^{B_j(L)}\bigr)=\mathrm{true}.(9)✦ For arbitrary base block length a>0a>0, (10) holds for each j∈[M]j\in[M]; (11) holds for every nonnegative length aa. Bj(a)≠⌀.B_j(a)\ne\varnothing.(10)✦ Bi(a)∩Bj(a)=⌀(i,j∈[M],i≠j).B_i(a)\cap B_j(a)=\varnothing\qquad(i,j\in[M],\ i\ne j).(11)✦

Let k,rk,r be nonnegative integers, let KK be finite, and let (Db)b∈K(D_b)_{b\in K} be finite blocks on an arbitrary coordinate set II. At every nonnegative depth ℓ\ell, the index count is (12). |Kℓ|=kℓ|K|.|K_\ell|=k^\ell|K|.(12)✦ If every base block has size aa, then (13) holds for every b∈Kℓb\in K_\ell. |Dℓ,b|=rℓa.|D_{\ell,b}|=r^\ell a.(13)✦ If r>0r>0 and every base block is nonempty, then (14) holds for every b∈Kℓb\in K_\ell. Dℓ,b≠⌀.D_{\ell,b}\ne\varnothing.(14)✦ For pairwise disjoint base blocks, (15) holds. Dℓ,b∩Dℓ,c=⌀(b,c∈Kℓ,b≠c).D_{\ell,b}\cap D_{\ell,c}=\varnothing \qquad(b,c\in K_\ell,\ b\ne c).(15)✦

Let TT be a tournament on [k][k], let λ\lambda take values in [r][r], and assume r>0r>0. Fix nonnegative integers ℓ,h\ell,h. If every base predicate Gh+ℓ,qG_{h+\ell,q} is false at 𝟎\mathbf 0, then (16) holds for every q∈[h]q\in[h]. Fℓ,h,q(𝟎)=false.F_{\ell,h,q}(\mathbf 0)=\mathrm{false}.(16)✦ If, in addition, every base predicate Gh+ℓ,qG_{h+\ell,q} is true at 𝟎Db\mathbf 0^{D_b} for every b∈Kb\in K, then (17) holds for every b∈Kℓb\in K_\ell and q∈[h]q\in[h]. Fℓ,h,q(𝟎Dℓ,b)=true.F_{\ell,h,q}\bigl(\mathbf 0^{D_{\ell,b}}\bigr)=\mathrm{true}.(17)✦ For r>0r>0 and nonempty, pairwise disjoint base blocks, the number of distinct blocks is (18). |{Dℓ,b:b∈Kℓ}|=kℓ|K|.\bigl|\{D_{\ell,b}:b\in K_\ell\}\bigr|=k^\ell|K|.(18)✦

In the paper, the result reads: for d≥1d\ge1 and M≥3M\ge3, with L=d+2L=d+2, k=2M2+1k=2M^2+1 and r=⌈M⌉r=\lceil\sqrt M\rceil, the specified construction has, at every level 0≤ℓ≤d0\le\ell\le d, all predicates false at zero and MkℓMk^\ell pairwise disjoint nonempty coordinate blocks of size LrℓLr^\ell, flipping any one of which at zero makes every predicate at that level true.

What Is Checked

The initial assertions concern the Hamming family (4) on [M]×[L][M]\times[L] with L=d+2L=d+2 and the base blocks (2); the tower assertions concern the recursively defined families (6) and (7) on (5), for arbitrary Boolean base predicates and a finite index set KK, with the stated hypotheses on the blocks and the label count.