# MAT 338 Day 22 2011

## 3300 days ago by kcrisman

Today, we're going to take it easy - lots of time exploring by hand an interesting question similar to some we've already seen.

Question:

$$\text{Take a positive integer }n\text{ and try to write it as }n=a^2+b^2\text{ for }a,b\in\mathbb{Z}\text{; for which }n\text{ is this possible, for which is it not?}$$

It seems that Albert Girard already knew the answer to this question in the first quarter of the 17th century, and Fermat discovered this a couple years later.  Girard is an interesting figure, less well-known than his contemporaries; he apparently was the first to use our modern notation for trigonometric functions, and spent his adult life in the Netherlands escaping religious persecution as a Protestant in France.

A full proof of the answer to this question did not come until Euler (no surprise here) about six score years later.

Some things to think about while you try this are

• Any special types of numbers easier than others?
• Any way of generating new such numbers from old ones?
• If some types of numbers are not a sum of squares, how might you prove this?

A separate question to at least keep track of is how many ways can you write a number as a sum of squares, assuming you can indeed write it in this way?

After we work on this a while, and collate our information, possibly making some guesses, I'll try to show a few different points of view of this problem.

First, let's mention something that you should have noticed, based on our patterns in the past.

Fact: $$\text{If }n\equiv 3\text{ mod }(4)\text{, then }n\text{ is not writeable as a sum of squares.}$$

You should be able to prove this pretty easily based on things you already know about squares modulo 4.

The next thing to note is that Sage has a nice command to tell us an answer.

two_squares(29)
 (2, 5) (2, 5)

If it doesn't exist, we get an error.  Notice that I picked a number $n\equiv 1\text{ mod }(4)$, but it is not writeable - so we can't just say that the 'Fact' above takes care of all cases which can't be written as a sum of squares.

two_squares(21)
 Traceback (click to the left of this block for traceback) ... ValueError: 21 is not a sum of two squares Traceback (most recent call last): File "", line 1, in File "_sage_input_6.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("dHdvX3NxdWFyZXMoMjEp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in File "/private/var/folders/Yy/YytEJm5VEB0+pBRD7JNLe++++TQ/-Tmp-/tmpv2nuGK/___code___.py", line 3, in exec compile(u'two_squares(_sage_const_21 ) File "", line 1, in File "/Applications/MathApps/sage/local/lib/python2.6/site-packages/sage/rings/arith.py", line 4350, in two_squares raise ValueError, "%s is not a sum of two squares"%n ValueError: 21 is not a sum of two squares

You can use this interact to avoid the errors.

@interact def _(n=29): try: a,b = two_squares(n) html("We can write ${0}={1}^2+{2}^2$".format(n,a,b)) except: html("${0}$ is not a sum of two squares".format(n))

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

Second, we can interpret this question very differently, relying on our geometric intuition.

var('x,y') @interact def _(n=(5,range(100))): viewsize=ceil(math.sqrt(n))+2 g(x,y)=x^2+y^2 p = implicit_plot(g-n,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 100) lattice_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2) curve_pts = [coords for coords in lattice_pts if g(coords[0],coords[1])==n] if len(curve_pts)==0: show(p+plot_lattice_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1) else: plot_curve_pts = points(curve_pts, rgbcolor = (0,0,1),pointsize=20) show(p+plot_lattice_pts+plot_curve_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1)

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

This graphic helps us visualize the problem.  If $n=a^2+b^2$, then $n$ is the square of the radius of a circle which has $(a,b)$ as the coordinates of a point.  So the sum of squares problem is actually a geometric one!

That is, we can rewrite our questions like this:

Question: Which circles around the origin have lattice points, and which ones do not?

Question: If a circle has lattice points, how many does it have?

This is the way I choose to prove the questions, though there are many ways, connecting the problem to geometry.  We will also see (later this semester) how this function of how many ways there are to write a number as a sum of two squares leads us to calculus ideas in number theory.

Connection to some very old mathematics

The following identity was, separately, already known to Diophantus (remember Diophantine equations?) around 250, to Brahmagupta (about whom more later) around 600, and to Leonardo of Pisa (known also as Fibonacci) around 1250.  $$\left(a^2+b^2\right)\left(c^2+d^2\right)=\left(ac-bd\right)^2+\left(ad+bc\right)^2$$  This may seem amazing to us, but to people used to needing lots of symbolic manipulation, it was just part of a toolkit by the time number theory began ascending with Fermat or Euler.

Fact: Products of numbers writeable as sums of squares may also be written as sums of squares!

