A look at the math that OpenAI claims computes faster Fourier transforms

What it claims

The post's verdict on OpenAI's "faster FFT" (in the released main.pdf) is that it has no practical use. The hidden constant is estimated at C ≈ 10^100 for N = 10^12. On that basis the author states that even at n = 10^100, standard Cooley-Tukey would still be about 10^99 times faster. The asymptotic gain is only "a teeny tiny bit" off the log(n) term.

How it works

• Baseline being beaten. Cooley-Tukey takes fewer than 5·n·log2(n) operations. That is about 50,000 versus 1,000,000 naive operations at n = 1,000 (20×), and a 10,000× gain at n = 10^6. The 5·log2(n) factor over the linear-time limit is about 200 at n = 10^12. That factor is the only room any faster FFT could win.
• Model of computation. The new algorithm assumes exact complex arithmetic, with single-step multiplication of arbitrary-precision numbers. Their magnitudes grow superpolynomially in n. The author notes that storing them as bits would make memory effectively exponential in the input length.
• Why that assumption is needed. Two known lower bounds fence off realistic models:
• Morgenstern (1973): no FFT beats ½·n·log n if the coefficients have bounded magnitude.
• Ailon, about forty years later: going below n·log n requires severe numerical instability.

The OpenAI result escapes both bounds only by dropping these constraints.

Evidence

The constants come from the author's chatbot session, not from the paper. The author says outright that they did not read main.pdf. Instead they had ChatGPT extract its claims. The post does not state whether the theorem itself is correct ("no one knows, and I don't care").

The same critique applies to the claimed O(n^2.25) matrix multiplication. Its bound has the form T(n) ≤ n^(2.25 + ε + C/log n) for every ε > 0. The author could not get any OpenAI model to give a numeric estimate of C, and says the construction does not allow C to be estimated at all.

Limits

• The figures above (C ≈ 10^100, magnitude growth) are second-hand, extracted via ChatGPT. Check them against main.pdf before citing.
• The post gives no runnable algorithm or code and makes no attempt to implement either result.
• The author grants that both papers, if better written, would likely be accepted at STOC/FOCS, and the matrix one would likely win awards. So for theoretical work, the results may matter even though they are useless for computation.
• For an engineer the takeaway is practical: neither result changes which FFT or matmul you should use. Under finite-precision arithmetic, the Morgenstern and Ailon bounds still describe the real limits.