Integer multiplication in Lean

Integer multiplication below n log n is proved in Lean on Mathlib's finite Turing machines.

IntegerMultBounds.MathlibTM2.statement is unconditional: one fixed Turing.FinTM2 machine multiplies every pair of natural numbers, with standard binary input/output encodings, in worst-case time O(n (log n)^(1-kappa)). The construction proves the positive saving kappa = 4222422970/2^46 (about 2^-14.02), exposed by MathlibTM2.mulInTime, where n is the total encoded input length. See the completed plan.

The running multiplier combines linear direct CRT routing with compact controls and full-width chunks above the root ⌈d/2⌉. It uses rounded synthetic layers on the T16 node (73 slots, 14336 data roles, 1,041,408 children, so log_73 (F/NW) < 999/1000). Its bit interchange uses PR97 stage 2: the opposite-bank compiler on design-B frames, variable-rank children, stopped recursion over atoms, and the F L F wrapper on the generic machine in MathlibTM2/M8. The atom exponent is 1/1000; the resulting ordinary bit exponent is tau = 1-123879734039/10^15 (Stage2Machine.Bound.uniform_bound). PR97's rank-one construction remains the leaf supplier (stage-one note). The parameters are epsilon = 31/64, lambda = 1-12387973/10^11 and lambda' = 1-12387972/10^11. The public saving is the binding layer margin epsilon (1-lambda'), just below the layout margin epsilon (1-tau), rounded down to 2^-46. Complete input preparation, distribution, transforms, output and cleanup are included in the fixed-machine proof. The public saving is more than 2^46 times the historical M2 saving 2^-66, as an exponent improvement.

This completed proof is the primary route. The retention audit lists its dependencies and legacy removal candidates; the retired native controller is preserved in Git history.

The next routing construction has completed R1 and R2: a concrete selective-update program with exact repair on every address, fully priced metadata setup, keying, routing, classification, sorting and cleanup, and restored borrowed registers. R3 now compiles framed physical source coordinates and activity into all eleven repair source profiles, composing classifiers, widths, headers, exact repair, placement and cleanup with restored borrowed tapes. This composition now accepts any geometry satisfying explicit guards and density bounds, allowing reservoir spacing. Complete directional destination maps now compose bulk and terminal rank permutations, with exact shear semantics and restored surrounding bits. A fixed-register schedule now executes repeated exact-repair calls from supplied raw configuration, including loading, cleanup and full input rewind. The full generated/placed price is proved independent of record order, and one complete generated/placed call now executes from a framed input bank with loading and erasure charged, using one fixed program across geometries. Repeated generated/placed calls now share one fixed bank and program, with composed rank semantics, summed prices and full input rewind. Matching-entry scanning now derives physical sources and activity with complete input restoration; a live residue filter gathers entries from a common table. Exact profile ordering and gathered-table cleanup now compose with full-table prefix extraction into one restoring input producer, with a uniform polynomial setup bound shared by every residue. These matching-produced calls now execute repeatedly on one fixed bank, with composed rank semantics, summed setup/repair/framing costs and full metadata rewind. A physical matching that fixes the chosen reservoir now yields its complete local middle-field table by executed placement, lookup, offset arithmetic and live counter enumeration; all temporary inputs are erased and every other tape is restored. Reservoir-class tables now also come from executed interval comparisons and a restoring scan of the original matching table. Both producers compose into one program that erases the intermediate class table. One complete generated/placed repair now executes from the original matching on a concrete shared-table bank, erasing the generated local table afterward. Such calls now repeat on one framed bank for a fixed matching, reservoir class and direction, with all setup, cleanup and final input rewind charged. Canonical raw and live input banks are constructed from dimensions and records. Complete generated/placed inputs now follow from arithmetic bounds and records, with one common generated program across configurations. Explicit logarithmic router parameters now discharge all stage arithmetic and metadata symbol bounds. A concrete bulk scheduler executes any residue list for a fixed matching class and direction, restores its surrounding bank, and charges framing, repair, cleanup and input rewind. Its output permutation now has the exact physical bulk-shear action, with source separation and all residue compositions proved in common coordinates. The physical terminal suffix now also executes on a fixed bank, including counter generation, compilation and cleanup, with exact shear semantics and a logarithmic instruction count; it currently requires records at least as wide as their addresses. Terminal and bulk execution now compose on one common framed bank, with a complete physical directional class shear and summed costs. Three directional rank permutations now implement each physical matching class; all three classes compose to the original coordinate involution and preserve outer record rows. This is rank semantics. A concrete directional call now installs terminal metadata and bulk input, executes both phases and erases its workspace with all costs charged. Three successive calls now execute a complete matching class with its exact class permutation and a reusable final bank. All three classes now execute as a nine-direction schedule with the original matching permutation, charged reloads and a reusable final bank. Intermediate records are now constructed automatically, and a charged final rewind restores every tape except the record stream. Two matching executions now implement an arbitrary coordinate permutation in eighteen directions, with all routing and final rewind charged and every other tape restored. The concrete outer input frame is still supplied; executed decomposition/table and frame generation, uniform pricing and amortization/fallback remain open. The complete router and multiplication integration remain in R3–R4; this work does not yet change the multiplication saving. See the active plan and the R2 audit.

The original, separate native-machine target is an actual deterministic machine with a fixed finite alphabet and a fixed number of one-dimensional tapes, correct on every positive input length, with worst-case runtime O(n (max(ceil(log₂ n), 1))^(1 - 83/10^12)).

IntegerMultBounds/Machine.lean defines the machine semantics and the target proposition IntegerMultBounds.Machine.EndToEnd. This is a proposition to be proved, not a theorem or an assumed interface. Its exponent saving is smaller than the current Mathlib result; this separate machine interface is not the active improvement route. Its transition function only sees the finite state and scanned symbols. Each step writes at most one cell per tape and moves each head at most one cell. Constants and the machine are chosen before quantifying over inputs.

IntegerMultBounds/MathlibTM2/Statement.lean states the target with Mathlib definitions only: Turing.TM2ComputableInTime with Mathlib's binary encodings encodingProd and encodingNatBool, so an auditor of the final result reads only that statement and its axioms. The note explains the statement.

IntegerMultBounds/MathlibTM2/Theorem.lean proves MathlibTM2.statement : MathlibTM2.Statement: a fixed Turing.FinTM2 machine multiplies in worst-case time O(n (log n)^(1-κ)) for an explicit κ > 0. Read Statement.lean (its imports are Mathlib only). With the required dependency artifacts available, run python3 scripts/check-lean-safe.py CompletedProofCheck.lean to check the public bound and audit its complete proof import closure. The audit permits only propext, Classical.choice and Quot.sound; an unapproved axiom fails the check. The note describes the machine and the proof.

The end-to-end Mathlib proof is complete, with no remaining algorithmic or runtime assumptions, at kappa = 4222422970/2^46 ≈ 0.00006000424. The running supplier uses the fully checked design-B compiler and frame geometry, including its actual cost histogram and reversed execution. This improves the saving by about 27.97%, or 0.35576 bits, over the previous plain-frame result.

The long-term direction is an unconditional kappa = 0.0023, following the productive helper jobs, finite mixed-to-uniform compiler, delayed BIT cover, and outer assembly of upstream PR 4359. That upstream construction is conditional, and the target is not proved here. PLAN.md keeps smaller checked improvements on the path, with design-B completed and explicit dependencies for the new construction.

The superseded native controller and its unused wrappers have been removed. The retirement record lists the deleted modules and how to recover them from Git history.

Install the version of Lean in lean-toolchain, then use the guarded local verification commands:

python3 scripts/build-lean-guarded.py IntegerMultBounds
python3 scripts/check-lean-safe.py AxiomAudit.lean
python3 scripts/check-lean-safe.py CompletedProofCheck.lean

For local component checks, use python3 scripts/check-lean-safe.py FILE. This runner permits one check per workspace, uses one Lean thread and a 24576 MiB Lean memory limit, and stops the process group if its observed RSS exceeds 28672 MiB or the check runs past twenty minutes. It also stops child processes if monitoring fails or the check is interrupted. Dependencies must already have compiled artifacts; it does not launch a broad build. The guarded build stops at 80 GiB combined RSS or three hours. Both runners share one workspace-wide lock.

To locate memory growth within a file, use python3 scripts/profile-lean-prefixes.py FILE --through LINE1 LINE2 ..., choosing increasing line numbers immediately after complete declarations or sections. Each check uses a fresh source copy ending in #exit and the same guard and cached imports; the original file and production build artifacts are untouched. Start with the imports, then section boundaries, then add boundaries around declarations in the interval where the peak rises. Results and logs go to a fresh directory under .lake/profiling. Use --serialize to measure partial-module serialization too. Failed checks stop the sweep and are not valid measurements. These are cumulative prefix peaks, not exclusive allocations: earlier peaks can hide later costs, and allocator retention makes subtracting peaks unsuitable for attributing exact memory to one theorem. For a machine-readable single-file measurement, the guard also accepts --report-json PATH before the file argument; elapsed time excludes lock waiting.

Lean and mathlib are pinned to v4.34.1; lake-manifest.json pins transitive dependencies. No theorem in this project uses a custom axiom or an admitted proof.

AxiomAudit.lean checks public and private project declarations, transitively, allowing only Lean's standard propext, Quot.sound, and Classical.choice. It rejects admitted proofs, custom axioms, and native-evaluation axioms. CI builds the project and runs this audit.

• Douglas Colkitt, A sharper exponent for integer multiplication, research draft, CrocSwap/integer-mult-bounds, commit 6e56487 (October 7, 2026).
• Its pinned OpenAI manuscript, Integer multiplication below n log n, in openai/math, commit adc7f12.
• David Harvey and Joris van der Hoeven, Integer multiplication in time O(n log n), Annals of Mathematics 193(2), 2021, 563–617. The upstream proof uses this multiplier as a subroutine. Lemma and section numbers in NLogN/ refer to the author-hosted manuscript.

• J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation 19(90), 1965, 297–301. (NLogN/FFT.lean)
• A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7, 1971, 281–292. (Schoenhage/)
• L. I. Bluestein, A linear filtering approach to the computation of discrete Fourier transform, IEEE Transactions on Audio and Electroacoustics 18(4), 1970, 451–455. (NLogN/Bluestein.lean)
• R. C. Agarwal and J. W. Cooley, New algorithms for digital convolution, IEEE Transactions on Acoustics, Speech, and Signal Processing 25(5), 1977, 392–410. (NLogN/Multidim.lean)

• complexitylib, commit 3f4b5fe, for the machine composition design (no code imported).
• mathlib4, v4.34.1.

The local integer-mult-bounds/ checkout is reference material and is ignored by this project's Git repository. The Lean project does not execute or trust the source repository's Python certificates.

MIT.