NON-REDUCTION OF RELATIONS IN THE GROMOV SPACE TO
POLISH ACTIONS

JESÚS A. ÁLVAREZ LÓPEZ AND ALBERTO CANDEL

ABSTRACT. It is shown that, in the Gromov space of isometry classes of pointed proper metric spaces, the equivalence relations defined by existence of coarse quasi-isometries or being at finite Gromov-Hausdorff distance, cannot be reduced to the equivalence relation defined by any Polish action.

CONTENTS

<table><tr><td>1. Introduction</td><td>1</td></tr><tr><td>2. The Gromov space</td><td>2</td></tr><tr><td>3. Equivalence relations on the Gromov space</td><td>4</td></tr><tr><td>4. Non-reduction to Polish actions</td><td>5</td></tr><tr><td>References</td><td>9</td></tr></table>

1. INTRODUCTION

Gromov [4, Chapter 3], [3] described a space, denoted here by $M_*$, whose points are isometry classes of pointed complete proper metric spaces. It is endowed with a topology which resembles the Tychonov topology of $\mathbb{R}^N$, or the compact open topology on the space of continuous functions $C(\mathbb{R})$. It also supports several equivalence relations of geometric interest, like the relation of being at finite Gromov-Hausdorff distance, $E_{GH}$, and the relation of being (coarsely) quasi-isometric, $E_{QI}$.

The following concepts relate the complexity of two equivalence relations on topological spaces, $E$ over $X$ and $F$ over $Y$. A map $\theta: X \to Y$ is called $(E, F)$-invariant if $xEx' \implies \theta(x)F\theta(x')$ ($\theta$ induces a mapping $\bar{\theta}: X/E \to Y/F$). It is said that $E$ is *Borel reducible* to $F$, denoted by $E \leq_B F$, if there is an $(E, F)$-invariant Borel mapping $\theta: X \to Y$ such that $xEx' \Leftrightarrow \theta(x)F\theta(y)$ ($\bar{\theta}: X/E \to Y/F$ is injective). If $E \leq_B F$ and $F \leq_B E$, then $E$ is said to be *Borel bi-reducible* with $F$, and is denoted by $E \sim_B F$. If the map $\theta$ can be chosen to be continuous, then the terms “continuously reducible” and “continuously bi-reducible” are used, with notation “$\leq_c$” and “$\sim_c$”.

<footnote n="1991">1991 Mathematics Subject Classification. 03E15, 54H05, 54H20, 54E50.</footnote>

<footnote>Key words and phrases. Gromov space, Gromov-Hausdorff metric, quasi-isometry.</footnote>

<footnote>Research of authors supported by Spanish Ministerio de Ciencia e Innovación, grants MTM2011-25656 and MTM2008-02640.</footnote>
For an example of an equivalence relation, let $G$ be a Polish group acting continuously on a Polish space $X$ (a Polish action). We then let $E_G^X$ denote the orbit equivalence relation whose equivalence classes are exactly the $G$-orbits. For instance, Hjorth's theory of turbulence [5], [6] is valid for relations defined by Polish actions. The following is our main result.

**Theorem 1.1.** $E_{GH} \not\le_B E_G^X$ and $E_{QI} \not\le_B E_G^X$ for any Polish group $G$ and any Polish $G$-space $X$.

The theory of turbulence is extended in [1] to more general equivalence relations on Polish spaces, and it is applied to $E_{QI}$ and $E_{GH}$. This is a non-trivial extension by Theorem 1.1.

The proof of Theorem 1.1 uses the following. Let $E_1$ be the equivalence relation on $\mathbb{R}^N$ consisting of the pairs $(x, y)$, with $x = (x_n)$ and $y = (y_n)$, such that there is some $N \in \mathbb{N}$ so that $x_n = y_n$ for all $n \ge N$ (the relation of eventual agreement). We have $E_1 \not\le_B E_G^X$ for any Polish group $G$ and any Polish $G$-space $X$ [7, Theorem 4.2] (see also [5, Theorem 8.2] for a different proof).

