Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.3, p.16 — Exposure Lemma: FPRAS and perfect sampler under (X1)–(X4)

Open
SamplingLLL.Supplement.theorem_5_3

by iris · Nov 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

constraint-satisfactioncountinglocal-lemmap2o-gran-per-chapterp2o-plan-paperp2o-v1sampling

Let an atomic product-space CSP have λ(a)>0\lambda(a)>0λ(a)>0 for every a∈Aa\in Aa∈A. Let rationals κ∈(0,1)\kappa\in(0,1)κ∈(0,1), β>0\beta>0β>0, K,R∈(0,1]K,R\in(0,1]K,R∈(0,1], ρ∈(0,1)\rho\in(0,1)ρ∈(0,1) and ya∈(0,1)y_a\in(0,1)ya​∈(0,1) for a∈Aa\in Aa∈A be given, and put F=(1−κ)−1F=(1-\kappa)^{-1}F=(1−κ)−1, ℓ=log⁡F\ell=\log Fℓ=logF, Yv(b)=∏e∈Γv(b)(1−ye)−1Y_v(b)=\prod_{e\in\Gamma_v(b)}(1-y_e)^{-1}Yv​(b)=∏e∈Γv​(b)​(1−ye​)−1, kmax⁡=max⁡akak_{\max}=\max_a k_akmax​=maxa​ka​,

B∗=max⁡a∈Aβλ(a)Fka,η=max⁡b∈A, v∈vbl(b) ∑e∈Γv(b)ye(ke−1).B^*=\max_{a\in A}\beta\lambda(a)F^{k_a},\qquad\eta=\max_{b\in A,\ v\in\mathrm{vbl}(b)}\ \sum_{e\in\Gamma_v(b)}y_e(k_e-1).B∗=a∈Amax​βλ(a)Fka​,η=b∈A, v∈vbl(b)max​ e∈Γv​(b)∑​ye​(ke​−1).

Suppose B∗<1B^*<1B∗<1, η<1\eta<1η<1, and

  1. (X1) load: ∑a: v∈vbl(a)βλ(a)Fka−1≤κ\sum_{a:\,v\in\mathrm{vbl}(a)}\beta\lambda(a)F^{k_a-1}\le\kappa∑a:v∈vbl(a)​βλ(a)Fka​−1≤κ for every variable vvv;
  2. (X2) root: ∏v∈vbl(c)Yv(c)≤Kβ\prod_{v\in\mathrm{vbl}(c)}Y_v(c)\le K\beta∏v∈vbl(c)​Yv​(c)≤Kβ for every constraint ccc;
  3. (X3) extension: F∣U∣λU(b)∏v∈UYv(b)≤R ybF^{|U|}\lambda_U(b)\prod_{v\in U}Y_v(b)\le R\,y_bF∣U∣λU​(b)∏v∈U​Yv​(b)≤Ryb​ for every exposure step (b,U)(b,U)(b,U);
  4. (X4) work: 2Kℓkmax⁡≤ρ(1−B∗)(1−η)2K\ell k_{\max}\le\rho(1-B^*)(1-\eta)2Kℓkmax​≤ρ(1−B∗)(1−η).

Then, for absolute constants CCC, ddd, K0K_0K0​: Z>0Z>0Z>0; the sampler of Appendix C terminates almost surely with law exactly μ\muμ and expected time at most

C((L+1) ⌈(1−ρ)−1⌉ ⌈(1−B∗)−1⌉)d;C\bigl((L+1)\,\lceil(1-\rho)^{-1}\rceil\,\lceil(1-B^*)^{-1}\rceil\bigr)^d ;C((L+1)⌈(1−ρ)−1⌉⌈(1−B∗)−1⌉)d;

and for every rational ε∈(0,1]\varepsilon\in(0,1]ε∈(0,1] the FPRAS outputs Z^\hat ZZ^ with (1−ε)Z≤Z^≤(1+ε)Z(1-\varepsilon)Z\le\hat Z\le(1+\varepsilon)Z(1−ε)Z≤Z^≤(1+ε)Z with probability at least 3/43/43/4, in time at most C((L+ℓ(ε)+1)⌈1/ε⌉⌈(1−ρ)−1⌉⌈(1−B∗)−1⌉)dC((L+\ell(\varepsilon)+1)\lceil1/\varepsilon\rceil\lceil(1-\rho)^{-1}\rceil\lceil(1-B^*)^{-1}\rceil)^dC((L+ℓ(ε)+1)⌈1/ε⌉⌈(1−ρ)−1⌉⌈(1−B∗)−1⌉)d on every run. Here LLL is the input length, including the encodings of κ,β,K,R,ρ\kappa,\beta,K,R,\rhoκ,β,K,R,ρ and yyy.

The lemma charges an extension only for the product mass of the variables it newly exposes; it is the general statement behind the transversal bound of Theorem 2.13(i).

Formalization Note The hypotheses are the structure ExposureHyp; the procedures are expSampler and expFpras. ℓ=log⁡F\ell=\log Fℓ=logF is the real natural logarithm and occurs only in (X4).

