Is there an algorithm for writing a number as a sum of three squares?

By Gauss's Theorem, every positive integer $n$ is a sum of three triangular numbers; these are numbers of the form $\frac{m(m+1)}2$. Clearly $$n = \frac{m_1^2+m_1}2 + \frac{m_2^2+m_2}2 + \frac{m_3^2+m_3}2,$$ so multiplying through by $4$ and completing the squares gives $$8n+3 = (2m_1+1)^2 + (2m_2+1)^2 + (2m_3+1)^2.$$ Thus writing $n$ as a sum of three triangular numbers is equivalent to writing $8n+3$ as a sum of three (necessarily odd) squares.

My question is;

Is there an algorithm for writing a positive integer as a sum of three squares?

• I find the question's wording is pretty bad. Oct 21 '12 at 16:34
• In general, there will be lots of ways to represent a given integer as the sum of three triangular numbers. I don't think any one of them has a distinguished formula. Oct 21 '12 at 17:32
• There is a lot of structure behind representations of sums of three squares. In an article that I don't yet understand, Simerka seems to have found a connection between writing numbers in different ways as sums of three squares and factoring this number. And writing $n$ as a sum of three triangular numbers is equivalent to writing $8n+3$ as a sum of three squares. Oct 21 '12 at 17:38
• This wording is better: taking back my downvote accordingly! Thanks! Oct 21 '12 at 18:32
• The arxive article is about Simerka's invention of a factoring algorithm using the class group of quadratic forms. He also has written an article on Legendre's work on the sums of three squares and trinary forms in which he connects sums of three squares with factoring integers in a way I do not yet understand. All I'm saying is that the question has some merit. There is also a hint at the factorization of integers in the algorithm presented in Will's link. Oct 21 '12 at 20:03

A representation of $n$ as a sum of three triangular numbers is equivalent to representing $8n+3$ as a sum of three odd squares. The question of computing representations as a sum of three squares has been much discussed here, see Efficient computation of integer representation as a sum of three squares

This problem is discussed in my paper with Rabin, Randomized algorithms in number theory, Commun. Pure Appl. Math. 39, 1985, S239 - S256. We give an algorithm that, assuming a couple of reasonable conjectures, will produce a representation as a sum of three squares in random polynomial time.

• Is it reasonable in practice? (I actually need to compute this :) Oct 22 '12 at 0:22
• Yes, it works very quickly. Oct 23 '12 at 13:20

One point that I do not see in the answer to which Igor links is size. Your target number is some $k \equiv 3 \pmod 8.$ So we take some odd $z$ and find out whether $k - z^2$ is the sum of two squares by factoring. My advice is to take $z$ as large as possible to begin, the decrease $z$ by 2 at each failure. There are two reasons for this.

First, the numbers $j \equiv 2 \pmod 8$ that actually are the sum of two squares are more frequent the smaller the approximate size of $j.$ Combining all congruence classes $\pmod 8,$ the number of integers up to some real positive $x$ is about $$\frac{0.7642 \; x}{\sqrt{\log x}},$$ so they get less frequent near $x$ as $x$ gets bigger.

Second, deciding whether $k-z^2$ is the sum of two squares is just factoring, and factoring is quicker for smaller numbers: powers of $2$ are irrelevant, any positive integer $j$ is the sum of two squares if and only if, when factoring $j,$ the exponent of any prime divisor $q \equiv 3 \pmod 4$ is even. Indeed, if there are any such, what you actually do is divide out all the appropriate $q^{2a}$ to arrive at a smaller number $j_0,$ write that as $x_0^2 + y_0^2 = j_0$ by solving that for each remaining prime power $p^w$ with $p \equiv 1 \pmod 4,$ which involves finding a square root of $-1 \pmod p$ and then screwing around. Combining pieces comes from $$(a^2 + b^2)(c^2 + d^2) = (ad-bc)^2 + (ac + bd)^2.$$ Oh, when yopu are done with $x_0^2 + y_0^2 = j_0,$ you put back each $q \equiv 3 \pmod 4$ with $(q^a x_0)^2 + (q^a y_0)^2 = q^{2a} j_0.$

Well, there is more to it, as you can see. But start with large $z.$ Size Matters.

• Is there a guarantee that there is a representation with z^2 being, say 7/8 of n or larger? Gerhard "Ask Me About System Design" Paseman, 2012.10.21 Oct 21 '12 at 20:19
• @Gerhard, I don't think there are any non-trivial guarantees, so the worst case behavior of starting with $z$ as large as possible is worse than the best case behavior of starting with $z$ small. Now that you mention it, at the cost of roughly constant slowdown, do two or three strategies at once (regarding the size of $z$) and hope for the best. But, all we know for sure is that, if $z$ is the largest, then $z^2$ is at least $1/3$ of the number. So that is one simple strategy, start $z$ there and increase. Oct 21 '12 at 20:31
• Now for the flip side: are there any examples known where there is no representation with z especially large? Gerhard "May Ask About Distribution Next" Paseman, 2012.10.21 Oct 21 '12 at 20:49
• @Gerhard, back from grocery shopping. I don't know that anyone has collected such examples, but i would expect them to get less frequent as the number gets large, as long as the number is not divisible by 4. So there would be no difficulty on a home computer picking out a range, say 1 to 1,000,000, run a triple loop in C, and report back when all $z$ are forced close to the minimum. As the target numbers get large the number of representations grow, so I would expect the odds of at least one solution with large $z$ to grow by "equidistribution," which goes back to Linnik. Oct 21 '12 at 21:29