Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sums of Squares

  1. Jun 8, 2006 #1
    Suppose X is a set consisting of squares with the property that any addition with elements of X (where no two are the same) gives a square (might not be in X). How many elements can X have?
     
  2. jcsd
  3. Jun 8, 2006 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    Wild guess - zero or infinite.
     
  4. Jun 8, 2006 #3

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Zero is definitely wrong. X can have at least two elements, e.g. {9, 16}. But can X have infinitely many? I doubt it. If X could have infinitely many, then there would be some natural n such that there are infinitely many Pythagorean triangles that have one non-hypoteneuse side with length equal to n. There's a theorem:

    You will get every primitive Pythagorean triple (a,b,c) with a odd and b even by using the formulas a = st, b = (s2 - t2)/2, c = (s2 + t2)/2 where s > t > 1 are chosen to be any odd integers with no common factors.

    Note, a primitive Pythagorean triple (PPT for short) is a triple (a,b,c) such that a, b, and c have no common factors (i.e. common to all three simultaneously) and a2 + b2 = c2.

    So suppose X contains some element x. Let F(x) be the full set of factors of x, i.e. F(x) = {d in N : d | x}. If (x,y,z) is a Pythagorean triple, then there exists some d in F(x) such that (d,yd/x,zd/x) is a primitive Pythagorean triple. Proof: set d = x/gcd(x,y,z). So to classify the Pythagorean triples involving x (but x not being the hypoteneuse) it suffices to classify all PPTs involving d (with d not in the hypoteneuse) for each d in F(x).

    Before we go on, note that if (a,b,c) is a PPT then one of {a,b} is even and the other is odd. Both can't be odd because the sum of two odd squares is not a square by modulo 4 arithmetic. Both can't be even because the sum of two even squares is even, so if a Pythagorean triple results, it can't be primitive. Now if d is odd, there are only finitely many pairs (s,t) such that d = st, thus only finitely many PPT involving d. It's also quite easy to see that if d is even, there are only finitely many pairs (s,t) such that d = (s2 - t2)/2, so there are again only finitely many PPT involving d. Thus, for any x, there are only finitely many Pythagorean triples involving x (again, x not hypoteneuse) and so X cannot be infinite.

    Note that this does not prove that |X| cannot be an arbitrarily large finite number, just that X cannot be infinite. The above doesn't do much in terms of telling us how big X can be, it just rules out two extreme cases.

    Now I think one would start by looking at 3 distinct positive elements of X, say x, y, and z. Let x + y = Y, x + z = Z. W.l.o.g., let z > y. Now we have Y - y = Z - z. Just to be clear, x, y, z, Y, and Z are squares; x, y, and z are elements of X; Y and Z may not be in X; X is a set, not a number. Let's also define a, b, c, B, and C to be the square roots of x, y, z, Y, and Z respectively. So

    Y - y = Z - z
    (B - b)(B + b) = (C - c)(C + c)

    Recall y < z, so Y < Z, b < c, and B < C. Of course, we also have that Y > y and Z > z, so C > c and B > b. And a, b, c, B, and C are all naturals. We know that B + b < C + c, and it's not hard to check that B - b > C - c. So we have C + c > B + b > B - b > C - c.

    I don't know if this is leading anywhere. It looks like a pretty hard problem to me, on the other hand there might be a nice, short solution that will make me look stupid ;).
     
  5. Jun 8, 2006 #4
    I think you forgot y+z=P for some square P. In a set {a,b,c} all of {a+b, a+c, b+c, a+b+c} must be squares. Your comments are very insightful. I am absolutely getting NOWHERE with this problem.
     
  6. Jun 8, 2006 #5

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    I didn't forget it, I just haven't used it (yet). I also don't know where to go with this problem, although I haven't thought about it since that last post.
     
  7. Jun 8, 2006 #6

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    I haven't read AKG's post, but another way to show the set must be finite- let n^2 be the least element. For any other element in the set m^2, you can bound m in terms of n (what is the minimum n^2+m^2 can be?). This gives an upper bound for the number of elements in terms of n as well of course.

    This is an unsolved problem, no? Moser's intro number theory book has a more relaxed version, asking if there exists a set of n integers (not required to be squares), where each pairwise sum is a square (no requirement for sums of triples or more). This is known to be true up to n=5, but no higher (this may be out of date though).
     
  8. Jun 9, 2006 #7
    I've relaxed some conditions and created some auxiliary problems, hopefully easier:

    A set X={a,b,...,k} such that any PAIRWISE nonidentical sum produces a square. How big can such sets be?

    A set X={a,b,...,k} such that ANY nonidentical sums produce a square. How big can such sets be?

    A set X={a,b,...,k} of squares such that any pairwise nonidentical sum produces a square. How big can such sets be?

    And finally, the holy grail, a set X={a,b,...,k} of squares such that any nonidentical sums produces a square. How much can such sets be?

    By 'nonidentical' I mean a+a is not allowed. Edit: And one of them is the problem you mentioned, I think.
     
  9. Jun 12, 2006 #8
    There is of course a trivial solution with a set of size 3, which is the Pythagorean "doubles" with the additional element of '0', e.g. {9, 16, 0}.

    I've written a program and determined that for 4 <= n <= 9, there is no set of n elements in which every element is unique and the square of some number less than 16, such that addition with any two or more of the elements of the set always gives another square.

    This is of course by no means an exhaustive test, since there are a lot of arbitrary conditions for the sake of making the computation faster, but it suggests to me that 3 is the largest value that meets the conditions of the problem.

    I wrote said program at midnight, so my results could be wrong. I'll look it over in the morning. Also, IANANT (I Am Not A Number Theorist), just an interested, 16-year-old reader. Cheers.
     
    Last edited: Jun 12, 2006
  10. Jun 13, 2006 #9
    If you use modulus to guide your answer there might be a better method.

    Let the set be {q,r,s,t} i.e four elements in size.

    Consider it modulus 8. A square can be either 0 or 1 or mod 8 but not 2, 3,5,6,or 7. At least one square should be 1 mod 8, otherwise you just each square in the set by 4 to get another set of the same size, but with smaller square numbers. So you let q be of the form 8n+1 and the other three must be either 4 or 0 mod 8 since two squares of the form 8n+1 added to gether cannot add to a square. You divide each of these squares by 4 repeatedly until you have another pathagorean triple with one square of the form 8n+1 again. Let this square be r. Now you three of the 4 numbers as numbers in either the form {8n+1, 4^t*(8m+1), 4^t*8p} or {8n+1, 4^t*(8m+1), and 4^t*(8p+4)} where each of the factors must be a square.
    ???
    Maybe you should consider it mod 7?
     
  11. Jul 6, 2006 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I did some modular math to help me write a fast program for the pairwise problem. It looks like {0, 44^2, 117^2, 240^2} works. I checked 5-tuples with largest member < 500 and didn't find any that worked, but there may be some higher.
     
    Last edited: Jul 7, 2006
  12. Jul 11, 2006 #11
    No Infinity

    It can't be infinite. Call the largest element L^2, and the smallest element s^2.

    [tex] (L + 1)^2 - (L^2) = 2 \times L + 1 . [/tex]

    For sufficiently large L, 2*L + 1 > s^2 always. This is going to be a general constraint, so given the smallest value one can always pick the largest value. It seems to me that max(L) increases without bound, so I'd be inclined to say the set could be of arbitrary size (< inf), but of course I haven't proven that.

    [tex] a^2 + b^2 = c^2. a = ( c - p ). c^2 - ( c - p )^2 = b^2 =

    p^2(2c/p - 1) = b^2. [/tex]

    This has solutions if 2c/p - 1 = n^2 for some integer n.

    [tex] p = \frac{2c}{n^2 + 1}. [/tex]

    The number of solutions will be however many n^2 + 1's c has as a factor. So a general procedure for testing the maximum number of elements:

    1. Pick a smallest element s^2.

    2. L = (s^2 - 1 )/2. L^2 will is the upper bound on the largest element.

    3. C^2 = L^2 + s^2. There will be fewer than C^1/2 elements. For a better estimate, count the number of factors C has which satisfy n^2 + 1.
    C is likely to be irrational, so find [itex] y = \prod_{n=2}^x (n^2 + 1) s.t. y < C. [/itex] This should give the largest set.

    I realize the above isn't very rigorous, and I ignored the possibility of
    (2c/p -1) being a rational square. 2c - p and p would both need to be perfect squares.
     
    Last edited: Jul 11, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Sums of Squares
  1. Sum of squares (Replies: 4)

  2. Sum of squares? (Replies: 1)

  3. Sums of Squares (Replies: 2)

Loading...