OpenAI's Claimed Faster Fourier Transform Is a 'Galactic Algorithm' With a 10^100 Constant

OpenAI's mathematics paper dump includes a paper — main.pdf — that claims a Fourier transform algorithm with a smaller log(n) factor than the classic Cooley-Tukey FFT. An analysis published on argmin.net argues the result is a "galactic algorithm": it is asymptotically faster in big-O terms, but its hidden constant is estimated at 10^100, and it assumes a model of computation — exact complex arithmetic on numbers whose magnitudes grow superpolynomially with n — that no physical computer implements. The Hacker News discussion of that analysis (240 points, 159 comments) split sharply between readers who found the critique devastating and readers who argued it is a rant against theoretical computer science rather than a refutation of the paper.

What OpenAI claimed

The claim at issue is narrow. The argmin.net post describes OpenAI's main.pdf as asserting a Fourier transform whose log(n) term is "a teeny tiny bit smaller than in the standard FFT." In big-O notation, that makes the new algorithm asymptotically faster than Cooley-Tukey, because a smaller logarithmic factor is still a smaller growth rate.

The post's author states plainly that he did not read the paper, and offers a reason:

Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I? I did what every other mathematician in the world does with AI slop mathematics: I fed it back into the slop machine and ran an information retrieval session with a chatbot interface to extract salient facts. Anthropomorphically speaking: I asked ChatGPT what it thinks about its own output. This is how we do mathematical research now. What a world.

Why the FFT's speed limit is a real open problem

The Fast Fourier Transform computes the frequency content of a length-n signal in far fewer than the n^2 arithmetic operations a naive discrete Fourier transform requires. The Cooley-Tukey algorithm, published in 1965, computes a length-n Fourier transform in fewer than 5n log2(n) arithmetic operations by recursively shuffling the input, computing two length-n/2 transforms, and recombining the outputs with linear work. (The argmin.net post notes that Wikipedia credits the same idea to Gauss in 1805, calling proper credit assignment "a perennial problem in academia.")

The practical payoff of that recursion is large. For n = 1,000, the FFT is roughly a 20-fold speedup over the naive transform; for n = 1,000,000, the speedup is about 10,000-fold.

The theoretical question is how much further the speedup can go. Any algorithm needs at least n operations just to write down its input, and the FFT is 5 log2(n) times slower than that floor — a factor of 200 when n is a trillion. Reducing that prefactor is the open problem OpenAI's paper claims to address.

The hidden constant: 10^100

Big-O notation discards constants by definition: T(n) = O(F(n)) means there exists an integer N and a constant C such that the running time is bounded by C times F(n) for all n beyond N. The argmin.net post argues this is exactly where the OpenAI result collapses in practice.

The post cites an estimated constant of C = 10^100 at N = 10^12 for the new algorithm, and concludes that "even when n=10^100, the venerable Cooley-Tukey-Gauss FFT would be 10^99 times faster." The post presents a crossover equation for the n at which the new algorithm would actually win, then dismisses it: "whatever the hell that number means."

The post borrows the term "galactic algorithms" from Richard Lipton and Ken Regan for algorithms whose hidden constants are unfathomably large. It notes that O(n) does not mean 50n — it could mean 10^80 n, roughly the number of atoms in the known universe, and still be called linear time.

The computation model problem: exact complex arithmetic

The deeper objection is not the constant but the machine the algorithm assumes. The argmin.net post states that OpenAI's model "uses exact complex arithmetic," meaning it assumes complex numbers can be stored and multiplied at arbitrary precision in a single operation. The algorithm requires multiplying complex numbers whose magnitudes grow superpolynomially with n, so storing them as bits would make memory effectively exponential in the input length.

The post's conclusion: "So even if this theorem in main.pdf is 'true' (no one knows, and I don't care), it's not actually solving the problem we set out to solve when looking for a faster FFT."

Lower bounds that already ruled this out

The argmin.net post argues the result should not have been surprising, because prior work already bounded how fast a Fourier transform can be under realistic arithmetic. In 1973, Jacques Morgenstern proved that a Fourier transform cannot be computed faster than ½ n log n if the complex coefficients used in the computation have bounded magnitude. In 2013 and 2014, Nir Ailon showed that an FFT faster than n log n cannot be achieved without severe numerical instabilities.

The post's framing is that both results were set aside as "too restrictive," and that OpenAI's algorithm escapes them only by adopting a model of computation that no real machine satisfies.

The same critique applies to the matrix multiplication result

