Integer multiplication below $n\log n$

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 lengthSource 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 modelSource 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 methodSource 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 nSource 4. So any saving must cut both data movement and arithmetic at onceSource 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 rearrangementSource 6. The other performs many arithmetic stages together. Both rest on a small fixed network that needs fewer smaller calls than a direct approachSource 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 timeSource 8. It also claims faster transposing of a square grid of bitsSource 9. That transposition result does not apply to models that may only move data aroundSource 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.