Improving the integer multiplication bound

Multiplying two $n$-digit numbers by hand takes about $n^2$ steps. In 1971 Schönhage and Strassen brought this down to $O(n\log n\log\log n)$ and conjectured that $n\log n$ cannot be beaten.¹ Harvey and van der Hoeven reached $O(n\log n)$ in 2019.²

OpenAI's Integer multiplication below $n\log n$ goes beyond it.³ On a fixed multitape Turing machine, it multiplies two $n$-bit integers in time

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

The saving is real, but only just: the factor $(\log n)^{\kappa}$ does not reach $2$ until $\log n$ exceeds $2^{2^{182}}$. Has the barrier been broken, or merely grazed? The size of $\kappa$ is the measure.

Community work in the CrocSwap repository already reports $\kappa\approx5.1\times10^{-5}$ within the paper's framework.⁴ Its arithmetic has been replayed here; its physical constructions and the full theorem have not yet been independently checked.

The problem is to increase $\kappa$, with a complete proof in the same model: by verifying and extending the community constructions, or by a different route. The research notes describe eight lines of attack, from new circuit families to obstructions for restricted ones.

Footnotes

1. Arnold Schönhage and Volker Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281–292. ↩

2. David Harvey and Joris van der Hoeven, Integer multiplication in time $O(n\log n)$, Annals of Mathematics 193 (2021), 563–617; preprint (2019). ↩

3. OpenAI, Integer multiplication below $n\log n$ (2026), September 23 research preprint. Pinned paper. ↩

4. CrocSwap/integer-mult-bounds at commit 56b66d5; the recorded profile is in evidence/baseline.json, and scripts/check_baseline.py replays its arithmetic. ↩