On the other hand, let $E_{K_\sigma}$ be the equivalence relation on $\prod_{n=2}^\infty \{1, \dots, n\}$ consisting of the pairs $(x, y)$, with $x = (x_n)$ and $y = (y_n)$, such that $\sup_n |x_n - y_n| < \infty$. We have $E \le_B E_{K_\sigma}$ for any $K_\sigma$ equivalence relation<fnref n="1" /> $E$ [9, Theorem 17 and Proposition 19], and therefore $E_1 \le_B E_{K_\sigma}$ because $E_1$ is $K_\sigma$ [9], [2, Exercise 8.4.3]; in particular, $E_{K_\sigma} \not\le_B E_G^X$ for any Polish group $G$ and every Polish $G$-space $X$. Therefore Theorem 1.1 follows by showing that $E_{K_\sigma} \le_B E_{GH}$ and $E_{K_\sigma} \le_B E_{QI}$ (Proposition 4.1).

The relations $E_{GH}$ and $E_{QI}$ resemble the equivalence relation $E_{\ell_\infty}$ on $\mathbb{R}^N$ defined by the action of $\ell_\infty$ on $\mathbb{R}^N$ by translations, or the equivalence relation $E_\infty$ on $C(\mathbb{R})$ defined by the action of $C_b(\mathbb{R})$. Thus Proposition 4.1 has some analogy with the property $E_{K_\sigma} \sim_B E_{\ell_\infty}$ [9, Proposition 19]; in particular, $E_1 \le_B E_{\ell_\infty}$ (see also [2, Theorem 8.4.2]). It also has some similarity with the property $E_{K_\sigma} \le_B E_\infty$, which follows because $E_{\ell_\infty} \le_c E_\infty$; this reduction can be realized by the map $\mathbb{R}^N \to C(\mathbb{R})$, assigning to each element its canonical continuous piecewise affine extension that is constant on $(-\infty, 0]$.

## 2. THE GROMOV SPACE

Let $M$ be a metric space and let $d_M$, or simply $d$, be its distance function. The Hausdorff distance between two non-empty subsets, $A, B \subset M$, is given by

$$H_d(A, B) = \max \left\{ \sup_{a \in A} \inf_{b \in B} d(a, b), \sup_{b \in B} \inf_{a \in A} d(a, b) \right\}.$$

Observe that $H_d(A, B) = H_d(\bar{A}, \bar{B})$, and $H_d(A, B) = 0$ if and only if $\bar{A} = \bar{B}$. Also, it is well known and easy to prove that $H_d$ satisfies the triangle inequality,

<footnote n="1">¹Recall that a subset of a topological space is called $K_\sigma$ when it is a countable union of compact subsets.</footnote>

<footnote n="2">²Recall that $\ell_\infty \subset \mathbb{R}^N$ is the linear subspace of bounded sequences, and $C_b(\mathbb{R}) \subset C(\mathbb{R})$ is the linear subspace of bounded continuous functions.</footnote>
and its restriction to the family of non-empty compact subsets of M is finite valued, and moreover complete if M is complete.

Let M and N be arbitrary non-empty metric spaces. A metric on $M \sqcup N$ is called *admissible* if its restrictions to M and N are $d_M$ and $d_N$, where M and N are identified with their canonical injections in $M \sqcup N$. The *Gromov-Hausdorff distance* (or *GH distance*) between M and N is defined by

$$d_{GH}(M, N) = \inf_{d} H_{d}(M, N),$$

where the infimum is taken over all admissible metrics $d$ on $M \sqcup N$. It is well known that $d_{GH}(M, N) = d_{GH}(\bar{M}, \bar{N})$, where $\bar{M}$ and $\bar{N}$ denote the completions of M and N, $d_{GH}(M, N) = 0$ if $\bar{M}$ and $\bar{N}$ are isometric, $d_{GH}$ satisfies the triangle inequality, and $d_{GH}(M, N) < \infty$ if $\bar{M}$ and $\bar{N}$ are compact.

There is also a pointed version of $d_{GH}$ which satisfies analogous properties: the (pointed) Gromov-Hausdorff distance (or GH distance) between two pointed metric spaces, $(M, x)$ and $(N, y)$, is defined by

$$d_{GH}(M, x; N, y) = \inf_{d} \max\{d(x, y), H_{d}(M, N)\}, \quad (1)$$

where the infimun is taken over all admissible metrics $d$ on $M \sqcup N$.

A metric space, or its distance function, is called proper (or Heine-Borel) if every open ball has compact closure. This condition is equivalent to the compactness of the closed balls, which means that the distance function to a fixed point is a proper function. Any proper metric space is complete and locally compact, and its cardinality is not greater than the cardinality of the continuum. Therefore it may be assumed that their underlying sets are subsets of $\mathbb{R}$. With this assumption, it makes sense to consider the set $M_*$ of isometry classes, $[M, x]$, of pointed proper metric spaces, $(M, x)$. The set $M_*$ is endowed with a topology introduced by M. Gromov [4, Section 6], [3], which can be described as follows.

