Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Separation exponent at least 2.131125283430

Proved
SensitivityCampaign.paley11987_sharper_decimal

by rgmohan · Oct 26, 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.131125283430−εbs(f)\ge s(f)^{2.131125283430-\varepsilon}bs(f)≥s(f)2.131125283430−ε. The decimal denotes the exact rational number 2131125283430/10122131125283430/10^{12}2131125283430/1012.

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.paley11987_sharper_decimal :
    SensitivityCampaign.AchievesExponent
      (2131125283430 / 1000000000000 : ℝ) := by sorry
Source
https://prove2.me/theorems/17127cc8-197a-4d2c-a452-3f589d1cd3b1
Read-back

What the Lean code literally says, in plain math · gpt-5.6-sol

For every positive real number ε\varepsilonε and every natural number SSS with S≥2S \ge 2S≥2, there exist a natural number nnn and a Boolean function f:(Fin⁡(n)→Bool⁡)→Bool⁡f : (\operatorname{Fin}(n) \to \operatorname{Bool}) \to \operatorname{Bool}f:(Fin(n)→Bool)→Bool such that the sensitivity of fff is at least SSS and

(sensitivity⁡(f))2.13112528343−ε≤blockSensitivity⁡(f).(\operatorname{sensitivity}(f))^{2.13112528343-\varepsilon} \le \operatorname{blockSensitivity}(f).(sensitivity(f))2.13112528343−ε≤blockSensitivity(f).

Here 2.131125283432.131125283432.13112528343 is the exact real number 2131125283430/10000000000002131125283430/10000000000002131125283430/1000000000000; sensitivity⁡(f)\operatorname{sensitivity}(f)sensitivity(f) is the maximum, over all Boolean inputs, of the number of individual coordinates whose Boolean value can be toggled to change the output; and blockSensitivity⁡(f)\operatorname{blockSensitivity}(f)blockSensitivity(f) is the maximum, over all inputs, of the cardinality of a finite family of pairwise disjoint, nonempty coordinate subsets such that toggling all coordinates in any one subset changes the output. The quantified nnn includes 000, although the requirement sensitivity⁡(f)≥S≥2\operatorname{sensitivity}(f) \ge S \ge 2sensitivity(f)≥S≥2 precludes a zero-coordinate witness.

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