OctoInformBeta

OpenAI preprint, September 2026 ยท ยง3. Sensitivity recurrences

Proposition 3.1 [Four coupled sensitivity recurrences]: Coupled bounds for ordinary and joint profiles of nested tournament families and their iterates

Four recurrences bound recursive sensitivity.

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

A recursive Boolean family has sensitive coordinates at each output value, and two predicates can share sensitive coordinates at a common input. The ordinary and joint profiles measure these two kinds of sensitivity through the recursion.

Let II be a finite coordinate set and let ๐”น={false,true}\mathbb B=\{\mathrm{false},\mathrm{true}\}. Write [a]={1,โ€ฆ,a}[a]=\{1,\ldots,a\}, with [0]=โŒ€[0]=\varnothing. A tournament TT on a finite vertex set VV is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices.โœฆ Write iโ†’ji\to j for an edge of TT. A tournament TT with natural parameter MM is regular if it has k=2M2+1k=2M^2+1 vertices, each with exactly M2M^2 outgoing neighbors.โœฆ

A good labeling ฮป:Vร—Vโ†’[r]\lambda:V\times V\to[r] of TT, where r>0r>0, is a map satisfying (1) for every UโІVU\subseteq V with |U|=t=16|U|=t=16 and every assignment a:Vโ†’[r]a:V\to[r]: โˆƒi,jโˆˆUiโ†’jandฮป(i,j)โ‰ a(j).\exists i,j\in U\quad i\to j\quad\text{and}\quad\lambda(i,j)\ne a(j).(1)โœฆ

Sensitivity Profiles

