Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§7.1.2, (7.9)–(7.10) — rates and integrated continuous cost

Proved
CompetitiveOnlinePD.WeightedCaching.continuous_growth

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 each smooth strictly unsatisfied clock τ\tauτ, let G={p∈B(t)∖{pt}:1/k≤x(p,r(p,t))<1}G=\{p\in B(t)\setminus\{p_t\}:1/k\le x(p,r(p,t))<1\}G={p∈B(t)∖{pt​}:1/k≤x(p,r(p,t))<1} and let B′B'B′ be the saturated pages. With j=r(p,t)j=r(p,t)j=r(p,t), the full rate chain is

dC2dτ=∑p∈Gcpdx(p,j)dy(t)dy(t)dτ=∑p∈Gx(p,j)≤(∣B(t)∣−k)−∑p∈B′1=(∣B(t)∣−k)dy(t)dτ−∑p∈B′dz(p,j)dτ=dDdτ.\frac{dC_2}{d\tau}=\sum_{p\in G}c_p\frac{dx(p,j)}{dy(t)}\frac{dy(t)}{d\tau} =\sum_{p\in G}x(p,j)\le (|B(t)|-k)-\sum_{p\in B'}1 =(|B(t)|-k)\frac{dy(t)}{d\tau}-\sum_{p\in B'}\frac{dz(p,j)}{d\tau}=\frac{dD}{d\tau}.dτdC2​​=p∈G∑​cp​dy(t)dx(p,j)​dτdy(t)​=p∈G∑​x(p,j)≤(∣B(t)∣−k)−p∈B′∑​1=(∣B(t)∣−k)dτdy(t)​−p∈B′∑​dτdz(p,j)​=dτdD​.

The statement also gives dy(t)/dτ=1dy(t)/d\tau=1dy(t)/dτ=1, dx(p,j)/dτ=x(p,j)/cpdx(p,j)/d\tau=x(p,j)/c_pdx(p,j)/dτ=x(p,j)/cp​ on GGG, and dz(p,j)/dτ=1dz(p,j)/d\tau=1dz(p,j)/dτ=1 on B′B'B′. Since y(t)y(t)y(t) has unit rate, its clock derivative is the derivative with respect to y(t)y(t)y(t) in the display. Differentiability itself is concluded from the explicit clock formulas; no regularity assumption on histories or runs is added.

At the endpoint of every finite execution, including all events,

C2≤D,C1+C2=C.C_2\le D,\qquad C_1+C_2=C.C2​≤D,C1​+C2​=C.

These are the integrated conclusion on printed p.158 and the exact cost decomposition; no extra factor of LLL is applied to the unscaled DDD.

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
  • reading: no visible operator between the two printed dual-objective sums → the second sum is subtracted; reason: equation (7.8), the dual constraints and the dual-profit derivatives fix the minus sign
  • 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
  • encoding: rates during continuous growth in (7.9)–(7.10) → classical derivatives at smooth live clocks excluding exactly activation and saturation events; reason: the source has jumps and event boundaries; the integrated conclusion still covers the whole execution and every endpoint
Preamble
import Definitions.Def_CompetitiveOnlinePD_WeightedCaching_Observables
Formal statement
namespace CompetitiveOnlinePD.WeightedCaching
open scoped BigOperators

theorem continuous_growth
    {P : Type} [Fintype P] [DecidableEq P]
    (k : ℕ) (hk : 1 ≤ k) (c : P → ℝ) (hc : ∀ p, 1 ≤ c p)
    (H : List P) :
    (∀ (h : List P) (p : P) (τ : ℝ), smoothLive k c h p τ →
      let F := fun u => clock false k c h p (run k c h) u
      let h' := h ++ [p]
      let G := growing k h' (F τ)
      let B' := saturated h' (F τ)
      HasDerivAt (fun u => continuousCost k c h' (F u))
        (∑ q ∈ G, c q * deriv (fun u => (F u).x q (h'.count q)) τ *
          deriv (fun u => (F u).y h'.length) τ) τ ∧
      (∑ q ∈ G, c q * deriv (fun u => (F u).x q (h'.count q)) τ *
          deriv (fun u => (F u).y h'.length) τ) =
        ∑ q ∈ G, (F τ).x q (h'.count q) ∧
      (∑ q ∈ G, (F τ).x q (h'.count q)) ≤
        required k h' - ∑ q ∈ B', (1 : ℝ) ∧
      required k h' - (∑ q ∈ B', (1 : ℝ)) =
        required k h' * deriv (fun u => (F u).y h'.length) τ -
          ∑ q ∈ B', deriv (fun u => (F u).z q (h'.count q)) τ ∧
      HasDerivAt (fun u => (F u).y h'.length) 1 τ ∧
      (∀ q ∈ G, HasDerivAt (fun u => (F u).x q (h'.count q))
        ((F τ).x q (h'.count q) / c q) τ) ∧
      (∀ q ∈ B', HasDerivAt (fun u => (F u).z q (h'.count q)) 1 τ) ∧
      HasDerivAt (fun u => dualValue k h' (F u))
        (required k h' * deriv (fun u => (F u).y h'.length) τ -
          ∑ q ∈ B', deriv (fun u => (F u).z q (h'.count q)) τ) τ) ∧
    (let s := run k c H
     continuousCost k c H s ≤ dualValue k H s ∧
     thresholdCost k c H s + continuousCost k c H s = cost c H s.x) := 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.9)–(7.10), printed p.157 (PDF p.68), and integrated bound printed p.158 (PDF p.69)

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