A superquadratic sensitivity separation

Source and verification

This article explains family 132 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Sensitivity at a vertex of the cube

For $x\in \{0,1{\}}^n$ and $B\subseteq [n]$, let $x^B$ be obtained by flipping the coordinates in $B$. For a total Boolean function $f$, its sensitivity at $x$ is

$$\begin{array}{c}s(f,x)=|\{i:f(x^{\{i\}})\ne f(x)\}|,\\ s(f)=\underset{x}{\max }s(f,x).\end{array}$$

Its block sensitivity $\mathrm{bs}(f,x)$ is the largest number of pairwise disjoint nonempty blocks $B_1,\dots ,B_m$ such that every individual block flip changes the output at $x$. Put $\mathrm{bs}(f)={\max }_x\mathrm{bs}(f,x)$. The blocks need not be singletons, but they must be disjoint. Since singleton blocks are allowed, $s(f)\le \mathrm{bs}(f)$.

For example, if $f$ is OR on $n$ bits, both measures equal $n$ at the zero input. To separate them, many larger blocks must change the output while every input has few sensitive individual bits. Controlling only the zero input does not bound $s(f)$.

These are maximum-over-input quantities. They differ from the uniform average sensitivity studied in polynomial threshold sensitivity, and from the operator norm of the sensitivity graph’s adjacency matrix.

🏷️ The quadratic strengthening

The original Sensitivity Conjecture asked for a polynomial bound of block sensitivity in sensitivity. Huang’s theorem, combined with the degree–block-sensitivity comparison described in the manuscript, gives the quartic upper bound $\mathrm{bs}(f)\le s(f{)}^4$. The present family concerns the stronger proposed quadratic bound. (OpenAI, 2026)

Source separation theorem

For every integer $d\ge 1$, the manuscript constructs a nonconstant total Boolean function with

$$\frac{\mathrm{bs}(f)}{s(f{)}^2}\ge \frac{2^d}{4(d+2{)}^2}.$$

Consequently no constant $C$ can make $\mathrm{bs}(f)\le Cs(f{)}^2$ hold for every total Boolean function. A fixed seed also yields a fixed exponent $\alpha >2$ and functions $F_m$ with

$$\begin{array}{c}\mathrm{bs}(F_m,0)\ge s(F_m{)}^{\alpha },\\ \mathrm{bs}(F_m,0)\to \infty .\end{array}$$

These statements are compatible with a universal quartic upper bound. (OpenAI, 2026)

The proof uses finite combinatorics, a probabilistic existence argument for labels, and recursive predicates. The label argument does not provide a claim of efficient construction at practical dimensions. We develop the recurrences because they explain how the example controls ordinary sensitivity rather than only a spectral surrogate.

🏷️ A labeled tournament

Fix depth $d\ge 1$ and a size parameter $M\ge 3$, chosen larger below. Set

$$\begin{array}{c}L=d+2,k=2M^2+1,\\ r=\lceil \sqrt{M}\rceil .\end{array}$$

A tournament directs exactly one edge between every pair of distinct vertices. Choose a regular tournament on $k$ vertices, with $M^2$ outgoing edges at every vertex; a cyclic orientation supplies one. Label every edge $i\to j$ by $a(i,j)\in [r]$, interpreted as a selected position in row $j$.

The labels are chosen to exclude the following pattern: a set $I$ of $16$ rows and positions $m_j\in [r]$ such that every internal edge entering $j$ has label $m_j$.

Choose all labels independently and uniformly. For fixed $I$ and fixed positions, the probability of that pattern is $r^{-\left(\genfrac{}{}{0ex}{}{16}{2}\right)}$. A union bound over at most $k^{16}{r}^{16}$ choices gives

$$\begin{array}{rl}\mathrm{Pr}(\text{a violation})& \le k^{16}{r}^{-104}\\ & \le 3^{16}{M}^{-20}<1.\end{array}$$

Thus a suitable finite labeling exists. Its role is to bound how many clauses can simultaneously be one target condition away from acceptance. (OpenAI, 2026)

🏷️ Nested predicates and disjoint blocks

At level $\ell$, construct predicates $P_{\ell ,q}$ for $1\le q\le H_{\ell }=d+1-\ell$, with

$$P_{\ell ,1}(x)\ge \cdots \ge P_{\ell ,H_{\ell }}(x).$$

This nesting concerns the predicate index. It does not assert monotonicity in the input bits.

For the initial level, partition $LM$ coordinates into $M$ disjoint blocks $E_j$ of size $L$. Let $z_j$ be the indicator vector of $E_j$, and put

