Today marks the birthday of Karl Friedrich Gauss, the “Prince of Mathematicians”, who was born on April 30, 1777. In honor of Gauss’s 238th birthday, I thought I would blog about one of Gauss’s favorite theorems — the Law of Quadratic Reciprocity — and its relation to the sign of the quadratic Gauss sum, which we will determine using the Discrete Fourier Transform. Our exposition mostly follows this paper by Ram Murty. Regarding the sign of the quadratic Gauss sum, Gauss conjectured the correct answer in his diary in May 1801, but it took more than four years until he was able to find a proof in August 1805. Gauss wrote to his friend W. Olbers that seldom had a week passed for four years that he had not tried in vain to prove his conjecture. Then:
Finally, two days ago, I succeeded – not on account of my hard efforts, but by the grace of the Lord. Like a sudden flash of lightning, the riddle was solved. I am unable to say what was the conducting thread that connected what I previously knew with what made my success possible.
It seems that Gauss’s original proof did not explicitly use the connection with the Discrete Fourier Transform, although certainly Gauss knew about the latter; in fact, many mathematical historians credit Gauss with the discovery of the Fast Fourier Transform, one of the most important algorithms in all of applied mathematics. See here for a thorough history of the determination of Gauss sums and here for a discussion of Gauss’s role in the discovery of the FFT. While there are hundreds of proofs of the Law of Quadratic Reciprocity (including eight due to Gauss himself), I have always felt that the proofs using Gauss sums are especially insightful. However, as the determination of the sign of the quadratic Gauss sum is traditionally considered difficult (perhaps because of Gauss’s quote above!), most Gauss sum-based proofs of Quadratic Reciprocity use a trick involving qth powers to avoid this evaluation. I’d like to point out here that (in hindsight — no disrespect to Gauss of course!) the sign is not really so difficult to determine, and once this is done there is a short and conceptual path to Quadratic Reciprocity.
Our first goal will be to evaluate the quadratic Gauss sum when is an odd prime number. We will then explain how to adapt the argument to evaluate for any odd positive integer . Finally, we explain how to deduce the Law of Quadratic Reciprocity in a straightforward way from this evaluation. For all of this, we use only basic linear algebra and elementary properties of abelian groups.
Let be the set of functions . The Discrete Fourier Transform (DFT) of is defined to be
(It is more traditional to put a minus sign in front of the but this would be a headache in the present context.)
This is a -linear map from to itself. With respect to the basis of given by the delta-functions for , the DFT is represented by the matrix whose entry is . Note that the trace of (and hence the trace of the Discrete Fourier Transform operator) is .
We begin by showing that the Legendre symbol is an eigenfunction for the discrete Fourier transform, with eigenvalue given by the quadratic Gauss sum. (Thus one can in some sense think of the Legendre symbol as a finite analogue of the Gaussian function , which is its own Fourier transform.)
Lemma 1: Let be an odd prime and let . Then .
Proof: Suppose first that . Since and multiplication by is a bijection on , we have (setting )
where the last equality follows from the fact that .
If , then since there are squares and non-squares in . Thus in both cases we have .
We claim that is equal to the quadratic Gauss sum . To see this, note that
Now plug in on both sides.
The (discrete) Fourier inversion formula asserts that
Exercise: Prove (2).
The Fourier inversion formula allows us to easily calculate the square of the quadratic Gauss sum:
Lemma 2: .
Proof: By (2) and the previous lemma, we have
and thus .
It follows that if and if . The question is, which signs are correct? Gauss showed that in both cases the sign is positive. We will prove this with an argument due to Issai Schur (with some simplifications by Ram Murty) which uses only basic linear algebra.
Recall that is equal to the trace of the discrete Fourier matrix . It will convenient to replace with , which is the matrix of the unitary discrete Fourier transform defined by
(The reason for the name is that is a unitary operator with respect to the Hermitian inner product on . The unitarity of is the discrete analogue of the Plancherel formula.)
The Fourier inversion formula can be stated in the unitary setting as . Thus is the matrix whose entry is if and otherwise. Since , we see that , which implies that the eigenvalues of are and the eigenvalues of itself are contained in the set . Moreover, since the minimal polynomial of is , it follows that is diagonalizable over .
We have seen that the Legendre symbol corresponds to an eigenvector of , but it is difficult to explicitly calculate a basis of eigenvectors for . This can easily be done for , however.
Lemma 3: Let be a positive odd integer.
• A basis for the -eigenspace of is given by the functions and for .
• A basis for the -eigenspace of is given by the functions for .
In particular, the characteristic polynomial of is .
Proof: This is a simple consequence of the identity .
We will calculate the trace of by first calculating its determinant. We will see in a moment that . Assuming this, the following completely elementary lemma will finish our task:
Lemma 4: Let be a positive odd integer, and define to be if and if . Let be an complex matrix such that:
(i) The characteristic polynomial of is .
(ii) The determinant of is .
(iii) The trace of is .
Then the characteristic polynomial of is if and if . In particular, the trace of is .
Proof: Let denote the respective multiplicities of as eigenvalues of . Since the eigenvalues of are the squares of the eigenvalues of , it follows from (i) that and . By (ii) we have
Since , it follows from (iii) that either:
Case 1: , , and ; or
Case 2: , , and .
In Case 1, (3) and imply easily that and thus .
Similarly, in Case 2 we must have and thus .
We now finish the calculation of the quadratic Gauss sum by showing that satisfies condition (ii) of Lemma 4.
Lemma 5: For any positive integer , the determinant of is .
Proof: Since is a Vandermonde matrix, its determinant is
where . Thus
where . (This also follows easily from the fact that the characteristic polynomial of is .)
It follows that , and we would like to determine which sign is correct. Note that (4) can be rewritten in terms of as
But is divisible by , and so . Note also that for . Thus is equal to times a positive quantity, as claimed.
Combining Lemmas 4 and 5, we obtain:
Corollary 1: Let be an odd prime. Then the Gauss sum is equal to if and if .
Note that the proof of Corollary 1 only used the hypothesis that is prime in order to show (using Lemmas 1 and 2) that satisfies condition (iii) of Lemma 4. (Our proofs that (i) and (ii) hold are valid for any positive odd integer .) Following Murty, we explain a nice trick which proves that (iii) holds for any positive odd integer as well.
Lemma 6: For any positive odd integer , .
Proof: We begin with a variant of the proof of Lemma 1 which shows that . First, observe that
Setting , we obtain
Since is odd, the sum over for a fixed value of is zero unless , in which case it is . Thus
Letting be as in the proof of Lemma 4, we have and thus
This implies that either
• Case 1 , and ; or
• Case 2 , and .
By condition (i) from Lemma 4 we have and . It follows easily that in Case 1 we must have and in Case 2 we must have . In both cases we conclude that .
Combining Lemmas 4 and 5, we obtain:
Corollary 2: Let be a positive odd integer. Then the Gauss sum is equal to if and if .
We can use Corollary 2 to obtain an elegant proof of the Law of Quadratic Reciprocity. We will make use of the following simple calculation:
Lemma 7: If and are distinct odd primes then
Proof: The Chinese Remainder Theorem tells us that there is an isomorphism given by . Thus
where the last equality is by (1).
By Lemma 1, we obtain
which is equivalent to the desired result.
We therefore obtain:
The Law of Quadratic Reciprocity: If and are distinct odd primes then
Proof: Let be as in the statement of Lemma 4. By Corollary 2 and Lemma 7, we have
which is equivalent to the stated result.
1. We calculated the multiplicities of each eigenvalue of the Unitary DFT operator . A more difficult problem is determining an explicit and “natural” basis of eigenvectors for . See for example Chapter I of this survey paper by Auslander and Tolimieri and this paper by Gurevich and Hadani.
2. There are higher-order analogues of Gauss sums in which one replaces the Legendre symbol with an mth power residue symbol, and the mth power of such a sum can easily be determined by elementary means. Determining which mth root is correct is still an open problem in general, but a partial solution was obtained for by C.R. Matthews in 1979 in this paper and its sequel. Matthews’ formulas are in terms of products of division values of elliptic functions; this is analogous to the classical formula
for the quadratic Gauss sum in the case .
3. For a totally different proof of the Law of Quadratic Reciprocity, based on Zolotarev’s Lemma and card dealing patterns, see this blog post of mine.
4. This is my first post created using Luca Trevisan’s Latex to WordPress converter.