Connecting the FFT and quadratic reciprocity
Some readers will look at the title of this post and think Ah yes, the FFT. I use it all the time. But what is this quadratic reciprocity?"
Others will look at the same title and think Gauss called the quadratic reciprocity theorem the jewel in the crown of mathematics. But what is this FFT thing? I think I remember an engineer saying something about that."
Gauss proved a theorem that relates quadratic reciprocity and the FFT. For distinct odd primes p and q, the following equation holds.
I'll spend the rest of this post unpacking this equation.
Legendre symbolsThe expressions on the left are not fractions but rather Legendre symbols. The parentheses are not for grouping but are part of the symbol.
The Legendre symbol
is defined to be 0 if a is a multiple of r, 1 if a has a square root mod r, and -1 otherwise.
Fourier transformsThe Discrete Fourier Transform (DFT) of a vector of length n multiplies the vector by the n by n Fourier matrix Fp whose j, k entry is equal to exp(2i jk / n). The Fast Fourier Transform (FFT) is a way to compute the DFT more quickly than directly multiplying by the Fourier matrix. Since the DFT is nearly always computed using the FFT algorithm, the DFT is commonly referred to as the FFT.
Matrix traceThe trace of a matrix is the sum of the elements along the main diagonal. So the trace of the Fourier matrix of size n is
The quadratic reciprocity theorem, also due to Gauss, is usually stated as
We can illustrate the theorem at the top of the page numerically with the following Python code, using the quadratic reciprocity theorem to evaluate the product of the Legendre symbols.
from numpy import exp, pitr = lambda p: sum(exp(2j*pi*k**2/p) for k in range(1, p+1))p, q = 59, 17print( tr(p*q)/(tr(p)*tr(q)) )print( (-1)**((p-1)*(q-1)/4) )
The first print statement produces (0.9999999999998136-1.4048176871018313e-13j) due to some loss of precision due to floating point calculations, but this is essentially 1, which is what the second print statement produces.
If we change q to 19, both statements print -1 (after rounding the first result).
Quadratic Gauss sumWe can quickly prove
if we assume the quadratic reciprocity theorem and the following equation for the trace of the Fourier matrix.
This proof is historically backward. It assumes quadratic reciprocity, but Gauss proved quadratic reciprocity by first proving the equation we're trying to prove. He then obtained the expression on the right hand side of the quadratic reciprocity theorem using the equation above for the trace of the Fourier matrix.
The trace of the Fourier matrix is now called a quadratic Gauss sum. It's a special case of more general sums that Gauss studied, motivated by his exploration of quadratic reciprocity.
Incidentally, Gauss gave many proofs of the quadratic reciprocity theorem. I don't know where the proof outlined hear fits into the sequence of proofs he developed.
Related postsThe post Connecting the FFT and quadratic reciprocity first appeared on John D. Cook.