OctoInformBeta

OpenAI preprint, September 2026 · §4. Quantitative bounds and separation

§4 (proof of Theorem 1.1): the final OR, dimension, and quantitative bounds: Exact dimension and quantitative bounds for an unbounded ratio of block sensitivity to squared sensitivity

Final disjunction (OR) witnesses give a superquadratic separation.

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

For an OR of disjoint copies of a Boolean function, sensitivity counts individual coordinates that change the output, whereas block sensitivity counts disjoint sets of coordinates that change it. The final construction concerns the ratio of block sensitivity to squared sensitivity as the depth increases.

Write 𝔹={false,true}\mathbb B=\{\mathrm{false},\mathrm{true}\} and let 𝟎\mathbf0 denote the all-false input. For a finite coordinate set II, an input x∈𝔹Ix\in\mathbb B^I and a block B⊆IB\subseteq I, the block flip xBx^B complements precisely the coordinates in BB.✦ The local sensitivity s(g,x)s(g,x) of a Boolean function g:𝔹I→𝔹g:\mathbb B^I\to\mathbb B is the number of coordinates ii for which g(x{i})≠g(x)g(x^{\{i\}})\ne g(x).✦ For a Boolean function g:𝔹I→𝔹g:\mathbb B^I\to\mathbb B on a finite coordinate set II and an input x∈𝔹Ix\in\mathbb B^I, the local block sensitivity bs(g,x)\mathrm{bs}(g,x) is the maximum size of a family of pairwise disjoint nonempty blocks BB satisfying g(xB)≠g(x)g(x^B)\ne g(x), with the empty family allowed.✦ For a Boolean function g:𝔹I→𝔹g:\mathbb B^I\to\mathbb B on a finite coordinate set II, the maximum sensitivity s(g)s(g) and maximum block sensitivity bs(g)\mathrm{bs}(g) are the maxima of the corresponding local quantities over all inputs, as in (1). s(g)=maxx∈𝔹Is(g,x),bs(g)=maxx∈𝔹Ibs(g,x).s(g)=\max_{x\in\mathbb B^I}s(g,x), \qquad \mathrm{bs}(g)=\max_{x\in\mathbb B^I}\mathrm{bs}(g,x).(1)

For a finite set KK, the OR gate OR⁡K:𝔹K→𝔹\operatorname{OR}_K:\mathbb B^K\to\mathbb B is true exactly when at least one of its inputs is true.✦ The block composition u∘vu\circ v of u:𝔹I→𝔹u:\mathbb B^I\to\mathbb B and v:𝔹J→𝔹v:\mathbb B^J\to\mathbb B is the Boolean function on I×JI\times J given by (2), where xi(j)=x(i,j)x_i(j)=x(i,j). (u∘v)(x)=u((v(xi))i∈I).(u\circ v)(x)=u\bigl((v(x_i))_{i\in I}\bigr).(2)✦ The OR of disjoint copies HKgH_Kg of g:𝔹I→𝔹g:\mathbb B^I\to\mathbb B is the function on K×IK\times I defined in (3). HKg=OR⁡K∘g.H_Kg=\operatorname{OR}_K\circ g.(3)✦

The Tower Predicate

For a natural number mm, write Fin⁡m={0,…,m−1}\operatorname{Fin}m=\{0,\ldots,m-1\}. Let d,M,rd,M,r be natural numbers, and put L=d+2L=d+2, k=2M2+1k=2M^2+1 and t=16t=16. A tournament TT on Fin⁡k\operatorname{Fin}k is a directed graph without loops in which exactly one of i→ji\to j and j→ij\to i holds for distinct vertices.✦ A regular tournament TT on Fin⁡k\operatorname{Fin}k with parameter MM is a tournament in which every vertex has outdegree M2M^2.✦

A good labelling of TT with rr labels is a map λ:Fin⁡k×Fin⁡k→Fin⁡r\lambda:\operatorname{Fin}k\times\operatorname{Fin}k\to\operatorname{Fin}r satisfying (4): for every set UU of tt vertices and every map m:Fin⁡k→Fin⁡rm:\operatorname{Fin}k\to\operatorname{Fin}r, there are i,j∈Ui,j\in U such that i→jandλ(i,j)≠m(j).i\to j\quad\text{and}\quad\lambda(i,j)\ne m(j).(4)✦

