theoremnovelstructure_uncertainunresolved_ref
Integer multiplication in O(n (lg n)^{1-κ}) time
Multiplies -bit integers in time,
the headline result
Theorem·
thm:main·§1 IntroductionStatement (paper)
There is one deterministic Turing machine , with a fixed finite
alphabet and a fixed finite number of one-dimensional tapes, that
computes this exact product for every and every pair of -bit
inputs. Its worst-case running time satisfies
In plain English
A single deterministic multitape Turing machine with a fixed alphabet and a fixed number of tapes multiplies any two -bit integers exactly, for every , in worst-case time with .
Why it's here
This is the paper's main result: it gives a power-of-log saving below the 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 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.
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