# MAT 338 Day 30 2011

## 2605 days ago by kcrisman

Our plan for today involves the following:

• Presentation from student
• (If time) Introduction to Function Questions via sums of squares

First, I will briefly comment on one thing I forgot last time!

What does quadratic reciprocity do for us?

It helps us solve Mordell equations!  Or at least the Legendre symbol does; the easiest cases use $\left(\frac{2}{p}\right)$ and multiplicativity.  But more advanced ones no doubt would need to compute more complicated square roots.  Here are two examples, without proof; there are many others.

• The equation $x^3=y^2+16$ has no integer solutions.  (Uses $\left(\frac{-8}{p}\right)$.)
• The equation $x^3=y^2-46$ has no integer solutions.  (Uses $\left(\frac{-18}{p}\right)$.)

The Proof!

Recall the statement of quadratic reciprocity.  For odd primes $p$ and $q$, we have that $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$  That is to say, the Legendre symbols are the same unless $p$ and $q$ are both of the form $4k+3$.

Proof:

We will use the criterion of Eisenstein's we've used throughout.  Recall that $p$ and $q$ are odd primes in the context of this proof. Now let  $$R=\sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{qe}{p}\right\rfloor\;$$ be the exponent in question, so that $$\left(\frac{q}{p}\right)=(-1)^R\; .$$

The key will be geometrically interpreting $\left\lfloor\frac{qe}{p}\right\rfloor$ as being the biggest integer less than $\frac{qe}{p}$.  The following features are present in the next graphic, which should clarify how we'll think of it geometrically.

• The line through the origin with slope $q/p$ (dotted blue).
• All the grid points in the box of width $p$ and height $q$ (box red, points black).
• Points with even $x$-coordinate corresponding to the highest one can get but stay under the line of slope $q/p$ (points blue).
• The box of width $\frac{p-1}{2}$ and height $\frac{q-1}{2}$ (green), which we'll need in a moment.

It should be clear that each blue stack has the same height as $\left\lfloor\frac{qe}{p}\right\rfloor$ for some even $e$.

var('x,y') @interact def _(p=(11,prime_range(3,100)),q=(7,prime_range(3,100))): E = [2,4..p-1] plot4 = plot((q/p)*x,(x,0,p),linestyle='--') plot3 = line([[0,0],[p,0],[p,q],[0,q],[0,0]],rgbcolor=(1,0,0)) plot2 = line([[0,0],[(p-1)/2,0],[(p-1)/2,(q-1)/2],[0,(q-1)/2],[0,0]],color='green') grid_pts_1 = [[i,j] for i in [1..p] for j in [1..q]] grid_pts_2 = [[i,j] for i in [1..(p-1)/2] for j in [1..(q-1)/2]] plot_grid_pts = points(grid_pts_1,rgbcolor=(0,0,0),pointsize=10) lattice_pts1 = [coords for coords in grid_pts_1 if (coords[0]*q-coords[1]*p>0 and coords[0]<p and coords[0] in E)] lattice_pts2 = [coords for coords in grid_pts_2 if (coords[0]*q-coords[1]*p>0 and coords[0]>p/2)] num1, num2 = len(lattice_pts1), len(lattice_pts2) if len(lattice_pts1)!=0: plot_lattice_pts1 = points(lattice_pts1, rgbcolor = (0,0,1),pointsize=20) else: plot_lattice_pts1 = Graphics() if len(lattice_pts2)!=0: plot_lattice_pts2 = points(lattice_pts2, rgbcolor = (0,.5,0),pointsize=20) else: plot_lattice_pts2 = Graphics() show(plot2+plot3+plot4+plot_grid_pts+plot_lattice_pts1,xmax=p,ymax=q,ymin=0) forms = '$'+'+'.join(['\left\lfloor\\frac{%s\cdot %s}{%s}\\right\\rfloor'%(q,e,p) for e in E])+'$' html("The blue dots represent "+forms) forms2 = '$'+'+'.join(['\left\lfloor\\frac{%s}{%s}\\right\\rfloor'%(q*e,p) for e in E]) forms3 = '+'.join(['%s'%(floor(q*e/p)) for e in E])+'=%s\equiv%s\\text{ mod }(2)$'%(sum([floor(q*e/p) for e in E]),sum([floor(q*e/p) for e in E])%2) html("This simplifies to "+forms2+'='+forms3)