$$\begin{array}{c}D(x)=\underset{j}{\min }\mathrm{dist}(x,z_j),\\ P_{0,q}(x)=1\{D(x)\le d+1-q\}.\end{array}$$

These predicates are unions of Hamming balls with integer radii from $d$ to zero. The centers are distance $2L=2d+4$ apart. All predicates vanish at zero, while flipping any $E_j$ makes every one of them accept.

At level $\ell \ge 1$, arrange $kr$ disjoint child inputs into $k$ rows with $r$ children each. Write $Q=H_{\ell -1}=H_{\ell }+1$. Clause $i$ for parent predicate $q$ requires

$$\begin{array}{c}{P}_{\ell -1,Q}(x_{i,c})=1(c\in [r]),\\ P_{\ell -1,Q-q}(x_{j,a(i,j)})=0(i\to j).\end{array}$$

The first requirements are targets in row $i$; the second are gates in other rows. The parent accepts if any clause holds. Increasing $q$ strengthens its zero-valued gate conditions, so the parent predicates remain nested. Within one clause, all conditions involve different children. Therefore one raw input-bit flip affects at most one condition of that clause, although it may affect several clauses.

At every level there are $M{k}^{\ell }$ pairwise disjoint blocks, each of size $L{r}^{\ell }$, that make all predicates accept when flipped at zero. Indeed, take one preceding-level block and copy it into every child of one row. Flipping their union satisfies every target of that row; all gate children lie in untouched rows and remain zero. Different rows or different preceding blocks give disjoint unions. The number of blocks is multiplied by $k$ at each level, while their size is multiplied by $r$.

The number of input bits at level $\ell$ is $LM(kr{)}^{\ell }$, so the claimed blocks fit exactly within the stated finite input space.

🏷️ Ordinary and joint sensitivity profiles

Let $S_{\ell ,b}$ be the largest number of sensitive bits over all level-$\ell$ predicates and all inputs at which that predicate equals $b$. The recursion needs a second quantity. Let $J_{\ell ,b}$ be the largest number of bits that simultaneously change two fixed distinct level-$\ell$ predicates from the common value $b$ to $1-b$, at the same input. A maximum over no pairs is zero.

At level zero,

$$\begin{array}{c}{S}_{0,0}\le L,S_{0,1}\le LM,\\ J_{0,0}=J_{0,1}=0.\end{array}$$

For the first bound, a rejecting input that can enter a ball by one flip is within distance $d+1$ of its center. There cannot be two such centers because their mutual distance is $2d+4$. All successful flips move toward the same center, yielding at most $d+1\le L$ possibilities. The accepting-side bound is the total number of bits.

For joint sensitivity, the distance function $D$ changes by at most one under one bit flip. Crossing two different integer radii in the same direction would require a change of at least two. Thus the joint profiles vanish initially.

Suppressing the preceding level in $S_b^{\prime },J_b^{\prime }$, the manuscript proves

$$\begin{array}{rl}{S}_{\ell ,1}& \le M^2{S}_0^{\prime }+r{S}_1^{\prime },\\ J_{\ell ,1}& \le M^2{J}_0^{\prime }+r{S}_1^{\prime },\\ S_{\ell ,0}& \le 16S_0^{\prime }+S_1^{\prime }+3J_1^{\prime },\\ J_{\ell ,0}& \le 16S_0^{\prime }+3J_1^{\prime }.\end{array}$$

The accepting-side inequalities follow by fixing one satisfied clause. Any output-changing flip must break a target or a gate. There are $r$ targets and $M^2$ gates. For two accepting parent predicates, fix a clause satisfying the stronger one. Breaking a gate even for the weaker parent forces two distinct child gate predicates to change together, explaining $J_0^{\prime }$.

At a rejecting input, candidate clauses must initially fail exactly one condition. Split them into clauses failing a target and clauses failing a gate.

For a target-failing clause $j$, denote the unique failed position by $m_j$. If two such clauses satisfy $i\to j$, the passing gate of clause $i$ forces the strongest predicate to vanish at position $a(i,j)$ in row $j$. That position must be the unique failed target, so $a(i,j)=m_j$. The forbidden-label property therefore permits fewer than $16$ target candidates. They contribute at most $16S_0^{\prime }$ possible repairs.

For gate-failing candidates, every target in their own rows already accepts. An internal tournament edge produces a failed gate in its source clause, so each candidate has internal outdegree at most one. If there are $m$ candidates,

$$\frac{m(m-1)}{2}\le m,$$

