Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 16.14 — the Lovász Local Lemma, asymmetric form

Proved
AppliedComb.ManyFaces.local_lemma_asymmetric

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, indexed by a finite set ι\iotaι. 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): for every subfamily G⊆ιG \subseteq \iotaG⊆ι with i∉Gi \notin Gi∈/G and G∩N(i)=∅G \cap N(i) = \emptysetG∩N(i)=∅,

P(Ai∩∏j∈GAj‾)=P(Ai) P(∏j∈GAj‾),P\Big(A_i \cap \prod_{j \in G}\overline{A_j}\Big) = P(A_i)\,P\Big(\prod_{j \in G}\overline{A_j}\Big),P(Ai​∩j∈G∏​Aj​​)=P(Ai​)P(j∈G∏​Aj​​),

where A‾\overline{A}A is the complement of AAA and ∏j∈GAj‾=⋂j∈GAj‾\prod_{j\in G}\overline{A_j} = \bigcap_{j\in G}\overline{A_j}∏j∈G​Aj​​=⋂j∈G​Aj​​. Suppose that for each iii there is a real number x(i)x(i)x(i) with 0<x(i)<10 < x(i) < 10<x(i)<1 such that

P(Ai)≤x(i)∏j∈N(i)(1−x(j)).P(A_i) \le x(i) \prod_{j \in N(i)} \big(1 - x(j)\big).P(Ai​)≤x(i)j∈N(i)∏​(1−x(j)).

Then for every non-empty subfamily G⊆ιG \subseteq \iotaG⊆ι,

P(∏i∈GAi‾)  ≥  ∏i∈G(1−x(i)).P\Big(\prod_{i \in G}\overline{A_i}\Big) \;\ge\; \prod_{i \in G}\big(1 - x(i)\big).P(i∈G∏​Ai​​)≥i∈G∏​(1−x(i)).

In particular, the probability that all events of F\mathcal FF fail is positive: P(∏i∈ιAi‾)>0P(\prod_{i \in \iota}\overline{A_i}) > 0P(∏i∈ι​Ai​​)>0.

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 R(3,n)≥c n2/ln⁡2nR(3, n) \ge c\, n^2/\ln^2 nR(3,n)≥cn2/ln2n (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. N(i)N(i)N(i) 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.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_ManyFaces_IndepOutside
Formal statement
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
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), pp. 326–327, Lemma 16.14
Read-back

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

Let Ω\OmegaΩ and ι\iotaι be arbitrary types, both finite. Ω\OmegaΩ carries a σ-algebra in which every subset is measurable. Let μ\muμ be a probability measure on Ω\OmegaΩ, so μ(Ω)=1\mu(\Omega)=1μ(Ω)=1. This forces Ω\OmegaΩ to be non-empty. Throughout, P(S)P(S)P(S) denotes μ(S)\mu(S)μ(S) taken as a real number in [0,1][0,1][0,1].

The remaining data are:

  • a family of events Ai⊆ΩA_i \subseteq \OmegaAi​⊆Ω, one for each i∈ιi \in \iotai∈ι (arbitrary subsets, not necessarily distinct);
  • for each i∈ιi \in \iotai∈ι, a finite set Ni⊆ιN_i \subseteq \iotaNi​⊆ι. Nothing links the NiN_iNi​ to each other; in particular j∈Nij \in N_ij∈Ni​ does not require i∈Nji \in N_ji∈Nj​;
  • a real number xix_ixi​ for each i∈ιi \in \iotai∈ι.

The hypotheses are:

  1. (No self-neighbour.) For every iii, i∉Nii \notin N_ii∈/Ni​.
  2. (Independence condition.) For every iii, the predicate IndepOutside(μ,A,N,i)\mathrm{IndepOutside}(\mu, A, N, i)IndepOutside(μ,A,N,i) 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 μ\muμ, the whole family (Aj)j∈ι(A_j)_{j\in\iota}(Aj​)j∈ι​, the whole family (Nj)j∈ι(N_j)_{j\in\iota}(Nj​)j∈ι​, and the index iii.
  3. (Range of xxx.) For every iii, 0<xi<10 < x_i < 10<xi​<1, both strict.
  4. (Asymmetric bound.) For every iii,
P(Ai)  ≤  xi∏j∈Ni(1−xj),P(A_i) \;\le\; x_i \prod_{j \in N_i} (1 - x_j),P(Ai​)≤xi​j∈Ni​∏​(1−xj​),

where the empty product (when Ni=∅N_i = \varnothingNi​=∅) equals 111.

Write allFail(A,G)\mathrm{allFail}(A, G)allFail(A,G) for a subset of Ω\OmegaΩ determined by the family AAA and a finite set G⊆ιG \subseteq \iotaG⊆ι. 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 G⊆ιG \subseteq \iotaG⊆ι,
∏i∈G(1−xi)  ≤  P(allFail(A,G)).\prod_{i \in G} (1 - x_i) \;\le\; P\big(\mathrm{allFail}(A, G)\big).i∈G∏​(1−xi​)≤P(allFail(A,G)).
  • (b) Taking G=ιG = \iotaG=ι (all indices),
P(allFail(A,ι))  >  0,P\big(\mathrm{allFail}(A, \iota)\big) \;>\; 0,P(allFail(A,ι))>0,

with strict inequality.

Degenerate cases.

  • ι\iotaι empty.
    • Hypotheses 1–4 hold vacuously.
    • Part (a) is vacuous, because there is no non-empty GGG.
    • Part (b) still asserts P(allFail(A,∅))>0P(\mathrm{allFail}(A, \varnothing)) > 0P(allFail(A,∅))>0. Whether that holds depends entirely on how allFail\mathrm{allFail}allFail treats the empty index set.
  • ι\iotaι a single element iii.
    • Hypothesis 1 forces Ni=∅N_i = \varnothingNi​=∅.
    • Hypothesis 4 then reads P(Ai)≤xiP(A_i) \le x_iP(Ai​)≤xi​ for some xi∈(0,1)x_i \in (0,1)xi​∈(0,1), which amounts to P(Ai)<1P(A_i) < 1P(Ai​)<1.
    • Part (a) with G={i}G = \{i\}G={i} asserts 1−xi≤P(allFail(A,{i}))1 - x_i \le P(\mathrm{allFail}(A, \{i\}))1−xi​≤P(allFail(A,{i})).
  • Ω\OmegaΩ. Ω\OmegaΩ cannot be empty, since it carries a probability measure. It may have exactly one point, in which case every P(Ai)P(A_i)P(Ai​) is 000 or 111.
  • No junk values. Because Ω\OmegaΩ is finite and μ\muμ is a probability measure, every P(⋅)P(\cdot)P(⋅) is a genuine finite value in [0,1][0,1][0,1]; no default value from converting an infinite measure arises. The factors 1−xj1 - x_j1−xj​ are real subtractions, lying strictly between 000 and 111 under hypothesis 3.
  • Satisfiability. Hypotheses 1, 3 and 4 are jointly satisfiable, for example with every Ai=∅A_i = \varnothingAi​=∅ and every Ni=∅N_i = \varnothingNi​=∅. Whether hypothesis 2 can be satisfied, or is automatically satisfied in such cases, cannot be determined without the definition of IndepOutside\mathrm{IndepOutside}IndepOutside.
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