Glonce

OpenAI's claimed faster Fourier transform is impractical, a blog post argues

researchThe Glonce editorsHacker News🔥69Glonce rating69Impact40Novelty45Relevance85Surprise45Players70Credibility55
OpenAI's claimed faster Fourier transform is impractical, a blog post argues

A post on the argmin blog looks at one result from the batch of mathematics papers OpenAI released last week: a claimed faster Fourier transform, in a paper file named main.pdf. The author's verdict is that there is no practically faster FFT here. The result is a 'galactic algorithm' with astronomically large hidden constants, and it rests on a model of computation that bears no resemblance to an actual computer.

The post first sets the stage. A naive Fourier transform of a length-n signal needs about n^2 arithmetic operations. The fast Fourier transform, devised by James Cooley and John Tukey in 1965, splits a length-n transform into two of length n/2 and recombines them, and with bookkeeping it needs fewer than 5 n log2 n operations. At n = 1,000 that is about 50,000 operations against 1,000,000, a 20-fold speedup; at n = 1,000,000 the speedup is 10,000-fold. Since you need at least n steps just to write the output down, the FFT sits a factor of 5 log2(n) above that speed limit, which is about 200 when n is a trillion. OpenAI's paper claims to shave that log(n) term by a teeny tiny bit.

The author says he did not read the paper, and asserts that no one at OpenAI did either. Instead the author fed it back to ChatGPT in an information retrieval session and asked what the chatbot thinks of its own output. The conclusion: no faster Fourier transform, only what the author calls rot that develops when formalism detaches from reality.

The core complaint is about big-O notation, which ignores constants. O(n) can hide a constant like 10^80, roughly the number of atoms in the known universe, which is why Richard Lipton and Ken Regan call such algorithms galactic. For the OpenAI FFT the post gives an estimated constant C of 10^100 when N = 10^12, so even at n = 10^100 the Cooley-Tukey-Gauss FFT would be 10^99 times faster. In big-O terms the new result is technically asymptotically faster, but it wins only when n is impossibly large.

The second problem is the model of computation. The paper uses exact complex arithmetic: complex numbers stored and multiplied at arbitrary precision, with magnitudes that grow superpolynomially in n, all multiplied in a single operation. Stored as bits, those numbers would need memory exponential in the input length. No computer can do this. So whether the theorem in main.pdf is true is something the author says no one knows and he does not care about, because it does not solve the problem people wanted solved.

The post adds history. In 1973 Jacques Morgenstern proved that no Fourier transform could beat ½ n log n if the complex coefficients used had bounded magnitude. Forty years later Nir Ailon showed that you cannot compute an FFT faster than n log n without severe numerical instabilities. Each time, people objected that the model was too restrictive. The author concludes that the new result is less a mathematical breakthrough and more an oddity of computer scientists being bad at formalizing their design specifications.

He extends the critique to other results in the release. One is a galactic algorithm to multiply two matrices in O(n^2.25) operations; its construction does not let you even estimate the constant hidden inside big O, and the author could not get an OpenAI model to produce a quantitative estimate of it either. He says that if written substantially better, such papers would have reached the most prestigious theory venues, STOC or FOCS, and the matrix multiplication paper would likely have won awards, yet none of it has to do with computers. He ties this to a theory culture that discourages running algorithms on a computer, and argues that AI is good at automating such worst tendencies, so it can now write useless theory papers.

Key facts

  • The author argues the faster Fourier transform in OpenAI's math paper batch (main.pdf) is a galactic algorithm: asymptotically faster in big-O terms, but only when n is impossibly large.
  • The post gives an estimated constant C of 10^100 when N = 10^12, so even at n = 10^100 the Cooley-Tukey-Gauss FFT would be 10^99 times faster.
  • The algorithm assumes exact complex arithmetic: numbers of superpolynomially growing magnitude multiplied in a single operation, which no real computer can do.
  • Morgenstern (1973) and Ailon (forty years later) had already shown that beating the standard FFT bounds needs bounded-coefficient or numerically unstable models.
  • The author did not read the paper; he asked ChatGPT about it, and he does not know or care whether the theorem is true.

Why it matters

The FFT is one of the most important innovations in digital signal processing, and its speedups, 20-fold at n = 1,000 and 10,000-fold at n = 1,000,000, can be the difference between a transform being computable or not. A claimed improvement therefore draws attention. The post argues that this one is an artifact of formalism: big-O notation treats all constants as equivalent, and the model of computation used is far from real machines. It also shows how a headline 'breakthrough' in a large batch of AI-released mathematics can say little about practical computing.

Who it affects

Practitioners who rely on FFTs in signal processing should see no change: the author did not find a practically faster FFT. The post is aimed more at mathematicians and theoretical computer scientists, and at anyone trying to judge the large batch of math papers OpenAI released. The author also directs his critique at the culture of theoretical computer science and its prestigious venues, STOC and FOCS.

How to use it

There is nothing to install or run. The post is a reading aid: it includes tutorial material on the Fourier transform, the FFT and big-O notation for readers who need a refresher. The practical lesson it offers is to check two things when you see an asymptotic speedup: how large the hidden constant is, and whether the model of computation resembles an actual computer.

How solid is it

This is an opinionated blog essay, not a formal refutation. The author says he did not read the paper and instead queried ChatGPT about it, so the critique rests on that session and his own reasoning about big-O and the computation model. The figures for the constant are given in the post as estimates. The exact bound claimed in main.pdf and the threshold value of n above which the OpenAI algorithm would win are not given in the text. No independent expert verification of the OpenAI proofs is reported, and no response from OpenAI is reported. The author himself says he does not know whether the theorem is true.

Risks and caveats

The post does not say the OpenAI result is wrong; it says the result is irrelevant to the practical problem, and that its truth is unknown to the author. The tone is polemical, with phrases like 'slop machine' and 'trash dump of proofs', and the broader claims about theoretical computer science culture and about AI amplifying bad habits are the author's opinions. The author also notes that Lipton and Regan argue galactic algorithms are useful because they spur research, though he knows of no legitimate example where a practical algorithm resulted. Readers should treat the numbers about the constant as the author's estimates rather than a verified analysis of the paper.

“This new OpenAI result is thus less a mathematical breakthrough and more an oddity of computer scientists being bad at formalizing their design specifications.”

— argmin blog post on OpenAI's faster Fourier transform