Theoretical computer science · Result 109

Integer multiplication below \(n\log n\)

1 paper

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.

Watch

The problem

What is being asked, where it comes from, and why it is hard. No proof needed.

▶Introduction to the problemin preparation

The solution proposed by OpenAI

How the paper solves it, step by step.

Full explanation

▶The proposed solutionin preparation

Papers 1

Integer multiplication below n log n

OpenAI · 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.

Read PDF Download Source

Cite

@misc{OAI:Integer-multiplication-below-n-log-n-September-23-2026,
  author = {{OpenAI}},
  title = {{Integer multiplication below $n\log n$}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf}{OAI:Integer-multiplication-below-n-log-n-September-23-2026}},
  year = {2026}
}

Formal verification

No Lean formalization is listed for this result yet. The repository notes that unformalized results could have issues.