and hence $m\le 3$. At most one has internal outdegree zero. Every other candidate’s failed gate lies in a row whose strongest predicate accepts. Repairing it must change both that strongest predicate and the weaker gate predicate from one to zero. These repairs cost $J_1^{\prime }$ each. The possible exceptional clause costs $S_1^{\prime }$, giving the third recurrence.

For a flip that makes two rejecting parent predicates accept simultaneously, even the exceptional gate must cross two distinct child thresholds: the two parent indices supply them. The $S_1^{\prime }$ term disappears, giving the fourth recurrence. This is the reason for carrying joint profiles through the recursion; replacing all joint bounds by ordinary sensitivity would lose the separation. (OpenAI, 2026)

🏷️ Normalization and the quantitative ratio

Choose $M\ge 9^{d+1}$. Normalize the profiles by their expected scale:

$$\begin{array}{c}{u}_{\ell }=\underset{b=0,1}{\max }\frac{S_{\ell ,b}}{M^{\ell +b}},\\ v_{\ell }=\underset{b=0,1}{\max }\frac{J_{\ell ,b}}{M^{\ell +b}},\\ \epsilon =\frac{\max (r,16)}{M}\le \frac{2}{3^{d+1}}.\end{array}$$

The four inequalities reduce to

$$\begin{array}{rl}{u}_{\ell }& \le (1+\epsilon )u_{\ell -1}+3v_{\ell -1},\\ v_{\ell }& \le \epsilon u_{\ell -1}+3v_{\ell -1},\end{array}$$

with $u_0\le L$ and $v_0=0$. For comparison sequences satisfying equality, induction gives $v_{\ell }\le \epsilon L(3^{\ell }-1)$. Summing the increments of the first sequence then gives

$$\begin{array}{rl}{u}_{\ell }& \le L+\epsilon L\left[\frac{3}{2}(3^{\ell }-1)-\ell \right]\\ & <2L(\ell \le d).\end{array}$$

The choice of $\epsilon$ controls the accumulated factor $3^{\ell }$, not only a single recursion step. Thus

$$S_{\ell ,b}\le 2L{M}^{\ell +b}.$$

Finally take $f$ to be the OR of $M$ disjoint copies of $P_{d,1}$. At a rejecting input all copies reject, giving at most $M{S}_{d,0}$ sensitive bits. At an accepting input, either two copies accept and no single flip changes the OR, or only one copy accepts and there are at most $S_{d,1}$ sensitive bits. Hence

$$s(f)\le 2L{M}^{d+1}.$$

The disjoint zero-input blocks from the $M$ copies give

$$\mathrm{bs}(f,0)\ge M^2{k}^d.$$

Since $f$ is nonconstant, its sensitivity is positive, and

$$\begin{array}{rl}\frac{\mathrm{bs}(f)}{s(f{)}^2}& \ge \frac{(k/M^2{)}^d}{4L^2}\\ & \ge \frac{2^d}{4(d+2{)}^2}.\end{array}$$

The constructed dimension is $n=L{M}^2(kr{)}^d$. To defeat a proposed quadratic constant, choose $d$ first, then $M$, then the finite labeling. This order of choices ensures that the function is a definite finite total Boolean function. (OpenAI, 2026)

🏷️ Composition gives a fixed power

For disjoint composition $f\circ g$, a raw input bit can change the output only if it changes its child value and that child’s coordinate is sensitive for $f$. Therefore

$$s(f\circ g)\le s(f)s(g).$$

If $g(0)=0$, disjoint zero-input sensitive blocks $C_i$ of $f$ and $D_j$ of $g$ produce disjoint blocks $C_i\times D_j$ of the composition. Flipping such a product changes exactly the child outputs indexed by $C_i$. Consequently

$$\mathrm{bs}(f\circ g,0)\ge \mathrm{bs}(f,0)\mathrm{bs}(g,0).$$

Fix $d=9$, so $L=11$, and choose $M\ge 9^{10}$. The seed bounds are

$$\begin{array}{c}A=22M^{10}\ge s(f),\\ B=M^2{k}^9\le \mathrm{bs}(f,0).\end{array}$$

They satisfy $B/A^2\ge 128/121>1$. Iterating this one fixed seed gives $s(F_m)\le A^m$ and $\mathrm{bs}(F_m,0)\ge B^m$. With

$$\alpha =\frac{\log B}{\log A}>2,$$

we obtain $s(F_m{)}^{\alpha }\le B^m\le \mathrm{bs}(F_m,0)$. A fixed superquadratic exponent follows from one sufficiently strong finite seed; its excess above two need not be large.

🏷️ Key steps and proof outlines

Fixing the candidate set before choosing a flip