## Click to the left again to hide and once more to show the dynamic interactive window

What we will now do is try to convince ourselves that the number of blue points has the same parity as the total number of (positive) points in and on the green box under the dotted line.   If we can do that, the following steps finish the proof of quadratic reciprocity.

• First, to get $\left(\frac{q}{p}\right)$, we can ignore $R$ and just focus on the number of positive lattice points in that more-or-less triangle.
• Then the same argument applies to $\left(\frac{p}{q}\right)$; we could ignore its crazy exponent (call it $R'$, if you must) and instead focus on the number of positive lattice points in and on the green box to the right of the dotted line.  (We've switched the role of $x$ and $y$, so 'above the $y$-axis' means to its right.)
• So the exponent of $-1$ we expect from $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)$ is just the sum of those two amounts.  That is, the exponent is the number of points in and on the green box.
• You'll note that this box has dimensions $\frac{p-1}{2}$ and $\frac{q-1}{2}$, so that would mean $$\frac{p-1}{2}\cdot\frac{q-1}{2}\equiv \sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{qe}{p}\right\rfloor+\sum_{\text{even }f,\; 0<f<q}\left\lfloor\frac{pf}{q}\right\rfloor\text{ mod }(2)\; ,$$ so that $$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{R+R'}=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\; .$$

This would definitely complete the theorem!

So we must show that the number of blue points (points under the line with even $x$-coordinate) is the same as the number of positive points in the green box under the line.  With Eisenstein, we call this second number $\mu$.  In the next graphic, there is a lot going on, but we can clarify each of the pieces.

var('x,y') @interact def _(p=(11,prime_range(3,100)),q=(7,prime_range(3,100))): E = [2,4..p-1] plot4 = plot((q/p)*x,(x,0,p),linestyle='--') plot3 = line([[0,0],[p,0],[p,q],[0,q],[0,0]],rgbcolor=(1,0,0)) plot2 = line([[0,0],[(p-1)/2,0],[(p-1)/2,(q-1)/2],[0,(q-1)/2],[0,0]],color='green') grid_pts_1 = [[i,j] for i in [1..p] for j in [1..q]] grid_pts_2 = [[i,j] for i in [1..(p-1)/2] for j in [1..(q-1)/2]] plot_grid_pts = points(grid_pts_1,rgbcolor=(0,0,0),pointsize=10) lattice_pts1 = [coords for coords in grid_pts_1 if (coords[0]*q-coords[1]*p>0 and coords[0]<p and coords[0] in E)] lattice_pts2 = [coords for coords in grid_pts_1 if (coords[0]*q-coords[1]*p<0 and coords[0]>(p-1)/2 and coords[1]<q and coords[0] in E)] lattice_pts3 = [coords for coords in grid_pts_1 if (coords[0]*q-coords[1]*p>0 and coords[0]<=(p-1)/2 and coords[0] not in E)] num1, num2 = len(lattice_pts1), len(lattice_pts2) if len(lattice_pts1)!=0: plot_lattice_pts1 = points(lattice_pts1, rgbcolor = (0,0,1),pointsize=20) else: plot_lattice_pts1 = Graphics() if len(lattice_pts2)!=0: plot_lattice_pts2 = points(lattice_pts2, rgbcolor = (0,.5,0),pointsize=20) else: plot_lattice_pts2 = Graphics() if len(lattice_pts3)!=0: plot_lattice_pts3 = points(lattice_pts3, rgbcolor = (0,.5,0),pointsize=20) else: plot_lattice_pts3 = Graphics() show(plot2+plot3+plot4+plot_grid_pts+plot_lattice_pts1+plot_lattice_pts2+plot_lattice_pts3,xmax=p,ymax=q,ymin=0) forms = '$\mu='+'+'.join(['\left\lfloor\\frac{%s\cdot %s}{%s}\\right\\rfloor'%(q,e,p) for e in [1..(p-1)/2]])+'$' html("The blue and green dots in the small triangle represent") html("the sum "+forms)

