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.