The sign of the Gauss sum

Let p be an odd prime. Let \left( \frac{a}{p} \right) be the Legendre symbol: \left( \frac{a}{p} \right)=1 if a is a quadratic residue modulo p, \left( \frac{a}{p} \right)=-1 if a is a quadratic nonresidue and \left( \frac{a}{p} \right)=0 if p divides a. Let \zeta denote e^{2 \pi i /p} and let

g(\zeta) = \sum_{j=0}^{p-1} \zeta^j \left( \frac{j}{p} \right).

As we’ll see below, it is not hard to show that g(\zeta)^2 = p^*, where p^* := (-1)^{(p-1)/2} p. Figuring out the sign of g(\zeta), 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 g(\zeta) is a positive real number when p \equiv 1 \mod 4 and is a positive multiple of i when p is congruent to {3} modulo {4}. Gauss’s proof starts out by proving the following identity:

If \eta is any primitive pth root of unity, then

\sum_{j=0}^{p-1} \left( \frac{j}{p} \right) \eta^j = \prod_{k=1}^{(p-1)/2} \left( \eta^{-i/2} - \eta^{i/2} \right) \quad (*).

Here the exponents of \eta on the right hand side are to be considered modulo p. For example, if p=7, the identity is

\eta + \eta^2 - \eta^3 + \eta^4 - \eta^5 - \eta^6 = (\eta^3 - \eta^4) (\eta^1 - \eta^6) (\eta^2 - \eta^5).

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

g(x) = \sum_{j=0}^{p-1} \left( \frac{j}{p} \right) x^j

and

h(x) = \prod_{k=1}^{(p-1)/2} (x^{-k/2} - x^{k/2} ).

In general, my convention is that x is an unspecified variable, \eta is any primitive pth root of unity and \zeta = e^{2 \pi i/p}. The reason that it is hard to compute the sign of g(\zeta) is that the sign of g(\eta) is different for different values of \eta, and there are few results which distinguish the pth 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 \eta.

I will be using very little about \left( \frac{a}{p} \right): basically, that \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right)\left( \frac{b}{p} \right) and Euler’s criterion, that a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \mod p. An easy consequence of the latter is that \left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}.

The computation of the sign of g(\zeta), using (*)

First, let’s work out the sign of h(\zeta). Every factor (\zeta^{-k/2} - \zeta^{k/2}) is a pure imaginary number; it is a positive multiple of i for k odd and a negative multiple for k even. 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.

Now, let’s check that h(\eta)^2 = p^*. We have

h(\eta)^2 = \prod_{k=1}^{(p-1)/2} ( \eta^{-k/2} - \eta^{k/2} )^2 =

\prod_{k=1}^{(p-1)/2} (\eta^{-k} -1)(1-\eta^k)=(-1)^{(p-1)/2} \prod_{k=1}^{p-1} (1-\eta^k).

We know that \prod_{j=1}^{p-1} (x-\eta^j) = x^{p-1} + x^{p-2} + \cdots +x+1, as both sides are monic polynomials of degree p-1 with the same roots. Plugging in x=1, we get

h(\eta)^2 = (-1)^{(p-1)/2} p = p^*.

Let’s also check that g(\eta)^2 = p^*. It is convenient to start by computing

g(\eta) g(\eta^{-1})=\sum_{j=0}^{p-1}\sum_{k=0}^{p-1}\eta^{j-k}\left(\frac{jk}{p}\right).

Rearranging the sum, this is

\sum_{a=0}^{p-1}\eta^a\sum_{j=0}^{p-1}\left(\frac{j(j+a)}{p}\right)

Let’s look at that inner sum. If a \neq 0, then it is \sum_{j \neq 0,-a}\left(\frac{1+aj^{-1}}{p}\right). As j ranges through \mathbb{Z}/p \setminus \{ 0, -a \}, the quantity 1+aj^{-1} takes every value except {0} and {1}, once each. So this is \sum_{r=2}^{p-1}\left(\frac{r}{p}\right)=-\left(\frac{1}{p}\right)=-1. Meanwhile, if a=0, then the inner sum is \sum_{j=1}^{p-1} \left( \frac{j^2}{p} \right) = p-1. So, in total, we have

g(\eta) g(\eta^{-1}) = \left( (p-1) -\eta -\eta^2 - \cdots - \eta^{p-1} \right)=p

We have g(\eta^{-1})=\sum_{j=0}^{p-1} \eta^{-j}\left(\frac{j}{p}\right) which is \sum_{j=0}^{p-1}\eta^{j}\left(\frac{-j}{p}\right)=\left(\frac{-1}{p}\right)g(\eta) so g(\eta)^2 = \left( \frac{-1}{p} \right) p = p^*.

At this point, we know that g(\eta)^2 = h(\eta)^2 = p^* so g(\eta) = \pm h(\eta). We know that h(\zeta) has the sign we want so, if we can prove (*), we win.

Proof of (*)

We already know that

g(\zeta) = \pm h(\zeta)

