BooleanAnalysis.fourier_coeff_chi
theoremverifiedimported Lean
Orthonormality of Walsh characters. For any two subsets $S, T \subseteq [n]$, the $L^2$ inner product of the Walsh--Fourier characters $\chi_S$ and $\chi_T$, taken with respect to the uniform measure on $\{0,1\}^n$, satisfies \[ \langle \chi_S, \chi_T\rangle \;=\; \begin{cases} 1 & S = T,\\ 0 & S \neq T. \end{cases} \] In particular, the family $\{\chi_S\}_{S\subseteq[n]}$ is orthonormal.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in set_option maxHeartbeats 400000 in open scoped BigOperators in variable {n : ℕ} in theorem BooleanAnalysis.fourier_coeff_chi (S T : Finset (Fin n)) : innerProduct (chiS S) (chiS T) = if S = T then 1 else 0
- Source
- TCSlib, `BooleanAnalysis.fourier_coeff_chi`
- 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.fourier_coeff_chi← BooleanAnalysis.fourier_coeff_chi (TCSlib/BooleanAnalysis/Basic.lean:360): 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.chiS_mul_chiSWalsh characters multiply by symmetric difference. Fix $n$, and for a subset $S\subseteq[n]$ let $\chi_S\colon\{0,1\}^n\to\bbr$ denote the…
- BooleanAnalysis.chiS_singletonValue of a singleton Walsh character. Fix a dimension $n$, a coordinate $i \in [n]$, and a point $x$ of the Boolean hypercube $\{0,1\}^n$.…
- BooleanAnalysis.sum_chiSSum of a Walsh character over the cube. Let $n$ be a natural number and let $S \subseteq [n]$. Summing the Walsh--Fourier character…
- 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…
- Used by 7
- 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…
- 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…
- BooleanAnalysis.innerProduct_chi_selfWalsh characters have unit norm. Let $n$ be a natural number and let $S \subseteq [n]$. Under the uniform measure on the Boolean hypercube…
- KKL.fourierCoeff_lowDegreePartFourier coefficients of the low-degree truncation. Let $f\colon\{0,1\}^n\to\bbr$ be a Boolean function and $k$ a natural number. For every…
- KKL.lowDegreePart_depends_on_influentialLow-degree part is close to a junta on the influential coordinates. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function, let $k$ be a natural…
- DecisionTree.fourierCoeff_sum_chiSRecovery of coefficients from a character expansion. Fix $n$, let $c$ assign a real number $c(S)$ to each subset $S \subseteq [n]$, and…
- 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 autoImplicit true inset_option relaxedAutoImplicit true inset_option maxHeartbeats 400000 inopen scoped BigOperators invariable {n : ℕ} in/-- **Orthonormality**: `⟪χ_S, χ_T⟫ = [S = T]`. The Walsh characters form an orthonormal system in `L²({0,1}ⁿ, uniform)`. **Source:** [OD14, §1.2]. -/theorem BooleanAnalysis.fourier_coeff_chi (S T : Finset (Fin n)) : innerProduct (chiS S) (chiS T) = if S = T then 1 else 0 := by simp only [innerProduct, expect, uniformWeight] have step : ∑ x : BoolCube n, chiS S x * chiS T x = ∑ x : BoolCube n, chiS (symmDiff S T) x := by congr 1; ext x; exact chiS_mul_chiS S T x rw [step, sum_chiS] by_cases hst : S = T · -- S = T: symmDiff S T = ∅ subst hst simp only [symmDiff_self, Finset.bot_eq_empty, ↓reduceIte] rw [← mul_pow]; norm_num · -- S ≠ T: symmDiff S T ≠ ∅ have hd : symmDiff S T ≠ ∅ := by intro h apply hst have : symmDiff S T = ⊥ := by rwa [Finset.bot_eq_empty] exact symmDiff_eq_bot.mp this simp [hd, hst]