The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity

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 $g_n := \sum_{x \in {\mathbb Z} / n{\mathbb Z}} e^{2\pi i x^2 / n}$ when ${n=p}$ is an odd prime number. We will then explain how to adapt the argument to evaluate $g_n$ for any odd positive integer $n$ . 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 ${H_n}$ be the set of functions ${f : {\mathbb Z} / n{\mathbb Z} \rightarrow {\mathbb C}}$ . The Discrete Fourier Transform (DFT) of ${f \in H_n}$ is defined to be $\hat{f}(x) = \sum_{y \in {\mathbb Z} / n{\mathbb Z}} f(y) e^{2\pi i x y / n}.$
(It is more traditional to put a minus sign in front of the ${2\pi i}$ but this would be a headache in the present context.)

This is a ${{\mathbb C}}$ -linear map from ${H_n}$ to itself. With respect to the basis of ${H_n}$ given by the delta-functions ${\delta_a}$ for ${a=0,1,\ldots,n-1}$ , the DFT is represented by the ${n \times n}$ matrix ${F_n}$ whose ${(a,b)}$ entry is ${F_{ij} = e^{2\pi i a b / n}}$ . Note that the trace of ${F_n}$ (and hence the trace of the Discrete Fourier Transform operator) is ${g_n}$ .

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 ${g(x) = e^{-\pi x^2} : {\mathbb R} \rightarrow {\mathbb R}}$ , which is its own Fourier transform.)

Lemma 1: Let ${p}$ be an odd prime and let ${h_p(x) = \left( \frac{x}{p} \right)}$ . Then ${\hat{h}_p(x) = g_p h_p(x)}$ .

Proof: Suppose first that ${x \neq 0}$ . Since ${h_p(0)=0}$ and multiplication by ${x}$ is a bijection on ${({\mathbb Z} / p{\mathbb Z})^*}$ , we have (setting ${b = xa}$ )
$\displaystyle \begin{array}{ll} \hat{h}_p(x) &= \sum_{a=1}^{p-1} \left( \frac{x}{p} \right) e^{2\pi i x a / p} \\ &= \sum_{b=1}^{p-1} \left( \frac{bx^{-1}}{p} \right) e^{2\pi i x b / p} \\ &= h_p(x^{-1}) \hat{h}_p(1) \\ &= h_p(x) \hat{h}_p(1), \\ \end{array}$
where the last equality follows from the fact that ${\left( \frac{x^{-1}}{p} \right) = \left( \frac{x}{p} \right)}$ .
If ${x = 0}$ , then ${\hat{h}_p(x) = \sum_{a=1}^{p-1} \left( \frac{x}{p} \right) = 0}$ since there are ${\frac{(p-1)}{2}}$ squares and ${\frac{(p-1)}{2}}$ non-squares in ${({\mathbb Z} / p{\mathbb Z})^*}$ . Thus in both cases we have ${\hat{h}_p(x) = \hat{h}_p(1) h_p(x)}$ .
We claim that ${\hat{h}_p(1)}$ is equal to the quadratic Gauss sum ${g_p}$ . To see this, note that
$\displaystyle \begin{array}{ll} \sum_{x \in {\mathbb Z} / p{\mathbb Z}} e^{2\pi i a x^2 / p} &= \sum_{y \in {\mathbb Z} / p{\mathbb Z}} \left( 1 + \left( \frac{y}{p} \right) \right) e^{2\pi i a y / p} \\ &= \left( \sum_{y \in {\mathbb Z} / p{\mathbb Z}} e^{2\pi i a y / p} \right) + \hat{h}_p(a) \\ &= \hat{h}_p(a). \end{array} \ \ \ \ \ (1)$
Now plug in ${a=1}$ on both sides. ${\blacksquare}$

The (discrete) Fourier inversion formula asserts that
$\displaystyle f(x) = \frac{1}{n} \sum_{y \in {\mathbb Z} / n {\mathbb Z}} \hat{f}(y) e^{-2\pi i x y / n} . \ \ \ \ \ (2)$

Exercise: Prove (2).

The Fourier inversion formula allows us to easily calculate the square of the quadratic Gauss sum:

Lemma 2: ${g_p^2 = \left( \frac{-1}{p} \right) p}$ .

Proof: By (2) and the previous lemma, we have
$\displaystyle \begin{array}{ll} h_p(x) &= \frac{1}{p} \sum_{y \in {\mathbb Z} / p {\mathbb Z}} \hat{h}_p(y) e^{-2\pi i x y / p} \\ &= \frac{g_p}{p} \sum_{y \in {\mathbb Z} / p {\mathbb Z}} h_p(y) e^{-2\pi i x y / p} \\ &= \frac{g_p}{p} \hat{h}_p(-x) \\ &= \frac{g_p^2}{p} h_p(-x) \\ &= \frac{g_p^2}{p} h_p(-1) h_p(x) \\ \end{array}$
and thus ${\frac{g_p^2}{p} h_p(-1) = 1}$ . ${\blacksquare}$

