Theorem 5.2 — one finite walk for each covariance branch
OpenQVolKLS.Supplement.theorem_5_2Fix the convex body, its rational inner and outer ball data, a finite rational list of tilts, rational spectral bounds , a certified , and accuracies . There are common dyadic lattice, radius, seed, and arithmetic-precision parameters that work for every listed tilt and every rational symmetric with . For each such branch:
- Algorithm 2 is lazy, positive, irreducible, and reversible for the lattice log-affine law.
- If is covariance-comparable with a fixed comparison constant, its two-warm mixing time is .
- Its zero-extended discriminant has an arbitrarily accurate implementation of an exact -block-encoding using coherent membership queries.
- Every listed lattice normalizer has relative error at most .
- With independent lattice samples, the empirical covariance satisfies
Moreover, after normalizing the inner radius, the inverse mesh is bounded by one absolute polynomial in all displayed geometric, tilt, spectral, accuracy, failure-budget, and KLS parameters.
Formalization Note The soft- and polynomial claims are expanded as and , with constants fixed before the varying data and with listing every required parameter and reciprocal. The empirical covariance is expressed by all directional quadratic forms.
Differences from the source:
- encoding: the source describes Algorithm 2 operationally and states matrix inequalities → Lean packages the common finite proposal, Metropolis kernel, dyadic probabilities, block encoding, and covariance inequalities as explicit predicates on the same finite lattice; reason: a direct finite-state encoding of the same algorithm and Loewner-order clauses
- encoding: the source writes and “at most polynomial” → Lean uses and with one displayed aggregate ; reason: makes every hidden absolute constant and parameter dependence explicit
- generalization: the source leaves the finite direction-sampler accuracy implicit in the common precision choice → Lean additionally chooses each walk with nonnegative direction error at most ; reason: Appendix B's construction permits arbitrary sufficiently fine precision, and the source's walks specialize to this choice
import Definitions.Def_QVolKLS_Supplement_LatticeWalk set_option autoImplicit false
namespace QVolKLS.Supplement
open MeasureTheory
open scoped ENNReal
/-- R. Zhang, arXiv:2610.04987 (held version, sha256 eee7a45e…), **Theorem 5.2
(One finite walk for each covariance branch)**, p.40, in the setting of §5.1, pp.37–40 and
Appendix B.6, pp.77–78.
One dyadic mesh and one radius/seed/precision regime work simultaneously for the whole finite tilt
list and every rational preconditioner in the supplied spectral range. Every resulting Algorithm 2
walk is lazy, positive, irreducible and reversible for the lattice law. A covariance-comparable
preconditioner has the stated uniform two-warm mixing bound; every walk has an arbitrarily accurate
zero-extended discriminant block-encoding with a constant number of coherent membership queries;
all normalizers and empirical covariances have the printed accuracy guarantees; and the inverse
mesh is polynomially bounded in every listed parameter.
The finite walk is tied to the paper's actual construction: its local finite-seed law approximates
the rounded uniform-ball proposal (83), its radius list is (85), and its connector is the uniform
signed integer-box proposal. The register covers every lattice point of the body and the connector
box covers every feasible difference.
**Formalization Note.** The universal comparison constant `c` is fixed before all dimensions and
inputs. `Õ(D²/ψ²)` is expanded as `C (D²/ψ²) (1+log Xi)^C`, and the final polynomial mesh
claim as `2^p ≤ C Xi^C`, with the same absolute `C` fixed before the data. `Xi` includes every
geometric bound and reciprocal, the largest tilt norm, both regularization bounds and reciprocals,
all three accuracy/failure reciprocals, `1/ψ`, the dimension and the number of stages. The sample
count is exactly the natural ceiling of `Csample D(1+log(4/εCov))²` for a universal sufficiently
large `Csample`. The statement fixes the body before choosing the common parameters, as printed.
-/
theorem theorem_5_2 :
∀ c : ℝ, 1 ≤ c →
∃ (C Csample Cq : ℝ), 0 < C ∧ 0 < Csample ∧ 0 < Cq ∧
∀ (D m : ℕ), 1 ≤ D →
∀ (K : Set (Euc D)) (xc : Fin D → ℚ) (r0 R0 : ℚ)
(bt : Fin (m + 1) → Fin D → ℚ) (lm lp psi eta zeta epsCov : ℚ),
IsConvexBody K → Metric.ball (ratPoint xc) (r0 : ℝ) ⊆ K →
K ⊆ Metric.closedBall (ratPoint xc) (R0 : ℝ) →
0 < r0 → r0 ≤ R0 → 0 < lm → lm ≤ lp → 0 < psi →
ENNReal.ofReal (psi : ℝ) ≤ (SongZhangKLS.psiN D)⁻¹ →
0 < eta → eta < 1 / 2 → 0 < zeta → zeta < 1 / 2 →
0 < epsCov → epsCov < 1 / 2 →
let Bstar : ℝ := ⨆ i, ‖ratPoint (bt i)‖
let Xi : ℝ := 1 + (D : ℝ) + (m : ℝ) + (r0 : ℝ) + (R0 : ℝ) +
1 / (r0 : ℝ) + 1 / (R0 : ℝ) + Bstar + (lm : ℝ) + (lp : ℝ) +
1 / (lm : ℝ) + 1 / (lp : ℝ) + 1 / (eta : ℝ) + 1 / (zeta : ℝ) +
1 / (epsCov : ℝ) + 1 / (psi : ℝ)
let L : ℕ := ⌈Csample * (D : ℝ) * (1 + Real.log (4 / (epsCov : ℝ))) ^ 2⌉₊
∃ q : CommonWalkParams D,
RegCovers D q.b q.p (Metric.closedBall (ratPoint xc) (R0 : ℝ)) ∧
ConnectorCovers q (R0 : ℝ) ∧
(2 : ℝ) ^ q.p ≤ C * Xi ^ C ∧
(∀ (i : Fin (m + 1)) (A : Matrix (Fin D) (Fin D) ℚ), A.transpose = A →
(∀ u : Euc D,
(lm : ℝ) * ‖u‖ ^ 2 ≤ quadForm A u ∧ quadForm A u ≤ (lp : ℝ) * ‖u‖ ^ 2) →
∃ W : LatticeWalk q K (ratPoint (bt i)) A,
0 ≤ W.epsDir ∧ W.epsDir ≤ 1 / 100 ∧
TransformedOuterRadiusBound q K (ratPoint xc) W.WA ∧
(∃ rhoA : ℝ, TransformedCellRadiusBound q W.WA rhoA ∧
q.rMesh = C * (D : ℝ) ^ 3 * rhoA) ∧
HasConstantQueryBlockEncoding q K (ratPoint (bt i)) A W Cq ∧
((∀ u : Euc D,
c⁻¹ * dirVariance (logAffineMeasure K (ratPoint (bt i))) u ≤ quadForm A u ∧
quadForm A u ≤ c * dirVariance (logAffineMeasure K (ratPoint (bt i))) u) →
∃ t : ℕ,
(t : ℝ) ≤ C * ((D : ℝ) ^ 2 / (psi : ℝ) ^ 2) *
(1 + Real.log Xi) ^ C ∧
MixTime2Le (walkOmega q K) eta (walkLaw q K (ratPoint (bt i))) W.P t)) ∧
(∀ i : Fin (m + 1),
|latticeZ K ((2 : ℝ)⁻¹ ^ q.p) (ratPoint (bt i)) /
logAffineZ K (ratPoint (bt i)) - 1| ≤ zeta ∧
1 - (epsCov : ℝ) ≤
covarianceGoodProbability (L := L) q K (ratPoint (bt i))) := by sorry
end QVolKLS.Supplement