Theorem 4.4 (p.17, eq. (24)) — bridge from lemma_4_3
ProvedCritWinSpin.p4c_theorem_4_4_from_lemma_4_3critical-windowp2o-v1reductionspin-systems
Assuming the statement of Lemma 4.3 (pp.15–16, eq. (23)), the full conclusion of Theorem 4.4 (p.17, eq. (24)) holds. This isolates the constructions of that section from the prerequisite estimate.
Preamble
import Mathlib import Definitions.Def_IsingLTL_BeliefProp_TVDist import Definitions.Def_QAlgorithms_ClassicalBinaryEncoding import Definitions.Def_QuantumPRC_IsPolyFamily import Definitions.Def_CritWinSpin_encInst import Definitions.Def_CritWinSpin_RandMachine import Definitions.Def_CritWinSpin_Wpot open QAlgorithms.LocalHamiltonian QuantumPRC IsingLTL.BeliefProp set_option autoImplicit false open MeasureTheory IsingLTL.BeliefProp
Formal statement
namespace CritWinSpin
/-- Bridge lemma for Theorem 4.4 (p.17, eq. (24)): the target conclusion given Lemma 4.3 (pp.15–16, eq. (23)). -/
theorem p4c_theorem_4_4_from_lemma_4_3 (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p) (hP : ∀ (S : SpinLaw) (hS : IsGHS S), ∃ M₀ Cₖ : ℝ, 0 < M₀ ∧ 0 < Cₖ ∧
∀ (N : ℕ) (L : Matrix (Fin N) (Fin N) ℝ) (s α : ℝ) (h : Fin N → ℝ),
tau S < s → s ≤ 2 * tau S + 1 →
(s • (1 : Matrix (Fin N) (Fin N) ℝ) - L * L.transpose).PosSemidef →
0 < α → α ≤ 1 →
(∀ᵐ z : Fin N → ℝ,
DifferentiableAt ℝ (fderiv ℝ (Wpot S s L h)) z ∧
DifferentiableAt ℝ (fderiv ℝ (Ualpha S s α L h)) z ∧
∀ v : Fin N → ℝ,
0 ≤ fderiv ℝ (fderiv ℝ (Wpot S s L h)) z v v ∧
fderiv ℝ (fderiv ℝ (Wpot S s L h)) z v v ≤ normSq v ∧
α * normSq v ≤ fderiv ℝ (fderiv ℝ (Ualpha S s α L h)) z v v ∧
fderiv ℝ (fderiv ℝ (Ualpha S s α L h)) z v v ≤ (1 + α) * normSq v) ∧
(Integrable (fun z : Fin N → ℝ => Real.exp (-Wpot S s L h z)) ∧
Integrable (fun z : Fin N → ℝ => normSq z * Real.exp (-Wpot S s L h z)) ∧
Integrable (fun z : Fin N → ℝ => Real.exp (-Ualpha S s α L h z)) ∧
Integrable (fun z : Fin N → ℝ => normSq z * Real.exp (-Ualpha S s α L h z)) ∧
max (∫ z : Fin N → ℝ, normSq z * normDens (Wpot S s L h) z)
(∫ z : Fin N → ℝ, normSq z * normDens (Ualpha S s α L h) z) ≤ M₀ * (N : ℝ) ∧
(1 / 2) * (∫ z : Fin N → ℝ,
|normDens (Ualpha S s α L h) z - normDens (Wpot S s L h) z|) ≤
α * M₀ * (N : ℝ) / 2) ∧
(∀ z w : Fin N → ℝ,
tvDist (kernelK S s L h z) (kernelK S s L h w) ≤
Cₖ * Real.sqrt (N : ℝ) * Real.sqrt (normSq (z - w)))) :
∃ (M : RandMachine) (C : ℝ) (k : ℕ),
∀ (N : ℕ) (I : Inst N) (m : ℕ) (δ : ℝ),
I.1.IsSymm → (castM I.1).PosSemidef → 0 ≤ δ →
((tau S * (1 + δ)) • (1 : Matrix (Fin N) (Fin N) ℝ) - castM I.1).PosSemidef → 5 ≤ m →
tvDist (outLaw M (tupleCode [encInst I, encBin m]) (decConfig S N))
(gibbsOpt S (castM I.1) (castV I.2)) ≤ 1 / (m : ℝ) ∧
(M.time (tupleCode [encInst I, encBin m]) : ℝ) ≤
C * ((N : ℝ) + (bitLen I : ℝ) + (m : ℝ)) ^ k *
Real.exp (C * (N : ℝ) * δ ^ ((p : ℝ) / ((p : ℝ) - 1))) := by sorry
end CritWinSpin
Source
Liu, Zhang, Ren, The Critical Window for Sampling and Learning-to-Sample in Spin Systems, STOC 2027 submission (manuscript sha256 f77584da…), Theorem 4.4 (p.17, eq. (24))