It follows that ${g_p = \pm \sqrt{p}}$ if ${p \equiv 1 \pmod{4}}$ and ${g_p = \pm i \sqrt{p}}$ if ${p \equiv 3 \pmod{4}}$ . 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 ${g_n}$ is equal to the trace of the discrete Fourier matrix ${F_n}$ . It will convenient to replace ${F_n}$ with ${U_n = \frac{1}{\sqrt{n}} F_n}$ , which is the matrix of the unitary discrete Fourier transform ${\Phi_n : H_n \rightarrow H_n}$ defined by $\displaystyle \Phi_n (f) = \frac{1}{\sqrt{n}} \hat{f}.$
(The reason for the name is that ${\Phi_n}$ is a unitary operator with respect to the Hermitian inner product ${\langle f , g \rangle = \sum_{y \in {\mathbb Z} / n {\mathbb Z}} f(y) \overline{g(y)}}$ on ${H_n}$ . The unitarity of $\Phi_n$ is the discrete analogue of the Plancherel formula.)

The Fourier inversion formula can be stated in the unitary setting as ${\Phi_n^2 (f(x)) = f(-x)}$ . Thus ${U_n^2}$ is the matrix whose ${(a,b)}$ entry is ${1}$ if ${a=-b}$ and ${0}$ otherwise. Since ${\Phi_n^4(f) = f}$ , we see that ${U_n^4 = I}$ , which implies that the eigenvalues of ${U_n^2}$ are ${\pm 1}$ and the eigenvalues of ${U_n}$ itself are contained in the set ${\{ \pm 1, \pm i \}}$ . Moreover, since the minimal polynomial of ${U_n}$ is ${X^4 - 1}$ , it follows that ${U_n}$ is diagonalizable over ${{\mathbb C}}$ .

We have seen that the Legendre symbol corresponds to an eigenvector of ${\Phi_p}$ , but it is difficult to explicitly calculate a basis of eigenvectors for ${\Phi_p}$ . This can easily be done for ${\Phi_p^2}$ , however.

Lemma 3: Let ${n}$ be a positive odd integer.
• A basis for the ${1}$ -eigenspace of ${\Phi_n^2}$ is given by the functions ${\delta_0}$ and ${\delta_j + \delta_{-j}}$ for ${1 \leq j \leq \frac{n-1}{2}}$ .
• A basis for the ${-1}$ -eigenspace of ${\Phi_n^2}$ is given by the functions ${\delta_j - \delta_{-j}}$ for ${1 \leq j \leq \frac{n-1}{2}}$ .
In particular, the characteristic polynomial of ${U_n^2}$ is ${(X - 1)^{(n+1)/2} (X+1)^{(n-1)/2}}$ .

Proof: This is a simple consequence of the identity ${\Phi_n^2 (f(x)) = f(-x)}$ . ${\blacksquare}$

We will calculate the trace of ${U_p}$ by first calculating its determinant. We will see in a moment that ${{\rm det}(U_p) = i^{p(p-1)/2}}$ . Assuming this, the following completely elementary lemma will finish our task:

Lemma 4: Let ${n}$ be a positive odd integer, and define ${e(n)}$ to be ${1}$ if ${n \equiv 1 \pmod{4}}$ and ${i}$ if ${n \equiv 3 \pmod{4}}$ . Let ${U}$ be an ${n \times n}$ complex matrix such that:
(i) The characteristic polynomial of ${U^2}$ is ${(X - 1)^{(n+1)/2} (X+1)^{(n-1)/2}}$ .
(ii) The determinant of ${U}$ is ${i^{n(n-1)/2}}$ .
(iii) The trace of ${U}$ is ${\pm e(n)}$ .
Then the characteristic polynomial of $U$ is $(x-1)(x^4 - 1)^{\frac{n-1}{4}}$ if $n \equiv 1 \pmod{4}$ and $(x-1)(x+1)(x-i)(x^4 - 1)^{\frac{n-3}{4}}$ if $n \equiv 3 \pmod{4}$ . In particular, the trace of ${U}$ is ${e(n)}$ .

