Global structure of the Gromov-Hausdorff space

This question has been asked and answered on MathOverflow. I have replicated the accepted answer by George Lowther below.

To answer the main question -- there are no nontrivial self-isometries of $\mathcal{GH}$.

I can give a proof of this, but as it is getting rather long, I will state some facts in $\mathcal{GH}$ without proof for now, and will come back and provide provide proofs or references.

First, a bit of notation. Let ${\rm diam}(A)=\sup\{d(a,b)\colon a,b\in A\}$ denote the diameter of a metric space $A$. For any $\lambda > 0$ use $\lambda A$ to denote the space with the same points as $A$, but with scaled metric given by $d_\lambda(a,b)=\lambda d(a,b)$. Let $\Delta_n$ denote the (n-1)-simplex - a space consisting of $n$ points all at unit distance from each other. So, $\Delta_1$ is the space consisting of a single point, and $\lambda\Delta_n$ is a space consisting of $n$ points all at distance $\lambda$ from each other.

Now, the following are standard, \begin{align} &d_{GH}(\Delta_1,A)=\frac12{\rm diam}(A),\\ &d_{GH}(A,B)\le\frac12\max({\rm diam}(A),{\rm diam}(B)),\\ &d_{GH}(\lambda A,\mu A)=\frac12\lvert\lambda-\mu\rvert{\rm diam}(A). \end{align} For reference, I am using Some Properties of Gromov–Hausdorff Distances by Fecundo Mémoli for the standard properties of $\mathcal{GH}$. Then, the one-point space $\Delta_1$ is distinguished just in terms of the metric on $\mathcal{GH}$ as follows,

1. $A$ is isometric to $\Delta_1$ if and only if $d_{GH}(B,C)\le\max(d_{GH}(A,B),d_{GH}(A,C))$ for all $B,C\in\mathcal{GH}$.

That this inequality holds for $A=\Delta_1$ follows from the first two standard properties above. On the other hand, if $A$ contains more than one point, so ${\rm diam}(A)>0$, we can take $B=\Delta_1$ and $C=\lambda A$ for any $\lambda > 1$, $$ \begin{eqnarray} d_{GH}(B,C)&=&d_{GH}(\Delta_1,\lambda A)=\frac\lambda2{\rm diam}(A) \\ &>&\frac12\max(1,\lambda-1){\rm diam}(A)=\max(d_{GH}(A,B),d_{GH}(A,C)) \end{eqnarray}. $$ So, statement 1 holds in both directions. Therefore, any isometry fixes $\Delta_1$ and, by the first standard property of $\mathcal{GH}$ above, it preserves the diameter of spaces.

Next, the simplexes $\Delta_n$ are distinguished in terms of the metric as follows,

2. The following are equivalent for any $A\in\mathcal{GH}$.

  • ${\rm diam}(A)=1$ and $d_{GH}(B,C)\le\max(d_{GH}(A,B),d_{GH}(A,C))$ for all $B,C\in\mathcal{GH}$ with diameter less than or equal to $1$.
  • $A=\Delta_n$ for some $n\ge2$.

The proof of this is given below. So, an $\iota$ is an isometry on $\mathcal{GH}$ maps the set of simplifies $\{\Delta_n\colon n\ge2\}$ to itself. Now, the finite spaces in $\mathcal{GH}$ can be identified.

3. For any $n\ge2$ and $A\in\mathcal{GH}$, the following are equivalent.

  • $d_{GH}(A,B)=d_{GH}(\Delta_n,B)$ for all $B\in\mathcal{GH}$ with $d_{GH}(\Delta_n,B)={\rm diag}(B)\ge\max({\rm diag}(A),1)$.
  • $A$ is a finite space $n$ or fewer points.

Therefore, if $\mathcal{GH}_n$ denotes the finite metric spaces with $n$ or fewer points, (2) and (3) imply that $\iota$ permutes $\{\mathcal{GH}_n\colon n\ge2\}$. As it must preserve the inclusions $\mathcal{GH}_n\subset\mathcal{GH}_{n+1}$, it follows that $\iota$ maps $\mathcal{GH}_n$ to itself for each $n\ge2$.