Jones and Jones use the notation $S_2$ to denote the set of numbers which can be written as a sum of squares, so another way to say this is $$\text{If }a,b\in S_2\text{, then }ab\in S_2\; .$$

@interact def _(m=(13,[0..100]),n=(8,[0..100])): try: a,b = two_squares(m) c,d = two_squares(n) html("We know we can write ${6}={0}\cdot {1}$ as $({2}^2+{3}^2)({4}^2+{5}^2)$".format(m,n,a,b,c,d,m*n)) html("But it is also writeable as $({0}\cdot{1}-{2}\cdot{3})^2+({0}\cdot{3}+{1}\cdot{2})^2={4}^2+{5}^2={6}$".format(a,c,b,d,abs(a*c-b*d),a*d+b*c,m*n)) except: html("Please pick numbers that are both writeable as a sum of two squares")

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

So we really can reduce questions back to primes, just like we want to.

Connection to pretty new mathematics

There is one final way to interpret all of this.  Suppose that $$n=a^2+b^2\; .$$  Then, if we let the symbol $i$ stand for a (putative) square root of negative one, so that $-1=i^2$, we could legitimately factor this: $$n=a^2-(i^2b^2)=(a+bi)(a-bi)$$  For instance, we could factor the prime number thirteen!!!

3^2+2^2; (3+2*i)*(3-2*i)
 13 13 13 13

It turns out that there is a beautiful connection between the theory of numbers in $S_2$ and the Gaussian integers (named after C.F. Gauss, who explored them a great deal, though others were at least incipiently aware of them), which we may define as the set $$\mathbb{Z}[i]=\{a+bi\mid a,b\in\mathbb{Z}\}$$ again, all the while assuming that we can have such a symbol $i$ with $i^2=-1$.

Indeed, if we bring back our lattice of integer points, we can think of such numbers as being points on the lattice, where the coordinate point $(3,2)$ corresponds to $3+2i$, one of the 'factors' of 13.  I'll plot both 'factors' below.

lattice_pts = [[i,j] for i in [-5..5] for j in [-5..5]] plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2) show(plot_lattice_pts+point([3,2],pointsize=30)+point([3,-2],pointsize=30),aspect_ratio=1)

Though we won't have time to explore it fully, there is a fantastically deep connection between these Gaussian integers and ways to write numbers as a sum of squares.

Indeed, it turns out that the word 'factor' becomes the legitimate word factor, and prime numbers can be defined in this new number system.  They turn out to be precisely the 'normal' primes of the form $4n+1$ and the 'factors' of the primes of the form $4n+3$ and $2$.

The basic reason is that we can use the Euclidean algorithm here; the 'size' of $3+2i$ is smaller than the 'size' of 13, and so we can use well-ordering on the 'size' of the numbers.   We'll define this 'size' next time when we prove exactly which integers are a sum of two squares.  See Section 10.2, or the internet, for more details about the connection to complex numbers.

There are many amazing questions to ask about this, and wonderful connections to abstract algebra.  Here is a picture to get you thinking.

@interact def _(viewsize=10): lattice_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2) Gaussian_primes = [ x for x in lattice_pts if ( is_prime(x[0]^2+x[1]^2) or (x[0]==0 and abs(x[1])%4==3 and is_prime(abs(x[1]))) or (x[1]==0 and abs(x[0])%4==3 and is_prime(abs(x[0]))) ) ] plot_Gaussian_primes=sum([polygon([(G[0]+1/2,G[1]+1/2),(G[0]+1/2,G[1]-1/2),(G[0]-1/2,G[1]-1/2),(G[0]-1/2,G[1]+1/2)],alpha=.6) for G in Gaussian_primes]) show(plot_Gaussian_primes+plot_lattice_pts,aspect_ratio=1) html("Plot of Gaussian primes with coordinates less than {0} in absolute value".format(viewsize))

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

Homework:

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.12.
3. Find as many integers $n$ as possible which are only writeable as a sum of squares via $n=a^2+a^2=2a^2$, i.e. $n$ is not writeable as a sum of distinct squares.
4. Verify the Brahmagupta-Fibonacci identity by hand (i.e. write all the algebra out).
5. 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\; .$$
6. 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}$.
7. 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.
8. Show a positive integer $k$ is the difference of two squares if and only if $k\not \equiv 2$ mod (4).  (Hint: Our Fermat stuff and why it ends...)
9. Look up the concepts of "Gaussian moat" and "Gaussian zoo" online and see what you think!