An explicit power saving for the exact discrete Fourier transform

Follow-up works

• Ryan Shea et al., Finite Network Improvements for the Exact Discrete Fourier Transform (GitHub manuscript, selected result recorded 2026-10-12). Uses this paper's model, local Fourier compiler and all-length reduction with credited community networks, and reports an all-length exponent saving of $\delta=0.0012331685$; independent human review is described as pending. [AI-generated per source]
• eumemic, Exact DFT with a 4.856·10⁻⁴ power saving in the logarithm (GitHub repository, accessed 2026-10-21). Keeps this paper's exact complex-arithmetic model and framework, swaps in a batched recursion and a community "paired-cube" network from CrocSwap/integer-mult-bounds, and claims θ = 1 − 607/1250000; the README says the proof is on paper with an exact finite certificate and is not formally verified. [AI-generated per source]
• Claude (Anthropic), Grouped recursion and colour registers: an improved exponent for the exact power-saving DFT (GitHub manuscript, 2026-10-08). The manuscript claims an all-length bound $O(n(\log n)^{1-3.2\cdot10^{-6}})$ in the original exact-arithmetic model through grouped recursive calls and shared auxiliary registers. [AI-generated per source]
• Oleksandr Pylypenko, An independent check of the local Fourier compiler in OpenAI's preprint "An explicit power saving for the exact discrete Fourier transform" (Zenodo preprint, DOI 10.5281/zenodo.23375871, 2026-10-14). Checks the Newton–Toeplitz local compiler of Section 3 exactly in cyclotomic fields and over F_p, reports strong floating-point instability, and says it neither confirms nor refutes the main theorem; code and data are at cyberdid/fft-power-saving-verification.
• spele1100, exact-dft: Exact DFT over cyclotomic fields (GitHub repository, accessed 2026-10-21). An exact-arithmetic implementation of this paper's components (local compiler, sector packing, tensor network budget, all-length driver); it reproduces the paper's constants W* = 2^71 and θ at h = 100 but not the asymptotic saving at small sizes.
• Swapnil Jain, mobius-x1: GF(2) Möbius / zeta transform in o(N log N) XOR gates (GitHub repository, accessed 2026-10-21). Credits this paper for its eight-row network, stages and fibre-batching recurrence, which it re-proves in a GF(2) setting to claim an o(N log N) XOR-circuit bound for the Möbius transform; the repository says it has been checked only by AI agents. [AI-generated per source]
• Ryan Shea (@ryaneshea), post on X (2026-10-08). Announces the Shea et al. research draft on Problem #130 with an all-length bound $T(n)=O(n(\log n)^{1-\delta})$, $\delta=7.3\times10^{-5}$; a follow-up post (2026-10-10) reports an updated $\delta=0.0007547360$.
• Eumemic (@dysmemic), post on X (2026-10-09). Says finite networks built by the community effort on the integer multiplication result also apply to this paper's algorithm, "raising its saving from 2.1·10⁻¹³ to 4.856·10⁻⁴ in the log exponent."
• Oleksandr Pylypenko (@Oleksan35109348), post on X (2026-10-14). Announces the independent test of the local Fourier compiler, reporting exact correctness at selected sizes but float64 relative error up to 8×10²³ at r=64, and states "This does NOT refute the theorem."

Comments and discussion

• Ben Recht, Faster Fourier Transforms (arg min blog, 2026-10-12). A critical post arguing the algorithm is "galactic" because of hidden constants and a unit-cost exact-arithmetic model that does not match real computers; the author discloses that he used ChatGPT to extract information rather than reading the manuscript.
• Hacker News discussion, A look at the math that OpenAI claims computes faster Fourier transforms (HN item 50065932, 2026-10-13). Thread on Recht's post, mostly about the unit-cost arithmetic model, coefficient growth, impractical constants and Morgenstern's bounded-coefficient bound.
• Scott Aaronson, The Mathocalypse (Shtetl-Optimized, October 2026). Lists the sub-n log n FFT among the release's TCS results, describing it as "breaking a barrier that had stood since the 1960s"; in the comments, b_jonas discusses the computational model. [family-level]
• Keith Adler (@keithadler), post on X (2026-10-08). A reply reviewing Ryan Shea's draft that transfers Jain's round-six network into this paper's model ($\delta=7.3\times10^{-5}$), using Lean Studio and Claude; the author writes "I tried to break it. I couldn't" and lists what held and what to tighten.

