Algorithm cost equals times its dual objective
ProvedPrimalDualOnline.SkiRental.alg_cost_eq_ratio_mul_dualLet be the purchase price, the number of ski days, and run the fractional primal-dual algorithm with rate . Write for the primal objective of the algorithm's solution and for the dual objective it has accumulated. Then
This is an exact equality in both directions, with no error term. Combinatorially, on each active day the primal objective grows by while the dual grows by , and on each day after the buy variable has reached neither grows; summing over the days turns the per-day relation into an identity between the two totals, each equal to .
This statement is the pivot of the mission. It converts a question about the algorithm's cost, which depends on the whole request sequence, into a question about the dual objective, which weak duality makes a lower bound on the offline optimum.
Source correspondence — read this before attacking the target.
- What the thesis states (p. 18, claim (ii)): "in each iteration, the ratio between the change in the primal and dual objective functions is bounded by ." The headline claim is an inequality, and it is stated per iteration, not in aggregate.
- What the thesis's proof computes (p. 19): on an active day, "the increase in the primal objective function is " — an exact per-day equality, and the dual increase is exactly .
- What this Lean theorem states: an exact equality between the aggregate primal cost and times the aggregate dual objective.
- Introduced by the formalization: this is a derived strengthening, not a verbatim transcription. It strengthens the source's "bounded by" to an equality, and it aggregates what the source states per iteration. Both steps are licensed by the exact computation in the source's own proof, but neither is how the source phrases the claim. A reader comparing the mission against Chapter 3 should expect to find the per-day equality and the per-iteration bound there, and to find the aggregate equality only here.
Formalization Note. The primal objective is read at the final buy level together with the rent variables at indices ; index contributes a buy term but no rent term. Both totals vanish at and are constant in once .
import Definitions.Def_PrimalDualOnline_SkiRentalLP import Definitions.Def_PrimalDualOnline_SkiRentalAlg import Mathlib.Tactic open PrimalDualOnline.SkiRental
theorem PrimalDualOnline.SkiRental.alg_cost_eq_ratio_mul_dual
(B : ℕ) (hB : 0 < B) (k : ℕ) :
algCost B (cOpt B) k = (1 + 1 / cOpt B) * algDualValue B (cOpt B) k := by sorryRead-back
What the Lean code literally says, in plain math · claude-opus-5
Binders. The statement quantifies over exactly two variables, both explicit: natural numbers and . It carries exactly one hypothesis, . There are no implicit arguments, no typeclass assumptions, no other side conditions — nothing constrains relative to , and nothing constrains the free parameter , because the statement instantiates it at one specific value.
The constant. , a real base raised to a natural-number power. The scalar on the right-hand side is
For this is when and lies in in general; the statement does not name, bound, or characterize it beyond writing it as that expression.
The sequences. With fixed throughout:
and, each looking at the same index (not ), if else , and if else .
The two sides, expanded. The left-hand side is the "primal cost" of the pair : . The right-hand side is the scalar times a plain sum: . Both sums run over the indices and are empty when .
What each side evaluates to combinatorially. Since indicates , the dual sum counts indices: . Unwinding the recursion with , as long as the guard holds , so exactly for , exactly, and for ; hence the count is . The primal side collapses correspondingly, and both sides equal
Exactness. The claim is an equality of real numbers, not an inequality in either direction and not an asymptotic or approximate relation: no error term, no limit, no "for sufficiently large ". The factor is asserted to be attained on the nose, for every and every .
Index asymmetry. The two sides do not range over the same indices. The left side evaluates at index — one past the last index appearing in either sum — and adds the terms ; the right side involves only and has no term at index . Moreover and are both computed from , the value before the -th update, whereas uses the value after updates.
Degenerate cases. : both sums empty, , so the claim reads . : exactly and both sides equal ; but index is outside the summation range anyway. : the sequence is frozen at and all summands with index vanish, so both sides are constant in ; the equality for large carries no more information than at . : , factor exactly , and for the claim reads . is excluded, though all expressions remain well-formed under .
What is NOT asserted. No optimality, minimality, or competitive-ratio claim: no offline optimum, adversary, or comparison quantity appears, so nothing says the ratio compares the cost to anything other than . Nothing asserts is the best, unique, or only constant with this property, and nothing for any other . No feasibility claim: not that , not that , not that is feasible for any dual program; the words "primal" and "dual" in the definition names carry no asserted linear-programming content, and no weak- or strong-duality statement is present. No structural facts about the sequence are asserted, even though they follow from the definitions: not , not monotonicity, not , not the closed form. Neither side is asserted to equal or the scaled version — that identification is a consequence of unfolding, not part of the statement. Nothing about limits as or about , nothing about any interpretation as days, prices, or decisions, and nothing about any algorithm's behaviour beyond the literal arithmetic identity.
Confirmed by the mission captain (proposal self-audit).