OctoInformBeta

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

Lemma 4.1 [Quantitative sensitivity profiles]: The two output sides satisfy quantitative estimates under an explicit parameter budget

Sensitivity bounds through a fixed tower.

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 a Boolean input xx on a finite coordinate set II and a block B⊆IB\subseteq I, the block flip xBx^B is the Boolean input obtained by complementing the coordinates in BB.✦ The local sensitivity s(f,x)s(f,x) of a Boolean function ff counts the coordinates whose individual flips change its value, as in (1). xB(i)={¬x(i),i∈B,x(i),i∉B,s(f,x)=|{i∈I:f(x{i})≠f(x)}|.x^B(i)= \begin{cases} \lnot x(i),&i\in B,\\ x(i),&i\notin B, \end{cases} \qquad s(f,x)=\bigl|\{i\in I:f(x^{\{i\}})\ne f(x)\}\bigr|.(1) For a family F=(F1,…,Fh)F=(F_1,\ldots,F_h) of Boolean predicates and a Boolean output bb, the side sensitivity sb(F)s_b(F) is the maximum local sensitivity among predicates and inputs with output bb, with default value zero; its definition is (2). sb(F)=max⁡({0}∪{s(Fq,x):1≤q≤h,Fq(x)=b}),b∈{false,true}.s_b(F)=\max\bigl(\{0\}\cup \{s(F_q,x):1\le q\le h,\ F_q(x)=b\}\bigr), \qquad b\in\{\mathrm{false},\mathrm{true}\}.(2)✦

Write [m]={1,…,m}[m]=\{1,\ldots,m\}. A tournament TT on [k][k] is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices.✦ A regular tournament TT with parameter MM is a tournament on [k][k] with k=2M2+1k=2M^2+1 vertices and outdegree M2M^2 at every vertex.✦ A good labelling of TT by rr labels is a map λ:[k]×[k]→[r]\lambda:[k]\times[k]\to[r] such that, for every vertex set UU of size t=16t=16 and every map m:[k]→[r]m:[k]\to[r], some i,j∈Ui,j\in U satisfy i→ji\to j and λ(i,j)≠m(j)\lambda(i,j)\ne m(j).✦

For a finite family of Boolean centres 𝒞=(ca)a∈A\mathcal C=(c_a)_{a\in A} on II, the union of Hamming balls of radius RR is the predicate ℬ𝒞,R\mathcal B_{\mathcal C,R} defined by (3), where dHd_H denotes Hamming distance. ℬ𝒞,R(x)=true⇔there exists a∈A with dH(x,ca)≤R.\mathcal B_{\mathcal C,R}(x)=\mathrm{true} \quad\Longleftrightarrow\quad \text{there exists }a\in A\text{ with }d_H(x,c_a)\le R.(3)✦ Let dd be a nonnegative integer, and set L=d+2L=d+2. For j∈[M]j\in[M], the block indicator centre cjc_j on [M]×[L][M]\times[L] is the Boolean input that is true exactly on block jj.✦ The initial Hamming family FF consists of the d+1d+1 predicates in (4), indexed from 11. cj(a,z)={true,a=j,false,a≠j,Fq=ℬ(cj)j∈[M],d+1−q,1≤q≤d+1.c_j(a,z)= \begin{cases} \mathrm{true},&a=j,\\ \mathrm{false},&a\ne j, \end{cases} \qquad F_q=\mathcal B_{(c_j)_{j\in[M]},\,d+1-q}, \quad 1\le q\le d+1.(4) The extension BB of a DD-predicate family FF is a collection of predicate families, one at each predicate count hh, defined by (5).✦ The construction base BB is the collection of predicate families defined by (5) with D=d+1D=d+1 and the initial Hamming family FF from (4). Bh,q(x)={Fq(x),h=D,false,h≠D,1≤q≤h.B_{h,q}(x)= \begin{cases} F_q(x),&h=D,\\ \mathrm{false},&h\ne D, \end{cases} \qquad 1\le q\le h.(5)✦

For a finite base coordinate set II, the tower coordinate sets IℓI_\ell are the products in (6). I0=I,Iℓ+1=([k]×[r])×Iℓ.I_0=I,\qquad I_{\ell+1}=([k]\times[r])\times I_\ell.(6)✦ The iterated family ℱ(ℓ,h)\mathcal F^{(\ell,h)} of hh predicates on IℓI_\ell equals BhB_h at depth zero; at successor depth it is the recursive predicate family formed from ℱ(ℓ,h+1)\mathcal F^{(\ell,h+1)} using TT and λ\lambda.✦ The tower side sensitivity Sℓ,bS_{\ell,b} is defined by (7), where D−ℓD-\ell is truncated at zero. Sℓ,b=sb(ℱ(ℓ,D−ℓ)).S_{\ell,b}=s_b\bigl(\mathcal F^{(\ell,D-\ell)}\bigr).(7)✦

The Claim

Theorem 1 (Quantitative sensitivity profiles). Let dd be a nonnegative integer.

For the coupled recurrence bound, let u,v:ℕ→ℝu,v:\mathbb N\to\mathbb R and ε,C≥0\varepsilon,C\ge0. Suppose ε3d+1≤2\varepsilon3^{d+1}\le2, u0≤Cu_0\le C and v0≤0v_0\le0, and suppose the recurrences (8) hold. uℓ+1≤(1+ε)uℓ+3vℓ,vℓ+1≤εuℓ+3vℓ,0≤ℓ<d.\begin{aligned} u_{\ell+1}&\le(1+\varepsilon)u_\ell+3v_\ell,\\ v_{\ell+1}&\le\varepsilon u_\ell+3v_\ell, \end{aligned} \qquad 0\le\ell<d.(8) Then the coupled recurrence estimate is (9). uℓ≤2C,vℓ≤εC(3ℓ−1),0≤ℓ≤d.u_\ell\le2C,\qquad v_\ell\le\varepsilon C(3^\ell-1), \qquad 0\le\ell\le d.(9)✦

Let C,M,rC,M,r be nonnegative integers with M>0M>0, and put ε=max⁡{r,16}/M\varepsilon=\max\{r,16\}/M. Suppose ε3d+1≤2\varepsilon3^{d+1}\le2. Let Sℓ,bS_{\ell,b} and Jℓ,bJ_{\ell,b} be arrays of nonnegative integers with S0,false≤CS_{0,\mathrm{false}}\le C, S0,true≤CMS_{0,\mathrm{true}}\le CM and J0,false=J0,true=0J_{0,\mathrm{false}}=J_{0,\mathrm{true}}=0. Suppose the ordinary and joint profiles satisfy (10). Sℓ+1,false≤16Sℓ,false+Sℓ,true+3Jℓ,true,Sℓ+1,true≤M2Sℓ,false+rSℓ,true,Jℓ+1,false≤16Sℓ,false+3Jℓ,true,Jℓ+1,true≤M2Jℓ,false+rSℓ,true,0≤ℓ<d.\begin{aligned} S_{\ell+1,\mathrm{false}} &\le16S_{\ell,\mathrm{false}}+S_{\ell,\mathrm{true}} +3J_{\ell,\mathrm{true}},\\ S_{\ell+1,\mathrm{true}} &\le M^2S_{\ell,\mathrm{false}}+rS_{\ell,\mathrm{true}},\\ J_{\ell+1,\mathrm{false}} &\le16S_{\ell,\mathrm{false}}+3J_{\ell,\mathrm{true}},\\ J_{\ell+1,\mathrm{true}} &\le M^2J_{\ell,\mathrm{false}}+rS_{\ell,\mathrm{true}}, \end{aligned} \qquad 0\le\ell<d.(10) Then the two-sided sensitivity estimate is (11). Sℓ,false≤2CMℓ,Sℓ,true≤2CMℓ+1,0≤ℓ≤d.S_{\ell,\mathrm{false}}\le2CM^\ell,\qquad S_{\ell,\mathrm{true}}\le2CM^{\ell+1}, \qquad 0\le\ell\le d.(11)✦

Suppose d≥1d\ge1 and M≥9d+1M\ge9^{d+1}, and choose r=⌈M⌉r=\lceil\sqrt M\rceil. Then (12) holds. max⁡{r,16}M3d+1≤2.\frac{\max\{r,16\}}{M}\,3^{d+1}\le2.(12)✦

Let M,r>0M,r>0 be integers, let TT be a regular tournament with parameter MM, and let λ\lambda be a good labelling by rr labels. Use the construction base, L=d+2L=d+2 and D=d+1D=d+1 in (7). Suppose max⁡{r,16}3d+1/M≤2\max\{r,16\}\,3^{d+1}/M\le2. Then the tower sensitivity estimate is (13). Sℓ,false≤2LMℓ,Sℓ,true≤2LMℓ+1,0≤ℓ≤d.S_{\ell,\mathrm{false}}\le2LM^\ell,\qquad S_{\ell,\mathrm{true}}\le2LM^{\ell+1}, \qquad 0\le\ell\le d.(13)✦

In the paper, the result reads: for d≥1d\ge1 and M≥9d+1M\ge9^{d+1}, with L=d+2L=d+2, r=⌈M⌉r=\lceil\sqrt M\rceil, a regular tournament and labels satisfying the good labelling condition, every level 0≤ℓ≤d0\le\ell\le d satisfies Sℓ,false≤2LMℓS_{\ell,\mathrm{false}}\le2LM^\ell and Sℓ,true≤2LMℓ+1S_{\ell,\mathrm{true}}\le2LM^{\ell+1}.

What Is Checked

The tower estimate (13) is stated over finite Boolean tower families with a regular tournament and good labels; the numerical estimates (11) and (9) concern arrays and real sequences satisfying their respective initial conditions and recurrences, and the budget estimate (12) concerns integers d≥1d\ge1 and M≥9d+1M\ge9^{d+1}.