AFTD Auto-Formalizing Theoretical Domains

finite_lopsided_function_product_bound

theoremverified

An abstract finite-set function with nonnegative values, decreasing event increments and local negative-dependency bounds satisfies the finite asymmetric local-lemma product bound.

Statement

theorem finite_lopsided_function_product_bound
    {I : Type*} [Fintype I] [DecidableEq I]
    (F : Finset I → ℝ) (N : I → Finset I) (p x : I → ℝ)
    (hF : ∀ S, 0 ≤ F S)
    (hinc : ∀ i S T, S ⊆ T → i ∉ T →
      F T - F (insert i T) ≤ F S - F (insert i S))
    (hdep : ∀ i S, i ∉ S → Disjoint S (N i) →
      F S - F (insert i S) ≤ p i * F S)
    (hx0 : ∀ i, 0 ≤ x i) (hx1 : ∀ i, x i < 1)
    (hprob : ∀ i, p i ≤ x i * ∏ j ∈ N i, (1 - x j)) :
    (∏ i, (1 - x i)) * F ∅ ≤ F Finset.univ
Source
Algebraic helper for the finite negative-dependency local lemma; EJC 14 (2007) R63, DOI 10.37236/981, Lemma 3. Independent finite-function proof of the standard induction, with no external Lean code copied.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof establishes the local-lemma product bound by combining a chain rule for telescoping decrements with strong induction over subsets. First, an auxiliary lemma `chain` proves by induction that single-step conditional bounds F(T) - F(T ∪ {i}) ≤ x(i) F(T) accumulate into a product bound (∏_{i ∈ V} (1 - x(i))) F(S \ V) ≤ F(S) for any subset V ⊆ S. Second, an auxiliary lemma `cond` proves by strong induction on S that the single-step bound holds universally, by restricting to K = S \ N(i), applying the dependency condition and local lemma bounds, and bounding F(K) via the chain rule on S \ K. Finally, specializing the chain rule to S = V = Finset.univ yields the product bound.

  1. The chain-rule lemma `chain` holds in the base case V = ∅.

    We formulate the auxiliary lemma `chain`: if single-step decrements satisfy F(T) - F(T ∪ {i}) ≤ x(i) F(T) for all proper subsets T ⊂ S and i ∉ T, then for any subset V ⊆ S, the product satisfies (∏_{j ∈ V} (1 - x(j))) F(S \ V) ≤ F(S). We proceed by induction on V using `Finset.induction_on`. In the base case V = ∅, the empty product is 1 and S \ ∅ = S, so the inequality reduces to F(S) ≤ F(S), which closes by simplification.

    lines 12–18

    uses Finset.induction_on

      classical
      have chain : ∀ S : Finset I,
          (∀ T ⊂ S, ∀ i ∉ T, F T - F (insert i T) ≤ x i * F T) →
          ∀ V ⊆ S, (∏ i ∈ V, (1 - x i)) * F (S \ V) ≤ F S := by
        intro S hs V
        induction V using Finset.induction_on with
        | empty => intro _; simp
  2. In the inductive step of `chain`, the set S \ (insert i V) is a strict subset of S that does not contain i.

    Assume the claim holds for V, and consider insert i V ⊆ S with i ∉ V. We obtain i ∈ S via `Finset.mem_insert_self` and V ⊆ S via `Finset.subset_insert`. By definition of set difference, i ∉ S \ insert i V. Since i ∈ S and i ∉ S \ insert i V, `Finset.ssubset_iff_of_subset` applied to the subset relation `Finset.sdiff_subset` proves that S \ insert i V is a strict subset of S.

    lines 19–25

    uses Finset.mem_insert_self, Finset.subset_insert, Finset.sdiff_subset, Finset.ssubset_iff_of_subset

        | @insert i V hi ih =>
          intro hsub
          have hiS := hsub (Finset.mem_insert_self _ _)
          have hVS : V ⊆ S := (Finset.subset_insert _ _).trans hsub
          have hiT : i ∉ S \ insert i V := by simp
          have hproper : S \ insert i V ⊂ S :=
            (Finset.ssubset_iff_of_subset Finset.sdiff_subset).2 ⟨i, hiS, hiT⟩
  3. The set identity insert i (S \ insert i V) = S \ V holds.

    We verify the equality by showing an arbitrary element j belongs to the left-hand set if and only if it belongs to S \ V. In the forward direction, if j = i, then j ∈ S and j ∉ V; if j ∈ S \ insert i V, then j ∈ S and j ∉ V ∪ {i}, so j ∉ V. In the reverse direction, if j ∈ S \ V, case analysis on whether j = i shows that j is either the inserted element i or belongs to S \ insert i V.

    lines 26–36

    uses Finset.mem_insert, Finset.mem_sdiff, Or.inr, Or.inl

          have heq : insert i (S \ insert i V) = S \ V := by
            ext j
            simp only [Finset.mem_insert, Finset.mem_sdiff]
            constructor
            · rintro (rfl | ⟨hjS, hjV⟩)
              · exact ⟨hiS, hi⟩
              · exact ⟨hjS, fun h => hjV (Or.inr h)⟩
            · rintro ⟨hjS, hjV⟩
              by_cases hji : j = i
              · exact Or.inl hji
              · exact Or.inr ⟨hjS, by simpa [hji] using hjV⟩
  4. The induction step of `chain` holds, accumulating the factor (1 - x(i)).

    Since S \ insert i V ⊂ S and i ∉ S \ insert i V, applying the hypothesis hs to this proper subset and rewriting with the set identity yields (1 - x(i)) F(S \ insert i V) ≤ F(S \ V). Each 1 - x(j) is nonnegative because x(j) < 1, so the product over V is nonnegative by `Finset.prod_nonneg`. Multiplying the single-step inequality by this product using `mul_le_mul_of_nonneg_left` and applying the induction hypothesis ih completes the induction.

    lines 37–46

    uses Finset.prod_nonneg, Finset.prod_insert, mul_le_mul_of_nonneg_left

          have hstep := hs _ hproper i hiT
          rw [heq] at hstep
          have hprod : 0 ≤ ∏ j ∈ V, (1 - x j) :=
            Finset.prod_nonneg (fun j _ => by linarith [hx1 j])
          rw [Finset.prod_insert hi]
          calc (1 - x i) * (∏ j ∈ V, (1 - x j)) * F (S \ insert i V)
              = (∏ j ∈ V, (1 - x j)) * ((1 - x i) * F (S \ insert i V)) := by ring
            _ ≤ (∏ j ∈ V, (1 - x j)) * F (S \ V) :=
              mul_le_mul_of_nonneg_left (by linarith) hprod
            _ ≤ F S := ih hVS
  5. The single-step conditional decrement bound F(S) - F(insert i S) ≤ x(i) F(S) holds for all S and i ∉ S.

    We formulate the auxiliary lemma `cond` and proceed by strong induction on S using `Finset.strongInduction`. The induction hypothesis ih states that the decrement bound holds for all strict subsets T ⊂ S and elements outside T.

    lines 47–52

    uses Finset.strongInduction

      have cond : ∀ S : Finset I, ∀ i ∉ S,
          F S - F (insert i S) ≤ x i * F S := by
        intro S
        induction S using Finset.strongInduction with
        | H S ih =>
          intro i hi
  6. The set K = S \ N(i) is disjoint from N(i), excludes i, and satisfies S \ K ⊆ N(i).

    Define K = S \ N(i) ⊆ S. Since i ∉ S and K ⊆ S, we have i ∉ K. By definition of set difference, every element of K lies outside N(i), so K and N(i) are disjoint by `Finset.disjoint_left.mpr`. Furthermore, if j ∈ S \ K, then j ∈ S and j ∉ K; if j were not in N(i), it would belong to S \ N(i) = K, a contradiction, so S \ K ⊆ N(i).

    lines 53–64

    uses Finset.sdiff_subset, Finset.disjoint_left.mpr, Finset.mem_sdiff.mp, Finset.mem_sdiff.mpr

          let K := S \ N i
          have hKS : K ⊆ S := Finset.sdiff_subset
          have hiK : i ∉ K := fun h => hi (hKS h)
          have hd : Disjoint K (N i) := by
            apply Finset.disjoint_left.mpr
            intro j hj hjN
            exact (Finset.mem_sdiff.mp hj).2 hjN
          have hsub : S \ K ⊆ N i := by
            intro j hj
            by_contra hjN
            exact (Finset.mem_sdiff.mp hj).2
              (Finset.mem_sdiff.mpr ⟨(Finset.mem_sdiff.mp hj).1, hjN⟩)
  7. The product over N(i) is bounded by that over S \ K, and `chain` bounds F(K).

    Because S \ K ⊆ N(i) and each 1 - x(j) is in [0, 1], `Finset.prod_le_prod_of_subset_of_le_one` shows that ∏_{j ∈ N(i)} (1 - x(j)) ≤ ∏_{j ∈ S \ K} (1 - x(j)). Applying `chain` to S, the induction hypothesis ih, and the subset S \ K ⊆ S, followed by simplifying S \ (S \ K) to K via `Finset.sdiff_sdiff_eq_self`, proves that (∏_{j ∈ S \ K} (1 - x(j))) F(K) ≤ F(S).

    lines 65–69

    uses Finset.prod_le_prod_of_subset_of_le_one, Finset.sdiff_subset, Finset.sdiff_sdiff_eq_self

          have hprod : (∏ j ∈ N i, (1 - x j)) ≤ ∏ j ∈ S \ K, (1 - x j) :=
            Finset.prod_le_prod_of_subset_of_le_one hsub
              (fun j _ => by linarith [hx1 j]) (fun j _ _ => by linarith [hx0 j])
          have hc := chain S ih (S \ K) Finset.sdiff_subset
          rw [Finset.sdiff_sdiff_eq_self hKS] at hc
  8. The single-step decrement satisfies F(S) - F(insert i S) ≤ x(i) F(S), completing the induction for `cond`.

    By decreasing increments (`hinc`), F(S) - F(insert i S) ≤ F(K) - F(insert i K) because K ⊆ S. Since K is disjoint from N(i), the dependency condition (`hdep`) bounds this by p(i) F(K). Substituting the local lemma condition (`hprob`), expanding the product bound via `mul_le_mul_of_nonneg_left` and `mul_le_mul_of_nonneg_right`, and applying the chain bound on F(K) yields x(i) F(S).

    lines 70–78

    uses mul_le_mul_of_nonneg_right, mul_le_mul_of_nonneg_left

          calc F S - F (insert i S)
              ≤ F K - F (insert i K) := hinc i K S hKS hi
            _ ≤ p i * F K := hdep i K hiK hd
            _ ≤ (x i * ∏ j ∈ N i, (1 - x j)) * F K :=
              mul_le_mul_of_nonneg_right (hprob i) (hF K)
            _ ≤ (x i * ∏ j ∈ S \ K, (1 - x j)) * F K :=
              mul_le_mul_of_nonneg_right (mul_le_mul_of_nonneg_left hprod (hx0 i)) (hF K)
            _ = x i * ((∏ j ∈ S \ K, (1 - x j)) * F K) := by ring
            _ ≤ x i * F S := mul_le_mul_of_nonneg_left hc (hx0 i)
  9. The finite asymmetric local-lemma product bound holds: (∏_i (1 - x(i))) F(∅) ≤ F(Finset.univ).

    We instantiate `chain` with S = Finset.univ and V = Finset.univ. The induction hypothesis of `chain` is supplied for all proper subsets by `cond`. The resulting inequality (∏_{i ∈ Finset.univ} (1 - x(i))) F(Finset.univ \ Finset.univ) ≤ F(Finset.univ) simplifies to (∏_i (1 - x(i))) F(∅) ≤ F(Finset.univ) using `simpa`.

    line 79

      simpa using chain Finset.univ (fun T _ => cond T) Finset.univ (fun _ h => h)
