Points within a Sphere

[jay_shark]

Show that if there are n points contained in a sphere of radius 1 , then the sum of the squares of the n(n-1)/2 distances between them is at most n^2 .

All solutions are welcomed .

[jay_shark]

My conjecture is that the points must be diametrically opposite to each other if we cut the sphere in half for n even . I'm not too sure what happens when n is odd .

[gumpzilla]

This is an interesting problem. I've been hacking at it for a few minutes but no big insights yet. I'll let you know if I come up with anything.

EDIT: Perhaps the most straightforward approach I see at the moment is as follows. Let's solve the problem for 3 points and see if the strategy becomes apparent. To simplify life, let's further reasonably assume that the limiting cases in which we're interested in will have all of the points on the boundary of the sphere, figure out how that works and then later on prove that it must be so. (Intuitively it seems true.) Then what I'm inclined to do is to maximize the sum of all of the distances, using Lagrange multipliers if necessary to enforce the constraint, and then place a bound on how big it can get.

[gumpzilla]

Okay, some progress. Notationally this is going to be a bitch. But it would appear your basic intuition is right.

So, what does the sum of the squares of the distances look like? It will look like a sum of (x_i - x_j)^2 for all i != j pairings, and all 3 coordinates x, y, z. Each point appears in (n-1) of these terms. Unpacking them all, and summing over different coordinates, we'll get (n-1) (x_i^2 + y_i^2 + z_i^2) for all i. Assuming these points are on the surface of the sphere, each of these sums contributes 1, and there are n of them. So we have a leading n(n-1) behavior. Already pretty close to n^2!

The rest of the sum will be -2 * (x_i*x_j + y_i*y_j + z_i*z_j), summed over all pairs such that i != j. This is the thing we need to minimize, and we want to show that it is less than n to get your result. Throwing in a term a_i * (x_i^2 + y_i^2 + z_i^2 - 1 ) to use Lagrange multipliers and then finding where the derivative is zero, you find that the extrema occur when x_i = (1 / a_i) * sum over x_j s.t. j != i. In other words, it's proportional to the mean of all of the other coordinates. It seems to me (though I haven't formally proved this yet) that the only way that you can get this is to distribute the points as vertices of a regular n-gon about one equatorial plane of the sphere. Notice that in this case, your conjecture basically holds (although this is a more complete specification.)

So, what you now need to prove is that for points on a regular n-gon, that last sum is less than n. I think the property that for every x_i, there is some j such that x_j = - x_i if n is even will let you do move forward. If x is odd, then instead of one diametrically opposed point, there will be two symmetrically located points that should average together.

EDIT: The other thing that occurs to me is that once you've gotten this far, the sum of pairwise products might be attackable by some kind of geometric mean < arithmetic mean argument to produce something that does the rest of it for you. In fact, I'm really liking that idea. Back in one sec.

EDIT AGAIN: Okay, I don't think that works so well, because the bound that gives you is that the sum of the pairwise products must be less than (n-1)n again. This does tell you that you can't do worse than zero as the sum of all of the distances, which is a nice thing to know, but it's insufficient for proving your result. So I think you need the machinery above.

[gumpzilla]

Okay, I think I've got it.

Forget the n-gon [censored]. What is really important is the constraint that at the extremes, the sum of all of, say, the x-coordinates is zero. Then, what this allows us to do is replace the partial sum

x_1*x_2 + x_1*x_3 + . . . + x_1*x_n = x_1 * (x_2 + . . . x_ n) = x_1 * (-x_1).

I think the factor of 2 in front of this sum allows you to avoid double counting, so you can then rack up n of these sums across the 3 coordinates and there you go.

I realize that my presentation is disjointed and not 100% rigorous but at this point I'm pretty convinced the argument is sound.

[jay_shark]

I think i'm getting close but i'm still trying to work out the algebra . It's always better to work with small n to give you some insight .

Also , this must be true for a circle as well so you may be able to gain additional information there .

[jay_shark]

well the sphere is of the form x^2+y^2+z^2=1

Take two points (x1,y1,z1); (x2,y2,z2)

Their distance is (x1-x2)^2+(y1-y2)^2+(z1-z2)^2= (x1^2+y1^2+z1^2)*2 - 2(x1x2 +y1y2+z1z2) =2-2(x1x2+y1y2+z1z2)=A

The sum of all the distances of the squares for any of the nC2 pairs is A*(nC2)=n(n-1) -2EE(xixj+yiyj+zizj)


I'm almost there .

[gumpzilla]

What was this problem for? I really enjoyed it quite a bit.

[jay_shark]

-2EE(xixj+yiyj+zizj)=-2[(x1+...xn)^2+(y1+...yn)^2+(z1+...zn)^2 - (x1^2+...xn^2)-(y1^2+...yn^2) - (z1^2+...yn^2)]

I have to clean this up a bit more .

[jay_shark]

This problem wasn't for anything in particular , I was just very interested in solving it for personal satisfaction :P