## Click to the left again to hide and once more to show the dynamic interactive window

Let's look at the two sets of green dots.

• The ones on top are the ones with even $x$-coordinates greater than $\frac{p-1}{2}$ which have $y$-coordinate less than $q$ and are above the line.
• The ones on the bottom are the ones with odd $x$-coordinates less than $\frac{p-1}{2}$ which have $y$-coordinate greater than $0$ and are below the line.

In other words, they are symmetric images - simply rotated around the point $$\left(\frac{p}{2},\frac{q}{2}\right)\; .$$  So in order to say that $\mu$ has the same parity as $R$ (which is our goal to finish the proof), we just have to show that either set of green points has the same parity as that of the set of blue points outside the green box.

• There are $q-1$ points in each such column of points outside the green box.
• In particular, there an even number of points in each such column.
• So whether the number of blue points in a given column is even or odd, it is guaranteed that the parity of the green points in that same column is also even or odd, respectively.
• So the parity of the green points outside the green box is the same as the parity of the blue points outside the green box.

Which means the parity of the points inside the triangle $(\mu)$ is the same as that of the blue points ($R$), which is what we wanted to prove!

Q.E.D.

Interlude of the student presentation.

Okay, I want to end with just a slight preview of what the final quarter of the course will be about - namely, functions and number theory.  We have already run into a few functions, most notably $\phi(n)$.

However, I want to talk about one we've encountered a little more recently, the number of ways to write $n$ as a sum of squares, or $r(n)$.  For instance, $r(25)=12$.  Why?  Because you can write it using the pairs $$(\pm 3,\pm 4),\; \; (\pm 4,\pm 3),\;\; (\pm 5,0)\text{ and }(0,\pm 5)\; .$$  That's a little different; here, we count ALL solutions, positive or negative, and in any particular order possible.

First off:

The function $r$ has a formula.   Let's write primes of the form $4k+1$ as $p$, and primes of the form $4k+3$ as $q$.  Then:

$$\text{If }n=2^dp_1^{e_1}\cdots p_k^{e_k}q_1^{f_1}\cdots q_\ell^{f_\ell},\text{ then }r(n)=\begin{cases}0 & \text{ if any }f_j\text{ is odd}\\4\prod_{i=1}^k(e_i+1) & \text{ otherwise}\end{cases}$$

Notice that the empty product (no primes of the form $4k+1$) is 1, just like a sum over zero elements is zero.

It turns out that every single proof of this is not very elementary.  They all either go into some detail regarding factorization of Gaussian integers, or do some lengthy divisibility and congruence analysis.  So we will skip them.

Secondly:

Just like with $\phi(n)$, there are some relations with multiplying.  Now that we have a formula, that is nearly immediate.  For instance, $$r(3)r(5)=r(15)$$ because both sides are zero!  But also $$r(25)r(13)=12\cdot 4=48=r(325)$$

But it doesn't always work.  For instance, $$r(25)r(4)=12\cdot 4=48\neq 12=r(100)\; .$$  Naturally, $\phi$ wasn't always multiplicative in this sense; however, here the inputs are relatively prime and it still doesn't work.  Is there any way we can say when the outputs would multiply?

Finally:

We can use $r(n)$ to talk about limits with functions.  Yes, limits in number theory!

The following graphic has as its basic content the circle with radius $\sqrt{n}$ and blue lattice points representing all pairs $(x,y)$ such that $x^2+y^2\leq n$.  There is a little box of area one around each such lattice point; as you might expect, the boxes roughly cover the circle, but certainly not exactly.

@interact def _(n=(5,[1..100])): viewsize=ceil(math.sqrt(n))+2 a=(math.sqrt(n)+1/math.sqrt(2))^2 b=(math.sqrt(n)-1/math.sqrt(2))^2 g(x,y) = x^2+y^2 P=Graphics() P += implicit_plot(g-n,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 200) P += implicit_plot(g-a,(-viewsize,viewsize),(-viewsize,viewsize),linestyle='--',plot_points = 200) P += implicit_plot(g-b,(-viewsize,viewsize),(-viewsize,viewsize),linestyle='--',plot_points = 300) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] P += points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (coords[1]^2+coords[0]^2<=n)] P += points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) squares=[line([[k-1/2,l-1/2],[k+1/2,l-1/2],[k+1/2,l+1/2],[k-1/2,l+1/2],[k-1/2,l-1/2]],rgbcolor=(1,0,0)) for [k,l] in lattice_pts] for object in squares: P += object show(P, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1) html("There are $%s$ boxes with a circle of radius $%s$"%(len(squares),math.sqrt(n))) html("The ratio of the area of boxes to the square of the radius is $\\approx%s$"%(len(squares)/(math.sqrt(n)^2)))

