Theorem 5.3, p.16 — Exposure Lemma: FPRAS and perfect sampler under (X1)–(X4)
OpenSamplingLLL.Supplement.theorem_5_3Let an atomic product-space CSP have for every . Let rationals , , , and for be given, and put , , , ,
Suppose , , and
- (X1) load: for every variable ;
- (X2) root: for every constraint ;
- (X3) extension: for every exposure step ;
- (X4) work: .
Then, for absolute constants , , : ; the sampler of Appendix C terminates almost surely with law exactly and expected time at most
and for every rational the FPRAS outputs with with probability at least , in time at most on every run. Here is the input length, including the encodings of and .
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. is the real natural logarithm and occurs only in (X4).
Differences from the source:
- reading: " has an FPRAS, and has a perfect sampler" → the clauses are stated for the explicit procedures
expSamplerandexpFprasof Appendix C, with no existential quantifier over programs; reason: the base mission'sProchas 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, , and , with universal polynomial degree" → sampler: expected ticks at most ; FPRAS: for every rational , relative error with probability at least and worst-case ticks at most under the work cap of p.25, with , 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: is assumed to exist → is a stated conclusion; reason: the conditional law requires , which the proof establishes
- encoding: , and are maxima over and over pairs , undefined for an empty family → the maxima are taken to be when there is nothing to maximize over; reason: all terms are nonnegative, so the values are the printed ones whenever ; for the statement is the trivial instance
import Mathlib import Definitions.Def_SamplingLLL_Supplement_expoData set_option autoImplicit false open scoped ENNReal
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