AFTD Auto-Formalizing Theoretical Domains

discrete_poincare_monotone_boolean

theoremverifiedformalization

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 LinearOrder is a TotalPreorder.
  • boolean_product_bernoulli_isProbabilityMeasureFor any finite type $U$ and parameter $p \in [0, 1]$ in unitInterval, the product Bernoulli measure boolean_product_bernoulli U p on…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

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]$.

  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.

    lines 1–14

    uses bernoulliMeasure_real_apply_of_notMem_of_mem, bernoulliMeasure_real_apply_of_mem_of_notMem

    open 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)
    
  2. 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`.

    lines 15–21

    uses Measure.pi_singleton, ENNReal.toReal_prod, discrete_poincare_monotone_boolean_bernW

    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))
    
  3. 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.

    lines 22–30

    uses MeasureTheory.integral_fintype, discrete_poincare_monotone_boolean_prodReal

    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]
    
  4. 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`).

    lines 31–77

    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_monoExt

    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⟩
    
  5. 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`.

    lines 78–97

    uses discrete_poincare_monotone_boolean_ext_self, discrete_poincare_monotone_boolean_ext_ne

    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 := rfl
    
  6. 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$).

    lines 98–130

    uses discrete_poincare_monotone_boolean_ext_self, discrete_poincare_monotone_boolean_ext_ne, discrete_poincare_monotone_boolean_split, discrete_poincare_monotone_boolean_weightSplit

    lemma 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
    
  7. 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.

    lines 131–146

    uses discrete_poincare_monotone_boolean_integralFormula, discrete_poincare_monotone_boolean_sumSplit

    lemma 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)
    
  8. 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)$.

    lines 147–177

    uses integral_of_ae_eq_zero_or_one, integral_one_sub_of_ae_eq_zero_or_one, variance_of_ae_eq_zero_or_one

    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]
      ring
    
  9. 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.

    lines 178–223

    uses discrete_poincare_monotone_boolean_integralSplit, discrete_poincare_monotone_boolean_updQ, discrete_poincare_monotone_boolean_updNe

    lemma 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]
    
  10. 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$.

    lines 224–268

    uses discrete_poincare_monotone_boolean_infSub, discrete_poincare_monotone_boolean_intUpdQ, discrete_poincare_monotone_boolean_intUpdNe

    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_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
    
  11. 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$.

    lines 269–318

    uses discrete_poincare_monotone_boolean_integralSplit, discrete_poincare_monotone_boolean_ext_self, discrete_poincare_monotone_boolean_ext_ne, discrete_poincare_monotone_boolean_boolLe

    lemma 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)
    
  12. 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.

    lines 319–335

    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]
    
  13. 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.

    lines 336–363

    uses Nat.strong_induction_on, Fintype.card_eq_zero_iff, discrete_poincare_monotone_boolean_varianceEq

    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]
  14. 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.

    lines 364–416

    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.

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

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