fourier_l2_sum_eq_norm_sq
For any complex-valued function f on the Boolean hypercube {0,1}^n, the sum over all subsets S of Fin n of the squared absolute value of the Fourier coefficient of f at S equals the squared L2 norm l2_norm_sq_c f.
Statement
theorem fourier_l2_sum_eq_norm_sq {n : ℕ} (f : (Fin n → Bool) → ℂ) : ∑ S : Finset (Fin n), ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 = l2_norm_sq_c f
- Formalizes
- arXiv:2611.06451 Section 2 (Fact 2.1)
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- l2_norm_sq_cThe squared L2 norm ||f||_2^2 of a function f : (Fin n -> Bool) -> ℂ with respect to the uniform distribution on the Boolean hypercube is…
- Used by 1
- fourier_tail_l2_boundLet f and P be complex-valued functions on {0,1}^n. If a collection U of subsets of Fin n satisfies |f_hat(S)| ≤ 2 * |(f - P)_hat(S)| for…
Read back from the Lean
For every natural number $n$ and every function $f : (\text{Fin } n \to \text{Bool}) \to \mathbb{C}$, the sum over all subsets $S \subseteq \text{Fin } n$ (i.e. elements of $\text{Finset } (\text{Fin } n)$) of the squared complex norm of
$$\frac{1}{2^n} \sum_{x : \text{Fin } n \to \text{Bool}} f(x) \prod_{i \in S} (\text{if } x(i) = \text{true then } -1 \text{ else } 1)$$
is equal to l2_norm_sq_c f.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes Parseval's identity for the Fourier transform on the Boolean hypercube by reducing the real identity to an algebraic identity over ℂ via z * star(z) = ‖z‖^2. In the sum over all subsets S of the squared Fourier coefficients, the coefficients are expanded as sums over hypercube points x and y. Swapping the summation order isolates the character sum ∑_S χ_S(x) χ_S(y), which expands into the product ∏_i (1 + (-1)^{x_i} (-1)^{y_i}); this product equals 2^n when x = y and vanishes when x ≠ y. Summing over y collapses the double sum to x = y, and canceling 2^n against the normalization factor (1/2^n)^2 yields 2⁻ⁿ ∑_x ‖f(x)‖^2, matching the hypercube L2 norm.
For any function c : Fin n → R into a commutative semiring, summing ∏_{i ∈ S} c(i) over all subsets S equals ∏_{i : Fin n} (1 + c(i)).
By identifying the collection of all subsets of `Fin n` as the powerset of the universal set (`Finset.powerset_univ`), the subset sum is rewritten as the standard expansion of the product of terms (1 + c(i)) over all subsets (`Finset.prod_one_add`).
uses
Finset.powerset_univ,Finset.prod_one_addrw [← Finset.powerset_univ, ← Finset.prod_one_add]For any boolean b, 1 + (-1)^b * (-1)^b = 2.
Case analysis on b shows that whether b is false (where 1 · 1 = 1) or true (where (-1) · (-1) = 1), the product of the signs is 1, so 1 + 1 = 2.
cases b <;> norm_num
For any two distinct booleans b₁ ≠ b₂, 1 + (-1)^{b₁} * (-1)^{b₂} = 0.
Evaluating all four combinations of values for b₁ and b₂, the cases where b₁ = b₂ contradict the hypothesis b₁ ≠ b₂. In the remaining two cases (b₁ = false, b₂ = true and b₁ = true, b₂ = false), one factor is 1 and the other is -1, giving 1 + (-1) = 0.
cases b1 <;> cases b2 · contradiction · norm_num · norm_num · contradiction
The characters are orthogonal: the sum over all subsets S of χ_S(x) * χ_S(y) equals 2^n if x = y, and 0 if x ≠ y.
The product of the two products over S is combined into a single product over S of (-1)^{x(i)} * (-1)^{y(i)} (`Finset.prod_mul_distrib`), and the sum over subsets is transformed into the coordinate product ∏_{i : Fin n} (1 + (-1)^{x(i)} * (-1)^{y(i)}) using `fourier_l2_sum_eq_norm_sq_sum_prod_subsets`. If x = y, each term is 2 by `fourier_l2_sum_eq_norm_sq_term_eq`, so the product is 2^n. If x ≠ y, there exists some coordinate i where x(i) ≠ y(i) (`Function.ne_iff.mp`); the corresponding factor is 0 by `fourier_l2_sum_eq_norm_sq_term_ne`, making the entire product vanish by `Finset.prod_eq_zero`.
uses
Finset.prod_mul_distrib,fourier_l2_sum_eq_norm_sq_sum_prod_subsets,fourier_l2_sum_eq_norm_sq_term_eq,Function.ne_iff.mp,Finset.prod_eq_zero,Finset.mem_univ,fourier_l2_sum_eq_norm_sq_term_nesimp_rw [← Finset.prod_mul_distrib] rw [fourier_l2_sum_eq_norm_sq_sum_prod_subsets] split_ifs with h · subst h simp_rw [fourier_l2_sum_eq_norm_sq_term_eq] simp · obtain ⟨i, hi⟩ := Function.ne_iff.mp h apply Finset.prod_eq_zero (Finset.mem_univ i) exact fourier_l2_sum_eq_norm_sq_term_ne hi
Every Walsh character χ_S(x) is real-valued, so star(χ_S(x)) = χ_S(x).
Complex conjugation distributes across the finite product over S (`star_prod`). For each element i ∈ S, the sign (-1)^{x(i)} is either 1 or -1, both of which are real numbers invariant under complex conjugation.
uses
star_prod,Finset.prod_congrrw [star_prod] apply Finset.prod_congr rfl intro i _ cases x i <;> simp
The complex conjugate of the Fourier coefficient f̂(S) equals 2⁻ⁿ ∑_x star(f(x)) * χ_S(x).
Conjugation distributes over the outer scalar multiplication and the sum over hypercube points x (`star_mul`, `star_sum`). The prefactor 1/2^n is real and unchanged, and each summand star(f(x) * χ_S(x)) simplifies to star(f(x)) * χ_S(x) because the character is real-valued (`fourier_l2_sum_eq_norm_sq_star_chi`).
uses
star_mul,star_sum,mul_comm,Finset.sum_congr,fourier_l2_sum_eq_norm_sq_star_chirw [star_mul, star_sum] have h1 : star ((1 : ℂ) / (2 : ℂ) ^ n) = (1 : ℂ) / (2 : ℂ) ^ n := by simp rw [h1, mul_comm] congr 1 apply Finset.sum_congr rfl intro x _ rw [star_mul, fourier_l2_sum_eq_norm_sq_star_chi, mul_comm]
The sum of f̂(S) * star(f̂(S)) expands into (1/2^n)^2 ∑_S ∑_x ∑_y f(x) * star(f(y)) * χ_S(x) * χ_S(y).
Using `fourier_l2_sum_eq_norm_sq_star_coeff`, the conjugated Fourier coefficient is rewritten as a sum over y with star(f(y)). Factoring out the scalar (1/2^n) * (1/2^n) (`Finset.mul_sum`), the product of the two sums over x and y is converted into a double sum using `Fintype.sum_mul_sum`. The terms are then rearranged so that f(x) * star(f(y)) multiplies the product of character evaluations χ_S(x) * χ_S(y).
uses
fourier_l2_sum_eq_norm_sq_star_coeff,Finset.mul_sum,Fintype.sum_mul_sumsimp_rw [fourier_l2_sum_eq_norm_sq_star_coeff] have hmul : ∀ S : Finset (Fin n), ((1 / (2 : ℂ) ^ n) * ∑ x, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) * ((1 / (2 : ℂ) ^ n) * ∑ x, star (f x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) = ((1 / (2 : ℂ) ^ n) * (1 / (2 : ℂ) ^ n)) * ((∑ x, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) * (∑ x, star (f x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1))) := by intro S; ring simp_rw [hmul, ← Finset.mul_sum, Fintype.sum_mul_sum] have hterm : ∀ (S : Finset (Fin n)) (x y : Fin n → Bool), (f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) * (star (f y) * (∏ i ∈ S, if y i then (-1 : ℂ) else 1)) = (f x * star (f y)) * ((∏ i ∈ S, if x i then (-1 : ℂ) else 1) * (∏ i ∈ S, if y i then (-1 : ℂ) else 1)) := by intros; ring simp_rw [hterm]
Exchanging the order of summation and applying character orthogonality collapses the double sum over x and y to a single sum over x.
Swapping the summation order (`Finset.sum_comm`) moves the sum over S inside the sums over x and y. Character orthogonality (`fourier_l2_sum_eq_norm_sq_sum_chi_mul`) evaluates the inner sum over S to 2^n when x = y and 0 when x ≠ y. Summing this conditional expression over y (`Fintype.sum_ite_eq`) eliminates all terms except y = x, leaving (1/2^n)^2 ∑_x f(x) * star(f(x)) * 2^n.
uses
Finset.sum_comm,Finset.mul_sum,fourier_l2_sum_eq_norm_sq_sum_chi_mul,mul_ite,mul_zero,Fintype.sum_ite_eqrw [Finset.sum_comm] have hswap : (∑ x : Fin n → Bool, ∑ S : Finset (Fin n), ∑ y : Fin n → Bool, (f x * star (f y)) * ((∏ i ∈ S, if x i then (-1 : ℂ) else 1) * (∏ i ∈ S, if y i then (-1 : ℂ) else 1))) = ∑ x : Fin n → Bool, ∑ y : Fin n → Bool, ∑ S : Finset (Fin n), (f x * star (f y)) * ((∏ i ∈ S, if x i then (-1 : ℂ) else 1) * (∏ i ∈ S, if y i then (-1 : ℂ) else 1)) := by congr 1; ext x; rw [Finset.sum_comm] rw [hswap] simp_rw [← Finset.mul_sum, fourier_l2_sum_eq_norm_sq_sum_chi_mul] simp_rw [mul_ite, mul_zero, Fintype.sum_ite_eq]
Parseval's identity holds algebraically over ℂ: ∑_S f̂(S) * star(f̂(S)) = 2⁻ⁿ ∑_x f(x) * star(f(x)).
Factoring the constant 2^n out of the sum over x (`Finset.sum_mul`) gives (1/2^n)^2 * 2^n * ∑_x f(x) * star(f(x)). Since 2 ≠ 0 (`two_ne_zero`), 2^n ≠ 0 (`pow_ne_zero`), so field simplification cancels the factor of 2^n against the denominator 2^{2n}, leaving 1/2^n.
uses
pow_ne_zero,two_ne_zero,Finset.sum_mulhave h_ne : (2 : ℂ) ^ n ≠ 0 := pow_ne_zero n two_ne_zero have : (∑ x : Fin n → Bool, (f x * star (f x)) * (2 : ℂ) ^ n) = (∑ x : Fin n → Bool, f x * star (f x)) * (2 : ℂ) ^ n := by rw [← Finset.sum_mul] rw [this] field_simp
To prove the real norm equality, it suffices to show that the complex embeddings of ∑_S ‖f̂(S)‖^2 and l2_norm_sq_c f are equal.
By the injectivity of the canonical coercion from ℝ to ℂ (`Complex.ofReal_inj.mp`), the equality can be proven in ℂ. Distributing the coercion into the sum (`Complex.ofReal_sum`), each real squared norm ‖f̂(S)‖^2 is identified with the complex norm squared `Complex.normSq` (`Complex.normSq_eq_norm_sq`), which expands to z * star(z) by `Complex.mul_conj`.
uses
Complex.ofReal_inj.mp,Complex.ofReal_sum,Complex.normSq_eq_norm_sq,Complex.mul_conjapply Complex.ofReal_inj.mp rw [Complex.ofReal_sum] have h1 : ∀ S : Finset (Fin n), ((‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 : ℝ) : ℂ) = ((1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) * star ((1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) := by intro S rw [← Complex.normSq_eq_norm_sq] exact (Complex.mul_conj _).symm simp_rw [h1]
The sum of the squared Fourier coefficients equals the squared L2 norm l2_norm_sq_c f.
Lemma `fourier_l2_sum_eq_norm_sq_c` reduces the left-hand sum to (1/2^n) * ∑_x f(x) * star(f(x)). Unfolding the definition of `l2_norm_sq_c f` as (1/2^n) * ∑_x ‖f(x)‖^2 and pushing the real-to-complex coercion across the product and sum (`Complex.ofReal_mul`, `Complex.ofReal_sum`), each term f(x) * star(f(x)) matches ↑(‖f(x)‖^2) by `Complex.mul_conj`.
uses
fourier_l2_sum_eq_norm_sq_c,Complex.ofReal_mul,Complex.ofReal_sum,Finset.sum_congr,Complex.normSq_eq_norm_sq,Complex.mul_conjrw [fourier_l2_sum_eq_norm_sq_c] dsimp [l2_norm_sq_c] rw [Complex.ofReal_mul, Complex.ofReal_sum] congr 1 · push_cast; rfl · apply Finset.sum_congr rfl intro x _ rw [← Complex.normSq_eq_norm_sq] exact Complex.mul_conj (f x)
Complex.mul_conj- The product of a complex number and its complex conjugate equals its squared norm.
Complex.normSq_eq_norm_sq- The squared complex norm `Complex.normSq z` equals the square of the real norm ‖z‖^2.
Complex.ofReal_inj.mp- The canonical coercion from ℝ to ℂ is injective: if ↑r = ↑s, then r = s.
Complex.ofReal_mul- The canonical coercion from ℝ to ℂ distributes over multiplication: ↑(r * s) = ↑r * ↑s.
Complex.ofReal_sum- The canonical coercion from ℝ to ℂ distributes over finite sums: ↑(∑ i ∈ s, f i) = ∑ i ∈ s, ↑(f i).
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.mul_sum- Multiplication distributes from the left over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.powerset_univ- The powerset of the universal finset `Finset.univ` is the universal finset of all subsets.
Finset.prod_congr- Two products over equal finite sets are equal if their terms agree on all elements.
Finset.prod_eq_zero- A finite product equals zero if at least one of its factors is zero.
Finset.prod_mul_distrib- The product of pointwise products equals the product of the individual products: ∏ x ∈ s, f x * g x = (∏ x ∈ s, f x) * ∏ x ∈ s, g x.
Finset.prod_one_add- The product ∏ i ∈ s, (1 + f i) expands into the sum over all subsets t ⊆ s of ∏ i ∈ t, f i.
Finset.sum_comm- The order of summation in a finite double sum can be swapped.
Finset.sum_congr- Two sums over equal finite sets are equal if their terms agree on all elements.
Finset.sum_mul- Multiplication distributes from the right over a finite sum: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
Fintype.sum_ite_eq- Summing an expression that is non-zero only when j = i evaluates to f(i).
Fintype.sum_mul_sum- The product of two finite sums equals the double sum of all pairwise products.
Function.ne_iff.mp- Two functions are unequal if and only if they differ at some input.
fourier_l2_sum_eq_norm_sq_c- Parseval's identity holds over ℂ: the sum of the products of each Fourier coefficient with its conjugate equals 2⁻ⁿ ∑_x f(x) * star(f(x)).
fourier_l2_sum_eq_norm_sq_star_chi- Each Walsh character χ_S(x) = ∏_{i ∈ S} (-1)^{x(i)} is real-valued, so it is invariant under complex conjugation.
fourier_l2_sum_eq_norm_sq_star_coeff- The complex conjugate of the Fourier coefficient f̂(S) equals 2⁻ⁿ ∑_x star(f(x)) * χ_S(x).
fourier_l2_sum_eq_norm_sq_sum_chi_mul- Character orthogonality: the sum over all subsets S of χ_S(x) * χ_S(y) equals 2^n if x = y, and 0 if x ≠ y.
fourier_l2_sum_eq_norm_sq_sum_prod_subsets- Summing ∏_{i ∈ S} c(i) over all subsets S of Fin n equals the product ∏_{i : Fin n} (1 + c(i)).
fourier_l2_sum_eq_norm_sq_term_eq- For any boolean b, 1 + (-1)^b * (-1)^b = 2.
fourier_l2_sum_eq_norm_sq_term_ne- For distinct booleans b₁ ≠ b₂, 1 + (-1)^{b₁} * (-1)^{b₂} = 0.
mul_comm- Multiplication is commutative: a * b = b * a.
mul_ite- Multiplication distributes over an if-then-else condition: a * (if P then b else c) = if P then a * b else a * c.
mul_zero- Multiplying any element by zero yields zero: a * 0 = 0.
pow_ne_zero- A non-zero element raised to any natural power is non-zero.
star_mul- Complex conjugation distributes over multiplication: star(r * s) = star s * star r.
star_prod- Complex conjugation distributes over finite products: star(∏ x ∈ s, f x) = ∏ x ∈ s, star(f x).
star_sum- Complex conjugation distributes over finite sums: star(∑ x ∈ s, f x) = ∑ x ∈ s, star(f x).
two_ne_zero- The natural number 2 is non-zero.
- The proof formalizes the Boolean hypercube as functions `Fin n → Bool`, with subsets `S : Finset (Fin n)` indexing the Walsh characters and Fourier coefficients.
- The core energy conservation identity is established entirely within the field of complex numbers (`fourier_l2_sum_eq_norm_sq_c`), and the real-valued statement is deduced via the injectivity of the canonical embedding ℝ ↪ ℂ.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
lemma fourier_l2_sum_eq_norm_sq_sum_prod_subsets {n : ℕ} {R : Type*} [CommSemiring R] (c : Fin n → R) : ∑ S : Finset (Fin n), ∏ i ∈ S, c i = ∏ i : Fin n, (1 + c i) := by rw [← Finset.powerset_univ, ← Finset.prod_one_add]lemma fourier_l2_sum_eq_norm_sq_term_eq (b : Bool) : 1 + (if b then (-1 : ℂ) else 1) * (if b then (-1 : ℂ) else 1) = 2 := by cases b <;> norm_numlemma fourier_l2_sum_eq_norm_sq_term_ne {b1 b2 : Bool} (h : b1 ≠ b2) : 1 + (if b1 then (-1 : ℂ) else 1) * (if b2 then (-1 : ℂ) else 1) = 0 := by cases b1 <;> cases b2 · contradiction · norm_num · norm_num · contradictionlemma fourier_l2_sum_eq_norm_sq_sum_chi_mul {n : ℕ} (x y : Fin n → Bool) : ∑ S : Finset (Fin n), (∏ i ∈ S, if x i then (-1 : ℂ) else 1) * (∏ i ∈ S, if y i then (-1 : ℂ) else 1) = if x = y then (2 : ℂ) ^ n else 0 := by simp_rw [← Finset.prod_mul_distrib] rw [fourier_l2_sum_eq_norm_sq_sum_prod_subsets] split_ifs with h · subst h simp_rw [fourier_l2_sum_eq_norm_sq_term_eq] simp · obtain ⟨i, hi⟩ := Function.ne_iff.mp h apply Finset.prod_eq_zero (Finset.mem_univ i) exact fourier_l2_sum_eq_norm_sq_term_ne hilemma fourier_l2_sum_eq_norm_sq_star_chi {n : ℕ} (S : Finset (Fin n)) (x : Fin n → Bool) : star (∏ i ∈ S, if x i then (-1 : ℂ) else 1) = ∏ i ∈ S, if x i then (-1 : ℂ) else 1 := by rw [star_prod] apply Finset.prod_congr rfl intro i _ cases x i <;> simplemma fourier_l2_sum_eq_norm_sq_star_coeff {n : ℕ} (f : (Fin n → Bool) → ℂ) (S : Finset (Fin n)) : star ((1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) = (1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, star (f x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1) := by rw [star_mul, star_sum] have h1 : star ((1 : ℂ) / (2 : ℂ) ^ n) = (1 : ℂ) / (2 : ℂ) ^ n := by simp rw [h1, mul_comm] congr 1 apply Finset.sum_congr rfl intro x _ rw [star_mul, fourier_l2_sum_eq_norm_sq_star_chi, mul_comm]lemma fourier_l2_sum_eq_norm_sq_c {n : ℕ} (f : (Fin n → Bool) → ℂ) : ∑ S : Finset (Fin n), ((1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) * star ((1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) = (1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * star (f x) := by simp_rw [fourier_l2_sum_eq_norm_sq_star_coeff] have hmul : ∀ S : Finset (Fin n), ((1 / (2 : ℂ) ^ n) * ∑ x, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) * ((1 / (2 : ℂ) ^ n) * ∑ x, star (f x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) = ((1 / (2 : ℂ) ^ n) * (1 / (2 : ℂ) ^ n)) * ((∑ x, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) * (∑ x, star (f x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1))) := by intro S; ring simp_rw [hmul, ← Finset.mul_sum, Fintype.sum_mul_sum] have hterm : ∀ (S : Finset (Fin n)) (x y : Fin n → Bool), (f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) * (star (f y) * (∏ i ∈ S, if y i then (-1 : ℂ) else 1)) = (f x * star (f y)) * ((∏ i ∈ S, if x i then (-1 : ℂ) else 1) * (∏ i ∈ S, if y i then (-1 : ℂ) else 1)) := by intros; ring simp_rw [hterm] rw [Finset.sum_comm] have hswap : (∑ x : Fin n → Bool, ∑ S : Finset (Fin n), ∑ y : Fin n → Bool, (f x * star (f y)) * ((∏ i ∈ S, if x i then (-1 : ℂ) else 1) * (∏ i ∈ S, if y i then (-1 : ℂ) else 1))) = ∑ x : Fin n → Bool, ∑ y : Fin n → Bool, ∑ S : Finset (Fin n), (f x * star (f y)) * ((∏ i ∈ S, if x i then (-1 : ℂ) else 1) * (∏ i ∈ S, if y i then (-1 : ℂ) else 1)) := by congr 1; ext x; rw [Finset.sum_comm] rw [hswap] simp_rw [← Finset.mul_sum, fourier_l2_sum_eq_norm_sq_sum_chi_mul] simp_rw [mul_ite, mul_zero, Fintype.sum_ite_eq] have h_ne : (2 : ℂ) ^ n ≠ 0 := pow_ne_zero n two_ne_zero have : (∑ x : Fin n → Bool, (f x * star (f x)) * (2 : ℂ) ^ n) = (∑ x : Fin n → Bool, f x * star (f x)) * (2 : ℂ) ^ n := by rw [← Finset.sum_mul] rw [this] field_simp/-- Orthonormality / energy identity relating Fourier coefficient squared norms to hypercube L2 norm. -/theorem fourier_l2_sum_eq_norm_sq {n : ℕ} (f : (Fin n → Bool) → ℂ) : ∑ S : Finset (Fin n), ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 = l2_norm_sq_c f := by apply Complex.ofReal_inj.mp rw [Complex.ofReal_sum] have h1 : ∀ S : Finset (Fin n), ((‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 : ℝ) : ℂ) = ((1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) * star ((1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)) := by intro S rw [← Complex.normSq_eq_norm_sq] exact (Complex.mul_conj _).symm simp_rw [h1] rw [fourier_l2_sum_eq_norm_sq_c] dsimp [l2_norm_sq_c] rw [Complex.ofReal_mul, Complex.ofReal_sum] congr 1 · push_cast; rfl · apply Finset.sum_congr rfl intro x _ rw [← Complex.normSq_eq_norm_sq] exact Complex.mul_conj (f x)