AFTD Auto-Formalizing Theoretical Domains

fourier_l2_sum_eq_norm_sq

theoremverifiedformalization

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.

  1. 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`).

    line 3

    uses Finset.powerset_univ, Finset.prod_one_add

      rw [← Finset.powerset_univ, ← Finset.prod_one_add]
  2. 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.

    line 7

      cases b <;> norm_num
  3. 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.

    lines 11–15

      cases b1 <;> cases b2
      · contradiction
      · norm_num
      · norm_num
      · contradiction
  4. 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`.

    lines 21–29

    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_ne

      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 hi
  5. 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.

    lines 33–36

    uses star_prod, Finset.prod_congr

      rw [star_prod]
      apply Finset.prod_congr rfl
      intro i _
      cases x i <;> simp
  6. 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`).

    lines 41–47

    uses star_mul, star_sum, mul_comm, Finset.sum_congr, fourier_l2_sum_eq_norm_sq_star_chi

      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]
  7. 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).

    lines 54–69

    uses fourier_l2_sum_eq_norm_sq_star_coeff, Finset.mul_sum, Fintype.sum_mul_sum

      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]
  8. 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.

    lines 70–80

    uses Finset.sum_comm, Finset.mul_sum, fourier_l2_sum_eq_norm_sq_sum_chi_mul, mul_ite, mul_zero, Fintype.sum_ite_eq

      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]
  9. 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.

    lines 81–85

    uses pow_ne_zero, two_ne_zero, Finset.sum_mul

      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
  10. 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`.

    lines 92–101

    uses Complex.ofReal_inj.mp, Complex.ofReal_sum, Complex.normSq_eq_norm_sq, Complex.mul_conj

      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]
  11. 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`.

    lines 102–110

    uses fourier_l2_sum_eq_norm_sq_c, Complex.ofReal_mul, Complex.ofReal_sum, Finset.sum_congr, Complex.normSq_eq_norm_sq, Complex.mul_conj

      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)
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.

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

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)
See it in the graphDiscuss this resultChallenge it