Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Classical separation exponent at least 2

Proved
SensitivityCampaign.classical

by marwahaha · Oct 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

block-sensitivityboolean-functionssensitivity

For every real ε > 0 and integer S ≥ 2, there exist n and a total Boolean function f on n bits such that s(f) ≥ S and bs(f) ≥ s(f)^(2−ε).

Preamble
import Mathlib
import Definitions.Def_SensitivityCampaign
Formal statement
namespace SensitivityCampaign
theorem classical : AchievesExponent (2 : ℝ) := by sorry
end SensitivityCampaign
Source
David Rubinstein, Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (1995), 297–299, https://doi.org/10.1007/BF01200762; Theorem 1 recalled in https://arxiv.org/abs/1008.0521
Read-back

What the Lean code literally says, in plain math · GPT-6 (independent blind auditor; exact runtime identifier unavailable)

For every real number ε>0\varepsilon>0ε>0 and every natural number S≥2S\ge 2S≥2, there exist a natural number nnn and a Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} satisfying S≤s(f)S\le s(f)S≤s(f) and s(f) 2−ε≤b(f)s(f)^{\,2-\varepsilon}\le b(f)s(f)2−ε≤b(f), where the exponentiation and this latter comparison are in the real numbers, after viewing the natural numbers s(f)s(f)s(f) and b(f)b(f)b(f) as real numbers. Here, for an input xxx and a set BBB of coordinate indices, xBx^BxB complements exactly the coordinates in BBB; s(f)s(f)s(f) is the maximum over all inputs xxx of the number of indices iii with f(x{i})≠f(x)f(x^{\{i\}})\ne f(x)f(x{i})=f(x); and b(f)b(f)b(f) is the maximum over all inputs xxx of the largest cardinality of a family of distinct, pairwise disjoint, nonempty sets BBB for which f(xB)≠f(x)f(x^B)\ne f(x)f(xB)=f(x) for every member. The empty family is permitted and contributes zero. The two maxima need not be attained at the same input. The witnesses nnn and fff may depend on both ε\varepsilonε and SSS; no single function or fixed dimension is required to work for all choices. The quantified dimension formally includes n=0n=0n=0, but that dimension has sensitivity zero and cannot satisfy S≤s(f)S\le s(f)S≤s(f) when S≥2S\ge2S≥2; in fact any witness has n≥Sn\ge Sn≥S. There is no upper bound on ε\varepsilonε: ε=2\varepsilon=2ε=2 and ε>2\varepsilon>2ε>2 are included, producing respectively zero and negative exponents, while ε=0\varepsilon=0ε=0 is excluded. Since a witness has s(f)≥2s(f)\ge2s(f)≥2, the base of the real power is positive. The statement requires the inequality for every positive ε\varepsilonε separately and does not assert s(f)2≤b(f)s(f)^2\le b(f)s(f)2≤b(f) for any witness.

Human review
  • Endorsed by Shuze Chen · Oct 16, 2026

    Confirmed by the moderator at approval.

  • Endorsed by marwahaha · Oct 16, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me