Faster computation of selected matrix-product entries
Lax350013.SparseMatrixProduct · concepts/Lax350013/SparseMatrixProduct.lean · lax-350013
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Theorem 1 computes up to selected entries in time when and . More generally, for , , any selected entries admit a polynomial saving for every . The individual statements also record Theorems 5, 25 and 30 and Corollaries 26 and 32. The callable versions also preserve memory and resource guarantees needed when these algorithms are used as subroutines.
Concept map
Evidence
This concept declares 7 statements. Each proof establishes one of them relative to its assumptions.
1 callableTheorem5 proven
2 corollary26_wanted proven
3 corollary32 proven
4 theorem1 proven
5 theorem25 proven
6 theorem30_wanted proven
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.MatrixPreprocessing |
| 26 | import Lax350013.CallableAlgorithms |
| 27 | |
| 28 | /-! |
| 29 | --- |
| 30 | title: Faster computation of selected matrix-product entries |
| 31 | type: theorem |
| 32 | --- |
| 33 | Theorem 1 computes up to selected entries in time when and . More generally, for , , any selected entries admit a polynomial saving for every . The individual statements also record Theorems 5, 25 and 30 and Corollaries 26 and 32. The callable versions also preserve memory and resource guarantees needed when these algorithms are used as subroutines. |
| 34 | -/ |
| 35 | |
| 36 | namespace Lax350013.SparseMatrixProduct |
| 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 | open Lax350013.MatrixPreprocessing |
| 45 | |
| 46 | /-- **Theorem 5**: "Let D ≥ 4 be a power of four and N ≥ D^18. Given as input matrices X ∈ |
| 47 | ℤ^{N×D} and Y ∈ ℤ^{D×N}, whose entries are integers of absolute value at most N^{O(1)}, as well as a |
| 48 | set W of at most N²/√D positions of an N × N matrix, the entries (XY)[I,J], (I,J) ∈ W, can be |
| 49 | computed deterministically in time O(N² log² D/D^{1/18})." `c` is the exponent hidden in |
| 50 | `N^{O(1)}`. (As a statement about the existence of programs, this follows from |
| 51 | `Corollary_26_wanted`, whose bound is smaller on these inputs: a statement of this kind cannot say |
| 52 | by which algorithm a bound is reached.) -/ |
| 53 | def Theorem_5 : Prop := |
| 54 | ∀ c : ℕ, ∃ (P : List Instr) (b : ℕ) (C : ℝ), |
| 55 | Solves (thinProduct []) P b |
| 56 | (fun x => (∃ k : ℕ, x.D = 4 ^ k) ∧ 4 ≤ x.D ∧ x.D ^ 18 ≤ x.N ∧ |
| 57 | (x.W.length : ℝ) ≤ (x.N : ℝ) ^ 2 / Real.sqrt x.D ∧ x.U = x.N ^ c) |
| 58 | (fun x => C * ((x.N : ℝ) ^ 2 * Real.log x.D ^ 2 / (x.D : ℝ) ^ (1 / 18 : ℝ))) |
| 59 | |
| 60 | /-- **Theorem 25**: "For every ε < ε* and every κ > 0 there is a γ > 0 such that the |
| 61 | following holds. Given as input matrices [...], where 2 ≤ D ≤ N^ε, [...] as well as a set W of at |
| 62 | most N²/D^κ positions of an N × N matrix, the entries (XY)[I,J], (I,J) ∈ W, can be computed |
| 63 | deterministically in time O(N² log² D/D^γ)." -/ |
| 64 | def Theorem_25 : Prop := |
| 65 | ∀ ε κ : ℝ, ε < epsStar → 0 < κ → ∃ γ : ℝ, 0 < γ ∧ |
| 66 | ∀ c₀ : ℕ, ∃ (P : List Instr) (b : ℕ) (C : ℝ), |
| 67 | Solves (thinProduct []) P b |
| 68 | (fun x => thinDom 2 ε c₀ x.toThinPair ∧ (x.W.length : ℝ) ≤ (x.N : ℝ) ^ 2 / (x.D : ℝ) ^ κ) |
| 69 | (fun x => C * ((x.N : ℝ) ^ 2 * Real.log x.D ^ 2 / (x.D : ℝ) ^ γ)) |
| 70 | |
| 71 | /-- **Corollary 26**, last sentence: "Hence, for every set W of positions of an N × N |
| 72 | matrix, the entries (XY)[I,J], (I,J) ∈ W, can be computed deterministically in O(|W| D^{0.437} + |
| 73 | N²/D^{0.063}) time". (With `D ≥ 1`, as in `Corollary_26`.) -/ |
| 74 | def Corollary_26_wanted : Prop := |
| 75 | ∀ c : ℕ, ∃ (P : List Instr) (b : ℕ) (C : ℝ), |
| 76 | Solves (thinProduct []) P b (fun x => 1 ≤ x.D ∧ x.D ^ 18 ≤ x.N ∧ x.U = x.N ^ c) |
| 77 | (fun x => C * ((x.W.length : ℝ) * (x.D : ℝ) ^ (0.437 : ℝ) + |
| 78 | (x.N : ℝ) ^ 2 / (x.D : ℝ) ^ (0.063 : ℝ))) |
| 79 | |
| 80 | /-- **Theorem 30**, the offline form (9): "In particular, for every set W of positions of |
| 81 | an N × N matrix, the entries (XY)[I,J], (I,J) ∈ W, can be computed deterministically in time O(L |W| |
| 82 | ∑_{d=0}^{t} α_d + L m ρ^t/(1 − ρ) N² + N·10^L/(√K N₀))." -/ |
| 83 | def Theorem_30_wanted : Prop := |
| 84 | ∀ c : ℕ, ∃ (P : List Instr) (b : ℕ) (C : ℝ), ∀ m L t : ℕ, |
| 85 | Solves (thinProduct [(m : ℤ), (L : ℤ), (t : ℤ)]) P b |
| 86 | (fun x => theorem30Dom c m L t x.toThinPair) |
| 87 | (fun x => C * cost9 L m t x.N x.W.length) |
| 88 | |
| 89 | /-- **Corollary 32**: "Let c, θ, γ, q, X, Y, D, and ε be as in Corollary 31, and let κ > 0. |
| 90 | For every set W of at most N²/D^κ positions of an N × N matrix, the entries (XY)[I,J], (I,J) ∈ W, |
| 91 | can be computed deterministically in time O(N² log² D (D^{−γ} + D^{q−κ}))". -/ |
| 92 | def Corollary_32 : Prop := |
| 93 | ∀ c θ ε κ : ℝ, 10 < c → 0 < θ → θ < 0.9 → ε < Rc c (gammaOf c θ) → 0 < κ → |
| 94 | ∀ c₀ : ℕ, ∃ (P : List Instr) (b : ℕ) (C : ℝ), |
| 95 | Solves (thinProduct []) P b |
| 96 | (fun x => thinDom 2 ε c₀ x.toThinPair ∧ (x.W.length : ℝ) ≤ (x.N : ℝ) ^ 2 / (x.D : ℝ) ^ κ) |
| 97 | (fun x => C * ((x.N : ℝ) ^ 2 * Real.log x.D ^ 2 * |
| 98 | ((x.D : ℝ) ^ (-gammaOf c θ) + (x.D : ℝ) ^ (qOf θ - κ)))) |
| 99 | |
| 100 | /-- For every `ε < ε₀` and every `κ > 0` there is a `γ > 0` such that, whenever `D ≤ N^ε`, the |
| 101 | entries at any set of at most `N²/D^κ` positions can be computed in `O(N²/D^γ)` time. The paper has |
| 102 | this sentence with `ε₀ = 0.1204` (Theorem 1). |
| 103 | |
| 104 | NOTE. The paper states no lower bound on `D` and `N` here; `D ≥ 1` and `N ≥ 1` are assumed. On the |
| 105 | case `D = 1`, which Theorem 25 and Corollary 32 exclude, see the NOTE at `DataStructureBelow`. -/ |
| 106 | def WantedBelow (ε₀ : ℝ) : Prop := |
| 107 | ∀ ε κ : ℝ, ε < ε₀ → 0 < κ → ∃ γ : ℝ, 0 < γ ∧ |
| 108 | ∀ c₀ : ℕ, ∃ (P : List Instr) (b : ℕ) (C : ℝ), |
| 109 | Solves (thinProduct []) P b |
| 110 | (fun x => thinDom 1 ε c₀ x.toThinPair ∧ (x.W.length : ℝ) ≤ (x.N : ℝ) ^ 2 / (x.D : ℝ) ^ κ) |
| 111 | (fun x => C * ((x.N : ℝ) ^ 2 / (x.D : ℝ) ^ γ)) |
| 112 | |
| 113 | /-- **Theorem 1**: "Let N ≥ D^18, let X ∈ ℤ^{N×D} and Y ∈ ℤ^{D×N} have entries of absolute |
| 114 | value N^{O(1)}, and let W be any set of |W| ≤ N²/√D positions. The entries (XY)[I,J], (I,J) ∈ W, |
| 115 | can be computed deterministically in O(N²/D^{0.063}) operations on O(log N)-bit integers. More |
| 116 | generally, for every ε < 0.1204 and every κ > 0 there is a γ > 0 such that, whenever D ≤ N^ε |
| 117 | and |W| ≤ N²/D^κ, the task takes O(N²/D^γ) operations." |
| 118 | |
| 119 | NOTE. The paper states no lower bound on `D`; `D ≥ 1` is assumed, and in the last sentence also |
| 120 | `N ≥ 1` (see `WantedBelow`). -/ |
| 121 | def Theorem_1 : Prop := |
| 122 | (∀ c₀ : ℕ, ∃ (P : List Instr) (b : ℕ) (C : ℝ), |
| 123 | Solves (thinProduct []) P b |
| 124 | (fun x => 1 ≤ x.D ∧ x.D ^ 18 ≤ x.N ∧ (x.W.length : ℝ) ≤ (x.N : ℝ) ^ 2 / Real.sqrt x.D ∧ |
| 125 | x.U = x.N ^ c₀) |
| 126 | (fun x => C * ((x.N : ℝ) ^ 2 / (x.D : ℝ) ^ (0.063 : ℝ)))) ∧ |
| 127 | WantedBelow 0.1204 |
| 128 | |
| 129 | /-- Faster computation of selected matrix-product entries: Theorem 5. -/ |
| 130 | axiom theorem5 : Theorem_5 |
| 131 | |
| 132 | |
| 133 | /-- Faster computation of selected matrix-product entries: Theorem 25. -/ |
| 134 | axiom theorem25 : Theorem_25 |
| 135 | |
| 136 | |
| 137 | /-- Faster computation of selected matrix-product entries: Corollary 26 wanted. -/ |
| 138 | axiom corollary26_wanted : Corollary_26_wanted |
| 139 | |
| 140 | |
| 141 | /-- Faster computation of selected matrix-product entries: Theorem 30 wanted. -/ |
| 142 | axiom theorem30_wanted : Theorem_30_wanted |
| 143 | |
| 144 | |
| 145 | /-- Faster computation of selected matrix-product entries: Corollary 32. -/ |
| 146 | axiom corollary32 : Corollary_32 |
| 147 | |
| 148 | |
| 149 | /-- Faster computation of selected matrix-product entries: Theorem 1. -/ |
| 150 | axiom theorem1 : Theorem_1 |
| 151 | |
| 152 | |
| 153 | /-- Callable contract proved by upstream `Light.Sec2.claim_theorem_5`. -/ |
| 154 | axiom callableTheorem5 : Lax350013.CallableAlgorithms.Claim.Theorem_5 Lax350013.CallableAlgorithms.lightModel |
| 155 | |
| 156 | end Lax350013.SparseMatrixProduct |
| 157 |
Used by
none
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