Finset.mem_insert_self
An element a belongs to insert a s.
Finset.subset_insert
Any finset s is a subset of insert a s.
Finset.sdiff_subset
The set difference s \ t is a subset of s.
Finset.ssubset_iff_of_subset
If s₁ ⊆ s₂, then s₁ ⊂ s₂ is a strict subset if and only if there exists some element in s₂ that is not in s₁.
Finset.induction_on
Induction principle on finsets: to prove a property for all finsets, it suffices to prove it for the empty set and show it is preserved when inserting a fresh element.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Or.inr
Injects a proof of the right disjunct into a disjunction a ∨ b.
Or.inl
Injects a proof of the left disjunct into a disjunction a ∨ b.
Finset.prod_nonneg
The product of nonnegative terms over a finite set is nonnegative.
Finset.prod_insert
If a ∉ s, the product over insert a s equals the term at a multiplied by the product over s.
mul_le_mul_of_nonneg_left
Multiplying an inequality on the left by a nonnegative element preserves the inequality.
Finset.strongInduction
Strong induction principle for finsets: a property holds for all finsets if it holds for any finset whenever it holds for all its strict subsets.
Finset.disjoint_left.mpr
Two finsets are disjoint if every element of the first finset is not an element of the second.
Finset.mem_sdiff.mp
If an element is in s \ t, then it is in s and not in t.
Finset.mem_sdiff.mpr
If an element is in s and not in t, then it is in s \ t.
Finset.prod_le_prod_of_subset_of_le_one
If s ⊆ t, all terms in t are nonnegative, and all terms in t \ s are at most 1, then the product over t is at most the product over s.
Finset.sdiff_sdiff_eq_self
If t ⊆ s, the double complement s \ (s \ t) equals t.
mul_le_mul_of_nonneg_right
Multiplying an inequality on the right by a nonnegative element preserves the inequality.

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

