Sums of Squares

p mod 4	k = 0	1	2	3	4	5	6	…
2	1	1	1	1	1	1	1
3	1	0	1	0	1	0	1
1	1	2	3	4	5	6	7

Multiply the result by 4, and you get the number of solutions in integers to the equation n = x² + y² … or divide the result by 2 and round up, and you get the number of interesting solutions, solutions satisfying the condition 0 ≤ y ≤ x.

Given the first method, it's easy to see why the second works: all the solutions appear in sets of eight, except for solutions of the form (a,0) and (a,a), which appear in sets of four, and which are mutually exclusive because the square root of 2 is irrational. But why does the first method work? I'm afraid I can't help you there. There's a proof in Introduction to Number Theory, but there's nothing in it that jumps out at me as a reason.

Anyway, just as an example, let's find the number of ways for n = 850. We have three terms, 2, 5², and 17, with table values 1, 3, and 2, so the product is 6, and the number of interesting solutions is 3. (You can figure out what they are pretty easily from the table of squares.)

Now, with that as background, I can tell you a funny story. In college, I took a course in solid-state physics, where among other things we talked about x-ray diffraction in crystals. The number of diffraction spots, it turns out, depends on how many points of the reciprocal lattice lie on a certain sphere … one point represents the incident beam, the rest represent diffraction spots. The next part I don't remember exactly … the professor asserted that certain numbers were or weren't possible, and I did or didn't believe him. In any case, I ended up thinking about the integer lattice in two dimensions, and about how circles could be made to intersect it. It's easy to find circles that contain two, three, or four points, so the particular problem I was concerned with was whether there was a circle that contained exactly five points. (Don't you wish you knew the answer?)

In the course of that investigation, I decided I needed to know about numbers that decomposed as sums of two squares in more than one way. At the time, I didn't understand the methods above, so I just wrote a program to print out all such numbers up to 900. I found that printout again the other day, and noticed that it had two striking properties.

First, most of the numbers, 54 out of 72, ended in “0” or “5”. That makes sense, given what I know now … to have multiple solutions, you need prime factors of the form 4m+1, and of those, 5 is by far the most economical.

Second, of the remaining numbers, most were products. Imagine my surprise when I saw those on a piece of paper fifteen years old! There were nine true products, starting with 221 and 377; three squares, which count as products in some kind of technical sense; and six numbers obtained by applying factors of 2 and 4 to the others.

I think the lesson here, if there is one, is that being able to factor numbers is very handy when you're dealing with multiplicative functions. (A multiplicative function is one that satisfies f(ab) = f(a) f(b) whenever a and b are relatively prime. Any such function can be computed using a table like the one above. Other examples include the number of divisors, the sum of divisors, and Euler's function, which showed up in Repeat Length.)