Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Separation exponent at least 2.0205

Proved
SensitivityCampaign.reach_20205

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

block-sensitivityboolean-functionsbs-20205-20261016sensitivity

For every epsilon > 0 and every integer S ≥ 2, some total Boolean function f satisfies s(f) ≥ S and bs(f) ≥ s(f)^(2.0205−epsilon).

Independent statement read-back:

The declaration 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 total 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)4041/2000−ε≤bs⁡(f)s(f)^{4041/2000-\varepsilon}\le \operatorname{bs}(f)s(f)4041/2000−ε≤bs(f), where the decimal 2.02052.02052.0205 denotes the exact real number 20205/10000=4041/200020205/10000=4041/200020205/10000=4041/2000, both natural-valued quantities in the power inequality are cast to real numbers, and the power is real exponentiation. The coordinates are indexed by Fin⁡(n)={0,…,n−1}\operatorname{Fin}(n)=\{0,\ldots,n-1\}Fin(n)={0,…,n−1}. For an input xxx and a subset BBB of coordinates, xBx^{B}xB denotes the input obtained by complementing exactly the coordinates in BBB. Explicitly, s(f)=max⁡x∈{0,1}n∣{i∈Fin⁡(n):f(x{i})≠f(x)}∣s(f)=\max_{x\in\{0,1\}^{n}}|\{i\in\operatorname{Fin}(n):f(x^{\{i\}})\ne f(x)\}|s(f)=maxx∈{0,1}n​∣{i∈Fin(n):f(x{i})=f(x)}∣, and bs⁡(f)\operatorname{bs}(f)bs(f) is the maximum, over all inputs xxx and all finite sets B\mathcal BB of coordinate subsets, of ∣B∣|\mathcal B|∣B∣ when distinct members of B\mathcal BB are pairwise disjoint and every B∈BB\in\mathcal BB∈B is nonempty and satisfies f(xB)≠f(x)f(x^{B})\ne f(x)f(xB)=f(x); a family failing these conditions contributes 000 to that maximum. The family B=∅\mathcal B=\varnothingB=∅ is allowed and contributes 000. The quantifier over nnn includes n=0n=0n=0; its input space contains the unique empty assignment, and both sensitivities are 000, so it cannot supply a witness satisfying S≤s(f)S\le s(f)S≤s(f) with S≥2S\ge2S≥2. Thus every witnessing function has positive sensitivity at least 222, including when ε\varepsilonε makes the real exponent zero or negative. Each function is defined on every Boolean assignment of its finite dimension, with no restricted or promise domain. The witnesses nnn and fff may depend on both ε\varepsilonε and SSS; no single function or common dimension is required to work for all choices.

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_20205 :
    SensitivityCampaign.AchievesExponent (2.0205 : ℝ) := by sorry
Source
Refinement of OpenAI/math, commit 1581d4cbdd69a0faf34b2089614fe2a814316a6a, lean/OAI/Combinatorics/Sensitivity; local proof snapshot f142fafe7b0ad4f46d209a530ee057421fe0f374, Sharp.Certificate finite_certificate_20205 and Sharp.Asymptotic rational_family_20205.
Human review
  • Endorsed by Shuze Chen · Oct 16, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Leo Shaposhnik · Oct 16, 2026

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

  • 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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me