Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/