one_fifo_payment_accounting
For all natural numbers k, P, and F_opt, every real number D_opt, and all natural numbers phi_0 and phi_final, if phi_0 = 0 and (P : ℝ) + (phi_final : ℝ) - (phi_0 : ℝ) ≤ (k + 1 : ℝ) * (F_opt : ℝ) + (k + 1 : ℝ) * D_opt, then (P : ℝ) ≤ (k + 1 : ℝ) * ((F_opt : ℝ) + D_opt).
Statement
theorem one_fifo_payment_accounting (k : ℕ) (P : ℕ) (F_opt : ℕ) (D_opt : ℝ) (phi_0 phi_final : ℕ) (h_phi_0 : phi_0 = 0) (h_acc : (P : ℝ) + (phi_final : ℝ) - (phi_0 : ℝ) ≤ (k + 1 : ℝ) * (F_opt : ℝ) + (k + 1 : ℝ) * D_opt) : (P : ℝ) ≤ (k + 1 : ℝ) * ((F_opt : ℝ) + D_opt)- Formalizes
- arXiv:2610.18767 Lemma 3.4
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- one_fifo_strictly_competitive_paging_with_delayFor any type α with decidable equality, any natural number k, and any paging with delay execution exec of type PagingWithDelayExecution α…
Read back from the Lean
For any natural numbers $k$, $P$, $F_{\mathrm{opt}}$, any real number $D_{\mathrm{opt}}$, and any natural numbers $\phi_0$ and $\phi_{\mathrm{final}}$: if $\phi_0 = 0$ and $$(P : \mathbb{R}) + (\phi_{\mathrm{final}} : \mathbb{R}) - (\phi_0 : \mathbb{R}) \le (k + 1 : \mathbb{R}) \cdot (F_{\mathrm{opt}} : \mathbb{R}) + (k + 1 : \mathbb{R}) \cdot D_{\mathrm{opt}},$$ then $$(P : \mathbb{R}) \le (k + 1 : \mathbb{R}) \cdot ((F_{\mathrm{opt}} : \mathbb{R}) + D_{\mathrm{opt}}).$$
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 bounds the payment cost P by (k + 1) times the offline cost (F_opt + D_opt) using a potential function accounting inequality. The proof expands the right-hand side of the goal by distributivity and substitutes the initial potential phi_0 = 0 into the accounting hypothesis, reducing its left-hand side to P + phi_final. Since the final potential phi_final is non-negative, linear arithmetic immediately concludes that P is bounded by the same upper bound.
The final potential phi_final is non-negative as a real number: (phi_final : ℝ) ≥ 0.
Because phi_final is a natural number, its embedding into the real numbers is non-negative.
uses
Nat.cast_nonneghave h_phi_final : (phi_final : ℝ) ≥ 0 := Nat.cast_nonneg phi_finalThe goal transforms to showing (P : ℝ) ≤ (k + 1 : ℝ) * (F_opt : ℝ) + (k + 1 : ℝ) * D_opt.
We apply the left distributive law to expand the product (k + 1) * (F_opt + D_opt) on the right-hand side of the goal.
uses
mul_addrw [mul_add]The accounting hypothesis simplifies to (P : ℝ) + (phi_final : ℝ) ≤ (k + 1 : ℝ) * (F_opt : ℝ) + (k + 1 : ℝ) * D_opt.
We substitute the hypothesis phi_0 = 0 into the accounting inequality and simplify by casting 0 to ℝ and evaluating the subtraction of 0.
uses
Nat.cast_zero,sub_zerosubst h_phi_0 simp only [Nat.cast_zero, sub_zero] at h_acc
(P : ℝ) ≤ (k + 1 : ℝ) * (F_opt : ℝ) + (k + 1 : ℝ) * D_opt. automation
Linear arithmetic over the real numbers deduces the goal directly from P + phi_final ≤ (k + 1) * F_opt + (k + 1) * D_opt and phi_final ≥ 0.
linarith
Nat.cast_nonneg- The canonical cast of any natural number into an ordered semiring (such as the real numbers) is non-negative.
mul_add- Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.
Nat.cast_zero- The cast of the natural number 0 into an additive monoid with one is 0.
sub_zero- Subtracting zero from any element in an additive group/monoid leaves it unchanged: a - 0 = a.
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.
/-- Number of payments of 1-FIFO is at most (k+1) times offline cost. -/theorem one_fifo_payment_accounting (k : ℕ) (P : ℕ) (F_opt : ℕ) (D_opt : ℝ) (phi_0 phi_final : ℕ) (h_phi_0 : phi_0 = 0) (h_acc : (P : ℝ) + (phi_final : ℝ) - (phi_0 : ℝ) ≤ (k + 1 : ℝ) * (F_opt : ℝ) + (k + 1 : ℝ) * D_opt) : (P : ℝ) ≤ (k + 1 : ℝ) * ((F_opt : ℝ) + D_opt) := by have h_phi_final : (phi_final : ℝ) ≥ 0 := Nat.cast_nonneg phi_final rw [mul_add] subst h_phi_0 simp only [Nat.cast_zero, sub_zero] at h_acc linarith