Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§6.1 rounding bound — Bernstein's scaled graph G_i has positive integer weights and every ≤h-hop path of weight in [2^i, 2^{i+1}] has G_i-weight ≤ ⌈4h/ε⌉

Proved
DecrNearAddAPSP.W2.section_6_1_rounding

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

apaspdynamic-shortest-pathshopsetsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rounding

Let GGG be a weighted graph with positive integer weights, 0<ε<10<\varepsilon<10<ε<1, h≥1h\ge1h≥1 an integer hop parameter, i≥0i\ge0i≥0 an integer, and αi=ε 2i/h\alpha_i=\varepsilon\,2^i/hαi​=ε2i/h. The scaled graph GiG_iGi​ keeps the edges of weight at most 2i+12^{i+1}2i+1, rounds each kept weight up to the nearest integer multiple of αi\alpha_iαi​ and divides by αi\alpha_iαi​, so the edge eee gets weight ⌈w(e)/αi⌉\lceil w(e)/\alpha_i\rceil⌈w(e)/αi​⌉. Then:

  1. every edge of GiG_iGi​ has a positive integer weight: ⌈w(e)/αi⌉≥1\lceil w(e)/\alpha_i\rceil\ge1⌈w(e)/αi​⌉≥1 whenever w(e)≤2i+1w(e)\le 2^{i+1}w(e)≤2i+1;
  2. for every path ppp of GGG (any walk, simple or not) with at most hhh hops and 2i≤w(p)≤2i+12^i\le w(p)\le 2^{i+1}2i≤w(p)≤2i+1,
wGi(p)=∑e∈p⌈w(e)αi⌉ ≤ ⌈4hε⌉.w_{G_i}(p)=\sum_{e\in p}\Big\lceil\frac{w(e)}{\alpha_i}\Big\rceil\ \le\ \Big\lceil\frac{4h}{\varepsilon}\Big\rceil .wGi​​(p)=e∈p∑​⌈αi​w(e)​⌉ ≤ ⌈ε4h​⌉.

This is what lets an ES-tree on GiG_iGi​ run to depth ⌈4h/ε⌉\lceil 4h/\varepsilon\rceil⌈4h/ε⌉ independently of Wmax⁡W_{\max}Wmax​ (Bernstein's rounding, used by SCALE in §7).

Differences from the source:

  • reading: 0 < ε (the scaled graph is defined for the paper's ε) → 0 < ε < 1; reason: the standing range of the §6 tools (Theorem 7, Lemma B.2 p. 97); the bound fails for large ε, where h edges each rounded to 1 exceed ⌈4h/ε⌉
  • generalization: for each 0 ≤ i ≤ log(nW_max) → for every i ∈ ℕ; reason: the claim holds for each scale separately; the paper's range is a subset, so the statement specializes to it
  • encoding: every edge in G_i has a positive integer weight → 0 < ⌈w(e)/α_i⌉ in ℤ for every edge with w(e) ≤ 2^{i+1}; reason: the ceiling is an integer by type; the kept edges are those of weight ≤ 2^{i+1}
  • generalization: any path p of at most h hops in G → every walk of G (simple or not) with at most h edges; reason: p. 6 defines a path as a sequence of edges; every edge of p has weight ≤ w(p) ≤ 2^{i+1} and is kept, and the statement specializes to simple paths
  • reading: a graph G = (V, E) (Lemma statement); §5 p. 25: "each edge e ∈ E has a positive weight w(e) > 0" → G.PosWeights (every edge weight ≥ 1); reason: standing assumption of the weighted sections (§5 p. 25), with integer weights (p. 6)
Preamble
import Mathlib
import Definitions.Def_DecrNearAddAPSP_W2_Graphs
Formal statement
namespace DecrNearAddAPSP.W2

/-- **§6.1 rounding bound** (p. 36). Let `G` have positive integer weights, `0 < ε < 1`, `h ≥ 1` a
hop parameter, `i ∈ ℕ`, and `α_i = ε·2^i/h`. In the scaled graph `G_i` (edges of weight at most
`2^{i+1}`, weight `w` mapped to `⌈w/α_i⌉`) every edge has a positive integer weight, and every path
`p` of `G` (any walk, simple or not) with at most `h` hops and `2^i ≤ w(p) ≤ 2^{i+1}` has `w_{G_i}(p) ≤ ⌈4h/ε⌉`. -/
theorem section_6_1_rounding {n : ℕ} (G : WGraph (Fin n)) (hpos : G.PosWeights) (ε : ℝ)
    (hε0 : 0 < ε) (hε1 : ε < 1) (h i : ℕ) (hh : 1 ≤ h) :
    (∀ e ∈ G.adj.edgeSet, G.wt e ≤ 2 ^ (i + 1) → 0 < scaledWeight ε h i (G.wt e)) ∧
    (∀ (u v : Fin n) (p : G.adj.Walk u v), p.length ≤ h →
      2 ^ i ≤ G.walkWeight p → G.walkWeight p ≤ 2 ^ (i + 1) →
      scaledWalkWeight G ε h i p ≤ ⌈4 * (h : ℝ) / ε⌉) := by sorry

end DecrNearAddAPSP.W2
Source
Koveshi, Roditty, Sapir, First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted Graphs, arXiv:2611.04635 (PDF sha256 6bb2b230…), p. 36, §6.1
Human review
  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 11, 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