Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§7.1.2, (7.3) — positive-coordinate complementary slackness

Proved
CompetitiveOnlinePD.WeightedCaching.positive_slack

by mikedeng1 · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-optimizationonline-algorithmsweighted-caching

Let PPP be a finite universe of unit-size pages, let k≥1k\ge1k≥1 be an integer, and let cp≥1c_p\ge1cp​≥1 be arbitrary real costs. A finite request list has no prescribed horizon or restriction on repetitions or on ∣P∣|P|∣P∣ relative to kkk. All states below are computed by the shared prefix algorithm. Write S(p,j)S(p,j)S(p,j) for its interval slack, DDD for its unscaled dual objective, and L=1+ln⁡kL=1+\ln kL=1+lnk.

At every reached state and every valid interval,

x(p,j)>0 ⟺ x~(p,j)>0,x(p,j)>0 ⟹ S(p,j)≥cp.x(p,j)>0\ \Longleftrightarrow\ \widetilde x(p,j)>0,\qquad x(p,j)>0\ \Longrightarrow\ S(p,j)\ge c_p.x(p,j)>0 ⟺ x(p,j)>0,x(p,j)>0 ⟹ S(p,j)≥cp​.

This gives the threshold-cost complementary-slackness condition without imposing it on the state or asserting positivity of an untouched coordinate.

Differences from the source:

  • encoding: finite unit-page universes and arbitrary request prefixes → a finite page type, finite lists and one-based natural indices restricted to valid requests and occurrence intervals; reason: every finite prefix is included, also the empty list; no final horizon or future request is an input to a transition
  • encoding: the next request time in the interval sums → the absent next occurrence is T+1 solely as a summation sentinel; reason: last intervals include all intervening requests through T; the sentinel is never a request
  • reading: the boxed parenthetical r(p_t,t) < t′ < r(p_t,t)+1 → updates between occurrence request times t(p,j)+1 and t(p,j+1)-1; reason: the consecutive counters admit no integer update time; printed p.152 specifies the intended lifetime
  • encoding: continuous updates until capacity is satisfied → an exact real scalar flow with simultaneous events, first-stop infimum and left/right activation states; reason: this gives the stated zero, jump, exponential and saturation rules without discretization; completion is a conclusion
  • encoding: inconsistent dummy page letters i,p and an overloaded time t → bound page variables and distinct horizon and row times; reason: the capacity rows and (7.6) bind the intended variables without changing any instance
Preamble
import Definitions.Def_CompetitiveOnlinePD_WeightedCaching_Observables
Formal statement
namespace CompetitiveOnlinePD.WeightedCaching
open scoped BigOperators

theorem positive_slack
    {P : Type} [Fintype P] [DecidableEq P]
    (k : ℕ) (hk : 1 ≤ k) (c : P → ℝ) (hc : ∀ p, 1 ≤ c p)
    (H : List P) (s : State P) (hs : reached k c H s) :
    ∀ v ∈ intervals H,
      (0 < s.x v.1 v.2 ↔ 0 < truncated k s.x v.1 v.2) ∧
      (0 < s.x v.1 v.2 → c v.1 ≤ slack H s v.1 v.2) := by sorry

end CompetitiveOnlinePD.WeightedCaching
Source
Buchbinder & Naor, The Design of Competitive Online Algorithms via a Primal-Dual Approach, copyright 2009, DOI:10.1561/0400000024, https://doi.org/10.1561/0400000024, (7.3), printed p.155 (PDF p.66)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me