Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
Active

Block Sensitivity vs. Sensitivity

How much larger can block sensitivity be than sensitivity for a total Boolean function?

For a total Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1}, a block of coordinates is sensitive at xxx if flipping every bit in that block changes f(x)f(x)f(x). Let s(f,x)s(f,x)s(f,x) count sensitive singletons and bs(f,x)bs(f,x)bs(f,x) be the maximum number of pairwise disjoint sensitive blocks. Define s(f)=max⁡xs(f,x)s(f)=\max_x s(f,x)s(f)=maxx​s(f,x) and bs(f)=max⁡xbs(f,x)bs(f)=\max_x bs(f,x)bs(f)=maxx​bs(f,x).

This campaign seeks larger exponents α\alphaα for which there exists an infinite family of total Boolean functions fk:{0,1}nk→{0,1}f_k:\{0,1\}^{n_k}\to\{0,1\}fk​:{0,1}nk​→{0,1}, indexed by k=1,2,…k=1,2,\ldotsk=1,2,…, satisfying

s(fk)→∞,bs(fk)≥s(fk)α−o(1)as k→∞.s(f_k)\to\infty,\qquad bs(f_k)\ge s(f_k)^{\alpha-o(1)}\quad\text{as }k\to\infty.s(fk​)→∞,bs(fk​)≥s(fk​)α−o(1)as k→∞.

Here o(1)o(1)o(1) denotes a quantity tending to zero as k→∞k\to\inftyk→∞. Higher is better. The classical exponent is 222, and Huang's bound gives a ceiling of 444.

OpenAI's construction achieves an exponent strictly greater than 222.

One sufficient way to establish an exponent α\alphaα is to find a single total Boolean function fff with s(f)>1s(f)>1s(f)>1 and bs(f)≥s(f)αbs(f)\ge s(f)^\alphabs(f)≥s(f)α. Input and output normalization followed by self-composition then yields the required asymptotic family.

Submit an entryLog in to start a draft.

Progress

23 missions
Best formalized bound≥ 2.13981

Block Sensitivity vs. Sensitivity: Reach $2.13981$Solved Oct 27, 2026

Formalized missions form a staircase from the weakest to the best value, one slot per mission at uniform spacing. A date in parentheses is later than the date of a better result. Open missions follow the history as unconnected circles labeled Today, ordered from less to more ambitious values. Select a point to highlight its mission on this page. Showing Oct 20 to Today, 12 of 23 missions. Press plus or minus to zoom the timeline, zero to show the full history, and the arrow keys to move along it while zoomed.Lower bound2.122.132.142.15(Oct 20)Oct 20Oct 20(Oct 27)(Oct 27)TodayBlock Sensitivity vs. Sensitivity: Periodic exponent $2.119$, ≥ 2.119, formalizedBlock Sensitivity vs. Sensitivity: Reach 2.127294, ≥ 2.127294, formalizedBlock Sensitivity vs. Sensitivity: Reach 2.13, ≥ 2.13, formalizedBlock Sensitivity vs. Sensitivity: Reach $2.1301$, ≥ 2.1301, formalizedBlock Sensitivity vs. Sensitivity: Reach $2.1303$, ≥ 2.1303, formalizedBlock Sensitivity vs. Sensitivity: Reach $2.1308255793978239\ldots$, ≥ 2.1308255793978239, formalizedBlock Sensitivity vs. Sensitivity: Reach $2.131121719190$, ≥ 2.131121719190, formalizedBlock Sensitivity vs. Sensitivity: Reach $2.131125302137$, ≥ 2.131125302137, formalizedBlock Sensitivity vs. Sensitivity: Reach $2.13303$, ≥ 2.13303, formalizedBlock Sensitivity vs. Sensitivity: Reach $2.13519$, ≥ 2.13519, formalizedBlock Sensitivity vs. Sensitivity: Reach $2.13981$, ≥ 2.13981, formalizedBlock Sensitivity vs. Sensitivity: Reach 2.15, ≥ 2.15, open mission
Formalized resultsOpen missions(Date) Formalized after a better resultCtrl + scroll to zoomPinch to zoom
Select a point to explore a mission

Missions

Open1

Completed22

Top contributors

RankContributorAccepted solutionsSubmitted problems
1MAmarwahaha5179
2YOyousofy3733
3SCShuze Chen31118
4DMdmilosch1018
5LSLeo Shaposhnik812
6RGrgmohan613
7FIfizzyinc350
8AAAbhishek Anand33
9RKRobin Kothari22
10BW@bwdaugherty11

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me