MAT 338 Day 24 2011

2372 days ago by kcrisman

Well, I just couldn't help myself, because you guys were so interested in the Gaussian integers.  Here is the basics of the argument for why primes of the form $4n+1$ can be written as a sum of squares, the complex numbers version!

• Let $p\equiv 1\text{ mod }(4)$, as we know.
• We already know that $$r = \left(\frac{p-1}{2}\right)!$$ is a square root of $-1$ modulo $p$.
• But now, instead of doing geometry, let's look at what that means.  It means, by definition of $$r^2\equiv -1\text{ mod }(p)$$ that $$p\mid r^2+1\; .$$
• Since $r^2+1$ is $r^2-i^2$, let's factor: $$r^2+1=(r+i)(r-i)$$
• Clearly $p$ does not divide either of those as something of the form $a+bi$.
• So (crucial!), if we assume the FTA still holds for Gaussian integers (things like $a+bi$), then $p$ factors in $\mathbb{Z}[i]$, and has a prime divisor $a+bi$.
• It's not hard to show that then $a-bi$ also must divide $p$. We'll skip this.
• Then $$(a+bi)(a-bi)\mid p^2\Rightarrow a^2+b^2 \mid p^2$$
• Further, this is a nontrivial divisor, since $a+bi$ was a proper divisor of $p$.  So the only possibility is $$a^2+b^2=p\; .$$

Naturally, I am skipping whether we actually have unique factorization in $\mathbb{Z}[i]$.  (It turns out you can prove this most easily using geometry as well!)

But this has some interesting implications that will serve us well going into our next topics.   Think about the following two problems.

• What numbers can be written as $x^2+2y^2$?
• What numbers can be written as $x^2+3y^2$?

These are very natural generalizations.  How could we approach them?

Fact: No number $$n\equiv 5\text{ or }n\equiv 7\text{ mod }(8)$$ can be written as $x^2+2y^2$.

Proof: Try all numbers modulo 8 and see what is possible!

So unsurprisingly, already Fermat claimed a partial converse - that any prime $p$ which is $p\equiv 1$ or $p\equiv 3\text{ mod }(8)$ could be written as a sum of a square and twice a square.

It turns out that Euler wasn't the one who proved that!  But you could almost imagine that by factoring $$x^2+2y^2=(x-\sqrt{2}iy)(x+\sqrt{2}iy)$$ you could start proving such things... and we will return to that idea again in passing.

L=[a^2+2*b^2 for a in [0..10] for b in [0..10]] L.sort(); L
 [0, 1, 2, 3, 4, 6, 8, 9, 9, 11, 12, 16, 17, 18, 18, 19, 22, 24, 25, 27, 27, 32, 33, 33, 34, 36, 36, 38, 41, 43, 44, 48, 49, 50, 51, 51, 54, 54, 57, 57, 59, 64, 66, 66, 67, 68, 72, 72, 73, 75, 76, 81, 81, 81, 82, 83, 86, 88, 89, 96, 97, 98, 99, 99, 99, 100, 102, 102, 107, 108, 108, 113, 114, 114, 118, 121, 123, 128, 129, 131, 132, 132, 134, 136, 137, 144, 147, 150, 153, 153, 162, 162, 163, 164, 166, 171, 172, 177, 178, 179, 187, 192, 198, 198, 200, 201, 204, 209, 209, 211, 216, 225, 226, 228, 236, 243, 249, 262, 264, 281, 300] [0, 1, 2, 3, 4, 6, 8, 9, 9, 11, 12, 16, 17, 18, 18, 19, 22, 24, 25, 27, 27, 32, 33, 33, 34, 36, 36, 38, 41, 43, 44, 48, 49, 50, 51, 51, 54, 54, 57, 57, 59, 64, 66, 66, 67, 68, 72, 72, 73, 75, 76, 81, 81, 81, 82, 83, 86, 88, 89, 96, 97, 98, 99, 99, 99, 100, 102, 102, 107, 108, 108, 113, 114, 114, 118, 121, 123, 128, 129, 131, 132, 132, 134, 136, 137, 144, 147, 150, 153, 153, 162, 162, 163, 164, 166, 171, 172, 177, 178, 179, 187, 192, 198, 198, 200, 201, 204, 209, 209, 211, 216, 225, 226, 228, 236, 243, 249, 262, 264, 281, 300]

