Exact Fourier transforms below n log n: the role of the arithmetic model

← All digests

Family 130 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

The fast Fourier transform is famous for reducing a dense calculation from roughly $n^2$ operations to $n\log n$. Is that familiar scale unavoidable, or could exact Fourier computation use asymptotically fewer arithmetic operations?

The answer depends on what counts as an operation. A floating-point implementation must control precision and numerical error. An exact arithmetic model treats each operation on a complex number as one step, even if the number would require an enormous representation in ordinary bits. Restrictions on coefficients and intermediate values can therefore change the lower-bound question.

This family contains two manuscripts claiming a saving below $n\log n$ in unrestricted exact complex arithmetic. One gives a single deterministic algorithm at every input length, with a tiny explicit improvement in the logarithmic exponent. The other gives an independent existence argument for smaller exact circuits along an unbounded sequence of lengths.

These are arithmetic-complexity claims. They do not assert a faster stable floating-point FFT, nor do they identify a practical crossover point at which the new construction wins.

2. Background and essential definitions

For an input vector $x=(x_0,\ldots,x_{n-1})\in\mathbb C^n$, the unnormalized discrete Fourier transform is

$$y_k=\sum_{j=0}^{n-1}\zeta_n^{jk}x_j, \qquad \zeta_n=\exp(2\pi i/n), \quad 0\le k<n.$$

The matrix of this linear map is $F_n=(\zeta_n^{jk})$. The transform expresses the data in terms of discrete oscillatory patterns. Computing every sum independently takes quadratic work, while FFT factorizations reuse intermediate calculations.

A linear circuit builds outputs using additions, subtractions, and multiplication by input-independent constants. Each scalar multiplication counts; the constants themselves may be complex. “Nonuniform” means that a different circuit and different constants may be chosen for each length, without charging for the process that finds them.

A uniform algorithm is one finite procedure that works at every length and constructs its required schedule. M1 additionally charges the preparation of scalars and array indexing, subject to its supplied-root convention.

A tensor product, or Kronecker product, combines matrix actions on independent coordinate axes. If $A$ is $q\times q$, its $b$-fold tensor power acts on $q^b$ coordinates. Applying $A$ separately along each axis uses $bq^{b-1}$ calls. A strict finite saving over that count can become an asymptotic improvement if it survives recursive batching.

Finally, $o(n\log n)$ means that the operation count divided by $n\log n$ tends to zero in the stated limit. It says more than improving a fixed leading constant, but says nothing by itself about feasible input sizes.

3. Development history and previous partial results

Cooley and Tukey’s classical factorization organizes composite-length transforms into smaller transforms and diagonal multiplications. The Good–Thomas construction is particularly convenient for coprime factors: coordinate permutations expose a tensor-product structure without intervening twiddle factors. Bluestein’s chirp identity reduces arbitrary lengths to convolution, providing another route to the usual $O(n\log n)$ arithmetic bound. These primary works are listed in M1’s references.

Lower bounds at that scale come with important hypotheses. Morgenstern’s determinant argument restricts coefficient magnitudes. Ailon’s unitary-gate lower bound restricts the computation to two-coordinate unitary operations, while his conditioning-sensitive analysis measures how unstable intermediate transformations are allowed to become.

The new manuscripts permit unrestricted coefficients and intermediate values, so these restricted-model lower bounds do not automatically contradict their claims. Normalizing the Fourier transform also matters when comparing coefficient-restricted models, even though an unrestricted circuit can insert a final scaling at linear cost.

On the algorithmic side, Alman and Rao used matrix non-rigidity to improve leading constants for Fourier and Walsh–Hadamard transforms. Their 2023 work remains within the $n\log n$ scale for the Fourier result. A vanishing ratio to $n\log n$ requires a different kind of gain.

The present family’s proposed bridge is a finite tensor saving. M2 develops a general existence argument and transfers it to Fourier circuits. M1 supplies an explicit local construction and accounts for the work needed to turn it into an all-length algorithm. A related phase network also appears in the integer-multiplication family, whose tape and precision model is separate.

4. What the new manuscripts claim

An explicit algorithm for every length

M1 states that a single deterministic algorithm computes $F_nx$ exactly with cost

$$O\!\left(n(\log n)^\theta(\log\log n)^{4-\theta}\right), \qquad \theta=0.999999999999789\ldots<1.$$

The manuscript defines $\theta$ by exact fixed constants; the decimal only indicates the size of the saving. An asymptotic consequence is

$$O\!\left(n(\log n)^{1-10^{-13}}\right)=o(n\log n).$$

The model has unit-cost exact complex field operations and unit-cost operations on integer address words of $O(\log(n+2))$ bits. That word-size bound applies to addresses, not to the precision of complex registers.

One explicitly specified root of unity is supplied, with order $D_*<1024n^3$. Preparing the remaining scalars, constructing the schedule, and organizing the arrays are charged. The input-linear computation uses addition, subtraction, and multiplication by prepared scalars; division is used only in scalar preparation with nonzero denominators.

M1 also states the same asymptotic bound for exact complex convolution and polynomial multiplication, using Fourier transforms and pointwise products. Those pointwise products are general field multiplications, so this consequence is a bilinear algorithm rather than an input-linear circuit.

