KKL.noisyInfluence_le_influence
theoremverifiedimported Lean
Noisy 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 $\rho\in\bbr$ satisfy $0\le\rho\le 1$. Then the noisy influence of $i$ on $f$ at noise rate $\rho$ is at most the influence of $i$ on $f$: \[ \mathrm{Inf}_i^{\rho}[f]\;\le\;\mathrm{Inf}_i[f]. \]
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.noisyInfluence_le_influence (i : Fin n) (f : BooleanFunc n) (ρ : ℝ) (hρ0 : 0 ≤ ρ) (hρ1 : ρ ≤ 1) : noisyInfluence ρ i f ≤ influence i f
- Source
- TCSlib, `KKL.noisyInfluence_le_influence`
- 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.noisyInfluence_le_influence← KKL.noisyInfluence_le_influence (TCSlib/BooleanAnalysis/KKL.lean:465): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- KKL.noisyInfluenceThe noisy influence of coordinate $i$ on $f$ at noise rate $\rho$ is…
- BooleanAnalysis.influenceThe influence of coordinate $i$ on $f$ measures how often flipping bit $i$ changes the output:…
- BooleanAnalysis.influence_eq_sum_fourierInfluence 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…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
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.noisyInfluence_le_influence (i : Fin n) (f : BooleanFunc n) (ρ : ℝ) (hρ0 : 0 ≤ ρ) (hρ1 : ρ ≤ 1) : noisyInfluence ρ i f ≤ influence i f := by rw [noisyInfluence, influence_eq_sum_fourier] apply Finset.sum_le_sum intro S _ split_ifs with hiS · exact mul_le_of_le_one_left (sq_nonneg _) (pow_le_one₀ hρ0 hρ1) · exact le_refl _-- Step 14: For rho in (0,1), noisy influence can be bounded using-- Inf_i^rho[f] <= (Inf_i[f])^{1-rho} ... actually we use a simpler bound.-- Key lemma: Inf_i^rho[f] <= Inf_i[f]^rho (by log-convexity / power mean).-- This is a nontrivial step; we state a weaker but sufficient version.