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.BooleanAnalysis.walsh_expansion← BooleanAnalysis.walsh_expansion (TCSlib/BooleanAnalysis/Basic.lean:282): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- BooleanAnalysis.uniformWeightThe uniform probability measure on $\{0,1\}^n$ assigns weight $2^{-n}$ to each point.
- BooleanAnalysis.expectThe expectation of $f$ under the uniform measure: \[ \E[f] \;=\; 2^{-n}\sum_{x\in\{0,1\}^n} f(x). \]
- BooleanAnalysis.sum_chiS_mul_eqCompleteness kernel for the Walsh basis. Let $x, y \in \{0,1\}^n$ be points of the Boolean hypercube. Then the sum of the products of…
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- BooleanAnalysis.innerProductThe $L^2$ inner product of two Boolean functions with respect to the uniform measure:…
- 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 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
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/-- **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]