A separate nonuniform existence theorem

Let $L(n)$ be the minimum number of scalar gates in an unrestricted exact complex linear circuit for $F_n$. M2 claims

$$\liminf_{n\to\infty}\frac{L(n)}{n\log_2n}=0.$$

Equivalently, arbitrarily large lengths admit circuits beating any fixed positive multiple of $n\log n$. M2 allows arbitrary prechosen coefficients without charging their generation or description length. Its main theorem concerns an unbounded sequence of lengths, not an all-length uniform running time. M1 supplies the stronger all-length algorithm in its own explicitly stated model.

5. Why the advance matters

Provisional importance: 4/5. Fourier computation is a central benchmark for arithmetic complexity. A genuine asymptotic saving in the unrestricted model would clarify that the familiar FFT scale is not a universal lower bound on every exact linear computation.

The result’s interest lies partly in the model boundary. It would show why coefficient bounds, conditioning, and uniform preparation are substantive assumptions rather than technical decorations. The family treats several of these issues separately instead of equating all notions of a “faster FFT.”

The all-length theorem also includes organizational costs that can erase an arithmetic saving: moving data, preparing constants, and constructing schedules. Accounting for them strengthens the uniform statement within the chosen exact-arithmetic model.

The score does not treat the tiny exponent as a forecast of practical acceleration. Exact complex registers and unrestricted coefficients are idealizations, and the construction’s fixed constants are enormous. Numerical and bit-complexity improvements would need additional results.

6. The main idea

Amplify one finite saving

The standard tensor-axis algorithm repeats the same small matrix operation across many coordinate fibers. If one fixed tensor power can be computed with strictly fewer calls, the improved block can replace the standard block recursively.

A single saved fraction then compounds with tensor order. Instead of a cost proportional to the number of coordinates times the number of axes, the recurrence produces a smaller exponent in the axis count. Since tensor order is logarithmic in the total dimension, this becomes a power saving in $\log n$.

M1 uses a fixed two-coordinate complex phase operation and a large explicit network. A crucial bookkeeping requirement is that all physical coordinates, including temporary roles, receive the intended final transformation. Otherwise recursive reuse could silently demand fresh workspace and lose the gain.

Transfer the saving without widening the computation

Fourier matrices of small widths are factored into simple layers using interpolation and structured triangular matrices. The compiler must stay on exactly the original number of coordinates. Temporary computations borrow coordinates containing arbitrary values and restore them afterward.

The construction synchronizes these layers across many coprime factors. At a synchronized call position, the operation decomposes into sectors carrying tensor powers of the same small matrix. The sector widths add up to the full transform length, allowing the amplified saving to control the whole stage.

Indexing needs equal care. A naive pass through every axis for every coordinate could itself cost $n\log n$. M1 gives explicit packing and traversal rules with linear array work at the relevant stages. Suitable products of small primes provide working lengths, and chirp convolution reaches every requested length.

Why some finite saving must exist

M2 reaches the finite saving through a different route. Suppose no invertible nonmonomial matrix ever admitted such a saving. “Monomial” here means a permutation followed by nonzero diagonal scalings.

The manuscript combines finite program comparisons into a hypothetical price function for matrix calls. The absence of simultaneous savings forces this price to obey exact rules under tensor products, direct sums, elimination of coordinates, and certain algebraic substitutions.

It then constructs matrices whose price can be evaluated in two incompatible ways. One description forces a cost proportional to a parameter $d$ times the width; another yields roughly three quarters of that leading term, plus lower-order terms. For sufficiently large $d$, the two cannot agree. The manuscript concludes that the no-saving assumption fails.

This price function is an auxiliary contradiction device, not an independently asserted lower bound on all circuits. The final Fourier circuits still count every scalar multiplication; temporary conventions that allow free permutations and scalings in matrix-call comparisons do not make those operations free in the final gate count.

7. Scope, limitations, and open questions

The supplied Fourier root is an explicit resource. The algorithms do not claim that rational field operations alone can generate roots of arbitrarily large order. All other preparation is charged as specified in M1.

No coefficient-size bound, finite-precision guarantee, or numerical-stability theorem is supplied. Unrestricted intermediate values can behave very differently from stable floating-point calculations. The address-word assumption does not change that limitation.

M2’s nonuniform subsequence theorem and M1’s uniform all-length theorem should remain distinct. Their relationship explains the progression of ideas, but their costs and available primitives differ.

The extremely small exponent saving and large constants leave practical crossover unresolved. Major further questions include whether a comparable improvement can survive bounded coefficients, numerical conditioning, finite precision, or a realistic bit-cost model. The family’s stated contribution is to exact arithmetic complexity, with those questions left separate.

8. Sources and further reading

The linked Ailon papers describe restricted-model lower bounds; Alman–Rao illustrates constant-factor improvements within the classical scale. M1’s bibliography supplies the original Cooley–Tukey, Good, Bluestein, and Morgenstern references. M1 below provides the explicit uniform algorithm, while M2 develops the independent finite-tensor existence argument.

Source manuscripts

• M1. OpenAI, An explicit power saving for the exact discrete Fourier transform (September 25, 2026).
• M2. OpenAI, Finite tensor savings and exact Fourier circuits (September 25, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.