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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: