How a 23-Year-Old Disproved Math's Assumed Speed Limit for Multiplication

Multiplication looks like the simplest operation in arithmetic, but computer scientists still don't know the fastest way to do it — and the search for that limit runs through a Moscow seminar room in 1960 and a Turing-machine proof published six decades later.

Kolmogorov's 1960 Seminar and the Week That Broke His Conjecture

The method taught in grade school — stacking one number on another and multiplying every digit against every digit — takes a number of single-digit multiplication steps that grows with the square of the digit count. Multiplying two two-digit numbers takes four such steps; two three-digit numbers take nine. Computer scientists call this O(n²), and for centuries it looked unavoidable.

At a 1960 seminar at Moscow State University, mathematician Andrey Kolmogorov formally proposed that O(n²) was in fact the fastest possible speed for multiplication. Anatoly Karatsuba, a 23-year-old student in the room, returned about a week later having disproven it. According to the account in Scientific American, Kolmogorov was stunned enough by the result that he wrote up the formal proof himself and submitted it to the Proceedings of the USSR Academy of Sciences with Karatsuba listed as lead author — who reportedly only learned the paper existed when the reprints arrived in the mail.

The 1971 conjecture that followed, and the 2019 paper that eventually answered it, both build on the same core idea Karatsuba introduced: trade expensive multiplications for cheap additions.

Karatsuba's Trick Turns Four Multiplications Into Three

The mechanism itself is almost willfully unintuitive. Split each number into two halves — for 12 × 34, that's a=1, b=2, c=3, d=4 — and the product expands into 100(ac) + 10(ad+bc) + (bd). The grade-school method computes ac, ad, bc, and bd separately: four multiplications. Karatsuba noticed that once you have ac and bd, the cross-term (ad+bc) can be recovered from a single additional multiplication — (a+b)×(c+d) minus ac minus bd — turning four multiplications into three.

Applied once, that's a modest saving. Applied recursively — splitting each half into halves again, and again — the savings compound. A four-digit pair like 1,234 × 5,678 drops from 16 single-digit multiplications to 9. At the scale of two 1,000-digit numbers, the grade-school method needs on the order of a million single-digit multiplications; Karatsuba's method needs fewer than 57,000. The algorithm now runs quietly inside real software: Python's implementation switches from grade-school to Karatsuba's method once integers reach roughly 630 decimal digits, a detail visible directly in Python's own source code.

Grade School, Karatsuba, and the Search for O(n log n)

Karatsuba's algorithm runs in roughly O(n^1.585) — worse than the theoretical floor, but a decisive improvement on O(n²). It ignited a decades-long hunt for something faster still. In 1971, Volker Strassen and Arnold Schönhage conjectured that O(n log n) was achievable — a bound so tight that it's barely more work than simply reading the digits of the numbers involved. That conjecture stood unproven for nearly half a century until David Harvey and Joris van der Hoeven presented an algorithm computing the product of two n-bit integers in O(n log n) bit operations, published in Annals of Mathematics in 2021.

Plotting the three stated formulas against each other shows why each breakthrough mattered, and why the gaps between them widen dramatically as numbers grow.

Why the Fastest Known Algorithm May Never Multiply a Real Number

The Harvey–van der Hoeven result is what computer scientists call a galactic algorithm: correct, faster in principle, and essentially useless in practice, because its overhead only pays off for numbers far larger than any real computation encounters. Karatsuba's method still does the practical work in modern software; O(n log n) exists mainly to mark the outer edge of what's mathematically possible.

That edge, though, is a belief, not a proof. Researchers widely suspect O(n log n) is the true floor for multiplication, but no one has proven a faster algorithm is impossible — the same position mathematicians were in before Karatsuba's week-long detour through Kolmogorov's conjecture. Interest in speeding up and re-verifying mathematical tools isn't confined to complexity theory, either: a separate project applying AI agents to revive dozens of retired math tools reflects the same broader push to re-examine long-settled mathematical infrastructure. For multiplication, the question that stalled a 23-year-old for exactly one week in 1960 is, six decades on, still open.