For a metric space $X$, two subspaces, $M, N \subset X$, two points, $x \in M$ and $y \in N$, and a real number $R > 0$, let $H_{d_{X,R}}(M, x; N, y)$ be given by

$$H_{d_{X,R}}(M, x; N, y) = \max \left\{ \sup_{u \in B_M(x, R)} d_X(u, N), \sup_{v \in B_N(y, R)} d_X(v, M) \right\}.$$

Then, for $R, r > 0$, let $U_{R,r} \subset M_*^2$ denote the subset of pairs $([M, x], [N, y])$ for which there is an admissible metric, $d$, on $M \sqcup N$ so that

$$\max\{d(x, y), H_{d,R}(M, x; N, y)\} < r.$$

Let $\Delta \subset M_*^2$ denote the diagonal.

**Lemma 2.1.** *The following properties hold:*

(i) $\bigcap_{R,r>0} U_{R,r} = \Delta$;

(ii) each $U_{R,r}$ is symmetric;

(iii) if $R \le S$, then $U_{R,r} \supset U_{S,r}$ for all $r > 0$;

(iv) $U_{R,r} = \bigcup_{s<r} U_{R,s}$ for all $R, r > 0$; and

(v) $U_{S,r} \circ U_{S,s} \subset U_{R,r+s}$, where $S = R + 2 \max\{r, s\}$.
*Proof.* Items (i)–(iv) are elementary. To prove (v), let $[M, x]$, $[N, y] \in \mathcal{M}_*$ and $[P, z] \in U_{S,r}(N, y) \cap U_{S,s}(M, x)$. Then there are admissible metrics, $d$ on $M \sqcup P$ and $\bar{d}$ on $N \sqcup P$, such that $d(x, z) < r$, $r_0 := H_{d,S}(M, x; P, z) < r$, $\bar{d}(y, z) < s$ and $s_0 := H_{\bar{d},S}(N, y; P, z) < s$. Let $\hat{d}$ be the admissible metric on $M \sqcup N$ such that

$$ \hat{d}(u, v) = \inf\{d(u, w) + \bar{d}(w, v) \mid w \in P\} $$

for all $u \in M$ and $v \in N$. Then

$$ \hat{d}(x, y) \le d(x, z) + \bar{d}(z, y) < r + s. $$

For each $u \in B_M(x, R)$, there is some $w \in P$ such that $d(u, w) < r_0$. Then

$$ d_P(z, w) \le d(z, x) + d_M(x, u) + d(u, w) < r + R + r_0 < S. $$

So there is some $v \in N$ such that $\bar{d}(w, v) < s_0$, and we have

$$ \hat{d}(u, v) \le d(u, w) + \bar{d}(w, v) < r_0 + s_0. $$

Hence $\hat{d}(u, N) < r_0 + s_0$ for all $u \in B_M(x, R)$. Similarly, $\hat{d}(v, M) < r_0 + s_0$ for all $v \in B_N(y, R)$. Therefore $H_{\hat{d},R}(M, x; N, y) \le r_0 + s_0 < r + s$. Then $[N, y] \in U_{R,r+s}(M, x)$. $\square$

By Lemma 2.1, the sets $U_{R,r}$ form a base of entourages of a metrizable uniformity on $\mathcal{M}_*$. Endowed with the induced topology, $\mathcal{M}_*$ is what is called the Gromov space in this paper. It is well known that $\mathcal{M}_*$ is a Polish space (see e.g. Gromov [4] or Petersen [8]); in particular, a countable dense subset is defined by the pointed finite metric spaces with Q-valued metrics.

### 3. EQUIVALENCE RELATIONS ON THE GROMOV SPACE

Recall the following terminology. A map between metric spaces, $\phi: M \to N$, is called bi-Lipschitz if there is some $\lambda \ge 1$ such that

$$ \lambda^{-1} d_M(u, v) \le d_N(\phi(u), \phi(v)) \le \lambda d_M(u, v) $$

