BooleanAnalysis.influence_eq_sum_fourier
theoremverifiedimported Lean
Influence via Fourier coefficients. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function and fix a coordinate $i\in[n]$. Then the influence of $i$ on $f$ equals the sum of the squared Fourier--Walsh coefficients over all frequencies containing $i$: \[ \mathrm{Inf}_i[f] \;=\; \sum_{\substack{S\subseteq[n]\\ i\in S}} \hat f(S)^2. \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in set_option maxHeartbeats 400000 in open scoped BigOperators in variable {n : ℕ} in theorem BooleanAnalysis.influence_eq_sum_fourier (i : Fin n) (f : BooleanFunc n) : influence i f = ∑ S : Finset (Fin n), if i ∈ S then fourierCoeff f S ^ 2 else 0
- Source
- TCSlib, `BooleanAnalysis.influence_eq_sum_fourier`
- Lean proof
- By Jingzhen Sha, Allan Li, Hydroxyi, Mina, Owen McGinty (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.BooleanAnalysis.influence_eq_sum_fourier← BooleanAnalysis.influence_eq_sum_fourier (TCSlib/BooleanAnalysis/Basic.lean:602): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 16
- BooleanAnalysis.walsh_expansionWalsh–Fourier expansion of a Boolean function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of arity $n$. Then at every point…
- 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.chiS_flipBitWalsh character under a single bit flip. Fix a subset $S\subseteq[n]$ of coordinates. For every point $x$ of the Boolean hypercube…
- 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…
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- BooleanAnalysis.influenceThe influence of coordinate $i$ on $f$ measures how often flipping bit $i$ changes the output:…
- 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.flipBitThe point $x^i\in\{0,1\}^n$ obtained from $x$ by flipping the $i$-th coordinate.
- 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.parsevalParseval's identity for Boolean functions. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function, and equip $\{0,1\}^n$ with the uniform…
- 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 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…
- KKL.influential_coords_cardFew influential coordinates. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function and let $\tau > 0$. The number of $\tau$-influential…
- KKL.lowDegreePart_depends_on_influentialLow-degree part is close to a junta on the influential coordinates. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function, let $k$ be a natural…
- KKL.noisyInfluence_le_influenceNoisy influence is dominated by influence. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function, let $i\in[n]$ be a coordinate, and 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 400000 inopen scoped BigOperators invariable {n : ℕ} in/-- **Influence via Fourier**: `Inf_i[f] = ∑_{S ∋ i} f̂(S)²`. **Source:** [OD14, §2.2]. -/theorem BooleanAnalysis.influence_eq_sum_fourier (i : Fin n) (f : BooleanFunc n) : influence i f = ∑ S : Finset (Fin n), if i ∈ S then fourierCoeff f S ^ 2 else 0 := by -- Key: f(x) - f(flipBit x i) = 2 * ∑_{S∋i} f̂(S) * χ_S(x) have key : ∀ x : BoolCube n, f x - f (flipBit x i) = 2 * ∑ S : Finset (Fin n), if i ∈ S then fourierCoeff f S * chiS S x else 0 := by intro x rw [show f x = ∑ S, fourierCoeff f S * chiS S x from walsh_expansion f x, show f (flipBit x i) = ∑ S, fourierCoeff f S * chiS S (flipBit x i) from walsh_expansion f _, ← Finset.sum_sub_distrib] simp_rw [← mul_sub, chiS_flipBit] -- Goal: ∑ S, f̂(S) * (χ_S(x) - if i∈S then -χ_S(x) else χ_S(x)) = 2 * ∑_{S∋i} f̂(S)*χ_S(x) trans (∑ S : Finset (Fin n), if i ∈ S then 2 * (fourierCoeff f S * chiS S x) else 0) · apply Finset.sum_congr rfl; intro S _ by_cases hiS : i ∈ S <;> simp [hiS, two_mul] ring · rw [show ∑ S : Finset (Fin n), (if i ∈ S then 2 * (fourierCoeff f S * chiS S x) else 0) = 2 * ∑ S : Finset (Fin n), if i ∈ S then fourierCoeff f S * chiS S x else 0 from by rw [Finset.mul_sum] apply Finset.sum_congr rfl; intro S _ split_ifs <;> ring] -- Define g(x) = ∑_{S∋i} f̂(S) * χ_S(x) -- influence i f = 𝔼[(2g(x))²/4] = 𝔼[g(x)²] = innerProduct g g = ∑_{S∋i} f̂(S)² by Parseval simp only [influence, expect, uniformWeight] simp_rw [key] simp_rw [show ∀ x : BoolCube n, (2 * ∑ S, if i ∈ S then fourierCoeff f S * chiS S x else 0) ^ 2 / 4 = (∑ S, if i ∈ S then fourierCoeff f S * chiS S x else 0) ^ 2 from fun x => by ring] -- Rewrite as innerProduct g g where g = ∑_S (if i∈S then f̂(S) else 0) * χ_S rw [show (2:ℝ)⁻¹^n * ∑ x : BoolCube n, (∑ S, if i ∈ S then fourierCoeff f S * chiS S x else 0) ^ 2 = innerProduct (fun x => ∑ S, (if i ∈ S then fourierCoeff f S else 0) * chiS S x) (fun x => ∑ S, (if i ∈ S then fourierCoeff f S else 0) * chiS S x) from by simp only [innerProduct, expect, uniformWeight, sq] congr 1 apply Finset.sum_congr rfl; intro x _ congr 1 · apply Finset.sum_congr rfl; intro S _; by_cases hiS : i ∈ S <;> simp [hiS] · apply Finset.sum_congr rfl; intro S _; by_cases hiS : i ∈ S <;> simp [hiS]] -- Apply Parseval: innerProduct g g = ∑_S (f̂_g(S))^2 rw [parseval] -- Compute: f̂_g(S) = if i∈S then f̂(S) else 0 apply Finset.sum_congr rfl; intro S _ have hfc : fourierCoeff (fun x => ∑ T, (if i ∈ T then fourierCoeff f T else 0) * chiS T x) S = if i ∈ S then fourierCoeff f S else 0 := by simp only [fourierCoeff, innerProduct, expect, uniformWeight] -- After unfolding, fourierCoeff f T = 2⁻ⁿ * ∑_y f(y) * χ_T(y), which appears in the goal -- Goal: 2⁻¹^n * ∑ y ∑ x (if i∈y then ...) * χ_y x * χ_S x = if i∈S then f̂(S) else 0 -- Rearrange: swap x and T sums, then pull out 2⁻¹^n rw [show (2:ℝ)⁻¹^n * ∑ x : BoolCube n, (∑ T, (if i ∈ T then 2⁻¹^n * ∑ y : BoolCube n, f y * chiS T y else 0) * chiS T x) * chiS S x = ∑ T : Finset (Fin n), (if i ∈ T then 2⁻¹^n * ∑ y : BoolCube n, f y * chiS T y else 0) * ((2:ℝ)⁻¹^n * ∑ x, chiS T x * chiS S x) from by -- Rearrange: distribute 2⁻¹^n inside, expand T-sum, swap sums rw [show (2:ℝ)⁻¹^n * ∑ x : BoolCube n, (∑ T, (if i ∈ T then 2⁻¹^n * ∑ y : BoolCube n, f y * chiS T y else 0) * chiS T x) * chiS S x = ∑ x : BoolCube n, ∑ T : Finset (Fin n), (if i ∈ T then 2⁻¹^n * ∑ y : BoolCube n, f y * chiS T y else 0) * ((2:ℝ)⁻¹^n * (chiS T x * chiS S x)) from by rw [Finset.mul_sum] apply Finset.sum_congr rfl; intro x _ rw [Finset.sum_mul, Finset.mul_sum] apply Finset.sum_congr rfl; intro T _; ring] rw [Finset.sum_comm] apply Finset.sum_congr rfl; intro T _ rw [← Finset.mul_sum, ← Finset.mul_sum]] simp_rw [show ∀ T : Finset (Fin n), (2:ℝ)⁻¹^n * ∑ x, chiS T x * chiS S x = if T = S then 1 else 0 from fun T => by rw [show (2:ℝ)⁻¹^n * ∑ x, chiS T x * chiS S x = innerProduct (chiS T) (chiS S) from by simp [innerProduct, expect, uniformWeight]] exact fourier_coeff_chi T S] simp only [mul_ite, mul_one, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true] rw [hfc] by_cases hiS : i ∈ S <;> simp [hiS]