OctoInformBeta

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

Lemma 2.2 [Initial sensitivity profiles]: Its joint sensitivities vanish for all nonnegative dd and MM

The initial family has bounded side sensitivities.

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 asks how much sensitivity a Hamming ball family can have on each output side, and how much two of its predicates can share.

Let II be a finite coordinate set, and let an input xx assign false or true to each coordinate. The block flip xBx^B of xx along a subset B⊆IB\subseteq I is the input specified in (1), where ¬\neg denotes Boolean complementation. xB(i)={¬x(i),i∈B,x(i),i∉B.x^B(i)= \begin{cases} \neg x(i),&i\in B,\\ x(i),&i\notin B. \end{cases}(1)✦ For a Boolean function ff on II, the local sensitivity s(f,x)s(f,x) is the number of coordinates whose individual flip changes its value, as in (2). s(f,x)=|{i∈I:f(x{i})≠f(x)}|.s(f,x)=\bigl|\{i\in I:f(x^{\{i\}})\ne f(x)\}\bigr|.(2)✦ The local joint sensitivity j(f,g,x)j(f,g,x) of two Boolean functions f,gf,g on II is the number of coordinates sensitive for both at xx, as in (3). j(f,g,x)=|{i∈I:f(x{i})≠f(x)andg(x{i})≠g(x)}|.j(f,g,x)=\bigl|\{i\in I: f(x^{\{i\}})\ne f(x)\ \text{and}\ g(x^{\{i\}})\ne g(x)\}\bigr|.(3)✦

For a family F=(Fp)1≤p≤hF=(F_p)_{1\le p\le h} of Boolean predicates on II and a Boolean value bb, the side sensitivity Sb(F)S_b(F) is the maximum local sensitivity at inputs with output bb, taken over the family, as in (4). Sb(F)=max⁡({s(Fp,x):1≤p≤h,Fp(x)=b}∪{0}).S_b(F)=\max\bigl(\{s(F_p,x):1\le p\le h,\ F_p(x)=b\}\cup\{0\}\bigr).(4)✦ The joint sensitivity Jb(F)J_b(F) is the maximum local joint sensitivity of two distinct predicates at an input where both have output bb, as in (5). Jb(F)=max⁡({j(Fp,Fp′,x):1≤p<p′≤h,Fp(x)=Fp′(x)=b}∪{0}).J_b(F)=\max\bigl(\{j(F_p,F_{p'},x): 1\le p<p'\le h,\ F_p(x)=F_{p'}(x)=b\}\cup\{0\}\bigr).(5)✦

Let 𝒞=(ca)a∈C\mathcal C=(c_a)_{a\in C} be a family of Boolean centers on II, indexed by a finite set CC, and write dHd_H for Hamming distance. The union g𝒞,Rg_{\mathcal C,R} of Hamming balls of nonnegative integer radius RR about a family 𝒞\mathcal C of Boolean centers on II is the Boolean predicate defined by (6). g𝒞,R(x)=true⇔there is a∈C with dH(x,ca)≤R.g_{\mathcal C,R}(x)=\mathrm{true} \quad\Longleftrightarrow\quad \text{there is }a\in C\text{ with }d_H(x,c_a)\le R.(6) For an input xx on II and a nonempty family 𝒞=(ca)a∈C\mathcal C=(c_a)_{a\in C} of Boolean centers on II, the nearest center distance δ𝒞(x)\delta_{\mathcal C}(x) is the minimum Hamming distance from xx to a center, as in (7). δ𝒞(x)=mina∈CdH(x,ca).\delta_{\mathcal C}(x)=\min_{a\in C}d_H(x,c_a).(7)✦

Fix nonnegative integers d,Md,M, put L=d+2L=d+2, and take the coordinate set I={1,…,M}×{1,…,L}I=\{1,\ldots,M\}\times\{1,\ldots,L\}. The block indicator center eje_j on II, for 1≤j≤M1\le j\le M, is the Boolean input defined by (8). ej(a,u)=true⇔a=j.e_j(a,u)=\mathrm{true}\quad\Longleftrightarrow\quad a=j.(8) The initial Hamming family F0=(F0,p)1≤p≤d+1F_0=(F_{0,p})_{1\le p\le d+1} on II is the family of Boolean predicates in (9), with ℰ=(ej)1≤j≤M\mathcal E=(e_j)_{1\le j\le M}. F0,p(x)=gℰ,d+1−p(x),1≤p≤d+1.F_{0,p}(x)=g_{\mathcal E,d+1-p}(x),\qquad 1\le p\le d+1.(9)✦ Its nesting is in the predicate index pp. Write S(0,b)=Sb(F0)S_{(0,b)}=S_b(F_0) and J(0,b)=Jb(F0)J_{(0,b)}=J_b(F_0) for its ordinary and joint profiles.

The Claim

Theorem 1. Let d,Md,M be nonnegative integers and L=d+2L=d+2. The initial family has the false-side bound (10), the true-side bound (11), and the joint profile (12) for either Boolean value bb: S(0,false)≤L.S_{(0,\mathrm{false})}\le L.(10)✦ S(0,true)≤LM.S_{(0,\mathrm{true})}\le LM.(11)✦ J(0,b)=0,b∈{false,true}.J_{(0,b)}=0,\qquad b\in\{\mathrm{false},\mathrm{true}\}.(12)✦

Let 𝒞=(ca)a∈C\mathcal C=(c_a)_{a\in C} be a finite family of Boolean centers on a finite coordinate set II, and let RR be a nonnegative integer. Suppose distinct centers satisfy dH(ca,ca′)>2(R+1)d_H(c_a,c_{a'})>2(R+1) whenever a≠a′a\ne a'. At any input xx with g𝒞,R(x)=falseg_{\mathcal C,R}(x)=\mathrm{false}, the local sensitivity satisfies (13): s(g𝒞,R,x)≤R+1.s(g_{\mathcal C,R},x)\le R+1.(13)✦

For any nonempty finite family 𝒞\mathcal C of Boolean centers on a finite coordinate set II, every input xx and coordinate i∈Ii\in I satisfy (14): |δ𝒞(x)−δ𝒞(x{i})|≤1.\left|\delta_{\mathcal C}(x)-\delta_{\mathcal C}(x^{\{i\}})\right|\le1.(14)✦

In the paper, the result reads: for d≥1d\ge1 and M≥3M\ge3, with L=d+2L=d+2, S(0,false)≤LS_{(0,\mathrm{false})}\le L, S(0,true)≤LMS_{(0,\mathrm{true})}\le LM, and J(0,false)=J(0,true)=0J_{(0,\mathrm{false})}=J_{(0,\mathrm{true})}=0.

What Is Checked

The initial profile statements concern the initial Hamming family (9) for all nonnegative d,Md,M; the Hamming ball statements concern finite coordinate sets and finite center families, with separation in (13) and nonemptiness in (14).