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.KKL.tail_fourier_weight_bound← KKL.tail_fourier_weight_bound (TCSlib/BooleanAnalysis/KKL.lean:256): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- BooleanAnalysis.totalInfluence_eq_sum_sq_degTotal influence via Fourier coefficients. For every Boolean function $f\colon\{0,1\}^n\to\bbr$, the total influence of $f$ is recovered…
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- BooleanAnalysis.totalInfluence$I[f] = \sum_{i=1}^n \mathrm{Inf}_i[f]$.
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- 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
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.
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.