AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

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.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.
See it in the graphDiscuss this resultChallenge it