Quadratic reciprocity: the game

Alice: Fine, but I want to move first.
Bob: What? This is my game!
A: Precisely! I’m sure you have figured out the strategy to win by now, so let me at least enjoy the game for a little bit.
B: Alright, fine. Are you sure you’ve got all the rules?
A: It’s not like there are too many of them.
B: So we first agree on the number of moves q and another number p.
A: Sure enough. Then I choose a number x_1 and take its square…
B: …then I choose another number x_2 and add its square to yours…
A: …and we just keep adding squares, summing q of them in total.
B: That’s right, and you want to prevent the total sum from being a multiple of p.
A: It doesn’t sound like a very exciting game, I don’t really think I want to play it.
B: Really? Not even once?
A: I mean, that’s just adding numbers! And after all, shouldn’t we be sending encrypted messages to each other or something instead of playing games?
B: You know, cryptography can be a bit like a game as well… either way, I just wanted to do something else for one. What should I do with the game now? Just forget about it?
A: If you care about your game so much we can try to work something out with it without playing it.
B: I don’t know why you don’t want to play so much, but I like the idea. So, do you want to work out the winning  strategy?
A: Hmm, that’s what everyone would do… how about the number of possible plays?
B: Well, we can choose arbitrary integers… but everything only matters modulo p, so I guess we can count possibilities that way.
A: We clearly have p possible choices for each x_i, so there are p^q possible plays. Now, how many of these are wins for me?
B: So basically we are counting solutions to

x_1^2+\dots+x_q^2\equiv 0\pmod p.

A: Congruences are always nicer with prime number modulus… can we assume that the number which we have conveniently happened to call p is a prime?
B: Sure, let’s even say it’s an odd prime. But still, how could we approach this?
A: Let’s try induction. Everything can be proven by induction, right?
B: We’ll see… Base case seems easy, so let’s get to the induction step right away.
A: Say I have chosen some number x_1. Number of solutions with this x_1 is the same as the number of solutions of

x_2^2+\dots+x_q^2\equiv -x_1^2\pmod p,

but this congruence has something else on the right hand side than zero…
B: True. I’m afraid we will have to deal with a more general problem if we want induction to work. So I think we should consider the number of solutions to the congruence

x_1^2+\dots+x_q^2\equiv a\pmod p.

A: Let’s give it a name, say we will call it N_q(a). But then even the case with one variable seems less trivial…
B: Yeah, there probably won’t be any simple expression which is 1 on zero, 2 on all other squares modulo p and 0 on nonsquares.
A: Wait, actually, if you were to subtract 1 from each of these numbers, we get expression which is 0 on zero, 1 on squares and -1 on nonsquares. This is precisely the Legendre symbol!
B: Ah! So we can say that N_1(a)=1+\left(\dfrac{a}{p}\right).
A: This gave me an idea. To find N_q(a) we can consider all tuples satisfying t_1+\dots+t_q=a, and then consider in how many ways these t_i can be replaced with squares.
B: If I understand correctly, what you are saying can be expressed as

N_q(a)=\displaystyle\sum_{t_1+\dots+t_q=a}N_1(t_1)\dots N_1(t_q)=\sum_{t_1+\dots+t_q=a}\left(1+\left(\dfrac{t_1}{p}\right)\right)\dots\left(1+\left(\dfrac{t_q}{p}\right)\right),

the t_i being taken modulo p, of course.
A: This gives us some expression for this number, but I suppose we both want something more “closed form”. This mess would be horrible to compute. Just imagine expanding this product!
B: Yeah, it would probably… actually, wait a moment. There will be a lot of cancellation in that sum. For example, consider the term \left(\dfrac{t_1}{p}\right)\dots\left(\dfrac{t_{q-1}}{p}\right) in the expanded product. In the sum, we can choose t_1,\dots,t_{q-1} independently and then we have unique choice of t_q. So when summing, this term contributes

\displaystyle \sum_{t_1,\dots,t_{q-1}}\left(\dfrac{t_1}{p}\right)\dots\left(\dfrac{t_{q-1}}{p}\right)=\left(\sum_{t_1}\left(\dfrac{t_1}{p}\right)\right)\left(\sum_{t_2,\dots,t_{q-1}}\left(\dfrac{t_1}{p}\right)\dots\left(\dfrac{t_{q-1}}{p}\right)\right)=0

