BooleanAnalysis.fourierCoeff_odd_even
theoremverifiedimported Lean
Vanishing of even-level Fourier coefficients of odd functions. Let $f : \{0,1\}^n \to \bbr$ be an odd Boolean function, meaning $f(\lnot x) = -f(x)$ for every $x \in \{0,1\}^n$, where $\lnot x$ denotes the pointwise negation of $x$. Then for every subset $S \subseteq [n]$ of even cardinality, the Fourier--Walsh coefficient of $f$ at $S$ vanishes: $\hat f(S) = 0$.
Statement
set_option maxHeartbeats 400000 in open scoped BigOperators in variable {n : ℕ} in lemma BooleanAnalysis.fourierCoeff_odd_even (f : BooleanFunc n) (hodd : isOddFunc f) (S : Finset (Fin n)) (heven : Even S.card) : fourierCoeff f S = 0
- Source
- TCSlib, `BooleanAnalysis.fourierCoeff_odd_even`
- Lean proof
- By Jingzhen Sha, Allan Li, Hydroxyi, Mina, Owen McGinty (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.BooleanAnalysis.fourierCoeff_odd_even← BooleanAnalysis.fourierCoeff_odd_even (TCSlib/BooleanAnalysis/Basic.lean:1044): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- BooleanAnalysis.uniformWeightThe uniform probability measure on $\{0,1\}^n$ assigns weight $2^{-n}$ to each point.
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- BooleanAnalysis.chiS_negWalsh character under global bit flip. Let $n$ be a natural number, let $S \subseteq [n]$, and let $x \in \{0,1\}^n$. Writing $\lnot x$…
- BooleanAnalysis.isOddFuncA Boolean function $f$ is odd if $f(\lnot x) = -f(x)$ for all $x$. This models antisymmetry of pairwise preferences in social choice.
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- BooleanAnalysis.chiSThe Walsh--Fourier character associated to $S\subseteq[n]$ is…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- Used by 1
- ArrowTheorem.corrFunc_eq_neg_third_of_weight_oneExtremal correlation concentrates weight on level one. Let $f:\{0,1\}^n\to\bbr$ be a $\pm 1$-valued Boolean function that is odd, meaning…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option maxHeartbeats 400000 inopen scoped BigOperators invariable {n : ℕ} in/-- For an odd function, the Fourier coefficient at any even-cardinality set is zero. -/lemma BooleanAnalysis.fourierCoeff_odd_even (f : BooleanFunc n) (hodd : isOddFunc f) (S : Finset (Fin n)) (heven : Even S.card) : fourierCoeff f S = 0 := by simp only [fourierCoeff, innerProduct, expect, uniformWeight] suffices h : ∑ x : BoolCube n, f x * chiS S x = 0 by simp [h] -- The bijection that flips all bits let e : BoolCube n ≃ BoolCube n := { toFun := fun x i => !x i invFun := fun x i => !x i left_inv := fun x => by ext; simp right_inv := fun x => by ext; simp } -- Change of variables: ∑_x f(x) χ_S(x) = ∑_x f(¬x) χ_S(¬x) -- Uses that x ↦ (¬x) is a bijection (involution) have hcv : ∑ x : BoolCube n, f x * chiS S x = ∑ x : BoolCube n, f (fun i => !x i) * chiS S (fun i => !x i) := (Fintype.sum_equiv e (fun x => f (fun i => !x i) * chiS S (fun i => !x i)) (fun x => f x * chiS S x) (fun _ => rfl)).symm -- Apply oddness and chiS_neg have hflip : ∑ x : BoolCube n, f (fun i => !x i) * chiS S (fun i => !x i) = -(∑ x : BoolCube n, f x * chiS S x) := by -- Expose the universal form so simp_rw can use hodd have hodd' : ∀ x : BoolCube n, f (fun i => !x i) = -f x := hodd -- (-1)^|S| = 1 when |S| is even have hone : (-1 : ℝ) ^ S.card = 1 := by obtain ⟨k, hk⟩ := heven rw [hk, ← two_mul, pow_mul, show (-1 : ℝ) ^ 2 = 1 from by norm_num, one_pow] simp_rw [hodd', chiS_neg, hone, one_mul, neg_mul] simp [Finset.sum_neg_distrib] linarith [hcv.trans hflip]