1
$\begingroup$

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$?

$\endgroup$
1

2 Answers 2

4
$\begingroup$
  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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – msm
    Jan 27, 2018 at 2:54

Not the answer you're looking for? Browse other questions tagged .