## Click to the left again to hide and once more to show the dynamic interactive window

What does this have to do with $r(n)$?

Again, the total number of representations of any integer less than or equal to $n$ can be thought of as the area of unit boxes around each lattice point giving the representation, and this number would be $$\sum_{k=0}^{n}r(k)\, .$$  So the area of the boxes can give us information about $r$.

As we noted, they neither cover nor are covered by the circle in question.  However:

• These boxes will entirely cover a disk of radius $\sqrt{n}$ minus half the diagonal length of the boxes, namely $\frac{1}{\sqrt{2}}$, which is the inner circle above.
• Likewise, they are completely contained in a disk of radius $\sqrt{n}$ plus half the diagonal length of the boxes.

Using these two pieces of information, in terms of area covered, $$\pi \left(\sqrt{n}-\frac{1}{\sqrt{2}}\right)^2\leq \sum_{k=0}^{n}r(k)\leq \pi \left(\sqrt{n}+\frac{1}{\sqrt{2}}\right)^2\, ,$$ which simplifes to $$\pi \frac{n-\sqrt{2n}+1/2}{n}\leq \frac{1}{n}\sum_{k=0}^{n}r(k)\leq \pi \frac{n+\sqrt{2n}+1/2}{n}\, ,$$ which yields $$\pi \left(1-\frac{\sqrt{2}}{n}+1/2n\right)\leq \frac{1}{n}\sum_{k=0}^{n}r(k)\leq \pi \left(1+\frac{\sqrt{2}}{n}+1/2n\right)\, .$$

• Since the limit as $n$ goes to $\infty$ of the lower and upper bounds with each of these inequalities outside guys exists and is $\pi$;
• And since removing one term from the sequence won't affect the limit as it's an average;
• Then the beloved squeeze theorem from the first few weeks of calculus implies that $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}r(k)=\pi\, .$$

We can interpret this as saying the average number of representations of a positive integer as a sum of squares is $\pi$.

WHAT?!

But true.

We will discuss these and many related ideas in the last few weeks.

Homework:

