Theorem 4.10 — Shattering forces exponentially slow Glauber mixing
OpenDQIShattered.Supplement.theorem_4_10decoded-quantum-interferometrygibbs-samplingglauber-dynamicsp2o-gran-per-chapterp2o-plan-paperp2o-v1random-xorsatshatteringspin-glass
Fix , an integer , a real , and an inverse temperature . If the Gibbs measure of is -shattered with high probability, then there is an , independent of , such that the random-scan single-site heat-bath Glauber dynamics for has worst-start total-variation mixing time at least
with probability tending to one.
Differences from the source:
- encoding: mixing time → Lean quantifies a fixed and requires that before every integer time some initial state remains at total variation distance greater than ; reason: this is the standard worst-start total-variation definition and avoids a default-valued infimum
- encoding: → Lean makes the ensemble's standing assumptions and explicit; reason: these are Definition 2.5's domain, not additional restrictions
Preamble
import Mathlib import Definitions.Def_DQIShattered_Supplement_Framework
Formal statement
namespace DQIShattered
namespace Supplement
/-- **Theorem 4.10.**
Zhou, Shutty, Sellke, Jordan, arXiv:2609.40345, held version sha256 0c7f6fdf…,
p.21.
For every `ε ∈ (0,1/2)`, if the random Max-`k`-XORSAT Gibbs measures are `ε`-shattered with
high probability in the exact sense of Definition 4.4, then their random-scan single-site
heat-bath Glauber chains have worst-start total-variation mixing time at least `exp(aN)` with
high probability, for one positive rate `a` independent of `N`. -/
theorem theorem_4_10 (ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1 / 2)
(k : ℕ) (hk : 2 ≤ k) (D β : ℝ) (hD : 0 < D)
(hshatter : IsShattered k D β ε) :
ExponentialGlauberMixing k D β := by sorry
end Supplement
end DQIShattered
Source
Zhou, Shutty, Sellke, Jordan, Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry, arXiv:2609.40345 (held version sha256 0c7f6fdf…), Theorem 4.10, pp.21–22