Clarification of sums of squares formula

Question

I’m trying to find all the ordered sums of squares: $n=x^2+y^2$, $0\leq x\leq y$ for particular $n$.

I’m confused about the sum of squares formula presented on Wolfram Alpha

“ To find in how many ways a positive integer n>1 can be expressed as a sum of $k=2$ squares ignoring order and signs, factor it as”

$n=2^{a_0}p_1^{2a_1}\cdots p_r^{2a_r}q_1^{b_1}\cdots q_{s}^{b_s}$, $p_i \equiv 3\pmod4$, $q_j\equiv 1 \pmod4$

...

then it is deduced that $r_2(n)=4(b_1+1)(b_2+1)\cdots(b_s+1)$ if $n$ can be factored in such a way, $r_2(n)=0$ if not.

I get that the powers of the $p_i$’s need to be even, because if $p$ is prime and $p \not\equiv 1 \pmod 4$ then $p$ cannot be written as a sum of squares, so multiplying by a square does not affect our sum, as sums are closed under multiplication.

This formula reminds me of a combinatorics problem but I can’t figure out where the $4$ comes from, or why we $\color{red}{\text{add 1}}$ to the powers $b_j$’s in the product. Why doesn’t $2^{a_0}$ affect $r_2(n)$? Or does it?

Edit:

I’m really having trouble understanding what the formula for $r_2(n)$ really means, say I had $n=50$ then the formula gives $r_2(50)=4\cdot 3=12$ while $50=1^2+7^2=5^2+5^2$ are the only two representations.

How does one go from $12$ to $2$?

Furthermore, given this question they were able to divide $48$ by $8$ to get $6$ representations, but I thought the formula was irrespective of signs and order?

Answer 1

One really needs to count all the ways to square two integers and sum to get the number in question. The $r_2(50)=12$ result, for example, is because we really do count separately each of the representations \begin{align*} 50&=1^2+7^2=(-1)^2+7^2=1^2+(-7)^2=(-1)^2+(-7)^2 \\ &=7^2+1^2=(-7)^2+1^2=7^2+(-1)^2=(-7)^2+(-1)^2 \\ &=5^2+5^2=(-5)^2+5^2=5^2+(-5)^2=(-5)^2+(-5)^2. \end{align*} In other words, we really are counting all ordered pairs of integers (not unordered pairs of positive integers): $$ r_2(n) = \#\big\{ (x,y)\in\Bbb Z^2\colon x^2+y^2=n \big\}. $$

Answer 2

If $n$ is a perfect square, the number of ways it can be expressed as the sum of two squares is $2^{x-1}\quad $ where $x$ is the number of "unique" odd prime numbers whose product makes up the square root of $n$. We can find these, starting with Euclid's formula shown here as:

$$ \qquad A=m^2-k^2\qquad B=2mk \qquad C=m^2+k^2\qquad$$

Here, $\quad C=\sqrt{n}\quad$ and we can find $\quad A,B\quad$ by solving the $C$-funtion for $k$ and testing a defined range of $m$-values to see which yield integers. Here is an example for $C = 65 = 5\times13$ which is a composite of $2$ primes so it can be represented by $2^{2-1}=2$ Primitive sums. There may be non-primitives but $2^{2-1}=2$ is the minimum. Note that, for example, $C=425=5^2\times13$ also has only two primitives because it has only two "uniques" prime factors.

\begin{equation} C=m^2+k^2\implies k=\sqrt{C-m^2}\qquad\\ \text{for}\qquad \bigg\lfloor\frac{ 1+\sqrt{2C-1}}{2}\bigg\rfloor \le m \le \lfloor\sqrt{C-1}\rfloor \end{equation}

The lower limit ensures $m>k$ and the upper limit ensures $k\in\mathbb{N}$. $$C=65\implies \bigg\lfloor\frac{ 1+\sqrt{130-1}}{2}\bigg\rfloor=6 \le m \le \lfloor\sqrt{65-1}\rfloor=8\\ \land \quad m\in\{7,8\}\Rightarrow k\in\{4,1\}\\$$ $$F(7,4)=(33,56,65)\qquad \qquad F(8,1)=(63,16,65) $$

As a final note, if $A$ is odd and $B$ is even in a primitive triple, as is customary, about half of all triples have $A>B$ and about half have $A<B$ as you can see in this sample.

\begin{array}{c|c|c|c|c|c|} n & k=1 & k=2 & k=3 & k=4 & k=5 \\ \hline Set_1 & 3,4,5 & 5,12,13& 7,24,25& 9,40,41& 11,60,61 \\ \hline Set_2 & 15,8,17 & 21,20,29 &27,36,45 &33,56,65 & 39,80,89\\ \hline Set_3 & 35,12,37 & 45,28,53 &55,48,73 &65,72,97 & 75,100,125 \\ \hline Set_{4} &63,16,65 &77,36,85 &91,60,109 &105,88,137 &119,120,169 \\ \hline Set_{5} &99,20,101 &117,44,125 &135,72,153 &153,104,185 &171,140,221 \\ \hline Set_{6} &43,24,145 &165,52,173 &187,84,205 &209,120,241 &231,160,281 \\ \hline \end{array} These were from an alternative formula that generates only and all of the subset of triples where $GCD(A,B,C)=(2x-1)^2, x \in\mathbb{N}$. The idea is the same for both formulas but the output of this one makes it clearer. With the exception of $Set_1$, for each $Set$ of triples, at least the first $k=n$ triples have $A>B$ which is more than half of all triples for large numbers.

\begin{align*} A=(2n-1)^2+ & 2(2n-1)k \\ B= \qquad\quad\quad & 2(2n-1)k+ 2k^2\\ C=(2n-1)^2+ & 2(2n-1)k+ 2k^2\\ \end{align*}