Let be an odd prime. Let be the Legendre symbol: if is a quadratic residue modulo , if is a quadratic nonresidue and if divides . Let denote and let
.
As we’ll see below, it is not hard to show that , where . Figuring out the sign of , on the other hand, is a famously hard problem; Gauss struggled with it for over a year before a sudden insight, at which point he wrote:
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.
The answer is that is a positive real number when and is a positive multiple of when is congruent to modulo . Gauss’s proof starts out by proving the following identity:
If is any primitive th root of unity, then
.
Here the exponents of on the right hand side are to be considered modulo . For example, if , the identity is
.
I tried to prove this the other day and, to my surprise, found that mathematical notation had proceeded far enough that it was no longer hard! I’m sure this argument isn’t original, but it is nice enough to go in a blog post.
Let’s define the polynomials
and
.
In general, my convention is that is an unspecified variable, is any primitive th root of unity and . The reason that it is hard to compute the sign of is that the sign of is different for different values of , and there are few results which distinguish the th roots of unity from each other. The essence of Gauss’s strategy is to reduce the problem to proving the identity , which does hold for any .
I will be using very little about : basically, that and Euler’s criterion, that . An easy consequence of the latter is that .
The computation of the sign of , using
First, let’s work out the sign of . Every factor is a pure imaginary number; it is a positive multiple of for odd and a negative multiple for even. So the product is either a positive multiple of or a positive real, according to whether is even or odd, as desired.
Now, let’s check that . We have
.
We know that , as both sides are monic polynomials of degree with the same roots. Plugging in , we get
.
Let’s also check that . It is convenient to start by computing
.
Rearranging the sum, this is
Let’s look at that inner sum. If , then it is . As ranges through , the quantity takes every value except and , once each. So this is . Meanwhile, if , then the inner sum is . So, in total, we have
We have which is so .
At this point, we know that so . We know that has the sign we want so, if we can prove , we win.
Proof of
We already know that
and, if we can show that the sign is , we win. From now on, every occurrence of will represent this crucial sign.
I’m going to write the next paragraph in a pretty elementary way. I’m not never sure whether it is better to be simple or to be compact. The compact statement is “we work in .”
We know that is a root of . Since is irreducible, every is a root of . (If you don’t know how to show that is irreducible, here is an alternate route: show that and for any integer not divisible by . You might find Gauss’s lemma useful.) So divides , say . Since is monic, the coefficients of are integers and we can reduce this equation modulo . Also, once we reduce modulo , we have so . We conclude:
We make the shift of variables , and expand both sides in powers of . When remembering this proof, once you get this far, you are home free. The proof writes itself from here.
The right side is simpler. We have . (This equation, like the many that will follow, takes place in .) So
.
On the left hand side, we have
So the coefficient of is . It’s better to start by working out , and then extend by linearity. If you do some computations, you’ll probably guess the answer, so I’ll skip right to the proof.
Lemma: We have for , and .
Proof: Set . Choose in so that . So , and we conclude that . As for , this is with ones.
Corollary: We have for , and .
Proof: Combine the above lemma with Euler’s criterion.
So we see that the coefficient of in is for and the coefficient of is .
Putting it all together, we have
.
So
by Wilson’s theorem. We win.
Final thoughts
We have it much easier than Gauss. First of all, I knew that some sort of identity like was true, although I didn’t remember the details. Discovering this result is surely the hardest part. Also, our notation is incomparably better: Gauss didn’t use the Legendre symbol, and didn’t work with congruences modulo polynomials. I’m not sure whether he would allow himself to work in the ring . Finally, many of us have seen a lot of the above computations before: The computations of and appear at the start of various cyclotomic proofs of quadratic reciprocity, some of them found by Gauss; the computation of modulo is the center of the proof of the Chevalley-Warning theorem.
Now that we have these advantages, the above proof can be summed up in two sentences. (1) It is easy to see that , so we just have to get the sign in . (2) Work -adically or, equivalently, -adically.
When we transform an art into a science, we aim to replace inspiration by perspiration.
Concrete Mathematics, Graham, Knuth and Patashnik
There is a fascinating result of Mueger’s which generalizes Gauss’s result on the sign of the Gauss sum. Let C be a ribbon category (this is a braided tensor category with a nicely consistent theory of duals). To each simple object we can attach two numbers, its dimension , and the scalar by which the ribbon element acts .
Define the Gauss sum attached to C to be
Then the absolute value squared of the Gauss sum is the dimension of C. Furthermore if C happens to be the Drinfel’d double of another category C’, then Mueger calculates that the Gauss sum is the dimension of C’. This gives the sign of the Gauss sum. The usual Gauss sum corresponds to the case where the tensor category is pointed.
I wish I understood this paper, because many years ago Henry Cohn asked me if there was a connection between quantum groups and the sign of the Gauss sum.
Somebody found new conceptual proofs to my theorems at:
http://arxiv.org/abs/0808.2447
I’m a bit disappointed that they didn’t mention Milgram’s theorem concerning signatures of lattices. It comes straight out of the Weil representation, and is a nice generalization of quadratic reciprocity.
I’m much more disappointed that Gauss went through the trouble of coming back from the dead to post on our blog (in English!), and didn’t bother to give us a new proof of quadratic reciprocity of his own.
Noah, do you have a reference for this result of Muger’s that you mention?
Peter: see Theorem 1.2 in “From Subfactors to Categories and Topology II.” This can be found on the arxiv: http://arxiv.org/abs/math/0111205
This is what I was searching for!
A few minor things to be corrected if you wish to edit the post:
– In (*), replace the two $i$’s by $k$’s.
– In the example where you apply (*) to $p=7$, replace $\eta^1-\eta^6$ by $\eta^6-\eta^1$ (I think so, at least).
– In the definition of $h$, I believe you should explain what $x^{-k/2}$ and $x^{k/2}$ mean. (Namely, $x^{k/2}$ means $x^{\text{the element }i\in\left\{0,1,…,p-1\right\}\text{ such that }2i\equiv k\mod p}$, and similarly $x^{k/2}$ means $x^{\text{the element }i\in\left\{0,1,…,p-1\right\}\text{ such that }2i\equiv -k\mod p}$.) Same goes for $\left(1+u\right)^{-k/2}$ and $\left(1+u\right)^{k/2}$. Simply saying that “exponents are modulo $p$” is not enough, because $x$ is not a $p$-th root of unity.
– “So the product is either a positive multiple of $i$ or a positive real, according to whether $(p-1)/2$ is even or odd, as desired.” This should be exactly the other way round: “So the product is either a positive multiple of $i$ or a positive real, according to whether $(p-1)/2$ is odd or even, as desired.”
– Several times, $x^p+\cdots +x+1$ should be $x^{p-1}+\cdots +x+1$.
– In the proof of the lemma, $S=0$ should be $S\equiv 0\mod p$.
– In the lemma and in the corollary, you sometimes write $\equiv 0\mod p$, but sometimes just $\equiv 0$ (without $\mod p$).
– After saying “Putting it all together, we have”, you have a two-lines formula. On the second of its lines, add a $\pm$ sign.