and, if we can show that the sign is +, we win. From now on, every occurrence of \pm 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 \mathbb{Z}[\zeta]/p \cong (\mathbb{Z}/p)[x]/(x-1)^{p-1}.”

We know that \zeta is a root of g(x) \mp h(x). Since x^{p-1} + \cdots + x+ 1 is irreducible, every \eta is a root of g(x) \mp h(x). (If you don’t know how to show that x^{p-1} + \cdots + x+ 1 is irreducible, here is an alternate route: show that g(\zeta^a) = \left( \frac{a}{p} \right) g(\zeta) and h(\zeta^a) = \left( \frac{a}{p} \right) h(\zeta) for any integer a not divisible by p. You might find Gauss’s lemma useful.) So x^p+\cdots+x+1 divides g(x) \mp h(x), say (x^p+\cdots+x+1) d(x) = g(x) \mp h(x). Since x^p-1 is monic, the coefficients of d(x) are integers and we can reduce this equation modulo p. Also, once we reduce modulo p, we have x^p-1=(x-1)^p so x^p+\cdots+x+1 \equiv (x^p-1)/(x-1) \equiv (x-1)^{p-1} \mod p. We conclude:

In (\mathbb{Z}/p)[x], we have g(x) \equiv \pm h(x) \mod (x-1)^{p-1}

We make the shift of variables x=1+u, and expand both sides in powers of u. 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 (1+u)^{-k/2}-(1+u)^{k/2} \equiv (-k) u \mod u^2. (This equation, like the many that will follow, takes place in (\mathbb{Z}/p)[u].) So

h(1+u) = (-1) (-2) \cdots (-(p-1)/2) u^{(p-1)/2} \mod u^{(p+1)/2}.

On the left hand side, we have

g(1+u) = \sum_{j=0}^{p-1} \sum_{r=0}^{p-1} \frac{j(j-1)\cdots (j-r+1)}{r!} u^r \left( \frac{j}{p} \right)

So the coefficient of u^r is \sum_{j=0}^{p-1} \frac{j(j-1)\cdots (j-r+1)}{r!} \left( \frac{j}{p} \right). It’s better to start by working out \sum_{j=0}^{p-1} j^d \left( \frac{j}{p} \right), 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 \sum_{j=0}^{p-1} j^d \equiv 0 for 0 \leq d < p-1, and \sum_{j=0}^{p-1} j^{p-1} \equiv -1 \mod p.

Proof: Set S=\sum_{j=0}^{p-1} j^d. Choose r in (\mathbb{Z}/p)^* so that r^d \not \equiv 1 \mod p. So r^d S \equiv S \mod p, and we conclude that S=0. As for \sum_{j=0}^{p-1} j^{p-1}, this is 0+1+1+\cdots+1 with p-1 ones.

Corollary: We have \sum_{j=0}^{p-1} j^d \left( \frac{j}{p} \right) \equiv 0 for 0 \leq d < (p-1)/2, and \sum_{j=0}^{p-1} j^{(p-1)/2} \left( \frac{j}{p} \right) \equiv -1 \mod p.

Proof: Combine the above lemma with Euler’s criterion.

So we see that the coefficient of u^d in g(1+u) is {0} for 0 \leq d < (p-1)/2 and the coefficient of u^{(p-1)/2} is (-1)/((p-1)/2)!.

Putting it all together, we have

(-1)/((p-1)/2)! u^{(p-1)/2} \equiv g(1+u) \equiv \pm h(1+u) \equiv

(-1)(-2)\cdots (-(p-1)/2) u^{(p-1)/2} \mod u^{(p+1)/2}.

So

\pm 1 \equiv (-1) (-1)(-2)\cdots (-(p-1)/2)(1)(2) \cdots ((p-1)/2) \equiv 1

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 g(\zeta) = h(\zeta) 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 (\mathbb{Z}/p)[x]. Finally, many of us have seen a lot of the above computations before: The computations of g(\zeta)^2 and h(\zeta)^2 appear at the start of various cyclotomic proofs of quadratic reciprocity, some of them found by Gauss; the computation of \sum_{j=0}^{p-1} j^r modulo p 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 h(\zeta)^2 = g(\zeta)^2=p^*, so we just have to get the sign in g(\zeta) = \pm h(\zeta). (2) Work p-adically or, equivalently, (1-\zeta)-adically.

When we transform an art into a science, we aim to replace inspiration by perspiration.

Concrete Mathematics, Graham, Knuth and Patashnik

Advertisements

8 thoughts on “The sign of the Gauss sum”

  1. 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 d, and the scalar by which the ribbon element acts \omega.

    Define the Gauss sum attached to C to be

    \sum_i \omega(X_i) d(X_i)^2.

    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.

  3. 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.

  4. Pingback: Computing Very Large Sums « Gödel’s Lost Letter and P=NP ~
  5. Pingback: Some quadratic reciprocity « Annoying Precision ~

  8. 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.

Comments are closed.