Formalization

• OpenAI math release, Lean scope note for family 130 (lean/docs/130.md). The comparator UniformFourier.lean formalizes this paper's uniform statement: exact DFT and convolution at every length in O(n(log n)^(1−10^−13)) work, with a supplied root and charged scalar preparation; the synthesis appendix is excluded. [family-level]
• Ryan Shea and credited contributors, fourier-transform-below-nlogn (GitHub repository, selected result recorded 2026-10-12). Reports local Lean, nanoda and comparator checks for its $\delta=0.0012331685$ all-length DFT and convolution statements, distinguishing them from pending leaderboard verification and human review. [AI-generated per source]
• danadran01 repository, An improved exponent for the exact power-saving DFT (formally verified) (GitHub, accompanying manuscript dated 2026-10-08). The repository supplies a Lean extension for the claimed $3.2\cdot10^{-6}$ saving, stating that the original DFT program and time-bound definitions are unchanged and providing build commands and an axiom audit. [AI-generated per source]

Possibly relevant literature (found by the agent, not checked)

• Nir Ailon, Tighter Fourier Transform Complexity Tradeoffs (arXiv:1404.1741, 2014–2015). Shows that speeding up the FFT by a factor b forces Ω(n) ill-conditioned intermediate steps, which bears on the paper's statement that it makes no conditioning or numerical-stability claim (the bibliography cites Ailon's arXiv:1305.4745 and arXiv:1403.1307, not this one).
• Christos H. Papadimitriou, Optimality of the fast Fourier transform (J. ACM 26(1):95–102, 1979). A classical optimality result for FFT addition counts under assumptions on the algorithm's graph; relevant to the introduction's point that n log n lower bounds depend on the permitted operations.
• Pavel Pudlák, A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits (ECCC TR98-042, 1998). Gives determinant-based lower bounds for bounded-coefficient linear circuits, extending the Morgenstern-type bounds that the paper says its unrestricted-coefficient model sidesteps.

Digests and expositions

• Franklin Baldo, Fourier below n log n: an interactive laboratory (blog, 2026-10-10). Illustrates the claimed exponent saving and chirp reduction, explicitly distinguishing its conventional FFT and quadratic chirp demonstrations from an implementation of the paper's tensor network.

News and blogs

• John D. Cook, Faster Fourier Transform (blog, 2026-10-07). A short post introducing this paper's O(n(log n)^(1−ε)) bound with ε = 10^−13 as theoretically significant but "of absolutely no practical value, for now."
• braindetox.kr, OpenAI FFT Preprint: 10^-13 Exponent Saving vs Real Speed (2026-10-14). An article contrasting this paper's stated model and caveats with the Cook and Recht posts; it notes that the 10^100 constant estimate comes from Recht's chatbot query, not from the preprint.
• Faizan, OpenAI Faster Fourier Transform: What It Means for Developers (DEV Community, 2026-10-19). A practitioner-oriented post on result 130 based on the Lean scope note, which separates the subsequential and uniform results and argues there is no demonstrated practical speedup. [family-level]
• Nil (@Nil053), post on X (2026-10-11). Claims a leaderboard-leading bound $O(n\log^{1-\kappa} n)$ for the exact DFT with κ = 0.0010221, up from 0.000876, citing a Lean proof and a method of Opus 5.5 orchestrating Codex and Opus agents. [AI-generated per source]