Exact Fourier transforms below n\log n

1 · The essentials

The discrete Fourier transform is a mathematical rule for turning a list of numbers into another list by taking particular weighted sums. These manuscripts describe ways to compute it exactly with fewer operations than the $n lo g n$ scale. The main manuscript gives a fixed, nonrandom procedure that works for every list length, with a bound of $O (n (lo g n)^{1 - 1 0^{- 13}})$ . The improvement in the exponent is explicit but extremely small. The count includes preparing the numbers used in the calculation and organizing the arrays, rather than treating those tasks as free. However, the result assumes exact calculations with complex numbers, allows unrestricted numerical weights, and requires a specified root used by the transform to be supplied. Both manuscripts are marked as Lean-formalized; the results concern this particular counting model, not a stated speed improvement on ordinary computers.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine a recipe that combines ingredients through many measured mixing steps, and a revised recipe that needs fewer steps. Here the measures must be perfectly exact, any numerical mixing weight is allowed, and a required special measure is supplied at the outset—so fewer counted steps do not by themselves establish a faster everyday kitchen procedure.

Why it matters

The main result gives an explicit improvement over the $n lo g n$ operation scale at every length in the stated exact-arithmetic model. The companion result refutes an $Ω (n lo g n)$ lower bound for unrestricted complex linear circuits. Together, they make the permissions of the computational model central to interpreting the result.

2 · Going further

The problem is to compute a length- $n$ discrete Fourier transform exactly. The main manuscript gives a deterministic algorithm with operation count $O (n (lo g n)^{1 - δ})$ , where $δ = 1 0^{- 13}$ , for every $n$ . Its assumptions are exact complex arithmetic, unrestricted coefficients, specified Fourier roots, and unit-cost indexing with logarithmic-size words. Scalar preparation and array organization are included in the count.

The companion manuscript addresses exact nonuniform Fourier circuits: separate circuits can be chosen for different lengths. It constructs circuits of size $o (n lo g n)$ along an unbounded sequence of lengths, counting every addition, subtraction, and scalar multiplication. In this unrestricted complex linear-circuit model, that result refutes an $Ω (n lo g n)$ lower bound; unlike the main result, its stated guarantee is along a sequence rather than at every length.

The construction idea described in the companion abstract is a finite tensor saving. For some invertible nonmonomial complex matrix, a tensor power can be computed with fewer matrix calls than the standard tensor-axis algorithm on the same coordinates, provided invertible monomial maps are freely allowed between calls. Monomial maps permute coordinates and multiply them by nonzero scalars. This intermediate matrix-call comparison should be distinguished from the final circuit count, which counts all the stated arithmetic operations.

The two manuscripts therefore present related savings at different levels: a tensor-based circuit construction along selected lengths, and an explicit deterministic algorithm for all lengths with preparation and organization costs included. The supplied abstracts do not explain the detailed passage between these levels. Both manuscripts are labeled Lean-formalized, but the supplied text does not identify the precise formalization boundaries for every supporting claim.

Useful notions

Complex numbers and exact arithmetic
Weighted sums and matrix multiplication
Asymptotic operation counts
Linear circuits
Tensor powers of matrices

What was known before / what is new

Before

The source uses $n lo g n$ as the comparison scale for Fourier computation. It also identifies a standard tensor-axis algorithm as the baseline for the finite matrix-call saving. It provides no further historical account of earlier algorithms or lower-bound results.

New

The main manuscript gives an explicit exponent saving of $1 0^{- 13}$ in a deterministic exact Fourier algorithm for every length, while counting scalar preparation and array organization. The companion manuscript constructs exact nonuniform circuits of size $o (n lo g n)$ along an unbounded sequence of lengths. Its stated mechanism is a finite tensor saving, and its stated consequence is the failure of the $Ω (n lo g n)$ lower bound in the unrestricted complex linear-circuit model.

Limits and assumptions

The all-length bound assumes exact complex arithmetic, unrestricted coefficients, supplied Fourier roots, and unit-cost logarithmic-size indexing. The companion circuit result is nonuniform and applies along an unbounded sequence of lengths; its tensor-saving comparison allows invertible monomial maps freely between matrix calls. The source does not establish a finite-precision implementation or a practical running-time advantage. Both manuscripts are labeled Lean-formalized, including the main result, but the supplied abstracts do not specify exactly which auxiliary claims are covered. They also do not state what questions remain open.

Mini glossary

Discrete Fourier transform: A transformation of a finite list into weighted sums whose weights are powers of a specified Fourier root.
Exact complex arithmetic: A model in which operations on complex numbers are performed exactly rather than through rounded approximations.
Nonuniform linear circuit: A prescribed arrangement of additions, subtractions, and scalar multiplications that may be chosen separately for each input length.
Tensor power: A matrix construction formed by repeatedly taking the tensor product of a matrix with itself.
Invertible monomial map: A linear map that permutes coordinates and scales each coordinate by a nonzero number.
$o (n lo g n)$: An operation count whose ratio to $n lo g n$ tends to zero along the lengths under consideration.

Keywords : Discrete Fourier transform · Exact arithmetic · Tensor savings

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Gives a deterministic length-n discrete Fourier transform algorithm using $O (n (lo g n)^{1 - δ})$ operations for every n, with explicit $δ = 1 0^{- 13}$ . The model uses exact complex arithmetic, unrestricted coefficients and a supplied root of unity, and counts scalar preparation and logarithmic-word indexing.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/130.md

Manuscripts in this family

★

An explicit power saving for the exact discrete Fourier transform

25/09/2026

Verified by Lean

We give a deterministic algorithm that computes the discrete Fourier transform at every length n in $O (n (lo g n)^{1 - 1 0^{- 13}})$ operations. The model uses exact complex arithmetic, unrestricted coefficients, specified Fourier roots, and unit-cost logarithmic-size indexing; scalar preparation and array organization are included.

PDF GitHub folder Lean formalization

Finite tensor savings and exact Fourier circuits

25/09/2026

Verified by Lean

We construct exact nonuniform Fourier circuits of size $o (n lo g n)$ along an unbounded sequence of lengths, counting every addition, subtraction, and scalar multiplication. This refutes the $Ω (n lo g 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.

PDF GitHub folder Lean formalization