Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

The batched preprocessing of Theorem 30, in every program beginning with base58B

Proved
Light.Batch.preCoreB_base58B

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

apsp-2995561apsp-exponentfine-grained-complexityword-ram

For every RRR and standard limits, base58B ++ R meets PreCoreBSpec lim (base58B ++ R) cShared30: the preprocessing preCore(L,m,t,N,D,aX,aY,b0)(L,m,t,N,D,aX,aY,b_0)(L,m,t,N,D,aX,aY,b0​), for a source XXX (K0N×DK_0N\times DK0​N×D, entries bounded by UUU) at aX and the transpose of a source YYY (D×K0ND\times K_0ND×K0​N) at aY, under the limits Lim30, returns within tPreCoreP cShared30 p t steps and builds the data structure DSReadyA of the batched input arrays bArrayL (stdLayout hmL) X β, bArrayR (stdLayout hmL) Y β (shared stage, all tiles, tries), keeping the memory below b0b_0b0​.

The batched layout (Batch/Tiling): the source of the left side is a K0N×DK_0N\times DK0​N×D matrix XXX (row by row), that of the right side a D×K0ND\times K_0ND×K0​N matrix YYY (stored transposed); the slot (g,h)(g,h)(g,h) of the band β\betaβ holds the row block number (βK0+g)K0+h(\beta K_0+g)K_0+h(βK0​+g)K0​+h of the source, so one run of Theorem 30's data structure computes K02K_0^2K02​ independent block products.

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 3b45b374640a.

import Definitions.Def_APSP2995561_Defs2

set_option autoImplicit false
set_option relaxedAutoImplicit false

open Light
open Light.Batch
open ThreeSumApsp ThreeSumApsp.Spec Light.Sec4
Formal statement
theorem Light.Batch.preCoreB_base58B (R : Program) (lim : Limits) (std : Std lim) :
    PreCoreBSpec lim (base58B ++ R) cShared30 := 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/Batch/Program.lean of the campaign's modified copy of that library, which is not published; the new definitions it uses are in the platform definition bundles APSP2995561_Defs1 and APSP2995561_Defs2 (and APSP2996001_Defs1-2, APSP299791_Defs1-5 of the earlier entries). It follows the technical note "Deterministic APSP via thin products" (revised 7 October 2026) refining 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), Proposition 2.1.

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