Harvey 2026 Integer Multiplication Algorithm Breaks the O(n log n) Barrier

Summary

The algorithm announced by David Harvey in October 2026 achieves o(n log n) bit‑operations for multiplying two n‑bit integers, improving on the long‑standing O(n log n) bound of the 2021 Harvey‑van der Hoeven algorithm. The result hinges on a novel tensor‑amplification technique that reduces the number of butterfly operations in the FFT‑based convolution, and on a sophisticated gadget that evaluates many independent DFTs with fewer slice‑calls than naïvely expected. Although the author has not checked every detail, the community consensus—bolstered by extensive LLM‑assisted verification—finds the claim plausible and potentially correct.

1. Why o(n log n) Matters

The takeaway: Reducing the exponent of the logarithmic factor below 1 would make integer multiplication asymptotically faster than any algorithm based on the classic FFT, overturning a belief that O(n log n) was optimal for decades.

Implications:

Introduces a new exponent of integer multiplication, α < 1, where the running time is O(n (log n)^α). The paper reports α≈0.9983, a tiny but mathematically significant improvement.
Breaks the barrier that has stood since Schönhage–Strassen (1971) and the 2021 O(n log n) algorithm.
Provides a template—tensor amplification + gadget construction—that may be refined to push α even lower, possibly toward the conjectured ½ lower bound.

2. High‑Level Structure of the New Algorithm

2.1. Building on the 2021 Algorithm

The 2021 Harvey‑van der Hoeven algorithm reduces integer multiplication to a high‑dimensional discrete Fourier transform (DFT) over the ring R = C[y]/(y^r + 1). The core cost comes from the butterfly arithmetic of the FFT, which contributes the O(n log n) term.

2.2. Tensor‑Amplification Idea

Let A be the 2 × 2 butterfly matrix. Computing A^{⊗ m} on a vector of size 2^m normally needs m·2^{m‑1} slice calls (butterfly applications).
If a program can compute A^{⊗ m} with g < m slice calls, then by recursively tensor‑expanding the program we obtain a factor (g/m)^k for inputs of size 2^{mk}. This yields a running time of n^{log g / log m} · 2^{n‑1}, i.e. O(N (log N)^α) with α = log g / log m < 1.
The key is to find such a program for a modest m and then amplify it.

2.3. The Gadget

Harvey describes a gadget that evaluates W independent copies of A^{⊗ m} using fewer than the naïve W·m slice calls. The construction:

Works with the unitary version C of the butterfly (C = (1/√2)·B).
Introduces slice calls Cv (direction‑specific butterfly) and relabellings (linear permutations) that are free in the Boolean circuit model.
Organises registers into subspaces of F₂^m and uses carefully chosen orthogonal vectors to turn a slice call into a controlled operation that simultaneously advances many registers.
By exploiting linear relations among the subspaces, the gadget saves a constant factor per register, turning the total slice‑call count from W·m to W·m − Θ(|T|), where |T| is cubic in a parameter h (the size of the underlying 3‑element subsets).

When h is large enough (h ≥ 22 according to the author’s calculations), the savings outweigh the overhead, giving a net reduction in slice calls.

3. Detailed Walk‑through of the Construction

3.1. Notation Recap

C₂: 2‑dimensional complex vector space.
(C₂)^{⊗ m}: Tensor power, representing an array of size 2^m.
F₂^m: Binary address space; vectors are written as v.
Cv: Slice call that applies C in direction v (i.e., on pairs (x, x+v)).
Φ_U: Linear operator that implements the product of Cv’s for a subspace U.
U, U^⊥: Non‑degenerate subspaces and their orthogonal complements under the dot product.

3.2. The Baby Program (Section 7.5)

The baby program works on a modest dimension h ≥ 8 and demonstrates the core saving:

Registers are split into data (x_T, y_S), side (A_{S,T}), and central (c_i, c_*).
Each register carries an associated subspace U; a slice call Cv updates U while leaving the underlying value unchanged.
A sequence of 8 steps alternates transform phases (adding slice calls to grow subspaces) and mix‑up phases (linear combinations of registers sharing the same subspace).
The total slice‑call count becomes W·h − 2|T| + 2(h² + h), which is < W·h for sufficiently large h because |T| = Θ(h³).

3.3. Scaling to the Main Program (Section 7.6)

The main program lifts the baby construction to m = h³ dimensions:

