Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Local lemma for an infinite index set: the whole family has a nonzero meet

Proved
QLLL.iInf_ne_bot

by sattath · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

lattice-theorylovasz-local-lemmaquantum-lll

Let LLL be a complete lattice and R:L→RR : L \to \mathbb{R}R:L→R a valuation (nonnegative, monotone, modular, R(⊤)=1R(\top) = 1R(⊤)=1, R(⊥)=0R(\bot) = 0R(⊥)=0). Let (Xi)i∈I(X_i)_{i \in I}(Xi​)i∈I​ be a family in LLL indexed by an arbitrary set III, and let Γ(i)⊆I\Gamma(i) \subseteq IΓ(i)⊆I be finite sets forming a dependency graph: for every iii and every finite S⊆IS \subseteq IS⊆I with i∉Si \notin Si∈/S and S∩Γ(i)=∅S \cap \Gamma(i) = \emptysetS∩Γ(i)=∅, R(Xi∧⋀j∈SXj)=R(Xi) R(⋀j∈SXj)R\big(X_i \wedge \bigwedge_{j \in S} X_j\big) = R(X_i)\,R\big(\bigwedge_{j \in S} X_j\big)R(Xi​∧⋀j∈S​Xj​)=R(Xi​)R(⋀j∈S​Xj​). Let 0≤yi<10 \le y_i < 10≤yi​<1 with R(Xi)≥1−yi∏j∈Γ(i)(1−yj)R(X_i) \ge 1 - y_i \prod_{j \in \Gamma(i)} (1 - y_j)R(Xi​)≥1−yi​∏j∈Γ(i)​(1−yj​) for every iii, and let ccc be a real number with c≤∏j∈S(1−yj)c \le \prod_{j \in S}(1 - y_j)c≤∏j∈S​(1−yj​) for every finite S⊆IS \subseteq IS⊆I. Assume RRR is continuous from above in the following sense: whenever b≤R(⋀j∈SXj)b \le R\big(\bigwedge_{j \in S} X_j\big)b≤R(⋀j∈S​Xj​) for every finite S⊆IS \subseteq IS⊆I, also b≤R(⋀i∈IXi)b \le R\big(\bigwedge_{i \in I} X_i\big)b≤R(⋀i∈I​Xi​). Suppose moreover that c>0c > 0c>0.

Then

⋀i∈IXi ≠ ⊥.\bigwedge_{i \in I} X_i \ \neq\ \bot.i∈I⋀​Xi​ = ⊥.

This is the qualitative conclusion of QLLL.lll_iInf: under the same hypotheses and a positive lower bound ccc on the finite products, the meet of the whole family is not the bottom element.

Preamble
import Definitions.Def_QLLL_LocalLemma_Basic
import Definitions.Def_QLLL_LocalLemma_Infinite
import Mathlib

open QLLL
open Finset
variable {α : Type*} [CompleteLattice α] (R : Valuation α)
variable {ι : Type*} {X : ι → α} {Γ : ι → Finset ι} {y : ι → ℝ}
Formal statement
theorem QLLL.iInf_ne_bot (hΓ : IsDependencyGraphOn R X Γ)
    (hy₀ : ∀ i, 0 ≤ y i) (hy₁ : ∀ i, y i < 1)
    (hX : ∀ i, 1 - y i * ∏ j ∈ Γ i, (1 - y j) ≤ R (X i))
    (c : ℝ) (hc : ∀ S : Finset ι, c ≤ ∏ j ∈ S, (1 - y j)) (hcpos : 0 < c)
    (hcont : ∀ b : ℝ, (∀ S : Finset ι, b ≤ R (S.inf X)) → b ≤ R (⨅ i, X i)) :
    (⨅ i, X i) ≠ ⊥ := by sorry
Source
Not in the paper; an extension of Theorem 14 to infinite index sets. Formalization companion to Ambainis, Kempe and Sattath, A Quantum Lovász Local Lemma, arXiv:0911.1696; see the blueprint https://sattath.github.io/Quantum-Lovasz-Local-Lemma/blueprint/

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me