Documentation

Atlas.BooleanFunctions.code.MISBound

theorem mis_combinatorial_bound (ρ : ℝ) (hρ_pos : 0 < ρ) (hρ_lt : ρ < 1) (ε : ℝ) (hε : ε > 0) :
∃ δ > 0, ∀ (k : ℕ) (f : (Fin k → Bool) → ℝ), (∀ (x : Fin k → Bool), f x ∈ Set.Icc (-1) 1) → (∀ (i : Fin k), 1 / 2 ^ k * ∑ x : Fin k → Bool, (f x - f (Function.update x i !x i)) ^ 2 / 4 ≤ δ) → 1 / 2 ^ k * ∑ x : Fin k → Bool, f x = 0 → 1 / 2 ^ k * ∑ x : Fin k → Bool, f x * (1 / 2 ^ k * ∑ y : Fin k → Bool, (∏ i : Fin k, if x i = y i then 1 else ρ) * f y) ≤ 1 - 2 / Real.pi * Real.arccos ρ + ε