When is Euclidean distortion finitely determined?

Question

The Euclidean distortion of a metric space $X$, denoted $c_2(X)$, is the infimum of $c$ for which there exists a map $f\colon X\to\ell^2$ such that

$$d_X(x,y) \leq \|f(x)-f(y)\|_{\ell^2} \leq c\cdot d_X(x,y).$$

In the introduction of their paper "Nonembeddability theorems via Fourier analysis", Khot and Naor mention the following in passing:

The Euclidean distortion of a metric space $X$ is relatively well understood: it is enough to understand the distortion of finite subsets of $X$, and for finite metrics there is a simple semidefinite program which computes their Euclidean distortion [39].

Here, reference [39] is Linial, London, and Rabinovich's "The geometry of graphs and some of its algorithmic applications", which introduced the semidefinite program mentioned above. I'm interested in the first part of Khot and Naor's claim, which appears to suggest that

$$c_2(X) = \sup_{\substack{T\subseteq X \\ |T|<\infty}}c_2(T)$$

for every metric space $X$. I.e., Euclidean distortion is finitely determined.

Question: Under what conditions on the metric space $X$ is $c_2(X)$ finitely determined?

Here's what I know:

• The inequality $\geq$ holds since restricting a bilipschitz function $X\to\ell^2$ to $T$ can only improve the bilipschitz constants.

• The equality is known to hold if $X$ is locally finite. This follows from the main result of Ostrovskii's "Embeddability of locally finite metric spaces into Banach spaces is finitely determined".

• The equality happens to hold for $X=\mathbb{R}/\mathbb{Z}$ with the quotient metric. This is a consequence of (the proof of) Claim 2.1 in Linial and Magen's "Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders", which establishes that $n$ equally spaced points in $X$ have distortion $\frac{n}{2}\sin\frac{\pi}{n}$. (This limits to the distortion of the obvious embedding of $X$ in $\mathbb{R}^2$.)

• The equality does not hold in pathological cases. For example, if $X$ is the power set of $\ell^2$ with trivial metric, then every finite subset of $X$ isometrically embeds into $\ell^2$ as the vertices of a regular simplex, but Cantor's theorem implies $c_2(X)=\infty$.

Answer 1

The problem is that you misdefined "Euclidean distortion". The infimum is over all maps into arbitrary Hilbert spaces, not just $\ell_2$. Of course, you can use only $\ell_2$ if the metric space is separable, but not when it is non separable. Now if every finite subset $F $of an infinite metric space $X$ embeds into $\ell_2$ with constant $C+ |F|^{-1}$, then $X$ C-embeds into an ultra power of $\ell_2$, and ultra powers of a Hilbert space are Hilbert spaces.