Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.4 — Work at one recursive level

Proved
NearlyOptimalPPR.Computation.recursive_level_work

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 are absolute C>0C>0C>0 and a positive integer ccc, uniform over all graph inputs, real parameters, depths and levels. For every 0<ε≤10<\varepsilon\le10<ε≤1, depth ℓ\ellℓ and finite block schedule, put P=C(2+log⁡(2/ε)+ℓ)cP=C(2+\log(2/\varepsilon)+\ell)^cP=C(2+log(2/ε)+ℓ)c. Run Normalize from its prescribed root state on any nonisolated seed with 0<α≤1/20<\alpha\le1/20<α≤1/2.

Every finite execution prefix and every created call of scale NNN and block bbb have at most PN/bPN/bPN/b episodes and full solves. Every completed episode, and the current episode while open, has at most one child call. Every created call eventually closes, including by ancestor interruption or component completion.

Writing Rj(N)R_j(N)Rj​(N) for the actual uniform work envelope at level jjj, for j<ℓj<\ellj<ℓ and N≥1N\ge1N≥1,

Rj(N)≤P(N2b+NbRj+1(b))+PN.R_j(N)\le P\left(\frac{N^2}{b}+\frac N b R_{j+1}(b)\right)+PN.Rj​(N)≤P(bN2​+bN​Rj+1​(b))+PN.

At the leaf, for every N≥1N\ge1N≥1,

Rℓ(N)≤P(N2b+Nb).R_\ell(N)\le P\left(\frac{N^2}{b}+Nb\right).Rℓ​(N)≤P(bN2​+Nb).

Here bbb is the schedule's legal fixed or balanced block at that level and scale. The same PPP is used at every level. Child initialization is charged to the parent, and a push is charged to its producing call including all open-record updates and the crossing update.

These bounds retain the full recurrence and finite-prefix counts used to establish termination and the recursive exponent improvement. Work and suprema live in nonnegative extended reals, so finiteness is asserted by the inequalities.

Differences from the source:

  • encoding: P=C(2+log(2/epsilon)+ell)^c with sufficiently large absolute C,c → uniform existential C>0 and positive integer c before epsilon, depth, schedule, graph and level; reason: an integer exponent represents a sufficiently large polynomial overhead without input-dependent constants
  • encoding: O(P N) in the recurrence → P N after uniform enlargement of P; reason: the source explicitly permits this enlargement on p.18
  • encoding: counts on every finite valid execution prefix and eventual call termination → counts on operationally reachable prefixes, and eventual closure of every created call; reason: no termination or proof invariant is assumed when forming the prefix
  • encoding: expected per-call work → the supremum of actual nonnegative charged work with deterministic idealized primitive charges; reason: the charge equals its expected value and nontermination remains 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.4 p.18, finite-prefix and termination arguments pp.28--29.
P is uniform across inputs and levels. Its uniform enlargement absorbs the
absolute constant of O(P*N), as allowed on p.18. -/
theorem recursive_level_work (m : SolveModel) :
    ∃ (C : ℝ) (c : ℕ), 0 < C ∧ 0 < c ∧
      ∀ (ε : ℝ) (ℓ : ℕ) (schedule : BlockSchedule), 0 < ε → ε ≤ 1 →
        let P := overhead C c ε ℓ
        (∀ (n : ℕ) (g : InputGraph n) (s : Fin n) (α : ℝ),
          0 < α → α ≤ 1 / 2 → 0 < g.graph.degree s →
          ∀ (t id : ℕ) (info : CallInformation),
            let run := recursiveRun m g s α (rootThreshold ε ℓ) ℓ schedule
            (run t).information id = some info →
              ((run t).episodes id : ℝ) ≤ P * info.scale / info.block ∧
              ((run t).fullSolves id : ℝ) ≤ P * info.scale / info.block ∧
              (∀ k ∈ (run t).episodeChildCounts id, k ≤ 1) ∧
              (∀ i ≤ (run t).top, ((run t).frames i).id = id →
                ((run t).frames i).childrenThisEpisode ≤ 1) ∧
              ∃ t' ≥ t, id ∈ (run t').closed) ∧
        (∀ (j : ℕ) (N : ℝ), j < ℓ → 1 ≤ N →
          let b := blockScale schedule ℓ j N
          workEnvelope m ε ℓ schedule j N ≤
            ENNReal.ofReal P *
              (ENNReal.ofReal (N ^ 2 / b) +
                ENNReal.ofReal (N / b) * workEnvelope m ε ℓ schedule (j + 1) b) +
              ENNReal.ofReal (P * N)) ∧
        (∀ N : ℝ, 1 ≤ N →
          let b := blockScale schedule ℓ ℓ N
          workEnvelope m ε ℓ schedule ℓ N ≤ ENNReal.ofReal (P * (N ^ 2 / b + N * b))) := by sorry

end NearlyOptimalPPR.Computation
Source
Rong-Hua Li, Quanqing Xu, Yichun Yang, Junjie Zhou, STOC 2027 submission #884 (October 2026), Lemma 4.4 p.18; proof §§5.3–5.4 pp.28–29
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