OpenAI's faster Fourier transform claim is a galactic algorithm, analysis finds

What the analysis found

A technical write-up on argmin.net, which reached the front page of Hacker News on 12 October 2026, examines a claim from a recent batch of OpenAI mathematics papers: a Fourier transform faster than the classical one. The author's verdict is that the result is marginally better asymptotically on paper but practically worthless, because its hidden constants are astronomical and its model of computation bears no resemblance to any machine we can build.

The speed limit being chased

The post opens with a short primer. A Fourier transform measures how much energy a signal carries in each frequency band, and computing that content naively across all n frequencies appears to cost n^2 arithmetic operations. The 1965 algorithm by James Cooley and John Tukey cuts this by splitting the problem: shuffle the input, run two transforms of half the length, then merge the results with a linear amount of work. Applied recursively about log2(n) times, the whole transform finishes in fewer than 5 n log2(n) operations. According to the post, that is roughly a 20-fold saving when n is 1,000 and about 10,000-fold when n is a million.

Since at least n operations are needed simply to write the output down, the open question is whether the logarithmic overhead, a factor near 200 when n is a trillion, can be reduced. That is the question OpenAI's paper claims to answer.

What OpenAI actually claimed

According to the analysis, the claim appears in a paper filed under the plain name main.pdf, part of a large collection of mathematics papers OpenAI released recently. Its headline bound trims the logarithmic term slightly relative to Cooley-Tukey, which makes it technically faster in the asymptotic sense. The author admits to not reading the paper in full, instead extracting the salient facts by querying a chatbot about its own organization's output, and quips that there is no reason to believe anyone at OpenAI read it closely either.

Galactic constants

The first problem the analysis identifies is the abuse of big-O notation. Big-O certifies growth rates while ignoring constants, so a supposedly linear-time algorithm might really cost 10^80 operations per element, or might only behave linearly for inputs larger than the number of atoms in the observable universe. Richard Lipton and Ken Regan coined the phrase galactic algorithms for exactly this category, the post notes. The estimated constant in OpenAI's bound is on the order of 10^100 with a threshold N of 10^12. By the author's arithmetic, even for inputs of size 10^100, the 1965 Cooley-Tukey FFT would still be about 10^99 times faster. The input size at which the new algorithm finally wins is not a number with any practical meaning.

A computer that does not exist

The second problem is the computational model. The paper assumes exact complex arithmetic, meaning numbers of arbitrary magnitude can be stored and multiplied in single operations. The algorithm's intermediate values grow superpolynomially with n, so representing them as bits would require memory effectively exponential in the input length. Machines with these capabilities do not exist, the author argues, so the theorem does not address the problem practitioners actually set out to solve.

This is also how the claim evades known impossibility results. In 1973, Jacques Morgenstern proved that no algorithm using bounded-magnitude coefficients can beat roughly one-half n log n. Decades later, Nir Ailon showed that going below n log n forces severe numerical instability. Earlier lower bounds like these were criticized as too restrictive; the new claim effectively prevails by discarding the restrictions entirely.

Why it matters

For anyone running signal-processing workloads, nothing changes: the classical FFT remains the fastest practical option, and the claimed advance offers no implementable path to beating it. More broadly, the episode is a warning about asymptotic claims quoted without constants, since a bound labeled linear can be meaningless for every input size the universe can hold. It also illustrates the review burden created when AI-assisted research is published in bulk, with outside experts reduced to feeding papers back into chatbots to triage them, as the author did here. The strongest defense of such work, attributed in the post to Lipton and Regan, is that galactic algorithms can seed searches for practical descendants, but the author knows of no case where that has actually happened and is skeptical it will in this one.