Lemma 34 — complete rounding-map properties
ProvedPagingDelay.PMD.lemma_34delayonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1paging
Let , and with . Put and . Then
The scalar map is nonincreasing and 3-Lipschitz throughout . All five conclusions of the lemma are included.
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: coordinatewise nonincreasing, 3-Lipschitz map on [δ,1] → AntitoneOn and LipschitzOnWith 3 on the closed interval; reason: these express the two scalar properties uniformly, rather than only at the supplied coordinates
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 34 — complete rounding-map properties, p. 26. -/
theorem lemma_34 (n k : ℕ) (hk : 1 ≤ k) (x : Fin n → ℝ)
(hx : ∀ i, delta k ≤ x i ∧ x i ≤ 1)
(hmass : (n : ℝ) - k ≤ ∑ i, x i) :
(∀ i, 0 ≤ roundingMap k (x i) ∧ roundingMap k (x i) ≤ 1) ∧
(∀ i, x i = delta k → roundingMap k (x i) = 1) ∧
(∑ i, roundingMap k (x i)) ≤ (k : ℝ) ∧
AntitoneOn (roundingMap k) (Set.Icc (delta k) 1) ∧
LipschitzOnWith 3 (roundingMap k) (Set.Icc (delta k) 1) := 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 34 — complete rounding-map properties, p. 26. 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.