Why Integer Multiplication May Beat n log n

A calculator can multiply two enormous integers before you finish blinking. The interesting question is not whether the answer arrives quickly on a laptop, but how the work grows when the inputs become impossibly large.

For two integers with n bits each, the long-standing target has been O(n log n) bit operations. Here, a bit operation is work on an individual zero or one, and n measures the length of the input rather than its numerical value. A September 23, 2026 preprint claims something more surprising: an exact, deterministic method running in O(n · (log n)^(1−κ)), with κ = 2^−182.

That exponent is so close to one that it looks almost insulting. Mathematically, it is enormous.

Why n log n became a barrier

Schoolbook multiplication treats every part of one number as interacting with every part of the other. That gives a quadratic cost, O(n²). Fast multiplication changes the problem into a form of polynomial convolution, then uses a fast Fourier transform, or FFT, to combine many pieces at once.

An FFT is a fast method for computing a discrete Fourier transform, a change of coordinates that turns convolution into pointwise multiplication. The details are intricate, but the broad effect is familiar: instead of handling every pair directly, the algorithm mixes values in carefully organized stages.

The progression has been remarkable. The Schönhage–Strassen algorithm from 1971 reached O(n log n log log n). Martin Fürer and later researchers reduced the extra factors. In 2021, David Harvey and Joris van der Hoeven published an unconditional O(n log n) algorithm in the multitape Turing-machine model. Their method used Gaussian resampling, multidimensional Fourier transforms, and Nussbaumer-style polynomial transforms.

For decades, n log n looked less like a temporary record and more like the natural floor. It was never proved to be a lower bound, though. Reading the input and writing the output already costs Ω(n), leaving a wide theoretical gap between linear time and n log n.

How can integer multiplication beat n log n?

The new claim attacks the machinery underneath the FFT rather than replacing multiplication with an unrelated trick.

A basic FFT step is called a butterfly. It takes two values and produces their sum and difference:

def butterfly(a, b):
 return a + b, a - b

One butterfly reaches only two values, but many butterflies arranged in layers can transform an entire array. For a transform with 2^m entries, the standard construction uses m · 2^(m−1) butterfly operations. The factor m comes from the number of layers, which is where the logarithm in n log n enters the cost.

The proposed improvement does not merely make one butterfly a little cheaper. It looks for a structured network that evaluates a large block of butterfly work with fewer arithmetic calls than the obvious arrangement. The network can also relabel coordinates, meaning it changes how values are grouped without changing the underlying computation.

That distinction matters. A shortcut for one fixed block would save only a constant factor. A constant factor does not change O(n log n) into a smaller asymptotic class. The crucial move is to repeat the structured shortcut across many coordinate directions, allowing the saving to compound.

Why amplification changes the story

Imagine finding a faster way to process a box containing sixteen small arrays. Repeating that trick over and over might save ten percent, but the saving would remain ten percent. The new approach tries to arrange the larger transform so that each repetition exposes another opportunity to reuse the same structural shortcut.

This process is described as amplification. In the underlying linear algebra, a small transform is applied across many axes of a multidimensional array. The algorithm mixes those axes through carefully chosen relabellings, then applies the cheaper block network repeatedly. The bookkeeping is formidable, but the intended result is a power saving in the number of logarithmic layers.

The headline relationship is:

T(n) / (n log n) = O((log n)^(-κ)) → 0

That limit is the whole point. A positive constant κ, no matter how tiny, makes the new running time little-o of n log n. Little-o notation means the ratio between the two costs tends to zero as the input grows. It does not mean the improvement is noticeable at ordinary sizes.

The difficult part is moving data, not only adding numbers

There is another trap in fast multiplication: arithmetic is only part of the job.

The 2026 preprint claims a result in both a Boolean circuit model and a fixed multitape Turing-machine model. A Boolean circuit counts logical gates, and fixed wiring can be treated very differently from data movement. A multitape Turing machine charges for reading, writing, and moving symbols along one-dimensional tapes. Rearranging a multidimensional array can therefore cost as much as the arithmetic performed on it.

The proposed algorithm has to speed up both sides. Its pipeline turns input bits into digit blocks, rearranges them with Chinese-remainder layouts, performs Gaussian resampling, evaluates synthetic Fourier transforms, and then reverses the process. The proof also has to track precision. Fourier-style methods use values that may look approximate during the calculation, but the final binary product must be exact.

The claimed construction handles this by bounding the accumulated error tightly enough that every recovered coefficient is within one-half of its correct integer value. Rounding can then recover the coefficients, and ordinary carry propagation produces the exact product. A missed rearrangement cost or a loose error estimate would be enough to break the final theorem.

A microscopic exponent with a macroscopic consequence

The stated value κ = 2^−182 is about 1.6 × 10^−55. In any practical calculation, 1−κ is indistinguishable from one. The constants and thresholds in the construction are also described as extraordinarily large, so this is not a new multiplication routine for ordinary computers.

The significance is structural. If the proof survives detailed checking, the conjecture that n log n is the optimal order for fixed-tape integer multiplication is false. The improvement would be exponentially larger, in the asymptotic sense, than earlier refinements involving log log n or iterated logarithms, even though the visible exponent barely moves.

As of October 20, 2026, David Harvey’s commentary treated the claim as plausible while stressing that he had not checked the proof in serious detail. That is the right level of caution. The next tests are line-by-line verification of the finite network, the tape rearrangements, the precision bounds, and the recursive cost estimate. A proof assistant formalization would strengthen confidence, but it would also need to formalize the machine model and the exact theorem, not only isolated arithmetic inequalities.

The headline is not that giant integers will multiply faster next week. It is that a barrier once regarded as part of the subject’s architecture may have been an artifact of how the computation was organized. If the argument holds, n log n will remain a historic milestone—but no longer the destination.