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.BoolFourier.fourier_coeff_eq← BoolFourier.fourier_coeff_eq (TCSlib/BooleanAnalysis/BLR/BoolFourier.lean:321): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- BoolFourier.expectation_eq_expectAgreement of two definitions of the uniform expectation. Let $n$ be a natural number and let $f : \{0,1\}^n \to \bbr$ be a Boolean…
- BooleanAnalysis.innerProductThe $L^2$ inner product of two Boolean functions with respect to the uniform measure:…
- BoolFourier.fourier_coeffThe Fourier coefficient of $f : \{0,1\}^n \to \mathbb{R}$ at $S \subseteq [n]$ is \[ \hat f(S) = \langle f, \chi_S \rangle. \]
- BoolFourier.inner_productThe inner product of $f, g : \{0,1\}^n \to \mathbb{R}$ is…
- BoolFourier.BoolFunA Boolean function of arity $n$ is an element of type $\{0,1\}^n \to \mathbb{R}$, defined as an abbreviation for…
- 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
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 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)