Theorem 3 / Corollary 5 — optimality of the greedy threshold breadth
ProvedSpecActions.greedy_threshold_optimalFix a continuation value and a marginal cost , and consider the per-window objective
with as above and confidences sorted in descending order. If is an index at which the greedy stopping rule fires — that is, for every and for every — then maximizes over .
This is the structural content of the confidence-aware selection theorem: the dynamic program collapses to a one-dimensional trade-off, so at runtime the system sorts confidences and adds branches greedily while the incremental hit probability scaled by exceeds , in per step.
import Definitions.Def_SpecActions_model
import Definitions.Def_SpecActions_model
namespace SpecActions
theorem greedy_threshold_optimal (pv : ℕ → ℝ) (Δ c : ℝ) (k : ℕ)
(hΔ : 0 < Δ) (hc : 0 < c)
(hpv0 : ∀ j, 0 ≤ pv j) (hpv1 : ∀ j, pv j ≤ 1)
(hsorted : ∀ i j, i ≤ j → pv j ≤ pv i)
(m : ℕ) (hm : m ≤ k)
(hbelow : ∀ j < m, c ≤ Δ * dqhit pv j)
(habove : ∀ j, m ≤ j → Δ * dqhit pv j ≤ c) :
∀ n ≤ k, specObjective pv Δ c n ≤ specObjective pv Δ c m := by sorry
end SpecActions
Read-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back — SpecActions.greedy_threshold_optimal.
The statement fixes an infinite sequence of real numbers , written (the argument pv), two real parameters and , and a natural number . Three quantities from the imported bundle appear in it, and they mean literally the following, for a natural number :
so that, written out fully, the objective being compared is
where the index of the second term is the natural number regarded as a real number. The products are over the indices ; for the product is empty and equals , hence , , and .
Hypotheses assumed. (i) ; (ii) ; (iii) for every natural number ; (iv) for every natural number ; (v) the sequence is non-increasing in the weak sense that for all natural with one has ; (vi) a natural number is given together with ; (vii) (below-threshold) for every natural with ,
(viii) (above-threshold) for every natural with — this includes itself and all indices beyond , the quantification being over all of —
Both threshold inequalities are non-strict, and they point in opposite directions on the two index ranges, which are disjoint ( versus ), so no index is constrained by both.
Conclusion asserted. For every natural number with ,
That is: among the indices , the given index attains a value of that is at least as large as that of any other index in that range.
Scope and degenerate cases. The comparison is made only over ; nothing is claimed about for . The inequality is non-strict, so no uniqueness of the maximizing index is claimed, and is not asserted to be the least or the greatest such index — it is supplied as a hypothesis-satisfying input, and no claim is made that an index satisfying (vi)–(viii) exists. If then is forced and the conclusion reduces to . If , hypothesis (vii) is vacuous and (viii) constrains every index ; the conclusion then says for all . Hypotheses (iii), (iv), (v) and (viii) constrain the entire infinite sequence, not merely its first entries, even though the conclusion only involves indices up to . Because , each factor lies in ; if some then every product with an index range reaching past vanishes, so and for all . The hypothesis set is jointly satisfiable — for instance for all with and any , any — so the statement is not vacuous. The identity relating to increments of is not part of what is asserted; enters only through hypotheses (vii) and (viii), and only through the objective .
Confirmed by the mission captain (proposal self-audit).