VibeMathedMath problems solved with AI

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

The fast Fourier transform computes Fn=(ζnjk)F_n=(\zeta_n^{jk}) with O(nlog⁡n)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+vu+v, u−vu-v and λu\lambda u with arbitrary fixed complex λ\lambda, each costing one, and must output FnxF_nx exactly for every xx. Is the minimum size L(n)L(n) of such a circuit at least cnlog⁡ncn\log n for some c>0c>0 and all large nn, or can the Fourier transform be computed exactly with o(nlog⁡n)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 fd4aeeb
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, lim inf⁡nL(n)/(nlog⁡2n)=0\liminf_n L(n)/(n\log_2 n)=0, along lengths that are products of distinct primes, so the unrestricted Ω(nlog⁡n)\Omega(n\log n) lower bound is false. Companion (Theorem 1.1): one deterministic algorithm computes FnxF_nx at every length in O(n(log⁡n)θ(log⁡log⁡n)4−θ)O(n(\log n)^{\theta}(\log\log n)^{4-\theta}) operations with θ<1−10−13\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 lim inf⁡L(n)/(nlog⁡2n)=0\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>0c>0 and N0≥2N_0\ge2 there are n≥N0n\ge N_0 and a circuit (a DAG of add, subtract and scale-by-any-complex gates) computing the unnormalised FnF_n exactly with fewer than cnlog⁡2ncn\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; nothing is claimed for bit complexity or floating-point FFTs. The 7 October 2026 update added the companion's Comparator challenge UniformFourier (OAI.PowerSaving.transform_main and convolution_main, solution module OAI.Computability.FourierTransform.Main); read here, it states one fixed exact-complex RAM program computing the DFT (and one for convolution) at every positive length with work O(n(log⁡n)1−10−13)=o(nlog⁡n)O(n(\log n)^{1-10^{-13}})=o(n\log n), given a supplied root of unity.

Sources

Changelog2 changes
  • Rasmus Lindahlchanged Verification note from “No independent mathematician has checked this yet. Checked here: Theorem 1.1 of the princi…” to “No independent mathematician has checked this yet. Checked here: Theorem 1.1 of the princi…”, also collectionVersion
  • Rasmus Lindahladded this entry

Discussion