A Union of Euclidean Metric Spaces is Euclidean

Abstract

A Union of Euclidean Metric Spaces is Euclidean, Discrete Analysis 2016:14, 15pp. A major theme in metric geometry concerns conditions under which it is possible to embed one metric space into another with small distortion. More precisely, if $M_1$ and $M_2$ are metric spaces, one would like to find a function $f:M_1\to M_2$ and constants $c$ and $C$ such that for every $x,y\in M_1$ the inequalities $cd(x,y)\leq d(f(x),f(y))\leq Cd(x,y)$ hold, with the ratio $C/c$ being as small as possible. For example, the famous [Johnson-Lindenstrauss lemma](https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma) states that if $a_1,\dots,a_n$ are points in a Euclidean space and $\epsilon>0$, then there are points $b_1,\dots,b_n$ that live in a Euclidean space of dimension at most $8\log n/\epsilon^2$ such that $$(1-\epsilon)\|a_i-a_j\|^2\leq\|b_i-b_j\|^2\leq(1+\epsilon)^2\|a_i-a_j\|^2$$ for every $i,j$. That is, a finite subset $A$ of a Euclidean space can be embedded with small distortion into a Euclidean space with dimension logarithmic in the size of $A$. A rather basic question one can ask about embeddings of small distortion is the following. Let $A$ and $B$ be two subspaces of a metric space $X$ and suppose that each can be embedded into Euclidean space with bounded distortion. Can their union $A\cup B$ also be embedded with bounded distortion? One might think that this question would have either a simple proof or a simple counterexample, but surprisingly it was a question asked by Assaf Naor that had been open for some time. It is solved in this paper. If $Z$ is a metric space, write $D_Z$ for the smallest distortion with which one can embed $Z$ into Euclidean space -- that is, the smallest possible ratio $C/c$ in the discussion above. The main result of the paper is that $D_{A\cup B}\leq 7D_AD_B+2(D_A+D_B)$. In particular, if $D_A$ and $D_B$ are finite, then so is $D_{A\cup B}$. This result leaves open several further interesting questions, mentioned at the end of the paper. In particular, the ingenious proof uses a specifically Hilbertian tool, the [Kirszbraun extension theorem](https://en.wikipedia.org/wiki/Kirszbraun_theorem), so it does not solve the problem for embeddings into other spaces, such as $\ell_1$. It would also be interesting to know what the best possible dependence is of $D_{A\cup B}$ on $D_A$ and $D_B$. It is likely that this paper will stimulate many further interesting developments in metric geometry.