The argmin.net post extends the argument to another result in the same OpenAI release: a galactic algorithm for multiplying two matrices in O(n^2.25) operations. The post's footnote states that the construction gives, for every epsilon greater than 0, a constant C such that T(n) <= n^(2.25 + epsilon + C/log(n)), and that no query to an OpenAI model produced a quantitative estimate of C.

The post concedes that, if written substantially better, these papers would have been accepted at STOC or FOCS, and that the matrix multiplication paper would likely have won awards. Its point is that this says something about the field's standards rather than about computers: "But neither of these has anything to do with computers!"

The post's summary judgment is blunt:

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

It also draws an analogy between the situation and setting automated agents at impossible problems, linking to a Wikipedia article titled "OpenAI rogue agent breach of Hugging Face."

The counterargument: theoretical computer science is mathematics, not engineering

The most common objection in the Hacker News thread is that the argmin.net post attacks theoretical computer science for being theoretical. One commenter argues that STOC, FOCS, and SODA are not venues for practical algorithms, and that work aimed at practical performance goes to ESA, ALENEX, VLDB, or SIGMOD instead:

I don't think it's fair to just shit on theory because they don't do experiments---they're mathematicians, and it is fine to have absurd constants in your big-O as long as they are constants.

Another commenter points out that galactic results are not new and are not unique to AI, citing the 2019 Harvey–van der Hoeven result showing integer multiplication can be done in O(n log n) with galactic overhead and no applications, and the textbook "median of medians" algorithm for worst-case linear-time selection. The same commenter invokes the Dijkstra line that "Computer Science Is Not About Computers, Any More Than Astronomy Is About Telescopes," and notes that undecidability results such as Wang tiling are core computer science with no direct hardware connection.

A third commenter frames the post as a rant that could have been written without mentioning AI at all: "He just really doesn't like TCS. That's fine, it's really a part of mathematics not science, but it's silly to dismiss a field with 'theoretical' in its name for being impractical." Another writes that the article "has basically nothing to do with the OpenAI paper" and adds, "Wake me up when someone has understood the proof."

One commenter defends the field's own vocabulary, noting that theoretical computer science already distinguishes galactic algorithms from "feasible" ones such as Karatsuba's or Strassen's, which produce measurable speedups on practical inputs.

What the Hacker News discussion added on the technical side

Several commenters focused on the exact-arithmetic assumption rather than the rhetoric. One asked whether "exact complex arithmetic" or "exact real arithmetic" is a common premise in this literature, saying that as an outsider they had assumed the relevant models were Turing-equivalent — later clarifying they meant universal register machines operating on integers rather than directly on real numbers.

Another commenter offered a mechanical explanation of how the claimed speedup is obtained: the algorithm exploits the algorithmic similarity between the discrete Fourier transform and multiplication to translate part of the DFT work into multiplication work, which costs O(1) in the exact-arithmetic model. The cost is that the magnitudes of the multiplied numbers grow superpolynomially with n — the commenter's phrasing is that the algorithm is "stuffing its work in there and using it as an oracle."

A commenter raised the same point as a direct challenge to the complexity analysis: if the algorithm requires multiplying complex numbers whose magnitudes grow superpolynomially with n, "doesn't that completely invalidate the big-O analysis!?"

One commenter linked to an ongoing effort to tighten the relevant bound, citing a value of kappa around 0.001635527380375392 in the CrocSwap integer-mult-bounds GitHub repository.

A separate thread compared the situation to AI systems that answer the wrong question well, linking to a prior Hacker News discussion titled "Navier-Stokes Lost in Translation" and invoking Deep Thought from The Hitchhiker's Guide to the Galaxy, which produced the answer before anyone knew the question.

What would settle the dispute

Both sides of the Hacker News thread converge on the same gap: no one in the discussion claims to have verified the proof. The argmin.net post explicitly declines to read the paper, and the commenters who defend theoretical computer science argue that the correct response is to find an actual error, a missing attribution, or another concrete defect rather than to object that the result is impractical.

The substantive technical questions left open by the exchange are narrower than the argument about the field. They are: whether the exact-complex-arithmetic model is standard for this class of result or an unusual choice; whether the superpolynomial growth of intermediate magnitudes is inherent to the construction or an artifact of how it was written down; and whether the estimated constant of 10^100 can be reduced. Until one of those is answered, the claim of a faster Fourier transform remains, as the argmin.net post puts it, an asymptotic statement about a machine that does not exist.