Integer multiplication below n log n

← All digests

Family 109 · Theoretical computer science
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-09

Multiplying two integers is elementary arithmetic, but determining its fastest possible algorithm is a deep complexity problem. Family 109 claims a running time strictly below the long-conjectured $n\log n$ barrier in the ordinary multitape bit model. The improvement is asymptotic and extraordinarily small, but its meaning is precise: it changes the proposed ultimate growth rate.

1. The question

Suppose two nonnegative integers are supplied as binary strings of length $n$. Their product has at most $2n$ bits. School multiplication forms and adds many shifted partial products, taking quadratic time in a straightforward implementation.

The output is only twice as long as either input. How close can multiplication come to the linear time required simply to read and write these strings?

For decades, a central benchmark was $n\log n$. Sophisticated algorithms eventually attained this upper bound, while a matching general lower bound remained conjectural. The manuscript claims an exact deterministic algorithm with running time

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

Since the logarithmic exponent is smaller than one, the ratio of this bound to $n\log n$ tends to zero. That remains true however tiny the fixed positive constant $\kappa$ is.

2. Background and essential definitions

What counts as computation

A multitape Turing machine has a fixed finite number of tapes, each divided into cells from a fixed finite alphabet. Its heads move locally, at most one cell per step. Reading, writing, and moving data all contribute to running time.

This model does not give free random access to an enormous array or charge one operation for multiplying arbitrarily large integers. A claim about bit complexity must account for moving the actual encoded data.

“Uniform” means one fixed machine works for every input length. There is no separate uncharged circuit or advice table for each $n$. “Worst case” means the time bound applies to every pair of inputs of that length.

Multiplication as convolution

Split each input into blocks of bits, interpreted as digits in a base $B$. Write

$$a=\sum_i a_iB^i,\qquad b=\sum_j b_jB^j.$$

Before carrying, the product has coefficients

$$c_k=\sum_{i+j=k}a_i b_j.$$

This sequence is the convolution of the digit sequences. For example, multiplying digit polynomials $(a_0+a_1z)(b_0+b_1z)$ produces the middle coefficient $a_0b_1+a_1b_0$. After convolution, ordinary carry propagation converts the coefficients into valid base-$B$ digits.

A discrete Fourier transform changes coordinates so that convolution becomes pointwise multiplication. Transform both sequences, multiply corresponding transformed entries, and apply an inverse transform. This is the source of fast multiplication’s connection with harmonic analysis.

Exact answers from approximate intermediates

An algorithm may use approximate complex numbers internally and still return an exact integer product. It needs a rigorous error bound: if every recovered integer coefficient is within strictly less than one half of its true value, rounding to the nearest integer recovers it exactly.

Working precision, intermediate scaling, and rounding therefore belong to the complexity analysis. An arithmetic-operation count alone cannot establish the manuscript’s bit-time theorem.

3. Development history and previous partial results

Karatsuba and Ofman’s 1962 work showed that splitting an integer into two parts need not require all four large products suggested by direct expansion. Their three-product identity gives subquadratic multiplication. Toom subsequently developed further splitting methods. These early advances made recursion an essential tool.

Schönhage and Strassen’s 1971 paper, Schnelle Multiplikation großer Zahlen, used transform methods to achieve $O(n\log n\log\log n)$ multitape time. They proposed $n\log n$ as the optimal order. The distinction between this conjecture and their proven upper bound is central to the present family.

Fürer’s 2007 algorithm reduced the remaining overhead to a very slowly growing factor involving the iterated logarithm. Later work by Harvey, van der Hoeven, and Lecerf further developed fast transform and precision techniques.

Harvey and van der Hoeven’s integer multiplication algorithm, published in 2021, attained the unconditional $O(n\log n)$ bound. Gaussian resampling allowed the required transforms to be organized into convenient multidimensional shapes. Reaching the conjectured scale settled an upper-bound question, but did not prove that faster algorithms were impossible.

The cost of rearranging data remained relevant. Harvey and van der Hoeven’s 2025 work related integer multiplication to matrix transposition in the tape model, emphasizing that arithmetic and data movement cannot be separated casually.

The new manuscript builds on the established transform reduction while claiming savings in both transform layers and address rearrangements. Its target is precisely the overhead that a sequence of full-array scans would otherwise preserve.

4. What the new manuscripts claim

M1 states that one deterministic Turing machine, with a fixed finite alphabet and a fixed finite number of one-dimensional tapes, multiplies every pair of $n$-bit integers exactly in

$$T(n)=O\!\left(n(\lg n)^{1-2^{-182}}\right), \qquad \lg n=\max\{\lceil\log_2 n\rceil,1\}.$$

The clipped logarithm simply makes the expression meaningful at small lengths. The input allows leading zeroes, and the output is the product padded to exactly $2n$ bits.