For a finite base coordinate set II and a natural number ℓ\ell, the tower coordinate sets 𝒯ℓ(I)\mathcal T_\ell(I) and the construction coordinate sets CℓC_\ell are the finite sets defined recursively in (5). 𝒯0(I)=I,𝒯ℓ+1(I)=(Fin⁡k×Fin⁡r)×𝒯ℓ(I),Cℓ=𝒯ℓ(Fin⁡M×Fin⁡L).\begin{aligned} \mathcal T_0(I)&=I,\qquad \mathcal T_{\ell+1}(I) =(\operatorname{Fin}k\times\operatorname{Fin}r)\times\mathcal T_\ell(I),\\ C_\ell&=\mathcal T_\ell(\operatorname{Fin}M\times\operatorname{Fin}L). \end{aligned}(5)

For a finite coordinate set II, a finite family of centers in 𝔹I\mathbb B^I and a radius RR, the union of Hamming balls of radius RR is the Boolean predicate on 𝔹I\mathbb B^I that is true exactly when the input has Hamming distance at most RR from one of the centers.✦ For a∈Fin⁡Ma\in\operatorname{Fin}M, the block indicator center cac_a on Fin⁡M×Fin⁡L\operatorname{Fin}M\times\operatorname{Fin}L is the Boolean input that is true exactly on coordinates whose first component equals aa.✦ With dHd_H denoting Hamming distance, the initial Hamming ball family B1,…,Bd+1B_1,\ldots,B_{d+1} is the family of Boolean predicates on Fin⁡M×Fin⁡L\operatorname{Fin}M\times\operatorname{Fin}L defined by (6). Bj(x)=true⇔∃a∈Fin⁡M,dH(x,ca)≤d+1−j,1≤j≤d+1.B_j(x)=\mathrm{true} \quad\Longleftrightarrow\quad \exists a\in\operatorname{Fin}M,\quad d_H(x,c_a)\le d+1-j, \qquad 1\le j\le d+1.(6)✦ For every index count hh, the construction base family is the family of hh Boolean predicates on Fin⁡M×Fin⁡L\operatorname{Fin}M\times\operatorname{Fin}L equal to B1,…,Bd+1B_1,\ldots,B_{d+1} when h=d+1h=d+1 and to the constant false family otherwise.✦ For a family A1,…,ADA_1,\ldots,A_D of Boolean predicates on a coordinate set II and a natural index count hh, the extended initial family is the family of hh Boolean predicates on II that equals A1,…,ADA_1,\ldots,A_D when h=Dh=D and consists of hh constant false predicates otherwise.✦

For a tournament TT on kk vertices, a labelling λ\lambda with rr labels and a base family of hh Boolean predicates on a coordinate set II for every natural index count hh, the tower predicate family consists of hh Boolean predicates on 𝒯ℓ(I)\mathcal T_\ell(I) at depth ℓ\ell. For a tournament TT on kk vertices, a labelling λ\lambda with rr labels and a base family on II for every natural index count, the tower predicate family at index count hh is the base family at index count hh at depth zero, and is the recursive predicate family formed from the preceding tower family at index count h+1h+1 at a successor depth.✦ For a regular tournament TT with parameter MM and a good labelling λ\lambda with rr labels, the terminal predicate Pd,1:𝔹Cd→𝔹P_{d,1}:\mathbb B^{C_d}\to\mathbb B is the sole predicate in the tower predicate family with the construction base family at depth dd and index count one.✦

The construction dimension N=N(d,M,r)N=N(d,M,r) is the natural number in (7). N(d,M,r)=LM2(kr)d.N(d,M,r)=LM^2(kr)^d.(7)✦

Coordinate relabelling along a bijection e:I→Je:I\to J sends a Boolean function gg on II to the function x↦g(x∘e)x\mapsto g(x\circ e) on JJ.✦

The Claim

Theorem 1. Let I,KI,K be finite sets and g:𝔹I→𝔹g:\mathbb B^I\to\mathbb B. Suppose the nonnegative integers Sfalse,StrueS_{\mathrm{false}},S_{\mathrm{true}} satisfy s(g,x)≤Sbs(g,x)\le S_b for every b∈𝔹b\in\mathbb B and every input x∈𝔹Ix\in\mathbb B^I with g(x)=bg(x)=b. Then the OR sensitivity bound is (8). s(HKg)≤max⁡{|K|Sfalse,Strue}.s(H_Kg)\le \max\bigl\{|K|S_{\mathrm{false}},S_{\mathrm{true}}\bigr\}.(8)✦ If g(𝟎)=falseg(\mathbf0)=\mathrm{false}, the bound at the all-false input is (9). |K|bs(g,𝟎)≤bs(HKg,𝟎).|K|\,\mathrm{bs}(g,\mathbf0) \le\mathrm{bs}(H_Kg,\mathbf0).(9)✦

