Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose one has $m$ points in $\mathbb{R}^n$ with the property that the distance between any two of them is some fixed constant $d$. Is it true that there is a sphere (living in $\mathbb{R}^n$) containing all of them?

Certainly, there is a sphere containing $m-1$ of them: choose any one of the $m$ points and consider the sphere of radius $d$ centered at that point. In fact, for any point I choose to be the center, such a sphere will contain the other $m-1$ points. Thus, it seems likely to me that there is some single sphere containing all of them, but I fail to see how to show this rigorously.

share|improve this question
    
Should that be "Suppose one has $m$ points in $\mathbb{R}^{n+1}$? An $n$-dimensional sphere does not fit in $\mathbb{R}^{n}$. –  Shaun Ault Aug 31 '11 at 0:19
1  
Also, you may realize that the set of $m$ points must define the vertices of a regular $(m-1)$-simplex, which can always be inscribed in an $(m-1)$-disk, the boundary of which is an $(m-2)$-sphere. Moreover, this imposes a restriction on the size of $m$ (given a fixed $n$). –  Shaun Ault Aug 31 '11 at 0:22
    
@Shaun I intend for the sphere to live in $\mathbb{R}^n$, so my use of $n$-sphere is inappropriate. I will edit to reflect this. –  Austin Mohr Aug 31 '11 at 0:25

4 Answers 4

up vote 5 down vote accepted

If you strengthen the statement a bit you should be able to prove it by induction on $m$. Something like:

Assume that $m\ge 2$ equidistant points in $\mathbb R^n$ are given. Then (a) the $m$ points span an $(m-1)$-dimensional hyperplane, (b) the points lie on exactly one sphere in the hyperplane they span, and (c) the radius of this sphere is less than $d$.

For the induction step, remove one of the given points and apply the induction hypothesis to the remaining $m-1$ ones. Then project the remaining point orthogonally on the hyperplane spanned by the $m-1$ points and draw the necessary conclusions.

share|improve this answer
    
+1 And as a byproduct you also get the inequality $m\le n+1$. –  Jyrki Lahtonen Aug 31 '11 at 7:19

My first thought on reading this question was, "Take the centroid of the $m$ points. It's obviously equidistant from all of them." Hang on. How am I going to prove that? "Come on! How could it not be?! All the points are indistinguishable... in some sense... and taking the mean to get the centroid doesn't distinguish between them either... in some sense... so..." Wait, what does that even mean?

Here is the result of my digging in my heels and attempting to formalize that initial impulse, rather than doing the reasonable thing of looking for a simple and sensible proof via induction like Henning's and Alex's nice answers.

The $m$ given points $\{v_1, \ldots, v_m\}$ are "indistinguishable" in the sense that any two of them, $v_i$ and $v_j$, can be exchanged by an isometry of $\mathbb R^n$ that leaves the rest of the points unchanged.¹

The centroid does not "distinguish" between points in the sense that any permutation of the given points still has the same centroid.

It turns out that we also need the fact that the centroid is preserved under isometries.²

Now, consider the isometry that swaps $v_i$ and $v_j$. Since the new points are a permutation of the original ones, they have the same centroid, say $v_0$. The isometry maps $v_i$ to $v_j$ and $v_0$ to $v_0$. Since it preserves distances, the distance between $v_i$ and $v_0$ is equal to the distance between $v_j$ and $v_0$. The same argument applies to all pairs of points, and we are done.


¹This isometry is simply reflection across the hyperplane that orthogonally bisects the line segment joining $v_i$ and $v_j$. All other points, being equidistant from $v_i$ and $v_j$, lie on this hyperplane and are unchanged by the reflection.

²That is, an isometry maps centroids to centroids. While this statement is eminently plausible, the only direct proof I can think of is that the centroid may be defined as the point minimizing the sum of squared distances to the $m$ given points.

share|improve this answer
    
+1 Nice use of the symmetry of the situation. –  Henning Makholm Aug 31 '11 at 14:23

The points themselves form the vertices of a regular simplex - the higher dimensional version of a tetrahedron. If you average the $m$ points, you obtain the centroid of the simplex. You can use induction to show that the centroid of a regular simplex with $m$ vertices is equidistant to each of the vertices.

share|improve this answer
    
Although it looks to me like the induction will be along the lines of Henning Makholm's answer. –  alex.jordan Aug 31 '11 at 1:32

In addition to the geometric proofs, here is a linear algebraic proof.

Claim: Given a collection of points $\{v_1, \ldots, v_m\}$ such that $\|v_i - v_j\| = 1$ if $i\neq j$, then letting $v_0 = \frac{1}{m} \sum v_i$ the mean of all the points, $\|v_i - v_0\| = \|v_j - v_0\|$ for any $i,j$.

Proof: by translating all the points, we can assume without loss of generality that $v_0 = 0$. This implies that $\sum v_i = 0$. Consider

$$ \langle v_j, \sum_{i = 1}^m v_i\rangle = \|v_j\|^2 + \sum_{i \neq j} \langle v_i, v_j\rangle = 0 $$

Now, using that

$$ \|v_i - v_j\|^2 = \|v_i\|^2 + \|v_j\|^2 - 2 \langle v_i, v_j\rangle = 1$$

we have that

$$ \|v_j\|^2 + \frac12 \sum_{i\neq j}( \|v_i\|^2 + \|v_j\|^2 - 1) = 0 $$

which we can expand to

$$ \frac{m}{2} \|v_j\|^2 + \frac12 \sum_{i = 1}^m \|v_i\|^2 = \frac{m-1}{2} $$

Observe now that $\sum_{i = 1}^m \|v_i\|^2 = C$ is independent of $j$, you have that

$$ \|v_j\|^2 = \frac{m-1 - C}{m} $$

is a constant independent of $j$. So all the points must lie on the sphere of radius $\sqrt{\frac{m-1-C}{m}}$ about the origin.

share|improve this answer
    
As an aside, you can even compute that $C = m-1-C$, so that $\|v_j\| = \sqrt{(m-1)/2m}$. –  Willie Wong Aug 31 '11 at 1:46

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.