Episode 109, October 2026

Faster than n log n?

A claimed multitape Turing machine that multiplies integers in time n (log n)^{1 − κ}, with κ = 2⁻¹⁸²

Covers result 109 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 109: Faster than n log n? An eight-point butterfly network above a strip of Turing-machine tape.

5:53. English captions available. The video loads from YouTube when you press play.

Chapters

The claims, in plain words

Multiplying two n-digit numbers the school way takes about n² digit products. Karatsuba and Ofman (1962) needed only three half-size products instead of four, which gives about n^1.585, and Toom pushed the exponent below 1 + ε for every fixed ε. The fast Fourier transform changed the scale: in 1971 Schönhage and Strassen multiplied n-bit numbers in time O(n log n log log n) on a multitape Turing machine and proposed n log n as the optimal order of growth. Fürer (2007) shrank the extra factor, and Harvey and van der Hoeven reached O(n log n) (Annals of Mathematics, 2021). Faster bounds were known only in stronger machine models, such as Schönhage’s storage modification machines.

Result 109 is one OpenAI preprint (73 pages) dated September 23, 2026. It claims one fixed Turing machine, with a finite alphabet and a fixed number of one-dimensional tapes, that computes the exact product of two n-bit integers for every n in worst-case time O(n (log n)^{1 − κ}), with κ = 2⁻¹⁸². That would refute the Schönhage–Strassen conjecture in this model: for every fixed machine, the time divided by n log n would tend to zero. The same bound follows for exact division with remainder and for integer square roots, and, through a reduction of Harvey and van der Hoeven, for transposing binary matrices on tapes.

What it doesn’t claim

It is not a practical algorithm. The saving over n log n is a factor (log n)^κ, which reaches 2 only when log₂ n = 2^2¹⁸²; in the paper’s words, the constants and thresholds are extremely large, and the algorithm is intended to establish a bit-complexity bound. The result concerns the multitape Turing machine; other models have their own, different bounds.

Where it stands

Posted as a preprint: OpenAI, 73 pages, dated September 23, 2026
Peer reviewed: Not yet
Checked in Lean: No; no Lean formalization was published for this result

Last checked October 19, 2026. The preprint has not been revised. OpenAI published no Lean formalization for this result. A companion preprint (result 130) uses the paper’s complex network for exact Fourier transforms below n log n operations. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

Why n log n. Splitting the numbers into digits turns the product into a convolution of digit lists, followed by carries, and fast Fourier transforms compute convolutions. A transform has about log n layers, each touching all of the roughly n stored bits; on tapes, data must also be rearranged between layers. Savings are needed both in moving data and in the butterfly arithmetic.
Two networks that save a power. Each network exchanges two banks of values in three stages, y ← y + x, x ← x − y, y ← y + x, giving (−y, x), a swap over the bits, and restores every scratch wire. When each wire carries an array stored in a changing representation, every change costs smaller calls to the same procedure; the representations are chosen so that the total number of smaller calls s is just below W·m, for W wires and m = 10⁶. Since s/W < m, interchanging two u-bit address fields costs O(V u^τ) with τ = 1 − 2⁻⁵⁰, against V·u for the standard method; simultaneous butterfly layers save a power in the same way.
Triples. The networks are built on the 161,700 triples of a 100-element set. In the bit network, 100 central wires collect, for each element, the sum of the values on triples containing it; scattering back gives each triple its own value plus those of triples meeting it in exactly one element, modulo 2, and side wires cancel those, as in decoding an index code. Labels from the triples’ indicator vectors make s fall short of W·m by about one part in 67 billion.
The exact product. The rest adapts the pipeline of Harvey and van der Hoeven: a Chinese-remainder map onto prime-length axes, Gaussian resampling to power-of-two lengths, Bluestein’s chirp back to convolution, and a twist into polynomials modulo y^r + 1, where roots of unity are signed shifts. The fast exchanges handle the data layouts and the butterfly layers speed up the polynomial transforms. Every recovered coefficient is within less than 1/2 of the true integer, so rounding and carries give the exact product. The smallest margin in the final cost table is 2⁻¹⁸¹ = 2κ.

The numbers in the video

Karatsuba’s recursion agrees with Python’s multiplication on 1,000 random pairs of 4,000-bit numbers; at 2²⁰ digits it needs about 315 times fewer digit products than the school method. For 1234 × 5678: 12 · 56 = 672, 34 · 78 = 2652, (12 + 34)(56 + 78) − 672 − 2652 = 2840, and the product is 7,006,652.
A floating-point Fourier multiplication of two random 100,000-bit numbers in 16-bit digits left every coefficient within 0.0034 of an integer; rounding gave the exact product.
The three-stage exchange takes (63, 22) to (63, 85), (−22, 85) and (−22, 63).
Both triple networks, with the paper’s eight-step schedule and random scratch values, added x to y and restored every scratch wire in 24 of 24 runs on ground sets of 5 to 8 elements.
For 100 elements: 161,700 triples, m = 1,000,000, about 1.77 × 10²⁰ wires in the bit network; the relative deficit (W·m − s)/(W·m) is 339/22,587,335,000,000, about one part in 67 billion.
The saving factor (log n)^κ − 1 is about 5 × 10⁻⁵⁵ for a million bits and below 10⁻⁵⁴ for 10⁸⁰ bits.

