Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

allTiles builds the tries of all tiles of the Theorem 30 data structure (pruned encodings)

Proved
Light.Sec4.allTiles_spec

by xuanji · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

apsp-299791apsp-exponentdata-structuresprogram-verification

Let PPP be a program of the light language whose procedure number 515151 is the body of allTiles, and in which the routine tile meets its specification for the limits lim\mathrm{lim}lim. Then allTiles meets its specification for lim\mathrm{lim}lim:

consider nBn_BnB​ row bands and nBn_BnB​ column bands whose encodings encA(β),encB(β)\mathrm{enc}_A(\beta),\mathrm{enc}_B(\beta)encA​(β),encB​(β) are stored at aENCA+β 10La_{\mathrm{ENCA}}+\beta\,10^LaENCA​+β10L and aENCB+β 10La_{\mathrm{ENCB}}+\beta\,10^LaENCB​+β10L, a table of nB2n_B^2nB2​ root cells from aRa_RaR​, a trie area of cap\mathit{cap}cap cells from tr\mathit{tr}tr that holds the trie array [0][0][0] (its length in the cell fp\mathit{fp}fp), and scratch strings cur,box\mathit{cur},\mathit{box}cur,box. Assume the standing assumptions on the limits, t≤m≤Lt\le m\le Lt≤m≤L, that some bounds A,BA,BA,B on the encodings at the leaves with at most mmm nines satisfy 10mAB≤word10^m AB\le\mathrm{word}10mAB≤word, that 10L≤word10^L\le\mathrm{word}10L≤word, that 1+nB2⋅11 (1+L ∣B∣)≤cap1+n_B^2\cdot11\,(1+L\,|\mathcal B|)\le\mathit{cap}1+nB2​⋅11(1+L∣B∣)≤cap where ∣B∣|\mathcal B|∣B∣ is the number of boxes of a tile, and that the areas lie in this order without overlap below the end of memory. Then for every depth ddd with d+4≤depthd+4\le\mathrm{depth}d+4≤depth, the call allTiles(aENCA,aENCB,nB,10L,aR,tr,fp,cur,box,L,m−t)\mathrm{allTiles}(a_{\mathrm{ENCA}},a_{\mathrm{ENCB}},n_B,10^L,a_R,\mathit{tr},\mathit{fp},\mathit{cur},\mathit{box},L,m-t)allTiles(aENCA​,aENCB​,nB​,10L,aR​,tr,fp,cur,box,L,m−t) ends within

nB(nB (ttile(L,m,t)+80)+40)+30n_B\big(n_B\,(t_{\mathrm{tile}}(L,m,t)+80)+40\big)+30nB​(nB​(ttile​(L,m,t)+80)+40)+30

steps; afterwards the trie area holds the tries of all nB2n_B^2nB2​ tiles (tile (β,β′)(\beta,\beta')(β,β′) built from row band β\betaβ and column band β′\beta'β′, each holding the values of all its boxes), the root cells hold their roots, and no cell below cur\mathit{cur}cur or behind the trie area has changed.

Only the leaves with at most mmm nines of the encodings are read, so the routine works with the pruned encodings left by the shared stage.

“Procedure ppp meets its specification within TTT steps” means: called at any depth ddd allowed by the hypothesis, with the given argument values and a memory μ\muμ satisfying the precondition, the body of ppp terminates within TTT steps without violating the limits, and the returned value and final memory satisfy the postcondition.

Formalization Note The statement is P[Proc.allTiles]? = some allTilesBody → TileSpecP lim P → AllTilesSpecP lim P.

Preamble
/-
Copyright (c) 2026 Anthropic, PBC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
SPDX-License-Identifier: Apache-2.0
-/
-- Generated by skeleton subtraction from the ThreeSumApsp library at commit 27a2fa4bab32.

import Definitions.Def_APSP299791_Defs5

set_option autoImplicit false
set_option relaxedAutoImplicit false

open Light
open Light.Sec4
open ThreeSumApsp ThreeSumApsp.Spec
open AllTiles
Formal statement
theorem Light.Sec4.allTiles_spec {lim : Limits} {P : Program} (hP : P[Proc.allTiles]? = some allTilesBody)
    (hTile : TileSpecP lim P) : AllTilesSpecP lim P := by sorry
Source
Developed for the prove2.me APSP exponent campaign (https://prove2.me/campaigns/apsp-exponent) on top of the Lean formalization anthropics/formal-math, folder 3sum-apsp, commit e1a4e65 (https://github.com/anthropics/formal-math/tree/e1a4e6508154ea59f030480661590a9fe3018011/3sum-apsp; Lean v4.33.1, Mathlib v4.33.1). The statement comes from the file 3sum-apsp/ThreeSumApsp/Programs/Sec4/Theorem30/AllTiles.lean of the campaign's modified copy of that library, which is not published; the new and modified definitions it uses are in the platform definition bundles APSP299791_Defs1 to APSP299791_Defs5. It builds on J. Alman and V. Vassilevska Williams, "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs", arXiv:2610.06783v1 (https://arxiv.org/abs/2610.06783v1), Theorem 30 (pp. 46-47), "Preprocessing". This result belongs to an improvement of the paper's bounds developed for this campaign and is not stated in the paper.

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me