since there is the same number of quadratic residues as nonresidues modulo p, so the first sum is zero.
A: That’s excellent! So we are only left with sums over 1 and over product of all the Legendre symbols. The ones are easy to count, so we are left with

N_q(a)=p^{q-1}+\displaystyle\sum_{t_1+\dots+t_q=a}\left(\dfrac{t_1}{p}\right)\dots\left(\dfrac{t_q}{p}\right)=p^{q-1}+\sum_{t_1+\dots+t_q=a}\left(\dfrac{t_1\dots t_q}{p}\right).

B: Multiplicativity of Legendre’s symbol is very useful; at the very least it reduces the number of brackets. Do you think there will be such a cancellation in the last sum as well?
A: I guess so; the p^{q-1} term is probably dominating. We can try grouping the terms in which the t_i are the same, just permuted. For example if we group the q terms corresponding to a cyclic permutation of t_1,\dots,t_q
B: Wait, there might be less than q of them if some of the t_i are equal.
A: Oops, true. But the number of such terms will certainly divide q. So if q happened to be prime, then there would be either one such term, which means that all t_i are equal, or exactly q of them… if we were to look modulo q, the latter terms would cancel out, so we can say

N_q(a)\equiv p^{q-1}+\displaystyle\sum_{qt\equiv a\pmod p}\left(\frac{t^q}{p}\right)\pmod q.

If p,q are distinct odd primes, then qt\equiv a\pmod p has a unique solution modulo p, so then

N_q(a)\displaystyle\equiv 1+\left(\frac{t^q}{p}\right)\equiv 1+\left(\frac{t^qq^{q+1}}{p}\right)\equiv 1+\left(\frac{a^qq}{p}\right)\equiv 1+\left(\frac{a}{p}\right)\left(\frac{q}{p}\right)\pmod q.

Isn’t that cool?
B: I suppose it is, but we want to find exact value of N_q(a), so working modulo q won’t help us, especially for when q is not prime. Maybe we should try to go back to induction?
A: Alright. But I still think that it’s cool to consider the number of solutions of an equation modulo p modulo q.
B: For q=1 the number of solutions clearly only depends only on whether a is zero, a quadratic residue or a nonresidue. I think the same should be true for larger q: if we have two nonzero squares b^2,c^2, then from a solution

x_1^2+\dots+x_q^2\equiv b^2\pmod p

of one equation to a solution

\displaystyle\left(\frac{x_1c}{b}\right)^2+\dots+\left(\frac{x_qc}{b}\right)^2\equiv c^2\pmod p

of another equation.
A: This gives a bijection! So we can say that numbers N_q(a) are the same for all nonzero squares! Also, a ratio of nonresidues is a residue, so we can do pretty much the same thing for nonsquares!
B: So it might be useful to somewhat forget about the number a and just think about whether it is or not a square. So we can let \square be a placeholder for a squares, so that N_q(\square) is a well-defined number…
A: …and we can also have N_q(\triangle) for nonsquares!
B: Wait, why a triangle?
A: Because it’s not a square.
B: …fair enough.
A: Oh! We can also have…
B: We are not using \bigcirc in place of 0.
A: …fine. Anyways, let’s try to find out something about N_{q+1}(0). First of all, x_1 might be zero.
B: In this case, x_2^2+\dots+x_{q+1}^2\equiv 0\pmod p. We know how many solutions this has – it’s N_q(0).
A: Good, now let’s see what happens if x_1 is nonzero. For equality to hold, x_2^2+\dots+x_{q+1}^2 must be -x_1^2. Is this a quadratic residue or a nonresidue?
B: It depends on whether -1 is a square or not. Thankfully we have the Euler’s criterion, which tells us that it’s a square precisely when p\equiv 1\pmod 4.
A: Oh god, we split into cases. Wonderful.
B: So if p\equiv 1\pmod 4, then for any nonzero x_1 we want x_2^2+\dots+x_{q+1}^2\equiv\square\pmod p, so we get N_{q+1}(0)=N_q(0)+(p-1)N_q(\square).
A: For p\equiv 3\pmod 4 we get N_{q+1}(0)=N_q(0)+(p-1)N_q(\triangle). So we are done with N_{q+1}(0) for now.
B: I think we are, though I have a feeling this was the easy part. So now let’s take a look at N_{q+1}(\square). If x_1=0, then we easily see that there are N_q(\square) solutions, so let x_1\neq 0.
A: Now we have x_1^2+(x_2^2+\dots+x_{q+1}^2)\equiv\square\pmod p, so we want x_2^2+\dots+x_{q+1}^2\equiv\square-x_1^2\pmod p. But we don’t know whether \square-x_1^2 is a square or not!
B: It sometimes is and sometimes isn’t, I’m afraid, and sometimes it’s zero. We should figure out how many times \square-x_1^2 is zero, square and nonsquare.
A: Clearly it’s zero for two values of x_1. So now how often is a difference of squares a square or nonsquare… I think we might quickly get lost with all these squares; we should give some names to these numbers.
B: You have defined last piece of notation, so now it’s my turn. Let’s say X_{1,1;a} is the number of solutons modulo p to b+c=a with b and c both quadratic residues, X_{1,-1;a} the number…
A: Why don’t you use squares and triangles?
B: Fine. X_{\square,\square;a} is what I’ve said, X_{\square,\triangle;a} is the same thing with b residue and c nonresidue and so on.
A: Now this is some notation I like!
B: Anyways, like we had with N_q(a), this quite clearly only depends on a being zero, a square or a nonsquare, so we can define X_{\square,\triangle;\square} and what not.
A: So now we have to figure out values of these numbers. Counting in X_{\square,\square;0} and others we have 12 unknowns. There are some obvious relations between these numbers, like

