Separation exponent at least 2.0205
ProvedSensitivityCampaign.reach_20205For 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 and every natural number , there exist a natural number and a total Boolean function such that and , where the decimal denotes the exact real number , both natural-valued quantities in the power inequality are cast to real numbers, and the power is real exponentiation. The coordinates are indexed by . For an input and a subset of coordinates, denotes the input obtained by complementing exactly the coordinates in . Explicitly, , and is the maximum, over all inputs and all finite sets of coordinate subsets, of when distinct members of are pairwise disjoint and every is nonempty and satisfies ; a family failing these conditions contributes to that maximum. The family is allowed and contributes . The quantifier over includes ; its input space contains the unique empty assignment, and both sensitivities are , so it cannot supply a witness satisfying with . Thus every witnessing function has positive sensitivity at least , including when 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 and may depend on both and ; no single function or common dimension is required to work for all choices.
import Mathlib import Definitions.Def_SensitivityCampaign import Theorems.Thm_SensitivityCampaign_finite_certificate import Theorems.Thm_SensitivityCampaign_finite_certificate_log open OAI.Paper320
theorem SensitivityCampaign.reach_20205 :
SensitivityCampaign.AchievesExponent (2.0205 : ℝ) := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.