BooleanAnalysis.plancherel
theoremverifiedformalizationimported Lean
Plancherel's identity. Let $f, g : \{0,1\}^n \to \bbr$ be Boolean functions. Then their $L^2$ inner product with respect to the uniform measure equals the sum, over all subsets $S \subseteq [n]$, of the products of their corresponding Fourier--Walsh coefficients: \[ \langle f, g\rangle \;=\; \sum_{S\subseteq[n]} \hat f(S)\,\hat g(S). \]
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.plancherel (f g : BooleanFunc n) : innerProduct f g = ∑ S : Finset (Fin n), fourierCoeff f S * fourierCoeff g S
- Formalizes
- Plancherel's identity, as formalized in TCSlib (`BooleanAnalysis.plancherel`)
- 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.plancherel← BooleanAnalysis.plancherel (TCSlib/BooleanAnalysis/Basic.lean:449): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- BooleanAnalysis.walsh_expansionWalsh–Fourier expansion of a Boolean function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of arity $n$. Then at every point…
- BooleanAnalysis.uniformWeightThe uniform probability measure on $\{0,1\}^n$ assigns weight $2^{-n}$ to each point.
- BooleanAnalysis.expectThe expectation of $f$ under the uniform measure: \[ \E[f] \;=\; 2^{-n}\sum_{x\in\{0,1\}^n} f(x). \]
- 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.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
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/-- **Plancherel's Identity**: `⟪f, g⟫ = ∑_{S ⊆ [n]} f̂(S)ĝ(S)` The sum of the products of Fourier coefficients equals the inner product -/theorem BooleanAnalysis.plancherel (f g : BooleanFunc n) : innerProduct f g = ∑ S : Finset (Fin n), fourierCoeff f S * fourierCoeff g S := by -- Expand f and g, and use bilinearity + orthonormality have expand : innerProduct f g = ∑ S : Finset (Fin n), ∑ T : Finset (Fin n), fourierCoeff f S * fourierCoeff g T * innerProduct (chiS S) (chiS T) := by -- The exact same expansion logic you used in Parseval, just with `f(x) * g(x)` simp_rw [innerProduct, expect, uniformWeight] simp_rw [show ∀ x : BoolCube n, f x * g x = (∑ S : Finset (Fin n), fourierCoeff f S * chiS S x) * (∑ T : Finset (Fin n), fourierCoeff g T * chiS T x) from fun x => by rw [← walsh_expansion f x, ← walsh_expansion g x]] -- ... (Proceed with the exact same Finset sum rearrangement steps from parseval) ... rw [show (2:ℝ)⁻¹^n * ∑ x : BoolCube n, (∑ S : Finset (Fin n), fourierCoeff f S * chiS S x) * (∑ T : Finset (Fin n), fourierCoeff g T * chiS T x) = ∑ S : Finset (Fin n), ∑ T : Finset (Fin n), fourierCoeff f S * fourierCoeff g T * ((2:ℝ)⁻¹^n * ∑ x : BoolCube n, chiS S x * chiS T x) from by -- Step 1: move 2⁻¹^n inside x-sum rw [Finset.mul_sum] rw [show ∑ x : BoolCube n, (2:ℝ)⁻¹^n * ((∑ S : Finset (Fin n), fourierCoeff f S * chiS S x) * (∑ T : Finset (Fin n), fourierCoeff g T * chiS T x)) = ∑ x : BoolCube n, ∑ S : Finset (Fin n), ∑ T : Finset (Fin n), (2:ℝ)⁻¹^n * (fourierCoeff f S * chiS S x * (fourierCoeff g T * chiS T x)) from by apply Finset.sum_congr rfl; intro x _ rw [Finset.sum_mul, Finset.mul_sum] apply Finset.sum_congr rfl; intro S _ rw [show (2:ℝ)⁻¹^n * (fourierCoeff f S * chiS S x * ∑ T, fourierCoeff g T * chiS T x) = ∑ T, (2:ℝ)⁻¹^n * (fourierCoeff f S * chiS S x * (fourierCoeff g T * chiS T x)) from by rw [show fourierCoeff f S * chiS S x * ∑ T, fourierCoeff g T * chiS T x = ∑ T, fourierCoeff f S * chiS S x * (fourierCoeff g T * chiS T x) from Finset.mul_sum _ _ _] rw [Finset.mul_sum]]] rw [Finset.sum_comm] apply Finset.sum_congr rfl; intro S _ -- Step 2c: swap x and T rw [Finset.sum_comm] apply Finset.sum_congr rfl; intro T _ rw [show ∑ x : BoolCube n, (2:ℝ)⁻¹^n * (fourierCoeff f S * chiS S x * (fourierCoeff g T * chiS T x)) = fourierCoeff f S * fourierCoeff g T * ((2:ℝ)⁻¹^n * ∑ x : BoolCube n, chiS S x * chiS T x) from by rw [show ∑ x : BoolCube n, (2:ℝ)⁻¹^n * (fourierCoeff f S * chiS S x * (fourierCoeff g T * chiS T x)) = ∑ x : BoolCube n, (fourierCoeff f S * fourierCoeff g T) * ((2:ℝ)⁻¹^n * (chiS S x * chiS T x)) from by apply Finset.sum_congr rfl; intro x _; ring] rw [← Finset.mul_sum, ← Finset.mul_sum]]] rw [expand] simp_rw [fourier_coeff_chi, mul_ite, mul_one, mul_zero] simp_rw [Finset.sum_ite_eq, Finset.mem_univ, if_true]