Lemma 16.15 — the Lovász Local Lemma, symmetric form
ProvedAppliedComb.ManyFaces.local_lemma_symmetricLet be a finite probability space and a finite family of events. For each let be a subfamily such that is independent of any event not in , that is, for every with and . Let and be real numbers with and , and suppose that
where is the base of the natural logarithm. Then
so the probability that all events of fail is positive.
This is the form in which the local lemma is usually applied: it needs only a uniform bound on the probabilities and on the number of dependencies.
Formalization Note. The page's displayed conclusion, , mentions and , which the lemma never introduces, and its gloss reads "the probability that all events in is positive". The book's proof sets and applies Lemma 16.14 with ; the statement is that reading: the explicit bound , with Fintype.card ι, together with positivity. The probability space is a Fintype Ω with the discrete σ-algebra and a probability measure μ, so every subset is an event, as in the book's definition (p. 214). The family is indexed by a finite type ι (repetitions allowed), and N i is a Finset ι with i ∉ N i. The independence hypothesis is IndepOutside.
import Mathlib import Definitions.Def_AppliedComb_ManyFaces_IndepOutside
namespace AppliedComb.ManyFaces
open MeasureTheory
/-- Lemma 16.15, the Lovász Local Lemma, symmetric form (Keller & Trotter, *Applied
Combinatorics* (2017 Edition), p. 328). `(Ω, μ)` is a finite probability space, the family is
`A : ι → Set Ω` with `𝓝(A i) = N i ⊆ ι \ {i}` and each `A i` independent of any event not in
`𝓝(A i)`. If `0 < p < 1`, `d ≥ 1`, `P(A i) ≤ p` and `|N i| ≤ d` for every `i`, and
`e · p · (d + 1) < 1`, then the probability that all events of the family fail is positive.
The page's displayed conclusion is misprinted; with the choice `x(E) = 1/(d + 1)` made in the
book's proof it reads `P(∏_{i} Ā_i) ≥ (1 − 1/(d + 1))^{|𝓕|}`, which is stated together with the
positivity. -/
theorem local_lemma_symmetric {Ω ι : Type*} [Fintype Ω] [MeasurableSpace Ω]
[DiscreteMeasurableSpace Ω] [Fintype ι] (μ : Measure Ω) [IsProbabilityMeasure μ]
(p d : ℝ) (hp : 0 < p ∧ p < 1) (hd : 1 ≤ d)
(A : ι → Set Ω) (N : ι → Finset ι) (hN : ∀ i, i ∉ N i)
(hind : ∀ i, IndepOutside μ A N i)
(hPp : ∀ i, μ.real (A i) ≤ p) (hNd : ∀ i, ((N i).card : ℝ) ≤ d)
(he : Real.exp 1 * p * (d + 1) < 1) :
(1 - 1 / (d + 1)) ^ Fintype.card ι ≤ μ.real (allFail A Finset.univ) ∧
0 < μ.real (allFail A Finset.univ) := by sorry
end AppliedComb.ManyFaces
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting.
- is a finite type equipped with the -algebra in which every subset is measurable.
- is a probability measure on , so and all values are finite reals.
- is a finite index type, with elements.
- and are real numbers, not required to be integers.
- is a family of subsets of .
- assigns to each a finite set . No symmetry between different is assumed.
Hypotheses.
- .
- .
- for every .
- For every and every with and ,
The intersection over is taken to be . 5. for every . 6. for every . 7. , where .
Conclusion. Both of the following hold:
Degenerate cases.
- Redundant bound. Hypotheses (2) and (7) together force , so the condition in (1) is implied.
- Empty . The intersection over the empty family is , of measure . The lower bound is , and the conclusion reads and .
- Empty . This is excluded, since is a probability measure.
- One-element .
- Every event has measure or .
- Hypothesis (5) with forces every .
- Therefore the intersection of complements is , and the conclusion is together with .
- Ill-defined values. All measures are finite, so the conversion to real numbers loses nothing. Since , the base lies in and no division by zero arises.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.