AFTD Auto-Formalizing Theoretical Domains

KKL.tail_fourier_weight_bound

theoremverifiedimported Lean

Fourier tail weight bound above level $k$. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function, and let $k$ be a positive integer. Then the total Fourier weight of $f$ carried by frequencies of size strictly greater than $k$ is bounded by the total influence divided by $k$: \[ \sum_{\substack{S \subseteq [n] \\ \abs{S} > k}} \hat f(S)^2 \;\le\; \frac{I[f]}{k}. \]

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
set_option maxHeartbeats 800000 in
open scoped BigOperators in
open BooleanAnalysis in
variable {n : ℕ} in
open Classical in
lemma KKL.tail_fourier_weight_bound (f : BooleanFunc n) (k : ℕ) (hk : 0 < k) :
    (∑ S : Finset (Fin n), if k < S.card then fourierCoeff f S ^ 2 else 0) ≤
    totalInfluence f / k
Source
TCSlib, `KKL.tail_fourier_weight_bound`
Lean proof
By Mina, Owen McGinty, Hydroxyi (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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1
  • KKL.lowDegree_approxLow-degree approximation error bound. Let $f\colon\{0,1\}^n\to\bbr$ be a Boolean function and let $k\ge 1$ be an integer. Writing…

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inset_option maxHeartbeats 800000 inopen scoped BigOperators inopen BooleanAnalysis invariable {n : ℕ} inopen Classical inlemma KKL.tail_fourier_weight_bound (f : BooleanFunc n) (k : ℕ) (hk : 0 < k) :    (∑ S : Finset (Fin n), if k < S.card then fourierCoeff f S ^ 2 else 0) ≤    totalInfluence f / k := by  have hk' : (k : ℝ) > 0 := Nat.cast_pos.mpr hk  rw [totalInfluence_eq_sum_sq_deg]  rw [Finset.sum_div]  apply Finset.sum_le_sum  intro S _  split_ifs with hS  · -- k < S.card, so fhat(S)^2 ≤ S.card * fhat(S)^2 / k    rw [le_div_iff₀ hk']    have hle : (k : ℝ) ≤ S.card := by exact_mod_cast Nat.le_of_lt hS    calc fourierCoeff f S ^ 2 * ↑k        = ↑k * fourierCoeff f S ^ 2 := mul_comm _ _      _ ≤ ↑S.card * fourierCoeff f S ^ 2 := by          apply mul_le_mul_of_nonneg_right hle (sq_nonneg _)  · -- S.card ≤ k, so LHS = 0    positivity-- Step 10: Combine steps 08 and 09 to get the L2 approximation theorem.
See it in the graphDiscuss this resultChallenge it