Asymptotic sensitivity separation exponent
DefinitionSensitivityCampaignAn exponent a is achievable if, for every positive epsilon and every integer sensitivity threshold S ≥ 2, there is a total Boolean function f with s(f) ≥ S and bs(f) ≥ s(f)^(a−epsilon). The witnesses may depend on epsilon and S.
import Mathlib
import Definitions.Def_SensitivitySeparation
namespace SensitivityCampaign
def AchievesExponent (a : ℝ) : Prop :=
∀ ε : ℝ, 0 < ε → ∀ S : ℕ, 2 ≤ S →
∃ (n : ℕ) (f : (Fin n → Bool) → Bool),
S ≤ OAI.Paper320.sensitivity f ∧
(OAI.Paper320.sensitivity f : ℝ) ^ (a - ε) ≤
(OAI.Paper320.blockSensitivity f : ℝ)
end SensitivityCampaign
Read-back
What the Lean code literally says, in plain math · Codex (independent auditor sub-agent)
For a Boolean function on bits, let be the maximum, over all inputs, of the number of individual coordinates whose flip changes its output, and let be the maximum size of a family of pairwise disjoint nonempty coordinate sets whose separate flips at input each change its output; the empty family is permitted and has size zero. Write for the maximum of over all inputs . For any real number , the proposition defined here holds exactly when, for every real and every natural number , there exist a natural number and a Boolean function on bits with and , where sensitivity values are regarded as real numbers in this inequality. No sign restriction is imposed on or . The function and dimension may depend on both and . The dimension is quantified over all natural numbers, including zero, but zero-dimensional functions have sensitivity zero and therefore cannot satisfy the required lower bound.
Confirmed by the moderator at approval.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.