Integer multiplication below n\log n

Multiplies two n-bit integers exactly at every input length in deterministic worst-case time O(n(\log n)^{1-\kappa}), with \kappa=2^{-182}, on one fixed finite-alphabet Turing machine with finitely many one-dimensional tapes. This disproves the Schönhage–Strassen n\log n optimality conjecture in the ordinary multitape bit model.

Manuscript

Integer multiplication below n log n

September 23, 2026 · source · cite as \cite{OAI:Integer-multiplication-below-n-log-n-September-23-2026}

We give a deterministic algorithm that multiplies two n-bit integers in O(n(\lg n)^{1-\kappa}) worst-case time, with \kappa=2^{-182}, on one fixed finite-alphabet Turing machine with a fixed finite number of one-dimensional tapes. The algorithm is exact for every input length and disproves the n\log n optimality conjecture of Schönhage and Strassen in this model.

Result 109 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Agora members.