KKL.fourierCoeff_lowDegreePart
theoremverifiedimported Lean
Fourier coefficients of the low-degree truncation. Let $f\colon\{0,1\}^n\to\bbr$ be a Boolean function and $k$ a natural number. For every subset $S\subseteq[n]$, the Fourier--Walsh coefficient of the low-degree part $f_{\le k}$ at frequency $S$ satisfies \[ \widehat{f_{\le k}}(S) \;=\; \begin{cases} \hat f(S) & \text{if } \abs{S}\le k,\\[2pt] 0 & \text{if } \abs{S} > k. \end{cases} \]
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.fourierCoeff_lowDegreePart (f : BooleanFunc n) (k : ℕ) (S : Finset (Fin n)) : fourierCoeff (lowDegreePart f k) S = if S.card ≤ k then fourierCoeff f S else 0
- Source
- TCSlib, `KKL.fourierCoeff_lowDegreePart`
- 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.fourierCoeff_lowDegreePart← KKL.fourierCoeff_lowDegreePart (TCSlib/BooleanAnalysis/KKL.lean:161): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- BooleanAnalysis.uniformWeightThe uniform probability measure on $\{0,1\}^n$ assigns weight $2^{-n}$ to each point.
- BooleanAnalysis.expectThe expectation of $f$ under the uniform measure: \[ \E[f] \;=\; 2^{-n}\sum_{x\in\{0,1\}^n} f(x). \]
- BooleanAnalysis.fourier_coeff_chiOrthonormality of Walsh characters. For any two subsets $S, T \subseteq [n]$, the $L^2$ inner product of the Walsh--Fourier characters…
- KKL.lowDegreePartThe low-degree part of $f$ at level $k$ keeps only the Fourier coefficients of degree at most $k$:…
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- BooleanAnalysis.chiS_singletonValue of a singleton Walsh character. Fix a dimension $n$, a coordinate $i \in [n]$, and a point $x$ of the Boolean hypercube $\{0,1\}^n$.…
- BooleanAnalysis.innerProduct_chi_selfWalsh characters have unit norm. Let $n$ be a natural number and let $S \subseteq [n]$. Under the uniform measure on the Boolean hypercube…
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- BooleanAnalysis.innerProductThe $L^2$ inner product of two Boolean functions with respect to the uniform measure:…
- BooleanAnalysis.chiSThe Walsh--Fourier character associated to $S\subseteq[n]$ is…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- BooleanAnalysis.flipBit_flipBitBit-flip is an involution. For a point $x$ in the Boolean hypercube $\{0,1\}^n$ and a coordinate $i$, flipping the $i$-th coordinate of…
- Used by 1
- KKL.lowDegree_l2_error$L^2$ error of the low-degree truncation. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function, and for a natural number $k$ let…
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.fourierCoeff_lowDegreePart (f : BooleanFunc n) (k : ℕ) (S : Finset (Fin n)) : fourierCoeff (lowDegreePart f k) S = if S.card ≤ k then fourierCoeff f S else 0 := by -- Step 1: Express fourierCoeff of lowDegreePart using linearity -- fourierCoeff (lowDegreePart f k) S = innerProduct (lowDegreePart f k) (chiS S) -- = expect (fun x => (∑ T, if |T|≤k then fhat(T)*χ_T(x) else 0) * χ_S(x)) -- = ∑ T, if |T|≤k then fhat(T) * expect (χ_T * χ_S) else 0 -- = ∑ T, if |T|≤k then fhat(T) * innerProduct χ_T χ_S else 0 -- = ∑ T, if |T|≤k then fhat(T) * (if T=S then 1 else 0) else 0 -- = if |S|≤k then fhat(S) else 0 show fourierCoeff (lowDegreePart f k) S = if S.card ≤ k then fourierCoeff f S else 0 unfold lowDegreePart unfold BooleanAnalysis.fourierCoeff innerProduct expect beta_reduce -- After unfolding: LHS = uniformWeight n * ∑ x, (∑ T, if T.card ≤ k then fhat_unfolded(T) * χ_T(x) else 0) * χ_S(x) -- where fhat_unfolded(T) = uniformWeight n * ∑ y, f y * χ_T y -- RHS = if S.card ≤ k then uniformWeight n * ∑ x, f x * χ_S x else 0 -- We will abbreviate fhat T := uniformWeight n * ∑ y, f y * χ_T y set w := uniformWeight n set fhat : Finset (Fin n) → ℝ := fun T => w * ∑ y, f y * chiS T y -- Now rearrange the LHS have step1 : w * ∑ x, (∑ T : Finset (Fin n), if T.card ≤ k then fhat T * chiS T x else 0) * chiS S x = ∑ T : Finset (Fin n), if T.card ≤ k then fhat T * (w * ∑ x, chiS T x * chiS S x) else 0 := by rw [Finset.mul_sum] conv_lhs => arg 2; ext x; rw [Finset.sum_mul] simp_rw [show ∀ (T : Finset (Fin n)) (x : BoolCube n), (if T.card ≤ k then fhat T * chiS T x else 0) * chiS S x = (if T.card ≤ k then fhat T * (chiS T x * chiS S x) else 0) from by intros; split_ifs <;> ring] simp_rw [Finset.mul_sum] rw [Finset.sum_comm] congr 1; ext T split_ifs with hT · congr 1; ext x; ring · simp rw [step1] -- Now w * ∑ x, chiS T x * chiS S x = innerProduct (chiS T) (chiS S) (after folding) -- But everything is unfolded, so we use fourier_coeff_chi directly have ortho : ∀ T : Finset (Fin n), w * ∑ x, chiS T x * chiS S x = if T = S then 1 else 0 := by intro T have := fourier_coeff_chi T S simp only [innerProduct, expect] at this exact this simp_rw [ortho] -- Now: ∑ T, if T.card ≤ k then fhat T * (if T = S then 1 else 0) else 0 -- = if S.card ≤ k then fhat S else 0 simp only [mul_ite, mul_one, mul_zero] -- Goal: ∑ T, if T.card ≤ k then (if T = S then fhat T else 0) else 0 -- = if S.card ≤ k then w * ∑ x, f x * chiS S x else 0 -- Collapse nested ifs conv_lhs => arg 2; ext T; rw [show (if T.card ≤ k then (if T = S then fhat T else 0) else 0) = (if T = S then (if S.card ≤ k then fhat S else 0) else 0) from by split_ifs <;> simp_all] simp [Finset.sum_ite_eq', fhat]-- Step 08: The L2 error of low-degree truncation is the tail Fourier weight.