I think I’m going to use this blog mostly to write up elegant ideas that I don’t think are well enough known and various computations that I do in the course of trying to learn new things. Last week, John Baez started a conversation on why quadratic reciprocity works. That didn’t really take off, so I’m going to write some more thoughts over here.

Quadratic reciprocity is the following theorem, first proven by Gauss: Let p be an odd prime and let a be an integer not divisible by p. Define (a/p) to be 1 if a is a square modulo p and -1 otherwise. (The standard notation is to write (a/p) as an upright fraction, with a horizontal bar, but I’m trying to minimize the number of LaTeX equations you have to load.) Then, if p and q are both (positive) odd primes, we have

$(p/q)(q/p)=(-1)^{(p-1)(q-1)/4}.$

For example, 5 is a square modulo p if and only if p is 1 or 4 modulo 5. The number 3 is a square modulo p if and only if p is 1 or 11 modulo 12. In general, for any given odd integer a, we can use the law of quadratic reciprocity to give a simple rule for deciding whether or not a is a square modulo p. This rule will depend only on the residue class of p modulo a if a is 1 mod 4, or on the class of p modulo 4a if a is 3 modulo 4. Everything I have said is perfectly valid when a is negative, by the way.

To my mind, the amazing part of QR is that (a/p) should be periodic at all as a function of p. Of course, strictly speaking it doesn’t make sense to say that (a/p) is periodic because it is only defined for prime p. So here is a better statement. Let a and b be any relatively prime odd integers, with b positive. Let $b=p_1 p_2 \cdots p_r$ be the factorization of b into odd primes. Then define (a/b) as $(a/p_1) (a/p_2) \cdots (a/p_r)$. Then, to my mind, the essence of QR is the theorem that (a/b) is periodic as a function of b, with period either a or 4a (depending on whether a is 1 or 3 modulo 4.) Once we know this, deducing the precise form of QR is not bad. I’ll do the case where q is a prime which is 1 modulo 4. The function $b \mapsto (q/b)$ must be a function on $(\mathbb{Z}/p)^*$ (by the periodicity claim) which takes only the values $\pm 1$ and which is multiplicative. Other than the function which is identically 1, it turns out that $b \mapsto (b/q)$ is the only option, so $(q/b)=(b/q)$. (Actually, I don’t know a simple proof that $(q/b)$ is not identically one as a function of b, but I don’t regard this as the hard step.) A slightly messier but similar argument works when q is 3 modulo 4.

So, why does this periodicity hold? To my mind, we don’t really have a good answer. There are many proofs. One of the cleanest elementary proofs (due to Zolotarev) is to notice that (a/b) is the sign of the permutation induced on the residue classes of $\mathbb{Z}/b$ under multiplication by a. One then adapts Eisenstein’s proof to work with the possibility of a composite number in the base. But I don’t feel that any of these proofs are really an explanation.

However, there is a principle in number theory that, if you can’t understand a property of the integers, you should think about the corresponding property for polynomials over finite fields. In this case, the corresponding property is the following. Let p be an odd prime and let $f[t]=f_0 t^d+\cdots+f_{d-1} t+f_d$ be a polynomial with coefficients in $\mathbb{Z}/p$. Define $|f|=p^d$. Then, if f and g are relatively prime monic polynomials in $\mathbb{Z}/p[x]$, we have

$(f/g)(g/f)=(-1)^{(|f|-1)(|g|-1)/4}$

The condition that f and g are monic should be thought of as analogous to the condition that p and q are positive back in ordinary QR. This theorem has a beautiful geometric proof. As above, I won’t actually write out all of the details, but I’ll get you far enough to see that (f/g) should have some sort of periodicity as a function of g.

Some shorthand is in order. Let k denote $\mathbb{Z}/p$ and let K denote the algebraic closure of k. Also, $K^*$ will be the unit group of K. There is a map $K \to K$ called the Frobenius map, which we will denote by F, given by $F(x)=x^p$. Note that k is exactly the fixed point set of F. If x is in k and $y \in K$ is any square root of x, then (x/p) is $F(y) y^{-1}$. More generally, let $g \in k[x]$ be an irreducible polynomial of degree d and let $f \in k[x]$ be relatively prime to g. Let $a \in K$ be a root of g and let b be a square root of f(a). Then $(f/g)=F^d(b) b^{-1}$. (Use the isomorphism between k[x]/g and the subfield of K generated by k and a.)

Here is a more geometric way to think of this. Let X, Y and G all denote $K^*$. This may seem silly, but $K^*$ is actualy playing three roles here, and I want to seperate them. We have a map $X \to Y$ given by $u \mapsto u^2$, this is a two-fold cover. The map F acts on both X and Y, compatibly. Let U denote the subset of K where f is not zero. Then we map U to Y by $a \mapsto f(a)$. Now, suppose that a, an element of U, is a root of the irreducible polynomial g of k[x]. Then the roots of g are $a$, $F(a)$, $F^2(a)$, …, $F^{d-1}(a)$. So the orbit of F acting on f(a) (which is a point of Y) is a cycle of length d. The preimage of this cycle up in X has cardinality 2d. The action of F on this preimage is either two cycles of length d, in which case (f/g) is 1, or is one cycle of length 2d, in which case (f/g) is -1.

