Does the exact discrete Fourier transform require order n log n operations in unrestricted linear circuits?

The fast Fourier transform computes $F_n=(\zeta_n^{jk})$ with $O(n\log n)$ arithmetic operations, and no asymptotically faster method was known. Matching lower bounds were proved only in restricted models: Morgenstern for linear circuits with bounded coefficients, Ailon for unitary two-coordinate gates or bounded intermediate conditioning. In the unrestricted model, a linear circuit uses gates $u+v$ , $u-v$ and $\lambda u$ with arbitrary fixed complex $\lambda$ , each costing one, and must output $F_nx$ exactly for every $x$ . Is the minimum size $L(n)$ of such a circuit at least $cn\log n$ for some $c>0$ and all large $n$ , or can the Fourier transform be computed exactly with $o(n\log n)$ operations?

Result: Disproved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Construction
Field: Algebraic complexity; arithmetic circuits for the Fourier transform
Posed by: Long-standing open question in algebraic complexity; discussed by Ailon (2013) and Alman and Rao (2023)
Year posed: —
Years open: —
Solved: 2026-09-25
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 45 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Principal (Theorem 1.1): in exact complex linear circuits with arbitrary prechosen coefficients, $\liminf_n L(n)/(n\log_2 n)=0$ , along lengths that are products of distinct primes, so the unrestricted $\Omega(n\log n)$ lower bound is false. Companion (Theorem 1.1): one deterministic algorithm computes $F_nx$ at every length in $O(n(\log n)^{\theta}(\log\log n)^{4-\theta})$ operations with $\theta<1-10^{-13}$ , counting scalar preparation and indexing, given one specified root of unity. Neither result concerns bounded coefficients (where Morgenstern's bound stands), numerical stability, bit complexity or finite fields, and the constants are astronomically large.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The family has two manuscripts dated September 25, 2026: 'Finite tensor savings and exact Fourier circuits' (this entry's principal, nonuniform circuits along a subsequence) and 'An explicit power saving for the exact discrete Fourier transform' (a uniform algorithm at every length). The explicit-power-saving paper reuses a phase network from another release manuscript on integer multiplication.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 of the principal manuscript was read against the question; it states $\liminf L(n)/(n\log_2 n)=0$ in the unrestricted model, refuting the lower bound. lean/formalization.yaml lists comparator ExactFourier, declaration OAI.ExactFourier.main_theorem. The statement was read here: for every $c>0$ and $N_0\ge2$ there are $n\ge N_0$ and a circuit (a DAG of add, subtract and scale-by-any-complex gates, outputs naming any available value) computing the unnormalised $F_n$ exactly with fewer than $cn\log_2 n$ gates. That is the headline claim. Not rebuilt here. Permitted axioms: propext, Quot.sound, Classical.choice. The model allows unbounded coefficients and conditioning, as the paper stresses; nothing is claimed for bit complexity or floating-point FFTs. The companion's every-length $O(n(\log n)^{1-10^{-13}})$ algorithm is not formalised.

Does the exact discrete Fourier transform require order n log n operations in unrestricted linear circuits?

What was actually shown

What the AI did

Verification

Sources

Discussion