Exact Fourier transforms below $n\log n$

The explanation

Take four numbers: 1, 2, 3 and 4. The discrete Fourier transform [a fixed recipe that splits a list into frequency components] makes four new numbers from them. Each output is a weighted sum of all four inputs. The weights are powers of i, the square root of minus one. Here the outputs are 10, −2−2i, −2 and −2+2i. Done directly, each of n outputs touches all n inputs. So the work grows like n times n.

The fast Fourier transform does far better. Cooley and Tukey's 1965 method uses about n log n operations [single additions, subtractions or multiplications]. Take about a million inputs, n = 2^20. Then n times n is about 1.1 trillion. But n times log₂n is about 21 million, roughly 52,000 times less. Bluestein's chirp trick later carried the n log n bound to every length, not only convenient ones.

Could anything beat the n log n scale itself? Alman and Rao improved the constant in front, to (15/4) n log₂n real operations for power-of-two lengths. That stays on the same scale. Lower bounds [proofs that no method can do better] exist only in restricted settings. Morgenstern's applies when every coefficient [a fixed number the method multiplies by] stays bounded in size. Ailon's apply to rotation-like steps on two numbers at a time. Another limits how distorted the middle steps may be.

These two papers prove that, in an idealized exact model, the scale can be beaten. The model computes with complex numbers exactly. It allows coefficients of any sizeSource 1. It is handed one specified root of unity [a complex number with some power equal to 1]. That root has polynomial order [its power grows at most like a fixed power of n]. From it, the method builds every needed weight. The companion paper gives circuits [fixed lists of operations] for some lengthsSource 2. Their cost falls below any fixed multiple of n log₂n. The main paper gives one algorithm for every length n. Its cost is O(n (log n)^(1−10^−13)) operationsSource 3. That count includes preparing the weights and arranging the data in memorySource 4.

The saving is real but almost unmeasurably small. Compared with n log n, the new bound saves a factor of (log n) raised to the power 10^−13. Ignore the hidden constants and take n = 2^20 again. That factor then differs from 1 by under 3 parts in ten trillion. To halve the work, log n itself would need about three trillion digits. The paper says plainly that its constants are enormous, with no useful crossover pointSource 5. This is a statement about how the cost grows, not about faster software.

The saving starts from one small, fixed computation. It applies a single 2-by-2 matrix of complex numbers along many axes at once. That is a tensor power [the same small map applied along every axis of a grid]. A known network from an OpenAI integer-multiplication paper does this with a strict savingSource 6. The hard part is carrying one fixed saving into a single algorithm for every lengthSource 7. The paper names three places it could leak. Recursive steps could each need fresh scratch space. Small Fourier transforms could need extra working room. Bookkeeping could cost one step per axis at every array entry. The paper counts each of these and shows none eats the savingSource 8.

The model matters for what the result means. Exact arithmetic with unlimited coefficients is not how computers handle real numbers. The paper makes no claim for floating-point FFTs, numerical stability or bit costSource 9. So it does not contradict Morgenstern's bounded-coefficient lower bound. The same speed carries over to multiplying two complex polynomials exactly, under the same assumptionsSource 10.

How sure is this? Formal versions of both results are written in Lean, a computer proof assistant. One is the subsequence result: at some lengths, circuits beat any fixed multiple of n log₂n. The other is the all-length program for the transform and for convolution, with cost O(n (log n)^(1−10^−13)). That formalization includes choosing the root and preparing the weights. The paper's appendix on extracting and searching for certificates lies outside it. No specialist review has been published.

What it doesn't show. This does not give a faster FFT for real computers, which round numbers and limit their size.