Not every finite metric space embeds in an $\mathbb{R}^{k}$

Question

This problem is present in "Supplements to the Exercises in Chapter 1-7 of Walter Rudin's Principles of Mathematical analysis" by Prof. George M. Bergman, which states as follows,

Let $X$ be a $4$-element set $\{w, x, y, z\}$, and let $d$ be the metric on $X$ under which the distance from $w$ to each of the other points is $1$, and the distance between any two of those points is $2$.

1. Show that no function $f$ of $X$ into a space $\mathbb{R}^{k}$ is distance-preserving, i.e., satisfies $|f(p) - f(q)| = d(p, q)$ for all $p, q \in X$.
2. The above example has the property that every $3$-point subset of $X$ can be embedded (mapped by a distance-preserving map) into space $\mathbb{R}^{k}$ for some $k$, but the whole $4$-point space cannot be so embedded for any $k$. Can you find a $5$-point metric space, every $4$-point subset of which can be so embedded but such that the whole $5$-point space cannot?

I searched on the internet about this topic and found the Cayley-Menger determinant may be helpful to part 2. However, here is a concrete $5$-point case and I was wondering if there are some intuitive counterexamples? And I also have no clue about part 1, can anyone give me some hints on it. Thanks in advance.

Answer 1

1. Suppose that $f$ exists. Without loss of generality, we may set $f(w) = 0$. Thus, $f(x)$, $f(y)$ and $f(z)$ must be the vertices of an equilateral triangle inscribed on the unit sphere, whose sides have length $2$. Alas, the largest equilateral triangles that you can inscribe on a unit sphere have sides of length $\sqrt 3$.

2. In general, let $X = \{ w, x_1, \dots, x_n \}$. Turn $X$ into a metric space by setting $d(w, x_i) = 1$ and $d(x_i, x_j) = \lambda$, where $\lambda$ is just large enough that you can inscribe a regular simplex with $n-1$ vertices on the unit sphere, but not a regular simplex with $n$ vertices.

Answer 2

It is easy to prove that every $3$-point of $\{w, x, y, z\}$ can be embedded into $\mathbb{R}^{k}$ for $k=3$ by an equilateral triangle with vertex $x,y,z$ or straight lines $\{w,x,z\}$, $\{w,x,y\}$ and $\{w,y,z\}$.

A counterexample of $5$-point case is as follows, let $\{v^{\prime},w^{\prime},x^{\prime},y^{\prime},z^{\prime}\}$ be the image of $\{v, w, x, y, z\}$ under $f$. Assume, without loss of generality, $v^{\prime}$ is the origin, and we follow the same idea of part 1, and construct the $4$-point set $\{w^{\prime},x^{\prime},y^{\prime},z^{\prime}\}$ as an equilateral figure with length of side $1$ in $\mathbb{R}^{k}$, e.g., a regular $4$-simplex in $\mathbb{R}^{3}$. Let the distance between $v^{\prime}$ and other points are all equal to $r$. By the Jung's theorem\index{Jung's theorem}, the upper bound of radius of the minimum ball enclosing these $4$ points is $\sqrt{\frac{k}{2(k+1)}}$ and this bound is attained by the regular $k$-simplex in $\mathbb{R}^{k}$. Suppose the $5$-point set is Euclidean, then we can always find a regular $k$-simplex in $\mathbb{R}^{k}$ with vertices $\{w^{\prime},x^{\prime},y^{\prime},z^{\prime}\}$ and the center at origin $v^{\prime}$. Then the regular $k$-simplex can be enclosed by a closed ball $\overline{B}(v^{\prime},r)$. Since for $3 \leq k < +\infty$, we have \begin{equation*} \sqrt{\frac{3}{8}} \leq r = \sqrt{\frac{k}{2(k+1)}} <\sqrt{\frac{1}{2}} \end{equation*} by letting $\sqrt{\frac{1}{3}} = r < \sqrt{\frac{3}{8}}$, such $v^{\prime}$ does not exist. Note that every $4$-points set is Euclidean since $\{w^{\prime},x^{\prime},y^{\prime},z^{\prime}\}$ can be a tetrahedron and $\{v^{\prime},x^{\prime},y^{\prime},z^{\prime}\}$ can be a equilateral triangle with center at $v^{\prime}$.