# Change of plans for general sum of squares

Hi All,

In my last post I described about Euler’s four square identity to for solving general sum of squares equation. My idea was to factorize the number, represent each prime as a sum of four squares, then use Euler’s four square identity to construct the sum of four squares representation for the original Number. But I found it slower than the algorithm I found here. So I adapted the latter. The idea is to reduce the problem of representing a number as a sum of four squares to representing a number as a sum of three squares.

#### Algorithm for representing a positive number n as a sum of three squares

1. If $n == 0$, then return $(0, 0, 0)$
2. Write $n$ as $4^vn_{1}$
3. if $n_{1} \in S$ then return the hard coded representation of $n_{1}$. Here, $S = {2, 3, 10, 34, 58, 85, 130, 214, 226, 370, 526, 706, 730, 1414, 1906, 2986, 9634}$. Representations for these numbers can be found here.
4. If $n_{1}$ is a perfect square then return $(2^v\sqrt{n_{1}}, 0, 0)$
5. if $n_{1} = 3 (mod 8)$, find an odd number $i, i < \sqrt{n_{1}}$ such that $\frac{n_{1} - i^2}{2}$ is a prime. Set $x = i$ and $p = \frac{n_{1} - i^2}{2}$. Find two numbers $y, z$ such that $y^2 + z^2 = p$. (You can use Cornacchia’s  algorithm for this. Return $(2^vx, 2^v(y + z), 2^v|y - z|)$.
6. If $n_{1} = 2 (mod 8)$ or $n_{1} = 6 (mod 8)$ then find an odd number $i, i < \sqrt{n_{1}}$ such that $n_{1} - i^2$ is a prime. Else find an even number $i, i < \sqrt{n_{1}}$ with the above requirement. Set $x = i$ and $p = n_{1} - i^2$. Find $y, z$ such that $y^2 + z^2 = p$ . Return $(2^vx, 2^vy, 2^vz)$.

Note that above algorithm can not be used if $n_{1} = 8k + 7$ for some integer $k \in Z$. That is if $n$ is in the form $4^v(8k + 7)$.

#### Algorithm for representing a positive number n as a sum of four squares

Every non-negative integer $n$ can be represented as a sum of four squares.

1. Write $n$ as $4^vn_{1}$.
2. If $n_{1} = 7 (mod 8)$ then set $d = 2$ and $n_{1} = n_{1} - 4$. If $n_{1} = 6 (mod 8)$ or $n_{1} = 2 (mod 8)$ then set $d = 1$ and $n_{1} = n_{1} - 1$. Otherwise set $d = 0$.
3. Use the algorithm described earlier to represent $n_{1}$ as a sum of three squares. Say, $x^2 + y^2 + z^2 = n$.
4. Return $(2^vd, 2^vx, 2^vy, 2^vz)$.

By using these two algorithms one can represent any non-negative integer as a sum of four squares. In the general sum of squares equation, where a given integer $n$ needs to be represented as a sum of $k$ squares, we can divide $k$  variables into segments of four and divide $n$ into that same number of segments and represent each segment by four squares using the algorithm given above.

Advertisements

### 2 Comments

1. Lee

why is 730 represented as 1^2 + 27^2 rather than 8^2 + 15^2 + 21^2? if there is a representation of an integer as the sum of three positive squares should that not be used instead of a representation as a sum of two positive squares?

2. Thank you lee for the comments. The algorithm I have used admits zeros in the representation. It provides a generalized method to construct a represention of a number as a sum of three integers. Normally, in number theory, zeros are allowed in these representations. If not, the four square theorem would not be true. But it would be great to look for a representation which does not contain zeros if such a one exists. But It’s computationally hard and sometimes not possible.