# Integer multiplication below $n\log n$

> A tape-based computer can multiply huge whole numbers slightly faster than the long-conjectured n log n limit. Plain-English explainer with sources.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-109/
Last updated: 2026-10-11

**A tape-based computer can multiply huge whole numbers slightly faster than the long-conjectured n log n limit.**

**Trust:** Claimed, not checked · **Papers:** 1 · **First paper:** September 23, 2026 · **Field:** Theoretical computer science · **Entry:** 109

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

Multiplying two n-bit numbers on a simple tape-based model computer was known to take about n log n steps. In 1971, Schönhage and Strassen proposed that this was the best possible growth rate. This paper claims to prove a slower-growing method, saving a factor of (log n) to the power 2^−182. If the proof holds, that conjecture fails in this model. The gain is far too small to matter in practice.

## At a glance

- **First step:** 1962 (Karatsuba and Ofman, first method faster than school multiplication (earliest result the paper cites))
- **Significance:** Major. It claims to break a growth rate conjectured optimal since 1971, though the gain is purely theoretical.
- **Trust:** Claimed, not checked
- **Field:** Theoretical computer science (1 paper)

## The explanation

Multiply 1234 by 5678 the way you learned at school. Each of the 4 top digits meets each of the 4 bottom digits. That makes 16 small products, which add up to 7,006,652. Double the length of both numbers, and the work roughly quadruples. Computers multiply in bits (binary digits, 0 or 1). Take two numbers that are each 2^20 bits long, about a million bits. The school method then needs about 1.1 trillion small products.

Faster methods have a long history. In 1962, Karatsuba and Ofman found a trick that beats the school method. It splits each number in half and applies the same trick again to the smaller pieces. In 1971, Schönhage and Strassen proved a much faster bound. Their time grows like n log n log log n, where n is the number of bits. Here log n is the number of times you can halve n before reaching 1. For a million bits, log n is about 20. So n log n is about 21 million, against 1.1 trillion for the school method.

Schönhage and Strassen also proposed n log n as the best possible growth rate. Fürer narrowed the gap in 2007. Harvey and van der Hoeven then proved a bound of order n log n, in a paper published in 2021. That met the conjectured limit. The open question was whether anyone could go below it.

The answer depends on the machine you count steps on. All of these bounds use a multitape Turing machine. That is a simple model computer. It reads and writes symbols on a fixed number of long tapes, moving one cell at a time. In other models, faster methods already existed. Schönhage obtained linear-time multiplication on a different machine model. Groff beat log n on a machine that can jump anywhere in memory instantly, after setup work not counted. Neither result settles the tape model.

This paper claims to prove that one fixed tape machine beats n log n. It multiplies exactly, for every input length[1]. Its time grows like n times (log n) to the power 1 − κ, where κ = 2^−182. That is n log n divided by (log n)^κ. As n grows, this divisor grows without limit. So the ratio to n log n shrinks toward zero. If the proof holds, the n log n conjecture fails in this model[2].

The saving is real but extremely slow. κ is about 1.6 × 10^−55. Take n = 2^64 bits, so log n is 64. Then the cost falls short of n log n by a fraction of about 7 × 10^−55. Halving the cost would need log n near 2 to the power 2^182. The paper says its constants are extremely large. It calls the algorithm a way to establish a bound, not a practical method[3].

Why was n log n such a firm wall? Fast methods turn multiplication into Fourier transforms (a standard way to mix data in about log n stages). A tape machine must scan its data in order, like a cassette. Scanning n bits at each of log n stages already costs n log n[4]. So any saving must cut both data movement and arithmetic at once[5].

The paper builds two new tape procedures for this. One swaps blocks of the data's address labels. Midway it stores mixed combinations of the data, not plain copies, yet the end result is an exact rearrangement[6]. The other performs many arithmetic stages together. Both rest on a small fixed network that needs fewer smaller calls than a direct approach[7]. Used again and again inside itself, that small surplus becomes the saving κ.

The same speed carries over to related tasks. The paper also claims division with remainder and integer square roots in the same time[8]. It also claims faster transposing of a square grid of bits[9]. That transposition result does not apply to models that may only move data around[10].

How sure is this? No Lean formalization is listed for this paper, so no computer proof checker has checked it. No specialist review has been published yet.

**What it doesn't show.** This does not give a faster multiplication method for real computers.

## Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

## Hype check

