AFTD Auto-Formalizing Theoretical Domains

one_fifo_payment_accounting

theoremverifiedformalization

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

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.

  1. 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.

    line 3

    uses Nat.cast_nonneg

      have h_phi_final : (phi_final : ℝ) ≥ 0 := Nat.cast_nonneg phi_final
  2. The 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.

    line 4

    uses mul_add

      rw [mul_add]
  3. 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.

    lines 5–6

    uses Nat.cast_zero, sub_zero

      subst h_phi_0
      simp only [Nat.cast_zero, sub_zero] at h_acc
  4. (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.

    line 7

      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

/-- 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
See it in the graphDiscuss this resultChallenge it