Find the cardinality of the following set $S_n=\{(x,y)|x^2+y^2=n, \text{where }x,y,n \in \mathbb Z\text{ and }n\geq0 \}$

Question

We are given with $$S_n=\{(x,y)|x^2+y^2=n, \text{where }x,y,n \in \mathbb Z\text{ and }n\geq0 \}$$ Now observe that $-\sqrt n\leq x\leq\sqrt n $ and similarily, $-\sqrt n\leq y\leq\sqrt n $. This means that $-\left \lfloor{\sqrt n}\right \rfloor\leq x\leq \left \lfloor{\sqrt n}\right \rfloor$ and $-\left \lfloor{\sqrt n}\right \rfloor\leq y\leq \left \lfloor{\sqrt n}\right \rfloor$. Through this result one can easily write code and figure out the cardinality of set $S_i$ but I was wondering whether an expression can be found that would allow one to directly compute $|S_i|$.

Answer 1

Let us denote the size $|S_n|$ as $r_2(n)$, as is done in this answer and on this Wolfram page. It can be computed as $$ r_2(n) = 4 \sum_{\text{odd } d \mid n} (-1)^{\frac{d-1}{2}}. $$ However, this formula is a bit cryptic. More usefully, $\frac{r_2(n)}{4}$ is multiplicative, that is for $a$ and $b$ relatively prime, $\frac{r_2(ab)}{4} = \frac{r_2(a)}{4} \cdot \frac{r_2(b)}{4}$. And, for a prime $p$: $$ r_2(p^k) = 4 \cdot \begin{cases} 1 & \text{if } p = 2 \\ 0 & \text{if } p \equiv 3 \pmod{4} \text{ and } k \text{ is odd} \\ 1 & \text{if } p \equiv 3 \pmod{4} \text{ and } k \text{ is even} \\ (k+1) & \text{if } p \equiv 1 \pmod{4}. \end{cases} $$ So this gives another way to write $r_2(n)$: if every odd prime congruent to $3$ mod $4$ divides into $n$ an even number of times, then we have $$ r_2(n) = 4 \prod_{\substack{p \equiv 1 \pmod{4} \\ p^k \mid n}} (k+1), $$ where $p^k$ is the highest prime power dividing $n$. Otherwise, $r_2(n) = 0$.

This sequence can be found on OEIS here.

---

Some special cases:

• The sum of two squares theorem: in your context, this says that $|S_n| = 0$ if $n$ contains an odd number of copies of some prime divisor $p \equiv 3 \pmod{4}$, and $|S_n| > 0$ otherwise.

• For $p, q$ distinct primes $\equiv 1 \pmod{4}$, $|S_p| = |S_q| = 8$ and $|S_{pq}| = 16$. (Because we allow for $x, y < 0$, a factor of $4$ arises for the sign of $x$ and $y$, and a factor of $2$ is for switching $x$ and $y$.) This is discussed in some related questions.

• The most trivial case, $|S_1| = 4$. We could also define $|S_0| = 1$, but most of the formulas in this answer don't apply for $|S_0|$.

---

Generating function:

$$ \sum_{n=1}^\infty r_2(n) x^n = 4\sum_{k=\color{red}{0}}^\infty \frac{(-1)^{k} x^{2k+1}}{1 - x^{2k+1}} = 4 \sum_{k=\color{red}{1}}^\infty \frac{x^{k}}{1 + x^{2k}}, $$

which can also be written as an infinite product involving Pochhamer symbols if we like. This is derived from the formula at the top of this post.

---

Cumulative sums: Gauss's circle problem

Finally, others have mentioned Gauss's circle problem. $\sum_{n=0}^{N} |S_n|$ is the number of integer coordinates inside a circle of radius $\sqrt{N}$ about the origin. Therefore it approximates the area of that circle, and we have $$ \sum_{n=0}^{N} r_2(n) \approx N \pi. $$

---

Notes on how to prove the formulas

I do not provide a proof here of the formulas for $r_2(n)$. The basic idea is that they come from Gaussian integer factorization (unique factorization property in the ring $\mathbb{Z}[i]$). In particular, every $(a,b)$ such that $n = a^2 + b^2$ corresponds to a factorization $$ n = (a + bi)(a - bi), $$ so to count the number of such factorizations we can count the number of ways to write $n = z \overline{z}$ where $z \in \mathbb{Z}[i]$. Then we factorize $n$ in the Gaussian integers, where the primes equivalent to $3$ mod $4$ do not decompose, but the primes equivalent to $1$ mod $4$ split into pairs. Using this, we can derive the desired formulas.