Proof maximum number of equidistant points for a given dimension [duplicate]

The question is quite straight forward, on $\mathbb{R}^2$ the maximum number of equidistant distinct points that can be layed (using the euclidean distance) is 3, forming thus an equilateral triangle. On $\mathbb{R}^3$ the maximum number of points is 4, forming thus a tetrahedon. My question is quite simple, is the maximum number of points that can be layed in $\mathbb{R}^n$ equal to $n+1$?

• – dxiv
Jan 27, 2018 at 2:38

1. Yes, you always place $$n+1$$ points equidistantly in $$\mathbb{R}^n$$—but you can't place $$n+2$$.
2. We can prove this with a few arguments. This proof uses the concept of linear independence.
3. Equilateral triangles are equiangular

We need a more quantified version of this statement, namely: If three distinct points $$v_a, v_b, v_c$$ are mutually separated by the same distance $$d$$, then the law of cosines says that

\begin{align*} ||v_b-v_c||^2 &= ||(v_a-v_c)-(v_a-v_b)||^2 \\ &= ||v_a-v_c||^2 +||v_a-v_b||^2 - 2(v_a-v_c)\cdot (v_a-v_b)\\ d^2 &= d^2 + d^2 - 2(v_a-v_c)\cdot (v_a-v_b)\\ d^2 &= 2(v_a-v_c)\cdot (v_a-v_b)\\ \frac{d^2}{2} &= (v_a-v_c)\cdot (v_a-v_b)\\ \end{align*}

1. If $$m$$ points are all equidistant, then the differences between one point and the rest are all linearly-independent vectors.

(Formally: if $$\{v_1,\ldots,v_m\}$$ are all equidistant, and we pick any one of those points $$v_i$$, then the set of differences $$V_i\equiv \{(v_i-v_j) : j \neq i\}$$ consists of $$m-1$$ linearly-independent vectors.)

I'll prove this below. For now, note that it implies the following statement.

2. You can't have more than $$n+1$$ equidistant points in $$\mathbb{R}^n$$

After all, $$\mathbb{R}^n$$ can contain at most $$n$$ linearly-independent vectors. But we've just shown that if you have $$m$$ equidistant points, their differences consistute $$m-1$$ linearly-independent vectors. Hence $$m-1 < n$$, or $$m < n+1$$.

3. You can have exactly n+1 equidistant points in $$\mathbb{R}^n$$.

The statement is true for $$n=1$$, as any pair of points is "equidistant" in a trivial way. To prove the inductive case, suppose $$n+1$$ points in $$\mathbb{R}^n$$ are linearly-independent and let $$c$$ be their center. Because the points are equidistant from each other, they're equidistant from their centroid.

We can embed $$\mathbb{R}^n$$ into $$\mathbb{R}^{n+1}$$ by adding an extra zero: $$f:\langle x_1,\ldots, x_n\rangle \mapsto \langle x_1,\ldots, x_n, 0\rangle.$$

This embedding is special: it preserves distances. So the $$y_i \equiv f(x_i)$$ are all separated by the same amount $$d$$, and are equidistant from $$f(c)$$.

This embedding also comes with a new direction. Let $$\vec{w}=\langle 0,0,0,\ldots,0,1\rangle$$ be a unit vector in the new direction. Then $$\vec{w}$$ is perpendicular to every member $$y_i$$. I claim (and it is straightforward to show) that the line $$q(t) = f(c) + t \cdot \vec{w}$$ consists of points that are equidistant from every $$y_i$$.

In fact, if $$C$$ is the distance of the points from their centroid, then all the points are at a distance of $$C^2 + t^2$$ from the point $$q(t)$$. By choosing an appropriate value of $$t \equiv \sqrt{d^2 - C^2}$$, we find a point $$q(t)$$ whose distance from each of the $$y_i$$ is the same as the distance between the $$y_i$$. Hence we have found $$n+2$$ points in $$\mathbb{R}^{n+1}$$ which are equidistant.

Proof of (3).

The statement holds in a trivial way for $$m=1$$— we have only one point— and for $$m=2$$, where we have only one difference vector. As long as the two chosen points are distinct, this difference is nonzero and therefore comprises a linearly-independent set.

For $$m\geq 3$$, suppose we have $$\{v_1,\ldots, v_{m}\}$$ equidistant points. Pick any one of them, say $$v_a$$, and assume we have coefficients $$\alpha_i$$ such that:

$$0 = \sum_{j \neq a} \alpha_j (v_a - v_j)$$

Pick any $$v_k \neq v_a$$ and dot both sides by $$(v_a-v_k)$$, pulling out the $$(v_a-v_k)$$ term as a special case: $$0 = \alpha_k(v_a - v_k)\cdot(v_a-v_k) + \sum_{j \neq a,k} \alpha_j (v_a - v_j)\cdot (v_a-v_k)$$

But these points are all mutually separated by distance $$d$$. Hence $$||v_a-v_k||^2 = d^2$$, and $$(v_a-v_j)\cdot(v_a-v_k) = d^2/2$$ for $$j\neq a,k$$, as we showed before. We have:

$$0 = \alpha_k d^2 + \frac{1}{2}\sum_{j \neq a,k} \alpha_j d^2$$ $$0 = 2\alpha_k + \sum_{j\neq a,k} \alpha_j$$ $$0 = \alpha_k + \sum_{j\neq a} \alpha_j$$

Note that this result holds for any $$k\neq a$$; hence we can sum this result over all values of $$k\neq a$$. If we do, we get $$0 = \sum_{k\neq a} \left( \alpha_k + \sum_j \alpha_j\right) = (m-1) \sum_{j \neq a} \alpha_j$$. Hence the coefficients sum to zero.

And because this statement holds for any $$k\neq a$$, we have that

$$\alpha_k + \sum_{j\neq a} \alpha_j = \alpha_{k^\prime} + \sum_{j\neq a} \alpha_j$$ or just $$\alpha_k = \alpha_{k^\prime}$$. Hence all coefficients are equal. We therefore conclude that all coefficients are zero, showing that the $$(v_a - v_j)$$ are linearly-independent.

I think the answer is yes. I have a sketchy idea of how maybe a proof could go. Suppose I have $d$ points in $\mathbb{R}^n$, and take a collection of all but one of them. Let the point left out be called $p_0$. These points are all embedded into $\mathbb{R}^n$, so take the orthogonal complement of $p_0$, and project all the other point into it. This projection map is $f(v) = v - \frac{1}{|p_0|^2}p \cdot v$

If $a,b$ are two other points in the collection, we should have:

$f(a) - f(b) =(a-b) - \frac{1}{|p_0|^2}(p \cdot a - p \cdot b)$

Now, I think that it could be true that $p \cdot a = p \cdot b$, by something to do with the equidistance. So, the projected points should give a collection of points in $n-1$ dimensions that are all equidistant.

Thus, $d-1 \leq n$, and so $d \leq n+1$.

• I do not think this proof works, but I think it has the right ideas. This is very sketchy, and I have not worked it out at all. But, the image I have in my head with a tetrahedron makes me think that something LIKE this proof has to work.
– msm
Jan 27, 2018 at 2:54