For natural numbers d,M,rd,M,r, let TT be a regular tournament with parameter MM and λ\lambda a good labelling with rr labels. The final OR function Gd,T,λG_{d,T,\lambda} on Fin⁡M×Cd\operatorname{Fin}M\times C_d is defined by (10). Gd,T,λ=HFin⁡MPd,1.G_{d,T,\lambda}=H_{\operatorname{Fin}M}P_{d,1}.(10)✦ Its coordinate count is (11). |Fin⁡M×Cd|=N(d,M,r).\bigl|\operatorname{Fin}M\times C_d\bigr|=N(d,M,r).(11)✦ For the fixed coordinate bijection e:Fin⁡M×Cd→Fin⁡Ne:\operatorname{Fin}M\times C_d\to\operatorname{Fin}N, the indexed final witness fd,T,λ:𝔹Fin⁡N→𝔹f_{d,T,\lambda}:\mathbb B^{\operatorname{Fin}N}\to\mathbb B is the relabelling in (12). fd,T,λ(x)=Gd,T,λ(x∘e).f_{d,T,\lambda}(x)=G_{d,T,\lambda}(x\circ e).(12)✦ Assume M>0M>0, r>0r>0 and max⁡{r,t}M3d+1≤2\frac{\max\{r,t\}}{M}\,3^{d+1}\le2; then the sensitivity estimate (13) holds. s(fd,T,λ)≤2LMd+1.s(f_{d,T,\lambda})\le2LM^{d+1}.(13)✦ When r>0r>0, the block sensitivity estimate is (14). bs(fd,T,λ,𝟎)≥M2kd.\mathrm{bs}(f_{d,T,\lambda},\mathbf0)\ge M^2k^d.(14)✦

For d≥1d\ge1 and M≥9d+1M\ge9^{d+1}, set r=⌈M⌉r=\lceil\sqrt M\rceil. There is a Boolean function F:𝔹Fin⁡N→𝔹F:\mathbb B^{\operatorname{Fin}N}\to\mathbb B with the properties in (15). N>0,F(𝟎)=false,F is nonconstant,s(F)≤2LMd+1,bs(F,𝟎)≥M2kd.\begin{gathered} N>0,\qquad F(\mathbf0)=\mathrm{false},\qquad F\text{ is nonconstant},\\ s(F)\le2LM^{d+1},\qquad \mathrm{bs}(F,\mathbf0)\ge M^2k^d. \end{gathered}(15)✦

Let d,Md,M be natural numbers with M>0M>0, and let uu be a nonconstant Boolean function on any finite coordinate set. Suppose s(u)≤2LMd+1s(u)\le2LM^{d+1} and bs(u,𝟎)≥M2kd\mathrm{bs}(u,\mathbf0)\ge M^2k^d. Then (16) holds. bs(u)s(u)2≥2d4(d+2)2.\frac{\mathrm{bs}(u)}{s(u)^2} \ge\frac{2^d}{4(d+2)^2}.(16)✦ The numerical lower bound has the natural depth limit (17). limd→∞d∈ℕ2d4(d+2)2=+∞.\lim_{\substack{d\to\infty\\d\in\mathbb N}} \frac{2^d}{4(d+2)^2}=+\infty.(17)✦

In the paper, the result reads: for every integer d≥1d\ge1, choose M≥9d+1M\ge9^{d+1} and good labels, set r=⌈M⌉r=\lceil\sqrt M\rceil, and let ff be the OR of MM disjoint copies of Pd,1P_{d,1}; then n=LM2(kr)dn=LM^2(kr)^d, f(𝟎)=falsef(\mathbf0)=\mathrm{false}, ff is nonconstant, s(f)≤2LMd+1s(f)\le2LM^{d+1} and bs(f,𝟎)≥M2kd\mathrm{bs}(f,\mathbf0)\ge M^2k^d, with bs(f)/s(f)2≥2d/(4(d+2)2)\mathrm{bs}(f)/s(f)^2\ge2^d/(4(d+2)^2) tending to infinity with dd.

What Is Checked

The OR estimates (8) and (9) concern arbitrary finite coordinate and copy sets; the construction statements concern natural parameters and regular tournaments with good labellings, and the ratio estimate (16) concerns any nonconstant finite Boolean function satisfying its two quantitative bounds.