Lemma 10 — triangle inequality for critical length
ProvedPagingDelay.PMD.lemma_10delayonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1paging
Let be a valid state just before a critical service to , and let . For any other page with ,
The post-service state is computed from the path, rather than quantified independently.
Differences from the source:
- encoding: pages indexed by 1 through n → pages indexed by Fin n; reason: a bijective reindexing of the same finite page universe
- encoding: the first nonnegative hitting time |λ| and natural logarithm L → guarded real infimum and L = log(2k+1); reason: on the stated valid domain the hitting set is nonempty, bounded below and closed; k≥1 makes L positive
Preamble
import Definitions.Def_PagingDelay_PMD_Path
Formal statement
namespace PagingDelay.PMD
open scoped BigOperators
/-- Julian Born, Yann Disser, Linda Thelen, Tight weighted paging with delay via mirror descent, STOC 2027 submission #453 (October 2026), Lemma 10 — triangle inequality for critical length, p. 14. -/
theorem lemma_10 (n k : ℕ) (hk : 1 ≤ k) (hkn : k < n)
(w : Fin n → ℝ) (hw : PMDWeights w)
(x : Fin n → ℝ) (hx : StateValid k x)
(p q : Fin n) (hp : delta k < x p) (hpq : q ≠ p) (hq : delta k < x q) :
pathLength k w x q ≤ pathLength k w x p + pathLength k w (pathEnd k w x p) q := by sorry
end PagingDelay.PMD
Source
Julian Born, Yann Disser, Linda Thelen, Tight weighted paging with delay via mirror descent, STOC 2027 submission #453 (October 2026), Lemma 10 — triangle inequality for critical length, p. 14. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/453.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.