for all $u, v \in M$. The term $\lambda$-bi-Lipschitz may be also used in this case. A subset $A \subset M$ is called a net$^3$ (respectively, separated) if there is some $C \ge 0$ such that $d_M(x, A) \le C$ for all $x \in M$ (respectively, there is some $\delta > 0$ so that $d_M(x, y) \ge \delta$ if $x \ne y$). The term C-net (respectively, $\delta$-separated) may be also used in this case. There always exist separated nets [1, Lemma 9.4]. A (coarse) quasi-isometry of $M$ to $N$ is a bi-Lipschitz bijection $\phi: A \to B$ for some nets $A \subset M$ and $B \subset N$. The existence of a quasi-isometry of $M$ to $N$ is equivalent to the existence of a finite sequence of metric spaces, $M = M_0, \dots, M_{2k} = N$, such that $d_{GH}(M_{2i-2}, M_{2i-1}) < \infty$ and there is a bi-Lipschitz bijection $M_{2i-1} \to M_{2i}$ for all $i \in \{1, \dots, k\}$. A pointed (coarse) quasi-isometry is defined in the same

<footnote>$^3$This term is used by Gromov with this meaning [4, Definition 2.14]. Other authors use it with other meanings.</footnote>
way, by using a pointed bi-Lipschitz bijection between nets that contain the distinguished points. The existence of a pointed quasi-isometry has an analogous characterization involving pointed Gromov-Hausdorff distances and pointed bi-Lipschitz bijections.

The following equivalence relations are considered on $\mathcal{M}_*$:

* The canonical relation, $E_{\text{can}}$, is defined by varying the distinguished point; i.e., $E_{\text{can}}$ consists of the pairs of the form $([M, x], [M, y])$ for any proper metric space $M$ and all $x, y \in M$.

* The Gromov-Hausdorff relation, $E_{GH}$, consists of the pairs $([M, x], [N, y]) \in \mathcal{M}_*^2$ such that $d_{GH}(M; N) < \infty$, or, equivalently, $d_{GH}(M, x; N, y) < \infty$.

* The Lipschitz relation, $E_{\text{Lip}}$, consists of the pairs $([M, x], [N, y]) \in \mathcal{M}_*^2$ such that there is a bi-Lipschitz bijection $M \to N$. If $M$ and $N$ are separated, this is equivalent to the existence of a pointed bi-Lipschitz bijection $(M, x) \to (N, y)$.

* The quasi-isometric relation, $E_{QI}$, consists of the pairs $([M, x], [N, y]) \in \mathcal{M}_*^2$ such that there is a quasi-isometry of $M$ to $N$, or, equivalently, there is a pointed quasi-isometry of $(M, x)$ to $(N, y)$. By the above observations, $E_{QI}$ is the smallest equivalence relation over $\mathcal{M}_*$ that contains $E_{GH} \cup E_{\text{Lip}}$.

Since $E_{\text{can}} \subset E_{GH} \cap E_{QI}$, it follows that $\mathcal{M}_*/E_{GH}$ can be identified with the set of classes of proper metric spaces modulo finite GH distance, and $\mathcal{M}_*/E_{QI}$ can be identified with the set of quasi-isometry types of proper metric spaces.

## 4. NON-REDUCTION TO POLISH ACTIONS

As indicated in Section 1, Theorem 1.1 follows from the following.

**Proposition 4.1.** $E_{K_\sigma} \leq_c E_{GH}$ and $E_{K_\sigma} \leq_c E_{QI}$.

*Proof.* Let us prove first that $E_{K_\sigma} \leq_c E_{QI}$, which is more difficult. Consider the metric $d$ on $\mathbb{R}^2$ defined by

$$d((u, v), (u', v')) = \begin{cases} |v| + |u - u'| + |v'| & \text{if } u \neq u' \\ |v - v'| & \text{if } u = u' \end{cases}.$$

This is the metric of an $\mathbb{R}$-tree. For each $x = (x_n) \in \prod_{n=2}^{\infty} \{1, \dots, n\}$ and $n \geq 2$, let

$$P_{x,n}^{\pm} = (\sum_{i=2}^{n} e^{i^2}, \pm e^{x_n}) \in \mathbb{R}^2, \quad M_{x,n} = \{P_{x,n}^{+}, P_{x,n}^{-}\},$$

and let $M_x := \bigcup_{n=2}^{\infty} M_{x,n}$, equipped with the restriction $d_x$ of $d$. Given any $x = (x_n) \in \prod_{n=2}^{\infty} \{1, \dots, n\}$, if $A \subset M_x$ is $C$-net for some $C \geq 0$, it easily follows that

