Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

The core procedure of the modular counting oracle writes all counts of the candidates (Lemma 4.1)

Proved
Light.Filter.oCore_spec

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

apsp-2996001apsp-exponentfine-grained-complexityword-ram

Let P0+ ⁣ ⁣+RP_0\mathbin{+\!\!+}RP0​++R be a program containing the procedures of the counting oracle (OCoreCtx: the procedures of the host of Theorem 17 that it reuses, the loop over the instances, and a #Lop-AE-SparseTri solver with time TnT_nTn​ and need ν\nuν). Let xxx be an oracle instance: an Exact Triangle instance with nnn vertices per part and weight bound UUU (three n×nn\times nn×n matrices ABABAB, BCBCBC, ACACAC in memory), a block size 1≤s≤n1\le s\le n1≤s≤n, a modulus p≥1p\ge1p≥1 and a place cnt for the ⌈n/s⌉n2\lceil n/s\rceil n^2⌈n/s⌉n2 counts, with the precondition x.Pre at free pointer fff, the host ready at depth ddd for the data of the instances (oDataOf x), and the limits HostLim allowing the host and the solver.

Then the core body oCoreBody, run in the frame oCoreArgs x f, ends within blockCost+tcoreRun(Tn,oDataOf x,U)\mathrm{blockCost}+t_{\mathrm{coreRun}}(T_n,\mathrm{oDataOf}\,x,U)blockCost+tcoreRun​(Tn​,oDataOfx,U) steps and leaves the memory with the list cntList n s p AB BC AC at cnt (for the candidate i=jn2+an+bi=jn^2+an+bi=jn2+an+b, the number of ccc in the block [js,min⁡((j+1)s,n))[js,\min((j+1)s,n))[js,min((j+1)s,n)) with p∣w(a,b)+w(b,c)+w(a,c)p\mid w(a,b)+w(b,c)+w(a,c)p∣w(a,b)+w(b,c)+w(a,c)), changing no other cell below fff.

Lemma 4.1: with ρ=w(a,b) mod p\rho=w(a,b)\bmod pρ=w(a,b)modp, the count is the number of common neighbours of (a,ρ)(a,\rho)(a,ρ) and (b)(b)(b) in the lopsided graph with Xa,(c,r)=[w(a,c)≡r]X_{a,(c,r)}=[w(a,c)\equiv r]Xa,(c,r)​=[w(a,c)≡r], Y(c,r),b=[w(b,c)+ρ≡−r]Y_{(c,r),b}=[w(b,c)+\rho\equiv -r]Y(c,r),b​=[w(b,c)+ρ≡−r]; the queries are grouped by ρ\rhoρ and cut into chunks, so each block costs at most 2p+12p+12p+1 solver calls at inner dimension spspsp.

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 7c34437be804.

import Definitions.Def_APSP2996001_Defs2

set_option autoImplicit false
set_option relaxedAutoImplicit false

open Light
open Light.Filter
open ThreeSumApsp ThreeSumApsp.Spec Light.Sec3 Light.Sec3.Et17
variable {lim : Limits} {d : ℕ}
Formal statement
theorem Light.Filter.oCore_spec {P₀ R : Program} {ν : ONums} {Tn : List ℕ → ℕ} {need : List ℕ → Light.Need}
    (C : OCoreCtx P₀ R ν Tn need) (x : OracleInst) (μ : ℕ → ℤ) (fr : ℕ) (hpre : x.Pre μ fr)
    (hr : Ready lim d x.toTriInst (oDataOf x) μ fr)
    (hlim : HostLim lim (d + 1) (oDataOf x) x.U (hostAddr x.toTriInst (oDataOf x) fr) need) :
    Ends lim (P₀ ++ R) d (oCoreBody ν) ⟨Light.frame (oCoreArgs x fr), μ⟩
      (et17Addr.blockCost + tCoreRun Tn (oDataOf x) x.U)
      fun σ' => Seg σ'.mem x.cnt (cntList x.n x.s x.p x.AB x.BC x.AC) ∧
        KeptBut μ σ'.mem fr x.cnt x.len := 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/Filter/OracleCore.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 APSP2996001_Defs1 and APSP2996001_Defs2 (and APSP299791_Defs1 to APSP299791_Defs5 of the 2.99791 entry). It follows the technical note "Deterministic APSP via thin products" (6 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), Lemma 4.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