Now, fix $n\ge2$, let $N=n(n-1)/2$, and $S$ be the subset of $\mathbb{R}^N$ consisting of points $\mathbf x=(x_{ij})_{1\le i < j\le n}$ with $x_{ij}>0$ and $x_{ik}\le x_{ij}+x_{jk}$ for all distinct $i,j$ (here, I am using $x_{ij}\equiv x_{ji}$ whenever $i > j$. Let $G$ be the group of linear transformations of $\mathbb{R}^N$ mapping $\mathbf x$ to $g_ \sigma(\mathbf x)=(x_{\sigma(i)\sigma(j)})$ for permutations $\sigma\in S_n$. Then, $S$ is a region in $\mathbb{R}^N$ with nonempty interior bounded by a finite set of hyperplanes, and maps in $G$ take the interior of $S$ into itself. We can define $\theta\colon S\to\mathcal{GH}$ by letting $\theta(\mathbf x)$ be the space with $n$ points $a_1,\ldots,a_n$ and $d(a_i,a_j)=x_{ij}$, and define a (continuous multivalued) function $f\colon S\to S$ by $\theta\circ f=\iota\circ\theta$. Then, $\theta$ maps $S$ onto the metric spaces with $n$ points, the values of $f(\mathbf x)$ are orbits of $G$, and the fact that $\iota$ is an isometry means that if $\mathbf y=f(\mathbf x)$ and $\mathbf y^\prime=f(\mathbf x^\prime)$, then $\min_g\lVert g(\mathbf y)-\mathbf y^\prime\rVert=\min_g\lVert g(\mathbf x)-\mathbf x^\prime\rVert$, with the minimum taken over $g\in G$ and using the $\ell_\infty$ norm on $\mathbb{R}^N$.

Now, let $X\subset\mathbb{R}^N$ consist of the fixed points of elements of $G$, which is a finite union of hyperplanes, and $S^\prime=S\setminus\ X$. Note that $f$ maps $S^\prime$ into itself -- suppose that $\mathbf y = f(\mathbf x)\in X$ for some $\mathbf x\in S^\prime$. Then, $g(\mathbf y)=\mathbf y$ for some $g\in G$. Choosing $f(\mathbf x^\prime)=\mathbf y^\prime$ arbitrarily close to $\mathbf y$ with $h(\mathbf y^\prime)\not=\mathbf y^\prime$ (all $h\in G$), we have $\mathbf x^\prime$ and and $g(\mathbf x^\prime)$ arbitrarily close to $\mathbf x$, so $g(\mathbf x)=\mathbf x$, contradicting the assumption. So, in the neighbourhood of any point in $S^\prime$, we can take a continuous branch of $f$, in which case $f$ is locally an isometry under the $\ell_\infty$ norm, which is only the case if $f(\mathbf x)=P\mathbf x+\mathbf b$ (where $P$ permutes and possibly flips the signs of elements of $\mathbf x$, and $\mathbf b\in\mathbb{R}^N$), with $P$ and $\mathbf b$ constant over each component of $S^\prime$. As $\mathbf x\to 0$, $\theta(\mathbf x)$ tends to $\Delta_1$, from which we see that $\mathbf b=0$.

So, we have $f(\mathbf x)=P\mathbf x$, and as the components of $f(\mathbf x)$ are positive, $P$ is a permutation matrix. In order that $f$ is continuous across the hyperplanes in $X$, we see that $P$ is constant over all of $S^\prime$ (choosing continuous branches of $f$ across each hyperplane). Then, $P^{-1}gP\in G$, for all $g\in G$, as $f$ is invariant under the action of $G$. So, $P$ is in the normalizer of $G$. Now, it can be seen that centraliser of $G$ in the group of permutations (acting on $\mathbb{R}^N$ by permuting the elements) is trivial, which implies that its normaliser is itself (Permutation Groups, see the comment preceding Theorem 4.2B). Hence $P\in G$, so $\iota$ acts trivially on the spaces with $n$ points. As the finite spaces are dense in $\mathcal{GH}$, $\iota$ is trivial.

I'll now give a proof of statement (2) above, for which the following alternative formulation of the Gromov-Hausdorff distance will be useful. A correspondence, $R$, between two sets $A$ and $B$ is a subset of $A\times B$ such that, for each $a\in A$ there exists $b\in B$ such that $(a,b)\in R$ and, for each $b\in B$, there is an $a\in A$ with $(a,b)\in R$. The set of correspondences between $A$ and $B$ is denoted by $\mathcal R(A,B)$. If $A,B$ are metric spaces then the discrepancy of $R$ is, $$ {\rm dis}(R)=\sup\left\{\lvert d(a_1,a_2)-d(b_1,b_2)\rvert\colon (a_1,b_1),(a_2,b_2)\in R\right\}. $$ The Gromov-Hausdorff distance is the infimum of ${\rm dis}(R)/2$ taken over $R\in\mathcal R(A,B)$.

Now, lets prove (2), starting with the case where $A=\Delta_n$, some $n\ge2$, for which we need to prove $$ d_{GH}(B,C)\le\max(d_{GH}(\Delta_n,B),d_{GH}(\Delta_n,C)) $$ whenever $B,C$ have diameter bounded by $1$. As we have, $d_{GH}(B,C)\le1/2$, the required inequality is trivial unless $d_{GH}(\Delta_n,B)$ and $d_{GH}(\Delta_n,C)$ are strictly less than $1/2$, so we suppose that this is the case. Denote the points of $\Delta_n$ by $p_1,p_2,\ldots,p_n$. If $R\in\mathcal R(\Delta_n,B)$ is such that ${\rm dis}(R)/2 < 1/2$, then letting $B_i$ consist of the points $b\in B$ with $(p_i,b)\in R$, the sets $B_1,\ldots,B_n$ cover $B$. For any $b,b^\prime\in B_i$ then $d(b,b^\prime)=\lvert d(p_i,p_i)-d(b,b^\prime)\rvert\le{\rm dis}(R)$, so the $B_i$ have diameters bounded by ${\rm dis}(R)$. Also, for any $i\not=j$, if $b\in B_i\cap B_j$ then ${\rm dis}(R)\ge\lvert d(p_i,p_j)-d(b,b)\rvert=1$, giving a contradiction. So, the $B_i$ are disjoint sets covering $B$. Similarly, if $S\in\mathcal R(\Delta_n,C)$ has ${\rm dis}(S)/2 < 1/2$ then we can partition $C$ into $n$ sets, $C_i$, of diameter bounded by ${\rm dis}(S)$. Defining $T=\bigcup_{i=1}^n(B_i\times C_i)\in\mathcal R(B,C)$, it can be seen that ${\rm dis}(T)\le\max({\rm dis}(R),{\rm dis}(S))$, from which the required inequality follows.

Now, we prove the converse - if $A$ has diameter $1$ and is not isometric to $\Delta_n$ for any $n$, then we can find spaces $B,C$ of diameter $1$ with $d_{GH}(B,C)=1/2$ and with $d_{GH}(A,B)$, $d_{GH}(A,C)$ strictly less than $1/2$. I'll consider first the case where $A$ is finite with $m\ge2$ points, so $A=\{a_1,\ldots,a_m\}$. As $A$ is not isometric to $\Delta_m$, there must exist two points separated by less than unit distance. Wlog, take $d(a_{m-1},a_m)=x < 1$. Then, $m > 2$, otherwise $A$ would have diameter $x < 1$. We can define $R\in\mathcal R(A,\Delta_{m-1})$ to be $\{(a_i,p_i)\colon i=1,\ldots,m-1\}\cup\{(a_m,p_{m-1})\}$, which has discrepancy bounded by the max of $\lvert d(a_i,a_j)-1\rvert$ over $i\not=j$ and $d(a_{m-1},a)m)=x$. So, $d_{GH}(A,\Delta_{m-1}) < 1/2$. Next, we can define $R\in\mathcal R(A,\Delta_m)$ to be the collection of pairs $(a_i,p_i)$ for $i=1,\ldots,m$. Its discrepancy is the max of $d(a_i,a_j)-1$ over $i\not=j$, which is strictly less than $1$, so $d_{GH}(A,\Delta_m) < 1/2$. However, $d_{GH}(\Delta_{m-1},\Delta_m)=1/2$, so $B=\Delta_{m-1}$ and $C=\Delta_m$ satisfies the desired properties.

Now, suppose that $A$ is not a finite space. For any $m\ge2$ there exists a collection $a_1,a_2,\ldots,a_m$ of $m$ distinct points in $A$. Then, by compactness, we can cover $A$ with a finite collection of nonempty sets $A_1,\ldots,A_r$ of diameter bounded by $1/2$. Set $A_{r+i}=\{a_i\}$ for $i=1,\ldots,m$. Let $S=\{s_1,\ldots,s_{m+r}\}$ be the finite space with $d(s_i,s_j)=1$ for $i,j > r$ and with distance $1/2$ between all other pairs of points. The correspondence $R=\bigcup_{i=1}^{m+r}(A_i\times\{s_i\})$ has discrepancy $$ {\rm dis}(R)=\max\left\{1/2,1-d(a_i,a_j)\colon 1\le i < j\le m\right\} < 1. $$ So, $S$ is finite with diameter $1$, contains a subset isometric to $\Delta_m$, and $d_{GH}(A,S) < 1/2$.

Now, we can let $B$ be any finite set with diameter $1$ and $d_{GH}(A,B) < 1/2$. If $m$ greater than the number of points in $B$, let $C$ be a finite set with diameter $1$, a subset isometric to $\Delta_m$, and $d_{GH}(A,C) < 1/2$. Then, $d_{GH}(B,C)=1/2$, and satisfies the required properties, proving (2).

Tags:

General Topology

Metric Spaces

Related

Inequality involving number of binary Lyndon words of length $n$ and $n+1$ Is there a continuous $f(x,y)$ which is not of the form $f(x,y) = g_1(x) h_1(y) + \dots + g_n(x) h_n(y)$ Independence of Poisson random variables coming from Poisson sampling Infinite Integral of Trigonometric Functions Is this extension of Goldbach's conjecture obviously false? Interesting functional equation: $f(x)=\frac{x}{x+f\left(\frac{x}{x+f(x)}\right)}$ How to solve this recurrence $K(n)=2K(n-1)-K(n-2)+C$? Is infinity an element of the natural numbers? Why can a closed, bounded interval be uncountable? Holder Continuous Functions on $[0,1]$ are complete + Banach space Are there more transcendental numbers or irrational numbers that are not transcendental? What is the primitive function of $\int 1/(x^{2n} +1)dx$?

Recent Posts