Faster Fourier Transforms

gist

Ben Recht examines the faster Fourier transform in OpenAI’s math paper dump and finds a galactic algorithm: its O(n(log n)^(1−10^−13)) bound hides constants so large that Cooley–Tukey wins for any realistic n, and it relies on exact arbitrary-precision complex arithmetic no computer has. He argues the result exposes how theoretical computer science, loose with big-O and indifferent to running code, rewards status puzzles, and that AI is now automating those worst habits.

ideas

• The FFT speed limit. Cooley–Tukey needs under 5n log₂ n operations; shaving the log factor would matter, which is why a faster FFT claim is intriguing.
• Galactic constants. The estimated constant is 10^100 for N = 10^12, so the new method only wins when n is at least 10^10^10^15.
• An impossible machine. The model assumes exact complex arithmetic on numbers that grow superpolynomially, multiplied in one step; Morgenstern and Ailon already showed bounded or stable computation cannot beat n log n.
• Theory without computers. Recht argues TCS culture accepts existence proofs never run, so such papers, better written, would reach STOC or FOCS and the n^2.25 matrix result might win awards.
• AI amplifies bad habits. Language models automate cultural practices nobody likes, and the absurd volume of AI proofs might prompt the field to change course.

quotes