Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.5 — Recursive running time

Proved
NearlyOptimalPPR.Computation.recursive_running_time

by mikedeng1 · Nov 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1pageranksddm-solvers

Fix the exact-SDDM model. There exist absolute C,c>0C,c>0C,c>0 chosen before every graph and parameter such that the following holds. Let GGG be a finite simple unweighted undirected graph with a nonisolated seed sss, real 0<α≤1/20<\alpha\le1/20<α≤1/2 and 0<ε≤10<\varepsilon\le10<ε≤1. Put

K=1/ε,ℓ=⌊log⁡(2K)log⁡log⁡(4K)⌋,b=⌊N(ℓ−j+1)/(ℓ−j+2)⌋.K=1/\varepsilon,\qquad\ell=\left\lfloor\sqrt{\frac{\log(2K)}{\log\log(4K)}}\right\rfloor,\qquad b=\left\lfloor N^{(\ell-j+1)/(\ell-j+2)}\right\rfloor.K=1/ε,ℓ=⌊loglog(4K)log(2K)​​⌋,b=⌊N(ℓ−j+1)/(ℓ−j+2)⌋.

Use this balanced block at each level jjj. The prescribed root call terminates and its actual charged work, equal to its expected value under the deterministic idealized solve charges, satisfies

EW≤CKexp⁡ ⁣(clog⁡(2K)log⁡log⁡(4K)).\mathbb E W\le C K\exp\!\left(c\sqrt{\log(2K)\log\log(4K)}\right).EW≤CKexp(clog(2K)loglog(4K)​).

For every η>0\eta>0η>0, there is 0<ε0≤10<\varepsilon_0\le10<ε0​≤1 independent of G,s,αG,s,\alphaG,s,α such that the displayed envelope is at most K1+ηK^{1+\eta}K1+η for 0<ε≤ε00<\varepsilon\le\varepsilon_00<ε≤ε0​. This states the full K1+o(1)K^{1+o(1)}K1+o(1) 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
Preamble
import Mathlib
import Definitions.Def_NearlyOptimalPPR_Computation_push

set_option autoImplicit false

open Finset Matrix MeasureTheory
open scoped ENNReal
Formal statement
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
Source
Rong-Hua Li, Quanqing Xu, Yichun Yang, Junjie Zhou, STOC 2027 submission #884 (October 2026), Lemma 4.5 pp.18–19
Human review
  • Endorsed by Shuze Chen · Nov 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me