AFTD Auto-Formalizing Theoretical Domains

BooleanAnalysis.influence

defimported Lean

The influence of coordinate $i$ on $f$ measures how often flipping bit $i$ changes the output: \[ \mathrm{Inf}_i[f] \;=\; \E\!\left[\frac{(f(x)-f(x^i))^2}{4}\right]. \] For $\pm 1$-valued $f$ this equals $\Pr[f(x)\ne f(x^i)]$.

Statement

set_option maxHeartbeats 400000 in
open scoped BigOperators in
variable {n : ℕ} in
noncomputable def BooleanAnalysis.influence (i : Fin n) (f : BooleanFunc n) : ℝ
Defined in
TCSlib, `BooleanAnalysis.influence`
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.
Verified
07 Oct 2026
Axioms
none listed
Built on 3
Used by 8

Lean source view module on GitHub

set_option maxHeartbeats 400000 in
open scoped BigOperators in
variable {n : ℕ} in
/-- The **influence** of coordinate `i` on `f`: `Inf_i[f] = Pr_x[f(x) ≠ f(xⁱ)]` where `xⁱ` denotes `x` with the `i`-th bit flipped. For `{-1,1}`-valued functions this equals `𝔼[(f(x) - f(xⁱ))² / 4]`. **Source:** [OD14, §2.1]. -/
noncomputable def BooleanAnalysis.influence (i : Fin n) (f : BooleanFunc n) : ℝ :=
  expect (fun x ↦ (f x - f (flipBit x i)) ^ 2 / 4)
See it in the graphDiscuss this resultChallenge it