$$e^{n^2} \geq C \implies A \cap M_{x,n} \neq \emptyset, \qquad (2)$$

$$(e^{n^2} \geq C \quad \& \quad e^{x_n} > C/2) \implies M_{x,n} \subset A. \qquad (3)$$

Let $\theta: \prod_{n=2}^{\infty} \{1, \dots, n\} \to \mathcal{M}_*$ be defined by $\theta(x) = [M_x, P_{x,2}^+]$.

*Claim 1.* $\theta$ is continuous.
With the notation of Section 2, given $x = (x_n) \in \prod_{n=2}^{\infty} \{1, \dots, n\}$ and $R, r > 0$, we have to prove that $\theta^{-1}(U_{R,r}(\theta(x)))$ is a neighborhood of $x$ in $\prod_{n=2}^{\infty} \{1, \dots, n\}$.
Take some integer $n_0 \ge 2$ such that $e^2 + \sum_{i=2}^{n_0} e^{i^2} + e^{n_0} > R$, and therefore $B_{M_x}(P_{x,2}^+, R) \subset \bigcup_{n=2}^{n_0} M_{x,n}$. Let $\mathcal{N}(x, n_0)$ be the open neighborhood of $x$ in $\prod_{n=2}^{\infty} \{1, \dots, n\}$ consisting of the elements $y = (y_n)$ such that $y_n = x_n$ if $n \le n_0$.
Then $P_{x,n}^{\pm} = P_{y,n}^{\pm}$ for $2 \le n \le n_0$ and $y \in V$, obtaining $d(P_{x,2}^+, P_{y,2}^+) = 0$ and $H_{d,R}(M_x, P_{x,2}^+; M_y, P_{y,2}^+) = 0$ for the isometric inclusion of $M_x$ and $M_y$ in $\mathbb{R}^2$ with $d$. Thus $\theta(\mathcal{N}(x, n_0)) \subset U_{R,r}(\theta(x))$, completing the proof of Claim 1.

Claim 2. $(\theta \times \theta)(E_{K_\sigma}) \subset E_{\text{Lip}}$, and therefore $(\theta \times \theta)(E_{K_\sigma}) \subset E_{QI}$.

This claim can be easily proved as follows. Let $(x, y) \in E_{K_\sigma}$ for $x = (x_n)$ and $y = (y_n)$ in $\prod_{n=2}^{\infty} \{1, \dots, n\}$. Thus there is some $C \ge 0$ such that $|x_n - y_n| \le C$ for all $n$. Consider the pointed bijection $\phi : (M_x, P_{x,2}^+) \to (M_y, P_{y,2}^+)$ defined by $\theta(P_{x,n}^{\pm}) = P_{y,n}^{\pm}$. Then, with $\lambda = e^C$, we have

$$d_x(P_{x,n}^+, P_{x,n}^-) = 2e^{x_n} \le 2e^{y_n+C} = \lambda d_y(P_{y,n}^+, P_{y,n}^-) \\ = \lambda d_y(\phi(P_{x,n}^+), \phi(P_{x,n}^-)),$$

and, similarly,

$$d_x(P_{x,n}^+, P_{x,n}^-) \ge \frac{1}{\lambda} d_y(\phi(P_{x,n}^+), \phi(P_{x,n}^-)).$$

On the other hand, for $P \in M_{x,m}$ and $Q \in M_{x,n}$ with $m < n$,

$$d_x(P, Q) = e^{x_m} + \sum_{i=m+1}^{n} e^{i^2} + e^{x_n} \le e^{y_m+C} + \sum_{i=m+1}^{n} e^{i^2} + e^{y_n+C} \\ \le \lambda \left( e^{y_m} + \sum_{i=m+1}^{n} e^{i^2} + e^{y_n} \right) = \lambda d_y(\phi(P), \phi(Q)),$$

and, similarly,

$$d_x(P, Q) \ge \frac{1}{\lambda} d_y(\phi(P), \phi(Q)).$$

Thus $\phi$ is a $\lambda$-bi-Lipschitz bijection, completing the proof of Claim 2.

Claim 3. $(\theta \times \theta)^{-1}(E_{QI}) \subset E_{K_\sigma}$.

