OctoInformBeta

OpenAI preprint, September 2026 ยท ยง4. Quantitative bounds and separation

Corollary 4.3 [A fixed exponent greater than two]: Iteration yields growing block sensitivity at the all-false input

A fixed exponent above two.

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 question is how large block sensitivity at the all-false input can be compared with maximum sensitivity. Let II be a finite coordinate set and let f:{false,true}Iโ†’{false,true}f:\{\mathrm{false},\mathrm{true}\}^{I}\to\{\mathrm{false},\mathrm{true}\} be a total Boolean function. Write ๐ŸŽ\mathbf{0} for the all-false input and [n]={0,โ€ฆ,nโˆ’1}[n]=\{0,\ldots,n-1\} for the numbered coordinate set of size nn. A Boolean function ff is nonconstant if ff takes different values at two inputs.

The block flip xBx^B of an input xx along a coordinate block BโІIB\subseteq I is the input that complements precisely the coordinates in BB, as in (1). xiB={ยฌxi,iโˆˆB,xi,iโˆ‰B.x^B_i= \begin{cases} \neg x_i,&i\in B,\\ x_i,&i\notin B. \end{cases}(1)โœฆ

The local sensitivity s(f,x)s(f,x) counts the coordinates whose individual flips change ff at xxโœฆ; the sensitivity s(f)s(f) is its maximum over inputs, as in (2).โœฆ s(f,x)=|{iโˆˆI:f(x{i})โ‰ f(x)}|,s(f)=maxxs(f,x).s(f,x)=\bigl|\{i\in I:f(x^{\{i\}})\ne f(x)\}\bigr|, \qquad s(f)=\max_x s(f,x).(2)

The local block sensitivity bs(f,x)\mathrm{bs}(f,x) is the largest size of a family of pairwise disjoint nonempty coordinate blocks, each changing ff at xx; the empty family is allowed.โœฆ The block sensitivity bs(f)\mathrm{bs}(f) of a Boolean function ff is the maximum of its local block sensitivity bs(f,x)\mathrm{bs}(f,x) over inputs xx, as in (3).โœฆ bs(f,x)=max⁡{|โ„ฌ|:โ„ฌโІ2I\{โŒ€},โ„ฌ pairwise disjoint,f(xB)โ‰ f(x) for every Bโˆˆโ„ฌ},bs(f)=maxxbs(f,x).\begin{aligned} \mathrm{bs}(f,x) &=\max\bigl\{|\mathcal B|: \mathcal B\subseteq 2^I\setminus\{\varnothing\},\ \mathcal B\text{ pairwise disjoint},\ f(x^B)\ne f(x)\text{ for every }B\in\mathcal B\bigr\},\\ \mathrm{bs}(f)&=\max_x\mathrm{bs}(f,x). \end{aligned}(3)

Iterated Block Composition

For each nonnegative integer mm, the coordinate set ImI_m of the mmth iterate is the set defined recursively by (4), where *\ast is a single coordinate. I0={*},Im+1=Iร—Im.I_0=\{\ast\},\qquad I_{m+1}=I\times I_m.(4)โœฆ

The iterated block composition fโˆ˜mf^{\circ m} is the Boolean function on ImI_m defined by (5): each outer coordinate receives the value of the previous iterate on its own block. fโˆ˜0(x)=x*,fโˆ˜(m+1)(x)=f(iโ†ฆfโˆ˜m(jโ†ฆx(i,j))).f^{\circ 0}(x)=x_\ast,\qquad f^{\circ(m+1)}(x) =f\bigl(i\mapsto f^{\circ m}(j\mapsto x_{(i,j)})\bigr).(5)โœฆ

For a bijection e:Jโ†’Ke:J\to K, the coordinate relabelling heh^e of a Boolean function hh on JJ is the function on KK given by he(x)=h(xโˆ˜e)h^e(x)=h(x\circ e).โœฆ Choose bijections em:Imโ†’[|I|m]e_m:I_m\to[|I|^m]. The indexed iterate GmG_m of ff is the relabelled function (fโˆ˜m)em(f^{\circ m})^{e_m}.โœฆ

Seed Bounds and Amplification

For a positive integer MM, the depth-nine parameters are k=2M2+1k=2M^2+1, AM=22M10A_M=22M^{10} and BM=M2k9B_M=M^2k^9. The seed gap (6) holds for every positive integer MM. 1<AM,AM2<BM.1<A_M,\qquad A_M^2<B_M.(6)โœฆ For every positive real MM, the ratio bound is (7). 128121โ‰คBMAM2.\frac{128}{121}\le\frac{B_M}{A_M^2}.(7)โœฆ

Suppose II is finite, f(๐ŸŽ)=falsef(\mathbf{0})=\mathrm{false}, and natural numbers A,BA,B satisfy s(f)โ‰คAs(f)\le A, Bโ‰คbs(f,๐ŸŽ)B\le\mathrm{bs}(f,\mathbf{0}), 1<A1<A and A2<BA^2<B. Set ฮฑ=log⁡B/log⁡A\alpha=\log B/\log A. Power amplification gives (8) for the indexed iterates GmG_m. ฮฑ>2,|I|m>0,Gm(๐ŸŽ)=false,Gm is nonconstant(mโ‰ฅ0),s(Gm)ฮฑโ‰คbs(Gm,๐ŸŽ)(mโ‰ฅ0),(BA2)mโ‰คbs(Gm)s(Gm)2(mโ‰ฅ0),limmโ†’โˆžbs(Gm,๐ŸŽ)=+โˆž.\begin{gathered} \alpha>2,\\ |I|^m>0,\qquad G_m(\mathbf{0})=\mathrm{false},\qquad G_m\text{ is nonconstant}\quad(m\ge0),\\ s(G_m)^\alpha\le\mathrm{bs}(G_m,\mathbf{0})\quad(m\ge0),\\ \left(\frac{B}{A^2}\right)^m \le\frac{\mathrm{bs}(G_m)}{s(G_m)^2}\quad(m\ge0),\\ \lim_{m\to\infty}\mathrm{bs}(G_m,\mathbf{0})=+\infty. \end{gathered}(8)โœฆ

The Claim

Theorem 1. There exist a real number ฮฑ>2\alpha>2, integers nmn_m, and total Boolean functions Fm:{false,true}[nm]โ†’{false,true}F_m:\{\mathrm{false},\mathrm{true}\}^{[n_m]} \to\{\mathrm{false},\mathrm{true}\} such that, for every integer mโ‰ฅ1m\ge1, nm>0n_m>0, Fm(๐ŸŽ)=falseF_m(\mathbf{0})=\mathrm{false} and FmF_m is nonconstant, with the separation and growth in (9). s(Fm)ฮฑโ‰คbs(Fm,๐ŸŽ)(mโ‰ฅ1),limmโ†’โˆžbs(Fm,๐ŸŽ)=+โˆž.s(F_m)^\alpha\le\mathrm{bs}(F_m,\mathbf{0})\quad(m\ge1), \qquad \lim_{m\to\infty}\mathrm{bs}(F_m,\mathbf{0})=+\infty.(9)โœฆ There is also a choice of these data for which the same conditions hold for every integer mโ‰ฅ0m\ge0, together with the geometric bound (10). (128121)mโ‰คbs(Fm)s(Fm)2(mโ‰ฅ0).\left(\frac{128}{121}\right)^m \le\frac{\mathrm{bs}(F_m)}{s(F_m)^2}\quad(m\ge0).(10)โœฆ

In the paper, the result reads: there exist a real ฮฑ>2\alpha>2 and nonconstant total Boolean functions FmF_m, for integers mโ‰ฅ1m\ge1, such that bs(Fm,๐ŸŽ)โ‰ฅs(Fm)ฮฑ\mathrm{bs}(F_m,\mathbf{0})\ge s(F_m)^\alpha for every mm and bs(Fm,๐ŸŽ)\mathrm{bs}(F_m,\mathbf{0}) tends to infinity.

What Is Checked

The amplification statement ranges over total Boolean functions ff on arbitrary finite coordinate sets, with f(๐ŸŽ)=falsef(\mathbf{0})=\mathrm{false} and natural numbers A,BA,B satisfying s(f)โ‰คAs(f)\le A, Bโ‰คbs(f,๐ŸŽ)B\le\mathrm{bs}(f,\mathbf{0}), 1<A1<A and A2<BA^2<B; the resulting families have numbered coordinate sets [nm][n_m].

The iterated coordinate sets in (4) satisfy the counting identity (11). |Im|=|I|m.|I_m|=|I|^m.(11)โœฆ