The discrete Fourier transform needs (2.78 - o(1)) N gates #
Let ω be a primitive N-th root of unity in a field F and dft ω N = (ω ^ (r c)) the
N-point Fourier matrix, for any N (in particular N = 2^k, the map computed by the fast
Fourier transform). For every ε > 0 and all large N, uniformly in the field:
- every fan-in-two linear circuit over
Fcomputingx ↦ dft ω N x, that is, every circuit with a local linear realization (Linear.Realization) in which each gate computes a linear combination of its arguments with arbitrary coefficients, has more than(1 + κ/2 - ε) N ≈ (2.78 - ε) Ngates (Linear.eventually_lt_size_dft), whereκ = π/(3 arccos((1 + 2√2)/4)) ≈ 3.5625is1/(2p)for the Gaussian edge-score pathwidth coefficientp; at least(25/9 - ε) N. This covers the complex DFT withω = e^{2πi/N}(Linear.eventually_lt_size_complexDFT,Linear.eventually_lt_size_fft); - over a finite field, the same holds for every fan-in-two circuit with arbitrary gates
F × F → Fcomputingx ↦ dft ω N x(eventually_lt_size_dft), such as the number-theoretic transforms overZMod qwithN ∣ q - 1(eventually_lt_size_ntt).
The Fourier matrix is not totally regular (for N = 4 it has singular 2 × 2 blocks), so the
bound for totally regular maps does not apply. Instead, the proof uses half cuts. The Fourier
matrix is the transposed Vandermonde matrix of the distinct nodes ω ^ c, and on any set C of
columns its first |C| rows are linearly independent. Hence for a set X of h = ⌊N/2⌋
inputs and any set Y of outputs, rank F[Yᶜ, X] + rank F[Y, Xᶜ] ≥ h
(le_blockRank_add_blockRank_dft, and le_blockRank_add_blockRank_vandermonde for any
distinct nodes): the first block has rank at least the number of the first h rows outside
Y, and the second, with N - h ≥ h columns, at least the number of the first h rows in Y.
Along the ordering of MultiOutput.exists_rank, the prefix holding exactly h inputs is
crossed by at least h signals by the rank-cut bound, and by at most
(A + η) (s - N)⁺ + O(log (N + s)) by the ordering bound (half_le_of_dft), so a circuit of
size s has s ≥ (1 + 1/(2A) - ε) N.
Prior art. Valiant (1975) observed that a linear circuit computing the Fourier transform is a
hyperconcentrator (Multigraph.Hyperconcentrator). For prime N all minors of the complex
Fourier matrix are nonsingular (Chebotarëv), so such circuits are superconcentrators, and Lev and
Valiant (Size bounds for superconcentrators, Theoretical Computer Science, 1983) derived
4 N - o(N) additions. For general N, including N = 2^k, Lokam (Complexity lower bounds
using linear algebra, 2009) and Ailon (arXiv:1403.1307) record no superlinear lower bound for
unrestricted linear circuits; the bound here is linear, with the constant 1 + κ/2 ≈ 2.78.
Half cuts #
Half cuts of Vandermonde matrices. For distinct nodes x c, every set X of h
columns with 2 h ≤ N, and every set Y of rows, the matrix (x c ^ r) satisfies
h ≤ rank M[Yᶜ, X] + rank M[Y, Xᶜ].
Half cuts of the Fourier matrix. For a primitive N-th root of unity ω, every set X
of ⌊N/2⌋ inputs and every set Y of outputs, ⌊N/2⌋ ≤ rank F[Yᶜ, X] + rank F[Y, Xᶜ].
Finite bounds #
The finite bound for the Fourier transform over a finite field. If a circuit over a
finite field, over any signature with fan-in at most two, computes x ↦ dft ω N x for a
primitive N-th root of unity ω, then under the graph-ordering hypothesis
⌊N/2⌋ ≤ (A + η) (s - N)⁺ + 3 log₂ (N + 3 s) + C for its size s.
The finite bound for linear circuits computing the Fourier transform, over any field.
Asymptotic bounds #
Linear circuits for the Fourier transform, general ordering coefficient. If the
graph-ordering hypothesis holds with coefficient A > 0 for every positive slack, then for every
ε > 0 and all large N, every fan-in-two circuit over any field with a local linear
realization computing x ↦ dft ω N x, for a primitive N-th root of unity ω, has more than
(1 + 1/(2A) - ε) N gates.
Linear circuits for the Fourier transform need (2.78 - ε) N gates. For every ε > 0
and all large N, every fan-in-two linear circuit over any field computing x ↦ dft ω N x, for
a primitive N-th root of unity ω, has more than (1 + κ/2 - ε) N gates, where
κ = π/(3 arccos((1 + 2√2)/4)) ≈ 3.5625.
Linear circuits for the Fourier transform need (25/9 - ε) N gates.
The complex DFT. For every ε > 0 and all large N, every fan-in-two linear circuit over
ℂ computing the N-point discrete Fourier transform x ↦ (e^{2πi r c/N}) x has more than
(1 + κ/2 - ε) N gates.
The fast Fourier transform is near optimal up to its constant. For every ε > 0 and all
large k, every fan-in-two linear circuit over ℂ computing the 2^k-point discrete Fourier
transform has more than (1 + κ/2 - ε) 2^k gates.
Arbitrary gates over a finite field, general ordering coefficient. If the graph-ordering
hypothesis holds with coefficient A > 0 for every positive slack, then for every ε > 0 and all
large N, every circuit over a finite field, over any signature with fan-in at most two, computing
x ↦ dft ω N x for a primitive N-th root of unity ω, has more than (1 + 1/(2A) - ε) N
gates.
The Fourier transform over a finite field needs (2.78 - ε) N gates. For every ε > 0
and all large N, every circuit over a finite field, over any signature with fan-in at most two,
computing x ↦ dft ω N x for a primitive N-th root of unity ω, has more than
(1 + κ/2 - ε) N gates, where κ = π/(3 arccos((1 + 2√2)/4)) ≈ 3.5625.
The Fourier transform over a finite field needs (25/9 - ε) N gates.
Primitive roots for number-theoretic transforms. For a prime q and N ∣ q - 1, ZMod q
contains a primitive N-th root of unity.
Number-theoretic transforms need (2.78 - ε) N gates. For every ε > 0 and all large
N, for every prime q and every primitive N-th root of unity ω in ZMod q (one exists
when N ∣ q - 1), every circuit over ZMod q, over any signature with fan-in at most two,
computing x ↦ dft ω N x has more than (1 + κ/2 - ε) N gates.