Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
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
show 3 more comments

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.