Family 109Theoretical computer scienceSep 23, 2026

Integer multiplication below n log n

What this paper proves

A single deterministic Turing machine with a fixed finite alphabet and a fixed number of one-dimensional tapes multiplies any two

n

-bit integers exactly, for every

n\ge1

, in worst-case time

O(n(\lg n)^{1-\kappa})

with

\kappa=2^{-182}

. The key ingredient is a faster interchange of address chunks on tape, which lets a whole layer of Hadamard butterflies in the transform be applied at once in near-linear time with a single final truncation, keeping the error below 1/2 so rounding and carries are exact. This disproves the Schönhage–Strassen conjecture that

n\log n

is optimal for integer multiplication in the multitape bit model.

Main theorem

theoremnovelInteger multiplication in O(n (lg n)^{1-κ}) timethm:main

A single deterministic multitape Turing machine with a fixed alphabet and a fixed number of tapes multiplies any two

n

-bit integers exactly, for every

n\ge1

, in worst-case time

O(n(\lg n)^{1-\kappa})

\kappa=2^{-182}

Theorem 1 · as stated in the paper

There is one deterministic Turing machine

A

, with a fixed finite alphabet and a fixed finite number of one-dimensional tapes, that computes this exact product for every

n\ge1

and every pair of

n

-bit inputs. Its worst-case running time satisfies

T_A(n)=O\!\left(n(\lg n)^{1-\kappa}\right), \qquad \kappa=2^{-182}.

Where the new idea lives · 3 novel steps (one is the main theorem)

Proposition 11Power-width chunk interchange in O(Ve^τ)

Swaps two

m^k

-digit chunks in

O(Ve^\tau)

time,

e=m^k

Proposition 14Simultaneous Hadamard layer in near-linear time

Applies a Hadamard layer in

O(Vd^{\lambda'})

time with one final truncation

Shape of the proof

novel otherOpen the graph →

95

statements mapped

55

sections

3

novel steps

115

friction flags

Map

The proof as a tree and a dependency graph. Start at the top and click down.

Ask

Questions answered with citations to the map you can click.