To prove this assertion, take some $x = (x_n)$ and $y = (y_n)$ in $\prod_{n=2}^{\infty} \{1, \dots, n\}$ such that $(\theta(x), \theta(y)) \in E_{QI}$. Then, for some $C \ge 0$ and $\lambda \ge 1$, there are $C$-nets, $A \subset M$ and $B \subset M(y)$ with $P_{x,2}^+ \in A$ and $P_{y,2}^+ \in B$, and there is a pointed $\lambda$-bi-Lipschitz bijection $\phi : (A, P_{x,2}^+) \to (B, P_{y,2}^+)$.

Claim 4. If $e^{n^2} \ge C$, $\frac{1}{n}e^{2n+1} > \lambda$ and $e^{(n+2)^2-(n+1)^2} > 3\lambda$, then $\phi(M_{x,n} \cap A) \subset M_{y,n}$.
Assume the conditions of this claim. Then $A \cap M_{x,m} \neq \emptyset$ for all $m \ge n$ by (2). Furthermore, for $2 \le k < \ell \le n$,

$$d_y(\phi(M_{x,n} \cap A), \phi(M_{x,n+1} \cap A)) \ge \frac{1}{\lambda} d_x(M_{x,n} \cap A, M_{x,n+1} \cap A)$$

$$> \frac{1}{\lambda} e^{(n+1)^2} > ne^{(n+1)^2-2n-1} = ne^{n^2} \ge 2e^n + \sum_{i=3}^{n} e^{i^2}$$

$$\ge e^{y_k} + \sum_{i=k+1}^{\ell} e^{i^2} + e^{y_\ell} = d_y(P', Q')$$

for all $P' \in M_{y,k}$ and $Q' \in M_{y,\ell}$. On the other hand, for $2 \le k < \ell$ with $\ell \ge n+2$,

$$d_y(\phi(P), \phi(Q)) \le \lambda d_x(M_{x,n} \cap A, M_{x,n+1} \cap A)$$

$$< \lambda(e^{(n+1)^2} + 2e^{n+1}) < \lambda 3e^{(n+1)^2} < e^{(n+2)^2} \le e^{\ell^2}$$

$$< e^{y_k} + \sum_{i=k+1}^{\ell} e^{i^2} + e^{y_\ell} = d_y(M_{y,k}, M_{y,\ell}).$$

for all $P \in M_{x,n} \cap A$ and $Q \in M_{x,n+1} \cap A$. Therefore, either

$$\phi(M_{x,n} \cap A) \subset M_{y,n} \quad \& \quad \phi(M_{x,n+1} \cap A) \subset M_{y,n+1}, \quad (4)$$

or

$$\phi((M_{x,n} \cup M_{x,n+1}) \cap A) \subset M_{y,m} \quad (5)$$

for some $m$. In the case (5), we have

$$2e^m = d_y(\phi(M_{x,n} \cap A), \phi(M_{x,n+1} \cap A))$$

$$\ge \frac{1}{\lambda} d_x(M_{x,n} \cap A, M_{x,n+1} \cap A) > e^{(n+1)^2}/\lambda,$$

giving $m > (n+1)^2 - \ln(2\lambda)$. Applying this to $n+1$ and $n+2$, we get that, either

$$\phi(M_{x,n+1} \cap A) \subset M_{y,n+1} \quad \& \quad \phi(M_{x,n+2} \cap A) \subset M_{y,n+2}, \quad (6)$$

or

