finite_lopsided_function_product_bound
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
- finite_lopsided_avoidance_of_card_boundIn a nonempty finite probability universe, finite bad events satisfying the negative-dependency cardinality inequalities and asymmetric…
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.
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.
uses
Finset.induction_onclassical 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
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.
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⟩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.
uses
Finset.mem_insert,Finset.mem_sdiff,Or.inr,Or.inlhave 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⟩
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.
uses
Finset.prod_nonneg,Finset.prod_insert,mul_le_mul_of_nonneg_lefthave 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
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.
uses
Finset.strongInductionhave 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
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).
uses
Finset.sdiff_subset,Finset.disjoint_left.mpr,Finset.mem_sdiff.mp,Finset.mem_sdiff.mprlet 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⟩)
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).
uses
Finset.prod_le_prod_of_subset_of_le_one,Finset.sdiff_subset,Finset.sdiff_sdiff_eq_selfhave 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
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).
uses
mul_le_mul_of_nonneg_right,mul_le_mul_of_nonneg_leftcalc 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)
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`.
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.
- Elementary linear inequalities and sign conditions are verified automatically by `linarith`, polynomial rearrangements by `ring`, and the final set-difference simplification `univ \ univ = ∅` by `simpa`.
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.
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)