19
$\begingroup$

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

$\endgroup$
6
  • 3
    $\begingroup$ I know nothing about this, could you explain a little why you might expect this to be true? $\endgroup$ – Jose27 Jun 17 '16 at 15:31
  • $\begingroup$ @David C. Ulrich : You had written a long and involved answer , I thought of reading it today , but I see you have deleted it , was there some serious error in it ? $\endgroup$ – user228169 Jun 19 '16 at 8:47
  • $\begingroup$ @Jose27 : Well , the five in the question I just arbitrarily chose , I know that the answer to the question is in negative if we wanted the real line instead of the plane ; but in plane I could get no where with it , so I asked $\endgroup$ – user228169 Jun 19 '16 at 8:48
  • $\begingroup$ The answer was simply wrong, as @achillehui pointed out. Yesterday I didn't see how to salvage it, this morning I believe I see how to fix it. Having screwed up once I'm going to check things carefully before posting the fixed version - stay tuned. (I "proved" something about embedding in $\Bbb R^n$, by induction. My version of the case $n=1$ was wrong, but having been given the correct version for $n=1$ I believe the induction is ok, although there's one new lemma needed.) $\endgroup$ – David C. Ullrich Jun 19 '16 at 13:37
  • $\begingroup$ Btw yes, $5$ is the right number for $\Bbb R^2$. $\endgroup$ – David C. Ullrich Jun 19 '16 at 14:01
23
$\begingroup$

"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...)

$\endgroup$
5
  • $\begingroup$ @achillehui Finally saw how to show $n+3$ is best possible; thought you might be interested. Thanks again... $\endgroup$ – David C. Ullrich Jun 21 '16 at 17:44
  • $\begingroup$ nice, it is good to see a proof that $n+3$ is best possible. $\endgroup$ – achille hui Jun 22 '16 at 1:01
  • $\begingroup$ @DavidC.Ullrich : Sorry to bother you after such a long time but I cannot understand the preliminary remarks before Theorem 1 , about the existence-uniqueness of $f$ ; could you please elaborate how do you construct such an $f$ and why it is unique ? $\endgroup$ – user228169 Jun 28 '16 at 14:33
  • $\begingroup$ @user228169 I can try to be a little more explicit, but I fear much of what I write is going to be just repeating what I wrote. If the following does not do it for you try to be more explicit about exactly what steps you don't follow. In that paragraph we are given an embedding $g:X\to\Bbb R$. We are given $a,b\in X$ and $x,y\in\Bbb R$ with $|x-y|=d((a,b)$. Now since $|x-y|=|g(a)-g(b)|$ it's possible to choose $\pm$ and $c$ so that if we set $f=\pm g+c$ then $f(a)=\pm g(a)+c=x$ and $f(b)=\pm g(b)+c=y$. (Consider two cases, depending on whether $y-x$ and $g(b)-g(a)$ have the same sign.) [...] $\endgroup$ – David C. Ullrich Jun 28 '16 at 14:53
  • $\begingroup$ @user228169 That gives existence of an embedding $f$ with thhe stated property. For uniqueness: Suppose $f$ and $f'$ are embeddings with the stated property. Suppose $c\in X$. Then $|f(c)-x|=|f'(c)-x|$ and $|f(c)-y|=|f'(c)-y|$. if $f(c)\ne f'(c)$ this would imply that $x=(f(c)-f'(c))/2$ and $y=(f(c)-f'(c))/2$, so $x=y$, contradiction. $\endgroup$ – David C. Ullrich Jun 28 '16 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy