Eq. (2.3): for and
ProvedPerturbedWF.eq_2_3metric-allocationonline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-v1work-functions
Let be a configuration space over a finite metric with transportation norm . For every , i.e. for all ,
This duality inequality is used throughout the analysis (Lemmas 2.3 and 3.1).
Formalization Note. is dualBall d and is transNorm d, defined by (2.1).
Differences from the source:
- encoding: v ∈ B* = {v : ‖v‖* ≤ 1} → v ∈ dualBall d, i.e. |v_i − v_j| ≤ d(i, j) for all i, j; reason: the characterization of B* stated after (2.2), p.5 (v ∈ B* iff |v_i − v_j| ≤ d(i, j)); the same set
Preamble
import Mathlib import Definitions.Def_PerturbedWF_WClass
Formal statement
namespace PerturbedWF
/-- **Eq. (2.3)** (p.5, PDF p.6). C. Coester, D. Kashaev, *Online Metric Problems via Randomly Perturbed Work Functions*, STOC 2027
submission (held version, sha256 e2e30a44…)
For `v ∈ B*`, `⟨v, x − y⟩ ≤ ‖x − y‖` for all `x, y ∈ C`.
**Formalization Note.** `B*` is `dualBall d` (`|v_i − v_j| ≤ d(i, j)`), `‖·‖` the
transportation norm (2.1). -/
theorem eq_2_3 {ι : Type} [Fintype ι] [DecidableEq ι] (C : Set (ι → ℝ))
(hC : IsConfigSpace C) (d : ι → ι → ℝ) (hd : IsFinMetric d) (v : ι → ℝ)
(hv : v ∈ dualBall d) (x y : ι → ℝ) (hx : x ∈ C) (hy : y ∈ C) :
dot v (x - y) ≤ transNorm d (x - y) := by sorry
end PerturbedWF
Source
Coester, Kashaev, Online Metric Problems via Randomly Perturbed Work Functions (STOC 2027 submission, held version, sha256 e2e30a44…), eq. (2.3), p.5 (PDF p.6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.