One sum, squared two ways

Every proof of reciprocity so far on this ladder has counted something: lattice points below a diagonal, folds in a strip of residues, cycles in a shuffle. This one adds up complex numbers, and it is the proof that leaves the integers behind.

Fix an odd prime $p$, let $\zeta = e^{2\pi i/p}$, and define

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

Half the terms are added and half are subtracted, and which half is decided by whether the index is a square modulo $p$. There is no obvious reason for that sum to be anything in particular. It is $\sqrt{p}$, or $i\sqrt{p}$, and which of the two is decided by $p$ modulo four.

Why the walk closes where it does #

The claim to establish first is about $g^2$, and the argument is a change of variable rather than a computation.

$$g^2 = \sum_{m}\sum_{n} \left(\frac{m}{p}\right)\left(\frac{n}{p}\right)\zeta^{m+n}.$$

Substitute $n = mt$, which is legitimate because $m$ is invertible and $t$ then ranges over all non-zero residues as $n$ does. The symbol is multiplicative, so $\left(\frac{m}{p}\right)\left(\frac{mt}{p}\right) = \left(\frac{m^2 t}{p}\right) = \left(\frac{t}{p}\right)$, and the exponent becomes $m(1+t)$:

$$g^2 = \sum_{t}\left(\frac{t}{p}\right)\sum_{m}\zeta^{m(1+t)}.$$

The inner sum is $p-1$ when $t \equiv -1$, since every term is then $\zeta^0$, and it is $-1$ otherwise, because the full sum of all $p$ powers of $\zeta$ is zero and the $m=0$ term is missing. So

$$g^2 = \left(\frac{-1}{p}\right)(p-1) - \sum_{t \neq -1}\left(\frac{t}{p}\right) = \left(\frac{-1}{p}\right)p,$$

using that the symbols over all non-zero $t$ sum to zero, half being $+1$ and half $-1$.

The whole derivation is one substitution and one fact about roots of unity, and the fact — that the $p$ non-trivial powers of $\zeta$ sum to $-1$ — is the statement that a regular polygon’s corners have their centre at the origin.

The sign Gauss could not get #

So $g^2 = \pm p$, and therefore $g$ is one of $\pm\sqrt{p}$ or $\pm i\sqrt{p}$. The square says nothing about which.

Gauss determined the sign in 1801 and it took him four years. The answer is that $g = \sqrt{p}$ when $p \equiv 1 \pmod 4$ and $g = i\sqrt{p}$ when $p \equiv 3 \pmod 4$ — always the positive root, never the negative one. In a letter of 1805 he wrote that the problem had tormented him and that the resolution arrived, as such things do, unbidden.

The figures here compute the walk directly and land on the right point, which is evidence rather than proof: a walk of twelve steps confirms $p=13$ and says nothing about $p = 10^6 + 3$. What the generator does assert is the part that is provable in three lines — that $|g|^2 = p$ and that $g^2$ has the right sign — and it says so rather than claiming the harder half.

Reciprocity, from evaluating one number twice #

The reason this construction proves the law is that $g^p$ can be computed in two ways.

Working modulo $q$ — that is, in a ring where $q$ has been set to zero, which is legitimate because everything in sight is an algebraic integer — the map $x \mapsto x^q$ is additive, since the binomial coefficients in between are all divisible by $q$. So

$$g^q \equiv \sum_n \left(\frac{n}{p}\right)\zeta^{nq}.$$

Substituting $m = nq$ and using multiplicativity again turns the right-hand side into $\left(\frac{q}{p}\right)g$.

On the other hand $g^q = g \cdot (g^2)^{(q-1)/2} = g\left(\left(\frac{-1}{p}\right)p\right)^{(q-1)/2}$, and by Euler’s criterion that last factor is congruent to $\left(\frac{(-1)^{(p-1)/2}p}{q}\right)$ modulo $q$.

Cancelling $g$, which is invertible because $g^2 = \pm p$ and $p \neq q$:

