DecisionTree.fourierCoeff_sum_chiS
theoremverifiedimported Lean
Recovery of coefficients from a character expansion. Fix $n$, let $c$ assign a real number $c(S)$ to each subset $S \subseteq [n]$, and consider the Boolean function $f(x) = \sum_{S \subseteq [n]} c(S)\,\chi_S(x)$, where $\chi_S$ is the Walsh--Fourier character of $S$. Then for every $T \subseteq [n]$ the Fourier--Walsh coefficient of $f$ at frequency $T$ recovers the corresponding coefficient, namely $\hat f(T) = c(T)$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open BooleanAnalysis in variable {n : ℕ} in lemma DecisionTree.fourierCoeff_sum_chiS (c : Finset (Fin n) → ℝ) (T : Finset (Fin n)) : fourierCoeff (fun x => ∑ S : Finset (Fin n), c S * chiS S x) T = c T
- Source
- TCSlib, `DecisionTree.fourierCoeff_sum_chiS`
- Lean proof
- By Hydroxyi, Owen McGinty, Seyoon Ragavan (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.DecisionTree.fourierCoeff_sum_chiS← DecisionTree.fourierCoeff_sum_chiS (TCSlib/BooleanAnalysis/LMN/DecisionTreeFourier.lean:263): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- BooleanAnalysis.uniformWeightThe uniform probability measure on $\{0,1\}^n$ assigns weight $2^{-n}$ to each point.
- BooleanAnalysis.fourier_coeff_chiOrthonormality of Walsh characters. For any two subsets $S, T \subseteq [n]$, the $L^2$ inner product of the Walsh--Fourier characters…
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- 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.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…
- 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.flipBit_flipBitBit-flip is an involution. For a point $x$ in the Boolean hypercube $\{0,1\}^n$ and a coordinate $i$, flipping the $i$-th coordinate of…
- Used by 1
- DecisionTree.fourierCoeff_signEvalFourier coefficients of a decision tree. Let $T$ be a decision tree on $n$ Boolean variables, and let $\sigma\!\circ\! T$ denote its…
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 inopen BooleanAnalysis invariable {n : ℕ} in/-- The Fourier coefficient of an explicit character combination reads off the coefficient (uniqueness of the Fourier expansion). -/lemma DecisionTree.fourierCoeff_sum_chiS (c : Finset (Fin n) → ℝ) (T : Finset (Fin n)) : fourierCoeff (fun x => ∑ S : Finset (Fin n), c S * chiS S x) T = c T := by have expand : fourierCoeff (fun x => ∑ S : Finset (Fin n), c S * chiS S x) T = ∑ S : Finset (Fin n), c S * innerProduct (chiS S) (chiS T) := by show uniformWeight n * ∑ x : BoolCube n, (∑ S : Finset (Fin n), c S * chiS S x) * chiS T x = ∑ S : Finset (Fin n), c S * (uniformWeight n * ∑ x : BoolCube n, chiS S x * chiS T x) calc uniformWeight n * ∑ x : BoolCube n, (∑ S : Finset (Fin n), c S * chiS S x) * chiS T x = uniformWeight n * ∑ x : BoolCube n, ∑ S : Finset (Fin n), c S * (chiS S x * chiS T x) := by congr 1 refine Finset.sum_congr rfl fun x _ => ?_ rw [Finset.sum_mul] exact Finset.sum_congr rfl fun S _ => by ring _ = uniformWeight n * ∑ S : Finset (Fin n), ∑ x : BoolCube n, c S * (chiS S x * chiS T x) := by rw [Finset.sum_comm] _ = ∑ S : Finset (Fin n), c S * (uniformWeight n * ∑ x : BoolCube n, chiS S x * chiS T x) := by rw [Finset.mul_sum] refine Finset.sum_congr rfl fun S _ => ?_ rw [← Finset.mul_sum] ring rw [expand] have hterm : ∀ S : Finset (Fin n), c S * innerProduct (chiS S) (chiS T) = if S = T then c S else 0 := by intro S rw [BooleanAnalysis.fourier_coeff_chi] split_ifs <;> simp simp only [hterm] simp