AFTD Auto-Formalizing Theoretical Domains

BooleanAnalysis.walsh_expansion

theoremverifiedimported Lean

Walsh–Fourier expansion of a Boolean function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of arity $n$. Then at every point $x\in\{0,1\}^n$, \[ f(x) \;=\; \sum_{S\subseteq[n]} \hat f(S)\,\chi_S(x), \] where the sum ranges over all subsets $S$ of $[n]$, $\chi_S$ is the Walsh character of $S$, and $\hat f(S)=\langle f,\chi_S\rangle$ is the Fourier–Walsh coefficient of $f$ at $S$.

Statement

set_option maxHeartbeats 400000 in
open scoped BigOperators in
variable {n : ℕ} in
theorem BooleanAnalysis.walsh_expansion (f : BooleanFunc n) (x : BoolCube n) :
    f x = ∑ S : Finset (Fin n), fourierCoeff f S * chiS S x
Source
TCSlib, `BooleanAnalysis.walsh_expansion`
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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 8
  • KKL.low_plus_high_eqLow and high degree parts reconstruct the function. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function and let $k \in \bbn$ be a threshold…
  • BooleanAnalysis.influence_eq_sum_fourierInfluence via Fourier coefficients. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function and fix a coordinate $i\in[n]$. Then the influence of…
  • ArrowTheorem.degree_one_implies_dictatorDegree-one unanimous voting rules are dictatorships. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function that is odd, is $\pm 1$-valued, and is…
  • BooleanAnalysis.plancherelPlancherel's identity. Let $f, g : \{0,1\}^n \to \bbr$ be Boolean functions. Then their $L^2$ inner product with respect to the uniform…
  • BoolFourier.fourier_expansionFourier–Walsh expansion. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function and let $x \in \{0,1\}^n$. Then $f$ agrees pointwise with the…
  • Bonami.degree_zero_constDegree-zero Boolean functions are constant. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of degree at most $0$; that is, every set $S$…
  • ArrowTheorem.expected_product_helperExpected product from the character kernel. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function, and let $\mathrm{votes}_1,\mathrm{votes}_2$…
  • BooleanAnalysis.parsevalParseval's identity for Boolean functions. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function, and equip $\{0,1\}^n$ with the uniform…

Lean source view module on GitHub

set_option maxHeartbeats 400000 inopen scoped BigOperators invariable {n : ℕ} in/-- **Walsh Expansion**: every Boolean function `f : {0,1}ⁿ → ℝ` can be written as `f(x) = ∑_{S ⊆ [n]} f̂(S) · χ_S(x)`. This is the Fourier inversion formula for the uniform measure on `{0,1}ⁿ`. **Source:** [OD14, §1.3]. -/theorem BooleanAnalysis.walsh_expansion (f : BooleanFunc n) (x : BoolCube n) :    f x = ∑ S : Finset (Fin n), fourierCoeff f S * chiS S x := by  simp only [fourierCoeff, innerProduct, expect, uniformWeight]  -- Goal: f x = ∑_S (2⁻ⁿ * ∑_y f(y) * χ_S(y)) * χ_S(x)  -- Proof: show both sides equal 2⁻ⁿ * ∑_y f(y) * ∑_S χ_S(y) * χ_S(x)  --        then use the completeness kernel  symm  calc ∑ S : Finset (Fin n), ((2:ℝ)⁻¹^n * ∑ y, f y * chiS S y) * chiS S x      = (2:ℝ)⁻¹^n * ∑ y : BoolCube n, ∑ S : Finset (Fin n), f y * (chiS S y * chiS S x) := by        -- Move 2⁻¹^n outside by rearranging: ∑_S (a * b_S) * c_S = a * ∑_S b_S * c_S,        -- then swap sum order and distribute f y        have step1 : ∑ S : Finset (Fin n), ((2:ℝ)⁻¹^n * ∑ y, f y * chiS S y) * chiS S x =            (2:ℝ)⁻¹^n * ∑ S : Finset (Fin n), (∑ y, f y * chiS S y) * chiS S x := by          rw [Finset.mul_sum]          apply Finset.sum_congr rfl; intro S _; ring        have step2 : ∑ S : Finset (Fin n), (∑ y, f y * chiS S y) * chiS S x =            ∑ y : BoolCube n, ∑ S : Finset (Fin n), f y * (chiS S y * chiS S x) := by          simp_rw [Finset.sum_mul]          rw [Finset.sum_comm]          apply Finset.sum_congr rfl; intro y _          apply Finset.sum_congr rfl; intro S _; ring        rw [step1, step2]    _ = (2:ℝ)⁻¹^n * ∑ y : BoolCube n, f y * (∑ S, chiS S y * chiS S x) := by        congr 1        apply Finset.sum_congr rfl; intro y _        rw [← Finset.mul_sum]    _ = (2:ℝ)⁻¹^n * ∑ y : BoolCube n, f y * (if y = x then (2:ℝ)^n else 0) := by        simp_rw [sum_chiS_mul_eq]    _ = (2:ℝ)⁻¹^n * (f x * (2:ℝ)^n) := by        congr 1        simp [Finset.sum_ite_eq', Finset.mem_univ]    _ = f x := by        rw [← mul_assoc, mul_comm ((2:ℝ)⁻¹^n) (f x), mul_assoc, ← mul_pow,            inv_mul_cancel₀ (by norm_num : (2:ℝ) ≠ 0), one_pow, mul_one]
See it in the graphDiscuss this resultChallenge it