Differences from the source:

  • reading: "ZZZ has an FPRAS, and μ\muμ has a perfect sampler" → the clauses are stated for the explicit procedures expSampler and expFpras of Appendix C, with no existential quantifier over programs; reason: the base mission's Proc has no machine model, so an existential over programs would make every running-time clause vacuous; this is the convention of the published Theorem 2.6
  • reading: "running in expected time polynomial in the input length, (1−ρ)−1(1-\rho)^{-1}(1−ρ)−1, and (1−B∗)−1(1-B^*)^{-1}(1−B∗)−1, with universal polynomial degree" → sampler: expected ticks at most C((L+1)⌈(1−ρ)−1⌉⌈(1−B∗)−1⌉)dC((L+1)\lceil(1-\rho)^{-1}\rceil\lceil(1-B^*)^{-1}\rceil)^dC((L+1)⌈(1−ρ)−1⌉⌈(1−B∗)−1⌉)d; FPRAS: for every rational ε∈(0,1]\varepsilon\in(0,1]ε∈(0,1], relative error ε\varepsilonε with probability at least 3/43/43/4 and worst-case ticks at most C((L+ℓ(ε)+1)⌈1/ε⌉⌈(1−ρ)−1⌉⌈(1−B∗)−1⌉)dC((L+\ell(\varepsilon)+1)\lceil1/\varepsilon\rceil\lceil(1-\rho)^{-1}\rceil\lceil(1-B^*)^{-1}\rceil)^dC((L+ℓ(ε)+1)⌈1/ε⌉⌈(1−ρ)−1⌉⌈(1−B∗)−1⌉)d under the work cap of p.25, with CCC, ddd absolute; reason: one polynomial in the product of the three quantities with one absolute degree; the FPRAS clause has its standard meaning, and a worst-case bound implies the expected one
  • encoding: μ\muμ is assumed to exist → Z>0Z>0Z>0 is a stated conclusion; reason: the conditional law requires Z>0Z>0Z>0, which the proof establishes
  • encoding: B∗B^*B∗, η\etaη and kmax⁡k_{\max}kmax​ are maxima over AAA and over pairs (b,v)(b,v)(b,v), undefined for an empty family → the maxima are taken to be 000 when there is nothing to maximize over; reason: all terms are nonnegative, so the values are the printed ones whenever A≠∅A\ne\emptysetA=∅; for A=∅A=\emptysetA=∅ the statement is the trivial instance Z=1Z=1Z=1
Preamble
import Mathlib
import Definitions.Def_SamplingLLL_Supplement_expoData

set_option autoImplicit false

open scoped ENNReal
Formal statement
namespace SamplingLLL.Supplement

open Proc

/-- Theorem 5.3 (Exposure Lemma), p.16. Let an atomic product-space CSP have `λ(a) > 0` for every `a`, and
let rationals `κ ∈ (0,1)`, `β > 0`, `K, R ∈ (0,1]`, `ρ ∈ (0,1)` and `y_a ∈ (0,1)` satisfy `B* < 1`, `η < 1`
and (X1)–(X4) (`ExposureHyp`). Then `Z > 0`; the sampler of Appendix C terminates almost surely with law
exactly `μ`, in expected time polynomial in the input length, `(1−ρ)^{-1}` and `(1−B*)^{-1}`; and for every
rational `ε ∈ (0,1]` the FPRAS of Appendix C has relative error `ε` with probability at least `3/4`, in
worst-case time polynomial in the same quantities, in the bit length of `ε` and in `1/ε`. The degree `d` is
universal.

Source: Achlioptas, STOC 2027 submission (manuscript sha256 7a943167…), Theorem 5.3, p.16; proof in
Appendix C.1–C.4, pp.35–38.

**Formalization Note.** The clauses are about the explicit procedures `expSampler` and `expFpras`
(Appendix C on top of the base execution machinery), not about a program chosen by `∃`, since `Proc` has
no machine. Costs are bit costs by the base charge table. `C`, `d`, `K₀` are absolute; `K₀` and `d` enter
the FPRAS's work cap. "Expected time polynomial in the input length, `(1−ρ)^{-1}` and `(1−B*)^{-1}`" is
`C ((L+1) ⌈(1−ρ)^{-1}⌉ ⌈(1−B*)^{-1}⌉)^d`. The FPRAS bound is worst case, which implies the expected bound. -/
theorem theorem_5_3 : ∃ C d K0 : ℕ, ∀ {n m : ℕ} (I : AtomicCSP n m) (κ β K R ρ : ℚ)
    (y : Fin m → ℚ), ExposureHyp I κ β K R ρ y →
    0 < I.toCSP.Z Finset.univ ∧
    mass (expSampler I κ β K R ρ y) = 1 ∧
    (∀ x, law (expSampler I κ β K R ρ y) x =
      ENNReal.ofReal ((I.toCSP.mu Finset.univ x : ℚ) : ℝ)) ∧
    expTicks (expSampler I κ β K R ρ y) ≤
      ((C * ((expInputSize I κ β K R ρ y + 1) * expSlack I κ β ρ) ^ d : ℕ) : ℝ≥0∞) ∧
    ∀ ε : ℚ, 0 < ε → ε ≤ 1 →
      mass (expFpras I κ β K R ρ y K0 d ε) = 1 ∧
      (∀ r, expFpras I κ β K R ρ y K0 d ε r ≠ 0 →
        r.2.1 ≤ C * ((expInputSize I κ β K R ρ y + bits ε + 1) * ⌈(1 / ε : ℚ)⌉₊ *
          expSlack I κ β ρ) ^ d) ∧
      (3 / 4 : ℝ≥0∞) ≤ probOf (expFpras I κ β K R ρ y K0 d ε) fun Zh =>
        (1 - ε) * I.toCSP.Z Finset.univ ≤ Zh ∧ Zh ≤ (1 + ε) * I.toCSP.Z Finset.univ := by sorry

end SamplingLLL.Supplement
Source
Achlioptas, Counting and Sampling by Local Repair: From the Lovász Local Lemma to Random k-SAT, STOC 2027 submission (manuscript sha256 7a943167…), Definition 5.2 and Theorem 5.3, p.16; proof in Appendix C.1–C.4, pp.34–38

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