Theorem 4.6 — Shattering in Max-XORSAT
OpenDQIShattered.Supplement.theorem_4_6decoded-quantum-interferometrygibbs-samplingglauber-dynamicsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1random-xorsatshatteringspin-glass
There is an such that, for every and every satisfying all hypotheses of Theorem 4.3, the Gibbs measure of is -shattered. More explicitly, a single constant , independent of , gives with probability at least for all sufficiently large nonempty clusters whose individual masses are at most , Hamming diameters are at most , pairwise separations are at least , and whose union has mass at least .
Differences from the source:
- reading: the hypotheses of Theorem 4.3 are incorporated by reference → Lean inlines “sufficiently small” , , , and the full interval (4.4); reason: the platform theorem must stand on its own
- generalization: the Gibbs measure is -shattered with high probability → Lean retains the stronger probability for all sufficiently large ; reason: Propositions 5.9–5.11 prove an exponentially-good bound
Preamble
import Mathlib import Definitions.Def_DQIShattered_Supplement_Framework
Formal statement
namespace DQIShattered
namespace Supplement
/-- **Theorem 4.6 (Shattering in Max-XORSAT).**
Zhou, Shutty, Sellke, Jordan, arXiv:2609.40345, held version sha256 0c7f6fdf…,
p.19.
Under every hypothesis of Theorem 4.3, the Gibbs measure is `(ε/k)`-shattered. The conclusion
keeps the exponentially good probability proved by Propositions 5.9–5.11: one fixed `c > 0`
controls both the exceptional probability and all four cluster clauses for all sufficiently
large `N`. -/
theorem theorem_4_6 :
∃ ε₀ : ℝ, 0 < ε₀ ∧ ∀ ε : ℝ, 0 < ε → ε < ε₀ →
∃ k₀ : ℕ, 3 ≤ k₀ ∧ ∀ k : ℕ, k₀ ≤ k →
∀ D : ℝ, (k : ℝ) ≤ D → ∀ β : ℝ, InHardRange k D ε β →
IsExponentiallyShattered k D β (ε / k) := 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.6, p.19; proof pp.28–30