OctoInformBeta

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

Lemma 4.2 [Sensitivity and zero-input blocks under composition]: Cartesian products of sensitive blocks are sensitive at zero when the inner function is false at zero

Sensitivity is submultiplicative under block composition.

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 sensitivity and block sensitivity behave when one Boolean function is substituted into every coordinate of another. Let II and JJ be finite coordinate sets, and let 𝔹={false,true}\mathbb B=\{\mathrm{false},\mathrm{true}\}. Take total Boolean functions f:𝔹I→𝔹f:\mathbb B^I\to\mathbb B and g:𝔹J→𝔹g:\mathbb B^J\to\mathbb B.

The block composition F=f∘gF=f\circ g is the Boolean function on I×JI\times J that applies gg to each row and ff to the resulting input.✦ For x∈𝔹I×Jx\in\mathbb B^{I\times J}, write xix_i for its row indexed by ii and y(x)y(x) for the input to ff, as in (1). xi(j)=x(i,j),y(x)(i)=g(xi),F(x)=f(y(x)).x_i(j)=x(i,j),\qquad y(x)(i)=g(x_i),\qquad F(x)=f(y(x)).(1)✦

For a finite coordinate set UU, an input z∈𝔹Uz\in\mathbb B^U, and a block B⊆UB\subseteq U, the block flip zBz^B is the input given by (2), where ¬\neg interchanges false\mathrm{false} and true\mathrm{true}. Write 𝟎U\mathbf{0}_U, or 𝟎\mathbf{0} when the coordinates are understood, for the input that is false at every coordinate of UU. zB(u)={¬z(u),u∈B,z(u),u∉B.z^B(u)= \begin{cases} \neg z(u),&u\in B,\\ z(u),&u\notin B. \end{cases}(2)✦

Let h:𝔹U→𝔹h:\mathbb B^U\to\mathbb B be a Boolean function. The pointwise sensitivity s(h,z)s(h,z) of hh at zz is the number of coordinates whose singleton flip changes the value of hh✦; the sensitivity s(h)s(h) is its maximum over all inputs, as in (3).✦ s(h,z)=|{u∈U:h(z{u})≠h(z)}|,s(h)=maxz∈𝔹Us(h,z).s(h,z)=\bigl|\{u\in U:h(z^{\{u\}})\ne h(z)\}\bigr|, \qquad s(h)=\max_{z\in\mathbb B^U}s(h,z).(3)

A sensitive block BB for hh at zz is a nonempty subset of UU such that h(zB)≠h(z)h(z^B)\ne h(z). The pointwise block sensitivity bs(h,z)\mathrm{bs}(h,z) of hh at zz is the maximum cardinality of a family of pairwise disjoint sensitive blocks, as in (4); the empty family is allowed.✦ bs(h,z)=maxℬ⊆2UB≠⌀,h(zB)≠h(z)(B∈ℬ)B∩B′=⌀(B,B′∈ℬ,B≠B′)|ℬ|.\mathrm{bs}(h,z)= \max_{\substack{ \mathcal B\subseteq 2^U\\ B\ne\varnothing,\ h(z^B)\ne h(z)\ (B\in\mathcal B)\\ B\cap B'=\varnothing\ (B,B'\in\mathcal B,\ B\ne B') }}|\mathcal B|.(4)✦

The Claim

Theorem 1. Let f:𝔹I→𝔹f:\mathbb B^I\to\mathbb B and g:𝔹J→𝔹g:\mathbb B^J\to\mathbb B be total Boolean functions on finite coordinate sets, and put F=f∘gF=f\circ g. For every input x∈𝔹I×Jx\in\mathbb B^{I\times J}, (5) holds, and the maximum satisfies (6). s(F,x)=∑i∈If(y(x){i})≠f(y(x))s(g,xi).s(F,x)= \sum_{\substack{i\in I\\f(y(x)^{\{i\}})\ne f(y(x))}}s(g,x_i).(5)✦ s(F)≤s(f)s(g).s(F)\le s(f)s(g).(6)✦ Suppose that g(𝟎J)=falseg(\mathbf{0}_J)=\mathrm{false}. Then (7) and (8) hold. F(𝟎I×J)=f(𝟎I).F(\mathbf{0}_{I\times J})=f(\mathbf{0}_I).(7)✦ bs(f,𝟎I)bs(g,𝟎J)≤bs(F,𝟎I×J).\mathrm{bs}(f,\mathbf{0}_I)\mathrm{bs}(g,\mathbf{0}_J) \le\mathrm{bs}(F,\mathbf{0}_{I\times J}).(8)✦ For any index sets KK and HH, let (Ck)k∈K(C_k)_{k\in K} and (Dℓ)ℓ∈H(D_\ell)_{\ell\in H} be families of pairwise disjoint sensitive blocks for ff at 𝟎I\mathbf{0}_I and for gg at 𝟎J\mathbf{0}_J, respectively. The Cartesian blocks Pk,ℓ=Ck×DℓP_{k,\ell}=C_k\times D_\ell satisfy (9) for all indices in the indicated families. Pk,ℓ≠⌀,Pk,ℓ∩Pk′,ℓ′=⌀if (k,ℓ)≠(k′,ℓ′),F(𝟎I×JPk,ℓ)≠F(𝟎I×J).\begin{gathered} P_{k,\ell}\ne\varnothing,\\ P_{k,\ell}\cap P_{k',\ell'}=\varnothing \quad\text{if }(k,\ell)\ne(k',\ell'),\\ F\bigl(\mathbf{0}_{I\times J}^{P_{k,\ell}}\bigr) \ne F(\mathbf{0}_{I\times J}). \end{gathered}(9)✦ For finite KK and HH, (10) holds. |K||H|≤bs(F,𝟎I×J).|K|\,|H|\le\mathrm{bs}(F,\mathbf{0}_{I\times J}).(10)✦

In the paper, the result reads: for total Boolean functions ff on aa bits and gg on bb bits, s(f∘g)≤s(f)s(g)s(f\circ g)\le s(f)s(g), and if g(𝟎)=falseg(\mathbf{0})=\mathrm{false}, then (f∘g)(𝟎)=f(𝟎)(f\circ g)(\mathbf{0})=f(\mathbf{0}) and bs(f∘g,𝟎)≥bs(f,𝟎)bs(g,𝟎)\mathrm{bs}(f\circ g,\mathbf{0})\ge \mathrm{bs}(f,\mathbf{0})\mathrm{bs}(g,\mathbf{0}), with any families of pp and qq pairwise disjoint nonempty sensitive blocks at zero for ff and gg yielding pqpq such blocks for f∘gf\circ g.

What Is Checked

The statements concern total Boolean functions on finite coordinate sets; the zero-input claims assume g(𝟎J)=falseg(\mathbf{0}_J)=\mathrm{false}, and the Cartesian block claims concern indexed families of pairwise disjoint sensitive blocks, with finite index sets for (10).