# 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 , then return

2. Write as

3. if then return the hard coded representation of . Here, . Representations for these numbers can be found here.

4. If is a perfect square then return

5. if , find an odd number such that is a prime. Set and . Find two numbers such that . (You can use Cornacchia’s algorithm for this. Return .

6. If or then find an odd number such that is a prime. Else find an even number with the above requirement. Set and . Find such that . Return .

Note that above algorithm can not be used if for some integer . That is if is in the form .

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

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

1. Write as .

2. If then set and . If or then set and . Otherwise set .

3. Use the algorithm described earlier to represent as a sum of three squares. Say, .

4. Return .

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 needs to be represented as a sum of squares, we can divide variables into segments of four and divide into that same number of segments and represent each segment by four squares using the algorithm given above.

- Posted in: GSoC-2013-SymPy
- Tagged: additive number theory, sum of four squares, sum of three squares

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?

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.