Puzzle time - sums of two squares
-
wrote on 29 Nov 2021, 13:51 last edited by
On average, how many ways are there to write a positive number n as the sum of two squares?
In other words, suppose n is a random integer between 1 and a zillion. What is the expected number of ordered pairs (i,j) of integers such that n = i^2+j ^2 ? For example, if n = 25 we get not only 25 = 0^2 + 5^2 and 25 = 3^2 + 4^2, but also 25 = 5^2 + 0^2 = 3^2 + (-4)2 etc., twelve ways in all.
-
wrote on 2 Dec 2021, 14:27 last edited by jon-nyc 12 Feb 2021, 14:28
HINT:
Let f(n) be the number of ways to write n as the sum of two squares. Then the average of f(n) for n = 1,2,...,Z is T/n where T is the total number of integer pairs (i,j) for which i^2 + j^2 is at most Z. What do these pairs (i,j) look like as Cartesian coordinates on the plane?
-
wrote on 2 Dec 2021, 15:10 last edited by Horace 12 Feb 2021, 15:30
Missed this one the first time. So you're looking for the number of pairs of integers lying on the circle of radius sqrt(n) since a^2 + b^2 is distance from origin squared. The problem then becomes the number of times that circle passes through a point composed of two integers. By symmetry and restriction to positive integers you would only look at one eighth of the circle.
Average number of times of an unbounded n implies this number does not increase without limit, and may be cyclical. I suspect the problem can be solved brute force by observing this cycle or this limit, but there is probably an elegant way to consider how many times this circle passes through integer vertexes.Actually I suppose the problem is asking for a function of n rather than a specific number. So it then becomes the number of times a circular arc of length (pi * 2 * sqrt(n))/8 passes through integer points on the plane.
-
wrote on 2 Dec 2021, 15:36 last edited by
Really we're looking for the expected value across all the integers from 1 to a zillion.
-
wrote on 2 Dec 2021, 17:33 last edited by
Hm, that number looks pretty familiar. A favorite of Larry's in fact.
-
wrote on 2 Dec 2021, 18:08 last edited by
Yes, by way of that hint, this one collapses into the Gauss Circle Problem.
-
wrote on 2 Dec 2021, 20:03 last edited by
Klaus and Jon doing math.
The sums of two squares.
-
wrote on 2 Dec 2021, 20:32 last edited by
It’s kind of a cool result. It’s framed as a kind of number theory problem and the answer is a transcendental number associated with geometry.
-
wrote on 2 Dec 2021, 20:44 last edited by
It is a cool result. But I'm not sure there's any low-math, non-brute-force way to get there. The connection between sum of squares and a circle is not very far towards the answer.
-
wrote on 2 Dec 2021, 20:55 last edited by
Unless you recognize it as the Gauss Circle Problem, which has a well-known answer.
-
wrote on 2 Dec 2021, 21:10 last edited by
And I would add an intuitive answer.
-
wrote on 2 Dec 2021, 21:30 last edited by
Yeah I guess the area thing would be intuitive and from there the circumference thing is also intuitive.