Lemma 4.5 — Recursive running time
ProvedNearlyOptimalPPR.Computation.recursive_running_timeFix the exact-SDDM model. There exist absolute chosen before every graph and parameter such that the following holds. Let be a finite simple unweighted undirected graph with a nonisolated seed , real and . Put
Use this balanced block at each level . The prescribed root call terminates and its actual charged work, equal to its expected value under the deterministic idealized solve charges, satisfies
For every , there is independent of such that the displayed envelope is at most for . This states the full bound; no fixed larger exponent replaces it.
The mathematical depth specifies this root-call analysis, not a free logarithm or square-root instruction in the goal's machine. Balanced blocks are obtained by the operational integer-power search, with preparation charged. Source-component completion and explicit output remain included in root work.
Differences from the source:
- encoding: K exp(O(sqrt(log(2K) log log(4K)))) = K^(1+o(1)) → uniform positive constants C,c and the full eventual exponent-1+eta assertion; reason: this makes both asymptotic quantifier orders explicit without changing their domain
- encoding: root call with the stated depth and balanced blocks → the operational root execution with the mathematically specified depth and charged integer block search; reason: depth selection is a parameter of this lemma; the existential goal machine must pay for all of its own parameter preparation
- encoding: expected root work → actual nonnegative root work under deterministic idealized solve charges; reason: these charges equal their expected values and nontermination is infinite
import Mathlib import Definitions.Def_NearlyOptimalPPR_Computation_push set_option autoImplicit false open Finset Matrix MeasureTheory open scoped ENNReal
namespace NearlyOptimalPPR.Computation
/-- Li, Xu, Yang, Zhou, STOC 2027 submission #884 (October 2026),
Lemma 4.5 pp.18--19. Quantitative envelope and the full 1+o(1) assertion. -/
theorem recursive_running_time (m : SolveModel) :
∃ C c : ℝ, 0 < C ∧ 0 < c ∧ subpolynomialEnvelope C c ∧
∀ (n : ℕ) (g : InputGraph n) (s : Fin n) (α ε : ℝ),
0 < α → α ≤ 1 / 2 → 0 < ε → ε ≤ 1 → 0 < g.graph.degree s →
let ℓ := balancedDepth ε
recursiveWork m g s α ε ℓ [] ≤ ENNReal.ofReal (envelope C c ε) ∧
∃ t : ℕ, (recursiveRun m g s α (rootThreshold ε ℓ) ℓ [] t).done = true := by sorry
end NearlyOptimalPPR.Computation
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.