AFTD Auto-Formalizing Theoretical Domains

fourier_tail_l2_bound

theoremverified

Let 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 every S in U, then the sum over S in U of |f_hat(S)|^2 is at most 4 * ||f - P||_2^2.

Statement

theorem fourier_tail_l2_bound {n : ℕ} (f : (Fin n → Bool) → ℂ) (P : (Fin n → Bool) → ℂ)
    (U : Finset (Finset (Fin n)))
    (hU : ∀ S ∈ U,
      ‖(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 - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖) :
    ∑ S ∈ U,
      ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2
    ≤ 4 * l2_norm_sq_c (fun x => f x - P x)
Source
arXiv:2611.06451 Theorem 3.1 proof (eq. 16)
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • fourier_l2_sum_eq_norm_sqFor 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…
  • 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…

Read back from the Lean

For any natural number $n$, any functions $f, P : (\text{Fin } n \to \text{Bool}) \to \mathbb{C}$, and any family of subsets $U \subseteq \mathcal{P}(\text{Fin } n)$ (represented as a Finset (Finset (Fin n))): If for every $S \in U$, $$\left\| \frac{1}{2^n} \sum_{x : \text{Fin } n \to \text{Bool}} f(x) \prod_{i \in S} (\text{if } x(i) \text{ then } -1 \text{ else } 1) \right\| \le 2 \left\| \frac{1}{2^n} \sum_{x : \text{Fin } n \to \text{Bool}} (f(x) - P(x)) \prod_{i \in S} (\text{if } x(i) \text{ then } -1 \text{ else } 1) \right\|,$$ then $$\sum_{S \in U} \left\| \frac{1}{2^n} \sum_{x : \text{Fin } n \to \text{Bool}} f(x) \prod_{i \in S} (\text{if } x(i) \text{ then } -1 \text{ else } 1) \right\|^2 \le 4 \cdot \text{l2\_norm\_sq\_c}(f - P).$$

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 theorem establishes an L^2 tail bound for functions where the Fourier coefficients of f are poorly approximated by P on a collection of frequencies U. For each S ∈ U, the hypothesis |f̂(S)| ≤ 2 |(f - P)^^(S)| squares to |f̂(S)|^2 ≤ 4 |(f - P)^^(S)|^2. Summing over U, factoring out 4, and extending the sum to all 2^n subsets gives an upper bound of 4 times the complete sum of squared Fourier coefficients. Parseval's identity then equates this complete Fourier sum with ||f - P||_2^2, completing the proof.

  1. For every frequency S ∈ U, the squared Fourier coefficient |f̂(S)|^2 is at most 4 * |(f - P)^^(S)|^2.

    For any S ∈ U, the hypothesis hU gives |f̂(S)| ≤ 2 * |(f - P)^^(S)|. Since norms are non-negative (norm_nonneg), both sides are non-negative, and squaring preserves the inequality via sq_le_sq'. Expanding (2 * |(f - P)^^(S)|)^2 into 4 * |(f - P)^^(S)|^2 by ring arithmetic yields the pointwise bound.

    lines 10–22

    uses sq_le_sq', norm_nonneg

      have key : ∀ S ∈ U,
          ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2
          ≤ 4 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := by
        intro S hS
        have h := hU S hS
        have hsq : ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2
            ≤ (2 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖) ^ 2 := by
          apply sq_le_sq'
          · linarith [norm_nonneg ((1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1))]
          · exact h
        calc ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2
            ≤ (2 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖) ^ 2 := hsq
          _ = 4 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := by ring
  2. The sum of |f̂(S)|^2 over S ∈ U is bounded by 4 * ∑_{S ∈ U} |(f - P)^^(S)|^2.

    Summing the pointwise inequality over all S ∈ U preserves the inequality by Finset.sum_le_sum. Factoring out the constant 4 from the summation using Finset.mul_sum gives 4 * ∑_{S ∈ U} |(f - P)^^(S)|^2.

    lines 23–26

    uses Finset.sum_le_sum, Finset.mul_sum

      calc
        ∑ S ∈ U, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2
            ≤ ∑ S ∈ U, 4 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := Finset.sum_le_sum key
        _ = 4 * ∑ S ∈ U, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := by rw [Finset.mul_sum]
  3. The sum 4 * ∑_{S ∈ U} |(f - P)^^(S)|^2 is at most the sum over all frequencies, 4 * ∑_S |(f - P)^^(S)|^2.

    Since U is a subset of all subsets of Fin n (Finset.subset_univ) and each squared norm term is non-negative, enlarging the index set from U to the full set of frequencies preserves and potentially increases the sum by Finset.sum_le_sum_of_subset_of_nonneg. Multiplying by 4 preserves the inequality by mul_le_mul_of_nonneg_left since 4 ≥ 0.

    lines 27–29

    uses mul_le_mul_of_nonneg_left, Finset.sum_le_sum_of_subset_of_nonneg, Finset.subset_univ

        _ ≤ 4 * ∑ S : Finset (Fin n), ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := by
            apply mul_le_mul_of_nonneg_left _ (by norm_num)
            exact Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ U) (by intro i _ _; positivity)
  4. The full sum 4 * ∑_S |(f - P)^^(S)|^2 equals 4 * ||f - P||_2^2.

    By Parseval's identity for the Boolean Fourier transform (fourier_l2_sum_eq_norm_sq), the sum of squared Fourier coefficients over all subsets S equals the squared L^2 norm of f - P.

    line 30

    uses fourier_l2_sum_eq_norm_sq

        _ = 4 * l2_norm_sq_c (fun x => f x - P x) := by rw [fourier_l2_sum_eq_norm_sq]
