A uniform absolute Fourier coefficient bound for Boolean functions
ProvedNarrowDNF.Fourier.coefficient_bool_abs_lecombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
Let be finite, , and . Regard the Boolean values as the real numbers zero and one. For , define
Then
The bound holds for every Boolean function, without a monotonicity assumption. It controls each coefficient by the exact absolute first moment of its character and retains the degree-dependent factor two.
Preamble
import Mathlib.Algebra.BigOperators.GroupWithZero.Finset
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Algebra.Order.BigOperators.Ring.Finset
import Mathlib.Analysis.SpecialFunctions.Sqrt
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Real.Basic
import Mathlib.Logic.Equiv.Prod
import Mathlib.Tactic.FieldSimp
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.Ring
import Definitions.Def_NarrowDNF_Fourier
import Definitions.Def_NarrowDNF_Influence
import Definitions.Def_NarrowDNF_ProductMeasure
import Theorems.Thm_NarrowDNF_Fourier_character_abs_mean
namespace NarrowDNF.FiberShift
end NarrowDNF.FiberShift
namespace NarrowDNF.Fourier
end NarrowDNF.Fourier
namespace NarrowDNF.Influence
end NarrowDNF.Influence
namespace NarrowDNF.ProductMeasure
end NarrowDNF.ProductMeasure
noncomputable section
open scoped BigOperators
open NarrowDNF
open NarrowDNF.Fourier
section Cube
variable {ι : Type*} [Fintype ι] [DecidableEq ι]
Formal statement
theorem NarrowDNF.Fourier.coefficient_bool_abs_le {p : ℝ} (hp0 : 0 < p) (hp1 : p < 1)
(f : (ι → Bool) → Bool) (s : ι → Bool) :
|coefficient p (fun x => Influence.boolValue (f x)) s| ≤
(2 * Real.sqrt (p * (1-p))) ^ degree s := by sorrySource