Major in theory if the proof holds, and of no practical use. The speed-up is a factor of (log n) to the power 2^−182, with extremely large constants. No Lean formalization is listed, and specialists have not yet published a review.

## Words used

- **Bit:** A binary digit, either 0 or 1.
- **log n:** Roughly how many times you can halve n before reaching 1; for a million it is about 20.
- **Turing machine:** A simple model computer that reads and writes symbols on long tapes, one cell at a time.
- **n log n conjecture:** Schönhage and Strassen's 1971 proposal that multiplying n-bit numbers cannot grow slower than n log n.
- **Fourier transform:** A standard way to mix and unmix data in stages, used by all fast multiplication methods here.
- **Matrix transposition:** Turning the rows of a grid into its columns.
- **Lean:** A computer program that checks mathematical proofs step by step.

## The original paper

- [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf) - September 23, 2026

## Quoted lines from the paper (10)

[1] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

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

[2] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

> The algorithm is exact for every input length and disproves the $n\log n$ optimality conjecture of Sch\"onhage and Strassen in this model.

[3] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

> The constants and thresholds in the construction are extremely large; the algorithm is intended to establish a bit-complexity bound.

[4] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

> Scanning an array of $\Theta(n)$ stored bits at each of $\Theta(\log n)$ transform levels already costs $\Theta(n\log n)$.

[5] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

> We therefore need savings in both movement and arithmetic.

[6] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

> Although its final effect is an exact permutation, its intermediate steps form pointwise XOR combinations of data.

[7] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

> This strict inequality is the source of the power saving.

[8] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

> Exact division and integer square root

[9] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

> Combining their quantitative reduction with Theorem … gives a deterministic fixed-tape algorithm that transposes a row-major $k\times k$ binary matrix in $O(k^2(\lg k)^{1-\kappa})$ time, with $\kappa$ as in Theorem ….

[10] From [Integer multiplication below n log n](https://github.com/openai/math/blob/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf):

> It therefore lies outside models restricted to moving data without such computations; see for the distinction.

## Other sources

- [A. Karatsuba and Yu. Ofman, “Multiplication of Many-Digital Numbers by Automatic Computers”, Doklady Akademii Nauk SSSR 145 (1962), 293–294](https://www.mathnet.ru/eng/dan26729)
- [A. Schönhage and V. Strassen, “Schnelle Multiplikation großer Zahlen”, Computing 7 (1971), 281–292](https://doi.org/10.1007/BF02242355)
- [M. Fürer, “Faster Integer Multiplication”, STOC 2007, 57–66](https://doi.org/10.1145/1250790.1250800)
- [D. Harvey and J. van der Hoeven, “Integer Multiplication in Time O(n log n)”, Annals of Mathematics 193 (2021), 563–617](https://doi.org/10.4007/annals.2021.193.2.4)
- [A. Schönhage, “Storage Modification Machines”, SIAM Journal on Computing 9 (1980), 490–508](https://doi.org/10.1137/0209036)
- [M. Groff, “Faster Integer Multiplication Using Preprocessing”, arXiv:1911.07124v2 (2019)](https://arxiv.org/abs/1911.07124v2)
- [D. Harvey and J. van der Hoeven, “Integer Multiplication Is at Least as Hard as Matrix Transposition”, FOCS 2025, 1366–1381](https://arxiv.org/abs/2503.22848v1)

## Related

- [Matrix multiplication with exponent at most 9/4](https://closedform.nishachay.tech/e/openai-math-2026-107/) - Theoretical computer science
- [Almost-linear-time exact matching and prescribed-degree factors in general graphs](https://closedform.nishachay.tech/e/openai-math-2026-120/) - Theoretical computer science
- [Exact Fourier transforms below n log n](https://closedform.nishachay.tech/e/openai-math-2026-130/) - Theoretical computer science
- [The computational complexity of Weisfeiler–Leman refinement](https://closedform.nishachay.tech/e/openai-math-2026-133/) - Theoretical computer science
- [Generalized star height at most three](https://closedform.nishachay.tech/e/openai-math-2026-134/) - Theoretical computer science
- [Theoretical computer science](https://closedform.nishachay.tech/science/mathematics/theoretical-computer-science/) - Field · 40 results
- [Open since the 1960s](https://closedform.nishachay.tech/open-since/1960s/) - Era · 33 results
- [Claimed, not yet checked](https://closedform.nishachay.tech/trust/claimed/) - Trust · 130 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20109%5D%20)