Theorem 4 — asymptotic relative cost increase
ProvedSpecActions.thm4_cost_limitAs the horizon grows, the relative cost increase of Algorithm 1 converges:
for all and , with the number of distinct actions across the branches. Paired with the asymptotic latency ratio, this is the closed-form Pareto trade-off the paper uses to choose the speculative breadth offline.
import Definitions.Def_SpecActions_model
import Definitions.Def_SpecActions_model
import Mathlib.Order.Filter.AtTopBot.Basic
namespace SpecActions
open Filter Topology
theorem thm4_cost_limit (α β pk kt : ℝ) (hα : 0 < α) (hβ : 0 < β)
(hpk0 : 0 ≤ pk) (hpk1 : pk ≤ 1) :
Tendsto (fun T : ℕ => (specCost T α β pk kt - seqCost T β) / seqCost T β)
atTop (𝓝 (kt - (kt + α / (α + β)) * (pk / (1 + pk)))) := by sorry
end SpecActions
Read-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back of thm4_cost_limit.
The statement fixes four real numbers together with exactly four hypotheses:
Nothing else is assumed about them. In particular there is no assumption relating and to each other (neither nor any ordering), and is a completely unconstrained real number — it may be negative, zero, or non-integral, and is not required to be a positive integer or to be related to in any way.
Two auxiliary quantities from the imported bundle enter the statement, and both must be unfolded.
First, the hit count , a real-valued function of a natural number defined by the total two-step recursion
This recursion is the only thing the statement knows about ; the separately-defined closed form is not referenced here, and no identity between the two is asserted.
Second, the two cost functions of a natural number (in both, is cast from into ):
where denotes truncated natural-number subtraction: it equals for and equals when .
The assertion is then a single limit statement about the relative cost gap
namely that the sequence converges, as runs to infinity through the natural numbers (along the "eventually, for all sufficiently large " filter), to the real number
in the standard topology of . This is a claim both that the limit exists and that its value is exactly the displayed expression; it is an unconditional two-sided convergence claim, not an inequality, not a bound, and not a one-sided or asymptotic-order estimate. Nothing is asserted about the rate of convergence, about monotonicity in , or about the value of at any particular finite .
Degenerate and boundary cases silently covered by the quantifiers:
- . Here and , so the quotient defining is , which in this setting evaluates to by the total-division convention rather than being undefined. Because the claim concerns only the behaviour for large , this value (and any finite number of initial values) has no bearing on the assertion.
- . Since , the denominator is nonzero, so is an ordinary quotient there.
- is permitted by . Then , so for every , and the claimed limit specializes to .
- is permitted by ; the claimed limit is then .
- negative or zero is permitted, in which case need not exceed and the limit value can be negative.
- No division by zero occurs in the limit expression: from , and from .
The four hypotheses are simultaneously satisfiable (for instance , , and any ), so the statement is not vacuous.
Finally, note the shape of the asserted limit value: it depends on and only through the single ratio , on only through , and is affine in ; the parameter does not otherwise appear in the limit, even though it appears in both cost functions.
Confirmed by the mission captain (proposal self-audit).