The bound holds at every input length and in the worst case. It is not an average over random integers, a randomized success guarantee, or a result restricted to a sparse sequence of convenient lengths.

The manuscript also states corresponding worst-case bounds for exact quotient-and-remainder division by a nonzero integer and for integer square root. The latter returns $\lfloor\sqrt a\rfloor$, an exact integer, not a floating-point estimate.

The constants and thresholds are explicitly described as extremely large. The theorem is intended as a bit-complexity result, without a claim of competitive performance on practical input sizes.

5. Why the advance matters

Importance: 5/5, provisional. If correct, the claim refutes the proposed $n\log n$ optimality threshold in a standard and restrictive model of computation. Integer multiplication is a basic operation underlying exact arithmetic and many number-theoretic algorithms, so its asymptotic complexity has unusually broad significance.

The size of the saving and its conceptual force should be distinguished. The factor gained over $n\log n$ is a power $(\log n)^{\kappa}$. Because $\kappa$ is so small, this grows imperceptibly over ordinary scales. Yet a fixed positive exponent saving disproves an eventual lower bound of the conjectured form.

The model also makes the result more demanding than a formal manipulation of arithmetic circuits. Moving bits to where they are needed is charged. A method that saves multiplications but spends the same $n\log n$ time reorganizing data would not establish the theorem.

The rating reflects the central problem and the claimed change in its asymptotic answer. It does not imply a useful replacement for current multiplication libraries.

6. The main idea

Two costs must fall together

A transform on a large array typically has many levels. If each level scans a linear volume of stored bits, logarithmically many levels produce the familiar $n\log n$ cost. The manuscript develops two procedures to reduce this burden.

The first exchanges two fields within array addresses. For example, an address may encode a row and a column; exchanging them reorganizes the data as a transpose. The final action is an exact permutation, but intermediate steps are allowed to mix data by exclusive-or operations.

The second processes many transform “butterflies” together. A basic normalized butterfly maps a pair to

$$(u,v)\longmapsto\left(\frac{u+v}{2},\frac{u-v}{2}\right).$$

Instead of charging a full separate pass for every coordinate direction, the construction combines operations across several directions. Numerical values use carefully chosen fixed-point representations, and truncation follows completed layers under controlled bounds.

Change the representation during the computation

The paper’s linear networks use different invertible coordinate systems for arrays at different stages. A stored array may represent a transformed version of the logical array. When a gate acts linearly on several arrays in the same coordinate system, applying the gate commutes with that common change of coordinates.

This makes it possible for intermediate coordinate changes to cancel, leaving the desired transformation only at the endpoints. Auxiliary values are restored, so they need not begin as a specially prepared store of zeroes.

One can think of this as computing with encoded data while keeping track of the encoding. It is an explanatory analogy: the paper supplies exact linear identities and charges the work needed to implement them on tapes.

A strict recursive saving

The finite network arranges that a larger task splits into fewer smaller calls than a direct volume-times-dimension accounting would predict. If $W$ is the number of data streams and the parameter grows by a factor $m$, the key inequality has the form $s<Wm$, where $s$ counts recursive calls.

After normalizing by stored volume, the recursive growth is strictly smaller than linear in the parameter. This produces a small positive power saving. The rest of the argument must preserve it through padding, shifts, precision management, and layout changes.

Return to exact integer arithmetic

The algorithm places these procedures inside convolution reductions involving multidimensional transforms and polynomial rings. Forward transforms retain compatible frequency orders, so some expensive permutations cancel across pointwise multiplication and the reverse transform.

Finally, the paper bounds the coefficient error below one half, rounds, and propagates carries. This is how approximate internal transform computations deliver the exact binary output required by the theorem.

7. Scope, limitations, and open questions

The statement is model-specific: fixed finite tapes, local head motion, and explicitly charged bit operations. It should not be restated merely as “a faster Fourier transform” or as an arithmetic bound over exact complex numbers. Family 130 studies a different transform model.

The result leaves open the optimal complexity of multiplication. It does not attain linear time, nor does it supply a matching lower bound for its new exponent. Improving the extremely small saving, reducing constants, and determining whether any ideas are practical are separate questions.

The algorithm also uses established multiplication machinery inside its construction. A faster final bound can arise even when some subroutines use an older bound, provided those subproblems are sufficiently small and the full cost accounting fits together.

8. Sources and further reading

The Harvey–van der Hoeven paper linked above explains the $n\log n$ baseline and the resampling framework. M1’s introduction separates its two tape procedures from the later convolution, precision, and carry steps; that separation is a useful guide through an otherwise technical algorithm.

Source manuscripts

• M1. OpenAI, Integer multiplication below n log n (September 23, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.