For which metric spaces is Gromov-Hausdorff distance actually achieved?

Question

Question

For which pairs $M,N$ of compact metric spaces does there exist a metric space $K$ along with isometric embeddings $i:M \to K$ and $j:N \to K$ so that the Hausdorff distance between $i(M)$ and $j(N)$ in $K$ equals the Gromov-Hausdorff distance between $M$ and $N$ exactly?

We always have $d_\text{GH}(M,N) \leq d_\text{H}(i(M),j(N))$ by definition, so it suffices to decide if there exist any constraints intrinsic to $M$ and $N$ which force the reverse inequality to also hold for some judicious choice of $i,j,K$.

Update

Bill Johnson's nice answer appears to settle the question for compact $M$ and $N$ affirmatively: the Gromov-Hausdorff distance can always be realized by an ultraproduct construction. In light of that answer -- and also in light of the fact that I did not intend to assume compactness in the original question but stupidly wrote it down anyway -- here is a modified question:

Can the GH-distance be similarly achieved if we only assume that $M$ and $N$ are bounded, rather than compact?

In general, I am interested in the weakest hypotheses on $M$ and $N$ which are known to guarantee embeddings into a common target space $K$ so that the Gromov-Hausdorff distance between $M$ and $N$ equals the Hausdorff distance of their isometric images in $K$. It is not clear to me that a modification of Bill's argument works when we drop compactness.

Background

Given a compact metric space $M$ and two subspaces $A, B \subset M$, their Hausdorff distance -- denoted $d_\text{H}(A,B)$ -- is defined to be the smallest $\epsilon > 0$ so that $B$ is contained in $A$ thickened by $\epsilon$ and vice-versa.

The Gromov-Hausdorff distance $d_\text{GH}(M,N)$ between two compact metric spaces $M$ and $N$ is defined to be the infimum over triples $(i,j,K)$ of $d_\text{H}(i(M),j(N))$ where $K$ is a metric space and $i,j$ are isometric embeddings of $M, N$ into $K$. The question asks when this infimum can be explicitly realized.

Answer 1

Unless I am missing something, the distance is achieved for compact metric spaces. Take isometries $i_n :M \to K_n$ and $j_n : N \to K_n$ that give you the Gromov-Hausdorff distance up to $1/n$. Let $K$ be an ultraproduct of the $K_n$ and $i$, $j$ the isometries from $M$, $N$ into $K$ induced by $i_n$, $j_n$. This achieves the distance, I think, when $M$ and $N$ are compact. To see that, given $x$ in $M$ take $y_n$ in $N$ s.t. the distance of $i_n(x) $ to $j_n(y_n)$ is less than the Hausdorff distance from $i_n(M)$ to $j_n(N)$. Let $y$ be the ultralimit of $y_n$ in $N$ (this is where compactness is used). Then the distance from $i(x)$ to $j(y)$ is at most the Gromov-Hausdorff distance from $M$ to $N$.

This is a pretty obvious argument, so I guess it is either written somewhere or is complete nonsense.

Answer 2

Bounded is not sufficient to ensure that the Gromov-Hausdorff distance is actually achieved. Here is a counterexample:

Let $M$ be a metric space whose underlying set is $\mathbb{N}\times\{0,1\}$ with the following metric: $d((a,i),(b,j))=1$ if $a\neq b$ and $d((a,0),(a,1))=2^{-a}$. Let $N$ be $M$ with a single new point $x$ such that $d(x,y)=1$ for all $y\neq x$. $d_{GH}(M,N)=0$ but this cannot be realized in any common embedding because $M$ and $N$ are not isomorphic.

For bounded metric spaces we can use the formalism of continuous logic to state a few situations in which we can ensure that the distance is actually achieved (although these conditions are probably not very useful).

The first one is for any bounded metric spaces $M$ and $N$ there are elementary extensions $M^\prime \succeq M$ and $N^\prime \succeq N$ and a common embedding $i:M^\prime \rightarrow K $ and $j:N^\prime \rightarrow K$ such that $d_H(i(M^\prime),j(M^\prime))=d_{GH}(M,N)$. You can achieve this with exactly the same argument as in Bill's answer, specifically an ultrapower construction, the only difference is that for non-compact spaces the ultrapower will grow.