Proof: Let ${a,b,c,d}$ denote the respective multiplicities of ${1,-1,i,-i}$ as eigenvalues of ${U}$ . Since the eigenvalues of $U^2$ are the squares of the eigenvalues of $U$ , it follows from (i) that ${a+b = \frac{n+1}{2}}$ and ${c+d = \frac{n-1}{2}}$ . By (ii) we have
$\displaystyle \det(U) = (-1)^{b+d} i^{c+d} = i^{2b+c+3d} = i^{n(n-1)/2},$
and thus $\displaystyle 2b+c-d \equiv n(n-1)/2 \pmod{4}. \ \ \ \ \ (3)$
Since ${{\rm trace}(U) = (a-b) + (c-d)i}$ , it follows from (iii) that either:
Case 1: ${n \equiv 1 \pmod{4}}$ , ${a - b = \pm 1}$ , and ${c = d}$ ; or
Case 2: ${n \equiv 3 \pmod{4}}$ , ${a = b}$ , and ${c - d = \pm 1}$ .
In Case 1, (3) and ${c=d}$ imply easily that ${a-b \equiv 1 \pmod{4}}$ and thus $a-b=1$ .
Similarly, in Case 2 we must have ${c - d \equiv 1 \pmod{4}}$ and thus $c-d=1$ . ${\blacksquare}$

We now finish the calculation of the quadratic Gauss sum ${g_p}$ by showing that ${U_n}$ satisfies condition (ii) of Lemma 4.

Lemma 5: For any positive integer ${n}$ , the determinant of ${U_n}$ is ${i^{n(n-1)/2}}$ .

Proof: Since ${F_n}$ is a Vandermonde matrix, its determinant is
$\displaystyle \det(F_n) = \prod_{0 \leq s < r \leq n-1} (\zeta^r - \zeta^s) \ \ \ \ \ (4)$
where ${\zeta = e^{2\pi i / n}}$ . Thus
$\displaystyle \det(F_n)^2 = (-1)^{\binom{n}{2}} \prod_{r \neq s} (\zeta^r - \zeta^s) = (-1)^{\binom{n}{2}} \prod_{j=0}^{n-1} f'(\zeta^j) = (-1)^{\binom{n}{2}} n^n,$
where ${f(x) = x^n - 1}$ . (This also follows easily from the fact that the characteristic polynomial of ${U_n^2}$ is ${(X - 1)^{(n+1)/2} (X+1)^{(n-1)/2}}$ .)
It follows that ${\det(U_n) = \pm i^{\binom{n}{2}}}$ , and we would like to determine which sign is correct. Note that (4) can be rewritten in terms of ${\eta = e^{\pi i / n}}$ as
$\displaystyle \det(F_n) = \prod_{s < r} \eta^{r+s} (\eta^{r-s} - \eta^{-(r-s)}) = \eta^{\sum_{s < r} {r+s}} \prod_{s < r} \left( 2i \sin \frac{(r-s)\pi}{n} \right).$
But ${{\sum_{s < r} {r+s}} = 2n (\frac{n-1}{2})^2}$ is divisible by ${2n}$ , and so ${\eta^{\sum_{s < r} {r+s}} = 1}$ . Note also that ${\sin \frac{(r-s)\pi}{n} > 0}$ for ${0 \leq s < r \leq n-1}$ . Thus $\displaystyle \det(U_n) = \frac{1}{n^{n/2}} \prod_{s < r} \left( 2i \sin \frac{(r-s)\pi}{n} \right)$ is equal to ${i^{n(n-1)/2}}$ times a positive quantity, as claimed. ${\blacksquare}$

Combining Lemmas 4 and 5, we obtain:

Corollary 1: Let ${p}$ be an odd prime. Then the Gauss sum ${g_p}$ is equal to ${\sqrt{p}}$ if ${p \equiv 1 \pmod{4}}$ and ${i \sqrt{p}}$ if ${p \equiv 3 \pmod{4}}$ .

Note that the proof of Corollary 1 only used the hypothesis that ${p}$ is prime in order to show (using Lemmas 1 and 2) that ${U_n}$ satisfies condition (iii) of Lemma 4. (Our proofs that (i) and (ii) hold are valid for any positive odd integer ${n}$ .) Following Murty, we explain a nice trick which proves that (iii) holds for any positive odd integer ${n}$ as well.

Lemma 6: For any positive odd integer ${n}$ , ${{\rm trace}(U_n) = \pm e(n)}$ .

Proof: We begin with a variant of the proof of Lemma 1 which shows that ${|{\rm trace}(U_n)| = 1}$ . First, observe that
$\displaystyle |{\rm trace}(F_n)|^2 = {\rm trace}(F_n) \overline{{\rm trace}(F_n)} = \sum_{k,\ell} \zeta^{k^2 - \ell^2} = \sum_{k,\ell} \zeta^{(k-\ell)(k+\ell)}.$
Setting ${k-\ell = m}$ , we obtain
$\displaystyle |{\rm trace}(F_n)|^2 = \sum_{\ell, m} \zeta^{m^2 + 2\ell m}.$
Since ${n}$ is odd, the sum over ${\ell}$ for a fixed value of ${m}$ is zero unless ${m=0}$ , in which case it is ${n}$ . Thus
$\displaystyle |{\rm trace}(U_n)|^2 = \frac{1}{n} |{\rm trace}(F_n)|^2 = 1$
as claimed.

