Faster computation of selected matrix-product entries

Lax350013.SparseMatrixProduct · concepts/Lax350013/SparseMatrixProduct.lean · lax-350013

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Theorem 1 computes up to N2/DN^2/\sqrt D selected entries in O(N2/D0.063)O(N^2/D^{0.063}) time when 1≤D1\leq D and D18≤ND^{18}\leq N. More generally, for D≤NεD\leq N^\varepsilon, ε<0.1204\varepsilon<0.1204, any N2/DκN^2/D^\kappa selected entries admit a polynomial saving for every κ>0\kappa>0. 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
    13 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Lean source view on GitHub

    1/-
    2Copyright (c) 2026 Anthropic, PBC. All rights reserved.
    3Released under Apache 2.0 license as described in the file LICENSE.
    4SPDX-License-Identifier: Apache-2.0
    5-/
    6/-
    7Modified for the independent Lax packaging by Édouard Bonnet, 2026.
    8Derived from 3sum-apsp/EndStatement.lean / PaperStatements.lean at upstream commit e1a4e6508154ea59f030480661590a9fe3018011.
    9Changes: Lax module/namespace layout, separated concepts and proofs, archive
    10annotations, and compatibility with the archive Lean/mathlib environment.
    11See NOTICE and README.md in the submission root for provenance and scope.
    12-/
    13
    14import Mathlib.Algebra.MvPolynomial.Basic
    15import Mathlib.Analysis.SpecialFunctions.Log.Base
    16import Mathlib.Analysis.SpecialFunctions.Log.Basic
    17import Mathlib.Analysis.SpecialFunctions.Pow.Real
    18import Mathlib.Combinatorics.SimpleGraph.Basic
    19import Mathlib.Data.Finset.Sort
    20import Mathlib.LinearAlgebra.Matrix.Notation
    21import Mathlib.MeasureTheory.Integral.Bochner.Basic
    22import Mathlib.NumberTheory.PrimeCounting
    23import Mathlib.Probability.Independence.Basic
    24import Mathlib.Tactic.DeriveFintype
    25import Lax350013.MatrixPreprocessing
    26import Lax350013.CallableAlgorithms
    27
    28/-!
    29---
    30title: Faster computation of selected matrix-product entries
    31type: theorem
    32---
    33Theorem 1 computes up to N2/DN^2/\sqrt D selected entries in O(N2/D0.063)O(N^2/D^{0.063}) time when 1≤D1\leq D and D18≤ND^{18}\leq N. More generally, for D≤NεD\leq N^\varepsilon, ε<0.1204\varepsilon<0.1204, any N2/DκN^2/D^\kappa selected entries admit a polynomial saving for every κ>0\kappa>0. 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
    36namespace Lax350013.SparseMatrixProduct
    37
    38open Finset
    39open Lax350013.WordRAM
    40open Lax350013.RAMResources
    41open Lax350013.ThinMatrices
    42open Lax350013.MatrixParameters
    43open Lax350013.MatrixTradeoffs
    44open 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
    48set W of at most N²/√D positions of an N × N matrix, the entries (XY)[I,J], (I,J) ∈ W, can be
    49computed 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
    52by which algorithm a bound is reached.) -/
    53def 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
    61following holds. Given as input matrices [...], where 2 ≤ D ≤ N^ε, [...] as well as a set W of at
    62most N²/D^κ positions of an N × N matrix, the entries (XY)[I,J], (I,J) ∈ W, can be computed
    63deterministically in time O(N² log² D/D^γ)." -/
    64def 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
    72matrix, the entries (XY)[I,J], (I,J) ∈ W, can be computed deterministically in O(|W| D^{0.437} +
    73N²/D^{0.063}) time". (With `D ≥ 1`, as in `Corollary_26`.) -/
    74def 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
    81an 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₀))." -/
    83def 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.
    90For every set W of at most N²/D^κ positions of an N × N matrix, the entries (XY)[I,J], (I,J) ∈ W,
    91can be computed deterministically in time O(N² log² D (D^{−γ} + D^{q−κ}))". -/
    92def 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
    101entries at any set of at most `N²/D^κ` positions can be computed in `O(N²/D^γ)` time. The paper has
    102this sentence with `ε₀ = 0.1204` (Theorem 1).
    103
    104NOTE. The paper states no lower bound on `D` and `N` here; `D ≥ 1` and `N ≥ 1` are assumed. On the
    105case `D = 1`, which Theorem 25 and Corollary 32 exclude, see the NOTE at `DataStructureBelow`. -/
    106def 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
    114value N^{O(1)}, and let W be any set of |W| ≤ N²/√D positions. The entries (XY)[I,J], (I,J) ∈ W,
    115can be computed deterministically in O(N²/D^{0.063}) operations on O(log N)-bit integers. More
    116generally, for every ε < 0.1204 and every κ > 0 there is a γ > 0 such that, whenever D ≤ N^ε
    117and |W| ≤ N²/D^κ, the task takes O(N²/D^γ) operations."
    118
    119NOTE. The paper states no lower bound on `D`; `D ≥ 1` is assumed, and in the last sentence also
    120`N ≥ 1` (see `WantedBelow`). -/
    121def 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. -/
    130axiom theorem5 : Theorem_5
    131
    132
    133/-- Faster computation of selected matrix-product entries: Theorem 25. -/
    134axiom theorem25 : Theorem_25
    135
    136
    137/-- Faster computation of selected matrix-product entries: Corollary 26 wanted. -/
    138axiom corollary26_wanted : Corollary_26_wanted
    139
    140
    141/-- Faster computation of selected matrix-product entries: Theorem 30 wanted. -/
    142axiom theorem30_wanted : Theorem_30_wanted
    143
    144
    145/-- Faster computation of selected matrix-product entries: Corollary 32. -/
    146axiom corollary32 : Corollary_32
    147
    148
    149/-- Faster computation of selected matrix-product entries: Theorem 1. -/
    150axiom theorem1 : Theorem_1
    151
    152
    153/-- Callable contract proved by upstream `Light.Sec2.claim_theorem_5`. -/
    154axiom callableTheorem5 : Lax350013.CallableAlgorithms.Claim.Theorem_5 Lax350013.CallableAlgorithms.lightModel
    155
    156end Lax350013.SparseMatrixProduct
    157
    Show ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…