The online buy trajectory is nondecreasing
ProvedPrimalDualOnline.SkiRental.algX_monotoneLet be the purchase price of a ski-rental instance and let be the fractional buy variable after updates, run with the rate . Then the trajectory is nondecreasing:
This is the formal content of the online requirement the source imposes on the model. Chapter 3 states it twice: "The online requirement is that previous decisions cannot be regretted. That is, if we already rented skies yesterday, we cannot change this decision today. This requirement is captured in the primal linear program by the restriction that the primal variables cannot be decreased" (p. 17–18), and again when the fractional algorithm is introduced: "we require that they cannot be decreased during the execution of the algorithm" (p. 18).
Without it, the cost accounting would not describe an online algorithm at all: a procedure permitted to lower could revisit and undo a purchase commitment it had already made, which is precisely what the model forbids.
Source correspondence.
- What the thesis states: that the fractional primal variables may not decrease during execution — a requirement on the model, stated in prose, not a numbered lemma.
- What this Lean theorem states: that the particular trajectory generated by the mission's
algXat rate is a monotone function of the day index. - Strengthenings introduced by the formalization: this turns a model requirement into a proved property of the specific recursion. The source imposes non-decrease as a constraint on admissible algorithms; here it is derived for the algorithm actually defined. Nothing stronger is claimed — not strict increase, no bound on the values, no limit, and nothing about any other rate parameter.
import Definitions.Def_PrimalDualOnline_SkiRentalLP import Definitions.Def_PrimalDualOnline_SkiRentalAlg import Mathlib.Tactic open PrimalDualOnline.SkiRental
theorem PrimalDualOnline.SkiRental.algX_monotone
(B : ℕ) (hB : 0 < B) :
Monotone (algX B (cOpt B)) := by sorryRead-back
What the Lean code literally says, in plain math · claude-opus-5
Binders. The statement takes two arguments: a natural number (explicit), and a hypothesis . There are no other variables, no implicit arguments, and no typeclass assumptions. In particular the real parameter of the underlying sequence is not quantified: it is fixed to the single value .
The objects involved. For a natural number and a real number , the sequence is defined by recursion on its index:
where is coerced from into in both occurrences, and the branch test is the strict inequality (so the value exactly takes the second, stationary branch). The real constant is
with coerced to inside the base and used as a natural-number exponent. Both are plain definitions with no side conditions; all divisions are total real division, so a zero denominator yields rather than being undefined.
What is asserted. For every natural number with , the function is monotone in Mathlib's sense. For a function on ordered by the usual , this unfolds to the universally quantified, non-strict implication
Both index quantifiers are universal, the antecedent is the weak order on naturals, and the conclusion is the weak order on reals. The case is included and holds trivially; the quantifiers range over all natural indices.
What is not asserted. The statement does not claim strict increase, nor strict increase at any particular step; consecutive values may be equal, and the second branch of the recursion makes the sequence stationary once a value is reached. It states no upper or lower bound on the values — nothing says they lie in , nothing says they are nonnegative, nothing says they ever reach or stay below . It states nothing about a limit, convergence, supremum, or eventual behaviour, and nothing about the number of steps needed for any event. There is no finite horizon, index range, or truncation anywhere: the function is defined on all of and the claim is about all indices. Nothing is claimed about any other value of the parameter , and nothing about itself — no sign, no bound, no optimality or extremal property, no relation to any cost, ratio, or algorithm. There is no mention of any cost function, competitive ratio, adversary, primal or dual objective, or feasibility condition.
Degenerate cases. The hypothesis excludes exactly . Given total division, is not a meaningless instance but a concrete one: , hence , hence the increment is , so the recursion for would read on the branch — the constant zero sequence. The hypothesis removes that instance. At one has and the recursion is while , starting from ; so , and from then on the guard fails and the sequence is constantly — a case where the asserted inequality holds with equality for all .
Confirmed by the mission captain (proposal self-audit).