When is the Sum of n Square Numbers Also a Perfect Square?
Date: 10/10/2005 at 21:59:29 From: TJ Subject: When is the sum of squares a square number In a geometry class I was teaching, I used the the formula P(n) = n(n + 1)(2n + 1)/6 to build up (pardon the pun) the idea of a "pyramidal number" (think of a stack of oranges). I had a sizable list when I stumbled on the coincidence that P(24) = 4900, which is a square number. Looking for more numbers of this sort, I was dismayed to find none (aside from P(1) = 1 = 1^2). I've written a program that searched up to n = 1,000,000,000, but I'm not sure if the floating point arithmetic is giving me proper results. Now the question is whether it can be shown no more exist? I tried setting up a contradiction in the (attempted!) proof below. We should assume there exists some i = 1, 2, 3 such that P(n) = n(n + 1)(2n + 1)/6 = i^2 and seek a contradiction. The first place to look is factors that are divisable by 6. In P(1) = 1*2*3/6, the 6 is cancelled out by the last two factors. In P(24) = 24*25*50/6, the 6 is cancelled out by the first term. But with 2n + 1, n + 1 , and n, I can't seem to find a way to narrow all of them out.
Date: 10/11/2005 at 19:33:08 From: Doctor Vogler Subject: Re: When is the sum of squares a square number Hi TJ, Thanks for writing to Dr. Math. What you have is a cubic Diophantine equation (which means a polynomial equation where you want integer solutions). And it's not an easy one either. My first thought is that you have an elliptic curve. Your equation is 6*i^2 = n(n + 1)(2n + 1). You can put this into standard form for an elliptic curve by assigning y = 72i x = 12n + 6 and then your equation becomes y^2 = x^3 - 36x or y^2 = x(x - 6)(x + 6). The theory of elliptic curves is deep and rich, and there is a lot more than I can explain in an email. I will say that there is a fairly simple method to find all of the rational points on an elliptic curve, with the caveat that there may be infinitely many. If (as happens not infrequently) there are only finitely many rational points on the elliptic curve, then finding them is pretty easy, and you can easily pick out the integer points from the list of rational points. When there are infinitely many rational points, they form a finitely generated group, which means that there is a way to "add" points together (which is done by intersecting lines with the elliptic curve) and there is a finite collection of generators (special rational points) such that every rational point is a (finite) sum of several copies of each of those generators. There is some talk of this in Cubic Diophantine Equation in Three Variables http://mathforum.org/library/drmath/view/66650.html In your case, those generators are (0, 0), (6, 0), and (-3, 9). I found these using some math programs off the internet, GNU Pari, and MW Rank (both free). Also, since the first two points have order 2 (adding either to itself will give zero), that means that all rational points are of the form k(-3, 9) + t where t is either zero, or one of the three points (0, 0), (6, 0), or their sum (-6, 0). So the easy way to look for integer points on your curve is to try various combinations of those generators, and the only ones where y is an integer divisible by 72 are (0, 0) (18, 72) (294, 5040) and their negatives (0, 0) (18, -72) (294, -5040). Those correspond to the solutions you already found, n=0, n=1, and n=24. But does this prove that there are no others? No, it doesn't, because there are infinitely many points to check, and we obviously can't check all of them. In fact, there is a proof by Siegel that every elliptic curve has only finitely many integer points. So it is likely that these are all of them, but it still doesn't prove that there are no others. Then there is a fairly new technique for finding all integer points by finding an upper bound on the coefficients of the generators (i.e. the k above). That means you only have to check k values up to that bound. But this technique is quite complicated and rather advanced, so it's probably best to see if we can prove the same thing by other means. So let's start over and try something else first. Here is a technique that works pretty well for certain kinds of Diophantine problems like yours. Namely, if you have a square that equals a formula that you can factor, you try to show that each factor has to be a square, or something close to it. This is what we will do: Your equation is 6*i^2 = n(n + 1)(2n + 1). First, and most importantly, we should try to show that the factors on the right are relatively prime, or nearly so. In your case, it doesn't take too much work to show that they must be relatively prime. That means that, when you divide up the prime factors of 6i^2, which will be something like 2^(odd) * 3^(odd) * p^(even) * q^(even) * ... * r^(even), among the three numbers n, n+1, and 2n+1, all of the powers of each prime will go to the same number. That means that, of the three factors n, n+1, and 2n+1, either one of them is 6 times a square and the other two are squares, or one of them is twice a square, one is three times a square, and the other is a square. Now we consider each possibility in turn. There are nine: Case 1: n = a^2, n+1 = b^2, 2n+1 = 6c^2. Case 2: n = a^2, n+1 = 6b^2, 2n+1 = c^2. Case 3: n = 2a^2, n+1 = 3b^2, 2n+1 = c^2. Case 4: n = 2a^2, n+1 = b^2, 2n+1 = 3c^2. Case 5: n = 3a^2, n+1 = 2b^2, 2n+1 = c^2. Case 6: n = 3a^2, n+1 = b^2, 2n+1 = 2c^2. Case 7: n = a^2, n+1 = 3b^2, 2n+1 = 2c^2. Case 8: n = a^2, n+1 = 2b^2, 2n+1 = 3c^2. Case 9: n = 6a^2, n+1 = b^2, 2n+1 = c^2. For other similar Diophantine equations, you might not have quite so many cases. In any case, the hope is that you can rule out certain cases completely, and can describe all solutions in the remaining cases without too much trouble. Let's see if we can do this: Case 1: n = a^2, n+1 = b^2, 2n+1 = 6c^2. In this case, 1 = (n+1) - n = b^2 - a^2 = (b - a)(b + a), and the only way that 1 can be written as a product of two factors is 1*1 and -1*-1. In either case, the difference is zero, which means that a=0, and therefore n=0. So n=0 and i=0 is the only possible solution in case 1. This is a technique that has many useful applications to various Diophantine equations, so it was worth mentioning. But, in fact, there is an easier way to show that there are no solutions in case 1 (notice that n=0 doesn't give 2n+1 six times a square; this solution actually belongs in case 9). You see, 2n+1 is odd, while 6c^2 is even. So they can't be equal! Case 2: n = a^2, n+1 = 6b^2, 2n+1 = c^2. In this case, we have 1 = c^2 - 2a^2 1 = 12b^2 - c^2 1 = 6b^2 - a^2 but the important one is the middle one, 1 + c^2 = 12b^2 is divisible by 3. It turns out that no square is one less than a multiple of 3, which is easy to prove. (If you haven't seen this before, I can show you how to prove it.) Essentially, what we have done is shown that there are no solutions mod 3. If you don't know what thas means, see our section about modular arithmetic at What is Mod? http://mathforum.org/library/drmath/sets/select/dm_mod.html Case 3: n = 2a^2, n+1 = 3b^2, 2n+1 = c^2. This is the same as case 2. Case 4: n = 2a^2, n+1 = b^2, 2n+1 = 3c^2. This is also like case 2; consider (2b)^2 + 1 or (2a)^2 + 1 in terms of c. Case 5: n = 3a^2, n+1 = 2b^2, 2n+1 = c^2. This is also like case 2; consider (2b)^2 + 1 in terms of a. Case 6: n = 3a^2, n+1 = b^2, 2n+1 = 2c^2. But 2n+1 is odd, while 2c^2 is even, so this can't happen. Case 7: n = a^2, n+1 = 3b^2, 2n+1 = 2c^2. This is just like case 6. So now we've ruled out seven of the nine cases, and there were no solutions. In case 8 is the solution n=1 (with a=b=c=1), and in case 9 are the solutions n=0 (with a=0 and b=c=1) and n=24 (with a=2, b=5, and c=7). Cases with solutions are usually harder than cases without, so I saved these for the end. Case 8: n = a^2, n+1 = 2b^2, 2n+1 = 3c^2. Case 9: n = 6a^2, n+1 = b^2, 2n+1 = c^2. We'd like to try to do some modular arithmetic, but the existance of even a single solution really prevents modular arithmetic from doing hardly anything at all in most cases. So we have to resort to some more sophisticated mathematics. At some point, you might start wondering if we should have just stopped with the elliptic curve stuff at the beginning.... Let's look at case 9. Case 8 is similar. You have three equations b^2 - 6a^2 = 1 c^2 - 12a^2 = 1 2b^2 - c^2 = 1, but the first one is just the average (sum and divide by 2) of the last two, so we might as well only concern ourselves with the last two. If we solve each of those equations separately, then we have two Pell Equations. Those are fairly complicated in themselves, but we have a solution, of sorts. You can read a lot about them at Solving with the Pell Equation http://mathforum.org/library/drmath/view/66869.html and more by searching our archives for the phrase "pell equation" or the Internet for the same phrase. In any case, we find that all integer solutions to the middle equation have c = [ (2 + sqrt(3))^k + (2 - sqrt(3))^k ]/2, and a = [ (2 + sqrt(3))^k - (2 - sqrt(3))^k ]/(4*sqrt(3)), or their negatives, where k has to be even (for the integer 2a to be even). All integer solutions to the last equation have c = [ (1 + sqrt(2))^m + (1 - sqrt(2))^m ]/2, and b = [ (1 + sqrt(2))^m - (1 - sqrt(2))^m ]/(2*sqrt(2)), or their negatives, where m has to be odd. Despite the square roots in those formulas, they will always give integers. Also, in each case, the first power determines the size of the number, since the second one will always be less than 1, and if the exponent (k or m) is large, then it will be almost zero. Actually, that last statement is only true when k and m are positive; the reverse is true when k and m are negative. In any case, we have to find (k, m) pairs where we can get the two formulas to give the same numbers. Well, k=0 and m=1 works, and this gives the solution a=0, b=1, and c=1. Also, k=2 and m=3 works, and this gives the solution a=2, b=5, and c=7. We can check other small values of k and m, but what about for large k and m? Well, when k and m are large, then we *nearly* have 2c = (2 + sqrt(3))^k = (1 + sqrt(2))^m, and if we take logs, then we find that we *nearly* have k log (2 + sqrt(3)) = m log (1 + sqrt(2)), and m log (2 + sqrt(3)) --- = -------------------. k log (1 + sqrt(2)) So this leads one to look for a really good rational approximation to that fraction on the right, which is approximately 1.4942107595693304002403087419748685961576760606761197594366027.... You can clearly see that 3/2 is a good approximation. The way to look for other good approximations is to look for large terms in the continued fraction expansion of this number, done by repeatedly subtracting off the integer part and then taking the reciprocal. We get 1, 2, 42, 1, 2, 6, 4, 11, 2, 4, 9, 1, 1, 1, 1, 7, ... and the only one that really stands out is the 42, indicating that the fraction up to that point was pretty close, and that is the 3/2 that we already mentioned. But, again, that doesn't prove that we won't find an astronomical term much later. In fact, for this kind of thing, we need to appeal to transcendental number theory, sometimes referred to as "Baker's method," after one of the foremost men in developing this theory (or *the* foremost, perhaps). But this method is also pretty complicated, and not anything I could explain in an email. (In fact, I might not be able to explain it at all, except by recommending Baker's book "Transcendental Number Theory.") Anyway, I had better stop there. I have left off at two different loose ends, each of which provides a difficult way to prove that all of the integer solutions to your Diophantine equation are the ones you already found. I tried to find a simple way to do the same thing, but to no avail. Oh well. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 11/09/2005 at 07:45:35 From: TJ Subject: When is the sum of squares a square number Dear Dr. Vogler, Thank you so much for your very thoughtful reply to my question. I'm sorry for not thanking you sooner, but my duties as a teacher occupy most of my daylight hours. While my understanding of elliptical curves and number theory is slight, your explaination was clear and engaging. It is nice to run in to a question with "a little meat on its bones"! With regards to this question, I am (sadly) a little out of my depth. Though I doubt I can make a significant contribution to its analysis, however, I could continue a numerical search for a solution. So, my only other question is whther the question is closed or not? At the end of the analysis, am I correct in reading that you mentioned there *might* be a solution? While the solution may be a bit over my head, has the question been resolved or not? If not, I can continue to work on a numerical approach. Otherwise, I can rest a little easier knowing there is a solution (and that there are people of your intellect and generosity still walking the Earth!). Thank you again for your time and consideration. Sincerely, TJ
Date: 11/09/2005 at 09:19:27 From: Doctor Vogler Subject: Re: When is the sum of squares a square number Hi TJ, I would find it highly unlikely that there is another larger solution that we haven't found yet, although I haven't proven it. But it is not an open question in the sense that there are published, practical algorithms for solving this kind of problem. It just takes someone going through the effort of working out all of the details. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum