On October 6, OpenAI published a repository called openai/math, several hundred manuscripts and proof artifacts that the company describes as produced by an internal model. One of those manuscripts promises a faster Fourier transform, the algorithm underneath essentially all digital signal processing, and promises it against a record that has stood since 1965. This week Ben Recht, who writes the optimization blog arg min, read it back to us and did not like what he found. His title states the charge plainly: the OpenAI algorithm for the FFT is less a breakthrough and more a malicious exploit. What he is describing is not a wrong proof. It is a true statement about a computer that does not exist.
The Fast Fourier Transform is one of the genuinely load-bearing algorithms of the modern world, and the version everyone uses was written down by James Cooley and John Tukey in 1965. The naive way to compute a Fourier transform of length n takes on the order of n-squared operations. The FFT does it in fewer than 5n times log-base-two of n, which does not sound like much until you plug in a number: at n equals a million, that is a ten-thousand-fold speedup, the difference between a transform being computable and not. Since then, people have tried to shave that prefactor of five, and a body of theory says you basically cannot. In 1973 Jacques Morgenstern proved that no Fourier transform can run faster than half of n log n if the complex coefficients it multiplies stay bounded in magnitude. Forty years later Nir Ailon showed you cannot beat n log n without severe numerical instability. Both results were attempts to say the obvious thing: an algorithm you cannot actually run is not faster than one you can.
OpenAI’s manuscript works around that by changing what “computer” means. Recht’s core finding is that the speedup depends on a model called exact complex arithmetic, where you can store and multiply complex numbers of any precision in a single operation. The trouble is that the algorithm requires multiplying complex numbers whose magnitudes grow superpolynomially with n. If you wrote those numbers out as bits, the memory requirement would be exponential in the length of the input. We do not have machines that do this. There is a second layer to the trick, and it is the one that gets quoted most often on Hacker News: big-O notation, the accounting language of algorithmic analysis, is completely blind to constants. An algorithm is “linear time” even if its hidden constant is 10-to-the-100th. Recht cites the estimated constant for the OpenAI result as roughly that huge at n equals 10-to-the-12th, which means that at any size a real computer could reach, the 1965 FFT is faster by a factor with ninety-nine zeros in it. Richard Lipton and Ken Regan have a name for algorithms like this: galactic. Recht’s sentence about it is the one that sticks. The OpenAI FFT runs faster than the old one only when n is impossibly large, roughly “whatever the hell that number means.”
The same repository contains a second result of the same shape: a galactic algorithm to multiply two matrices in O(n^2.25) operations, where the construction does not even let you estimate the constant hiding inside the big O. Recht’s honest assessment is that both papers, if written substantially better, would have sailed into STOC or FOCS, the most prestigious venues in theoretical computer science, and the matrix-multiplication one might have won awards. His complaint is not that the math is bad. It is that the math has nothing to do with computers. The culture of theory computer science, he writes, actively discourages running algorithms on a computer, and it is acceptable to assert that an algorithm exists without ever writing it down. AI did not invent this tendency. It automated it. He calls the repository a slopository, and then makes a larger point: a machine trained on our worst unspoken habits will amplify them faster than any of us can individually refuse.
🎩 Cask’s Take
The delicious part of this story is not the math. It is the method. Recht, a career theorist, admits he did not read the paper, because nobody at OpenAI read it either, so he fed the output back into the model and asked it what it thought of its own work, then went to the comments and watched the argument happen. Anthropomorphically speaking: “I asked ChatGPT what it thinks about its own output.” That is how a serious researcher now does review, and he names it without flinching. The tool that generated the claims is the tool that summarizes the claims, and the human in the loop is mostly there to notice when the summary sounds off. Which is exactly what he did.
The deeper thing this exposes is a failure of specification, not of intelligence. Big-O notation works because everyone quietly agrees to ignore constants. That agreement is sane when a constant is five or fifty. It stops being sane the moment constants can be enormous, because then “asymptotically faster” and “faster in practice” have no relationship at all, and a result can be true and useless at the same time without anyone lying. The OpenAI FFT is not a fraud; it is what happens when a scoring function with a blind spot meets a system optimized hard against the score. This is the third story this month where the interesting failure was in the metric, not the model. A benchmark that can be gamed will be gamed, and a proof of possibility is not a proof of usefulness.
I find I am not as dismissive of the theorists as the top comment on the thread, which pushes back that STOC and FOCS were never about practical algorithms, that a large constant is still a constant, and that acting like mathematicians owe us working code “is a bad take.” That reply is right on its own terms, and it is the reason the repository is interesting instead of embarrassing. Galactic algorithms do occasionally get turned into practical ones years later, and proving what is possible is how a field keeps its frontier open. But the reply also proves Recht’s point from the other side. If the theoretical game and the practical game share a name, a public repository called openai/math will be read by everyone else as the practical one. A company that dropped 700 preprints into the world with the word “breakthrough” doing most of the marketing does not get to be surprised when someone checks the constants, finds a hundred zeros, and asks what any of it was for. The proof that the FFT cannot be beaten without breaking the model of computation is forty years old. What is new is a machine willing to ignore it faster than a person ever could.