# fractal structure of the sum of squares function

The sum of squares function came up at a job interview, corrected for signs and symmetry.

$d_2(n)=\#\{(x,y): x^2 + y^2 = n\}$

However, want $(x,y)\sim (\pm x, \pm y) \sim (y,x)$. The first 20 numbers are:

1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0

A quick search on Online Encyclopedia of Integer Sequences shows a few candidates:

• number of partitions into 2 squares A000161
• the regular paper-folding (dragon curve sequence) A014577
• sequence A082410

So my script is probably correct :-) but I wonder what relation the sum of squares function has with the dragon curve.

• Number of ways of writing n as a sum of 2 squares when order does not matter.
• Number of similar sublattices of square lattice with index n.
• Sequence can be obtained by L-system with rules L->L1R, R->L0R, 1->1, 0->0, starting with L, and dropping all L and R
• One half of the infinite Farey Tree can be mapped one-to-one onto A014577 since both sequences can be derived directly from the binary. First few terms are:

1,...1,...0,...1,...1,...0,...0,...1,...1,...1,...
1/2.2/3..1/3..3/4..3/5..2/5..1/4..4/5..5/7..5/8,..

Do these objects belong? Are these sets of objects correlated or is it a coincidence?

Maybe some relation to the Gauss circle problem.

-

[Corrected from Erick Wong's comment below.]

There is definitely a relationship for small $n$.

This depends on the formula in the OEIS page that $$a_n=\frac{1+\left(\frac{-1}{n}\right)}2$$

where $\left(\frac{-1}{n}\right)$ is the Jacobi symbol. It turns out, if $n=x^2+y^2$ has a solution, then $\left(\frac{-1}{n}\right)=1$. For $n<21$, it is also true that $\left(\frac{-1}{n}\right)=-1$ if there is no such solution. So, for $n<21$, $a_n=1$ if and only iff $d_2(n)>0$.

In general, if $a_n=0$ then $d_2(n)=0$. It is not true, as I wrote earlier, that if $d_2(n)=0$ then $a_n=0$. For example, $d_2(21)=0$ but $a_{21}=1$.

-
The characterization of $(-1/n) = 1$ is for the Legendre symbol, not the Jacobi symbol, no? Take, for instance $n=21$ (which is conveniently located just after the explicitly calculated terms in the question...). –  Erick Wong Jan 17 '13 at 17:48
Oh, Duh! You are quite right, brain death. –  Thomas Andrews Jan 17 '13 at 17:49