Theorem 7.2 (eq. 40), forgery-to-error core
OpenCritWinSpin.p7b_thm72_forge_to_errorcdhcritical-windowhardnessreductionspin-systems
Let be a source satisfying , and let the lifted model and slot machine of Theorem 6.3 be fixed. This lemma isolates the forgery-to-error step of Theorem 7.2: it asserts that for all large the quantity
is a lower bound for both the sample-extension error and the sample-amplification error of the lifted instance law. Here is the probability that outputs a fresh valid configuration whose message is distinct from all given messages; the remaining terms are the collision bound, the bound, and the total-variation errors of . This is the hard information-theoretic core of eq. (40); the subsequent conversion of into is clause (iii) of and is carried out in the parent theorem.
Preamble
import Mathlib import Definitions.Def_IsingLTL_BeliefProp_TVDist import Definitions.Def_CritWinSpin_Lhat open QAlgorithms.Complexity QAlgorithms.LocalHamiltonian QuantumPRC OWFLocalDesc IsingLTL.BeliefProp set_option autoImplicit false
Formal statement
namespace CritWinSpin
/-- Theorem 7.2, eq. (40), forgery-to-error core: the quantitative conclusion with the CDH advantage replaced by the source forgery probability. Combined with SourceProps(iii) (forgeProb ≤ C T sqrt(d) Adv_CDH(B)) this yields Theorem 7.2. -/
theorem p7b_thm72_forge_to_error (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p)
(F : BilinearFamily) (src : BinarySource F) (C : ℝ) (hC : 0 < C) (hsrc : SourceProps F src C)
(w ε : ℝ) (Ac Cc : ℕ) (hw : 1 ≤ w) (hε : 0 < ε) (hεd : ε < dExp p)
(hpar : GadgetParams p w ε Ac Cc)
(Ccap : ℝ) (hCcap : 0 < Ccap)
(liftF : Str → Str) (hliftF : CookPvsNP.PolyTimeComputable liftF) (slotM : PPT)
(û : (d : ℕ) → (desc : Str) → WatersKey F desc d → ℚ) (d₁ : ℕ)
(hlift : ∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
IsUhat S ((thetaQ p Ac Cc (src.n d) : ℚ) : ℝ) (cloudSize p Cc (src.n d)) (û d desc key) ∧
liftF (encInst (src.ham d desc key)) =
tupleCode [encInst (liftInst S p Ac Cc (src.ham d desc key) (û d desc key)),
encRat (û d desc key)])
(hdec : ∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
LhatDecodes (slotKernel S p Cc slotM (src.ham d desc key) (û d desc key)))
(k T : ℕ → ℕ) (hk : EffPoly k) (hk₁ : ∀ d, 1 ≤ k d) (hT : EffPoly T)
(hTk : ∀ d, ⌈Ccap * ((k d : ℝ) + 1 + (src.n d : ℝ) ^ 2)⌉₊ ≤ T d)
(v₁ v₂ : ℕ → ℝ)
(hv₁ : ∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
tvDist (LhatMu (slotKernel S p Cc slotM (src.ham d desc key) (û d desc key))
(muH (castM (src.ham d desc key).1) (castV (src.ham d desc key).2)) (T d) (k d))
(gibbsTupleOpt S (castM (liftJQ S p Ac Cc (src.ham d desc key) (û d desc key)))
(castV (liftHQ p Cc (src.ham d desc key) (û d desc key))) (k d)) ≤ v₁ d)
(hv₂ : ∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
tvDist (LhatMu (slotKernel S p Cc slotM (src.ham d desc key) (û d desc key))
(muH (castM (src.ham d desc key).1) (castV (src.ham d desc key).2)) (T d) (k d + 1))
(gibbsTupleOpt S (castM (liftJQ S p Ac Cc (src.ham d desc key) (û d desc key)))
(castV (liftHQ p Cc (src.ham d desc key) (û d desc key))) (k d + 1)) ≤ v₂ d)
(A : PPT) :
(∃ (d₀ : ℕ), ∀ d ≥ d₀,
1 - forgeProb src A (T d) d -
((T d : ℝ) + ((T d).choose 2 : ℝ)) * (1 / (2 : ℝ) ^ d) -
2 * (T d : ℝ) * Real.exp (-((src.n0 d : ℝ) ^ 2)) - v₁ d - v₂ d ≤
errExt S (keyLiftLaw F d fun desc key =>
liftInst S p Ac Cc (src.ham d desc key) (û d desc key)) A (k d)) ∧
(∃ (d₀ : ℕ), ∀ d ≥ d₀,
1 - forgeProb src A (T d) d -
((T d : ℝ) + ((T d).choose 2 : ℝ)) * (1 / (2 : ℝ) ^ d) -
2 * (T d : ℝ) * Real.exp (-((src.n0 d : ℝ) ^ 2)) - v₁ d - v₂ d ≤
errAmp S (keyLiftLaw F d fun desc key =>
liftInst S p Ac Cc (src.ham d desc key) (û d desc key)) A (k d)) := by sorry
end CritWinSpinSource
Liu, Zhang, Ren, The Critical Window for Sampling and Learning-to-Sample in Spin Systems, STOC 2027 submission (manuscript sha256 f77584da…), p.27, Theorem 7.2, eq. (40), §7.