AFTD Auto-Formalizing Theoretical Domains

BoolFourier.fourier_coeff_eq

theoremverifiedimported Lean

Agreement of two Fourier coefficient definitions. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function of arity $n$, and let $S \subseteq [n]$. Then the two definitions of the Fourier–Walsh coefficient $\hat f(S)$ coincide: both are equal to the $L^2$ inner product of $f$ with the Walsh character $\chi_S$, \[ \hat f(S) \;=\; \langle f, \chi_S\rangle \;=\; 2^{-n}\sum_{x\in\{0,1\}^n} f(x)\,\chi_S(x). \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Finset BooleanAnalysis in
lemma BoolFourier.fourier_coeff_eq {n : ℕ} (f : BoolFun n) (S : Finset (Fin n)) :
    fourier_coeff f S = fourierCoeff f S
Source
TCSlib, `BoolFourier.fourier_coeff_eq`
Lean proof
By Prastik Mohanraj, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Prastik Mohanraj. All rights reserved, 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 6
Used by 2
  • 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…
  • BoolFourier.parseval_identityParseval's identity for the Walsh–Fourier expansion. Let $f : \{0,1\}^n \to \bbr$ be a real-valued function on the Boolean hypercube, and…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Finset BooleanAnalysis inlemma BoolFourier.fourier_coeff_eq {n : ℕ} (f : BoolFun n) (S : Finset (Fin n)) :    fourier_coeff f S = fourierCoeff f S := by  unfold fourier_coeff inner_product BooleanAnalysis.fourierCoeff BooleanAnalysis.innerProduct  exact expectation_eq_expect _-- f(x) = ∑_S f̂(S) χ_S(x)
See it in the graphDiscuss this resultChallenge it