Addresses become F₂^{m} = (F₂^{h})^{⊗ 3}, i.e., h × h × h bit arrays.
Data registers are now triples x_{a₁,a₂,a₃}, y_{a₁,a₂,a₃} for all triples (a₁,a₂,a₃)∈T³.
Three stages apply the baby program along each tensor dimension, each time tensor‑inflating the slice directions (v → v⊗v_{a₂}⊗v_{a₃}, etc.).
After the three stages, every register has been transformed by C^{⊗ m}, i.e., the full DFT needed for the convolution.
The total slice‑call count simplifies to W·m − Θ(|T|²), again strictly smaller than the naïve W·m for large h.

4. Community Reactions & Open Issues

Commenter	Key Point	Relevance
jdb1729	Formal Lean proof exists (α≈1‑2⁻¹⁴·³⁸).	Confirms plausibility; provides a machine‑checked foundation.
Kapura	Author admits not reading the papers; relies on LLM explanations.	Highlights the new research workflow where LLMs mediate understanding.
kenferry	LLM (Claude Fable 5.1) appears to “understand” the paper instantly, unlike humans.	Raises concerns about trust and verification when AI claims correctness.
DannyBee	Model cannot yet produce a program with g < m; argues why it may be impossible.	Suggests a potential barrier: each slice call can at most double non‑zero entries.
flebron	Emphasises the distinction between O and o notation.	Clarifies that the improvement is strictly sub‑O(n log n).
Eji1700	Practical impact is limited for now; the improvement is asymptotic.	Sets realistic expectations for near‑term applications.

Open technical questions (as identified by the author):

Linear‑operation count & synthetic roots of unity – how they interact with tensor amplification.
Effect of increasing the dimension parameter d in the 2021 algorithm.
Data‑rearrangement costs in the Turing model – currently ignored but essential for a full complexity claim.
Finding a smaller gadget – a better gadget could push α lower, perhaps toward the conjectured ½.

5. Consequences for Related Problems

Exponent of Integer Multiplication: The paper defines α as the infimum of exponents satisfying O(n (log n)^α). The new bound shows α < 1, overturning the previous belief that α = 1.
Network‑Coding Lower Bounds: Combined with the Boolean‑circuit lower bound of Afshani et al. [AFKL19], the result disproves the Li–Li network‑coding conjecture.
Polynomial Multiplication over Finite Fields: The current state‑of‑the‑art is O(n log n · 4^{log* n}) [HvdH19]. The techniques suggest a conditional O(n (log n)^α) algorithm, but no unconditional improvement is yet known.
Prime‑Enumeration Algorithms: Harvey’s own prime‑enumeration work [Har26] relies on fast multiplication in F₂[x]; the new bound could improve the bottleneck if the conditional polynomial‑multiplication improvement materialises.

6. The Role of AI in the Discovery

Harvey’s note is unusual in that most of the understanding came from an LLM (Claude Fable 5.1):

The author asked the model to explain the dense 38‑page manuscript.
The model supplied step‑by‑step clarifications, identified the crucial amplification trick, and even generated a sanity‑check implementation of the baby program.
This workflow illustrates a new research paradigm where human experts act as orchestrators of AI reasoning rather than the sole source of insight.

The community’s mixed reactions—excitement about the breakthrough, but also caution about over‑reliance on opaque AI explanations—reflect the broader debate on AI‑augmented mathematics.

7. Outlook

The algorithm’s asymptotic improvement is real (assuming the gadget and amplification arguments hold). The next milestones are:

Formal verification (e.g., Lean proofs) to eliminate any lingering doubt.
Extension to the Turing model, accounting for data‑movement costs.
Optimization of the gadget to lower α further, perhaps approaching the theoretical ½ barrier.
Exploration of practical impact, such as integration into high‑precision libraries, once the constant factors become reasonable.

If these steps succeed, the result will not only rewrite the textbook entry for integer multiplication but also cement AI as a first‑class collaborator in frontier theoretical computer science.

8. References

[AFKL19] Afshani, Freksen, Kamma, Larsen. Lower bounds for multiplication via network coding, ICALP 2019.
[Har26] D. Harvey. Faster enumeration of primes, arXiv:2606.22851, 2026.
[HvdH19] D. Harvey & J. van der Hoeven. Faster polynomial multiplication over finite fields, J. Complexity 54 (2019).
[HvdH21] D. Harvey & J. van der Hoeven. Integer multiplication in time O(n log n), Ann. of Math. 193 (2021).
[HvdH22] D. Harvey & J. van der Hoeven. Polynomial multiplication over finite fields in time O(n log n), J. ACM 69 (2022).
[HvdH25] D. Harvey & J. van der Hoeven. Integer multiplication is at least as hard as matrix transposition, arXiv:2503.22848, 2025.
[LL04] Z. Li & B. Li. Network coding in undirected networks, CISS 2004.
[TC26a‑c] The Company. Integer multiplication below n log n (GitHub, 2026).
Additional community comments are quoted throughout the article.