If every five point subset of a metric space can be isometrically embedded in the plane then is it possible for the metric space also?

Let $X$ be a metric space with at least $5$ points such that any five point subset of $X$ can be isometrically embedded in $\mathbb R^2$ , then is it true that $X$ can also be isometrically embedded in $\mathbb R^2$ ?

Solution 1:

"Embeddings" below are isometric; $(X,d)$ is a metric space.

In fact $X$ can be embedded in $\Bbb R^n$ if and only if every subset of $X$ containing no more than $n+3$ points can be embedded in $\Bbb R^n$. Thanks to @achillehui for noticing that the first version of this post was wrong, for stating the correct version of the result, and for telling us it's due to Menger (Untersuchungen über allgemeine Metrik, Mathematische Annalen, 100:75–163, 192) way back in 1928. Edit I've finally seen how to give an example showing that $n+3$ is best possible. See the bonus section at the bottom.

The proof is by induction on $n$. You may notice that the structure of the proof for $n=1$ is identical to the structure of the induction step. In fact the case $n=1$ could be derived by induction from the case $n=0$. That might involve some head-scratching; it seems best just to give the case $n=1$ separately.

In the case $n=1$ various plausible but not quite trivial lemmas can be replaced by the following triviality: If $X$ can be embedded in $\Bbb R$, $a,b$ are two distinct points of $X$, $x,y$ are two distinct points of $\Bbb R$, and $|x-y|=d(a,b)$, then there is exactly one embedding $f:X\to\Bbb R$ with $f(a)=x$ and $f(b)=y$. (For existence, replace the given embedding $g$ by $\pm g+c$. For uniqueness, note that if $|f(a)-t|=|f(a)-s|$ and $t\ne s$ then $f(a)=(s+t)/2$, and similarly for $f(b)$.)

Theorem 1. $X$ can be embedded in $\Bbb R$ if and only if any four points of $X$ can be embedded in $\Bbb R$.

Proof: For the less trivial direction: We may assume $X$ has more than one point. Choose $p,q\in X$ and define $f(p)=0$, $f(q)=d(p,q)$. Suppose $r\in X$, $r\ne p,q$. The hypothesis and the comment above (with $\{p,q,r\}$ in place of $X$) shows that there is a unique embedding $g$ of $p,q,r$ with $g(p)=f(p)$ and $g(q)=f(q)$. Define $f(r)=g(r)$.

We have defined $f:X\to\Bbb R$ such that $|f(r)-f(p)|=d(r,p)$ and $|f(r)-f(q)|=d(r,q)$ for every $r$. We are done if we can show that $|f(r)-f(s)|=d(r,s)$ for $r,s\notin\{p,q\}$. As above there is a unique embedding $g$ of $p,q,r,s$ in $\Bbb R$ with $g(p)=f(p)$ and $g(q)=f(q)$. Uniqeness of the embedding of $p,q,r$ shows that $g(r)=f(r)$. Similarly $g(s)=f(s)$, so $|f(r)-f(s)|=|g(r)-g(s)|=d(r,s)$. QED.

The case $n>1$ requires a few preliminaries.

Lemma 0. Suppose $x_1,\dots,x_N,y_1,\dots,y_N\in\Bbb R^n$ and $|x_j-x_k|=|y_j-y_k|$ for all $j,k$. Then there is an isometry $f:\Bbb R^n\to\Bbb R^n$ with $f(x_j)=y_j$.

Proof: Let $v_j=x_j-x_0$, $w_j=y_j-y_0$. We have $|v_j|=|w_j|$ and $|v_j-v_k|=|w_j-w_k|$. The parallelogram law shows that $|v_j+v_k|=|w_j+w_k|$, so that $v_j\cdot v_k=w_j\cdot w_k$ by polarization. Hence $$\left|\sum t_jv_j\right|=\left|\sum t_jw_j\right|.$$In particular $\sum t_jv_j=0$ if and only if $\sum t_jw_j=0$, so that there exists a linear map $T:span(v_j)\to span(w_j)$ with $$T\left(\sum t_jv_j\right)=\sum t_jw_j.$$Now $T$ is evidently an isometry; extend $T$ to an orthogonal map from $\Bbb R^n$ to itself by mapping the orthogonal complement of $span(v_j)$ to the orthogonal complement of $span(w_j)$. QED.

Definition We say $F\subset\Bbb R^n$ is coplanar if there exist $c\in\Bbb R$ and $v\in\Bbb R^n$ with $v\ne0$ such that $x\cdot v=c$ for every $x\in F$.

Lemma 1. Suppose $x_1,\dots,x_N\in\Bbb R^{n}$ and $\{x_1,\dots,x_N\}$ are not coplanar. If $|x_j-y|=|x_j-z|$ for all $j$ then $y=z$.

Proof: Saying $|x_j-y|=|x_j-z|$ is the same as $(x_j-\frac{y+z}{2})\cdot(z-y)=0$; if $y\ne z$ this says that $x_1,\dots,x_N$ are coplanar. QED.

