discrete_poincare_monotone_boolean
Let $U$ be a finite non-empty type with decidable equality, and let $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$ be a monotone function. For any parameter $p$ in the unit interval unitInterval, the variance of the real indicator fun x => if f x then 1 else 0 under boolean_product_bernoulli U p is at most $(p : \mathbb{R}) * (1 - (p : \mathbb{R})) * \sum_{i : U} \mathrm{boolean\_influence}\ U\ f\ i\ p$.
Statement
theorem discrete_poincare_monotone_boolean (U : Type*) [Fintype U] [Nonempty U] [DecidableEq U] (f : (U → Bool) → Bool) (hf : Monotone f) (p : unitInterval) : ProbabilityTheory.variance (fun x ↦ if f x then (1 : ℝ) else 0) (boolean_product_bernoulli U p) ≤ (p : ℝ) * (1 - (p : ℝ)) * ∑ i : U, boolean_influence U f i p
- Formalizes
- arXiv:2610.30730 Lemma 2.1
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- boolean_product_bernoulliGiven a finite type $U$ and a parameter $p$ in the unit interval
unitInterval(the closed interval $[0, 1]$),… - boolean_influenceGiven a finite type $U$ with decidable equality, a Boolean function $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$, coordinate $i \in U$,…
- boolean_influence_le_oneFor any finite type $U$ with decidable equality, monotone Boolean function $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$, coordinate…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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…
- boolean_product_bernoulliGiven a finite type $U$ and a parameter $p$ in the unit interval
Read back from the Lean
For any finite, nonempty type $U$ with decidable equality, any monotone function $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$ (with respect to the pointwise order on $U \to \mathrm{Bool}$), and any parameter $p \in [0, 1]$ (an element of unitInterval), the variance of the indicator function of $f$ (mapping $x$ to $1$ if $f(x) = \mathrm{true}$ and $0$ otherwise) with respect to the product Bernoulli measure on $U \to \mathrm{Bool}$ with parameter $p$ is less than or equal to $p(1 - p) \sum_{i : U} \mathrm{Inf}_i(f)$, where $\mathrm{Inf}_i(f)$ is the influence of coordinate $i$ on $f$ at parameter $p$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The discrete Poincaré inequality for monotone Boolean functions is proved by strong induction on the cardinality $n = |U|$. For $n = 0$, $U$ is empty, so the indicator is constant and both the variance and influences vanish. For $n > 0$, we condition on any chosen coordinate $q \in U$, which decomposes $f$ into two monotone functions $f_0, f_1$ on $U \setminus \{q\}$ whose expectations satisfy $\mu_0 \le \mu_1$ and whose variances satisfy the inductive hypothesis. Conditioning expresses the variance of the indicator as $((1-p)\mu_0 + p\mu_1)(1 - ((1-p)\mu_0 + p\mu_1))$, the influence at $q$ as $\mu_1 - \mu_0$, and the influences at other coordinates as a $(1-p, p)$-mixture of their influences on $f_0$ and $f_1$. The inductive step is completed by applying a scalar inequality that combines the inductive bounds on $f_0$ and $f_1$ with the fact that $(\mu_1 - \mu_0)^2 \le \mu_1 - \mu_0$ on $[0, 1]$.
For any Boolean $b$, the real measure of $\{b\}$ under the Bernoulli measure with parameter $p$ equals the weight $W(p, b)$, which is $p$ if $b = \mathrm{true}$ and $1-p$ if $b = \mathrm{false}$.
The single-bit weight function $W(p, b)$ is defined to be $p$ if $b$ is true and $1-p$ if $b$ is false. Case analysis on $b$ matches each case with mathlib's lemmas for the real value of the Bernoulli measure on singletons: `bernoulliMeasure_real_apply_of_notMem_of_mem` for false and `bernoulliMeasure_real_apply_of_mem_of_notMem` for true.
uses
bernoulliMeasure_real_apply_of_notMem_of_mem,bernoulliMeasure_real_apply_of_mem_of_notMemopen MeasureTheory ProbabilityTheory open scoped BigOperators noncomputable def discrete_poincare_monotone_boolean_W (p : unitInterval) (b : Bool) : ℝ := if b then (p : ℝ) else 1 - (p : ℝ) lemma discrete_poincare_monotone_boolean_bernW (p : unitInterval) (b : Bool) : (bernoulliMeasure true false p).real {b} = discrete_poincare_monotone_boolean_W p b := by cases b · rw [discrete_poincare_monotone_boolean_W, if_neg (by simp)] exact bernoulliMeasure_real_apply_of_notMem_of_mem p (measurableSet_singleton false) (by simp) (by simp) · rw [discrete_poincare_monotone_boolean_W, if_pos rfl] exact bernoulliMeasure_real_apply_of_mem_of_notMem p (measurableSet_singleton true) (by simp) (by simp)
For any configuration $x : U \to \mathrm{Bool}$, the probability of the singleton $\{x\}$ under the product Bernoulli measure is the product of coordinate weights $\prod_{i \in U} W(p, x(i))$.
By definition, `boolean_product_bernoulli` is the product measure of independent Bernoulli measures on each coordinate. Expanding the measure of the singleton $\{x\}$ via `Measure.pi_singleton` gives the product of single-coordinate measures, which converts to real via `ENNReal.toReal_prod`. Each factor is then rewritten as $W(p, x(i))$ using `discrete_poincare_monotone_boolean_bernW`.
uses
Measure.pi_singleton,ENNReal.toReal_prod,discrete_poincare_monotone_boolean_bernWlemma discrete_poincare_monotone_boolean_prodReal (U : Type*) [Fintype U] (p : unitInterval) (x : U → Bool) : (boolean_product_bernoulli U p).real {x} = ∏ i, discrete_poincare_monotone_boolean_W p (x i) := by rw [boolean_product_bernoulli, Measure.real_def, Measure.pi_singleton, ENNReal.toReal_prod (Finset.univ) (fun i => (bernoulliMeasure true false p) {x i})] exact Finset.prod_congr rfl (fun i _ => discrete_poincare_monotone_boolean_bernW p (x i))
The integral of any real-valued function $h$ on $U \to \mathrm{Bool}$ under the product Bernoulli measure equals the finite sum $\sum_{x} (\prod_{i \in U} W(p, x(i))) \cdot h(x)$.
Since $U \to \mathrm{Bool}$ is finite, the integral with respect to a discrete measure reduces to a sum over points weighted by their singleton measures via `MeasureTheory.integral_fintype`. Substituting the product formula from `discrete_poincare_monotone_boolean_prodReal` for each singleton measure and simplifying scalar multiplication yields the identity.
uses
MeasureTheory.integral_fintype,discrete_poincare_monotone_boolean_prodReallemma discrete_poincare_monotone_boolean_integralFormula (U : Type*) [Fintype U] [DecidableEq U] (p : unitInterval) (h : (U → Bool) → ℝ) : ∫ x, h x ∂(boolean_product_bernoulli U p) = ∑ x, (∏ i, discrete_poincare_monotone_boolean_W p (x i)) * h x := by rw [MeasureTheory.integral_fintype (MeasureTheory.Integrable.of_finite)] refine Finset.sum_congr rfl (fun x _ => ?_) rw [discrete_poincare_monotone_boolean_prodReal] simp [smul_eq_mul]
Fixing a coordinate $q \in U$, configurations on $U \setminus \{q\}$ can be extended by assigning a Boolean value $b$ at $q$; this extension map commutes with coordinate updates and is monotone.
The definition `discrete_poincare_monotone_boolean_ext` takes a configuration $y$ on the subtype of elements different from $q$ and a Boolean $b$, assigning $b$ at $q$ and $y(a)$ at $a \ne q$. Case analysis on indices verifies that evaluating at $q$ gives $b$ (`ext_self`), evaluating at $a \ne q$ gives $y(a)$ (`ext_ne`), updating at $q$ replaces $b$ (`updQ`), and updating at $a \ne q$ commutes with updating $y$ (`updNe`). Coordinate-wise comparison shows that this extension is monotone with respect to $y$ (`monoExt`).
uses
discrete_poincare_monotone_boolean_ext_self,discrete_poincare_monotone_boolean_ext_ne,discrete_poincare_monotone_boolean_updQ,discrete_poincare_monotone_boolean_updNe,discrete_poincare_monotone_boolean_monoExtnoncomputable def discrete_poincare_monotone_boolean_ext (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) : U → Bool := fun a => if h : a = q then b else y ⟨a, h⟩ lemma discrete_poincare_monotone_boolean_ext_self (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) : discrete_poincare_monotone_boolean_ext U q y b q = b := by simp [discrete_poincare_monotone_boolean_ext] lemma discrete_poincare_monotone_boolean_ext_ne (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) (a : U) (ha : a ≠ q) : discrete_poincare_monotone_boolean_ext U q y b a = y ⟨a, ha⟩ := by simp [discrete_poincare_monotone_boolean_ext, ha] lemma discrete_poincare_monotone_boolean_updQ (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b b' : Bool) : Function.update (discrete_poincare_monotone_boolean_ext U q y b) q b' = discrete_poincare_monotone_boolean_ext U q y b' := by funext a by_cases h : a = q · rw [h]; simp [Function.update, discrete_poincare_monotone_boolean_ext] · simp [Function.update, discrete_poincare_monotone_boolean_ext, h] lemma discrete_poincare_monotone_boolean_updNe (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) (a : U) (ha : a ≠ q) (c : Bool) : Function.update (discrete_poincare_monotone_boolean_ext U q y b) a c = discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) b := by funext j by_cases hq : j = q · rw [hq]; simp [Function.update, discrete_poincare_monotone_boolean_ext, (show q ≠ a from fun h => ha h.symm)] · by_cases haj : j = a · rw [haj]; simp [Function.update, discrete_poincare_monotone_boolean_ext, ha] · simp [Function.update, discrete_poincare_monotone_boolean_ext, hq, haj] lemma discrete_poincare_monotone_boolean_monoExt (U : Type*) [DecidableEq U] (q : U) (b : Bool) : Monotone (fun y : {a : U // a ≠ q} → Bool => discrete_poincare_monotone_boolean_ext U q y b) := by intro y y' hy a change discrete_poincare_monotone_boolean_ext U q y b a ≤ discrete_poincare_monotone_boolean_ext U q y' b a by_cases h : a = q · rw [h]; simp [discrete_poincare_monotone_boolean_ext_self] · rw [discrete_poincare_monotone_boolean_ext_ne U q y b a h, discrete_poincare_monotone_boolean_ext_ne U q y' b a h] exact hy ⟨a, h⟩
There is a canonical bijection between $U \to \mathrm{Bool}$ and $(\{a : U // a \ne q\} \to \mathrm{Bool}) \times \mathrm{Bool}$, with inverse given by the configuration extension map.
The equivalence `discrete_poincare_monotone_boolean_split` maps $x$ to the pair $(x|_{U \setminus \{q\}}, x(q))$. Its inverse reconstructs $x$ by extending the restricted configuration with $x(q)$. Case analysis on whether an index equals $q$ verifies that these maps are mutually inverse using `ext_self` and `ext_ne`.
uses
discrete_poincare_monotone_boolean_ext_self,discrete_poincare_monotone_boolean_ext_nenoncomputable def discrete_poincare_monotone_boolean_split (U : Type*) [DecidableEq U] (q : U) : (U → Bool) ≃ ({a : U // a ≠ q} → Bool) × Bool where toFun x := (fun a => x a.1, x q) invFun yb := discrete_poincare_monotone_boolean_ext U q yb.1 yb.2 left_inv x := by funext a by_cases h : a = q · subst h; simp [discrete_poincare_monotone_boolean_ext] · simp [discrete_poincare_monotone_boolean_ext, h] right_inv yb := by obtain ⟨y, b⟩ := yb simp only [Prod.mk.injEq] exact ⟨funext (fun a => discrete_poincare_monotone_boolean_ext_ne U q y b a.1 a.2), discrete_poincare_monotone_boolean_ext_self U q y b⟩ @[simp] lemma discrete_poincare_monotone_boolean_splitSymm (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) : (discrete_poincare_monotone_boolean_split U q).symm (y, b) = discrete_poincare_monotone_boolean_ext U q y b := rfl
Product weights factor across the split $U = (U \setminus \{q\}) \cup \{q\}$, so weighted sums over $U \to \mathrm{Bool}$ decompose into an outer sum over $U \setminus \{q\}$ averaging the false- and true-extensions with weights $1-p$ and $p$.
The product $\prod_{i \in U} W(p, x(i))$ separates into $W(p, x(q))$ times the product over $U \setminus \{q\}$ via `discrete_poincare_monotone_boolean_weightSplit`. Re-indexing the sum along `discrete_poincare_monotone_boolean_split`, grouping by the product type, and summing over Booleans decomposes the sum into extensions with false (weight $1-p$) and true (weight $p$).
uses
discrete_poincare_monotone_boolean_ext_self,discrete_poincare_monotone_boolean_ext_ne,discrete_poincare_monotone_boolean_split,discrete_poincare_monotone_boolean_weightSplitlemma discrete_poincare_monotone_boolean_weightSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (y : {a : U // a ≠ q} → Bool) (b : Bool) : (∏ i : U, discrete_poincare_monotone_boolean_W p (discrete_poincare_monotone_boolean_ext U q y b i)) = (∏ a : {a : U // a ≠ q}, discrete_poincare_monotone_boolean_W p (y a)) * discrete_poincare_monotone_boolean_W p b := by rw [← Finset.mul_prod_erase Finset.univ (fun i => discrete_poincare_monotone_boolean_W p (discrete_poincare_monotone_boolean_ext U q y b i)) (Finset.mem_univ q)] rw [discrete_poincare_monotone_boolean_ext_self, mul_comm] congr 1 rw [Finset.prod_subtype (p := fun a => a ≠ q) (s := Finset.univ.erase q) (by intro x; simp)] exact Finset.prod_congr rfl (fun a _ => by rw [discrete_poincare_monotone_boolean_ext_ne U q y b a.1 a.2]) lemma discrete_poincare_monotone_boolean_sumSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (h : (U → Bool) → ℝ) : ∑ x : U → Bool, (∏ i, discrete_poincare_monotone_boolean_W p (x i)) * h x = ∑ y : {a : U // a ≠ q} → Bool, (∏ a, discrete_poincare_monotone_boolean_W p (y a)) * ((1 - (p:ℝ)) * h (discrete_poincare_monotone_boolean_ext U q y false) + (p:ℝ) * h (discrete_poincare_monotone_boolean_ext U q y true)) := by rw [← Equiv.sum_comp (discrete_poincare_monotone_boolean_split U q).symm (fun x => (∏ i, discrete_poincare_monotone_boolean_W p (x i)) * h x)] rw [Fintype.sum_prod_type] refine Finset.sum_congr rfl (fun y _ => ?_) rw [Fintype.sum_bool] simp only [discrete_poincare_monotone_boolean_splitSymm] rw [discrete_poincare_monotone_boolean_weightSplit U q p y false, discrete_poincare_monotone_boolean_weightSplit U q p y true] simp only [discrete_poincare_monotone_boolean_W, Bool.false_eq_true, if_false, if_true] ring
The integral of $h$ under the product Bernoulli measure splits as $(1-p) \int h(\mathrm{ext}(q, \cdot, \mathrm{false})) + p \int h(\mathrm{ext}(q, \cdot, \mathrm{true}))$ on $U \setminus \{q\}$.
Using `discrete_poincare_monotone_boolean_integralFormula`, the three integrals are rewritten as finite sums. The sum decomposition from `discrete_poincare_monotone_boolean_sumSplit` applies directly, and distributing the coefficients $(1-p)$ and $p$ across the sums verifies equality.
uses
discrete_poincare_monotone_boolean_integralFormula,discrete_poincare_monotone_boolean_sumSplitlemma discrete_poincare_monotone_boolean_integralSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (h : (U → Bool) → ℝ) : ∫ x, h x ∂(boolean_product_bernoulli U p) = (1 - (p:ℝ)) * ∫ y, h (discrete_poincare_monotone_boolean_ext U q y false) ∂(boolean_product_bernoulli {a : U // a ≠ q} p) + (p:ℝ) * ∫ y, h (discrete_poincare_monotone_boolean_ext U q y true) ∂(boolean_product_bernoulli {a : U // a ≠ q} p) := by rw [discrete_poincare_monotone_boolean_integralFormula U p h, discrete_poincare_monotone_boolean_integralFormula {a : U // a ≠ q} p (fun y => h (discrete_poincare_monotone_boolean_ext U q y false)), discrete_poincare_monotone_boolean_integralFormula {a : U // a ≠ q} p (fun y => h (discrete_poincare_monotone_boolean_ext U q y true)), discrete_poincare_monotone_boolean_sumSplit U q p h, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib] exact Finset.sum_congr rfl (fun y _ => by ring)
For any Boolean function $f$, the variance of its real indicator $\mathbb{I}_{f(x)}$ equals $\mu (1 - \mu)$, where $\mu = \mathbb{E}[\mathbb{I}_{f(x)}]$ is its mean.
Because the indicator takes values only in $\{0, 1\}$, its expectation is the measure of the set where it equals $1$ (`integral_of_ae_eq_zero_or_one`), and the measure of the set where it equals $0$ is $1 - \mu$ via `integral_one_sub_of_ae_eq_zero_or_one`. Applying `variance_of_ae_eq_zero_or_one` gives $\mathrm{Var}(\mathbb{I}_{f(x)}) = \mu(1 - \mu)$.
uses
integral_of_ae_eq_zero_or_one,integral_one_sub_of_ae_eq_zero_or_one,variance_of_ae_eq_zero_or_onenoncomputable def discrete_poincare_monotone_boolean_mean (U : Type*) [Fintype U] (f : (U → Bool) → Bool) (p : unitInterval) : ℝ := ∫ x, (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) lemma discrete_poincare_monotone_boolean_varianceEq (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (p : unitInterval) : ProbabilityTheory.variance (fun x => if f x then (1:ℝ) else 0) (boolean_product_bernoulli U p) = discrete_poincare_monotone_boolean_mean U f p * (1 - discrete_poincare_monotone_boolean_mean U f p) := by have hmeas : AEMeasurable (fun x : U → Bool => if f x then (1:ℝ) else 0) (boolean_product_bernoulli U p) := (measurable_of_finite _).aemeasurable have hae : ∀ᵐ ω ∂(boolean_product_bernoulli U p), (if f ω then (1:ℝ) else 0) = 0 ∨ (if f ω then (1:ℝ) else 0) = 1 := by filter_upwards with ω; by_cases h : f ω <;> simp [h] have h1 : discrete_poincare_monotone_boolean_mean U f p = (boolean_product_bernoulli U p).real {ω : U → Bool | (if f ω then (1:ℝ) else 0) = 1} := integral_of_ae_eq_zero_or_one hmeas hae have h0 : (boolean_product_bernoulli U p).real {ω : U → Bool | (if f ω then (1:ℝ) else 0) = 0} = ∫ x, 1 - (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) := (integral_one_sub_of_ae_eq_zero_or_one hmeas hae).symm have hsub : ∫ x, 1 - (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) = 1 - discrete_poincare_monotone_boolean_mean U f p := by rw [integral_sub] · rw [integral_const, discrete_poincare_monotone_boolean_mean]; simp [Measure.real, smul_eq_mul] · exact Integrable.of_finite · exact Integrable.of_finite rw [variance_of_ae_eq_zero_or_one hmeas hae, ← h1, h0, hsub] ring
The expectation of $f(x[q \mapsto c])$ equals the expectation of $f(\mathrm{ext}(q, \cdot, c))$ on $U \setminus \{q\}$, and for $a \ne q$, the expectation of $f(x[a \mapsto c])$ splits into the $(1-p, p)$-mixture of expectations on $U \setminus \{q\}$.
Applying the integral splitting lemma `discrete_poincare_monotone_boolean_integralSplit`: when updating at $q$, the value at $q$ is fixed to $c$ regardless of the conditioning branch by `updQ`, so both branches coincide and $(1-p) + p = 1$ leaves the expectation of $f(\mathrm{ext}(q, \cdot, c))$. When updating at $a \ne q$, the update commutes with extension by `updNe`, producing the weighted combination of integrals of the updated restrictions.
uses
discrete_poincare_monotone_boolean_integralSplit,discrete_poincare_monotone_boolean_updQ,discrete_poincare_monotone_boolean_updNelemma discrete_poincare_monotone_boolean_intUpdQ (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) (c : Bool) : ∫ x, (if f (Function.update x q c) then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) = ∫ y, (if f (discrete_poincare_monotone_boolean_ext U q y c) then (1:ℝ) else 0) ∂(boolean_product_bernoulli {a : U // a ≠ q} p) := by rw [discrete_poincare_monotone_boolean_integralSplit U q p (fun x => if f (Function.update x q c) then (1:ℝ) else 0)] have e1 : (fun y : {a : U // a ≠ q} → Bool => (if f (Function.update (discrete_poincare_monotone_boolean_ext U q y false) q c) then (1:ℝ) else 0)) = (fun y => (if f (discrete_poincare_monotone_boolean_ext U q y c) then (1:ℝ) else 0)) := by funext y; rw [discrete_poincare_monotone_boolean_updQ] have e2 : (fun y : {a : U // a ≠ q} → Bool => (if f (Function.update (discrete_poincare_monotone_boolean_ext U q y true) q c) then (1:ℝ) else 0)) = (fun y => (if f (discrete_poincare_monotone_boolean_ext U q y c) then (1:ℝ) else 0)) := by funext y; rw [discrete_poincare_monotone_boolean_updQ] rw [e1, e2, ← add_mul] have : (1 - (p:ℝ)) + (p:ℝ) = 1 := by ring rw [this, one_mul] lemma discrete_poincare_monotone_boolean_intUpdNe (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) (a : U) (ha : a ≠ q) (c : Bool) : ∫ x, (if f (Function.update x a c) then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) = (1 - (p:ℝ)) * ∫ y, (if f (discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) false) then (1:ℝ) else 0) ∂(boolean_product_bernoulli {b : U // b ≠ q} p) + (p:ℝ) * ∫ y, (if f (discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) true) then (1:ℝ) else 0) ∂(boolean_product_bernoulli {b : U // b ≠ q} p) := by rw [discrete_poincare_monotone_boolean_integralSplit U q p (fun x => if f (Function.update x a c) then (1:ℝ) else 0)] have e1 : (fun y : {b : U // b ≠ q} → Bool => (if f (Function.update (discrete_poincare_monotone_boolean_ext U q y false) a c) then (1:ℝ) else 0)) = (fun y => (if f (discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) false) then (1:ℝ) else 0)) := by funext y; rw [discrete_poincare_monotone_boolean_updNe] have e2 : (fun y : {b : U // b ≠ q} → Bool => (if f (Function.update (discrete_poincare_monotone_boolean_ext U q y true) a c) then (1:ℝ) else 0)) = (fun y => (if f (discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) true) then (1:ℝ) else 0)) := by funext y; rw [discrete_poincare_monotone_boolean_updNe] rw [e1, e2]
The influence of coordinate $q$ equals the difference of conditioned means $\mu_1 - \mu_0$, and for $a \ne q$, the influence decomposes as $(1-p) \mathrm{Inf}_a(f_0) + p \mathrm{Inf}_a(f_1)$.
By definition, the influence of coordinate $i$ is the difference between the expectation with coordinate $i$ set to true and with $i$ set to false (`discrete_poincare_monotone_boolean_infSub`). At $q$, substituting `intUpdQ` gives $\mu_1 - \mu_0$. At $a \ne q$, substituting `intUpdNe` into both terms and rearranging coefficients shows that the influence on $U$ is the convex combination of influences on the restrictions $f_0$ and $f_1$.
uses
discrete_poincare_monotone_boolean_infSub,discrete_poincare_monotone_boolean_intUpdQ,discrete_poincare_monotone_boolean_intUpdNenoncomputable def discrete_poincare_monotone_boolean_S (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (i : U) (c : Bool) (p : unitInterval) : ℝ := ∫ x, (if f (Function.update x i c) then (1 : ℝ) else 0) ∂(boolean_product_bernoulli U p) lemma discrete_poincare_monotone_boolean_infSub (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (i : U) (p : unitInterval) : boolean_influence U f i p = discrete_poincare_monotone_boolean_S U f i true p - discrete_poincare_monotone_boolean_S U f i false p := by simp only [boolean_influence, discrete_poincare_monotone_boolean_S] exact integral_sub Integrable.of_finite Integrable.of_finite lemma discrete_poincare_monotone_boolean_infSplitQ (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) : boolean_influence U f q p = discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p - discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p := by rw [discrete_poincare_monotone_boolean_infSub] have h1 : discrete_poincare_monotone_boolean_S U f q true p = discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p := discrete_poincare_monotone_boolean_intUpdQ U q p f true have h2 : discrete_poincare_monotone_boolean_S U f q false p = discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p := discrete_poincare_monotone_boolean_intUpdQ U q p f false rw [h1, h2] lemma discrete_poincare_monotone_boolean_infSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) (a : U) (ha : a ≠ q) : boolean_influence U f a p = (1 - (p:ℝ)) * boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) ⟨a, ha⟩ p + (p:ℝ) * boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) ⟨a, ha⟩ p := by rw [discrete_poincare_monotone_boolean_infSub, discrete_poincare_monotone_boolean_infSub, discrete_poincare_monotone_boolean_infSub] have e1 := discrete_poincare_monotone_boolean_intUpdNe U q p f a ha true have e2 := discrete_poincare_monotone_boolean_intUpdNe U q p f a ha false simp only [discrete_poincare_monotone_boolean_S] rw [e1, e2] ring
The mean satisfies $\mu = (1-p)\mu_0 + p\mu_1$, lies in $[0, 1]$, and satisfies $\mu_0 \le \mu_1$ whenever $f$ is monotone.
The mean decomposition `meanSplit` is an immediate specialization of `integralSplit`. The bounds $0 \le \mu \le 1$ follow from nonnegativity and comparison with $\int 1 = 1$. When $f$ is monotone, setting coordinate $q$ to false is pointwise bounded by setting it to true; applying $f$ and integrating both sides preserves the inequality by `discrete_poincare_monotone_boolean_boolLe`, establishing $\mu_0 \le \mu_1$.
uses
discrete_poincare_monotone_boolean_integralSplit,discrete_poincare_monotone_boolean_ext_self,discrete_poincare_monotone_boolean_ext_ne,discrete_poincare_monotone_boolean_boolLelemma discrete_poincare_monotone_boolean_meanSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) : discrete_poincare_monotone_boolean_mean U f p = (1 - (p:ℝ)) * discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p + (p:ℝ) * discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p := discrete_poincare_monotone_boolean_integralSplit U q p (fun x => if f x then (1:ℝ) else 0) lemma discrete_poincare_monotone_boolean_meanBounds (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (p : unitInterval) : 0 ≤ discrete_poincare_monotone_boolean_mean U f p ∧ discrete_poincare_monotone_boolean_mean U f p ≤ 1 := by constructor · exact integral_nonneg (fun x => by by_cases h : f x <;> simp [h]) · have h2 : ∫ x, (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) ≤ ∫ _x : U → Bool, (1:ℝ) ∂(boolean_product_bernoulli U p) := by apply integral_mono Integrable.of_finite Integrable.of_finite intro x; by_cases h : f x <;> simp [h] rw [show discrete_poincare_monotone_boolean_mean U f p = ∫ x, (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) from rfl] rwa [show (∫ _x : U → Bool, (1:ℝ) ∂(boolean_product_bernoulli U p)) = 1 by rw [integral_const]; simp] at h2 lemma discrete_poincare_monotone_boolean_boolLe : ∀ a b : Bool, a ≤ b → (if a then (1:ℝ) else 0) ≤ (if b then (1:ℝ) else 0) := by intro a b hab match a, b, hab with | true, true, _ => simp | false, true, _ => simp | false, false, _ => simp | true, false, h => exact absurd h (by decide) lemma discrete_poincare_monotone_boolean_meanMono (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) (hf : Monotone f) : discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p ≤ discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p := by apply integral_mono Integrable.of_finite Integrable.of_finite intro y have hle : discrete_poincare_monotone_boolean_ext U q y false ≤ discrete_poincare_monotone_boolean_ext U q y true := by intro a by_cases h : a = q · rw [h]; simp [discrete_poincare_monotone_boolean_ext_self] · rw [discrete_poincare_monotone_boolean_ext_ne U q y false a h, discrete_poincare_monotone_boolean_ext_ne U q y true a h] exact discrete_poincare_monotone_boolean_boolLe _ _ (hf hle)
If $p \in [0, 1]$, $0 \le m_0 \le m_1 \le 1$, and $m_k(1 - m_k) \le p(1-p)S_k$ for $k \in \{0, 1\}$, then $((1-p)m_0 + pm_1)(1 - ((1-p)m_0 + pm_1)) \le p(1-p)((m_1 - m_0) + (1-p)S_0 + pS_1)$. automation
Expanding the LHS yields $(1-p)m_0(1-m_0) + pm_1(1-m_1) + p(1-p)(m_1 - m_0)^2$. Since $0 \le m_1 - m_0 \le 1$, we have $(m_1 - m_0)^2 \le m_1 - m_0$. Scaling the two inductive hypotheses by $1-p$ and $p$ and adding this inequality yields the bound, which `nlinarith` verifies automatically.
lemma discrete_poincare_monotone_boolean_keyIneq (p m0 m1 S0 S1 : ℝ) (hp0 : 0 ≤ p) (hp1 : p ≤ 1) (hm0 : 0 ≤ m0) (hm01 : m0 ≤ m1) (hm1 : m1 ≤ 1) (h0 : m0 * (1 - m0) ≤ p * (1 - p) * S0) (h1 : m1 * (1 - m1) ≤ p * (1 - p) * S1) : ((1 - p) * m0 + p * m1) * (1 - ((1 - p) * m0 + p * m1)) ≤ p * (1 - p) * ((m1 - m0) + ((1 - p) * S0 + p * S1)) := by have hq : (0:ℝ) ≤ 1 - p := by linarith have hpq : (0:ℝ) ≤ p * (1 - p) := mul_nonneg hp0 hq have hx0 : (0:ℝ) ≤ m1 - m0 := by linarith have hx1 : m1 - m0 ≤ 1 := by linarith have hC : p * (1 - p) * (m1 - m0) ^ 2 ≤ p * (1 - p) * (m1 - m0) := by have := mul_nonneg hpq (mul_nonneg hx0 (by linarith : (0:ℝ) ≤ 1 - (m1 - m0))) nlinarith have hA := mul_le_mul_of_nonneg_left h0 hq have hB := mul_le_mul_of_nonneg_left h1 hp0 nlinarith [hA, hB, hC]
When $|U| = 0$, the Poincaré inequality holds trivially since both variance and influences vanish.
We set up strong induction on $n = |U|$ with `Nat.strong_induction_on`. If $n = 0$, $U$ is empty by `Fintype.card_eq_zero_iff`, so there is only one configuration. The indicator function is therefore constant, having variance $0$ by `discrete_poincare_monotone_boolean_varianceEq`, and the sum of influences is empty, which evaluates to $0$. Thus $0 \le 0$ holds.
uses
Nat.strong_induction_on,Fintype.card_eq_zero_iff,discrete_poincare_monotone_boolean_varianceEqlemma discrete_poincare_monotone_boolean_aux : ∀ (n : ℕ) (U : Type*) [Fintype U] [DecidableEq U], Fintype.card U = n → ∀ (f : (U → Bool) → Bool), Monotone f → ∀ p : unitInterval, ProbabilityTheory.variance (fun x => if f x then (1 : ℝ) else 0) (boolean_product_bernoulli U p) ≤ (p : ℝ) * (1 - (p : ℝ)) * ∑ i : U, boolean_influence U f i p := by intro n induction n using Nat.strong_induction_on with | _ n ih => intro U instF instD hcard f hf p rcases Nat.eq_zero_or_pos n with hn | hn · have hise : IsEmpty U := Fintype.card_eq_zero_iff.mp (hcard.trans hn) letI := hise have hX : (fun x : U → Bool => (if f x then (1:ℝ) else 0)) = fun _ => (if f (fun a => isEmptyElim a) then (1:ℝ) else 0) := by funext x rw [Subsingleton.elim x (fun a => isEmptyElim a)] rw [discrete_poincare_monotone_boolean_varianceEq] have hm : discrete_poincare_monotone_boolean_mean U f p = (if f (fun a => isEmptyElim a) then (1:ℝ) else 0) := by have h2 : discrete_poincare_monotone_boolean_mean U f p = ∫ x, (if f (fun a => isEmptyElim a) then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) := by simp only [discrete_poincare_monotone_boolean_mean]; rw [hX] rw [h2, integral_const]; simp rw [hm] have hsum0 : (∑ i : U, boolean_influence U f i p) = 0 := by rw [Finset.univ_eq_empty]; simp rw [hsum0] by_cases hc : f (fun a => isEmptyElim a) <;> simp [hc]
When $|U| > 0$, the Poincaré inequality holds on $U$ by the induction hypothesis on $U \setminus \{q\}$ and `discrete_poincare_monotone_boolean_keyIneq`, proving the main theorem.
Since $n > 0$, $U$ is nonempty (`Fintype.card_pos_iff`), so we pick an element $q \in U$. The subtype $V = \{b : U // b \ne q\}$ has cardinality $n - 1 < n$ by `Fintype.card_subtype_lt`. Applying the induction hypothesis to the restrictions $f_0$ and $f_1$, which remain monotone by `discrete_poincare_monotone_boolean_monoExt`, gives variance bounds for both. The total influence decomposes into $\mathrm{Inf}_q(f) = \mu_1 - \mu_0$ (`infSplitQ`) plus the sum over $V$, which decomposes into $(1-p) \sum \mathrm{Inf}(f_0) + p \sum \mathrm{Inf}(f_1)$ via `infSplit`. Expressing $\mathrm{Var}(f)$ in terms of its mean via `varianceEq` and `meanSplit`, applying `discrete_poincare_monotone_boolean_keyIneq` completes the induction step `aux`. Specializing `discrete_poincare_monotone_boolean_aux` to $n = |U|$ concludes the main theorem.
uses
Fintype.card_pos_iff,Fintype.card_subtype_lt,discrete_poincare_monotone_boolean_monoExt,discrete_poincare_monotone_boolean_varianceEq,discrete_poincare_monotone_boolean_meanBounds,discrete_poincare_monotone_boolean_meanMono,discrete_poincare_monotone_boolean_infSplit,discrete_poincare_monotone_boolean_infSplitQ,discrete_poincare_monotone_boolean_meanSplit,discrete_poincare_monotone_boolean_keyIneq,discrete_poincare_monotone_boolean_aux· obtain ⟨q⟩ : Nonempty U := Fintype.card_pos_iff.mp (by rw [hcard]; exact hn) have hcardV : Fintype.card {b : U // b ≠ q} < n := by rw [← hcard] exact Fintype.card_subtype_lt (p := fun b => b ≠ q) (x := q) (by simp) have ih0 := ih (Fintype.card {b : U // b ≠ q}) hcardV {b : U // b ≠ q} rfl (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) (hf.comp (discrete_poincare_monotone_boolean_monoExt U q false)) p rw [discrete_poincare_monotone_boolean_varianceEq] at ih0 have ih1 := ih (Fintype.card {b : U // b ≠ q}) hcardV {b : U // b ≠ q} rfl (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) (hf.comp (discrete_poincare_monotone_boolean_monoExt U q true)) p rw [discrete_poincare_monotone_boolean_varianceEq] at ih1 have hb0 := discrete_poincare_monotone_boolean_meanBounds {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p have hb1 := discrete_poincare_monotone_boolean_meanBounds {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p have hmono := discrete_poincare_monotone_boolean_meanMono U q p f hf have hVsum : (∑ i : {b : U // b ≠ q}, boolean_influence U f i.1 p) = (1 - (p:ℝ)) * (∑ i : {b : U // b ≠ q}, boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) i p) + (p:ℝ) * (∑ i : {b : U // b ≠ q}, boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) i p) := by rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib] exact Finset.sum_congr rfl (fun i _ => discrete_poincare_monotone_boolean_infSplit U q p f i.1 i.2) have hinfl : (∑ i : U, boolean_influence U f i p) = (discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p - discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p) + ((1 - (p:ℝ)) * (∑ i : {b : U // b ≠ q}, boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) i p) + (p:ℝ) * (∑ i : {b : U // b ≠ q}, boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) i p)) := by have hsplit : (∑ i : U, boolean_influence U f i p) = boolean_influence U f q p + ∑ i : {b : U // b ≠ q}, boolean_influence U f i.1 p := by rw [← Finset.add_sum_erase Finset.univ (fun i => boolean_influence U f i p) (Finset.mem_univ q)] congr 1 rw [Finset.sum_subtype (p := fun b => b ≠ q) (s := Finset.univ.erase q) (by intro x; simp)] rw [hsplit, discrete_poincare_monotone_boolean_infSplitQ U q p f, hVsum] have hmean := discrete_poincare_monotone_boolean_meanSplit U q p f rw [discrete_poincare_monotone_boolean_varianceEq, hmean, hinfl] exact discrete_poincare_monotone_boolean_keyIneq (p:ℝ) _ _ _ _ p.2.1 p.2.2 hb0.1 hmono hb1.2 ih0 ih1 /-- Discrete Poincare inequality for monotone Boolean functions under the product Bernoulli measure. -/ theorem discrete_poincare_monotone_boolean (U : Type*) [Fintype U] [Nonempty U] [DecidableEq U] (f : (U → Bool) → Bool) (hf : Monotone f) (p : unitInterval) : ProbabilityTheory.variance (fun x ↦ if f x then (1 : ℝ) else 0) (boolean_product_bernoulli U p) ≤ (p : ℝ) * (1 - (p : ℝ)) * ∑ i : U, boolean_influence U f i p := discrete_poincare_monotone_boolean_aux (Fintype.card U) U rfl f hf p
bernoulliMeasure_real_apply_of_notMem_of_mem- For a measurable set $s$ such that $x ∉ s$ and $y ∈ s$, the Bernoulli measure on $\{x, y\}$ with parameter $p$ assigns real measure $1 - p$ to $s$.
bernoulliMeasure_real_apply_of_mem_of_notMem- For a measurable set $s$ such that $x ∈ s$ and $y ∉ s$, the Bernoulli measure on $\{x, y\}$ with parameter $p$ assigns real measure $p$ to $s$.
Measure.pi_singleton- The product measure of a singleton configuration $\{f\}$ equals the product over coordinates of the marginal measures of $\{f(i)\}$.
ENNReal.toReal_prod- The real value of a finite product of extended nonnegative reals equals the product of their real values.
discrete_poincare_monotone_boolean_bernW- The real Bernoulli measure of a single Boolean $\{b\}$ equals the Bernoulli weight $W(p, b)$.
MeasureTheory.integral_fintype- The integral of a function over a finite type with respect to a measure equals the sum of its values weighted by the singleton measures.
discrete_poincare_monotone_boolean_prodReal- The real product Bernoulli measure of a configuration $\{x\}$ on $U \to \mathrm{Bool}$ equals $\prod_{i \in U} W(p, x(i))$.
discrete_poincare_monotone_boolean_ext_self- The configuration extension $\mathrm{ext}(q, y, b)$ evaluated at coordinate $q$ equals $b$.
discrete_poincare_monotone_boolean_ext_ne- For $a \ne q$, the configuration extension $\mathrm{ext}(q, y, b)$ evaluated at coordinate $a$ equals $y(a)$.
discrete_poincare_monotone_boolean_updQ- Updating the configuration extension $\mathrm{ext}(q, y, b)$ at coordinate $q$ to value $b'$ yields $\mathrm{ext}(q, y, b')$.
discrete_poincare_monotone_boolean_updNe- Updating the configuration extension $\mathrm{ext}(q, y, b)$ at coordinate $a \ne q$ to value $c$ equals $\mathrm{ext}(q, y[a \mapsto c], b)$.
discrete_poincare_monotone_boolean_monoExt- For any fixed Boolean $b$, the extension map $y \mapsto \mathrm{ext}(q, y, b)$ from $\{a : U // a \ne q\} \to \mathrm{Bool}$ to $U \to \mathrm{Bool}$ is monotone.
discrete_poincare_monotone_boolean_split- The canonical equivalence between configurations on $U$ and pairs consisting of a configuration on $U \setminus \{q\}$ and a Boolean value at $q$.
discrete_poincare_monotone_boolean_weightSplit- The product weight of an extended configuration $\mathrm{ext}(q, y, b)$ factors into the product weight of $y$ on $U \setminus \{q\}$ and the single-bit weight $W(p, b)$.
discrete_poincare_monotone_boolean_sumSplit- A product-weighted sum over $U \to \mathrm{Bool}$ decomposes into a sum over configurations $y$ on $U \setminus \{q\}$ of the $(1-p, p)$-weighted combination of $h(\mathrm{ext}(q, y, \mathrm{false}))$ and $h(\mathrm{ext}(q, y, \mathrm{true}))$.
discrete_poincare_monotone_boolean_integralFormula- The integral of $h$ under the product Bernoulli measure on $U \to \mathrm{Bool}$ equals $\sum_x (\prod_i W(p, x(i))) h(x)$.
integral_of_ae_eq_zero_or_one- For an almost-everywhere $\{0, 1\}$-valued random variable $X$, its integral equals the real measure of the event $\{X = 1\}$.
integral_one_sub_of_ae_eq_zero_or_one- For an almost-everywhere $\{0, 1\}$-valued random variable $X$, the integral of $1 - X$ equals the real measure of the event $\{X = 0\}$.
variance_of_ae_eq_zero_or_one- The variance of an almost-everywhere $\{0, 1\}$-valued random variable $X$ equals $\mu(X = 0) \cdot \mu(X = 1)$.
discrete_poincare_monotone_boolean_varianceEq- The variance of the real indicator of a Boolean function $f$ under the product Bernoulli measure equals $\mu(1 - \mu)$, where $\mu$ is its expectation.
discrete_poincare_monotone_boolean_integralSplit- The integral of $h$ under the product Bernoulli measure splits as $(1-p)$ times the integral of $h(\mathrm{ext}(q, \cdot, \mathrm{false}))$ plus $p$ times the integral of $h(\mathrm{ext}(q, \cdot, \mathrm{true}))$ on $U \setminus \{q\}$.
discrete_poincare_monotone_boolean_intUpdQ- The integral of the indicator of $f(x[q \mapsto c])$ equals the integral of the indicator of $f(\mathrm{ext}(q, \cdot, c))$ under the product measure on $U \setminus \{q\}$.
discrete_poincare_monotone_boolean_intUpdNe- For $a \ne q$, the integral of the indicator of $f(x[a \mapsto c])$ decomposes into the $(1-p, p)$-mixture of integrals of the restrictions with coordinate $a$ updated.
discrete_poincare_monotone_boolean_infSub- The Boolean influence of coordinate $i$ on $f$ equals the difference between the expectation with coordinate $i$ set to true and the expectation with $i$ set to false.
discrete_poincare_monotone_boolean_infSplitQ- The Boolean influence of coordinate $q$ equals the difference between the restricted mean with $q$ set to true and the restricted mean with $q$ set to false.
discrete_poincare_monotone_boolean_infSplit- For $a \ne q$, the Boolean influence of coordinate $a$ on $f$ is $(1-p)$ times its influence on the false-restriction plus $p$ times its influence on the true-restriction.
discrete_poincare_monotone_boolean_meanSplit- The expectation of a Boolean function $f$ on $U$ is $(1-p)$ times the expectation of its false-restriction plus $p$ times the expectation of its true-restriction.
discrete_poincare_monotone_boolean_meanBounds- The expectation of the indicator of any Boolean function under the product Bernoulli measure lies in $[0, 1]$.
discrete_poincare_monotone_boolean_meanMono- For a monotone Boolean function $f$, the expectation of its false-restriction on $U \setminus \{q\}$ is less than or equal to the expectation of its true-restriction.
discrete_poincare_monotone_boolean_boolLe- If $a \le b$ in $\mathrm{Bool}$, then the real indicator $(a \text{ ? } 1 : 0)$ is at most $(b \text{ ? } 1 : 0)$.
discrete_poincare_monotone_boolean_keyIneq- If $p \in [0, 1]$, $0 \le m_0 \le m_1 \le 1$, and $m_k(1 - m_k) \le p(1-p)S_k$ for $k \in \{0, 1\}$, then $((1-p)m_0 + pm_1)(1 - ((1-p)m_0 + pm_1)) \le p(1-p)((m_1 - m_0) + (1-p)S_0 + pS_1)$.
Nat.strong_induction_on- Strong induction on the natural numbers: to prove $P(n)$ for all $n$, it suffices to show that $(\forall m < n, P(m)) \implies P(n)$.
Fintype.card_eq_zero_iff- A finite type has cardinality zero if and only if it is empty.
Fintype.card_pos_iff- A finite type has strictly positive cardinality if and only if it is nonempty.
Fintype.card_subtype_lt- For any element $x$ of a finite type $U$, the subtype of elements different from $x$ has strictly smaller cardinality than $U$.
discrete_poincare_monotone_boolean_aux- The auxiliary statement asserting that for every natural number $n$, any finite type $U$ of cardinality $n$, and any monotone Boolean function $f$, the discrete Poincaré inequality holds.
- The core algebraic step `discrete_poincare_monotone_boolean_keyIneq` is discharged via nonlinear arithmetic (`nlinarith`), which automatically expands the variance of the mixture and combines $(m_1 - m_0)^2 ≤ m_1 - m_0$ with the two scaled inductive hypotheses.
- Configurations on $U \setminus \{q\}$ are formalized using the subtype `{a : U // a ≠ q}`, requiring explicit helper functions and lemmas (`ext`, `updQ`, `updNe`, `monoExt`, and `split`) to translate between functions on $U$ and functions on the punctured domain.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
open MeasureTheory ProbabilityTheoryopen scoped BigOperatorsnoncomputable def discrete_poincare_monotone_boolean_W (p : unitInterval) (b : Bool) : ℝ := if b then (p : ℝ) else 1 - (p : ℝ)lemma discrete_poincare_monotone_boolean_bernW (p : unitInterval) (b : Bool) : (bernoulliMeasure true false p).real {b} = discrete_poincare_monotone_boolean_W p b := by cases b · rw [discrete_poincare_monotone_boolean_W, if_neg (by simp)] exact bernoulliMeasure_real_apply_of_notMem_of_mem p (measurableSet_singleton false) (by simp) (by simp) · rw [discrete_poincare_monotone_boolean_W, if_pos rfl] exact bernoulliMeasure_real_apply_of_mem_of_notMem p (measurableSet_singleton true) (by simp) (by simp)lemma discrete_poincare_monotone_boolean_prodReal (U : Type*) [Fintype U] (p : unitInterval) (x : U → Bool) : (boolean_product_bernoulli U p).real {x} = ∏ i, discrete_poincare_monotone_boolean_W p (x i) := by rw [boolean_product_bernoulli, Measure.real_def, Measure.pi_singleton, ENNReal.toReal_prod (Finset.univ) (fun i => (bernoulliMeasure true false p) {x i})] exact Finset.prod_congr rfl (fun i _ => discrete_poincare_monotone_boolean_bernW p (x i))lemma discrete_poincare_monotone_boolean_integralFormula (U : Type*) [Fintype U] [DecidableEq U] (p : unitInterval) (h : (U → Bool) → ℝ) : ∫ x, h x ∂(boolean_product_bernoulli U p) = ∑ x, (∏ i, discrete_poincare_monotone_boolean_W p (x i)) * h x := by rw [MeasureTheory.integral_fintype (MeasureTheory.Integrable.of_finite)] refine Finset.sum_congr rfl (fun x _ => ?_) rw [discrete_poincare_monotone_boolean_prodReal] simp [smul_eq_mul]noncomputable def discrete_poincare_monotone_boolean_ext (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) : U → Bool := fun a => if h : a = q then b else y ⟨a, h⟩lemma discrete_poincare_monotone_boolean_ext_self (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) : discrete_poincare_monotone_boolean_ext U q y b q = b := by simp [discrete_poincare_monotone_boolean_ext]lemma discrete_poincare_monotone_boolean_ext_ne (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) (a : U) (ha : a ≠ q) : discrete_poincare_monotone_boolean_ext U q y b a = y ⟨a, ha⟩ := by simp [discrete_poincare_monotone_boolean_ext, ha]lemma discrete_poincare_monotone_boolean_updQ (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b b' : Bool) : Function.update (discrete_poincare_monotone_boolean_ext U q y b) q b' = discrete_poincare_monotone_boolean_ext U q y b' := by funext a by_cases h : a = q · rw [h]; simp [Function.update, discrete_poincare_monotone_boolean_ext] · simp [Function.update, discrete_poincare_monotone_boolean_ext, h]lemma discrete_poincare_monotone_boolean_updNe (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) (a : U) (ha : a ≠ q) (c : Bool) : Function.update (discrete_poincare_monotone_boolean_ext U q y b) a c = discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) b := by funext j by_cases hq : j = q · rw [hq]; simp [Function.update, discrete_poincare_monotone_boolean_ext, (show q ≠ a from fun h => ha h.symm)] · by_cases haj : j = a · rw [haj]; simp [Function.update, discrete_poincare_monotone_boolean_ext, ha] · simp [Function.update, discrete_poincare_monotone_boolean_ext, hq, haj]lemma discrete_poincare_monotone_boolean_monoExt (U : Type*) [DecidableEq U] (q : U) (b : Bool) : Monotone (fun y : {a : U // a ≠ q} → Bool => discrete_poincare_monotone_boolean_ext U q y b) := by intro y y' hy a change discrete_poincare_monotone_boolean_ext U q y b a ≤ discrete_poincare_monotone_boolean_ext U q y' b a by_cases h : a = q · rw [h]; simp [discrete_poincare_monotone_boolean_ext_self] · rw [discrete_poincare_monotone_boolean_ext_ne U q y b a h, discrete_poincare_monotone_boolean_ext_ne U q y' b a h] exact hy ⟨a, h⟩noncomputable def discrete_poincare_monotone_boolean_split (U : Type*) [DecidableEq U] (q : U) : (U → Bool) ≃ ({a : U // a ≠ q} → Bool) × Bool where toFun x := (fun a => x a.1, x q) invFun yb := discrete_poincare_monotone_boolean_ext U q yb.1 yb.2 left_inv x := by funext a by_cases h : a = q · subst h; simp [discrete_poincare_monotone_boolean_ext] · simp [discrete_poincare_monotone_boolean_ext, h] right_inv yb := by obtain ⟨y, b⟩ := yb simp only [Prod.mk.injEq] exact ⟨funext (fun a => discrete_poincare_monotone_boolean_ext_ne U q y b a.1 a.2), discrete_poincare_monotone_boolean_ext_self U q y b⟩@[simp] lemma discrete_poincare_monotone_boolean_splitSymm (U : Type*) [DecidableEq U] (q : U) (y : {a : U // a ≠ q} → Bool) (b : Bool) : (discrete_poincare_monotone_boolean_split U q).symm (y, b) = discrete_poincare_monotone_boolean_ext U q y b := rfllemma discrete_poincare_monotone_boolean_weightSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (y : {a : U // a ≠ q} → Bool) (b : Bool) : (∏ i : U, discrete_poincare_monotone_boolean_W p (discrete_poincare_monotone_boolean_ext U q y b i)) = (∏ a : {a : U // a ≠ q}, discrete_poincare_monotone_boolean_W p (y a)) * discrete_poincare_monotone_boolean_W p b := by rw [← Finset.mul_prod_erase Finset.univ (fun i => discrete_poincare_monotone_boolean_W p (discrete_poincare_monotone_boolean_ext U q y b i)) (Finset.mem_univ q)] rw [discrete_poincare_monotone_boolean_ext_self, mul_comm] congr 1 rw [Finset.prod_subtype (p := fun a => a ≠ q) (s := Finset.univ.erase q) (by intro x; simp)] exact Finset.prod_congr rfl (fun a _ => by rw [discrete_poincare_monotone_boolean_ext_ne U q y b a.1 a.2])lemma discrete_poincare_monotone_boolean_sumSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (h : (U → Bool) → ℝ) : ∑ x : U → Bool, (∏ i, discrete_poincare_monotone_boolean_W p (x i)) * h x = ∑ y : {a : U // a ≠ q} → Bool, (∏ a, discrete_poincare_monotone_boolean_W p (y a)) * ((1 - (p:ℝ)) * h (discrete_poincare_monotone_boolean_ext U q y false) + (p:ℝ) * h (discrete_poincare_monotone_boolean_ext U q y true)) := by rw [← Equiv.sum_comp (discrete_poincare_monotone_boolean_split U q).symm (fun x => (∏ i, discrete_poincare_monotone_boolean_W p (x i)) * h x)] rw [Fintype.sum_prod_type] refine Finset.sum_congr rfl (fun y _ => ?_) rw [Fintype.sum_bool] simp only [discrete_poincare_monotone_boolean_splitSymm] rw [discrete_poincare_monotone_boolean_weightSplit U q p y false, discrete_poincare_monotone_boolean_weightSplit U q p y true] simp only [discrete_poincare_monotone_boolean_W, Bool.false_eq_true, if_false, if_true] ringlemma discrete_poincare_monotone_boolean_integralSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (h : (U → Bool) → ℝ) : ∫ x, h x ∂(boolean_product_bernoulli U p) = (1 - (p:ℝ)) * ∫ y, h (discrete_poincare_monotone_boolean_ext U q y false) ∂(boolean_product_bernoulli {a : U // a ≠ q} p) + (p:ℝ) * ∫ y, h (discrete_poincare_monotone_boolean_ext U q y true) ∂(boolean_product_bernoulli {a : U // a ≠ q} p) := by rw [discrete_poincare_monotone_boolean_integralFormula U p h, discrete_poincare_monotone_boolean_integralFormula {a : U // a ≠ q} p (fun y => h (discrete_poincare_monotone_boolean_ext U q y false)), discrete_poincare_monotone_boolean_integralFormula {a : U // a ≠ q} p (fun y => h (discrete_poincare_monotone_boolean_ext U q y true)), discrete_poincare_monotone_boolean_sumSplit U q p h, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib] exact Finset.sum_congr rfl (fun y _ => by ring)noncomputable def discrete_poincare_monotone_boolean_mean (U : Type*) [Fintype U] (f : (U → Bool) → Bool) (p : unitInterval) : ℝ := ∫ x, (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p)lemma discrete_poincare_monotone_boolean_varianceEq (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (p : unitInterval) : ProbabilityTheory.variance (fun x => if f x then (1:ℝ) else 0) (boolean_product_bernoulli U p) = discrete_poincare_monotone_boolean_mean U f p * (1 - discrete_poincare_monotone_boolean_mean U f p) := by have hmeas : AEMeasurable (fun x : U → Bool => if f x then (1:ℝ) else 0) (boolean_product_bernoulli U p) := (measurable_of_finite _).aemeasurable have hae : ∀ᵐ ω ∂(boolean_product_bernoulli U p), (if f ω then (1:ℝ) else 0) = 0 ∨ (if f ω then (1:ℝ) else 0) = 1 := by filter_upwards with ω; by_cases h : f ω <;> simp [h] have h1 : discrete_poincare_monotone_boolean_mean U f p = (boolean_product_bernoulli U p).real {ω : U → Bool | (if f ω then (1:ℝ) else 0) = 1} := integral_of_ae_eq_zero_or_one hmeas hae have h0 : (boolean_product_bernoulli U p).real {ω : U → Bool | (if f ω then (1:ℝ) else 0) = 0} = ∫ x, 1 - (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) := (integral_one_sub_of_ae_eq_zero_or_one hmeas hae).symm have hsub : ∫ x, 1 - (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) = 1 - discrete_poincare_monotone_boolean_mean U f p := by rw [integral_sub] · rw [integral_const, discrete_poincare_monotone_boolean_mean]; simp [Measure.real, smul_eq_mul] · exact Integrable.of_finite · exact Integrable.of_finite rw [variance_of_ae_eq_zero_or_one hmeas hae, ← h1, h0, hsub] ringlemma discrete_poincare_monotone_boolean_intUpdQ (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) (c : Bool) : ∫ x, (if f (Function.update x q c) then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) = ∫ y, (if f (discrete_poincare_monotone_boolean_ext U q y c) then (1:ℝ) else 0) ∂(boolean_product_bernoulli {a : U // a ≠ q} p) := by rw [discrete_poincare_monotone_boolean_integralSplit U q p (fun x => if f (Function.update x q c) then (1:ℝ) else 0)] have e1 : (fun y : {a : U // a ≠ q} → Bool => (if f (Function.update (discrete_poincare_monotone_boolean_ext U q y false) q c) then (1:ℝ) else 0)) = (fun y => (if f (discrete_poincare_monotone_boolean_ext U q y c) then (1:ℝ) else 0)) := by funext y; rw [discrete_poincare_monotone_boolean_updQ] have e2 : (fun y : {a : U // a ≠ q} → Bool => (if f (Function.update (discrete_poincare_monotone_boolean_ext U q y true) q c) then (1:ℝ) else 0)) = (fun y => (if f (discrete_poincare_monotone_boolean_ext U q y c) then (1:ℝ) else 0)) := by funext y; rw [discrete_poincare_monotone_boolean_updQ] rw [e1, e2, ← add_mul] have : (1 - (p:ℝ)) + (p:ℝ) = 1 := by ring rw [this, one_mul]lemma discrete_poincare_monotone_boolean_intUpdNe (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) (a : U) (ha : a ≠ q) (c : Bool) : ∫ x, (if f (Function.update x a c) then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) = (1 - (p:ℝ)) * ∫ y, (if f (discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) false) then (1:ℝ) else 0) ∂(boolean_product_bernoulli {b : U // b ≠ q} p) + (p:ℝ) * ∫ y, (if f (discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) true) then (1:ℝ) else 0) ∂(boolean_product_bernoulli {b : U // b ≠ q} p) := by rw [discrete_poincare_monotone_boolean_integralSplit U q p (fun x => if f (Function.update x a c) then (1:ℝ) else 0)] have e1 : (fun y : {b : U // b ≠ q} → Bool => (if f (Function.update (discrete_poincare_monotone_boolean_ext U q y false) a c) then (1:ℝ) else 0)) = (fun y => (if f (discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) false) then (1:ℝ) else 0)) := by funext y; rw [discrete_poincare_monotone_boolean_updNe] have e2 : (fun y : {b : U // b ≠ q} → Bool => (if f (Function.update (discrete_poincare_monotone_boolean_ext U q y true) a c) then (1:ℝ) else 0)) = (fun y => (if f (discrete_poincare_monotone_boolean_ext U q (Function.update y ⟨a, ha⟩ c) true) then (1:ℝ) else 0)) := by funext y; rw [discrete_poincare_monotone_boolean_updNe] rw [e1, e2]noncomputable def discrete_poincare_monotone_boolean_S (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (i : U) (c : Bool) (p : unitInterval) : ℝ := ∫ x, (if f (Function.update x i c) then (1 : ℝ) else 0) ∂(boolean_product_bernoulli U p)lemma discrete_poincare_monotone_boolean_infSub (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (i : U) (p : unitInterval) : boolean_influence U f i p = discrete_poincare_monotone_boolean_S U f i true p - discrete_poincare_monotone_boolean_S U f i false p := by simp only [boolean_influence, discrete_poincare_monotone_boolean_S] exact integral_sub Integrable.of_finite Integrable.of_finitelemma discrete_poincare_monotone_boolean_infSplitQ (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) : boolean_influence U f q p = discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p - discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p := by rw [discrete_poincare_monotone_boolean_infSub] have h1 : discrete_poincare_monotone_boolean_S U f q true p = discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p := discrete_poincare_monotone_boolean_intUpdQ U q p f true have h2 : discrete_poincare_monotone_boolean_S U f q false p = discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p := discrete_poincare_monotone_boolean_intUpdQ U q p f false rw [h1, h2]lemma discrete_poincare_monotone_boolean_infSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) (a : U) (ha : a ≠ q) : boolean_influence U f a p = (1 - (p:ℝ)) * boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) ⟨a, ha⟩ p + (p:ℝ) * boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) ⟨a, ha⟩ p := by rw [discrete_poincare_monotone_boolean_infSub, discrete_poincare_monotone_boolean_infSub, discrete_poincare_monotone_boolean_infSub] have e1 := discrete_poincare_monotone_boolean_intUpdNe U q p f a ha true have e2 := discrete_poincare_monotone_boolean_intUpdNe U q p f a ha false simp only [discrete_poincare_monotone_boolean_S] rw [e1, e2] ringlemma discrete_poincare_monotone_boolean_meanSplit (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) : discrete_poincare_monotone_boolean_mean U f p = (1 - (p:ℝ)) * discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p + (p:ℝ) * discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p := discrete_poincare_monotone_boolean_integralSplit U q p (fun x => if f x then (1:ℝ) else 0)lemma discrete_poincare_monotone_boolean_meanBounds (U : Type*) [Fintype U] [DecidableEq U] (f : (U → Bool) → Bool) (p : unitInterval) : 0 ≤ discrete_poincare_monotone_boolean_mean U f p ∧ discrete_poincare_monotone_boolean_mean U f p ≤ 1 := by constructor · exact integral_nonneg (fun x => by by_cases h : f x <;> simp [h]) · have h2 : ∫ x, (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) ≤ ∫ _x : U → Bool, (1:ℝ) ∂(boolean_product_bernoulli U p) := by apply integral_mono Integrable.of_finite Integrable.of_finite intro x; by_cases h : f x <;> simp [h] rw [show discrete_poincare_monotone_boolean_mean U f p = ∫ x, (if f x then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) from rfl] rwa [show (∫ _x : U → Bool, (1:ℝ) ∂(boolean_product_bernoulli U p)) = 1 by rw [integral_const]; simp] at h2lemma discrete_poincare_monotone_boolean_boolLe : ∀ a b : Bool, a ≤ b → (if a then (1:ℝ) else 0) ≤ (if b then (1:ℝ) else 0) := by intro a b hab match a, b, hab with | true, true, _ => simp | false, true, _ => simp | false, false, _ => simp | true, false, h => exact absurd h (by decide)lemma discrete_poincare_monotone_boolean_meanMono (U : Type*) [Fintype U] [DecidableEq U] (q : U) (p : unitInterval) (f : (U → Bool) → Bool) (hf : Monotone f) : discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p ≤ discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p := by apply integral_mono Integrable.of_finite Integrable.of_finite intro y have hle : discrete_poincare_monotone_boolean_ext U q y false ≤ discrete_poincare_monotone_boolean_ext U q y true := by intro a by_cases h : a = q · rw [h]; simp [discrete_poincare_monotone_boolean_ext_self] · rw [discrete_poincare_monotone_boolean_ext_ne U q y false a h, discrete_poincare_monotone_boolean_ext_ne U q y true a h] exact discrete_poincare_monotone_boolean_boolLe _ _ (hf hle)lemma discrete_poincare_monotone_boolean_keyIneq (p m0 m1 S0 S1 : ℝ) (hp0 : 0 ≤ p) (hp1 : p ≤ 1) (hm0 : 0 ≤ m0) (hm01 : m0 ≤ m1) (hm1 : m1 ≤ 1) (h0 : m0 * (1 - m0) ≤ p * (1 - p) * S0) (h1 : m1 * (1 - m1) ≤ p * (1 - p) * S1) : ((1 - p) * m0 + p * m1) * (1 - ((1 - p) * m0 + p * m1)) ≤ p * (1 - p) * ((m1 - m0) + ((1 - p) * S0 + p * S1)) := by have hq : (0:ℝ) ≤ 1 - p := by linarith have hpq : (0:ℝ) ≤ p * (1 - p) := mul_nonneg hp0 hq have hx0 : (0:ℝ) ≤ m1 - m0 := by linarith have hx1 : m1 - m0 ≤ 1 := by linarith have hC : p * (1 - p) * (m1 - m0) ^ 2 ≤ p * (1 - p) * (m1 - m0) := by have := mul_nonneg hpq (mul_nonneg hx0 (by linarith : (0:ℝ) ≤ 1 - (m1 - m0))) nlinarith have hA := mul_le_mul_of_nonneg_left h0 hq have hB := mul_le_mul_of_nonneg_left h1 hp0 nlinarith [hA, hB, hC]lemma discrete_poincare_monotone_boolean_aux : ∀ (n : ℕ) (U : Type*) [Fintype U] [DecidableEq U], Fintype.card U = n → ∀ (f : (U → Bool) → Bool), Monotone f → ∀ p : unitInterval, ProbabilityTheory.variance (fun x => if f x then (1 : ℝ) else 0) (boolean_product_bernoulli U p) ≤ (p : ℝ) * (1 - (p : ℝ)) * ∑ i : U, boolean_influence U f i p := by intro n induction n using Nat.strong_induction_on with | _ n ih => intro U instF instD hcard f hf p rcases Nat.eq_zero_or_pos n with hn | hn · have hise : IsEmpty U := Fintype.card_eq_zero_iff.mp (hcard.trans hn) letI := hise have hX : (fun x : U → Bool => (if f x then (1:ℝ) else 0)) = fun _ => (if f (fun a => isEmptyElim a) then (1:ℝ) else 0) := by funext x rw [Subsingleton.elim x (fun a => isEmptyElim a)] rw [discrete_poincare_monotone_boolean_varianceEq] have hm : discrete_poincare_monotone_boolean_mean U f p = (if f (fun a => isEmptyElim a) then (1:ℝ) else 0) := by have h2 : discrete_poincare_monotone_boolean_mean U f p = ∫ x, (if f (fun a => isEmptyElim a) then (1:ℝ) else 0) ∂(boolean_product_bernoulli U p) := by simp only [discrete_poincare_monotone_boolean_mean]; rw [hX] rw [h2, integral_const]; simp rw [hm] have hsum0 : (∑ i : U, boolean_influence U f i p) = 0 := by rw [Finset.univ_eq_empty]; simp rw [hsum0] by_cases hc : f (fun a => isEmptyElim a) <;> simp [hc] · obtain ⟨q⟩ : Nonempty U := Fintype.card_pos_iff.mp (by rw [hcard]; exact hn) have hcardV : Fintype.card {b : U // b ≠ q} < n := by rw [← hcard] exact Fintype.card_subtype_lt (p := fun b => b ≠ q) (x := q) (by simp) have ih0 := ih (Fintype.card {b : U // b ≠ q}) hcardV {b : U // b ≠ q} rfl (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) (hf.comp (discrete_poincare_monotone_boolean_monoExt U q false)) p rw [discrete_poincare_monotone_boolean_varianceEq] at ih0 have ih1 := ih (Fintype.card {b : U // b ≠ q}) hcardV {b : U // b ≠ q} rfl (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) (hf.comp (discrete_poincare_monotone_boolean_monoExt U q true)) p rw [discrete_poincare_monotone_boolean_varianceEq] at ih1 have hb0 := discrete_poincare_monotone_boolean_meanBounds {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p have hb1 := discrete_poincare_monotone_boolean_meanBounds {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p have hmono := discrete_poincare_monotone_boolean_meanMono U q p f hf have hVsum : (∑ i : {b : U // b ≠ q}, boolean_influence U f i.1 p) = (1 - (p:ℝ)) * (∑ i : {b : U // b ≠ q}, boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) i p) + (p:ℝ) * (∑ i : {b : U // b ≠ q}, boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) i p) := by rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib] exact Finset.sum_congr rfl (fun i _ => discrete_poincare_monotone_boolean_infSplit U q p f i.1 i.2) have hinfl : (∑ i : U, boolean_influence U f i p) = (discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) p - discrete_poincare_monotone_boolean_mean {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) p) + ((1 - (p:ℝ)) * (∑ i : {b : U // b ≠ q}, boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y false)) i p) + (p:ℝ) * (∑ i : {b : U // b ≠ q}, boolean_influence {b : U // b ≠ q} (fun y => f (discrete_poincare_monotone_boolean_ext U q y true)) i p)) := by have hsplit : (∑ i : U, boolean_influence U f i p) = boolean_influence U f q p + ∑ i : {b : U // b ≠ q}, boolean_influence U f i.1 p := by rw [← Finset.add_sum_erase Finset.univ (fun i => boolean_influence U f i p) (Finset.mem_univ q)] congr 1 rw [Finset.sum_subtype (p := fun b => b ≠ q) (s := Finset.univ.erase q) (by intro x; simp)] rw [hsplit, discrete_poincare_monotone_boolean_infSplitQ U q p f, hVsum] have hmean := discrete_poincare_monotone_boolean_meanSplit U q p f rw [discrete_poincare_monotone_boolean_varianceEq, hmean, hinfl] exact discrete_poincare_monotone_boolean_keyIneq (p:ℝ) _ _ _ _ p.2.1 p.2.2 hb0.1 hmono hb1.2 ih0 ih1/-- Discrete Poincare inequality for monotone Boolean functions under the product Bernoulli measure. -/theorem discrete_poincare_monotone_boolean (U : Type*) [Fintype U] [Nonempty U] [DecidableEq U] (f : (U → Bool) → Bool) (hf : Monotone f) (p : unitInterval) : ProbabilityTheory.variance (fun x ↦ if f x then (1 : ℝ) else 0) (boolean_product_bernoulli U p) ≤ (p : ℝ) * (1 - (p : ℝ)) * ∑ i : U, boolean_influence U f i p := discrete_poincare_monotone_boolean_aux (Fintype.card U) U rfl f hf p