# 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. – Julien Puydt 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. – Greg Martin 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. – Franz Lemmermeyer Oct 21 '12 at 17:38
This wording is better: taking back my downvote accordingly! Thanks! – Julien Puydt Oct 21 '12 at 18:32
A bit confusing, Simerka lived a long time ago, the recent item is a history/overview by Franz, see arxiv.org/abs/1201.0282 Meanwhile, what is quite definitely in Grosswald's book is the relation of number of representations as three squares to certain classnumbers, see mathoverflow.net/questions/3596/… – Will Jagy Oct 21 '12 at 19:17

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 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 :) – Igor Rivin Oct 22 '12 at 0:22
Yes, it works very quickly. – Jeffrey Shallit 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 – Gerhard Paseman 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. – Will Jagy 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 – Gerhard Paseman 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. – Will Jagy Oct 21 '12 at 21:29