Letting ${a,b,c,d}$ be as in the proof of Lemma 4, we have ${{\rm trace}(U) = (a-b) + (c-d)i}$ and thus
$\displaystyle 1 = |{\rm trace}(U_n)|^2 = (a-b)^2 + (c-d)^2.$
This implies that either
• Case 1 ${a - b = \pm 1}$ , and ${c = d}$ ; or
• Case 2 ${a = b}$ , and ${c - d = \pm 1}$ .
By condition (i) from Lemma 4 we have ${a+b = \frac{n+1}{2}}$ and ${c+d = \frac{n-1}{2}}$ . It follows easily that in Case 1 we must have ${n \equiv 1 \pmod{4}}$ and in Case 2 we must have ${n \equiv 1 \pmod{4}}$ . In both cases we conclude that ${{\rm trace}(U_n) = \pm e(n)}$ . ${\blacksquare}$
Combining Lemmas 4, 5, and 6, we obtain:

Corollary 2: Let ${n}$ be a positive odd integer. Then the Gauss sum ${g_n}$ is equal to ${\sqrt{n}}$ if ${n \equiv 1 \pmod{4}}$ and ${i \sqrt{n}}$ if ${n \equiv 3 \pmod{4}}$ .

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 ${p}$ and ${q}$ are distinct odd primes then $\frac{g_{pq}}{g_p g_q} = \left( \frac{p}{q} \right) \left( \frac{q}{p} \right).$

Proof: The Chinese Remainder Theorem tells us that there is an isomorphism ${{\mathbb Z} / p {\mathbb Z} \times {\mathbb Z} / q {\mathbb Z} {\buildrel \sim\over\longrightarrow} {\mathbb Z} / pq {\mathbb Z}}$ given by ${(x,y) \mapsto xq+yp}$ . Thus
$\displaystyle \begin{array}{ll} g_{pq} &= \sum_{z \in {\mathbb Z} / pq{\mathbb Z}} e^{2\pi i z^2 / pq} \\ &= \sum_{x \in {\mathbb Z} / p{\mathbb Z}} \sum_{y \in {\mathbb Z} / q{\mathbb Z}} e^{2\pi i (xq+yp)^2 / pq} \\ &= \sum_{x \in {\mathbb Z} / p{\mathbb Z}} e^{2\pi i q x^2 / p} \sum_{y \in {\mathbb Z} / q{\mathbb Z}} e^{2\pi i p y^2 / q} \\ &= \hat{h}_p(q) \hat{h}_q(p), \end{array}$
where the last equality is by (1).
By Lemma 1, we obtain
$\displaystyle g_{pq} = \left( \frac{q}{p} \right) g_p \left( \frac{p}{q} \right) g_q$
which is equivalent to the desired result. ${\blacksquare}$

We therefore obtain:

The Law of Quadratic Reciprocity: If ${p}$ and ${q}$ are distinct odd primes then
$\displaystyle \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = \left\{ \begin{array}{ll} +1 & {\rm \; if \; \; \; } p\equiv 1 \pmod{4} {\rm \; \; \; or \; \; \;} q \equiv 1 \pmod 4 \\ -1 & {\rm \; if \; \; \;} p\equiv q \equiv 3 \pmod{4} \\ \end{array} \right.$

Proof: Let ${e(n)}$ be as in the statement of Lemma 4. By Corollary 2 and Lemma 7, we have
$\displaystyle \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = \frac{g_{pq}}{g_p g_q} = \frac{e(pq) \sqrt{pq}}{e(p) \sqrt{p} \cdot e(q) \sqrt{q}} = \frac{e(pq)}{e(p) e(q)}$
which is equivalent to the stated result. ${\blacksquare}$

Concluding remarks

1. We calculated the multiplicities of each eigenvalue of the Unitary DFT operator $\Phi_n$ . A more difficult problem is determining an explicit and “natural” basis of eigenvectors for $U_n$ . 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 $m=3,4$ 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

$g_p = (-1)^{\frac{(p-1)(p-3)}{8}} (2i)^{\frac{p-1}{2}} \prod_{j=1}^{\frac{p-1}{2}} \sin \left( \frac{2\pi j}{p} \right)$

for the quadratic Gauss sum $g_p$ in the case $m=2$ .

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.

One thought on “The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity”

Pingback: Quadratic Reciprocity via Lucas Polynomials | Matt Baker's Math Blog

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity

One thought on “The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity”

Leave a Reply Cancel reply

Share this:

Like this:

Related

One thought on “The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity”

Leave a Reply Cancel reply