VibeMathedMath problems solved with AI
Sign in

Is block sensitivity at most quadratic in sensitivity? (Nisan-Szegedy)

For a total Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}, the sensitivity s(f)s(f) is the largest number of single bits whose flip changes ff at some input, and the block sensitivity bs(f)\mathrm{bs}(f) the largest number of disjoint blocks of bits each of whose flip changes ff at some input. Nisan and Szegedy (1994) explicitly suggested bs(f)≤s(f)2\mathrm{bs}(f)\le s(f)^2. Rubinstein's functions give bs=s2/2\mathrm{bs}=s^2/2, improved to 23s2−13s\frac23s^2-\frac13s by Ambainis and Sun (2011); Huang's 2019 proof of the Sensitivity Conjecture gives bs(f)≤s(f)4\mathrm{bs}(f)\le s(f)^4. Is there a universal constant CC with bs(f)≤C s(f)2\mathrm{bs}(f)\le C\,s(f)^2 for every total Boolean function?

Result
Disproved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Boolean function complexity; sensitivity
Posed by
Noam Nisan and Mario Szegedy (Section 4, Computational Complexity 1994)
Year posed
1994
Years open
32y
Solved
2026-09-25
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
35 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: for every integer d≥1d\ge1 an explicit recursive construction gives a nonconstant total Boolean function with bs(f)/s(f)2≥2d/(4(d+2)2)\mathrm{bs}(f)/s(f)^2\ge2^d/(4(d+2)^2), so no bound bs≤Cs2\mathrm{bs}\le C s^2 holds; the abstract also claims a fixed α>2\alpha>2 with bs(f)≥s(f)α\mathrm{bs}(f)\ge s(f)^\alpha along an unbounded family. This does not close the gap to Huang's upper bound bs≤s4\mathrm{bs}\le s^4; the true exponent remains open.

What the AI did

The release README says every result in openai/math was produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not one of the README's two exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The manuscript adapts the gated-tournament architecture of Meiburg's 2026 spectral-sensitivity separation (arXiv 2608.00851), whose own attribution credits GPT-5.6-Sol with those ideas.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the quadratic question: for every CC some nonconstant total ff has bs(f)>C s(f)2\mathrm{bs}(f)>C\,s(f)^2, with bs/s2≥2d/(4(d+2)2)\mathrm{bs}/s^2\ge2^d/(4(d+2)^2) for each d≥1d\ge1. lean/formalization.yaml lists SensitivitySeparation.json (declaration OAI.Paper320.quantitative_separation, file OAI/Combinatorics/Sensitivity/Separation.lean). The statement SensitivitySeparation.lean was read here; not rebuilt here. It defines sensitivity and block sensitivity (disjoint nonempty blocks) as in the paper and states, for every d≥1d\ge1, a nonconstant ff on Fin n inputs with 2d/(4(d+2)2)≤bs(f)/s(f)22^d/(4(d+2)^2)\le\mathrm{bs}(f)/s(f)^2; the ratio is unbounded, so this states the headline disproof. The abstract's fixed exponent α>2\alpha>2 is not in this statement. Permitted axioms: propext, Quot.sound, Classical.choice.

Sources

Changelog1 change

Discussion