1. Evaluate all Legendre symbols for $p=7$ using Euler's Criterion.
2. Evaluate the Legendre symbols for $p=11$ and $a=2,3,5$ using the calculation of Eisenstein's we used at the beginning.
3. Use the previous problem, your knowledge of $\left(\frac{-1}{11}\right)$ and of perfect squares to evaluate the other Legendre symbols for $p=11$.
4. Use the Eisenstein calculation to reprove the mod (8) criterion for $\left(\frac{2}{p}\right)$.
5. Make up several hard-looking Legendre symbols $\left(\frac{a}{29}\right)$ (modulo $p=29$) that are easy to solve by adding $p$ or by factoring $a$.
6. Use the multiplicative property of the Legendre symbol to give a congruence condition for when $\left(\frac{-2}{p}\right)=\pm 1$.
7. For $0<a,b<p$, prove that at least one of $a,b,$ and $ab$ is a quadratic residue of $p$.
8. Prove that if $\left(\frac{2}{n}\right)$ is the Jacobi symbol instead of the Legendre symbol, it is still true that it $=1$ precisely when $n\equiv \pm 1\text{ mod }(8)$.  (Remember, $n$ has to be odd by definition.)
9. Prove that for any prime $p$, if $1<i,j<\frac{p}{2}$ and $i\neq j$, then $i^2\not\equiv j^2$ mod ($p$).  (Hint: factor!)
10. Last class we conjectured and proved that $$\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0\, .$$  Conjecture (and, if you can, prove) a similar result for $$\sum_{a\in Q_p} a\, .$$
11. Prove: if $p\equiv 3$ mod (4), and if $a\not\equiv \pm 1,0$, then $a$ is a QR if and only if $p-a$ is not a QR.
12. Verify the previous exercise for $p=23$.
13. Let $p$ be a prime of the form $p=2q+1$, where $q$ is prime (recall that $q$ is called a Germain prime in this case).  Show that every residue from 1 to $p-2$ is either a primitive root of $p$ or a quadratic residue.  (Hint: How many possible orders can an element of $U_p$ can have?)
14. Show that if $p$ is an odd prime, then there are exactly $\frac{p-1}{2}-\phi(p-1)$ residues which are neither QRs nor primitive roots. (Hint: don't think too hard - just do the obvious counting up.)
15. Evaluate five non-obvious Legendre symbols $(\frac{a}{p})$ for $p=47$ using quadratic reciprocity.
16. Find congruence criteria for $p$ for when $a\in Q_p$ for $a=-3,6$, and $9$. (Hint: Don't do any extra work - use what you know!)

Appendix:

One can also prove quadratic reciprocity using the Gauss Lemma of the appendices.  Jones and Jones essentially give the proof on pages 133-135; it is similar in style, though less elegant, than Eisenstein's proof.  The key thing to remember is that we can change the congruence condition on one variable, $x$, into a lattice-point condition on two variables, $x$ and $y$, and then use techniques of the past for that!

The following interactive graphic shows how this works.

var('x,y') @interact def _(p=(19,prime_range(3,100)),q=(23,prime_range(3,100))): html('We see that $(%s-1)/2$ is $%s$ and $(%s-1)/2$ is $%s$'%(p,(p-1)/2,q,(q-1)/2)) html('So the parity is $\\frac{(%s-1)(%s-1)}{4}=%s\\equiv %s\\text{ mod }(2)$'%(p,q,(p-1)*(q-1)/4,((p-1)*(q-1)/4)%2)) plot1 = plot((1/p)*(q*x+p/2),(x,0,p)) plot2 = plot((1/p)*(q*x-q/2),(x,0,p)) plot3 = line([[1,1],[(p-1)/2,1],[(p-1)/2,(q-1)/2],[1,(q-1)/2],[1,1]],rgbcolor=(1,0,0)) grid_pts = [[i,j] for i in [1..(p-1)/2] for j in [1..(q-1)/2]] plot4 = plot((q/p)*x,(x,0,p),linestyle='--') plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=10) lattice_pts1 = [coords for coords in grid_pts if (coords[0]*q-coords[1]*p<0 and coords[0]*q-coords[1]*p>-p/2)] lattice_pts2 = [coords for coords in grid_pts if (coords[0]*q-coords[1]*p>0 and coords[0]*q-coords[1]*p<q/2)] num1, num2 = len(lattice_pts1), len(lattice_pts2) if len(lattice_pts1)!=0: plot_lattice_pts1 = points(lattice_pts1, rgbcolor = (0,0,1),pointsize=20) else: plot_lattice_pts1 = Graphics() if len(lattice_pts2)!=0: plot_lattice_pts2 = points(lattice_pts2, rgbcolor = (0,.5,0),pointsize=20) else: plot_lattice_pts2 = Graphics() show(plot1+plot2+plot3+plot4+plot_grid_pts+plot_lattice_pts1+plot_lattice_pts2,xmax=(p-1)/2,ymax=(q-1)/2,ymin=0) html('And indeed the parity of green points plus blue points $%s+%s=%s\\equiv %s\\text{ mod }(2)$ is the same'%(num2,num1,num2+num1,(num2+num1)%2)) html('The Gauss lemma tells us the green points and blue points give us the Legendre symbols') html('So we predict $\left(\\frac{%s}{%s}\\right)\left(\\frac{%s}{%s}\\right)=(-1)^{%s+%s}=(-1)^{%s}=%s$'%(p,q,q,p,num2,num1,(num2+num1)%2,(-1)^(num2+num1))) html('And in fact Sage computes it to be $%s\cdot %s=%s$'%(legendre_symbol(p,q),legendre_symbol(q,p),legendre_symbol(p,q)*legendre_symbol(q,p)))