Uniform randomized TM2 sampler witness (ULA + HS rejection in critical window, exact finite-state Gibbs outside) for Theorem 4.4
OpenCritWinSpin.p4c_4_4_randmachinecritwinspinp4crandmachinetheorem_4_4
Given the regularity, second-moment, density total-variation, and kernel Lipschitz bounds from Lemma 4.3 together with the Hubbard–Stratonovich discrepancy, acceptance lower bound, and Gibbs conditioning identity, constructs a uniform randomized multi-stack Turing machine and constants , such that for every symmetric PSD instance satisfying and accuracy :
In the first regime, locates a rational spectral cap with and runs discretized ULA on paired with Hubbard–Stratonovich rejection sampling; in the second regime, evaluates the finite-state Gibbs distribution directly by enumeration.
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
/-- Uniform randomized multi-stack Turing machine (`RandMachine`) witness for
`CritWinSpin.p4c_theorem_4_4_from_lemma_4_3`: discretized ULA on `U_alpha` with Hubbard–Stratonovich
rejection sampling inside `2τI - J ⪰ 0`, and exact finite-state Gibbs enumeration outside. -/
theorem p4c_4_4_randmachine :
∀ (S : SpinLaw) (p : ℕ), IsGHS S → IsTypeP S p →
(∀ (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)))) →
∀ (C₄₂ : ℝ), 0 < C₄₂ →
(∀ {N : ℕ} (J L : Matrix (Fin N) (Fin N) ℝ) (h : Fin N → ℝ) (s : ℝ),
tau S < s → J.PosSemidef → J = L * L.transpose →
Integrable (fun z : Fin N → ℝ => Real.exp (-Wpot S s L h z)) →
(∀ z : Fin N → ℝ,
0 ≤ hsV S L h z - Wpot S s L h z ∧
hsV S L h z - Wpot S s L h z ≤ (N : ℝ) * (C₄₂ * (s - tau S) ^ ((p : ℝ) / ((p : ℝ) - 1)))) ∧
0 < ∫ z : Fin N → ℝ, Real.exp (-Wpot S s L h z) ∧
Real.exp (-((N : ℝ) * (C₄₂ * (s - tau S) ^ ((p : ℝ) / ((p : ℝ) - 1))))) ≤
1 - ∫ z : Fin N → ℝ, normDens (Wpot S s L h) z * kernelK S s L h z none ∧
(∀ x : Config S (Fin N),
(∫ z : Fin N → ℝ, normDens (Wpot S s L h) z * kernelK S s L h z (some x)) /
(1 - ∫ z : Fin N → ℝ, normDens (Wpot S s L h) z * kernelK S s L h z none) =
gibbs S J h x)) →
∃ (M : RandMachine) (C_poly C_exp : ℝ) (k_poly : ℕ), 0 < C_poly ∧ 0 < C_exp ∧
∀ (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 : ℝ) ∧
(((2 * tau S) • (1 : Matrix (Fin N) (Fin N) ℝ) - castM I.1).PosSemidef →
∃ s : ℝ, tau S < s ∧ s ≤ 2 * tau S + 1 ∧
(s • (1 : Matrix (Fin N) (Fin N) ℝ) - castM I.1).PosSemidef ∧
s - tau S ≤ tau S * δ + 1 / ((max 1 N : ℝ) ^ (((p : ℝ) - 1) / (p : ℝ))) ∧
(M.time (tupleCode [encInst I, encBin m]) : ℝ) ≤
C_poly * ((N : ℝ) + (bitLen I : ℝ) + (m : ℝ)) ^ k_poly *
Real.exp (C_exp * (N : ℝ) * (s - tau S) ^ ((p : ℝ) / ((p : ℝ) - 1)))) ∧
(¬ ((2 * tau S) • (1 : Matrix (Fin N) (Fin N) ℝ) - castM I.1).PosSemidef →
(M.time (tupleCode [encInst I, encBin m]) : ℝ) ≤
C_poly * ((N : ℝ) + (bitLen I : ℝ) + (m : ℝ)) ^ k_poly *
Real.exp (C_exp * (N : ℝ))) := by sorry
end CritWinSpinSource
Decomposition child of CritWinSpin.p4c_theorem_4_4_from_lemma_4_3