Rough isometries

An isometry is a map {f\colon X\rightarrow Y} between two metric spaces {X,Y} which preserves all distances: {d_Y(f(x),f(x')) = d_X(x,x')} for all {x,x'\in X}. (After typing a bunch of such formulas, one tends to prefer shorter notation: {|f(x)f(x')| = |xx'|}, with the metric inferred from contexts.) It’s a popular exercise to prove that every isometry from a compact metric space into itself is surjective.

A rough isometry allows additive distortion of distances: {|\,|f(x)f(x')| - |xx'|\,|\le \epsilon}. (As contrasted with bi-Lipschitz maps, which allow multiplicative distortion). Rough isometries ignore small-scale features (in particular, they need not be continuous), but accurately capture the large scale structure of a space. This makes them convenient for studying hyperbolic spaces (trees and their relatives), where the large-scale structure is of interest.

If {f} is an {\epsilon}-rough isometry, then the Gromov-Hausdorff distance {d_{GH}} between {X} and {f(X)} is at most {\epsilon/2}. This follows from a convenient characterization of {d_{GH}}: it is equal to {\frac12 \inf_R \textrm{dis}\,(R)} where the infimum is taken over all subsets {R\subset X\times Y} that project surjectively onto each factor, and {\textrm{dis}\,(R) = \sup \{|\,|xx'|-|yy'|\,| \colon xRy, \ x'Ry' \} }.

Since small-scale features are ignored, it is not quite natural to talk about rough isometries being surjective. A natural concept for them is {\epsilon}-surjectivity, meaning that every point of {Y} is within distance {\le \epsilon} of {f(X)}. When this happens, we can conclude that {d_{GH}(X,Y)\le 3\epsilon/2}, because the Hausdorff distance between {Y} and {f(X)} is at most {\epsilon}.

Recalling that an isometry of a compact metric space {X} into {X} is automatically onto, it is natural to ask whether {\epsilon}-rough isometries of {X} into {X} are {\epsilon}-surjective. This, however, turns out to be false in general.

First example, a finite space: {X=\{0,1,2,\dots,n\}} with the metric {d(i,j) = i+j} (when {i\ne j}). Consider the backward shift {f(i)=i-1} (and {f(0)=0}). By construction, this is a rough isometry with {\epsilon=2}. Yet, the point {n} is within distance {n} from {f(X) = \{0,1,2,\dots, n-1\}}.

The above metric can be thought of a the distance one has to travel from {i} to {j} with a mandatory visit to {0}. This makes it similar to the second example.

Second example, a geodesic space: {X} is the graph shown below, a subset of {\mathbb R^2} with the intrinsic (path) metric, i.e., the length of shortest path within the set.

Comb space
Comb space

Define {f(x,y) = ((x-1)^+, (y-1)^+)} where {{\,}^+} means the positive part. Again, this is a {2}-rough isometry. The omitted part, shown in red below, contains a ball of radius {5} centered at {(5,5)}. Of course, {5} can be replaced by any positive integer.

Omitted part in red
Omitted part in red

Both of these examples are intrinsically high-dimensional: they cannot be accurately embedded into {\mathbb R^d} for low {d} (using the restriction metric rather than the path metric). This raises a question: does there exist {C=C(d)} such that for every compact subset {K\subset \mathbb R^d}, equipped with the restriction metric, every {\epsilon}-rough isometry {f\colon K\rightarrow K} is {C(d)\epsilon}-surjective?

Four-point CAT(0) condition

The definition of a metric space guarantees that if we pick three points {A,B,C} from it, we can draw a triangle in the Euclidean plane, with vertices labeled {A,B,C} so that the side lengths are equal to the corresponding distances {|AB|, |BC|, |CA|} in the metric space. In other words, we can represent any triple of points as vertices of a triangle.

Triangle representation
Triangle representation

The above paragraph is from Tight spans and Gromov hyperbolicity, but here the similarity ends. Moving on to four points {A,B,C,D} we find that it is possible to draw a quadrilateral with side lengths equal to the corresponding distances
{|AB|, |BC|, |CD|, |DA|}.

Quadrilateral with prescribed side lengths
Quadrilateral with prescribed side lengths

Except for the degenerate case (one length equal to the sum of three others), the quadrilateral is not rigid: one can change the angles while keeping the sidelengths the same.

Since the quadrilateral has one degree of freedom, we cannot hope to have the correct lengths of both diagonals {AC} and {BD}. One of two diagonals can be made to match the metric space distance, just be drawing two triangles and gluing them together. But this is not so interesting.

There is an interesting class of metric spaces for which one can always draw a Euclidean quadrilateral as above so that neither diagonal is too short (they are allowed to be too long). These are called CAT(0) spaces, and they generalize the concept of a Riemannian manifold of nonpositive sectional curvature (more on this later). Every Euclidean space is CAT(0) for obvious reasons.

For example, if a CAT(0) space contains four points with pairwise distances {|AB|=|CD|=2}, {|BC|=|DA|=1}, then {|AC|^2+|BD|^2\le 10}. Indeed, any Euclidean quadrilateral with these sidelengths is a parallelogram, in which the sum of squares of the diagonals is {2\cdot (2^2+1^2)=10}. (It never pays to draw {ABCD} with self-intersections, because that only makes the “diagonals” shorter).

For a non-parallelogram example, take {|AB|=2}, {|BC|=3}, {|CD|=4},and {|DA|=5}. The diagonal lengths {|AC|=4} and {|BD|=6} are allowed by the axioms of a metric space, but not by the CAT(0) condition.

Non-CAT(0) quadrilateral
Non-CAT(0) quadrilateral

This can be checked using a bunch of cosine formulas:

\displaystyle    \cos\angle ADB = \frac{5^2+6^2-2^2}{2\cdot 5\cdot 6} =\frac{19}{20}, \\ {}\\    \cos\angle CDB = \frac{4^2+6^2-3^2}{2\cdot 4\cdot 6} =\frac{43}{48}, \\ {} \\   \cos\angle CDA = \frac{|AD|/2}{|CD|} =\frac{5}{8},

where the last computation is simpler because {\triangle CDA} is isosceles. Since {\angle CDA=\angle CDB+\angle ADB}, the addition law of cosines yields a contradiction.

Let’s see what CAT(0) has to do with curvature. First, a closed curve with intrinsic metric is not a CAT(0) space. Indeed, one can find four points {A,B,C,D} on the curve that are equally spaced at distances {L/4}, where {L} is the length of the curve. Then the corresponding Euclidean quadrilateral must be a rhombus of sidelength {L/4}. One of its diagonals will be at most {L\sqrt{2}/4}, which is less than {L/2} required by the intrinsic metric of the curve.

As a corollary, a CAT(0) space does not have closed geodesics. One can object that compact negatively curved manifolds (e.g., double torus) have plenty of closed geodesics. The answer is that to actually characterize nonnegatively curved spaces, one must impose the CAT(0) condition only locally.

The standard definitions of a CAT(0) space require any two points to be connected by a geodesic, and are stated in terms of geodesics. Here is one of them: for any geodesic {\gamma\colon [a,b]\rightarrow X} and for any fixed point {A\in X} the function

\displaystyle  F(t)=d\,^2(\gamma(t),A)-t^2 \ \ \ \ \ (1)

is convex. (Here {d\,^2} is the square of the distance.)

Distance function on a geodesic
Distance function on a geodesic

The condition (1) may look contrived, until one realizes that in a Euclidean space {F} is always an affine function. Thus, the definition says that the distance function in a CAT(0) space is at least as convex as in a Euclidean space. By the way, (1) indeed implies that {t\mapsto d(\gamma(t),A)} is a convex function. I leave this as an exercise.

Three hyperbolic metrics

Up to a constant factor, there is just one conformally invariant Riemannian metric {\rho} on the disk {\mathbb{D}=\{z\in {\mathbb C}\colon |z|<1\}}. Indeed, on the tangent space at {0} the metric must be a multiple of the Euclidean one, due to rotational invariance. Normalizing so that at {0} both metrics coincide, we can use the invariance under conformal automorphisms (Möbius transformations)

\displaystyle \psi_a(z) = \frac{z+a}{1+\bar a z},\quad |a|<1

to find that on the tangent space at {a} the metric {\rho} differs from Euclidean only by the factor of {|\psi'_a(a)| (1-|a|^2)^{-1}}. This can be written as {d\rho(z) = (1-|z|^2)^{-1}|dz|}, indicating what we integrate to find the length of curves with respect to {\rho}. This is the Poincaré disk model of the hyperbolic plane. The geodesics of {\rho} are precisely the circles orthogonal to {\partial\mathbb{D}}, and diameters.

Hyperbolic geodesics
Hyperbolic geodesics

We could model the hyperbolic plane on any other proper simply-connected domain {\Omega\subset {\mathbb C}}, just by pulling back {\rho} under the Riemann map {\phi\colon\Omega\rightarrow\mathbb{D}}. Explicitly, {d\rho_{\Omega}(z)=(1-|\phi(z)|^{-2})\,|\phi'(z)|\,|dz|}. But is this really explicit? We have no closed form for {\phi} except for very special domains {\Omega}. The density {\rho_\Omega} can be quite tricky: see this MathOverflow question.

On the disk {\mathbb{D}}, the density of {\rho} is roughly the reciprocal of the distance to the boundary. The Koebe distortion theorem yields the same for all simply connected domains:

\displaystyle \mathrm{dist}\,(z,\partial \Omega)^{-1} \le \frac{|d\rho_\Omega(z)|}{|dz|}\le 4\, \mathrm{dist}\,(z,\partial \Omega)^{-1}

Disk and slit plane realize 1 and 4, respectively.
Disk and slit plane realize 1 and 4, respectively.

This suggests replacing the hyperbolic metric {\rho_\Omega} with the quasihyperbolic metric {d\delta_\Omega(z)=\mathrm{dist}\,(z,\partial \Omega)^{-1}\,|dz|}. The density of {\delta_\Omega} is about as simple as we could wish for, but the shape of its geodesics is not as obvious; indeed, a number of papers were written on this subject in the last 35 years.

Can we have a hyperbolic-type metric with explicit geodesics and explicit density? The Hilbert metric delivers both, at least in bounded convex domains. The idea is simple: instead of dividing the length of each tangent vector {v\in T_a} by {\mathrm{dist}\,(a,\partial \Omega)}, we divide it by {\mathrm{dist}_v\,(a,\partial \Omega)}, which is the distance measured in the direction of {v}. In other words, this is how long you could walk in the direction {v} before hitting the boundary. It is clear that the length of any curve going to the boundary is infinite due to the divergence of {\int_{0^+} \frac{dx}{x}}, same as for hyperbolic and quasihyperbolic metrics. Since it is awkward to have a “metric” that is not symmetric (the lengths of {v} and {-v} are not the same), we symmetrize:

\displaystyle \|v\|_{\Omega,a} =\frac12 \left(\frac{1}{\mathrm{dist}_v\,(a,\partial \Omega)} +    \frac{1}{\mathrm{dist}_{-v}\,(a,\partial \Omega)} \right) |v|_{{\mathbb R}^2}

Directional distances to the boundary
Directional distances to the boundary

Now the distances between points are defined in the usual way, as the infimum of lengths of connecting curves {\gamma \colon [a,b]\rightarrow\Omega},

\displaystyle L(\gamma) = \int_a^b \|\gamma'(t)\|_{\Omega,\gamma(t)}\,dt

This is the Hilbert metric {d_\Omega}. Despite all its non-Euclideanness, the geodesics of {d_\Omega} are line segments. This (nontrivial) fact makes it easy to calculate the distance between two points {a,b\in\Omega}: besides the points themselves, one only needs to consider the pair of points {a',b'} where the line through {a,b} meets {\partial \Omega}. The integral ends up being (half of) the logarithm of the cross-ratio of these four points. Assuming {a',a,b,b'} are situated in the listed order, the relevant cross-ratio is

\displaystyle \frac{|a'-b|\, |a-b'|}{|a'-a|\,|b-b'|}

which is greater than {1}, making the logarithm positive.

I personally find the integral of reciprocals of distances more intuitively accessible than the logarithm of cross-ratio. Either version of the definition makes it clear that the Hilbert metric is invariant under projective transformations, a property not shared by the metrics {\rho} and {\delta}.

It turns out that {d_{\mathbb D}} is also a model of the hyperbolic plane, but with geodesics being line segments rather than circular arcs. Along each diameter {d_{\mathbb D}} coincides with {\rho}, because at Euclidean distance {r} from the center it scales vectors by

\displaystyle    \frac{1}{2}\left(\frac{1}{1-r}+\frac{1}{1+r}\right) = \frac{1}{1-r^2}

Behold the magic of partial fractions!