AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
Used by 1

Lean source view module on GitHub

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
See it in the graphDiscuss this resultChallenge it