Exact Fourier Cost Has Vanishing Normalized Growth on a Subsequence

Fast Fourier transform algorithms use about n log₂ n arithmetic operations. The manuscript proves a sharper asymptotic statement for a deliberately unrestricted exact-circuit model: the limit inferior, as n grows, of the minimum gate count divided by n log₂ n is zero. In other words, arbitrarily large selected lengths admit circuits whose normalized cost becomes arbitrarily small. The claim is not that every length has a faster circuit or that a practical FFT replacement is available.^†

A circuit must return every Fourier output exactly for every complex input. Its wiring and constants may depend on the transform length, but not on input values. Preparing constants is free; each use of scalar multiplication is charged as one gate, as are additions and subtractions. The model imposes no limits on coefficient size, description length, or numerical conditioning. The theorem therefore concerns exact arithmetic in a nonuniform model, not numerical stability or ordinary Fourier software.

For a q-by-q matrix acting along b tensor axes, the direct method uses q^(b−1) matrix calls per axis, or bq^(b−1) calls altogether. A finite win means carrying out that same tensor map on exactly the same q^b coordinates with fewer calls.

The definition uses an auxiliary cost model: coordinate permutations and nonzero coordinate scalings between matrix calls are free. In the final scalar-circuit model, scalar multiplications are charged again. The proof accounts for those costs when translating the matrix-call saving into gates. It establishes that some invertible, nonmonomial matrix has a finite win for some tensor power; it does not provide an explicit winning matrix.

Tensor copies of the winning computation can then be synchronized by their call slots. Each slot divides the coordinates into sectors: in some tensor copies the matrix is active, while in others the operation is an identity. The source illustrates the coordinate-weighted sector count for q = 2, b = 2, and j = 3:

This is exact bookkeeping, not a randomized or approximate computation. The resulting bound for the k-th tensor power has the form Cq^k(k+1)^α, where 0 < α < 1. The technical induction is omitted, but the bound includes every monomial scaling. That exponent below one is the leverage: after amplification, the gate bound grows more slowly than the usual number of tensor-axis calls.

Amplification alone does not establish a Fourier result. The construction must transfer the saving without adding spare registers or assuming that a borrowed coordinate starts at zero.

Suppose the goal is to add 2x to y while borrowing an unknown register z. First set z ← z + 2x, then y ← y + z. Undo the change to z, and subtract the restored z from y. The unknown initial value cancels, leaving y + 2x while returning x and z unchanged. This works for every initial value. The manuscript’s replay lemma extends the cleanup to an entire linear computation.

The Fourier bridge combines that replay with structured factorizations. Small Fourier transforms become shallow sequences of pair operations and monomial maps without extra coordinates. Another lemma implements the needed pair operations through a common call pattern in the winning matrix, restoring the other coordinates.

For the relevant lengths, choose n as a product of m distinct primes rᵢ > 2q. Chinese remainder permutations identify the length-n Fourier transform with a tensor product of the prime-length transforms, up to input and output permutations. Taking more distinct primes gives unbounded lengths; their product makes log n grow at least linearly in m. The proof also bounds the primes in terms of m: the m-th eligible prime is at most polynomially large in m, so each factor contributes only logarithmic-scale overhead. In the manuscript’s estimate, the layer overhead is at most on the order of log⁴ m + 1.

Synchronizing the prime-factor patterns makes each call slot a direct sum of powers of the winning matrix. The sectors fill the original width exactly. Combining the amplified gate bound with the layer overhead gives a total bounded by n times that overhead and (m+1)^α. After division by n log n, the overhead contributes a factor on the order of log⁴ m, while the denominator grows at least linearly in m. The ratio therefore tends to zero: the positive power m^(1−α) outgrows the fixed logarithmic factor. This gives the claimed result along unbounded selected lengths.

The existence of a finite win is proved by contradiction. Assume none exists. Packing finite comparisons, separation, and compactness then produce an auxiliary price function on invertible matrices. This is not a scalar gate count: a basic shear has price one, monomial maps have price zero, and tensor products and direct sums obey exact price laws. The argument assumes no continuity of the price function.

Further lemmas control invertible submatrices, feedback connections, and specializations of rational matrix families. Their hypotheses support exact finite identities, not approximate circuits. Under the no-win assumption, these rules are applied to two descriptions of the same carefully chosen reflection.

The first description uses signed bit matrices to force a lower bound on the reflection’s price relative to its width. The second uses a sparse symmetric description, together with a dense-pair bound and two algebraic specializations, to obtain an upper bound on that same quantity. Because the object and price are identical, both bounds would have to hold simultaneously. For d = 31, the construction has width 2^64: one description requires price per width of at least d − 4 = 27, while the other permits at most 3d/4 + 7/2 = 26.75. No value satisfies both inequalities, so the no-win assumption fails.

That contradiction supplies the finite saving; tensor amplification and the exact-width Fourier transfer turn it into vanishing normalized cost along an unbounded subsequence. The result is exact and nonuniform, with no guarantee of numerical stability or practical efficiency.