Find The Circle

OK, time to post the solution to the sums of squares problem I put up a little while ago.

I once heard of a game that Feynman used to play with his classmates called "find the circle" in which somebody would state some mathematical fact that has a pi in it and the other players would have to figure out what circle came up in the math behind the fact that resulted in a pi showing up (I can currently find no evidence of this game ever being played, so its possible I was imagining this story, or the relavent character was not Feynman). Essentially, the point is that the only places that pi ever would show up involve a circle, and when it shows up other places you can bet there is a circle hiding somewhere. Personally I don't agree with that philosophy, I think that pi is more fundamental than that, but this puzzle will not be a demonstration of my belief, a circle will show up quite nicely for us.

Alright, let us suppose we have a function, called g(k), which is the number of times that k can be written as the sum of two squares as outlined in the puzzle. Next we will let f(m) be the sum of 1 through m of g(k), then the average number of ways that numbers can be written as the sum of two squares is f(n)/n, that is, we seek to prove that for large N

f(N)/N = π

Consider taking some value k, for each way it can be expressed as the sum of two squares, we can write x²+y²=k for some (x,y), and for each pair (x,y) that solves x²+y²=k, we have a way to write k as the sum of two squares. That is, for each point in the plane with integer coordinates on a circle of radius √k, we have a way to express k as the sum of two squares. So we can say that g(k) is the number of integer points on a circle of radius √k. This means that we can say that f(m) is equal to the number of integer points that lie on a circle of radius equal to root some integer less than or equal to m. But every point with integer coordinates lies on a circle of radius equal to the square root of some integer (specifically (x,y) lies on a circle of radius √(x²+y²)) so f(m) is simply equal to the number of integer points that lie inside a circle of radius √m.

So, how do we calculate the number of integer points that lie inside a circle of radius R? Suppose for each such point, we shade the 1x1 square that is to its lower left. Then the total area shaded is equal to the number of points, and we can easily see that the shaded area is approximately equal to the area of the circle of radius R. I always hate using the term "approximately" in a non-technical sense though, so lets be technical about it.

It is easy to see that the shaded area equal to the circle area up to an error term that is, at most, the area of a strip with width √2 that runs around the circumference of the circle. In reality the error will be much smaller than this, we tend to have missing area in the upper right parts and extra area in the lower left parts and these will typically cancel pretty well, but nevermind that, I want an easy upper bound on the size of the error term. Since the shaded area is known to equal f(m) and the area of a circle of radius √m is πm, we can see that

f(m)=πm+C√m

where C√m is our error term, C can be positive or negative, and can depend on m, but its absolute value is bounded by a constant (the constant being 2π√2, for those paying attention).

So finally we can see that

f(N)/N=π+C/√N

for large enough N to consider the second term small, the average number of ways the first N numbers can be written as the sum of two squares is π.