The block flip xBx^B of an input xโˆˆ๐”นIx\in\mathbb B^I in a block BโІIB\subseteq I is the input defined by (2), where ยฌ\neg complements a Boolean value: (xB)i={ยฌxi,iโˆˆB,xi,iโˆ‰B.(x^B)_i= \begin{cases} \neg x_i,&i\in B,\\ x_i,&i\notin B. \end{cases}(2)โœฆ

The local sensitivity s(f,x)s(f,x) of a Boolean function f:๐”นIโ†’๐”นf:\mathbb B^I\to\mathbb B at an input xโˆˆ๐”นIx\in\mathbb B^I is the number of coordinates whose flip changes its value.โœฆ The local joint sensitivity j(f,g;x)j(f,g;x) of Boolean functions f,g:๐”นIโ†’๐”นf,g:\mathbb B^I\to\mathbb B at an input xโˆˆ๐”นIx\in\mathbb B^I is the number of coordinates whose flip changes both values, as in (3): s(f,x)=|{iโˆˆI:f(x{i})โ‰ f(x)}|,j(f,g;x)=|{iโˆˆI:f(x{i})โ‰ f(x),g(x{i})โ‰ g(x)}|.\begin{aligned} s(f,x)&=\bigl|\{i\in I:f(x^{\{i\}})\ne f(x)\}\bigr|,\\ j(f,g;x)&=\bigl|\{i\in I:f(x^{\{i\}})\ne f(x),\ g(x^{\{i\}})\ne g(x)\}\bigr|. \end{aligned}(3)

For a family F=(Fq)qโˆˆ[m]F=(F_q)_{q\in[m]} of Boolean predicates on ๐”นI\mathbb B^I and bโˆˆ๐”นb\in\mathbb B, the side sensitivity sb(F)s_b(F) and joint sensitivity jb(F)j_b(F) are the maxima in (4); an empty eligible set has maximum zero: sb(F)=max⁡({0}โˆช{s(Fq,x):qโˆˆ[m],xโˆˆ๐”นI,Fq(x)=b}),jb(F)=max⁡({0}โˆช{j(Fq,Fqโ€ฒ;x):q<qโ€ฒ,q,qโ€ฒโˆˆ[m],xโˆˆ๐”นI,Fq(x)=Fqโ€ฒ(x)=b}).\begin{aligned} s_b(F)&=\max\bigl(\{0\}\cup \{s(F_q,x):q\in[m],\ x\in\mathbb B^I,\ F_q(x)=b\}\bigr),\\ j_b(F)&=\max\bigl(\{0\}\cup \{j(F_q,F_{q'};x):q<q',\ q,q'\in[m],\ x\in\mathbb B^I, \ F_q(x)=F_{q'}(x)=b\}\bigr). \end{aligned}(4)

A nested family F=(Fq)qโˆˆ[m]F=(F_q)_{q\in[m]} of Boolean predicates on ๐”นI\mathbb B^I is a family whose acceptance sets decrease with the predicate index, as specified in (5) for every input xโˆˆ๐”นIx\in\mathbb B^I: qโ‰คqโ€ฒ,Fqโ€ฒ(x)=trueโ‡’Fq(x)=true.q\le q',\quad F_{q'}(x)=\mathrm{true} \quad\Longrightarrow\quad F_q(x)=\mathrm{true}.(5)โœฆ

The Recursive Family

Let FF have h+1h+1 predicates. For an input xโˆˆ๐”น(Vร—[r])ร—Ix\in\mathbb B^{(V\times[r])\times I}, its child input at row jj and label cc is xj,cโˆˆ๐”นIx_{j,c}\in\mathbb B^I, defined by xj,c(a)=x((j,c),a)x_{j,c}(a)=x((j,c),a).โœฆ The reversed gate index at predicate position qโˆˆ[h]q\in[h] is gh(q)=h+1โˆ’qg_h(q)=h+1-q.โœฆ

For a family FF of h+1h+1 Boolean predicates on ๐”นI\mathbb B^I, a predicate index qโˆˆ[h]q\in[h] and a vertex iโˆˆVi\in V, the row clause Cq,iC_{q,i} is the Boolean predicate on ๐”น(Vร—[r])ร—I\mathbb B^{(V\times[r])\times I} that requires acceptance by the last predicate throughout row ii and rejection by the gate predicate at each labeled outgoing neighbor, as in (6): Cq,i(x)=truequadโ‡”(โˆ€cโˆˆ[r],Fh+1(xi,c)=true)โˆง(โˆ€jโˆˆV,iโ†’jโ‡’Fgh(q)(xj,ฮป(i,j))=false).C_{q,i}(x)=\mathrm{true}quad\Longleftrightarrow\quad \left(\forall c\in[r],\ F_{h+1}(x_{i,c})=\mathrm{true}\right) \ \land\ \left(\forall j\in V,\ i\to j\ \Longrightarrow\ F_{g_h(q)}(x_{j,\lambda(i,j)})=\mathrm{false}\right).(6)โœฆ

For a family FF of h+1h+1 Boolean predicates on ๐”นI\mathbb B^I, the recursive family โ„›(F)\mathcal R(F) is the family of hh Boolean predicates on ๐”น(Vร—[r])ร—I\mathbb B^{(V\times[r])\times I} that accept when at least one row clause accepts, as in (7): โ„›(F)q(x)=trueโ‡”โˆƒiโˆˆV,Cq,i(x)=true.\mathcal R(F)_q(x)=\mathrm{true}\quad\Longleftrightarrow\quad \exists i\in V,\ C_{q,i}(x)=\mathrm{true}.(7)โœฆ

Iteration

A base collection โ„ฌ=(B(a))aโ‰ฅ0\mathcal B=(B^{(a)})_{a\ge0} is a collection whose entry B(a)B^{(a)} is a family of aa Boolean predicates on ๐”นI\mathbb B^I for each aa. For each nonnegative integer level โ„“\ell and each nonnegative integer aa, the tower coordinate set Iโ„“I_\ell and iterated family F(โ„“,a)F^{(\ell,a)} are defined by (8), using the fixed tournament and labeling: I0=I,Iโ„“+1=(Vร—[r])ร—Iโ„“,F(0,a)=B(a),F(โ„“+1,a)=โ„›(F(โ„“,a+1)).\begin{aligned} I_0&=I,& I_{\ell+1}&=(V\times[r])\times I_\ell,\\ F^{(0,a)}&=B^{(a)},& F^{(\ell+1,a)}&=\mathcal R\bigl(F^{(\ell,a+1)}\bigr). \end{aligned}(8)

For a natural number DD, the ordinary tower profile Sโ„“,bS_{\ell,b} and joint tower profile Jโ„“,bJ_{\ell,b} are the side and joint sensitivities in (9), with subtraction truncated at zero: Sโ„“,b=sb(F(โ„“,Dโˆ’โ„“)),Jโ„“,b=jb(F(โ„“,Dโˆ’โ„“)).S_{\ell,b}=s_b\bigl(F^{(\ell,D-\ell)}\bigr),\qquad J_{\ell,b}=j_b\bigl(F^{(\ell,D-\ell)}\bigr).(9)

The Claim

Theorem 1. Let TT be a regular tournament with parameter MM and let ฮป\lambda be a good labeling by r>0r>0 labels. Let FF be a nested family of h+1h+1 Boolean predicates on a finite coordinate set. Its recursive family P=โ„›(F)P=\mathcal R(F) satisfies (10): strue(P)โ‰คM2sfalse(F)+rstrue(F),jtrue(P)โ‰คM2jfalse(F)+rstrue(F),sfalse(P)โ‰ค16sfalse(F)+strue(F)+3jtrue(F),jfalse(P)โ‰ค16sfalse(F)+3jtrue(F).\begin{aligned} s_{\mathrm{true}}(P) &\le M^2s_{\mathrm{false}}(F)+r s_{\mathrm{true}}(F),\\ j_{\mathrm{true}}(P) &\le M^2j_{\mathrm{false}}(F)+r s_{\mathrm{true}}(F),\\ s_{\mathrm{false}}(P) &\le16s_{\mathrm{false}}(F)+s_{\mathrm{true}}(F) +3j_{\mathrm{true}}(F),\\ j_{\mathrm{false}}(P) &\le16s_{\mathrm{false}}(F)+3j_{\mathrm{true}}(F). \end{aligned}(10)โœฆ For a base collection โ„ฌ\mathcal B with B(D)B^{(D)} nested and an integer depth 0โ‰คโ„“<D0\le\ell<D, the tower profiles satisfy (11): Sโ„“+1,trueโ‰คM2Sโ„“,false+rSโ„“,true,Jโ„“+1,trueโ‰คM2Jโ„“,false+rSโ„“,true,Sโ„“+1,falseโ‰ค16Sโ„“,false+Sโ„“,true+3Jโ„“,true,Jโ„“+1,falseโ‰ค16Sโ„“,false+3Jโ„“,true.\begin{aligned} S_{\ell+1,\mathrm{true}} &\le M^2 S_{\ell,\mathrm{false}}+r S_{\ell,\mathrm{true}},\\ J_{\ell+1,\mathrm{true}} &\le M^2 J_{\ell,\mathrm{false}}+r S_{\ell,\mathrm{true}},\\ S_{\ell+1,\mathrm{false}} &\le16S_{\ell,\mathrm{false}}+S_{\ell,\mathrm{true}} +3J_{\ell,\mathrm{true}},\\ J_{\ell+1,\mathrm{false}} &\le16S_{\ell,\mathrm{false}}+3J_{\ell,\mathrm{true}}. \end{aligned}(11)โœฆ

In the paper, the result reads: for dโ‰ฅ1d\ge1 and Mโ‰ฅ3M\ge3, fix the regular tournament and labeling of Sectionย 2, take r=โŒˆMโŒ‰r=\lceil\sqrt M\rceil and t=16t=16, and for 1โ‰คโ„“โ‰คd1\le\ell\le d write Sbโ€ฒ=Sโ„“โˆ’1,bS'_b=S_{\ell-1,b} and Jbโ€ฒ=Jโ„“โˆ’1,bJ'_b=J_{\ell-1,b}; the four bounds are (12): Sโ„“,trueโ‰คM2Sfalseโ€ฒ+rStrueโ€ฒ,Jโ„“,trueโ‰คM2Jfalseโ€ฒ+rStrueโ€ฒ,Sโ„“,falseโ‰คtSfalseโ€ฒ+Strueโ€ฒ+3Jtrueโ€ฒ,Jโ„“,falseโ‰คtSfalseโ€ฒ+3Jtrueโ€ฒ.\begin{aligned} S_{\ell,\mathrm{true}}&\le M^2 S'_{\mathrm{false}}+rS'_{\mathrm{true}},\\ J_{\ell,\mathrm{true}}&\le M^2 J'_{\mathrm{false}}+rS'_{\mathrm{true}},\\ S_{\ell,\mathrm{false}}&\le tS'_{\mathrm{false}}+S'_{\mathrm{true}} +3J'_{\mathrm{true}},\\ J_{\ell,\mathrm{false}}&\le tS'_{\mathrm{false}}+3J'_{\mathrm{true}}. \end{aligned}(12)

What Is Checked

The recursive statement concerns nested Boolean families on finite coordinate sets, regular tournaments and good labelings; the tower statement concerns a base collection whose DD-predicate family is nested, at depths below DD.