Lemma 16.14 — the Lovász Local Lemma, asymmetric form
ProvedAppliedComb.ManyFaces.local_lemma_asymmetricLet be a finite probability space and a finite family of events, indexed by a finite set . For each let be a subfamily such that is independent of any event not in : for every subfamily with and ,
where is the complement of and . Suppose that for each there is a real number with such that
Then for every non-empty subfamily ,
In particular, the probability that all events of fail is positive: .
The local lemma finds objects that avoid every one of many bad events even when those objects are exceedingly rare, provided each bad event depends on only a few others. It is the source of lower bounds such as (Section 16.8).
Formalization Note. The probability space is a Fintype Ω with the discrete σ-algebra and a probability measure μ, so every subset is an event, matching the book's finite probability spaces (p. 214). Probabilities are μ.real. The family is A : ι → Set Ω with ι finite, so repeated events are allowed. is N i : Finset ι with i ∉ N i. Independence is IndepOutside μ A N i, the book's conditional equation in multiplicative form; see that definition. The two conclusions are stated as a conjunction. For empty ι the second conjunct says the whole space has positive probability.
import Mathlib import Definitions.Def_AppliedComb_ManyFaces_IndepOutside
namespace AppliedComb.ManyFaces
open MeasureTheory
/-- Lemma 16.14, the Lovász Local Lemma, asymmetric form (Keller & Trotter, *Applied
Combinatorics* (2017 Edition), pp. 326–327). `(Ω, μ)` is a finite probability space in which every
subset is an event; the family `𝓕` is `A : ι → Set Ω` indexed by a finite type `ι`, and
`𝓝(A i) = N i ⊆ ι \ {i}`. If each `A i` is independent of any event not in `𝓝(A i)` and there are
reals `0 < x i < 1` with `P(A i) ≤ x i · ∏_{j ∈ N i} (1 − x j)`, then for every non-empty
subfamily `G`, `P(∏_{i ∈ G} Ā_i) ≥ ∏_{i ∈ G} (1 − x i)`; in particular the probability that all
events of the family fail is positive. -/
theorem local_lemma_asymmetric {Ω ι : Type*} [Fintype Ω] [MeasurableSpace Ω]
[DiscreteMeasurableSpace Ω] [Fintype ι] (μ : Measure Ω) [IsProbabilityMeasure μ]
(A : ι → Set Ω) (N : ι → Finset ι) (hN : ∀ i, i ∉ N i)
(hind : ∀ i, IndepOutside μ A N i) (x : ι → ℝ) (hx : ∀ i, 0 < x i ∧ x i < 1)
(hP : ∀ i, μ.real (A i) ≤ x i * ∏ j ∈ N i, (1 - x j)) :
(∀ G : Finset ι, G.Nonempty → ∏ i ∈ G, (1 - x i) ≤ μ.real (allFail A G)) ∧
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
Let and be arbitrary types, both finite. carries a σ-algebra in which every subset is measurable. Let be a probability measure on , so . This forces to be non-empty. Throughout, denotes taken as a real number in .
The remaining data are:
- a family of events , one for each (arbitrary subsets, not necessarily distinct);
- for each , a finite set . Nothing links the to each other; in particular does not require ;
- a real number for each .
The hypotheses are:
- (No self-neighbour.) For every , .
- (Independence condition.) For every , the predicate holds.
- This predicate is defined in the imported bundle, and its definition was not available to this read-back.
- Its exact content is therefore not stated here and must be checked against that definition. It depends on , the whole family , the whole family , and the index .
- (Range of .) For every , , both strict.
- (Asymmetric bound.) For every ,
where the empty product (when ) equals .
Write for a subset of determined by the family and a finite set . It is also defined in the imported bundle and was not available here, so which set it is must be checked against its definition.
Conclusion. Both of the following hold:
- (a) For every non-empty finite set ,
- (b) Taking (all indices),
with strict inequality.
Degenerate cases.
- empty.
- Hypotheses 1–4 hold vacuously.
- Part (a) is vacuous, because there is no non-empty .
- Part (b) still asserts . Whether that holds depends entirely on how treats the empty index set.
- a single element .
- Hypothesis 1 forces .
- Hypothesis 4 then reads for some , which amounts to .
- Part (a) with asserts .
- . cannot be empty, since it carries a probability measure. It may have exactly one point, in which case every is or .
- No junk values. Because is finite and is a probability measure, every is a genuine finite value in ; no default value from converting an infinite measure arises. The factors are real subtractions, lying strictly between and under hypothesis 3.
- Satisfiability. Hypotheses 1, 3 and 4 are jointly satisfiable, for example with every and every . Whether hypothesis 2 can be satisfied, or is automatically satisfied in such cases, cannot be determined without the definition of .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.