theoremnovelstructure_uncertainunresolved_ref

Integer multiplication in O(n (lg n)^{1-κ}) time

Multiplies nn-bit integers in O(n(lg⁡n)1−κ)O(n(\lg n)^{1-\kappa}) time, κ=2−182\kappa=2^{-182}
the headline result
Theorem·thm:main·§1 Introduction

Statement (paper)

There is one deterministic Turing machine AA, with a fixed finite alphabet and a fixed finite number of one-dimensional tapes, that computes this exact product for every n≥1n\ge1 and every pair of nn-bit inputs. Its worst-case running time satisfies TA(n)=O ⁣(n(lg⁡n)1−κ),κ=2−182. T_A(n)=O\!\left(n(\lg n)^{1-\kappa}\right), \qquad \kappa=2^{-182}.

In plain English

A single deterministic multitape Turing machine with a fixed alphabet and a fixed number of tapes multiplies any two nn-bit integers exactly, for every n≥1n\ge1, in worst-case time O(n(lg⁡n)1−κ)O(n(\lg n)^{1-\kappa}) with κ=2−182\kappa=2^{-182}.

Why it's here

This is the paper's main result: it gives a power-of-log saving below the nlg⁡nn\lg n barrier for integer multiplication. Its proof fixes explicit parameters, builds the transform and CRT address-map machinery, bounds the numerical error by less than 1/2 so rounding and carries are exact, and uses the cost table to obtain the p1−κp^{1-\kappa} factor; the corollaries on exact division and square root then reuse the theorem as their multiplication cost.
Classified novel:
This is the paper's headline result. It improves the previous best multitape Turing machine bound of O(n log n) (Harvey–van der Hoeven 2019/2021) by a power-of-log factor (lg n)^{-κ}, and no prior result achieves time below n lg n.

Uses

Nothing else in the paper

Used by

corExact division and square root in multiplication timeclaimNewton routines cost O(B(p)) on fixed tapesclaimExact quotient and root by correction tests

Inside the proof

claimFixed exponents satisfy all parameter conditionsclaimTransform sizes and precision satisfy band boundsclaimDistinct primes meet resampling hypothesesclaimCRT address map via controlled shiftsclaimComplex convolution via coefficient twistclaimChirp transform and source transform proceduresclaimTwo scalings by S undo normalizationsclaimDisk margins and error propagation through transformsclaimFinal error below 1/2; rounding and carries exactclaimCost table yields the final time bound

Sources

PaperOpen
Section
§1 Introduction
Page
—
Label
thm:main
Line
sections/00-introduction.tex:21
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    structure_uncertain
    No proof environment; the proof is the whole of Section 9 (sections/08-assembly.tex), outlined here.
  • warn
    unresolved_ref
    Prime existence uses the external prime-interval lemma [HarveyHoeven2021, Lemma 5.1]; ring products use the established O(n log n) multiplier as a subroutine.