OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1 [Superquadratic separation]: An exponential lower bound in the construction depth

Block sensitivity outgrows squared 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

The comparison between sensitivity and block sensitivity asks how a Boolean function’s response to single coordinate changes constrains its response to changes on disjoint blocks. Let II be a finite coordinate set and let 𝔹={false,true}\mathbb B=\{\mathrm{false},\mathrm{true}\}. A total Boolean function on II is a function f:𝔹I→𝔹f:\mathbb B^I\to\mathbb B, defined at every input. A total Boolean function f:𝔹I→𝔹f:\mathbb B^I\to\mathbb B is nonconstant if it takes different values at two inputs.

For an input x∈𝔹Ix\in\mathbb B^I and a block B⊆IB\subseteq I, the block flip xB∈𝔹Ix^B\in\mathbb B^I is the input obtained by complementing exactly the coordinates in BB, as in (1); here b¯\overline b denotes the complement of a Boolean value bb. (xB)i={xi¯,i∈B,xi,i∉B.(x^B)_i= \begin{cases} \overline{x_i},&i\in B,\\ x_i,&i\notin B. \end{cases}(1)✦

The pointwise sensitivity s(f,x)s(f,x) of ff at xx is the number of coordinates whose individual flips change its value, and the sensitivity s(f)s(f) of ff is the maximum of this number over inputs, as in (2). s(f,x)=|{i∈I:f(x{i})≠f(x)}|,s(f)=maxx∈𝔹Is(f,x).s(f,x)=\bigl|\{i\in I:f(x^{\{i\}})\ne f(x)\}\bigr|, \qquad s(f)=\max_{x\in\mathbb B^I}s(f,x).(2)

The pointwise block sensitivity bs(f,x)\mathrm{bs}(f,x) of ff at xx is the largest number of pairwise disjoint nonempty blocks whose flips each change its value; the block sensitivity bs(f)\mathrm{bs}(f) of ff is its maximum over inputs, as in (3). bs(f,x)=maxℱ⊆2Ipairwise disjoint∀B∈ℱ,B≠⌀,f(xB)≠f(x)|ℱ|,bs(f)=maxx∈𝔹Ibs(f,x).\begin{aligned} \mathrm{bs}(f,x) &=\max_{\substack{ \mathcal F\subseteq 2^I\ \text{pairwise disjoint}\\ \forall B\in\mathcal F,\ B\ne\varnothing,\ f(x^B)\ne f(x) }}|\mathcal F|,\\ \mathrm{bs}(f)&=\max_{x\in\mathbb B^I}\mathrm{bs}(f,x). \end{aligned}(3)

For a positive integer nn, write [n]={0,…,n−1}[n]=\{0,\ldots,n-1\} for its coordinate set and 𝒇𝒂𝒍𝒔𝒆∈𝔹[n]\mathbf{false}\in\mathbb B^{[n]} for the all-false input.

The Claim

Theorem 1. For every real C>0C>0, there exist a positive integer nn and a nonconstant total Boolean function f:𝔹[n]→𝔹f:\mathbb B^{[n]}\to\mathbb B with f(𝒇𝒂𝒍𝒔𝒆)=falsef(\mathbf{false})=\mathrm{false} such that Cs(f)2<bs(f).C\,s(f)^2<\mathrm{bs}(f).(4)✦ For every integer d≥1d\ge1, there exist a positive integer nn and a nonconstant total Boolean function f:𝔹[n]→𝔹f:\mathbb B^{[n]}\to\mathbb B with f(𝒇𝒂𝒍𝒔𝒆)=falsef(\mathbf{false})=\mathrm{false} such that 2d4(d+2)2≤bs(f)s(f)2.\frac{2^d}{4(d+2)^2}\le\frac{\mathrm{bs}(f)}{s(f)^2}.(5)✦

In the paper, the result reads: for every real C>0C>0, there are a positive integer nn and a nonconstant total Boolean function f:𝔹[n]→𝔹f:\mathbb B^{[n]}\to\mathbb B such that bs(f)>Cs(f)2\mathrm{bs}(f)>C\,s(f)^2, and, more precisely, for every integer d≥1d\ge1, the construction gives a nonconstant total Boolean function ff with bs(f)/s(f)2≥2d/(4(d+2)2)\mathrm{bs}(f)/s(f)^2\ge2^d/(4(d+2)^2).

What Is Checked

The claims (4) and (5) concern nonconstant total Boolean functions on a positive number of coordinates whose value at the all-false input is false\mathrm{false}.