Theorem 6 — depth-focused relative cost
ProvedSpecActions.thm6_depth_costUnder the depth-focused policy with deterministic latencies and correctness probability , the relative cost increase is exactly
for every . A step whose guess is correct spends ; a step whose guess is wrong also pays for the branches spawned before the real response arrived, the series .
This is the exact identity. The paper immediately replaces it with the approximation , which agrees with the exact expression only when is an integer; the milestone asserts the exact floor version, which is what the proof establishes.
import Definitions.Def_SpecActions_model
import Definitions.Def_SpecActions_model
namespace SpecActions
theorem thm6_depth_cost (T : ℕ) (a b p : ℝ) (ha : 0 < a) (hb : 0 < b)
(hba : b < a) (hp0 : 0 ≤ p) (hp1 : p ≤ 1) (hT : 1 ≤ T) :
(depthSpecCost T a b p - depthSeqCost T a) / depthSeqCost T a
= ((T : ℝ) - 1) / (T : ℝ) *
((1 - p) * (a * ⌊a / b⌋ - b * ((1 + ⌊a / b⌋) * ⌊a / b⌋ / 2))
+ p * (b * ⌊a / b⌋)) / a := by sorry
end SpecActions
Read-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back — SpecActions.thm6_depth_cost
The declaration fixes one natural number and three real numbers , , , all universally quantified as explicit arguments, together with six hypotheses that are assumed to hold simultaneously:
- ,
- ,
- ,
- ,
- ,
- (an inequality between natural numbers, so and the case is excluded).
All arithmetic in the conclusion happens in : is cast from into , and every occurrence of is real subtraction of the cast, not truncated natural subtraction.
Two quantities imported from the definition bundle occur in the statement. Writing for the integer floor of the real quotient , cast back into (with one has , hence ), they are
Neither definition is given any meaning here beyond these formulas; in particular no probabilistic, temporal, or algorithmic interpretation of , , , , or of the two cost expressions is part of the claim.
The conclusion is the single equation
i.e. the relative excess of over , measured against , equals the displayed expression. The grouping on the right-hand side is: the factor is multiplied by the bracketed sum, and that whole product is then divided by .
Points the quantifiers silently cover:
- Division. The left-hand side divides by ; under the hypotheses and this is strictly positive, so no division-by-zero convention is invoked. Likewise and on the right.
- . Then and , so the left side is , and the factor makes the right side as well; the equation is the statement in this boundary case.
- and . Both endpoints are admitted; at only the term survives on the right, at only the term.
- Floor. is an integer-valued quantity depending on and ; the equation must hold for every real pair , including those where is an exact integer and those where it is not.
- Non-vacuity. The hypothesis set is satisfiable — e.g. , , , — so the statement is not vacuously true for want of admissible arguments.
Nothing beyond this pointwise algebraic identity is asserted: there is no existential claim, no inequality, no monotonicity or optimality statement, and no connection to the other definitions in the bundle (, , , , , -hit, or the speculation objective). The declaration is stated with its proof omitted (sorry), so it records the claim only.
Confirmed by the mission captain (proposal self-audit).