Theorem 2.18, p.10 — random scopes, adversarial signs: counting and sampling random -CNF up to density
OpenSamplingLLL.Supplement.theorem_2_18There are an absolute constant , absolute constants , and a threshold such that, for every , the algorithm (with its internal constants fixed, depending on only) has the following property. Let be fixed and choose clause scopes independently and uniformly from the -subsets of (Definition 2.17). With probability tending to one as over the scopes, simultaneously for every assignment of literal signs and every rational :
- the formula is satisfiable;
- , given the formula and , outputs a number within relative error of the number of satisfying assignments with probability at least ;
- returns a satisfying assignment whose law is within total variation distance of the uniform law on satisfying assignments;
- the expected running time of both is at most
This is counting and sampling for random -CNF at clause density of order when the adversary chooses the signs after seeing the scopes.
Formalization Note is the pair of procedures akCount, akSample: compute and , perform the peeling and closure of p.57, and run the algorithms of Theorem F.6 with and . Both terminate with probability one, which is part of the statement. The probability over the scopes is scopeProb, and "with high probability" is the limit .
Differences from the source:
- reading: "for every , a randomized algorithm " → is the explicit pair of procedures
akCount,akSampleof p.66, 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: the algorithm of p.66 uses the constant ("Choose the seed-threshold constant"), the constant of in (67) and "sixteen times the proved polynomial upper bound" (p.57) without giving their values → is quantified existentially before ; and the cap polynomial existentially after and before ; reason: these are the constants of the paper's own algorithm; may depend on only, through the absolute constant (p.66)
- reading: "With high probability over the random clause scopes" → the probability of the event tends to one as , the event quantifying over all sign patterns and all inside; reason: the paper's own reading (pp.57, 65: "with probability tending to one")
- reading: "The expected running time is with " → expected ticks at most with absolute, for rational; reason: the accuracy is a rational given in binary and reading it is charged; the two bounds agree when is written with bits
- encoding: " sufficiently large and fixed"; "approximates within relative error with probability at least "; "returns a satisfying assignment" → ; both procedures terminate with probability one; every output of the sampler satisfies all clauses; reason: the usual meaning of the phrases; termination is needed for the output laws to be probability laws
import Mathlib import Definitions.Def_SamplingLLL_Supplement_peelCore set_option autoImplicit false open scoped ENNReal open Filter Topology
namespace SamplingLLL.Supplement
open Proc
/-- Theorem 2.18 (Random scopes, adversarial signs), p.10. There are an absolute constant `c > 0` and, for
every `k`, a randomized algorithm `A_k` with the following property. Let `k` be sufficiently large and
fixed, let `0 < α ≤ c 2^k/k²` be fixed, and take `m = ⌊αn⌋` clause scopes independently and uniformly from
the `k`-subsets of `[n]` (Definition 2.17). With probability tending to one as `n → ∞` over the scopes,
simultaneously for every assignment of literal signs and every rational `ε ∈ (0,1)`: the formula is
satisfiable; `A_k`, given the formula and `ε`, (i) approximates its number of satisfying assignments within
relative error `ε` with probability at least `3/4`, and (ii) returns a satisfying assignment whose law is
within total variation distance `ε` of the uniform law on satisfying assignments; and the expected running
time of both is at most `((n + ℓ(ε))/ε)^{C(k)}` with `C(k) = 2^{C₀ k}`, `C₀` absolute.
Source: Achlioptas, STOC 2027 submission (manuscript sha256 7a943167…), Definition 2.17 and Theorem 2.18,
p.10; proof on pp.65–66 (F.6–F.9), with the algorithms of Theorem F.6, pp.55–57.
**Formalization Note.** `A_k` is the pair of explicit procedures `akCount` and `akSample` of p.66: compute
`α = m/n` and `∆ = ⌈A_seed(αk + k log k)⌉`, perform the peeling and closure of p.57, and run the algorithms
of Theorem F.6 with `a_blk = d/8`, `β = 4`. The seed constant `A_seed` is absolute ("Choose the
seed-threshold constant `A_seed`", p.65) and is quantified before `k`; the constants of Theorem F.6's
algorithms that the paper leaves implicit (`C_core` of (67) and the work-cap polynomial `K ·^e`) are
quantified after `k` and before `α`, so `A_k` depends on `k` only. "With high probability" is the limit
`n → ∞` (pp.57, 65), of an event that quantifies over all signs and all `ε` inside. The accuracy `ε` is a
rational given in binary and reading it is charged, so the time bound is in `(n + bits ε)/ε` (the paper's
`n/ε` when `ε` is written with `O(log(1/ε))` bits). "Sufficiently large `k`" is `k ≥ k₀`. -/
theorem theorem_2_18 : ∃ c : ℝ, 0 < c ∧ ∃ C₀ Aseed k₀ : ℕ, ∀ k : ℕ, k₀ ≤ k → ∃ Ccore K e : ℕ,
∀ α : ℝ, 0 < α → α ≤ c * 2 ^ k / (k : ℝ) ^ 2 →
Tendsto (fun n : ℕ => scopeProb n ⌊α * (n : ℝ)⌋₊ k fun scope =>
∀ (sgn : Fin ⌊α * (n : ℝ)⌋₊ → Fin n → Bool) (ε : ℚ), 0 < ε → ε < 1 →
let I := kcnf scope sgn
let T : ℝ := (((n : ℝ) + bits ε) / ε) ^ (2 ^ (C₀ * k))
(∃ x, I.toCSP.sat Finset.univ x = true) ∧
mass (akCount k Aseed Ccore K e scope sgn ε) = 1 ∧
(3 / 4 : ℝ≥0∞) ≤ probOf (akCount k Aseed Ccore K e scope sgn ε) (fun Nh =>
(1 - ε) * (numSat I : ℚ) ≤ Nh ∧ Nh ≤ (1 + ε) * (numSat I : ℚ)) ∧
expTicks (akCount k Aseed Ccore K e scope sgn ε) ≤ ENNReal.ofReal T ∧
mass (akSample k Aseed Ccore scope sgn ε) = 1 ∧
SupportedOn (akSample k Aseed Ccore scope sgn ε)
(fun x => I.toCSP.sat Finset.univ x = true) ∧
tvDist (akSample k Aseed Ccore scope sgn ε)
(fun x => if I.toCSP.sat Finset.univ x = true then (numSat I : ℝ)⁻¹ else 0) ≤ ε ∧
expTicks (akSample k Aseed Ccore scope sgn ε) ≤ ENNReal.ofReal T)
atTop (𝓝 1) := by sorry
end SamplingLLL.Supplement