OpenAI faster Fourier transform claim draws galactic algorithm criticism

What the post says

Ben Recht's Oct. 12, 2026 post on arg min examines part of OpenAI's math repository that claims a faster Fourier transform. He writes that the claim is less a breakthrough and more a malicious exploit, and he says he did not read the paper. Instead, he used a chatbot to pull out salient facts from what he calls AI slop mathematics.

The Fourier transform measures frequency content through dot products. For a length n digital signal, only n dot products at multiples of 2 pi over n are needed. A naive computation appears to require n squared operations. The fast Fourier transform devised by James Cooley and John Tukey in 1965 splits the input, computes two length n over 2 transforms, and recombines the outputs. Repeated log base 2 n times, it uses fewer than 5 n log base 2 n operations. For n equal to 1,000, n squared is 1,000,000 and 5 n log n is around 50,000, a 20 fold speedup. For n equal to 1,000,000, the speedup is 10,000 fold.

Why the speedup is galactic

Recht says the OpenAI result only makes the log n term slightly smaller in big O notation. He argues that big O can hide constants so large that the algorithm is galactic. His estimated values were C equals 10 to the 100 when N equals 10 to the 12. Even when n equals 10 to the 100, he says the Cooley and Tukey FFT would be 10 to the 99 times faster.

The model also assumes exact complex arithmetic. It requires multiplying complex numbers whose magnitudes grow superpolynomially with n, in a single operation. Stored as bits, the memory requirement would effectively be exponential in the input length. Recht notes that Jacques Morgenstern proved in 1973 that a Fourier transform could not run faster than one half n log n if complex coefficients had bounded magnitude. Forty years later, Nir Ailon showed that computing an FFT faster than n log n brought severe numerical instabilities.

A broader criticism

Recht connects the FFT claim to other results in the same repository, including a galactic matrix multiplication algorithm in O(n^2.25). He says the construction does not even let readers estimate the constant hidden inside big O. His broader point is that theoretical computer science often rewards proving that an algorithm exists without writing it down or running it on a computer. In his view, AI can now automate that tendency, producing papers that are formally stated yet detached from the computers people actually build.

Sources: Arg Min