\displaystyle X_{\square,\triangle;a}=X_{\triangle,\square;a}.

B: Ones with a=0 should be easy to find. If we have b+c=0, so b=-c, we see that, depending on p modulo 4
A: Can we please focus on just one case modulo 4 for now? There are already enough numbers laying around.
B: Alright, for p\equiv 1\pmod 4 we see that b is quadratic residue iff c is, so from that we get

\displaystyle X_{\square,\square;0}=X_{\triangle,\triangle;0}=\frac{p-1}{2},X_{\square,\triangle;0}=0.

A: Also, if we consider all possible sums of b,c quadratic residues, and on the other hand we count X_{\square,\square;a} for all a, we will find

\displaystyle\frac{p-1}{2}X_{\square,\triangle;\square}+\frac{p-1}{2}X_{\square,\triangle;\triangle}+X_{\square,\triangle;0}=\left(\frac{p-1}{2}\right)^2,

so, as X_{\square,\square;0}=0, dividing by \frac{p-1}{2} we get

\displaystyle X_{\square,\triangle;\square}+X_{\square,\triangle;\triangle}=\frac{p-1}{2}.

B: Also, similarly,

\displaystyle X_{\square,\square;\square}+X_{\square,\square;\triangle}+1=\frac{p-1}{2}.

This looks like we’re getting somewhere. Hmm, when we were multiplying formulas by ratio of two squares or nonsquares, we could show that X_{\cdot,\cdot;a} is the same for all squares or for all nonsquares a. What if we tried to multiply by a ratio of a square and a nonsquare?
A: The result would be a nonsquare, so it’d flip the character of all terms… so this gives us another bijection! We have from this that swapping squares and triangles gives the same number! So for example, X_{\square,\triangle;\triangle}=X_{\triangle,\square;\square}=X_{\square,\triangle;\square}. But wait, plugging that into my last equation, we can see

\displaystyle X_{\square,\triangle;\square}=\frac{p-1}{4}!

B: Now this is real progress! So we can figure out all of X_{\square,\triangle;a}. Now we have to relate these to other variables. Counting the solutions to equation a=b+c with constrained b,c worked before, so we can try restricting a to be a square as well. If we take, say, b to also be a residue and c to be a nonresidue, then we easily get \frac{p-1}{2}X_{\square,\triangle;\square}.
A: Note that we can rewrite a=b+c as a+(-c)=b. But -c is a quadratic residue whenever c is, so we can in essentially the same way see that the number of solutions is \frac{p-1}{2}X_{\square,\square;\triangle}. So we must have

\displaystyle X_{\square,\triangle;\square}=X_{\square,\square;\triangle}.

B: This is just what we needed! We can now figure out all the variables:

\displaystyle X_{\square,\square;\square}=\frac{p-5}{4},X_{\square,\triangle;\square}=X_{\square,\square;\triangle}=\frac{p-1}{4},X_{\square,\triangle;0}=0;X_{\square,\square;0}=\frac{p-1}{2}

