Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Analytic feasibility certificate for the APSP exponent 2.9929479187094

Proved
ApspBound.apsp_feasibility

by darkhipo · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

analysisasymptoticscomputational-complexitynumerical-analysisoptimization

Consider the aligned-cache reduction for All-Pairs Shortest Paths (APSP), whose cost accounting is organized into 47 inequalities spanning the geometric regimes of the reduction and the four cost phases (scalar stages x∈{0,u}x\in\{0,u\}x∈{0,u} and cyclic stages z∈{0,v}z\in\{0,v\}z∈{0,v}). Each inequality has the form target<Φ(T,G,q1)\text{target} < \Phi(T,G,q_1)target<Φ(T,G,q1​), where Φ\PhiΦ is affine in the entropic cost parameters TTT (box/cache formation), GGG (box gain) and q1q_1q1​ (residual query exponent), and the target is either 000 (a positivity or geometry condition) or the stage saving δ=3−2.9929479187094\delta = 3 - 2.9929479187094δ=3−2.9929479187094. This theorem is the closed analytic feasibility certificate: at the true real-logarithm parameters TTT, GGG, q1q_1q1​—obtained from the binary-entropy analysis and pinned inside their certified rational enclosures by proved logarithm bounds—every one of the 47 cost inequalities holds with a common strictly positive slack 2×10−142\times 10^{-14}2×10−14; in particular the check family has exactly 47 members. Equivalently, each of the six cost categories of the written reduction saves strictly more than δ\deltaδ below cubic time, uniformly over every stage, certifying that the exponent 2.99294791870942.99294791870942.9929479187094 (i.e. 3−δ3-\delta3−δ) is analytically feasible for the reduction's cost model. The theorem is a certificate of these 47 cost inequalities at exact real-logarithm parameters; it does not by itself constitute a complete word-RAM algorithm for APSP.

Preamble
import Definitions.Def_ApspBound_Model
Formal statement
import Definitions.Def_ApspBound_Model

theorem ApspBound.apsp_feasibility :
    ApspBound.Numerical.checks.length = 47 ∧
    ∀ check ∈ ApspBound.Numerical.checks,
      (check.target : ℝ) + ApspBound.Analytic.uniformSlack <
        ApspBound.Analytic.evalReal check.expression := by sorry
Source
Joshua Wharton (QFEX), APSP aligned-cache exponent refinement (2026). Certificate adapted from shreshth-s/thin-matrix-results, commit 8a21eaae81599913dba562727e03a9b48c36a5b9. Packaged and independently verified by the BigO strike, 2026-10-28.

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