sq_le_sq'
In an ordered ring, if -b ≤ a and a ≤ b, then a^2 ≤ b^2.
norm_nonneg
The norm of any element in a seminormed group is non-negative.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finite set s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ s} g(i).
Finset.mul_sum
Multiplication distributes over finite sums: a * ∑_{i ∈ s} f(i) = ∑_{i ∈ s} (a * f(i)).
mul_le_mul_of_nonneg_left
Multiplying both sides of an inequality b ≤ c by a non-negative element a ≥ 0 yields a * b ≤ a * c.
Finset.sum_le_sum_of_subset_of_nonneg
If s ⊆ t and f(i) ≥ 0 for all elements i outside s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ t} f(i).
Finset.subset_univ
Every finite set in a finite type is a subset of the universal set of that type.
fourier_l2_sum_eq_norm_sq
Parseval's identity: the sum of the squared magnitudes of all Boolean Fourier coefficients of a function equals its squared L^2 norm.

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

/-- Fourier tail L2 bound for frequencies where f is poorly approximated. -/theorem fourier_tail_l2_bound {n : ℕ} (f : (Fin n → Bool) → ℂ) (P : (Fin n → Bool) → ℂ)    (U : Finset (Finset (Fin n)))    (hU : ∀ S ∈ U,      ‖(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 - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖) :    ∑ S ∈ U,      ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2    ≤ 4 * l2_norm_sq_c (fun x => f x - P x) := by  have key : ∀ S ∈ U,      ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2      ≤ 4 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := by    intro S hS    have h := hU S hS    have hsq : ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2        ≤ (2 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖) ^ 2 := by      apply sq_le_sq'      · linarith [norm_nonneg ((1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1))]      · exact h    calc ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2        ≤ (2 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖) ^ 2 := hsq      _ = 4 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := by ring  calc    ∑ S ∈ U, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2        ≤ ∑ S ∈ U, 4 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := Finset.sum_le_sum key    _ = 4 * ∑ S ∈ U, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := by rw [Finset.mul_sum]    _ ≤ 4 * ∑ S : Finset (Fin n), ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, (f x - P x) * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 := by        apply mul_le_mul_of_nonneg_left _ (by norm_num)        exact Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ U) (by intro i _ _; positivity)    _ = 4 * l2_norm_sq_c (fun x => f x - P x) := by rw [fourier_l2_sum_eq_norm_sq]
See it in the graphDiscuss this resultChallenge it