BooleanAnalysis.parseval
theoremverifiedformalizationimported Lean
Parseval's identity for Boolean functions. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function, and equip $\{0,1\}^n$ with the uniform probability measure. Then the $L^2$ inner product of $f$ with itself equals the sum of the squares of its Fourier--Walsh coefficients over all subsets $S \subseteq [n]$: \[ \langle f, f\rangle \;=\; \sum_{S \subseteq [n]} \hat f(S)^2. \]
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.parseval (f : BooleanFunc n) : innerProduct f f = ∑ S : Finset (Fin n), fourierCoeff f S ^ 2
- Formalizes
- Parseval's identity for Boolean functions, as formalized in TCSlib (`BooleanAnalysis.parseval`)
- 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.parseval← BooleanAnalysis.parseval (TCSlib/BooleanAnalysis/Basic.lean:391): 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$.
- Used by 5
- KKL.lowDegree_l2_error$L^2$ error of the low-degree truncation. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function, and for a natural number $k$ let…
- BooleanAnalysis.influence_eq_sum_fourierInfluence via Fourier coefficients. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function and fix a coordinate $i\in[n]$. Then the influence of…
- BooleanAnalysis.parseval_pm_oneParseval's identity for $\pm 1$-valued functions. Let $f \colon \{0,1\}^n \to \bbr$ be a Boolean function that is $\pm 1$-valued, meaning…
- KKL.lowDegreePart_depends_on_influentialLow-degree part is close to a junta on the influential coordinates. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function, let $k$ be a natural…
- 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 autoImplicit true inset_option relaxedAutoImplicit true inset_option maxHeartbeats 400000 inopen scoped BigOperators invariable {n : ℕ} in/-- **Parseval's Identity**: `‖f‖² = ∑_{S ⊆ [n]} f̂(S)²`. The sum of squared Fourier coefficients equals the squared `L²` norm. **Source:** [OD14, §1.4]. -/theorem BooleanAnalysis.parseval (f : BooleanFunc n) : innerProduct f f = ∑ S : Finset (Fin n), fourierCoeff f S ^ 2 := by -- Expand f = ∑_S f̂(S) χ_S and use bilinearity + orthonormality have expand : innerProduct f f = ∑ S : Finset (Fin n), ∑ T : Finset (Fin n), fourierCoeff f S * fourierCoeff f T * innerProduct (chiS S) (chiS T) := by -- Expand innerProduct and uniformWeight first so f x * f x becomes visible simp_rw [innerProduct, expect, uniformWeight] -- Now rewrite f(x)*f(x) using walsh_expansion simp_rw [show ∀ x : BoolCube n, f x * f x = (∑ S : Finset (Fin n), fourierCoeff f S * chiS S x) * (∑ T : Finset (Fin n), fourierCoeff f T * chiS T x) from fun x => by rw [← walsh_expansion f x]] -- Goal: 2⁻¹^n * ∑_x (∑_S ...) * (∑_T ...) = ∑_S ∑_T f̂S * f̂T * (2⁻¹^n * ∑_x χSx * χTx) -- Use the rearrangement: rw [show (2:ℝ)⁻¹^n * ∑ x : BoolCube n, (∑ S : Finset (Fin n), fourierCoeff f S * chiS S x) * (∑ T : Finset (Fin n), fourierCoeff f T * chiS T x) = ∑ S : Finset (Fin n), ∑ T : Finset (Fin n), fourierCoeff f S * fourierCoeff f 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] -- Goal: ∑_x 2⁻¹^n * ((∑_S ...) * (∑_T ...)) = ∑_S ∑_T f̂S * f̂T * (...) -- Step 2: per x, expand products of sums and collect: -- ∑_x 2⁻¹^n * (∑_S ∑_T f̂S * χSx * (f̂T * χTx)) = ∑_S ∑_T f̂S * f̂T * (2⁻¹^n * ∑_x χSx*χTx) -- Step 2a: expand per-x product to ∑_x ∑_S ∑_T rw [show ∑ x : BoolCube n, (2:ℝ)⁻¹^n * ((∑ S : Finset (Fin n), fourierCoeff f S * chiS S x) * (∑ T : Finset (Fin n), fourierCoeff f T * chiS T x)) = ∑ x : BoolCube n, ∑ S : Finset (Fin n), ∑ T : Finset (Fin n), (2:ℝ)⁻¹^n * (fourierCoeff f S * chiS S x * (fourierCoeff f 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 f T * chiS T x) = ∑ T, (2:ℝ)⁻¹^n * (fourierCoeff f S * chiS S x * (fourierCoeff f T * chiS T x)) from by rw [show fourierCoeff f S * chiS S x * ∑ T, fourierCoeff f T * chiS T x = ∑ T, fourierCoeff f S * chiS S x * (fourierCoeff f 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 _ -- Step 2d: factor out f̂S * f̂T rw [show ∑ x : BoolCube n, (2:ℝ)⁻¹^n * (fourierCoeff f S * chiS S x * (fourierCoeff f T * chiS T x)) = fourierCoeff f S * fourierCoeff f 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 f T * chiS T x)) = ∑ x : BoolCube n, (fourierCoeff f S * fourierCoeff f 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] apply Finset.sum_congr rfl; intro S _; ring