Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Numeric propagation followed by activation has the source raw memory effect

Proved
NearlyOptimalPPR.Computation.exterior_activation_raw_exec

by Shuze Chen · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

Assume a represented exterior selection reaches the activation threshold after its source update, with valid parent-domain nesting and a represented nonnegative boundary counter. Let ddd be the selected vertex's degree, hhh the current top level, and w=16(ℓ+3)w=16(\ell+3)w=16(ℓ+3) the record width. The complete numeric-and-activation prefix has a finite execution with

t≤84w+442+(h+1)(4w+60)+d((h+1)(8w+39)+8w+50).t\le84w+442+(h+1)(4w+60)+d((h+1)(8w+39)+8w+50).t≤84w+442+(h+1)(4w+60)+d((h+1)(8w+39)+8w+50).

Its numeric payload is exactly the prescribed exterior residual/potential update followed by the activation record transformations. Its graph cache covers the enlarged stored set, and the selected level's list is the source prepended to its old active list, using three fresh cells after any newly stored adjacency row. Output is preserved and charged work increases by ttt. The degree/neighbor query count is tracked exactly.

The result describes the intermediate numeric and activation state before restoring queue coverage; that restoration is supplied separately by the touched-refresh theorem.

Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_runtime
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_buffers
open Finset Matrix
open scoped ENNReal
set_option autoImplicit false
noncomputable section
attribute [local instance] Classical.propDecidable
Formal statement
namespace NearlyOptimalPPR.Computation
open SparseQueue
theorem exterior_activation_raw_exec (m : SolveModel) {n : ℕ} (g : InputGraph n) (ω : ℕ → Bool)
    (logical : RecursiveState n) (s : Fin n) (α ε : ℝ) (ell length t boundary : ℕ) (v : Fin n)
    (st : MachineState) (hh : st.scalar.halted=false)
    (pm : RecursiveMachineMemory g s α ε ell length logical st) (hDepth : logical.top ≤ ell)
    (ht : t ≤ logical.top) (hvDomain : v ∈ parentDomain logical t)
    (hSubset : ∀ i ≤ logical.top, (logical.frames i).active ⊆ parentDomain logical i)
    (hSelected : st.scalar.core.ptrs 112=(t : ℤ)) (hv : st.scalar.core.ptrs 40=(v.val : ℤ))
    (hBoundary : logical.boundaryEdges=(boundary : ℤ))
    (hAdmit : relative logical t v+compilerExteriorDelta g α logical t v=3*(logical.frames t).q/8) :
    let width := 16*(ell+3)
    let δ := compilerExteriorDelta g α logical t v
    let free := if v ∈ logical.stored then st.scalar.core.ptrs 20 else st.scalar.core.ptrs 20+((g.neighbors v).length : ℤ)
    ∃ steps out, ∃ J : ℤ → ℤ,
      MachineEval m g ω exteriorNumericRawCode st steps out ∧
      steps ≤ 84*width+442+(logical.top+1)*(4*width+60)+
        (g.neighbors v).length*((logical.top+1)*(8*width+39)+8*width+50) ∧
      GraphCache g J width (insert v logical.stored) free ∧
      (∀ z, z ∉ cacheWriteCells width v.val (st.scalar.core.ptrs 20) (g.neighbors v).length → J z=st.scalar.integerMemory z) ∧
      J (vertexRecordAddress width v.val 1)=(if v ∈ logical.stored then st.scalar.integerMemory (vertexRecordAddress width v.val 1) else st.scalar.core.ptrs 20) ∧
      out.scalar.integerMemory=exteriorActivationIntegerMemory g v (logical.frames 0).active boundary t logical.top width free
        (exteriorNumericPayload g logical ell α t v δ J st.scalar.core.mem).1 ∧
      out.scalar.core.mem=exteriorActivationRealMemory (exteriorNumericPayload g logical ell α t v δ J st.scalar.core.mem).2
        v.val t logical.top width ((logical.frames t).q*LocalPush.deg g.graph v/2) (logical.frames t).openBudget ∧
      VertexListRep out.scalar.integerMemory (out.scalar.integerMemory (levelHeaderAddress t 1))
        (v::(pm.frames t ht).activeVertices) (nodeCells free ∪ (pm.frames t ht).activeFoot) ∧
      (∀ z ∈ nodeCells free ∪ (pm.frames t ht).activeFoot, z < free+3) ∧
      out.scalar.core.ptrs 20=free+3 ∧ out.scalar.core.ptrs 100=(logical.top : ℤ) ∧ out.scalar.core.ptrs 0=0 ∧
      out.scalar.core.ptrs 40=(v.val : ℤ) ∧ out.scalar.core.ptrs 116=(v.val : ℤ) ∧
      out.scalar.core.ptrs 120=((g.neighbors v).length : ℤ) ∧
      out.scalar.queries=st.scalar.queries+1+(if v ∈ logical.stored then 0 else (g.neighbors v).length+1)+(g.neighbors v).length ∧
      out.work=st.work+steps ∧ out.output=st.output ∧ out.scalar.halted=false := by sorry
end NearlyOptimalPPR.Computation
Source
Li, Xu, Yang, Zhou, Nearly optimal Personalized PageRank computation, STOC 2027 submission #884, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/884.pdf, Algorithms 1 and 6–9, pp. 5,14–22; charged local-machine realization of the mission computational model.

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