Explicit thin matrix preprocessing bounds

Lax350013.MatrixPreprocessing · concepts/Lax350013/MatrixPreprocessing.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

    Corollary 26 gives O(N2/D0.063)O(N^2/D^{0.063}) preprocessing time and space and O(D0.437)O(D^{0.437}) time per query for 1≤D1\leq D and D18≤ND^{18}\leq N. Theorem 30 gives the underlying bounds at integer recursion parameters. Theorem 3 extends the trade-off to every ε<0.1204\varepsilon<0.1204 and every positive query exponent. The callable versions also preserve memory and resource guarantees needed when these algorithms are used as subroutines.

    Concept map
    12 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.

    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.MatrixTradeoffs
    26import Lax350013.CallableAlgorithms
    27
    28/-!
    29---
    30title: Explicit thin matrix preprocessing bounds
    31type: theorem
    32---
    33Corollary 26 gives O(N2/D0.063)O(N^2/D^{0.063}) preprocessing time and space and O(D0.437)O(D^{0.437}) time per query for 1≤D1\leq D and D18≤ND^{18}\leq N. Theorem 30 gives the underlying bounds at integer recursion parameters. Theorem 3 extends the trade-off to every ε<0.1204\varepsilon<0.1204 and every positive query exponent. The callable versions also preserve memory and resource guarantees needed when these algorithms are used as subroutines.
    34-/
    35
    36namespace Lax350013.MatrixPreprocessing
    37
    38open Finset
    39open Lax350013.WordRAM
    40open Lax350013.RAMResources
    41open Lax350013.ThinMatrices
    42open Lax350013.MatrixParameters
    43open Lax350013.MatrixTradeoffs
    44
    45/-- **Corollary 26**, first two sentences: "Let N ≥ D^18, and let X ∈ ℤ^{N×D} and Y ∈ ℤ^{D×N}
    46have entries of absolute value at most N^{O(1)}. We can preprocess them deterministically in
    47O(N²/D^{0.063}) time and space, after which any single entry (XY)[I,J] can be computed
    48deterministically in O(D^{0.437}) time."
    49
    50NOTE. 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). -/
    52def 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
    60N₀", with entries "of absolute value at most N^{O(1)}". -/
    61def 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
    66this, 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
    68constant `C` is chosen after the exponent `c` and before `m`, `L`, `t`. These parameters are given
    69to the preprocessing after `N` and `D`; the two programs do not depend on them. -/
    70def 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
    76value N^{O(1)}. The pair (X,Y) can be preprocessed deterministically in O(N²/D^{0.063}) time [...].
    77After this, any single entry (XY)[I,J] can be computed deterministically in O(D^{0.437}) time [...].
    78More generally, for every ε < 0.1204 and every q > 0 there is a γ > 0 such that, whenever D ≤ N^ε,
    79the pair can be preprocessed in O(N²/D^γ) time, after which any single entry can be computed in
    80O(D^q) time." The first part is `Corollary_26`.
    81
    82NOTE. 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
    84time only. -/
    85def Theorem_3 : Prop :=
    86 Corollary_26 ∧ DataStructureBelow 0.1204
    87
    88/-- Explicit thin matrix preprocessing bounds: Corollary 26. -/
    89axiom corollary26 : Corollary_26
    90
    91
    92/-- Explicit thin matrix preprocessing bounds: Theorem 30. -/
    93axiom theorem30 : Theorem_30
    94
    95
    96/-- Explicit thin matrix preprocessing bounds: Theorem 3. -/
    97axiom theorem3 : Theorem_3
    98
    99
    100/-- Callable contract proved by upstream `Light.Sec4.claim_corollary_26_wanted`. -/
    101axiom callableCorollary26 : Lax350013.CallableAlgorithms.Claim.Corollary_26_wanted Lax350013.CallableAlgorithms.lightModel
    102
    103end Lax350013.MatrixPreprocessing
    104
    Show ProofShow ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…