Explicit thin matrix preprocessing bounds
Lax350013.MatrixPreprocessing · concepts/Lax350013/MatrixPreprocessing.lean · lax-350013
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Corollary 26 gives preprocessing time and space and time per query for and . Theorem 30 gives the underlying bounds at integer recursion parameters. Theorem 3 extends the trade-off to every and every positive query exponent. The callable versions also preserve memory and resource guarantees needed when these algorithms are used as subroutines.
Concept map
Evidence
Lean source view on GitHub
| 1 | /- |
| 2 | Copyright (c) 2026 Anthropic, PBC. All rights reserved. |
| 3 | Released under Apache 2.0 license as described in the file LICENSE. |
| 4 | SPDX-License-Identifier: Apache-2.0 |
| 5 | -/ |
| 6 | /- |
| 7 | Modified for the independent Lax packaging by Édouard Bonnet, 2026. |
| 8 | Derived from 3sum-apsp/EndStatement.lean / PaperStatements.lean at upstream commit e1a4e6508154ea59f030480661590a9fe3018011. |
| 9 | Changes: Lax module/namespace layout, separated concepts and proofs, archive |
| 10 | annotations, and compatibility with the archive Lean/mathlib environment. |
| 11 | See NOTICE and README.md in the submission root for provenance and scope. |
| 12 | -/ |
| 13 | |
| 14 | import Mathlib.Algebra.MvPolynomial.Basic |
| 15 | import Mathlib.Analysis.SpecialFunctions.Log.Base |
| 16 | import Mathlib.Analysis.SpecialFunctions.Log.Basic |
| 17 | import Mathlib.Analysis.SpecialFunctions.Pow.Real |
| 18 | import Mathlib.Combinatorics.SimpleGraph.Basic |
| 19 | import Mathlib.Data.Finset.Sort |
| 20 | import Mathlib.LinearAlgebra.Matrix.Notation |
| 21 | import Mathlib.MeasureTheory.Integral.Bochner.Basic |
| 22 | import Mathlib.NumberTheory.PrimeCounting |
| 23 | import Mathlib.Probability.Independence.Basic |
| 24 | import Mathlib.Tactic.DeriveFintype |
| 25 | import Lax350013.MatrixTradeoffs |
| 26 | import Lax350013.CallableAlgorithms |
| 27 | |
| 28 | /-! |
| 29 | --- |
| 30 | title: Explicit thin matrix preprocessing bounds |
| 31 | type: theorem |
| 32 | --- |
| 33 | Corollary 26 gives preprocessing time and space and time per query for and . Theorem 30 gives the underlying bounds at integer recursion parameters. Theorem 3 extends the trade-off to every and every positive query exponent. The callable versions also preserve memory and resource guarantees needed when these algorithms are used as subroutines. |
| 34 | -/ |
| 35 | |
| 36 | namespace Lax350013.MatrixPreprocessing |
| 37 | |
| 38 | open Finset |
| 39 | open Lax350013.WordRAM |
| 40 | open Lax350013.RAMResources |
| 41 | open Lax350013.ThinMatrices |
| 42 | open Lax350013.MatrixParameters |
| 43 | open Lax350013.MatrixTradeoffs |
| 44 | |
| 45 | /-- **Corollary 26**, first two sentences: "Let N ≥ D^18, and let X ∈ ℤ^{N×D} and Y ∈ ℤ^{D×N} |
| 46 | have entries of absolute value at most N^{O(1)}. We can preprocess them deterministically in |
| 47 | O(N²/D^{0.063}) time and space, after which any single entry (XY)[I,J] can be computed |
| 48 | deterministically in O(D^{0.437}) time." |
| 49 | |
| 50 | NOTE. The paper states no lower bound on `D`; `D ≥ 1` is assumed (for `D = 0` the bound |
| 51 | `O(D^{0.437})` would be 0 steps). -/ |
| 52 | def Corollary_26 : Prop := |
| 53 | ∀ c : ℕ, ∃ (P Q : List Instr) (qI qJ qOut : ℤ) (b : ℕ) (C : ℝ), |
| 54 | IsDataStructure P Q qI qJ qOut b [] (fun x => 1 ≤ x.D ∧ x.D ^ 18 ≤ x.N ∧ x.U = x.N ^ c) |
| 55 | (fun x => C * ((x.N : ℝ) ^ 2 / (x.D : ℝ) ^ (0.063 : ℝ))) |
| 56 | (fun x => C * ((x.N : ℝ) ^ 2 / (x.D : ℝ) ^ (0.063 : ℝ))) |
| 57 | (fun x => C * (x.D : ℝ) ^ (0.437 : ℝ)) |
| 58 | |
| 59 | /-- The hypotheses of **Theorem 30**: "Let m ≥ 1, D = 4^m, L ≥ 10m, 0 ≤ t ≤ m, and N ≥ √K |
| 60 | N₀", with entries "of absolute value at most N^{O(1)}". -/ |
| 61 | def theorem30Dom (c m L t : ℕ) (x : ThinPair) : Prop := |
| 62 | 1 ≤ m ∧ x.D = 4 ^ m ∧ 10 * m ≤ L ∧ t ≤ m ∧ Real.sqrt (K L m) * (N0 L m : ℝ) ≤ (x.N : ℝ) ∧ |
| 63 | x.U = x.N ^ c |
| 64 | |
| 65 | /-- **Theorem 30**: "we can preprocess them deterministically in time and space" (8). "After |
| 66 | this, any single entry (XY)[I,J] can be computed deterministically in O(L ∑_{d=0}^{t} |
| 67 | α_d) time." "The constants hidden in the O(·) depend only on the exponent in N^{O(1)}": the |
| 68 | constant `C` is chosen after the exponent `c` and before `m`, `L`, `t`. These parameters are given |
| 69 | to the preprocessing after `N` and `D`; the two programs do not depend on them. -/ |
| 70 | def Theorem_30 : Prop := |
| 71 | ∀ c : ℕ, ∃ (P Q : List Instr) (qI qJ qOut : ℤ) (b : ℕ) (C : ℝ), ∀ m L t : ℕ, |
| 72 | IsDataStructure P Q qI qJ qOut b [(m : ℤ), (L : ℤ), (t : ℤ)] (theorem30Dom c m L t) |
| 73 | (fun x => C * cost8 L m t x.N) (fun x => C * cost8 L m t x.N) (fun _ => C * costQuery L m t) |
| 74 | |
| 75 | /-- **Theorem 3**: "Let N ≥ D^18, and let X ∈ ℤ^{N×D}, Y ∈ ℤ^{D×N} have entries of absolute |
| 76 | value N^{O(1)}. The pair (X,Y) can be preprocessed deterministically in O(N²/D^{0.063}) time [...]. |
| 77 | After this, any single entry (XY)[I,J] can be computed deterministically in O(D^{0.437}) time [...]. |
| 78 | More generally, for every ε < 0.1204 and every q > 0 there is a γ > 0 such that, whenever D ≤ N^ε, |
| 79 | the pair can be preprocessed in O(N²/D^γ) time, after which any single entry can be computed in |
| 80 | O(D^q) time." The first part is `Corollary_26`. |
| 81 | |
| 82 | NOTE. The departures are those of the two definitions: `D ≥ 1` in the first part; `D ≥ 1` and |
| 83 | `N ≥ 1` in the second; and in both the space is bounded like the time, while the theorem speaks of |
| 84 | time only. -/ |
| 85 | def Theorem_3 : Prop := |
| 86 | Corollary_26 ∧ DataStructureBelow 0.1204 |
| 87 | |
| 88 | /-- Explicit thin matrix preprocessing bounds: Corollary 26. -/ |
| 89 | axiom corollary26 : Corollary_26 |
| 90 | |
| 91 | |
| 92 | /-- Explicit thin matrix preprocessing bounds: Theorem 30. -/ |
| 93 | axiom theorem30 : Theorem_30 |
| 94 | |
| 95 | |
| 96 | /-- Explicit thin matrix preprocessing bounds: Theorem 3. -/ |
| 97 | axiom theorem3 : Theorem_3 |
| 98 | |
| 99 | |
| 100 | /-- Callable contract proved by upstream `Light.Sec4.claim_corollary_26_wanted`. -/ |
| 101 | axiom callableCorollary26 : Lax350013.CallableAlgorithms.Claim.Corollary_26_wanted Lax350013.CallableAlgorithms.lightModel |
| 102 | |
| 103 | end Lax350013.MatrixPreprocessing |
| 104 |
From Mathlib
Mathlib.Algebra.MvPolynomial.BasicMathlib.Analysis.SpecialFunctions.Log.BaseMathlib.Analysis.SpecialFunctions.Log.BasicMathlib.Analysis.SpecialFunctions.Pow.RealMathlib.Combinatorics.SimpleGraph.BasicMathlib.Data.Finset.SortMathlib.LinearAlgebra.Matrix.NotationMathlib.MeasureTheory.Integral.Bochner.BasicMathlib.NumberTheory.PrimeCountingMathlib.Probability.Independence.BasicMathlib.Tactic.DeriveFintype
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments