Browse › Theoretical computer science › 130 Exact Fourier transforms below $n\log n$
Finite tensor savings and exact Fourier circuits
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues (1 open) · Source on GitHub
Abstract
We construct exact nonuniform Fourier circuits of size $o(n\log n)$ along an unbounded sequence of lengths, counting every addition, subtraction, and scalar multiplication. This refutes the $\Omega(n\log n)$ lower bound in the unrestricted complex linear-circuit model. The construction uses a finite tensor saving: a tensor power of some invertible nonmonomial complex matrix can be computed with fewer matrix calls than the standard tensor-axis algorithm on the same coordinates, when invertible monomial maps are allowed freely between calls.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Comments and discussion
- 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 unit-cost coefficient model. [family-level]
Formalization
- OpenAI math release, Lean scope note for family 130 (lean/docs/130.md). The comparator
ExactFourier.leanformalizes this paper's Theorem 1.1: for every c > 0 and N_0 ≥ 2, some n ≥ N_0 has an exact DFT circuit with fewer than c n log_2 n gates, with no all-length, bounded-coefficient, conditioning or bit-complexity claim; the synthesis appendix is excluded. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Josh Alman, Kronecker Products, Low-Depth Circuits, and Matrix Rigidity (arXiv:2102.11992, STOC 2021). Gives circuits for Kronecker powers of fixed-size matrices, including Walsh–Hadamard circuits with large coefficients that sidestep bounded-coefficient lower bounds; relevant to the paper's discussion of tensor-power circuits (the bibliography cites only Alman–Li 2025 on this theme).
- 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 point that its circuits allow arbitrary intermediate conditioning (the bibliography cites 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 restrictions on the algorithm's graph; relevant to the paper's survey of lower bounds proved under restrictions on the algorithm.
- 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 argument that Theorem 1.1 avoids by allowing unbounded coefficients.
Digests and expositions
- Perplexity / Orply, Exact Fourier Cost Has Vanishing Normalized Growth on a Subsequence (Orply, 2026-10-11). An AI-assisted rendering summarizing the paper's nonuniform circuit model, finite tensor saving, width-preserving Fourier transfer and price-function contradiction. [AI-generated per source]
News and blogs
- Peter Hall and Joseph Howlett, The most exciting claims from OpenAI's heap of new proofs (Scientific American, 2026-10-08). Has a short section on paper 130's sub-n log n Fourier result, described mainly through the uniform (log n)^(1−10^−13) bound. [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 130
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Finite-tensor-savings-and-exact-Fourier-circuits-September-25-2026,
author = {{OpenAI}},
title = {{Finite tensor savings and exact Fourier circuits}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Finite-tensor-savings-and-exact-Fourier-circuits-September-25-2026/main.pdf}{OAI:Finite-tensor-savings-and-exact-Fourier-circuits-September-25-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/130.md. The Lean statements have not been checked by people against the paper's claims.
Family 130: Exact Fourier transforms below $n\log n$
Gives a deterministic length-n discrete Fourier transform algorithm using $O(n(\log n)^{1-\delta})$ operations for every n, with explicit $\delta=10^{-13}$. The model uses exact complex arithmetic, unrestricted coefficients and a supplied root of unity, and counts scalar preparation and logarithmic-word indexing.
Other papers in this family:
- An explicit power saving for the exact discrete Fourier transform · September 25, 2026