A Union of Euclidean Metric Spaces is Euclidean

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