OpenAI algorithm for the FFT is less a breakthrough and more a malicious exploit

Ben Recht dissects OpenAI’s claim of a faster Fast Fourier Transform and shows it is an asymptotic curiosity, not a practical breakthrough. He explains the FFT’s importance and how Cooley-Tukey achieves roughly 5 n log2 n arithmetic operations. OpenAI’s proof reduces the log factor in big-O terms, but Recht demonstrates the result hides astronomically large constants and relies on an unrealistic computation model: exact complex arithmetic on numbers whose magnitudes grow superpolynomially, implying astronomic bit-sizes and effectively exponential memory if represented realistically. Estimated constants (roughly 10^100 when N = 10^12) mean the new algorithm would only outperform classical FFTs at impossibly large n, so the “speedup” is purely asymptotic.

He situates the claim among prior theoretical barriers (Morgenstern’s and Ailon’s limits) to argue that breaking FFT lower bounds requires implausible assumptions or causes numerical instability. The same critique applies to OpenAI’s matrix-multiplication claims, where hidden constants are unquantified. Recht contends that theoretical computer science often prizes existence proofs divorced from real machines, and that AI now amplifies the production of such formal but practically irrelevant results. The takeaway: these proofs are mathematical oddities that exploit holes in formal models rather than deliver usable algorithmic advances.