payment_window_amortized_bound
For any page type α, any natural number k, and any payment window w : PaymentWindow α k, the offline cost covers the online payment and potential change: 1 ≤ (k + 1 : ℝ) * (w.delta_fetches_opt : ℝ) + (k + 1 : ℝ) * w.delta_delay_opt - (w.delta_phi : ℝ).
Statement
theorem payment_window_amortized_bound {α : Type*} (k : ℕ) (w : PaymentWindow α k) : 1 ≤ (k + 1 : ℝ) * (w.delta_fetches_opt : ℝ) + (k + 1 : ℝ) * w.delta_delay_opt - (w.delta_phi : ℝ)
- Formalizes
- arXiv:2610.18767 Section 3.2, Lemma 3.4
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- PaymentWindowA structure PaymentWindow parameterized by page type α and cache capacity k : ℕ, consisting of a requested page : α, offline fetch count…
Read back from the Lean
For any type α, any natural number k, and any PaymentWindow α k w, the real number 1 is less than or equal to (k + 1) * w.delta_fetches_opt + (k + 1) * w.delta_delay_opt - w.delta_phi (where k + 1, w.delta_fetches_opt, and w.delta_phi are coerced to ℝ).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem shows that for any payment window, the offline cost scaled by $k + 1$ minus the potential change covers the normalized online payment of 1: $1 \le (k + 1)\Delta F_{\mathrm{opt}} + (k + 1)\Delta D_{\mathrm{opt}} - \Delta\Phi$. The proof splits into three cases according to the definition of a payment window: either the potential drops by at least 1, or the potential grows by at most $k$ while the offline algorithm pays at least 1 page fetch or at least 1 unit of delay. In every case, non-negativity of the parameters and straightforward arithmetic show that the offline contribution and potential change combine to at least 1.
The offline delay, the offline page fetch count, and the parameter $k$ are all non-negative as real numbers: $0 \le w.\text{delta\_delay\_opt}$, $0 \le (w.\text{delta\_fetches\_opt} : \mathbb{R})$, and $0 \le (k : \mathbb{R})$.
The delay $w.\text{delta\_delay\_opt}$ is non-negative by definition of a payment window (`w.delta_delay_nonneg`). Because the fetch count $w.\text{delta\_fetches\_opt}$ and the cache size parameter $k$ are natural numbers, their canonical casts to the real numbers are automatically non-negative.
have hd : 0 ≤ w.delta_delay_opt := w.delta_delay_nonneg have hf : (0 : ℝ) ≤ (w.delta_fetches_opt : ℝ) := by positivity have hk : (0 : ℝ) ≤ (k : ℝ) := by positivity
It suffices to establish the amortized bound in each of the three cases provided by the payment window condition (`w.case_condition`).
By definition of a payment window, at least one of three mutually compatible conditions holds: (1) the potential drops by at least 1 ($\Delta\Phi \le -1$); (2) the offline algorithm incurs at least 1 fetch and the potential increases by at most $k$ ($\Delta F_{\mathrm{opt}} \ge 1$ and $\Delta\Phi \le k$); or (3) the offline algorithm incurs at least 1 unit of delay and the potential increases by at most $k$ ($\Delta D_{\mathrm{opt}} \ge 1$ and $\Delta\Phi \le k$).
rcases w.case_condition with h | ⟨hf1, hφ⟩ | ⟨hd1, hφ⟩
In Case 1, where the potential drops by at least 1, the amortized bound holds.
Casting the hypothesis $w.\text{delta\_phi} \le -1$ to the real numbers yields $\Delta\Phi \le -1$, which implies $-\Delta\Phi \ge 1$. Since $k \ge 0$, $\Delta F_{\mathrm{opt}} \ge 0$, and $\Delta D_{\mathrm{opt}} \ge 0$, the scaled offline terms $(k + 1) \Delta F_{\mathrm{opt}}$ and $(k + 1) \Delta D_{\mathrm{opt}}$ are both non-negative. Hence the entire right-hand side is at least $0 + 0 - (-1) = 1$.
· have h' : (w.delta_phi : ℝ) ≤ -1 := by exact_mod_cast h nlinarith
In Case 2, where the offline algorithm fetches at least one page and the potential increases by at most $k$, the amortized bound holds.
Casting the hypotheses gives $\Delta\Phi \le k$ and $\Delta F_{\mathrm{opt}} \ge 1$ in $\mathbb{R}$. Since $k \ge 0$, we have $(k + 1) \Delta F_{\mathrm{opt}} \ge k + 1$. With $\Delta D_{\mathrm{opt}} \ge 0$ and $-\Delta\Phi \ge -k$, the right-hand side is bounded below by $(k + 1) + 0 - k = 1$.
· have hφ' : (w.delta_phi : ℝ) ≤ (k : ℝ) := by exact_mod_cast hφ have hf1' : (1 : ℝ) ≤ (w.delta_fetches_opt : ℝ) := by exact_mod_cast hf1 nlinarith
In Case 3, where the offline algorithm incurs at least 1 unit of delay and the potential increases by at most $k$, the amortized bound holds.
Casting the hypotheses gives $\Delta\Phi \le k$ and $\Delta D_{\mathrm{opt}} \ge 1$ in $\mathbb{R}$. Since $k \ge 0$, we have $(k + 1) \Delta D_{\mathrm{opt}} \ge k + 1$. Together with $\Delta F_{\mathrm{opt}} \ge 0$ and $-\Delta\Phi \ge -k$, the right-hand side is bounded below by $0 + (k + 1) - k = 1$.
· have hφ' : (w.delta_phi : ℝ) ≤ (k : ℝ) := by exact_mod_cast hφ have hd1' : (1 : ℝ) ≤ w.delta_delay_opt := by exact_mod_cast hd1 nlinarith
- The proof uses `exact_mod_cast` repeatedly to lift integer and natural-number inequalities into real-number inequalities before arithmetic reasoning.
- The final inequality in each branch is closed by `nlinarith`, which handles the bilinear products $(k + 1) \cdot \Delta F_{\mathrm{opt}}$ and $(k + 1) \cdot \Delta D_{\mathrm{opt}}$ along with linear bounds.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Amortized charge inequality for each payment window. -/theorem payment_window_amortized_bound {α : Type*} (k : ℕ) (w : PaymentWindow α k) : 1 ≤ (k + 1 : ℝ) * (w.delta_fetches_opt : ℝ) + (k + 1 : ℝ) * w.delta_delay_opt - (w.delta_phi : ℝ) := by have hd : 0 ≤ w.delta_delay_opt := w.delta_delay_nonneg have hf : (0 : ℝ) ≤ (w.delta_fetches_opt : ℝ) := by positivity have hk : (0 : ℝ) ≤ (k : ℝ) := by positivity rcases w.case_condition with h | ⟨hf1, hφ⟩ | ⟨hd1, hφ⟩ · have h' : (w.delta_phi : ℝ) ≤ -1 := by exact_mod_cast h nlinarith · have hφ' : (w.delta_phi : ℝ) ≤ (k : ℝ) := by exact_mod_cast hφ have hf1' : (1 : ℝ) ≤ (w.delta_fetches_opt : ℝ) := by exact_mod_cast hf1 nlinarith · have hφ' : (w.delta_phi : ℝ) ≤ (k : ℝ) := by exact_mod_cast hφ have hd1' : (1 : ℝ) ≤ w.delta_delay_opt := by exact_mod_cast hd1 nlinarith