fourier_tail_l2_bound
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.
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.
uses
sq_le_sq',norm_nonneghave 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
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.
uses
Finset.sum_le_sum,Finset.mul_sumcalc ∑ 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]
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.
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)
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.
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.
- The Fourier coefficients are written out directly as explicit sums `(1 / 2^n) * ∑ x, f x * ∏ i ∈ S, if x i then -1 else 1` rather than using a dedicated Fourier transform operator.
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.
/-- 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]