Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 16.15 — the Lovász Local Lemma, symmetric form

Proved
AppliedComb.ManyFaces.local_lemma_symmetric

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricslovasz-local-lemmap2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1probability

Let (Ω,P)(\Omega, P)(Ω,P) be a finite probability space and F=(Ai)i∈ι\mathcal F = (A_i)_{i \in \iota}F=(Ai​)i∈ι​ a finite family of events. For each iii let N(i)⊆ι∖{i}N(i) \subseteq \iota \setminus \{i\}N(i)⊆ι∖{i} be a subfamily such that AiA_iAi​ is independent of any event not in N(i)N(i)N(i), that is, P(Ai∩∏j∈GAj‾)=P(Ai) P(∏j∈GAj‾)P(A_i \cap \prod_{j \in G}\overline{A_j}) = P(A_i)\,P(\prod_{j \in G}\overline{A_j})P(Ai​∩∏j∈G​Aj​​)=P(Ai​)P(∏j∈G​Aj​​) for every G⊆ιG \subseteq \iotaG⊆ι with i∉Gi \notin Gi∈/G and G∩N(i)=∅G \cap N(i) = \emptysetG∩N(i)=∅. Let ppp and ddd be real numbers with 0<p<10 < p < 10<p<1 and d≥1d \ge 1d≥1, and suppose that

P(Ai)≤p,∣N(i)∣≤dfor every i,e p (d+1)<1,P(A_i) \le p, \qquad |N(i)| \le d \quad \text{for every } i, \qquad e\,p\,(d+1) < 1,P(Ai​)≤p,∣N(i)∣≤dfor every i,ep(d+1)<1,

where eee is the base of the natural logarithm. Then

P(∏i∈ιAi‾)  ≥  (1−1d+1)∣F∣  >  0,P\Big(\prod_{i \in \iota} \overline{A_i}\Big) \;\ge\; \Big(1 - \frac{1}{d+1}\Big)^{|\mathcal F|} \;>\; 0,P(i∈ι∏​Ai​​)≥(1−d+11​)∣F∣>0,

so the probability that all events of F\mathcal FF 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, P(∏E∈FE‾)≥∏E∈G(1−x(E))P(\prod_{E\in\mathcal F}\overline E) \ge \prod_{E\in\mathcal G}(1 - x(E))P(∏E∈F​E)≥∏E∈G​(1−x(E)), mentions G\mathcal GG and xxx, which the lemma never introduces, and its gloss reads "the probability that all events in F\mathcal FF is positive". The book's proof sets x(E)=1/(d+1)x(E) = 1/(d+1)x(E)=1/(d+1) and applies Lemma 16.14 with G=F\mathcal G = \mathcal FG=F; the statement is that reading: the explicit bound (1−1/(d+1))∣F∣(1 - 1/(d+1))^{|\mathcal F|}(1−1/(d+1))∣F∣, with ∣F∣=|\mathcal F| = ∣F∣= 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.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_ManyFaces_IndepOutside
Formal statement
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
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 328, Lemma 16.15 (conclusion misprinted; read from the proof, x(E) = 1/(d+1))
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting.

  • Ω\OmegaΩ is a finite type equipped with the σ\sigmaσ-algebra in which every subset is measurable.
  • μ\muμ is a probability measure on Ω\OmegaΩ, so μ(Ω)=1\mu(\Omega) = 1μ(Ω)=1 and all values are finite reals.
  • ι\iotaι is a finite index type, with ∣ι∣|\iota|∣ι∣ elements.
  • ppp and ddd are real numbers, not required to be integers.
  • (Ai)i∈ι(A_i)_{i \in \iota}(Ai​)i∈ι​ is a family of subsets of Ω\OmegaΩ.
  • NNN assigns to each iii a finite set Ni⊆ιN_i \subseteq \iotaNi​⊆ι. No symmetry between different NiN_iNi​ is assumed.

Hypotheses.

  1. 0<p<10 < p < 10<p<1.
  2. d≥1d \ge 1d≥1.
  3. i∉Nii \notin N_ii∈/Ni​ for every iii.
  4. For every iii and every G⊆ιG \subseteq \iotaG⊆ι with i∉Gi \notin Gi∈/G and G∩Ni=∅G \cap N_i = \emptysetG∩Ni​=∅,
μ(Ai∩⋂j∈GAjc)=μ(Ai) μ(⋂j∈GAjc).\mu\Big(A_i \cap \bigcap_{j \in G} A_j^{c}\Big) = \mu(A_i)\,\mu\Big(\bigcap_{j\in G} A_j^{c}\Big).μ(Ai​∩j∈G⋂​Ajc​)=μ(Ai​)μ(j∈G⋂​Ajc​).

The intersection over G=∅G = \emptysetG=∅ is taken to be Ω\OmegaΩ. 5. μ(Ai)≤p\mu(A_i) \le pμ(Ai​)≤p for every iii. 6. ∣Ni∣≤d|N_i| \le d∣Ni​∣≤d for every iii. 7. e⋅p⋅(d+1)<1e \cdot p \cdot (d+1) < 1e⋅p⋅(d+1)<1, where e=exp⁡(1)e = \exp(1)e=exp(1).

Conclusion. Both of the following hold:

(1−1d+1)∣ι∣  ≤  μ(⋂i∈ιAic)andμ(⋂i∈ιAic)>0.\Big(1 - \frac{1}{d+1}\Big)^{|\iota|} \;\le\; \mu\Big(\bigcap_{i \in \iota} A_i^{c}\Big) \qquad\text{and}\qquad \mu\Big(\bigcap_{i \in \iota} A_i^{c}\Big) > 0.(1−d+11​)∣ι∣≤μ(i∈ι⋂​Aic​)andμ(i∈ι⋂​Aic​)>0.

Degenerate cases.

  • Redundant bound. Hypotheses (2) and (7) together force p<1/(2e)p < 1/(2e)p<1/(2e), so the condition p<1p < 1p<1 in (1) is implied.
  • Empty ι\iotaι. The intersection over the empty family is Ω\OmegaΩ, of measure 111. The lower bound is (1−1/(d+1))0=1(1 - 1/(d+1))^0 = 1(1−1/(d+1))0=1, and the conclusion reads 1≤11 \le 11≤1 and 1>01 > 01>0.
  • Empty Ω\OmegaΩ. This is excluded, since μ\muμ is a probability measure.
  • One-element Ω\OmegaΩ.
    • Every event has measure 000 or 111.
    • Hypothesis (5) with p<1p < 1p<1 forces every Ai=∅A_i = \emptysetAi​=∅.
    • Therefore the intersection of complements is Ω\OmegaΩ, and the conclusion is (1−1/(d+1))∣ι∣≤1(1 - 1/(d+1))^{|\iota|} \le 1(1−1/(d+1))∣ι∣≤1 together with 1>01 > 01>0.
  • Ill-defined values. All measures are finite, so the conversion to real numbers loses nothing. Since d≥1d \ge 1d≥1, the base 1−1/(d+1)1 - 1/(d+1)1−1/(d+1) lies in [1/2,1)[1/2, 1)[1/2,1) and no division by zero arises.
Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me