Faster than the FFT?

0:00The Fourier transform

The discrete Fourier transform takes n numbers and returns n weighted sums, with weights that are powers of an n-th root of unity. Done directly, that takes on the order of n squared operations. The fast Fourier transform of Cooley and Tukey splits a transform into smaller ones; Good and Thomas showed that for coprime factors the split is an exact tensor product, up to reordering, and Bluestein’s chirp trick turns any length into a convolution. Together they give a constant times n log n operations at every length. In our check, the coprime splitting reproduces the transform on lengths up to 210, and the chirp identity on lengths up to 100, to rounding error. Whether n log n is necessary is a long-standing open question. Lower bounds exist only in restricted models: Morgenstern proved one for circuits whose fixed coefficients are bounded in size, and Ailon for unitary two-coordinate gates on exactly n registers, or with well-conditioned intermediate steps. Alman and Rao improved the leading constant for power-of-two lengths, which leaves the n log n scale in place. Episode 109 covered a claim from the same release that integers can be multiplied faster than n log n; a small piece of that construction reappears here.

1:21The claim

Result 130 is two OpenAI preprints, of 49 and 31 pages, both dated September 25. Both use exact complex arithmetic, with every addition, subtraction and multiplication by a fixed constant costing one operation. The first claims that for every positive c there are arbitrarily long lengths n with an exact circuit for the transform using fewer than c·n log n operations. So no lower bound of a constant times n log n holds in this unrestricted model. That is an existence result along a sparse sequence of lengths. The second claims one deterministic algorithm for every length, using O(n (log n)^(1 − 10⁻¹³)) operations, counting the preparation of its constants and its index arithmetic, given one specified root of unity. It also gives exact convolution and polynomial multiplication in the same time, allowing products of two inputs. Nothing is claimed about floating-point arithmetic, numerical stability, bit complexity, or bounded coefficients, and the second paper says its constants are enormous. In our check, the fast recursion only starts on arrays with 2^72,000,000 entries, and even with every constant ignored, the explicit bound beats n log n only once the logarithm of the logarithm of n passes about 500 trillion. OpenAI published Lean formalizations of both main statements, 139 files and about 34,000 lines with imports, not counting Mathlib. We have not run the Lean check.

3:04How the proofs go

The explicit algorithm rests on one two-by-two matrix, C, with entries (1 + i)/2 and (1 − i)/2. Applied twice, it swaps two coordinates. Applying C along each of k binary axes, the ordinary way, costs k·2^(k − 1) applications of C. The paper builds a fixed network from the integer multiplication construction. Two banks of wires, indexed by triples of triples from a 100-element set, are exchanged, X and Y becoming −Y and X, using auxiliary wires whose arbitrary contents are restored exactly. In our check, we built this network on a 5-element set and confirmed the exchange and the restoration. Now replace every wire by an array indexed by a million bits, so 2^1,000,000 entries. Give every gate a binary subspace as its frame: scalar gates commute with frames, and moving between nested frames costs one directional step with C per dimension added or removed. Done this way, the whole network applies C on all million coordinates of every one of its roughly 2 × 10²¹ arrays, with about 6.9 quadrillion fewer directional steps than the ordinary method, a saving of under 4 parts in a trillion. Applied recursively in batches, that tiny fixed saving lowers the exponent: the tensor powers of C cost O(2^k k^θ), with θ 1 − 2.1 × 10⁻¹³. In our check, the frame identities hold on small cases, to rounding error, and the constants reproduce θ. To reach the Fourier transform, Newton interpolation factors the Fourier matrix of size r into diagonal matrices and a triangular Toeplitz matrix with its transpose. Each Toeplitz factor is computed by convolutions that borrow other coordinates with arbitrary contents and restore them, so everything runs on exactly r coordinates, in O(log⁴ r) layers, each a permutation with scalings or disjoint copies of C on pairs. The working length is a product of distinct small odd primes times a power of two, so the transform is a tensor product of small ones; synchronizing their layers, each slot splits into independent blocks, each a tensor power of C, handled by the fast recursion. Any requested length is then handled by a chirp convolution at a working length between 2 and 4 times larger. In our check, the Newton factorization is exact for every primitive root of every order up to 24. The 49-page paper reaches its existence theorem by another route. Call a finite win any fixed invertible matrix, not just a scaled permutation, whose tensor power can be computed exactly on the same coordinates with fewer calls than the ordinary method, when permutations and scalings are free. If no finite win existed, the paper builds a price for every matrix, with rules for tensor products, direct sums, corners and feedback. Pricing a family of signed reflections two ways then gives incompatible answers, roughly dw against (3/4)dw, so some finite win must exist. One finite win, amplified through tensor powers and carried to Fourier matrices by the same exact-width factorization, gives circuits below c·n log n along a sequence of lengths.

6:33Where it stands

The preprints are not peer reviewed and have not been revised. The Lean formalizations cover the existence theorem, and the uniform transform and convolution with their running time; the uniform proof uses its own smaller network, with a larger saving. We have not run them. Neither paper is among those OSVerify reviewed, and we have seen no expert review. If they hold, the fast Fourier transform is not optimal in the exact arithmetic model: n log n is not a lower bound there. The gain is real but astronomically small and appears only at astronomical sizes, and lower bounds with bounded coefficients, as well as floating-point and bit-level questions, are untouched.