Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Separation exponent at least 2.127294

Proved
SensitivityCampaign.reach_2127294

by Abhishek Anand · Oct 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

block-sensitivityboolean-functionssensitivity

For every real ε>0\varepsilon>0ε>0 and every integer S≥2S\ge2S≥2, there is a total Boolean function fff with s(f)≥Ss(f)\ge Ss(f)≥S and bs(f)≥s(f)2.127294−εbs(f)\ge s(f)^{2.127294-\varepsilon}bs(f)≥s(f)2.127294−ε.

Preamble
import Mathlib
import Definitions.Def_SensitivityCampaign
import Theorems.Thm_SensitivityCampaign_finite_certificate
import Theorems.Thm_SensitivityCampaign_finite_certificate_log
open OAI.Paper320
Formal statement
theorem SensitivityCampaign.reach_2127294 :
    SensitivityCampaign.AchievesExponent (2.127294 : ℝ) := by sorry
Source
https://github.com/bigospeedrun/site/issues/2
Read-back

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

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} such that S≤s(f)S\le s(f)S≤s(f) and s(f) 2.127294−ε≤bs⁡(f)s(f)^{\,2.127294-\varepsilon}\le \operatorname{bs}(f)s(f)2.127294−ε≤bs(f), where the latter inequality uses real numbers and real exponentiation, and 2.1272942.1272942.127294 is the exact rational number 1063647/5000001063647/5000001063647/500000. For an input xxx and a subset BBB of its nnn coordinates, let xBx^{B}xB denote the input obtained by complementing exactly the coordinates in BBB. Here 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); and bs⁡(f)\operatorname{bs}(f)bs(f) is the maximum, over all inputs xxx, of the largest cardinality of a finite family of pairwise disjoint, nonempty coordinate subsets BBB such that f(xB)≠f(x)f(x^{B})\ne f(x)f(xB)=f(x) for every member BBB of that family. The empty family is allowed and has cardinality zero; in the defining maximum, any family failing the stated requirements also contributes zero. The witnesses nnn and fff may depend on both ε\varepsilonε and SSS. Although the quantifier over nnn includes zero, n=0n=0n=0 has sensitivity zero and therefore cannot satisfy S≤s(f)S\le s(f)S≤s(f) under S≥2S\ge2S≥2. There is no upper bound on ε\varepsilonε, so the exponent may be zero or negative; the required base satisfies s(f)≥2s(f)\ge2s(f)≥2.

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

    Confirmed by the moderator at approval.

  • Endorsed by Abhishek Anand · Oct 20, 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