Read the source

Integer multiplication below n log n (PDF), 73 pages.
An explicit power saving for the exact discrete Fourier transform (PDF), the companion preprint.
The collection’s catalog, where this is result 109.

The paper

OpenAI groups related papers into one result; this one has a single paper.

Integer multiplication below n log n

Transcript

Read the full script

0:00Multiplying numbers

Multiplying two numbers of n digits the school way takes about n² digit products. In 1962, Karatsuba and Ofman did better: split each number into halves, and three half-size products, instead of four, give the whole product. Repeating the split gives about n^1.585. Toom pushed the exponent below one plus any fixed amount. In our check, Karatsuba’s recursion agreed with Python’s own multiplication on a thousand random pairs, and for a million digits it needs about 300 times fewer digit products than the school method. The fast Fourier transform changed the scale. In 1971, Schönhage and Strassen multiplied n-bit numbers in time n log n log log n on a multitape Turing machine, and proposed n log n as the true order of growth. Fürer shrank the extra factor in 2007, and Harvey and van der Hoeven reached n log n itself, in a paper published in 2021. Faster bounds were known only in stronger machine models, such as Schönhage’s storage modification machines. In our check, a floating-point Fourier multiplication of two random 100,000-bit numbers left every coefficient within 0.004 of an integer, and rounding gave the exact product.

1:21The claim

Result 109 is one OpenAI preprint, 73 pages, dated September 23. It claims one fixed multitape Turing machine that multiplies two n-bit numbers exactly, at every length, in worst-case time of order n (log n)^(1 − κ), where κ = 2^−182. That would refute Schönhage and Strassen’s conjecture that n log n is optimal in this model. The same bound follows for exact division and integer square roots, and, through a reduction of Harvey and van der Hoeven, for transposing binary matrices on tapes. The saving is extraordinarily small. The bound beats n log n by a factor of (log n)^κ, and that factor reaches two only when log n is 2^(2^182). The paper says its constants are extremely large, and that the algorithm is meant to establish a bound. There is no Lean formalization for this result. A companion preprint, result 130, uses one of the same networks for exact Fourier transforms.

2:30How the proof goes

Why n log n? Split both numbers into digits: the product is a convolution of the digit lists, followed by carries, and fast Fourier transforms compute convolutions. A transform has about log n layers, and each layer touches all of the roughly n stored bits. On a tape, data must also be rearranged between layers, and each pass costs time proportional to the tape’s length. So the paper needs savings in both places: moving data, and the butterfly arithmetic of each layer. The savings come from two fixed linear networks. Each exchanges two banks of values in three stages: add x to y, subtract y from x, and add x to y again. Over the bits, this is the familiar swap of two registers by exclusive or. Now let every wire carry a whole array, stored in a representation that changes along the network. Each change costs smaller calls to the same procedure, and the representations are chosen so that the total number of smaller calls, s, falls just below the number of wires, W, times a parameter m of 1,000,000. When s over W is less than m, the recursion saves a power: interchanging two address fields of u bits costs the volume times u^τ, with τ = 1 − 2^−50. The networks are built from the triples of a 100-element set, about 162,000 of them. In the bit network, 100 central wires collect, for each element, the sum of the values on triples containing it. Scattering back gives each triple its own value plus those of triples meeting it in exactly one element, and side wires cancel those, as in decoding an index code. Scratch wires end with their original contents. Labels from the triples’ indicator vectors make the total cost s fall short of W times m by about one part in 67 billion. In our check, the gate schedule added x to y and restored random scratch values in every small case. The rest adapts the pipeline of Harvey and van der Hoeven. The digit convolution moves onto prime-length axes by the Chinese remainder theorem; Gaussian resampling turns those transforms into ones with power-of-two lengths; Bluestein’s chirp makes them convolutions again; and a twist turns one coordinate into a polynomial ring, where roots of unity are signed shifts. The fast exchanges handle the data layouts, and the simultaneous butterfly layers speed up the polynomial transforms. Precision bounds keep every recovered coefficient within less than one half of the true integer, so rounding and carries give the exact product. In the final cost table, the smallest margin is 2^−181: twice κ.

5:20Where it stands

The preprint is not peer reviewed and has not been revised. There is no Lean formalization, and the argument rests on many explicit estimates over 70 pages. It is not among the papers OSVerify reviewed, and we have seen no expert review. If it holds, n log n is not the limit for multiplying integers on a multitape Turing machine; the saving is real in principle, and invisible at any size that could ever be written down.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.