theorem finite_lopsided_function_product_bound    {I : Type*} [Fintype I] [DecidableEq I]    (F : Finset I → ℝ) (N : I → Finset I) (p x : I → ℝ)    (hF : ∀ S, 0 ≤ F S)    (hinc : ∀ i S T, S ⊆ T → i ∉ T →      F T - F (insert i T) ≤ F S - F (insert i S))    (hdep : ∀ i S, i ∉ S → Disjoint S (N i) →      F S - F (insert i S) ≤ p i * F S)    (hx0 : ∀ i, 0 ≤ x i) (hx1 : ∀ i, x i < 1)    (hprob : ∀ i, p i ≤ x i * ∏ j ∈ N i, (1 - x j)) :    (∏ i, (1 - x i)) * F ∅ ≤ F Finset.univ := by  classical  have chain : ∀ S : Finset I,      (∀ T ⊂ S, ∀ i ∉ T, F T - F (insert i T) ≤ x i * F T) →      ∀ V ⊆ S, (∏ i ∈ V, (1 - x i)) * F (S \ V) ≤ F S := by    intro S hs V    induction V using Finset.induction_on with    | empty => intro _; simp    | @insert i V hi ih =>      intro hsub      have hiS := hsub (Finset.mem_insert_self _ _)      have hVS : V ⊆ S := (Finset.subset_insert _ _).trans hsub      have hiT : i ∉ S \ insert i V := by simp      have hproper : S \ insert i V ⊂ S :=        (Finset.ssubset_iff_of_subset Finset.sdiff_subset).2 ⟨i, hiS, hiT⟩      have heq : insert i (S \ insert i V) = S \ V := by        ext j        simp only [Finset.mem_insert, Finset.mem_sdiff]        constructor        · rintro (rfl | ⟨hjS, hjV⟩)          · exact ⟨hiS, hi⟩          · exact ⟨hjS, fun h => hjV (Or.inr h)⟩        · rintro ⟨hjS, hjV⟩          by_cases hji : j = i          · exact Or.inl hji          · exact Or.inr ⟨hjS, by simpa [hji] using hjV⟩      have hstep := hs _ hproper i hiT      rw [heq] at hstep      have hprod : 0 ≤ ∏ j ∈ V, (1 - x j) :=        Finset.prod_nonneg (fun j _ => by linarith [hx1 j])      rw [Finset.prod_insert hi]      calc (1 - x i) * (∏ j ∈ V, (1 - x j)) * F (S \ insert i V)          = (∏ j ∈ V, (1 - x j)) * ((1 - x i) * F (S \ insert i V)) := by ring        _ ≤ (∏ j ∈ V, (1 - x j)) * F (S \ V) :=          mul_le_mul_of_nonneg_left (by linarith) hprod        _ ≤ F S := ih hVS  have cond : ∀ S : Finset I, ∀ i ∉ S,      F S - F (insert i S) ≤ x i * F S := by    intro S    induction S using Finset.strongInduction with    | H S ih =>      intro i hi      let K := S \ N i      have hKS : K ⊆ S := Finset.sdiff_subset      have hiK : i ∉ K := fun h => hi (hKS h)      have hd : Disjoint K (N i) := by        apply Finset.disjoint_left.mpr        intro j hj hjN        exact (Finset.mem_sdiff.mp hj).2 hjN      have hsub : S \ K ⊆ N i := by        intro j hj        by_contra hjN        exact (Finset.mem_sdiff.mp hj).2          (Finset.mem_sdiff.mpr ⟨(Finset.mem_sdiff.mp hj).1, hjN⟩)      have hprod : (∏ j ∈ N i, (1 - x j)) ≤ ∏ j ∈ S \ K, (1 - x j) :=        Finset.prod_le_prod_of_subset_of_le_one hsub          (fun j _ => by linarith [hx1 j]) (fun j _ _ => by linarith [hx0 j])      have hc := chain S ih (S \ K) Finset.sdiff_subset      rw [Finset.sdiff_sdiff_eq_self hKS] at hc      calc F S - F (insert i S)          ≤ F K - F (insert i K) := hinc i K S hKS hi        _ ≤ p i * F K := hdep i K hiK hd        _ ≤ (x i * ∏ j ∈ N i, (1 - x j)) * F K :=          mul_le_mul_of_nonneg_right (hprob i) (hF K)        _ ≤ (x i * ∏ j ∈ S \ K, (1 - x j)) * F K :=          mul_le_mul_of_nonneg_right (mul_le_mul_of_nonneg_left hprod (hx0 i)) (hF K)        _ = x i * ((∏ j ∈ S \ K, (1 - x j)) * F K) := by ring        _ ≤ x i * F S := mul_le_mul_of_nonneg_left hc (hx0 i)  simpa using chain Finset.univ (fun T _ => cond T) Finset.univ (fun _ h => h)
See it in the graphDiscuss this resultChallenge it