Integer algorithms before rounding the exponents

Lax350013.IntegerAlgorithmBounds · concepts/Lax350013/IntegerAlgorithmBounds.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 19 gives Exact Triangle bounds from both constructions. Theorem 22 carries these improvements to 3SUM, min-plus product and APSP, retaining the logarithmic and o(1)o(1) factors before rounding. These statements are deterministic integer word-RAM bounds; they do not assert the paper’s real-RAM or randomized bounds. The callable versions also preserve memory and resource guarantees needed when these algorithms are used as subroutines.

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

    This concept declares 9 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.ExactTriangle
    26import Lax350013.ThreeSUM
    27import Lax350013.MinPlusProduct
    28import Lax350013.APSP
    29import Lax350013.RAMResources
    30import Lax350013.CallableAlgorithms
    31
    32/-!
    33---
    34title: Integer algorithms before rounding the exponents
    35type: theorem
    36---
    37Theorem 19 gives Exact Triangle bounds from both constructions. Theorem 22 carries these improvements to 3SUM, min-plus product and APSP, retaining the logarithmic and o(1)o(1) factors before rounding. These statements are deterministic integer word-RAM bounds; they do not assert the paper’s real-RAM or randomized bounds. The callable versions also preserve memory and resource guarantees needed when these algorithms are used as subroutines.
    38-/
    39
    40namespace Lax350013.IntegerAlgorithmBounds
    41
    42open Finset
    43open Lax350013.WordRAM
    44open Lax350013.RAMResources
    45
    46/-- **Theorem 19**: "For every constant ν ≥ 1, Exact Triangle on n vertices per part with
    47integer weights of absolute value at most n^ν can be solved by a deterministic algorithm in
    48O(n^{3−1/648} log² n) time [...], and in O(n^{3−ε'} log n) ≤ O(n^{3−ε_T}) time", with `ε' = 0.00175`
    49and `ε_T = 0.0017`. (The paper reaches the first bound using Theorem 5 and the second using
    50Corollary 26. This cannot be said by "there is a program": as statements about the existence of
    51programs, the first and the third bound follow from the second, which is smaller.) -/
    52def Theorem_19 : Prop :=
    53 SolvedInTime Lax350013.ExactTriangle.ExactTriangle (3 - 1 / 648) 2 ∧
    54 SolvedInTime Lax350013.ExactTriangle.ExactTriangle (3 - 0.00175) 1 ∧
    55 SolvedInTime Lax350013.ExactTriangle.ExactTriangle (3 - 0.0017) 0
    56
    57/-- **Theorem 22**, the bounds "Using Theorem 5": 3SUM in `O(n^{1.99923})` time, "and the
    58(min,+)-product [...] as well as APSP [...] in Õ(n^{3−1/1944}) ≤ O(n^{2.99949}) time". (The
    59intermediate form `n^{2−1/1296+o(1)}` for 3SUM is `Theorem_22_threeSum` below. "Using Theorem 5"
    60cannot be said by "there is a program": as statements about the existence of programs, all five
    61bounds follow from those of `Theorem_22_second`, which are smaller.) -/
    62def Theorem_22_first : Prop :=
    63 SolvedInTime Lax350013.ThreeSUM.ThreeSum 1.99923 0 ∧
    64 SolvedInPolylogTime Lax350013.MinPlusProduct.MinPlusProduct (3 - 1 / 1944) ∧
    65 SolvedInPolylogTime Lax350013.APSP.APSP (3 - 1 / 1944) ∧
    66 SolvedInTime Lax350013.MinPlusProduct.MinPlusProduct 2.99949 0 ∧
    67 SolvedInTime Lax350013.APSP.APSP 2.99949 0
    68
    69/-- **Theorem 22**, the bounds "Using Corollary 26 instead": 3SUM in `O(n^{1.9992})` time,
    70the (min,+)-product and APSP in "Õ(n^{3−ε'/3}) ≤ O(n^{2.99942})" time, with
    71`ε' = 0.00175`. (The intermediate form `n^{2−ε'/2+o(1)}` for 3SUM is `Theorem_22_threeSum`
    72below.) -/
    73def Theorem_22_second : Prop :=
    74 SolvedInTime Lax350013.ThreeSUM.ThreeSum 1.9992 0 ∧
    75 SolvedInPolylogTime Lax350013.MinPlusProduct.MinPlusProduct (3 - 0.00175 / 3) ∧
    76 SolvedInPolylogTime Lax350013.APSP.APSP (3 - 0.00175 / 3) ∧
    77 SolvedInTime Lax350013.MinPlusProduct.MinPlusProduct 2.99942 0 ∧
    78 SolvedInTime Lax350013.APSP.APSP 2.99942 0
    79
    80/-- **Theorem 22**, the two bounds for 3SUM before rounding: "Using Theorem 5 (through
    81Theorem 19), deterministic algorithms solve 3SUM on n integers of absolute value at most n^ν in
    82n^{2−1/1296+o(1)} ≤ O(n^{1.99923}) time [...]. Using Corollary 26 instead, the times are
    83n^{2−ε'/2+o(1)} ≤ O(n^{1.9992}) [...]", with `ε' = 0.00175`. The rounded bounds are in
    84`Theorem_22_first` and `Theorem_22_second`. (As a statement about the existence of programs, the
    85first bound follows from the second, which is smaller.) -/
    86def Theorem_22_threeSum : Prop :=
    87 SolvedInLittleOTime Lax350013.ThreeSUM.ThreeSum (2 - 1 / 1296) ∧
    88 SolvedInLittleOTime Lax350013.ThreeSUM.ThreeSum (2 - 0.00175 / 2)
    89
    90/-- **Theorem 2**, the deterministic half: "On a word RAM with O(log n)-bit words,
    91deterministic algorithms solve the following problems, where all numbers in the input are integers
    92of absolute value n^{O(1)}: Exact Triangle on n-vertex graphs in O(n^{2.9983}) time, APSP on
    93directed n-vertex graphs with no negative cycles in O(n^{2.9995}) time, the (min,+)-product of two
    94n × n matrices in O(n^{2.9995}) time, and 3SUM on n numbers in O(n^{1.9992}) time." (For APSP and
    95the (min,+)-product, Theorem 22 prints the smaller exponent 2.99942: `Theorem_22_second`.)
    96
    97NOTE. Here Exact Triangle has the tripartite form of Section 3.2, with `n` vertices per part; for
    98`n`-vertex graphs see `Theorem_2_graphs`. -/
    99def Theorem_2 : Prop :=
    100 SolvedInTime Lax350013.ExactTriangle.ExactTriangle 2.9983 0 ∧
    101 SolvedInTime Lax350013.APSP.APSP 2.9995 0 ∧
    102 SolvedInTime Lax350013.MinPlusProduct.MinPlusProduct 2.9995 0 ∧
    103 SolvedInTime Lax350013.ThreeSUM.ThreeSum 1.9992 0
    104
    105/-- Integer algorithms before rounding the exponents: Theorem 19. -/
    106axiom theorem19 : Theorem_19
    107
    108
    109/-- Integer algorithms before rounding the exponents: Theorem 22 first. -/
    110axiom theorem22_first : Theorem_22_first
    111
    112
    113/-- Integer algorithms before rounding the exponents: Theorem 22 second. -/
    114axiom theorem22_second : Theorem_22_second
    115
    116
    117/-- Integer algorithms before rounding the exponents: Theorem 22 threeSum. -/
    118axiom theorem22_threeSum : Theorem_22_threeSum
    119
    120
    121/-- Integer algorithms before rounding the exponents: Theorem 2. -/
    122axiom theorem2 : Theorem_2
    123
    124
    125/-- Callable contract proved by upstream `Light.Sec3.claim_theorem_19_usingTheorem5`. -/
    126axiom callableExactTriangleFirst : Lax350013.CallableAlgorithms.Claim.Theorem_19_explicit Lax350013.CallableAlgorithms.lightModel (1 / 648) 2
    127
    128
    129/-- Callable contract proved by upstream `Light.Sec3.claim_theorem_19_usingCorollary26`. -/
    130axiom callableExactTriangleSecond : Lax350013.CallableAlgorithms.Claim.Theorem_19_explicit Lax350013.CallableAlgorithms.lightModel 0.00175 1
    131
    132
    133/-- Callable contract proved by upstream `Light.Sec3.claim_exactTriangleUniform_usingTheorem5`. -/
    134axiom uniformExactTriangleFirst : Lax350013.CallableAlgorithms.Claim.ExactTriangleUniform Lax350013.CallableAlgorithms.lightModel (1 / 648) 2
    135
    136
    137/-- Callable contract proved by upstream `Light.Sec3.claim_exactTriangleUniform_usingCorollary26`. -/
    138axiom uniformExactTriangleSecond : Lax350013.CallableAlgorithms.Claim.ExactTriangleUniform Lax350013.CallableAlgorithms.lightModel 0.00175 1
    139
    140end Lax350013.IntegerAlgorithmBounds
    141
    Show ProofShow ProofShow 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…