The second one is that if $M$ and $N$ are "resplendent" in the model theoretic sense then there will always exist $i:M\rightarrow K$ and $j:N\rightarrow K$ such that $d_H(i(M),j(N))=d_{GH}(i(M),j(N))$. Nobody has bothered to write up the details of how resplendence works in continuous logic but I'm fairly confident that the most common conditions ensuring it will work the same as they do in discrete logic, in particular if you know that $M$ and $N$ have the same density character and are either saturated or special then the Gromov-Hausdorff distance between them will be achieved.

In general though I imagine that for an arbitrary pair of bounded metric spaces this problem is very hard.

Answer 3

Front Note: Hanson's example works perfectly through a good correspondence (I failed to consider the case where $\infty$ is related to two elements that are pairs.) but I will keep the following up as a belabored example of bounded does not imply attains distance. Apologies

First, recall that the Gromov Hausdorff distance between metric spaces can be calculated through correspondences.

A correspondence $R \subset X \times Y$ is a relation that satisfies $\pi_X(R) = X, \pi_Y(Y) = Y$ and let $\mathcal{R}(X,Y)$ be the set of correspondences between $X,Y$. Then we can define the distortion of a correspondence by:

$$dis(R) = \sup \{ |d(x,x') - d(y,y') | (x,y), (x',y') \in R \}$$

Then it is true for all metric spaces that

$$d_{GH}(X,Y) = \frac{1}{2}\inf_{R \in \mathcal{R}(X,Y)} dis(R)$$

Consider $X = \{ (a, i) : a \in \mathbb{N}, i \in \{ 0,1 \} \}$ .

Then give this the metric: $d((a,i),(b,j)) = 1, d((a,0),(a,1))= 1-2^a$ . Here, as an analyst, $0 \notin \mathbb{N}$

Then let $Y= X \cup \{\infty\}$ where $\infty$ lies distance 1 from all other elements. Note that the point at infinity has the limiting behaviour of the $(a,1)$ to some degree (distance 1 from everything).

Then note that $X, Y$ can't be isometric as $X$ contains no point distance 1 from all other points. We will now show that $d_{GH}(X,Y) = 0$ through the use of correspondences, we will define a correspondence with $dis(R) = 2^{-n}$

Here we define the correspondence for each n by the following. First we relate the first n spikes directly across X and Y.

But then we zig-zag after this point. If we give X the lexicographic ordering, we move each element further along. Then we put $\infty$ at $(n,0)$.

Then note that $\infty$ was previously distance 1 from everything. Now it is distance 1 from everything but $(n,1)$ which it is distance $1-2^{-n}$ from.

Furthermore other terms either maintain distance 1 or they gain a new neighbor so distance changes from $1$ to $1-2^{-m}$ for $m > n$ showing $dis(R) = 2^{-n}$.

Thus $d_{GH}(X,Y) = 0$ and notably $X,Y$ are complete bounded metric spaces that fail to be isometric despite being lying distance 0 apart showing that being totally bounded is a crucial property to attain the distance.

Answer 4

In the embedding problem we care only about the distances between the images of $x\in X$ and $y \in Y$ denoted by $\rho(x,y)$, the rest of the container space being superfluous. Therefore, we consider

$$\rho\colon X \times Y\to [0, \infty)$$ such that

1. $ \rho(x,y) + \rho(x,y') \ge d_Y(y,y')$

2. $ \rho(x,y) + \rho(x',y) \ge d_X(x,x')$

3. $ \rho(x,y) + d_Y(y, y') \ge \rho(x,y')$

4. $\rho(x,y) + d_X(x,x') \ge \rho(x', y)$

From 3., 4. we get

5. $|\rho(x, y)-\rho(x,y')| \le d_Y(y,y')$

6. $|\rho(x,y) - \rho(x',y)| \le d_X(x,x')$

Now the G-H distance between $X$ and $Y$ equals

$$\inf_{\rho}( D_{\rho})\colon = \inf_{\rho} (\max( \sup_{x\in X} \inf_{y\in Y} \rho(x,y), \sup_{y\in y} \inf_{x\in X} \rho(x,y)) )$$

over all functions $\rho$ satisfying the conditions 1.-4. It is easy to see that if $X$, $Y$ are compact this family of functions $\{\rho\}$ satisfies the conditions of Arzela-Ascoli, and moreover the functional $\rho\mapsto D_{\rho}$ is continuous. Hence the G-H distance is achieved for compact metric space $X$, $Y$.