1 · The essentials
Imagine a rule that takes a list of zeros and ones and returns either zero or one. One way to measure how easily its answer changes is to count which single entries can change the answer when flipped. Another way allows groups of entries to flip together, with no entry belonging to more than one group. The manuscript constructs rules for which the second measure becomes much larger than the square of the first. More precisely, the second measure can grow beyond any fixed multiple of that square. This contradicts the proposed square-based bound, called the quadratic strengthening of the Sensitivity Conjecture. The main result has a Lean formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine a panel of switches controlling a light: you can test either individual switches or separate groups of switches flipped together. The result concerns rules where many separate groups can change the light’s state, even though the number of effective single-switch changes is much smaller by the comparison described above.
Why it matters
Sensitivity and block sensitivity compare the effect of changing individual inputs with the effect of changing disjoint groups of inputs. This construction rules out a proposed universal bound relating them: block sensitivity cannot always be bounded by a fixed constant times sensitivity squared. The conclusion concerns that quadratic strengthening, not a rejection of every possible relationship between the two measures.
2 · Going further
The setting is nonconstant total Boolean functions: rules defined on every binary input of their given length, with outputs that are not all the same. Sensitivity measures influential single-bit flips, whereas block sensitivity allows disjoint groups of bits to flip together. The quadratic strengthening would bound by a fixed constant multiple of for all such functions.
The main manuscript constructs examples with unbounded block sensitivity and, for some fixed , the inequality . Its abstract also explicitly states that block sensitivity grows faster than any constant multiple of sensitivity squared. The argument is therefore constructive in the sense that it supplies a family of functions violating the proposed bound, but the supplied abstract does not describe the construction or its internal steps. The main result has a Lean formalization; no companion manuscripts or further details of the formalization’s scope are supplied.
Useful notions
- Binary inputs and outputs
- Flipping an input bit
- Disjoint groups of inputs
- Comparing growth rates
- Squares and powers
What was known before / what is new
Before
The source identifies a proposed quadratic strengthening of the Sensitivity Conjecture as the target of the result. That proposal would limit block sensitivity by a constant multiple of sensitivity squared. The supplied text gives no further account of earlier results or historical development.
New
The manuscript constructs nonconstant total Boolean functions whose block sensitivity exceeds any fixed constant multiple of sensitivity squared across the family. More specifically, the examples have unbounded block sensitivity and satisfy for a fixed exponent . The main result has a Lean formalization.
Limits and assumptions
The result is an existence statement about a constructed family of nonconstant total Boolean functions, not a claim that every Boolean function exhibits this separation. The source does not specify the value of the fixed exponent beyond , nor does it give construction details. It identifies the main result as Lean-formalized but does not provide a finer breakdown of the formalization’s coverage. The quadratic strengthening is ruled out; the supplied text does not identify which further questions remain open.
Mini glossary
- Total Boolean function —
- A rule that assigns a binary output to every binary input of its given length.
- Nonconstant —
- Having outputs that are not all the same.
- Sensitivity —
- A measure counting influential individual-bit flips that change a function’s output.
- Block sensitivity —
- A measure allowing disjoint groups of input bits to be flipped together to change a function’s output.
- Quadratic strengthening —
- The proposed bound that block sensitivity is always at most a fixed constant multiple of sensitivity squared.
- Superquadratic separation —
- A gap in which block sensitivity grows beyond every fixed constant multiple of sensitivity squared.
Keywords : Sensitivity · Block sensitivity · Boolean functions
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Constructs total Boolean functions with block sensitivity for a fixed α > 2, disproving the quadratic strengthening of the Sensitivity Conjecture. Here counts influential individual-bit flips, while block sensitivity allows disjoint groups of bits to change together.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
A superquadratic separation between sensitivity and block sensitivity
25/09/2026We disprove the quadratic strengthening of the Sensitivity Conjecture by constructing nonconstant total Boolean functions whose block sensitivity grows faster than any constant multiple of sensitivity squared. In fact, for some fixed α > 2, our examples have unbounded block sensitivity and satisfy .