boolean_influence_le_one
lemmaverified
For any finite type $U$ with decidable equality, monotone Boolean function $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$, coordinate $i \in U$, and parameter $p$ in unitInterval, boolean_influence U f i p is at most 1.
Statement
lemma boolean_influence_le_one (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (hf : Monotone f) (i : U) (p : unitInterval) : boolean_influence U f i p ≤ 1
- Source
- arXiv:2610.30730 Lemma 2.1
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- boolean_influenceGiven a finite type $U$ with decidable equality, a Boolean function $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$, coordinate $i \in U$,…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - boolean_product_bernoulliGiven a finite type $U$ and a parameter $p$ in the unit interval
unitInterval(the closed interval $[0, 1]$),… - boolean_product_bernoulli_isProbabilityMeasureFor any finite type $U$ and parameter $p \in [0, 1]$ in
unitInterval, the product Bernoulli measureboolean_product_bernoulli U pon… - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- discrete_poincare_monotone_booleanLet $U$ be a finite non-empty type with decidable equality, and let $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$ be a monotone function.…
Read back from the Lean
For any finite type U with decidable equality, any monotone function f : (U → Bool) → Bool (with respect to the pointwise ordering on U → Bool and the standard order on Bool), any coordinate i : U, and any probability parameter p : unitInterval, the Boolean influence of coordinate i on f with parameter p is at most 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The influence of any coordinate on a monotone Boolean function is at most 1. -/ lemma boolean_influence_le_one (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (hf : Monotone f) (i : U) (p : unitInterval) : boolean_influence U f i p ≤ 1 := by have hpt : ∀ x : U → Bool, (if f (Function.update x i true) then (1:ℝ) else 0) - (if f (Function.update x i false) then 1 else 0) ≤ 1 := by intro x have hle : Function.update x i false ≤ Function.update x i true := by intro j by_cases h : j = i · subst h; simp [Function.update] · simp [Function.update, h] have hmono : f (Function.update x i false) ≤ f (Function.update x i true) := hf hle cases h1 : f (Function.update x i true) · have h2 : f (Function.update x i false) = false := by have hle' : f (Function.update x i false) ≤ false := by rw [h1] at hmono; exact hmono exact le_antisymm hle' (Bool.false_le _) simp [h2] · cases h2 : f (Function.update x i false) · simp · simp have hint1 : MeasureTheory.Integrable (fun x : U → Bool => (if f (Function.update x i true) then (1:ℝ) else 0) - (if f (Function.update x i false) then 1 else 0)) (boolean_product_bernoulli U p) := MeasureTheory.Integrable.of_finite have hint2 : MeasureTheory.Integrable (fun _ : U → Bool => (1:ℝ)) (boolean_product_bernoulli U p) := MeasureTheory.Integrable.of_finite have hmono_int := MeasureTheory.integral_mono hint1 hint2 hpt have hconst : ∫ (_ : U → Bool), (1:ℝ) ∂boolean_product_bernoulli U p = 1 := by rw [MeasureTheory.integral_const]; simp unfold boolean_influence rw [hconst] at hmono_int exact hmono_int