$$\phi((M_{x,n+1} \cup M_{x,n+2}) \cap A) \subset M_{y,m'} \quad (7)$$

for some $m' > (n+2)^2 - \ln(2\lambda)$. If (5) and (7) hold, then $m = m'$ and

$$\phi((M_{x,n} \cup M_{x,n+1} \cup M_{x,n+2}) \cap A) \subset M_{y,m},$$

which is a contradiction because $\phi$ is a bijection whereas

$$\#((M_{x,n} \cup M_{x,n+1} \cup M_{x,n+2}) \cap A) \ge 3 > 2 = \#M_{y,m}.$$

If (5) and (6) hold, then $n+1 = m > (n+1)^2 - \ln(2\lambda)$, which contradicts the condition $e^{(n+2)^2-(n+1)^2} > 3\lambda$. So (4) must be true, showing Claim 4.

From Claim 4, it easily follows that

$$\phi(M_{x,n} \cap A) = M_{y,n} \cap B \quad (8)$$
for $n$ large enough. Suppose first that $M_{x,n} \subset A$ for such an $n$, and therefore $M_{y,n} \subset B$ by (8). Thus

$$2e^{y_n} = d_y(P_{y,n}^{+}, P_{y,n}^{-}) = d_y(\phi(P_{x,n}^{+}), \phi(P_{x,n}^{-})) \geq \frac{1}{\lambda} d_x(P_{x,n}^{+}, P_{x,n}^{-}) = \frac{2e^{x_n}}{\lambda},$$

giving $y_n \geq x_n - \ln \lambda$. Similarly, $y_n \leq x_n + \ln \lambda$, obtaining $|x_n - y_n| \leq \ln \lambda$.

Now, assume that $M_{x,n} \not\subset A$ for such an $n$; in particular, $C > 0$. Then $M_{y,n} \not\subset B$ by (8). So $e^{x_n}, e^{y_n} \leq C/2$ by (3), giving $x_n, y_n \leq \ln(C/2)$, and therefore $|x_n - y_n| \leq \ln(C/2)$.

Hence $|x_n - y_n| \leq \max\{\ln \lambda, \ln(C/2)\}$ for all $n$ large enough, and therefore $\sup_n |x_n - y_n| < \infty$, obtaining that $(x, y) \in E_{K_\sigma}$. This completes the proof of Claim 3.

Claims 1, 2 and 3 show that $\theta$ realizes the reduction $E_{K_\sigma} \leq_c E_{QI}$.

A similar argument with a slight modification of the definition of $M(x)$, using $P_{x,n}^{\pm} = (\sum_{i=2}^n e^{i^2}, \pm x_n)$, shows that $E_{K_\sigma} \leq_B E_{GH}$. $\square$

**Remark 1.** In Claim 1, $\theta$ is in fact a topological embedding, as shows the following argument. First, let us prove that $\theta$ is injective. Suppose that $\theta(x) = \theta(y)$ for some $x = (x_n)$ and $y = (y_n)$ in $\prod_{n=2}^\infty \{1, \dots, n\}$. This means that there is a pointed isometry $\phi : (M_x P_{x,2}^+) \to (M_y, P_{y,2}^+)$. We get $\phi(M_{x,n}) = M_{y,n}$ for all $n \geq 2$ by Claim 4 with $A = M_x, B = M_y, C = 0$ and $\lambda = 1$; in fact, the argument can be simplified in this case. Hence, for each $n \geq 2$,

$$2e^{x_n} = d_x(P_{x,n}^{+}, P_{x,n}^{-}) = d_y(\phi(P_{x,n}^{+}), \phi(P_{x,n}^{-})) = d_y(P_{y,n}^{+}, P_{y,n}^{-}) = 2e^{y_n},$$

giving $x_n = y_n$. Thus $x = y$.

Finally, let us prove that $\phi^{-1} : \phi(\prod_{n=2}^\infty \{1, \dots, n\}) \to \prod_{n=2}^\infty \{1, \dots, n\}$ is continuous at $\phi(x)$ for every $x = (x_n) \in \prod_{n=2}^\infty \{1, \dots, n\}$. With the notation of the proof of Claim 1, we have to check that, for all $n_0 \geq 2$, there is some $R, r > 0$ so that $\phi^{-1}(U_{R,r}(\theta(x))) \subset \mathcal{N}(x, n_0)$. Let $y = (y_n) \in \prod_{n=2}^\infty \{1, \dots, n\}$ such that $\theta(y) \in U_{R,r}(\theta(x))$ for some $R, r > 0$ to be determined later. Then there is a metric $d'$ on $M_x \cup M_y$, extending $d_x$ and $d_y$, such that $d'(P_{x,2}^+, P_{y,2}^+) < r$ and $H_{d',R}(M_x, P_{x,2}^+; M_y, P_{y,2}^+) < r$. Since $e^n < e^{(n+1)^2}$ for all $n \geq 2$, we can take $R$ such that

$$e^2 + \sum_{i=2}^{n_0} e^{i^2} + e^{n_0} < R < e^2 + \sum_{i=2}^{n_0+1} e^{i^2},$$

and therefore $B_{M_x}(P_{x,2}^+, R) = \bigcup_{n=2}^{n_0} M_{x,n}$ and $B_{M_y}(P_{y,2}^+, R) = \bigcup_{n=2}^{n_0} M_{y,n}$. So, for each $P_{x,n}^{\pm}$ with $2 \leq n \leq n_0$, there is some $\hat{P}_{x,n}^{\pm} \in M_y$ such that $d(P_{x,n}^{\pm}, \hat{P}_{x,n}^{\pm}) < r$; in particular, we can take $\hat{P}_{x,2}^{\pm} = P_{y,2}^{\pm}$. Let $\hat{M}_{x,n} = \{\hat{P}_{x,n}^{+}, \hat{P}_{x,n}^{-}\}$ for $2 \leq n \leq n_0$. Choose $r$ such that $r < 1$ and $e^n + r < e^{(n+1)^2}$ for $2 \leq n \leq n_0$. So $\hat{M}_{x,n} = M_{y,n}$ for $2 \leq n \leq n_0$. Then, by the triangle inequality,

$$2e^{x_n} = d_x(P_{x,n}^{+}, P_{x,n}^{-}) \leq d_y(\hat{P}_{x,n}^{+}, \hat{P}_{x,n}^{-}) + 2r \\ = d_y(P_{y,n}^{+}, P_{y,n}^{-}) + 2r = 2e^{y_n} + 2r,$$
giving $e^{x_n} \le e^{y_n} + r$. Similarly, we get $e^{x_n} \ge e^{y_n} - r$. Thus $|e^{x_n} - e^{y_n}| \le r$, obtaining $x_n = y_n$ because $r < 1$. Therefore $y \in \mathcal{N}(x, n_0)$, as desired.

*Remark 2.* According to Claim 2, the map $\theta$ of the proof of Proposition 4.1 also gives the reduction $E_{K_\sigma} \le_c E_{\mathrm{Lip}}$. An analogous property is satisfied with another point of view: considering Polish metric spaces as the elements of the space of closed subspaces of some universal Polish metric space, like the Urysohn space, the relation given by the existence of bi-Lipschitz bijections is Borel bi-reducible with $E_{K_\sigma}$ [9, Theorem 24].

## REFERENCES

[1] J.A. Álvarez López and A. Candel, *Turbulent relations*, preprint arXiv:1209.0307 [math.LO].

[2] S. Gao, *Invariant descriptive set theory*, Pure and Applied Mathematics (Boca Raton), vol. 293, CRC Press, Boca Raton, FL, 2009. MR 2455198 (2011b:03001)

[3] M. Gromov, *Groups of polynomial growth and expanding maps*. Appendix by Jacques Tsits, *Inst. Hautes Études Sci. Publ. Math*. (1981), no. 53, 53–73. MR 623534 (83b:53041)

[4] —, *Metric structures for Riemannian and non-Riemannian spaces*, Progress in Mathematics, vol. 152, Birkhäuser Boston Inc., Boston, MA, 1999, Based on the 1981 French original [MR0682063 (85e:53051)], With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates. MR 1699320 (2000d:53065)

[5] G. Hjorth, *Classification and orbit equivalence relations*, Mathematical Surveys and Monographs, vol. 75, American Mathematical Society, Providence, RI, 2000. MR 1725642 (2000k:03097)

[6] —, *A dichotomy theorem for turbulence*, J. Symbolic Logic **67** (2002), no. 4, 1520–1540. MR 1955250 (2004b:03069)

[7] A.S. Kechris and A. Louveau, *The classification of hypersmooth Borel equivalence relations*, J. Amer. Math. Soc. **10** (1997), no. 1, 215–242. MR 1396895 (97e:03067)

[8] P. Petersen, *Riemannian geometry*, Graduate Texts in Mathematics, vol. 171, Springer-Verlag, New York, 1998. MR 1480173 (98m:53001)

[9] C. Rosendal, *Cofinal families of Borel equivalence relations and quasiorders*, J. Symbolic Logic **70** (2005), 1325–1340. MR 2194249 (2006i:03074)

DEPARTAMENTO DE XEOMETRÍA E TOPOLOXÍA, FACULTADE DE MATEMÁTICAS, UNIVERSIDADE DE SANTIAGO DE COMPOSTELA, 15782 SANTIAGO DE COMPOSTELA, SPAIN

E-mail address: jesus.alvarez@usc.es

DEPARTMENT OF MATHEMATICS, CALIFORNIA STATE UNIVERSITY AT NORTHRIDGE, 18111 NORDHOFF STREET, NORTHRIDGE, CA 91330, U.S.A.

E-mail address: alberto.candel@csun.edu