and the rest can be easily figured out by swapping squares and triangles.
A: We get quite similar results for p\equiv 3\pmod 4:

\displaystyle X_{\square,\square;\square}=X_{\square,\triangle;\square}=\frac{p-3}{4},X_{\square,\square;\triangle}=\frac{p+1}{4},X_{\square,\triangle;0}=\frac{p-1}{2};X_{\square,\square;0}=0.

B: You are incredibly fast at mental algebra I see.
A: Now that we have figured out these values, we can finally… what did we need these values for again?
B: We are given a square \square and we need to figure out for how many x_1, in the equation x_1^2+(x_2^2+\dots+x_{q+1}^2)=\square the second summand is square or a nonsquare.
A: Ah, right. If p\equiv 1\pmod 4, exactly for X_{\square,\square;\square}=\frac{p-5}{4} values of x_1^2, so for \frac{p-5}{2} values of x_1, that summand has to be a square, which it can be in N_q(\square) ways.
B: And for 2X_{\square,\triangle;\square}=\frac{p-1}{2} values of x_1 it has to be a nonsquare, which it can be in N_q(\triangle) ways. So this gives…
A: Remember that also x_1 can be zero, and for two choices of x_1 we need x_2^2+\dots+x_{q+1}^2\equiv 0\pmod p!
B: Good point. In total, we get

\displaystyle N_{q+1}(\square)=\frac{p-5}{2}N_q(\square)+\frac{p-1}{2}N_q(\triangle)+N_q(\square)+2N_q(0)=\frac{p-3}{2}N_q(\square)+\frac{p-1}{2}N_q(\triangle)+2N_q(0).

A: We can deal with N_{q+1}(\triangle) similarly, the only difference being that now x_1^2 can’t be \triangle, so we don’t get N_q(0) term. All in all,

\displaystyle N_{q+1}(\triangle)=\frac{p-1}{2}N_q(\square)+\frac{p+1}{2}N_q(\triangle).

B: Also, to recap, in this case we have

\displaystyle N_{q+1}(0)=(p-1)N_q(\square)+N_q(0).

So we have a simultaneous recurrence involving three functions. How could we get around solving it?
A: Well, of course the hard part is actually figuring out what the answer possibly could be, since once we know the formula we will most likely be able to prove it inductively. One way to find the formula is to note that, if we denote by \mathbf x_q a vertical vector with entries N_q(\square),N_q(\triangle),N_q(0), then above system of recurrences can be written as \mathbf x_{q+1}=M\mathbf x_q for certain matrix M, so that \mathbf x_q=M^{q-1}\mathbf x_1. Hence we would like to find explicit formulas for the coefficients of the power of the matrix M. Standard method for doing that in linear algebra is via diagonalization: we find an invertible matrix C and a diagonal matrix D such that M=C^{-1}DC. It is not always possible, but using eigenvalues and eigenvectors we can rather straightforwardly figure out that it is possible for M, and indeed we can explicitly find C,D. Usefulness of this approach is that now M^{q-1}=(C^{-1}DC)^{q-1}=C^{-1}D^{q-1}C and taking powers of diagonal matrices is simple – you just take powers of the diagonal entries. This method is a very effective in practice, and in general it can…
B: Alright, enough of that rambling, what is the formula?
A: …as I was about to say, it gives us, for odd q,

N_q(\square)=p^{q-1}+p^{(q-1)/2},N_q(\triangle)=p^{q-1}-p^{(q-1)/2},N_q(0)=p^{q-1}

and for even q we have

N_q(\square)=p^{q-1}-p^{(q-2)/2},N_q(\triangle)=p^{q-1}-p^{(q-2)/2},N_q(0)=p^{q-1}+p^{q/2}-p^{(q-2)/2}.

B: That’s great! I suppose at this point we have achieved what we tried to achieve.
A: Not quite yet – we still have p\equiv 3\pmod 4 to work out. Thankfully, exactly the method works here, except now the sign changes for different values modulo 4. For q respectively 0,1,2,3\pmod 4 we have

