---
id: "lib-2026-10-12-faster-fourier-transforms"
type: "library"
title: "Faster Fourier Transforms"
lang: "EN"
org: "Ben Recht (arg min)"
source_type: "Practitioner post"
date: "2026-10-12"
week: "2026-W42"
url: "https://nosov.ai/library/lib-2026-10-12-faster-fourier-transforms/"
original_url: "https://www.argmin.net/p/faster-fourier-transforms"
tier: "B"
tier_name: "Useful, limited"
tier_reason: "A critique by Ben Recht, a prominent Berkeley machine-learning theorist, of OpenAI's claimed faster FFT; expert and specific, but an essay that argues from the cost model rather than new evidence."
summary_basis: "full-text"
original_minutes: "9"
tags: ["ai for math", "claims scrutiny"]
---

# Faster Fourier Transforms

Tier B (Useful, limited): A critique by Ben Recht, a prominent Berkeley machine-learning theorist, of OpenAI's claimed faster FFT; expert and specific, but an essay that argues from the cost model rather than new evidence.

Summary based on the full text.

## In short

Ben Recht's arg min post (12 October 2026) examines one result in OpenAI's recent release of AI-produced mathematics: an algorithm claimed to compute Fourier transforms faster than the standard FFT. His argument is that the gain exists only on paper. The hidden constant is astronomically large and the proof assumes a computer that can multiply arbitrarily large complex numbers in one step. He uses it to attack a theory culture that rewards asymptotic results with no link to real machines.

## Key numbers

- 10^100: estimated hidden constant C in OpenAI's FFT algorithm when N = 10^12
- 5 n log2 n: arithmetic operations the standard Cooley-Tukey FFT needs, the bound the new result claims to beat
- 20-fold: speedup of the classic FFT over the naive transform at n = 1,000 (10,000-fold at one million)
- 1973: year Morgenstern proved no FFT beats 1/2 n log n with bounded coefficients

## What it reports

- The classic FFT needs fewer than 5 n log2 n operations; the new result is asymptotically a tiny bit smaller in the log term.
- The estimated constant C is 10^100 at N = 10^12, so even at n = 10^100 the standard FFT would be 10^99 times faster. Recht calls it a "galactic algorithm".
- The model assumes exact complex arithmetic with numbers whose magnitude grows superpolynomially with n; stored as bits, memory would be effectively exponential in input length.
- Earlier lower bounds already showed you need such unrealistic models: Morgenstern (1973) with bounded coefficients, and Ailon on numerical stability.
- A companion result, matrix multiplication in O(n^2.25), gives no way to estimate its constant either.
- Recht admits he did not read the paper closely and used ChatGPT to extract its claims.

## How they got it

An argument from definitions and prior lower bounds, with a short tutorial on the FFT and big-O notation. No code, benchmarks or independent proof check.

## Limits

- Recht summarises the paper through a chatbot session by his own account, so the details of the claim are second-hand.
- He does not dispute that the theorem may be correct; the critique is about relevance, not validity.
- Polemical tone; the broader claims about theoretical computer science are opinion.

## Why it matters for companies

Labs now announce AI-generated "breakthroughs" in bulk, and headlines rarely check whether a result changes anything you could run. This post is a template for that check: ask what model of computation the claim assumes and how large the hidden constants are. Treat vendor claims of AI-discovered algorithms as unproven for practical use until someone shows a speedup on real hardware.

Original: https://www.argmin.net/p/faster-fourier-transforms