This suggests a definition. X is a principal homogenous space for the action of G. For any a in U, define an element [f/a] of G by $[f/a]=F(b) b^{-1}$, where b is any square root of f(a). Note that this is independent of the choice of b. This can be seen by direct computation; the conceptual argument is that the two square roots of f(a) are related by multiplication by the element -1 of G, the group G is abelian and F(-1)=-1. We then have
$(f/g)=(f/\prod_{i=0}^{d-1} (x-F^i(a)) )=\prod_{i=0}^{d-1} [f/F^i(a)].$
(Plug in the definition of [f/F^i(a)] and watch the sum telescope.) We then obtain immediately from the definitions that, even if g is not irreducible in k[x], we have
$(f/g)=\prod_{i=0}^{d-1} [f/a_i]$
where $g(x)=(x-a_0)(x-a_1) \cdots (x-a_{d-1})$ is the factorization of g in K[x].

Now, here is the geometric statement we will prove. Let U be any subset of K with a finite complement and let s be a map from U to G given by a rational function. Then there exists a polynomial m with the following property: If $g=\prod_{i=0}^{d-1} (x-a_i)$ and $g'=\prod_{i=0}^{d-1} (x-a'_i)$ are two polynomials of the same degree which are nonzero at the points of K-U and if $g=g' \mod m$ then $\prod_{i=0}^{d-1} s(a_i)=\prod_{i=0}^{d-1} s(a'_i)$. Moreover, we can choose m to only have roots on the complement of U. Applying this theorem to $s(a)=[f/a]$ will tell us that (f/g) has some sort of periodicity in terms of the degree of g and the value of f modulo some power of g; as before, getting the exact form of (f/g) at this point is relatively easy. This is a good point to pause and make sure you have understood everything.

Notice that this statement makes complete sense when K is the complex numbers (and G the nonzero complex numbers.) Moreover, when K is the complex numbers, it is natural to think of U not as an open subset of the complex plane but as an open subset of the Riemman sphere. In this context, the two conditions that g and g’ have the same degree and that they have no zeroes in K-U are really the same condition — that g and g’ have poles of the same order at each point in the complement of U or, in other words, that the meromorphic function g/g’ is well defined in the complement of U. From now on, I’ll state things in terms of the complex numbers. If you want to know how to make this argument rigorous back in the original finite field setting, you should learn algebraic geometry. (Really, you should learn algebraic geometry. If you have been enjoying and understanding up to this point, you’ll find algebraic geometry beautiful.)

So, here is the right formulation. Let $U = \mathbb{CP}^1 \setminus \{ z_1, \ldots, z_r \}$ be a subset of the Riemann sphere with finite complement. Let s be a map from U to $\mathbb{C}^*$ given by a rational function. Then we can assign an integer $c_i$ to each point $z_i$ of the complement of U such that the following holds — if h is a meromorphic function on $\mathbb{CP}^1$ which, near $z_i$, is equal to 1 to order $(z-z_i)^{c_i}$ then $\prod s(b_i)^{e_i}=1$ where $b_i$ are the zeroes and poles of h on U and $e_i$ is the order of the pole $b_i$.

There are lots of proofs of this theorem in the complex world, and I urge you to try to find one. Here is a proof which will generalize to the finite field case. Let $\omega$ be the pull back to U of the differential form $dz/z$ on $G=\mathbb{C}^*$. Then $\omega$ is a meromorphic differential form on all of $\mathbb{CP}^1$ which is holomorphic on U. Take $c_i$ to be one more than the order of the pole of $\omega$ at $z_i$. Now, consider the meromorphic map $\phi: \mathbb{CP}^1 \to G$ given by $\phi(t) = \prod_{h(u)=t} s(u)$. We want to show that $\phi(0)=\phi(\infty)$. Now $\phi^* \omega$ is holomorpic everywhere except at the points $h(z_i)$ (where i runs from 1 to r). By our hypothesis on h, all of these points are 1. But a local computation at 1 shows that $\phi^* \omega$ is also holomorphic there. So $\phi^* \omega$ is a global holomorphic one-form, and hence is zero. Then $\phi$ is a constant map, and we are done.

I’m not sure who first worked out this idea, but Serre in his elegant little book Algebraic Groups and Class Fields presents a huge generalization of it. Basically, for any abelian extension of k[x], Serre shows how to build G, X and Y (which will no longer all be the same) and run this argument. I am basically simplifying Serre’s argument for the special case of quadratic extensions here; the reader who wants to see the original should read Serre, particularly sections VI.2.8 and III.2.