# Listing all solutions to $n = x^2 + y^2 + z^2$ with integers

I would like to list all ways of writing $n$ as the sum of 3 squares. This is slightly different from finding just one:

My current implementation is the naive one which runs in $O(n^{3/2})$ time: Write all numbers $n = x^2 + y^2 + z^2$ with

• $x < \sqrt{n}$
• $y < \sqrt{n - x^2}$
• $z < \sqrt{n - x^2 - y^2}$

Perhaps there is a more efficient way using Quaternions or matrices or something?

# Finding All Representations

The linked questions efficiently compute one representation $n = x^2 + y^2 + z^2$. However, I am hoping to find a complete list of all representations and I would like to know if we can do any better than the naïve algorithm.

• Possible duplicate of Is there an algorithm for writing a number as a sum of three squares? – Igor Rivin Oct 2 '15 at 19:52
• Duplicate of mathoverflow.net/questions/110239/… – Igor Rivin Oct 2 '15 at 19:52
• @IgorRivin Can the algorithm for finding one representation be turned into an algorithm for finding all representations? – john mangual Oct 2 '15 at 19:54
• A fair point, so the question is not quite a duplicate. – Igor Rivin Oct 2 '15 at 20:08
• Somewhat less naive is to loop over $x < \sqrt{n}$. For each $m = n - x^2$ you then want to find all representations $m = y^2 + z^2$, which can be obtained by factoring $m$ over the Gaussian integers. I'm pretty sure we don't know the true complexity of that (not even of factoring over the integers), but it's certainly $o(m)$. – Robert Israel Oct 2 '15 at 20:12

The number of representation can be as big as $\sqrt{n},$ so this is a lower bound on the complexity of any algorithm. Now, the algorithm is to iterate through all $k\leq \sqrt{n},$ and try to represent $n-k^2$ as a sum of squares (in all possible ways). This is equivalent to factoring, so the complexity will be not that bad above optimal (factoring is "hard", but not so hard compared to $\sqrt{n},$ indeed, this algorithm runs in time $O(n^{1/2 + \epsilon})$ for any $\epsilon > 0.$)
• For each of the numbers $k < \sqrt{n}$ I can factor $n - k^2$ which I can do in $\sqrt{n}$ time, so the total run time is $\sqrt{n} \times \sqrt{n} = n$. – john mangual Oct 2 '15 at 20:35
• The factorization step takes $log(n)$ time or something ? – john mangual Oct 2 '15 at 21:20