$$\left(\frac{q}{p}\right) = \left(\frac{(-1)^{(p-1)/2}p}{q}\right) = \left(\frac{-1}{q}\right)^{(p-1)/2}\left(\frac{p}{q}\right),$$

and the first factor is $(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$ by the first supplement. Rearranged, that is the law.

What the computation actually used #

Three things, and it is worth listing them because each is a different kind of ingredient.

The symbol is multiplicative. That came from the cyclic structure of the residues and is used twice, once in each substitution.

The powers of $\zeta$ sum to zero. That is geometry — the corners of a regular polygon balance — and it is what makes the inner sum collapse.

Raising to the $q$-th power is additive modulo $q$. That is the freshman’s dream, true in characteristic $q$ and false everywhere else, and it is the step no counting proof has an analogue of.

The third is the one that makes this proof generalise. Counting lattice points is a technique with a ceiling; working in a ring of characteristic $q$ and using that the $q$-th power map is a homomorphism is the beginning of a subject.

The sum as a shape #

The walks are worth looking at as pictures rather than only as computations, because they have a structure the algebra does not mention.

Each is made of $p-1$ unit steps at angles $2\pi n/p$, and the sign attached to each step means the walk goes round the circle of directions taking every other one forward and every other one backward, in the pattern of the squares. The pattern of squares modulo $p$ is not periodic in any simple way, so the walk is not a polygon and not a spiral; it wanders and returns.

What is fixed is the endpoint. Whatever the shape of the excursion, it finishes at distance $\sqrt{p}$ from where it began, and along one of two axes. A picture where the intermediate points look arbitrary and the last one does not is a good picture of a theorem: the content is in the destination.

These curves are not the ones usually shown. The famous Gauss-sum picture is of the partial sums of $\sum \zeta^{n^2}$, which trace out a curve of spirals and straight runs and were studied for their own sake. The walk here is a close relative — the two sums are equal, since $\sum_n \zeta^{n^2}$ counts each square residue twice and adds $\zeta^0$ — and the drawing is different because the terms are taken in a different order.

Why the two sums are the same #

That identity is worth doing, since it explains why the literature’s sum and this page’s are interchangeable.

$$\sum_{n=0}^{p-1}\zeta^{n^2} = \sum_{a} \#\{n : n^2 \equiv a\}\,\zeta^a.$$

The count is $1$ for $a = 0$, $2$ for a non-zero square, and $0$ for a non-square — which is exactly $1 + \left(\frac{a}{p}\right)$. So the sum is

$$\sum_a \left(1 + \left(\frac{a}{p}\right)\right)\zeta^a = 0 + g,$$

because the first part sums all $p$ roots of unity to zero. The two sums agree exactly, and the choice between them is a choice of which computation to make visible.

A worked evaluation, at five #

Small enough to do by hand. Modulo five the squares are $1$ and $4$, and the non-squares are $2$ and $3$. So

$$g = \zeta + \zeta^4 - \zeta^2 - \zeta^3$$

with $\zeta = e^{2\pi i/5}$. The pairs are conjugate, so $\zeta + \zeta^4 = 2\cos(2\pi/5)$ and $\zeta^2 + \zeta^3 = 2\cos(4\pi/5)$, and both are real. Numerically $2\cos(2\pi/5) = 0.618\ldots$ and $2\cos(4\pi/5) = -1.618\ldots$, so $g = 0.618 + 1.618 = 2.236\ldots$, which is $\sqrt{5}$.

Those two cosines are the golden ratio and its negative reciprocal, which is not a coincidence: they are the two roots of $x^2 + x - 1 = 0$, the quadratic whose roots are Gauss’s periods for $p = 5$. The Gauss sum is their difference, and the difference of the roots of a quadratic is the square root of its discriminant — here $\sqrt{1 + 4} = \sqrt 5$.

That is the general mechanism in its smallest case. The Gauss sum is the difference between the sum of the square roots of unity and the sum of the non-square ones, those two sums are the roots of a quadratic with integer coefficients, and $g^2 = \pm p$ says the discriminant of that quadratic is $\pm p$.

The sum is a Fourier transform of itself #

There is a second reason this particular sum is the one everybody studies, and it has nothing to do with reciprocity.

The Legendre symbol, read as a function on the residues modulo $p$, is one of the $p-1$ multiplicative characters of that group, and the Gauss sum is exactly its discrete Fourier transform evaluated at one point. More is true: the symbol is its own transform up to the factor $g$. Transforming the function $n \mapsto \left(\frac{n}{p}\right)$ returns the same function multiplied by $g$, which makes the symbol an eigenvector of the transform and $g$ its eigenvalue.

That is why the absolute value comes out at $\sqrt{p}$ rather than at anything else. The discrete transform on $p$ points scales lengths by $\sqrt{p}$, so any eigenvector has an eigenvalue of that size, and $|g| = \sqrt{p}$ is a statement about the transform rather than about squares. The theorem that took three lines above is, from this angle, a special case of a conservation law: the transform preserves total energy, and an eigenvector’s eigenvalue has to have modulus matching the scaling.

Two subjects agreeing on a number is usually a sign they are the same subject. The discrete transform on the residues modulo $p$ and the arithmetic of squares modulo $p$ are built from the same group, and every fact about one is a fact about the other written in different notation. The Gauss sum is the dictionary entry that gets used most.

Where the quadratic field comes in #

The last observation is the door out of elementary number theory, and it is worth opening a crack.

The sum of the square roots of unity and the sum of the non-square ones both lie in the field generated by $\zeta$, and each is fixed by every element of that field’s symmetry group that squares things — so both live in a subfield of index two. That subfield is $\mathbb{Q}(\sqrt{p^*})$ where $p^* = (-1)^{(p-1)/2}p$, and $g = \sqrt{p^*}$ is the element that generates it.

So the Gauss sum is a bridge: it exhibits the quadratic field $\mathbb{Q}(\sqrt{p^*})$ sitting inside the cyclotomic field $\mathbb{Q}(\zeta_p)$. Reciprocity, in the language that grew out of this, is the statement that every quadratic field sits inside a cyclotomic one — and Kronecker and Weber later proved the same is true of every field with abelian symmetry group whatever.

That is what makes this proof the important one. The lattice count is a beautiful argument that ends where it starts. This one names an object that turns out to be the first case of a general theory, and it names it in the course of proving something elementary.

Four years for a sign, and what that says about the subject #

The chronology of this one result is unusually well documented, because Gauss kept a diary.

He had the theorem $g^2 = \pm p$ by 1801, when the Disquisitiones appeared, and he needed the sign for his fourth proof of reciprocity. He computed the sum numerically for many primes, saw the pattern immediately, and could not prove it. The diary entry recording the eventual proof is dated 30 August 1805, and the accompanying letter to Olbers describes four years of trying every week without success, and then the answer arriving all at once, unconnected to anything he had been doing.

What is worth taking from that is not the anecdote but the difficulty ratio. The square of the sum takes three lines. The sign of the sum took the best analyst of the age four years. The two statements look equally hard from outside and are not remotely: one is an algebraic identity that any manipulation will produce, the other is a determination of a branch, and determining branches is a different kind of problem with a different kind of proof.

Modern proofs of the sign go through a limiting argument, or through the analytic behaviour of theta functions, or through counting eigenvalues of the discrete transform — and all of them import machinery from outside the algebra. That, rather than Gauss’s persistence, is the lesson: an algebraic identity leaves a sign undetermined precisely because algebra cannot see order, and settling it needs an ingredient that can.

The pattern repeats throughout this subject. The existence of a solution is often much easier than the size of one; the fact that something is a square is easier than exhibiting the root; and a magnitude is easier than an argument. Where a proof stops is usually where the technique stops seeing.

What the picture cannot show #

The sign is asserted and not proved. The figures compute the walk for one prime at a time and find the positive root, at every prime they are drawn for. Gauss’s four years were spent on the statement that this always happens, and nothing in a picture of one walk bears on it.

The proof of the law happens in a ring the picture does not contain. Working modulo $q$ inside the algebraic integers is where reciprocity comes from above, and there is no drawing of it: the objects are congruence classes of algebraic numbers, and a plane figure of the walk lives in the complex numbers with no congruence in sight.

And the walks are only drawn small. At $p = 5$ every step is visible; at $p = 43$ the excursion is a tangle. The theorem is about all primes and the pictures stop where legibility does.

What such sums are actually used for #

Reciprocity is the historical reason for the Gauss sum and not the main modern one. The main one is counting.

Ask how many pairs of residues satisfy an equation modulo $p$ — say $x^2 + y^2 \equiv 1$, or $y^2 \equiv x^3 + 1$. The count is close to $p$, because a curve through a grid of $p^2$ points meets about $p$ of them, and the interesting quantity is the error. Writing the number of square roots of a residue as $1 + \left(\frac{a}{p}\right)$, exactly as the identity between the two sums did above, turns the count into a sum of Legendre symbols, and a sum of Legendre symbols against a character is a Gauss sum or a close relative called a Jacobi sum.

The consequence is a bound. Since $|g| = \sqrt{p}$, the error in the count is of size $\sqrt{p}$ rather than of size $p$ — and that single fact, in its general form, is the Weil conjecture for curves. The square root that took Gauss four years to sign is the square root in every modern estimate of how many solutions an equation has modulo a prime.

The smallest instance is worth carrying because it can be checked by hand. The number of solutions of $x^2 + y^2 \equiv 1$ modulo a prime $p \equiv 1 \pmod 4$ is exactly $p - 1$, and modulo $p \equiv 3 \pmod 4$ it is exactly $p + 1$ — a discrepancy of one either way, decided by the same congruence that decides the first supplement. The circle over a finite field remembers whether $-1$ is a square, and it is the only thing about the field it remembers.

That is the shape of the whole business. A count that is nearly what it should be is uninteresting; the error term is where the arithmetic is, and the Gauss sum is the object that measures it.

Where it fails, and what it needs #

The sum is quadratic and the pattern does not simply continue. The obvious generalisation replaces the Legendre symbol with a cubic or quartic character, and the resulting sums do have absolute value $\sqrt{p}$ — but their arguments are not determined by any congruence, and the corresponding higher reciprocity laws need the cubic or quartic residue symbol to be defined over $\mathbb{Z}[\omega]$ or $\mathbb{Z}[i]$ rather than over $\mathbb{Z}$.

The proof needs $p$ and $q$ distinct and odd. The step cancelling $g$ requires $g$ invertible modulo $q$, which needs $q \nmid p$. The supplements are outside this argument for the same reason they are outside the lattice one.

And the sum is over a prime modulus. For composite $n$ the analogous sum can vanish, and the theory of when it does is a subject with its own name.

Where the ladder goes next #

The last rung asks what all this is for, and the answer turns out not to be about squares at all. Which primes a quadratic form represents is decided by a congruence condition exactly when the relevant class group is small enough, and reciprocity is the first and easiest case of that. The Gauss sum is the object the general theory is built on, and the last rung is where it is pointed at something.

Sideways: the cyclotomic polynomial is the algebra behind the roots of unity used throughout, and the sign of a shuffle is the previous rung’s completely different route to the same law.

What is worth carrying away #

An identity between two evaluations of one quantity is worth more than either evaluation.

Nothing here computes anything hard. $g^2 = \pm p$ takes a substitution; $g^q$ takes the freshman’s dream. What produces a theorem is that the two are computations of the same number, so setting them equal says something neither said alone.

And the object outlives the proof. The lattice-point argument proves reciprocity and stops. The Gauss sum proves reciprocity and then turns out to be the element exhibiting one field inside another, which is the beginning of class field theory. When a proof introduces a new object rather than a new count, the object is usually the part that lasts.