N_q(\square)=p^{q-1}-p^{(q-2)/2},N_q(\triangle)=p^{q-1}-p^{(q-2)/2},N_q(0)=p^{q-1}+p^{q/2}-p^{(q-2)/2},
N_q(\square)=p^{q-1}+p^{(q-1)/2},N_q(\triangle)=p^{q-1}-p^{(q-1)/2},N_q(0)=p^{q-1},
N_q(\square)=p^{q-1}+p^{(q-2)/2},N_q(\triangle)=p^{q-1}+p^{(q-2)/2},N_q(0)=p^{q-1}-p^{q/2}+p^{(q-2)/2},
N_q(\square)=p^{q-1}-p^{(q-1)/2},N_q(\triangle)=p^{q-1}+p^{(q-1)/2},N_q(0)=p^{q-1}.

B: I have no idea how you are doing these things in your head, but I’ll trust you it’s correct. This seems like a complete answer to our problem, at least modulo a prime.
A: You have reminded me – I’ve earlier found this one congruence for N_q(a). I wonder how this big formula will look like reduced modulo q: since we only deal with odd q, the formula will simplify a bit. Also, we can use the Legendre symbol here – we can write N_q(a)=p^{q-1}\pm\left(\frac{a}{p}\right)p^{(q-1)/2}, with - sign iff p\equiv q\equiv 3\pmod 4.
B: Reducing this modulo q, using Euler’s criterion we have

N_q(a)\equiv 1\pm\left(\frac{a}{p}\right)\left(\frac{p}{q}\right)\pmod q

so, comparing with the earlier formula…
A: …we get

1+\left(\frac{a}{p}\right)\left(\frac{q}{p}\right)\equiv 1\pm\left(\frac{a}{p}\right)\left(\frac{p}{q}\right)\pmod q,

so setting, for example, a=1
B: …we find

\left(\frac{q}{p}\right)=\pm\left(\frac{p}{q}\right)

with - sign iff p\equiv q\equiv 3\pmod 4.
A: …so, we have just proven quadratic reciprocity. By playing around with your dumb game.
B: Please, let that be at the very least a proof that this game is not dumb. Alright, if you really don’t want to deal with it anymore then we can go do some public key exchange. What do you think?
A: Sounds great. I’ll go grab Eve, she really likes listening to our encrypted messages for some reason.
B: Alright. Catch you later.


The above proof is due to V.A. Lebesgue. I follow exposition from “The Quadratic Equation in Fp and the Quadratic Reciprocity Law” by R. Jakimczuk.

Originally I couldn’t make up my mind on whether I should follow this proof or the variation apparently due to W. Castryck (see his “A shortened classical proof of the quadratic reciprocity law”) which, instead of counting solutions to x_1^2+x_2^2+\dots+x_q^2\equiv a\pmod p, counts solutions to the alternating sum equation x_1^2-x_2^2+\dots+x_q^2\equiv a\pmod p for odd q. Castryck’s proof is in pretty much every aspect simpler than Lebesgue’s, but has one drawback which would definitely discourage Bob from presenting it to Alice – the corresponding game is nearly trivial. The game which Bob has designed is definitely much more interesting and I encourage everyone reading this article to do what Alice didn’t want to do, namely figure out the winning strategy, possibly with the winning condition replaced by “the sum of squares is a\pmod p” for some fixed a, or even something more complex. Feel free to explore this game to your heart’s desire, generalizing to composite moduli, more complicated equations and what not. I don’t know if the gaming aspect of this theory has been explored before, but there is a beautiful and deep theory regarding the number of solutions of a given equation modulo various integers.

Last note: I am aware of the fact that the title of this post might be considered to be somewhat false advertisement, because throughout this article the only point at which we have used the game aspect is to motivate the question. I did try to find a proof of this theorem which would in more essential way use the game structure, for example encoding the Legendre symbol as the winning player, unfortunately to no avail. If anyone has any ideas on how to make this proof, or possibly some other proof of QR (I was thinking of Zolotarev’s proof, neatly explained in this article), more game-y, I’d certainly love to hear about that!

Post-last note: the form of this post might or might not have been subconciously inspired by this blog post by Adam P. Goucher, in which he explains Poncelet’s porism in the form of a Socratic dialogue.

Advertisements

2 thoughts on “Quadratic reciprocity: the game

  1. Great work. I haven’t finished this yet, but so far the concepts are very clearly explained. It’s the first post of yours where I feel I have some hope of fully understanding it!

    1. Thanks for the kind words! I must admit that this is the first post of mine where I have actually tried to make the content accessible to a wide audience. I hope to make more of such posts in the future, and the one coming up tomorrow should be, hopefully, quite understandable as well.

Share a thought

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s