Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Separation exponent at least 2.05

Proved
SensitivityCampaign.reach_205

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

block-sensitivityboolean-functionssensitivity

For every real ε > 0 and every integer S ≥ 2, there exist n and a total Boolean function f on n bits with s(f) ≥ S and bs(f) ≥ s(f)^(41/20−ε). This is the campaign’s asymptotic separation target at the exact exponent 2.05.

Preamble
import Mathlib
import Definitions.Def_SensitivityCampaign
Formal statement
theorem SensitivityCampaign.reach_205 :
    SensitivityCampaign.AchievesExponent (2.05 : ℝ) := by sorry
Source
Campaign target requested by the campaign creator; background: https://github.com/bigospeedrun/site/issues/2 and https://github.com/openai/math/blob/main/lean/docs/132.md
Read-back

What the Lean code literally says, in plain math · Codex (independent blind auditor sub-agent)

The theorem SensitivityCampaign.reach_205\mathrm{SensitivityCampaign.reach\_205}SensitivityCampaign.reach_205 asserts that 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 function f:{0,1}n→{0,1}f:\{0,1\}^{n}\to\{0,1\}f:{0,1}n→{0,1} such that S≤s(f)S\le s(f)S≤s(f) and s(f)41/20−ε≤b(f)s(f)^{41/20-\varepsilon}\le b(f)s(f)41/20−ε≤b(f), where the latter inequality is in the real numbers and the natural numbers s(f)s(f)s(f) and b(f)b(f)b(f) are converted to real numbers before taking the real power or comparing. The decimal 2.052.052.05 denotes exactly 41/2041/2041/20. For an input xxx and a subset BBB of the coordinate set {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1}, let xBx^{B}xB be the input obtained by negating each Boolean coordinate in BBB and leaving every other coordinate unchanged. Then s(f)s(f)s(f) is the maximum, over all inputs xxx, of the number of coordinates iii for which f(x{i})≠f(x)f(x^{\{i\}})\ne f(x)f(x{i})=f(x). The number b(f)b(f)b(f) is the maximum, over all inputs xxx, of the maximum number of members of a finite set B\mathcal BB of coordinate subsets satisfying both that distinct members of B\mathcal BB are disjoint and that every member BBB is nonempty and obeys f(xB)≠f(x)f(x^{B})\ne f(x)f(xB)=f(x); equivalently, in the literal maximum over all such finite sets of subsets, a set failing either condition contributes zero. The empty set B\mathcal BB is permitted and contributes zero. The witnesses nnn and fff may depend on both ε\varepsilonε and SSS; no single pair is asserted to work for all such parameters, and neither witness is required to be unique. The existential quantifier permits n=0n=0n=0, but then s(f)=0s(f)=0s(f)=0 and the requirement S≤s(f)S\le s(f)S≤s(f) cannot hold for S≥2S\ge2S≥2. There is no upper bound on ε\varepsilonε, so the exponent 41/20−ε41/20-\varepsilon41/20−ε may be positive, zero, or negative; for any witnesses satisfying the assertion, its base is at least 222. The assertion imposes no requirement for ε≤0\varepsilon\le0ε≤0 or S<2S<2S<2.

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