Theorem 6 (corrected: integer ceiling in eq. (25)) — triangular Fourier mixing bound
OpenQSDMixing.GU.Supplement.triangular_feature_mixingfourier-analysismarkov-chainp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-mixing-timequantum-state-discrimination
Let be independent finite random variables and let be triangular with target . For each , define
Then for every integer ,
Put and . For , the resulting integer mixing-time bound is
At , the displayed total-variation estimate gives ; at it yields no finite upper bound.
Differences from the source:
- correction: equation (25) states without integer rounding → Lean takes the natural-number ceiling, uses the time-two consequence at , and returns at ; reason: for , , , , and , one has and but the printed right side is less than
- encoding: independent coordinates → a product of finite marginal probability laws; reason: product mass is exactly finite-coordinate independence
- encoding: conditional expectations in equation (23) → nested finite sums over an outer and an independent inner source vector, with the th coordinate replaced; reason: triangularity makes later coordinates irrelevant and the sums are the two expectations in the displayed order
- encoding: a maximum over nontrivial characters of a trivial factor → supremum of the finite set, assigned zero when the set is empty; reason: the corresponding term is zero and no mixing obstruction is present
Preamble
import Mathlib import Definitions.Def_QSDMixing_GU_Supplement_TriangularWalk set_option autoImplicit false
Formal statement
namespace QSDMixing.GU.Supplement
/-- **Theorem 6, p.25 (corrected integer bound).** The conditional Fourier biases of an
independent-coordinate triangular feature map control total variation at every integer `t>1`.
The mixing-time consequence uses the ceiling of the printed real threshold, with the endpoint
`λ=0` handled by the same `t=2` estimate and `λ=1` assigned no finite bound.
Zhou, Leditzky, *A mixing time method for estimating the sample complexity of quantum state
discrimination*, arXiv:2609.40182 (held version, sha256 62fb68dd…), Theorem 6, p.25,
eqs. (23)--(25).
**Formalization Note.** Equation (25) as printed omits integer rounding. For one coordinate
`B=Z/2Z`, increment law `p(0)=5/8`, `p(1)=3/8`, and `ε=1/10`, one has `λ=1/16` and
`t_min=2`, whereas the printed right side is `(log 2 + 2 log 10)/log 16 < 2`. The ceiling is
therefore a necessary correction, not a weakening. -/
theorem triangular_feature_mixing (n : ℕ) (hn : 0 < n) (W : TriangularWalk n) :
(∀ t : ℕ, 1 < t →
W.tv t ≤ (1 / 2 : ℝ) *
∑ i, Real.sqrt (((Fintype.card (W.Target i) : ℝ) - 1) * (W.lambda i) ^ t)) ∧
∀ ε : ℝ, 0 < ε → ε < 1 →
W.mixingTime ε ≤ W.mixingBound ε := by sorry
end QSDMixing.GU.Supplement
Source
Zhou, Leditzky, A mixing time method for estimating the sample complexity of quantum state discrimination, arXiv:2609.40182 (held version, sha256 62fb68dd…), Theorem 6, p.25, eqs. (23)–(25)