The sensitivity recurrences above depend on a quantifier distinction worth making explicit. At a rejecting input, the lists $\mathcal{T}$ and $\mathcal{G}$ of clauses with one failed target or one failed gate are fixed before the flipped coordinate is chosen. A clause that becomes true must belong to one of these lists: a bit lies in just one child input, and the conditions of any fixed clause concern distinct children. Thus one flip cannot repair two failed conditions of the same clause.

The final accepting witness is allowed to vary with the flip. The proof takes a union over the fixed initial lists, which bounds all such choices at once. It does not select one eventual accepting clause and use it for every flip. Conversely, at an accepting input one can fix an initially satisfied clause, because every flip changing the parent to zero must destroy that same clause. These two different witness choices explain the asymmetry between the zero-side and one-side recurrences in “Sensitivity recurrences.” (OpenAI, 2026)

The second threshold removes the expensive exception

Fix distinct parent indices $q<q^{\prime }$ and put $g=Q-q$, $g^{\prime }=Q-q^{\prime }$, so $g^{\prime }<g<Q$. Suppose both parents initially reject and a flip makes the stronger parent $q^{\prime }$ accept. Its witnessing clause also becomes true for $q$ and lies in the weaker parent’s initial candidate lists.

If the witness was gate-defective, its unique failed gate initially has $P_g=1$. Nesting forces $P_{g^{\prime }}=1$ there as well. After the flip, satisfying the stronger clause requires $P_{g^{\prime }}=0$, which forces $P_g=0$. Both fixed child predicates therefore change on the same raw coordinate. This costs $J_1^{\prime }$, including for the exceptional gate-defective clause that has no outgoing edge within $\mathcal{G}$.

For ordinary sensitivity that exceptional clause costs $S_1^{\prime }$, because no other candidate row forces its strongest child predicate to accept. For joint sensitivity, the second parent index supplies the second child threshold without needing that row information. This is the precise reason the recurrence for $J_{\ell ,0}$ omits $S_1^{\prime }$. It remains valid even when a bit can cross many thresholds inside a recursive child: the proof asks that two particular thresholds cross, not that at most one can cross.

The recursive invariant tracks simultaneous transitions.

Ordinary sensitivity alone does not close the useful bound. The auxiliary joint profile begins at zero and is generated only through a small normalized forcing term. The nesting of the predicates lets the parent argument recover that stronger information at every depth.

Why the error parameter must depend on depth

The normalized bounds have a dominant ordinary profile $u_{\ell }$ and a smaller joint profile $v_{\ell }$. Their comparison equations can be written

$$\left(\genfrac{}{}{0ex}{}{u_{\ell }}{v_{\ell }}\right)\le \left(\begin{array}{cc}1+\epsilon & 3\\ \epsilon & 3\end{array}\right)\left(\genfrac{}{}{0ex}{}{u_{\ell -1}}{v_{\ell -1}}\right).$$

The entry $3$ permits accumulated joint error to grow geometrically. Choosing merely a small fixed $\epsilon$ would therefore fail as $d$ increases. Under the induction $u_{\ell -1}\le 2L$, the second row gives

$$v_{\ell }\le 2\epsilon L\sum _{j=0}^{\ell -1}{3}^j=\epsilon L(3^{\ell }-1).$$

Substitution into the first row and summation yields the displayed bound for $u_{\ell }$. The choice $\epsilon \le 2/3^{d+1}$ makes the bound less than $2L$ through the entire prescribed depth, closing the induction. The large value of $M$ is thus used to control an accumulated error, while the tournament supplies the factor $k\approx 2M^2$ in the block count. After the final OR balances accepting and rejecting sensitivity, that extra factor two survives as $2^d$ in the ratio.

Finally, composition requires the seed’s zero input to remain rejecting. This ensures that flipping a product block changes exactly the intended child outputs and gives multiplicative block sensitivity at zero. General maximum block sensitivity without a common rejecting basepoint would not justify that product-block argument. The constructed seed supplies this compatibility explicitly, and its fixed ratio $B>A^2$ converts into the exponent $\alpha =\log B/\log A>2$.

🏷️ Reading connections

Huang’s sensitivity theorem addresses the polynomial upper-bound question. This family rules out its quadratic strengthening while remaining consistent with that theorem. Polynomial threshold sensitivity studies uniform average sensitivity under a threshold-degree constraint; neither its averaging convention nor its degree parameter should be substituted for the maximum sensitivity used here.

🏷️ Manuscripts and verification scope

• A superquadratic separation between sensitivity and block sensitivity — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. It describes both the unbounded quadratic ratio and the fixed exponent obtained by composition. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A superquadratic separation between sensitivity and block sensitivity.