Lemma 2. Suppose $F\subset\Bbb R^n$ is not coplanar. Then $F$ has a non-coplanar subset containing exactly $n+1$ points.

Proof: Fix $x_0\in F$. The set $\{x-x_0:x\in F\}$ spans $\Bbb R^n$, so it must contain a basis. QED.

Theorem 2. $X$ can be embedded in $\Bbb R^n$ if and only if every subset of $X$ containing no more than $n+3$ points can be embedded in $\Bbb R^n$.

Proof: The proof is by induction on $n$. The case $n=1$ is exactly Theorem 1 above. Suppose then that the theorem holds for embeddings into $\Bbb R^n$, and suppose that every subset of $X$ containing no more than $n+4$ points can be embedded in $\Bbb R^{n+1}$.

We want to show that $X$ can be embedded in $\Bbb R^{n+1}$, so we may assume that $X$ cannot be embedded in $\Bbb R^n$. By induction there exists $S \subset X$, with $|S|\le n+3$, such that $S$ cannot be embedded in $\Bbb R^n$. By hypothesis there exists an embedding $f:S\to\Bbb R^{n+1}$. Since $S$ cannot be embedded in $\Bbb R^n$, the image $f(S)$ cannot be coplanar. Applying Lemma 2 we see this: There exist $p_1,\dots,p_{n+2}\in X$ and an embedding $f$ of $p_1,\dots,p_{n+2}$ in $\Bbb R^{n+1}$ such that if we set $x_j=f(p_j)$ then $x_1,\dots,x_{n+2}$ are not coplanar.

Suppose that $q\ne p_1,\dots,p_{n+2}$. The hypothesis and Lemma 1 show that there is exactly one $x\in\Bbb R^{n+1}$ with $|x-x_j|=d(q,p_j)$ for all $j$; define $f(q)=x$.

We have defined $f:X\to\Bbb R^{n+1}$. To show that $f$ is an isometry it is enough to show that if $r,q\ne p_1,\dots p_{n+2}$ then $|f(r)-f(q)|=d(r,q)$. The hypothesis shows that there is an embedding $g:\{r,q,p_1,\dots,p_{n+2}\}\to\Bbb R^{n+1}$, and now Lemma 0 shows that there exists such a $g$ with $g(p_j)=f(p_j)$. Now Lemma 1 shows that $g(r)=f(r)$ and $g(q)=f(q)$, so that $|f(r)-f(q)|=|g(r)-g(q)|=d(r,q)$. QED

Bonus In fact $n+3$ is best possible.

In the first version of this answer I "proved" Theorem 2 with $2n+1$ in place of $n+3$. The induction was ok, more or less the same as above; the problem was that I'd "proved", largely on the basis of wishful thinking, that Theorem 1 was true with $3$ in place of $4$. Thanks again to @achillehui for pointing out that was wrong.

I think the simplest way to show that $4$ is best possible for $n=1$ is this: Let $X$ consist of the four points $(0,0),(0,1),(1,0),(1,1)$, with the $\ell^1$ metric (that is, $d(x,y)=|x_1-y_1|+|x_2-y_2|$). It's easy to see that any $3$-point subset of $X$ embeds in $\Bbb R$, and that $X$ itself does not.

That example actually generalizes to $n\ge1$, but when it's presented that way it's not so clear how. I'm going to give a fairly careful description of an example showing that $5$ is best possible for $n=2$. I claim that it is clear that the example below generalizes to show that $n+3$ is best possible for $n\ge2$, and I leave as an unimportant exercise to show how the example for $n=1$ above is actually the same construction as what I give for $n=2$, if you look at it right.

Let $a_1,a_2,a_3$ be the vertices of an equilateral triangle in the plane. Let $c$ be the center of that triangle. Let $X=\{a_1,a_2,a_3,c,c'\}$, where $c'$ is something else. Define a metric on $X$: First, define the distance between any two points of $\{a_1,a_2,a_3,c\}$ to be the euclidean distance as points in the plane. Define $$d(c',a_j)=d(c,a_j)$$and set $$d(c,c')=2h,$$where $h$ is the perpendicular distance from $c$ to one of the sides of our triangle. No need to scratch your head over the triangle inequality, that will follow when we show that any $4$-point subset of $X$ can be embedded in the plane.

If we remove $c'$ from $X$ what remains is a subset of the plane. If we remove $c$ we can set $f(c')=c$ to embed the remaining four points.

Suppose we remove $a_3$. Map each of the points $a_1,a_2,c$ to itself. Map $c'$ to the point on the other side of the segment $[a_1,a_2]$, so we get a rhombus with diagonals $[a_1,a_2]$ and $[c,f(c')]$.

So any four points of $X$ can be embedded in the plane. But $X$ itself does not embed in the plane; if this is not clear it can be proved from Lemma 1 and Lemma 0 using arguments as above.

So $5$ is best possible for $n=2$. And I assert again that the same construction shows that $n+3$ is best possible for $n\ge2$; if anyone wants to write a formal description go for it. (For $n=3$ we start with the vertices and center of a regular tetrahedron and add a sort of duplicate of the center point...)