But before we do, we will go more in depth with looking at what points are even possible on such a curve.  Remember, if $x^2+y^2=n$ was a circle of radius $\sqrt{n}$, then $x^2+2y^2=n$ must be an ellipse!  So we will spend a few days looking at the notion of (integer) lattice points on a curve.

It is a question at the heart of modern number theory, so we should at least spend a little more time on it - plus, it has such nice pictures!  It turns out it will have a surprising connection to calculus and group theory too.

var('x,y') @interact def _(n=3): plot1=implicit_plot(x^2+2*y^2-n,(x,-n,n),(y,-n,n),plot_points=100) grid_pts = [[i,j] for i in [-n..n] for j in [-n..n]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (2*coords[1]^2+coords[0]^2)==n] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) show(plot1+plot_grid_pts+plot_lattice_pts,figsize=[-5,5],aspect_ratio=1) html("The ellipse $x^2+2y^2=%s"%n) Click to the left again to hide and once more to show the dynamic interactive window We we are going to do is to try to make our way to finding integer solutions to some more difficult Diophantine equations, but slowly, using an idea which simplifies Pythagorean triple geometry. Remember that we thought of Pythagorean triples as solutions to $$x^2+y^2=z^2\; .$$ Namely, let's divide the whole Pythagorean thing by$z^2$: $$\frac{x^2}{z^2}+\frac{y^2}{z^2}=1\Rightarrow \left(\frac{x}{z}\right)^2+\left(\frac{y}{z}\right)^2=1\, .$$ Since we can always get any two rational numbers to get a common denominator, what that means is the Pythagorean problem is the same as finding all rational solutions to $$a^2+b^2=1\, ,$$ which seems to be a very different problem. Let's investigate this. var('x,y') @interact def _(slope=-2/3): plot1=implicit_plot(x^2+y^2-1,(x,-1.5,1.5),(y,-1.5,1.5),plot_points=100) plot2=plot(slope*(x-1),x,-1.5,1.5) plot3=point(((slope^2-1)/(slope^2+1),-2*slope/(slope^2+1)),rgbcolor=(1,0,1),pointsize=20) show(plot1+plot2+plot3+point((1,0),rgbcolor=(0,0,0),pointsize=20),figsize=[-5,5],aspect_ratio=1) Click to the left again to hide and once more to show the dynamic interactive window The blue line intersects the circle$x^2+y^2=1$in the point$(1,0)$and has rational slope denoted by 'slope'. If you change the variable 'slope', then the line will change. It is not a hard exercise to see that the line through two rational points on a curve will have rational slope, nor what its formula is, so that every rational point on the circle is gotten by intersecting$(1,0)$with a line with rational slope. It is a little harder to show that intersecting such a line with the circle always gives a rational point, but this is also true! It is also far more useful, as it gives us a technique to find all rational points and hence all Pythagorean triples. Here are the details: • The line with slope$t$has formula$y=t(x-1)$. • The intersections with the circle$x^2+y^2=1$are gotten by plugging in$y$, so: $$x^2+(t(x-1))^2=1\Rightarrow x^2+t^2 x^2-2xt^2+t^2=1$$ • This can be completely solved using the quadratic formula to get$\frac{t^2\pm 1}{t^2+1}$as the answers. • Since$\frac{t^2+1}{t^2+1}=1$gives the point$(1,0)$which we already knew, the other point is$\frac{t^2-1}{t^2+1}=x$. • Then$y=t\left(\frac{t^2-1}{t^2+1}-1\right)=\frac{-2t}{t^2+1}$• So every rational slope$t$gives us the point$\left(\frac{t^2-1}{t^2+1},\frac{-2t}{t^2+1}\right)$. Even the inputs$t=0$and$t=\infty$have an appropriate interpretation in this framework, believe it or not. Such a description of the (rational) points of the circle is called a parametrization. Plug in various$t$and see what you get! Note that the book started with$(-1,0)$, and also got a parametrization - in fact, a slightly different one. Will this always work? Here is an amazing fact we will not prove. Fact: If you have a quadratic equation with rational coefficients with at least one rational point, then you can get all others by intersecting all lines with rational slope through that point on the curve. var('x,y') @interact def _(slope=-1/2,f=x^2+3*y^2-1): f(x,y)=f plot1=implicit_plot(f,(x,-1.5,1.5),(y,-1.5,1.5),plot_points=100) plot2=plot(slope*(x-1),x,-1.5,1.5) show(plot1+plot2+point((1,0),rgbcolor=(0,0,0),pointsize=20),figsize=[-5,5],aspect_ratio=1) Click to the left again to hide and once more to show the dynamic interactive window Once again, the line above goes through$(1,0)$and so has equation$y=t(x-1)$. The ellipse is$x^2+3y^2=1$, so that $$x^2+3t^2(x-1)^2=1\Rightarrow x^2+3t^2x^2-6t^2x+3t^2-1=0$$ is the equation we must solve for$x$to find a parametrization of$x$in terms of$t$. This seems daunting; however, we already know that there is a solution$x=1$, so that$x-1$must be a factor of the expression! So we could factor it out if we wished. Alternately, we could use the quadratic formula and discard the solution$x=1$. Let's do that now! At the end we should get$x=\frac{3t^2-1}{3t^2+1},y=\frac{-2t}{3t^2+1}$, which leads to very interesting solutions like$\left(\frac{11}{13},\frac{-4}{13}\right)$. var('x,y') viewsize=15 plot1=plot3d(sqrt(x^2+3*y^2),(x,-viewsize,viewsize),(y,-viewsize/2,viewsize/2)) grid_pts = [[i,j,k] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize] for k in [0..viewsize]] lattice_pts = [coords for coords in grid_pts if (coords[0]^2+3*coords[1]^2==coords[2]^2)] plot_lattice_pts = point3d(lattice_pts, rgbcolor = (1,0,0),pointsize=20) show(plot1+plot_lattice_pts) And such solutions lead us directly to INTEGER solutions of equations like$x^2+3y^2=z^2$! Since$x$and$y$have a common denominator, we can just multiply through by the square of that denominator to get a solution to this. E.g. $$11^2+3(-4)^2=13^2$$ which is rather non-obvious solution, to say the least, and only one of many that this method can help us find. However, this method does NOT always work. Namely, you need at least one rational point to start off with. And what if there isn't one that exists? It turns out that Diophantus already knew of some such curves: Fact:$x^2+y^2=15$has no rational points. The way to prove this is to correspond this to integer points on$x^2+y^2=15z^2$. Every rational point on the first curve looks like$(p/q,r/q)$for some$p,r,q\in\mathbb{Z}$, so multiplying through by the common denominator gives us integer points on the second surface. But now consider the whole thing modulo 4 - what are the possibilities? var('x,y') viewsize=15 plot1=plot3d(sqrt(x^2+y^2)/sqrt(15),(x,0,viewsize),(y,0,viewsize)) grid_pts = [[i,j,k] for i in [0..viewsize] for j in [0..viewsize] for k in [0..3*viewsize]] lattice_pts = [coords for coords in grid_pts if (coords[0]^2+coords[1]^2==15*coords[2]^2)] plot_lattice_pts = point3d(lattice_pts, rgbcolor = (1,0,0),pointsize=20) show(plot1+plot_lattice_pts) So as we can see there are NO rational points on a circle of radius$\sqrt{15}$because there are no integer points on the corresponding surface other than ones with$x,y=0$- and those correspond to$z=0$, which would give a zero denominator on the circle. Here is a place where rational points are helped by integer points instead of vice versa. Another one to try is finding rational points on the ellipse$2x^2+3y^2=1$, which would correspond to$2x^2+3y^2=z^2$. Here a different technique might help - look at it modulo 3! In this case it reduces to $$2\equiv (zx^{-1})^2\text{ mod }(3)$$ which is impossible since$[0],[1],[2]$all square to$[0]$or$[1]$in$\mathbb{Z}_3$. In any case, our investigation of integer points has led us through rational points back to integer points! Next time we will look at some remarkable properties that sets of integer points on certain curves have, and whether any such points even exist. With that in view, let's take any remaining time by trying to find integer points on the following curves: •$y^3=x^2+2$(sometimes called the Bachet equation) •$x^2-2y^2=1$(studied by the Greeks, such as Theon of Smyrna, to shed light on$\sqrt{2}$) •$x^2+2y^2=9$We've already discussed the first one in the context of Bachet and Euler discussing that $$3^3=5^2+2$$ seeming to be the only possible solution. It is one of a more general type called the Mordell equation ($y^3=x^2+k$). Mordell had a lot to do with these; notice that unlike the others discussed today, it is not quadratic/conic but rather cubic, which makes them far more mysterious - and useful for cryptography, though we won't get into that. The second is of a type often called Pell's equation; it is just a hyperbola. In the event, Pell did not have anything to do with them. var('x,y') @interact def _(k=(2,[-10..10])): viewsize=abs(k)+5 g(x,y)=y^3-x^2 plot1 = implicit_plot(g-k,(x,-viewsize,viewsize),(y,-viewsize,viewsize),plot_points = 100) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (coords[1]^3-coords[0]^2==k)] if len(lattice_pts)>0: plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) show(plot1+plot_grid_pts+plot_lattice_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1) else: show(plot1+plot_grid_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1) html("Integer points on the Mordell equation$y^3=x^2+%s$"%k) Click to the left again to hide and once more to show the dynamic interactive window var('x,y') @interact def _(d=[2..20]): viewsize=8+abs(d) f(x,y)=x^2-d*y^2 plot1 = implicit_plot(f-1,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 200) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (coords[0]^2-d*coords[1]^2==1)] if len(lattice_pts)>0: plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) show(plot1+plot_grid_pts+plot_lattice_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1) else: show(plot1+plot_grid_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1) html("Integer points on Pell's equation$x^2-%sy^2=1$"%d) Click to the left again to hide and once more to show the dynamic interactive window The homework, due Monday: 1. Prove that if$n\equiv 3\text{ mod }(4)$, then$n$cannot be written as a sum of two squares. 2. Read Section 10.3 in the book; the notation$S_3$describes the set of integers writeable as a sum of three squares, as$S_2$might indicate the set of things writeable as the sum of two squares. Do Exercises 10.9-10.11. 3. Verify the Brahmagupta-Fibonacci identity by hand (i.e. write all the algebra out). 4. Let$r_2(n)$be the number of different ways to write$n$as a sum of squares, where every different way is counted. For instance, $$r_2(2)=4\text{ because }(-1,1),(-1,-1),(1,1),(1,-1)\text{ all work.}$$ Prove that $$r_2\left(2^n\right)=4\text{ for all }n\; .$$ 5. Let$N$be odd, and let$N=a^2+b^2$and$N=c^2+d^2$, where the pairs$(a,b)$and$(c,d)$are both positive and not the same or just switched in order. Verify the following: • It's okay to assume that$a$and$c$are odd and$b$and$d$are even. • If this is the case, show that$k=gcd(a-c,b-d)$and$n=gcd(a+c,b+d)$are both even. • Then show that$\frac{a-c}{k}=\frac{b+d}{n}$and$\frac{b-d}{k}=\frac{a+c}{n}$. • Finally, show that neither factor of$N$we get is trivial (i.e., 1). 6. Pick four random (to you) three digit numbers which are not of the form$4k+3$and decide whether they are a sum of two squares. 7. Prove that if$n\equiv 12$mod (16), show that$n$cannot be written as a sum of two squares. 8. Check every piece of the Zagier proof: • The set$S$is finite. Try figuring out what$S$is for$p=5$or$p=13$, the smallest such primes. • Each$(x,y,z)$has exactly one of the three things to go to. • If you take the output and apply the function again, you get$(x,y,z)$back (this is a little tougher). • If$(x,y,z)$goes to$(x,y,z)$then it turns out that$(x,y,z)=(1,1,\frac{p-1}{4})$(you will probably need to use the definition of$S$for this, and remember that we assume$p\equiv 1$mod (4)). • That if the map$(x,y,z)\to (x,z,y)$has a point which is fixed (the output is same as input) then this, combined with the definition of$S$, means that$p$is writeable as the sum of two squares. 9. Look for a pattern, similar to the one we found for sums of squares, for which primes can be written in the form$x^2+3y^2$. Prove that the primes not of this form are impossible. 10. Find a parametrization (similar to the ones above) for rational points on the following curves: • The ellipse$x^2+3y^2=1$• The hyperbola$x^2-2y^2=1$11. Prove that the Bachet equation cannot have any solutions with$x$or$y$even. 12. Why can the Pell equation ($x^2-dy^2=1$) not have any solutions if$d\$ happens to be a perfect square?