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.

Previous

Nonvanishing of L-functions via Dedekind zeta functions

Next

Proof of the Riemann hypothesis… for polynomials

2 Comments

  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!

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

Leave a Reply

Powered by WordPress & Theme by Anders Norén