Faster lopsided triangle algorithms
Lax350013.LopsidedTriangleAlgorithms · concepts/Lax350013/LopsidedTriangleAlgorithms.lean · lax-350013
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Corollary 16 solves counting and detection in time for and . Corollary 15 records the earlier logarithmic bound for powers of four. 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.LopsidedTriangles |
| 26 | import Lax350013.CallableAlgorithms |
| 27 | |
| 28 | /-! |
| 29 | --- |
| 30 | title: Faster lopsided triangle algorithms |
| 31 | type: theorem |
| 32 | --- |
| 33 | Corollary 16 solves counting and detection in time for and . Corollary 15 records the earlier logarithmic bound for powers of four. The callable versions also preserve memory and resource guarantees needed when these algorithms are used as subroutines. |
| 34 | -/ |
| 35 | |
| 36 | namespace Lax350013.LopsidedTriangleAlgorithms |
| 37 | |
| 38 | open Finset |
| 39 | open Lax350013.WordRAM |
| 40 | open Lax350013.RAMResources |
| 41 | open Lax350013.ThinMatrices |
| 42 | open Lax350013.LopsidedTriangles |
| 43 | |
| 44 | /-- **Corollary 15**: "Let D ≥ 4 be a power of four with n ≥ D^18, and consider an instance |
| 45 | of #Lop-AE-SparseTri(n,D) or of Lop-AE-SparseTri(n,D) with |W| query pairs. If |W| ≤ n²/√D, then |
| 46 | the instance can be solved deterministically in O(n² log² D/D^{1/18}) time. In general, [...] in |
| 47 | time O((n² + |W|√D) log² D/D^{1/18})." The general bound contains the first one, since |
| 48 | `|W|√D ≤ n²` there. (As a statement about the existence of programs, this follows from |
| 49 | `Corollary_16`, whose bound is smaller; see the remark at `Theorem_5`.) -/ |
| 50 | def Corollary_15 : Prop := |
| 51 | ∃ (Pc Pd : List Instr) (b : ℕ) (C : ℝ), |
| 52 | Solves lopCount Pc b |
| 53 | (fun x => x.ZeroOne ∧ x.U = 1 ∧ (∃ k : ℕ, x.D = 4 ^ k) ∧ 4 ≤ x.D ∧ x.D ^ 18 ≤ x.N) |
| 54 | (fun x => C * (((x.N : ℝ) ^ 2 + (x.W.length : ℝ) * Real.sqrt x.D) * Real.log x.D ^ 2 / |
| 55 | (x.D : ℝ) ^ (1 / 18 : ℝ))) ∧ |
| 56 | Solves lopDetect Pd b |
| 57 | (fun x => x.ZeroOne ∧ x.U = 1 ∧ (∃ k : ℕ, x.D = 4 ^ k) ∧ 4 ≤ x.D ∧ x.D ^ 18 ≤ x.N) |
| 58 | (fun x => C * (((x.N : ℝ) ^ 2 + (x.W.length : ℝ) * Real.sqrt x.D) * Real.log x.D ^ 2 / |
| 59 | (x.D : ℝ) ^ (1 / 18 : ℝ))) |
| 60 | |
| 61 | /-- **Corollary 16**: "Let n ≥ D^18, and consider an instance of #Lop-AE-SparseTri(n,D) or |
| 62 | of Lop-AE-SparseTri(n,D) with |W| query pairs. It can be solved deterministically in O(|W| |
| 63 | D^{0.437} + n²/D^{0.063}) time." |
| 64 | |
| 65 | NOTE. The paper states no lower bound on `D`; `D ≥ 1` is assumed, as in `Corollary_26` below. -/ |
| 66 | def Corollary_16 : Prop := |
| 67 | ∃ (Pc Pd : List Instr) (b : ℕ) (C : ℝ), |
| 68 | Solves lopCount Pc b (fun x => x.ZeroOne ∧ x.U = 1 ∧ 1 ≤ x.D ∧ x.D ^ 18 ≤ x.N) |
| 69 | (fun x => C * ((x.W.length : ℝ) * (x.D : ℝ) ^ (0.437 : ℝ) + |
| 70 | (x.N : ℝ) ^ 2 / (x.D : ℝ) ^ (0.063 : ℝ))) ∧ |
| 71 | Solves lopDetect Pd b (fun x => x.ZeroOne ∧ x.U = 1 ∧ 1 ≤ x.D ∧ x.D ^ 18 ≤ x.N) |
| 72 | (fun x => C * ((x.W.length : ℝ) * (x.D : ℝ) ^ (0.437 : ℝ) + |
| 73 | (x.N : ℝ) ^ 2 / (x.D : ℝ) ^ (0.063 : ℝ))) |
| 74 | |
| 75 | /-- Faster lopsided triangle algorithms: Corollary 15. -/ |
| 76 | axiom corollary15 : Corollary_15 |
| 77 | |
| 78 | |
| 79 | /-- Faster lopsided triangle algorithms: Corollary 16. -/ |
| 80 | axiom corollary16 : Corollary_16 |
| 81 | |
| 82 | |
| 83 | /-- Callable contract proved by upstream `Light.Sec3.claim_corollary_15_first`. -/ |
| 84 | axiom callableCorollary15First : Lax350013.CallableAlgorithms.Claim.Corollary_15_first Lax350013.CallableAlgorithms.lightModel |
| 85 | |
| 86 | |
| 87 | /-- Callable contract proved by upstream `Light.Sec3.claim_corollary_15`. -/ |
| 88 | axiom callableCorollary15General : Lax350013.CallableAlgorithms.Claim.Corollary_15_general Lax350013.CallableAlgorithms.lightModel |
| 89 | |
| 90 | |
| 91 | /-- Callable contract proved by upstream `Light.Sec3.claim_corollary_16`. -/ |
| 92 | axiom callableCorollary16 : Lax350013.CallableAlgorithms.Claim.Corollary_16 Lax350013.CallableAlgorithms.lightModel |
| 93 | |
| 94 | end Lax350013.LopsidedTriangleAlgorithms |
| 95 |
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