Question

What is the distance in the sense of Gromov-Hausdorff between $\mathbb{Z}_{p_1}$ and $\mathbb{Z}_{p_2}$ with the usual p-adic metrics? I got stuck and simply have no idea how to deal with such questions: I've got two metric trees and have to observe somehow all embeddings to all spaces which seems a bit intractable.

Answer 1

The Gromov--Hausdorff distance is good only to define topology; i.e., one should not care about distance between particular spaces. But since you insist, I will answer an easier question which is closely related.

There is a modified distance $d'_{GH}(X,Y)$ defined as infimum of all numbers $\varepsilon>0$ such that there are maps $f_1\colon X\to Y$ and $f_2\colon Y\to X$ such that $$|f_i(x)-f_i(y)|\ge |x-y|-\varepsilon.$$

This distance $d^\prime_{GH}$ is equivalent to $d_{GH}$ and it is usually easier to find value $d^\prime_{GH}$

If $ p < q < p^2$ then it is easy to see that

$$ d^\prime_{GH} ( \mathbb Z_{p},\mathbb Z_{q}) = \tfrac{p-1}{p}. $$ Further, if $ p^2 < q < p^3$ then

$$ d^\prime_{GH} ( \mathbb Z_{p},\mathbb Z_{q}) = \tfrac{p^2-1}{p^2}$$ and so on.

Answer 2

My guess is that covering numbers will give you fairly accurate lower bounds on the Gromov-Hausdorff distance. If a space $X$ can be covered by $k$ balls of radius $r$, but a space $Y$ cannot be covered by $k$ balls of radius $R$, then the Gromov-Hausdorff distance between the two spaces has to be at least $(R-r)/2$. The covering numbers for the p-adics can be explicitly computed, so one should be able to work out explicit lower bounds this way. Conversely, once one finds a scale r at which $X$ and $Y$ have similar covering behaviour, it should be possible (especially given the ultrametric (tree) structure of both spaces) to find a way to move elements of X to elements of Y and vice versa while distorting the metric by at most O(r), so one should get an upper bound comparable to the lower bound.

Answer 3

I hope you get a much better answer than the following - there must be an established body of techniques for computing GH distances. (Edit: see this MO question.)The following is very elementary, but given the "where do I start?" tone of your question, maybe it's not completely useless.

First, you don't have to think about "all embeddings to all spaces". To compute the GH distance between spaces $X$ and $Y$, you only need to think about all metrics on the disjoint union $X \amalg Y$ that extend the given metrics on $X$ and $Y$. (This is probably proved in almost every text in which the GH metric is defined.) Given any such metric on $X \amalg Y$, you can take the Hausdorff distance between $X$ and $Y$. The GH distance between $X$ and $Y$ is the inf of all Hausdorff distances arising in this way.

So, for instance, it's easy to show that $d_{GH}(\mathbb{Z}_{p_1}, \mathbb{Z}_{p_2}) \leq 1$. For this, all we need to know about $\mathbb{Z}_{p_1}$ and $\mathbb{Z}_{p_2}$ is that they each have diameter $\leq 1$. Indeed, let $X$ and $Y$ be metric spaces of diameter $\leq 1$. Extend the metrics on $X$ and $Y$ to a metric on $X \amalg Y$ by taking $d(x, y) = 1/2$ for all $x \in X$ and $y \in Y$. With this metric, $X \amalg Y$ has diameter $\leq 1$, so the Hausdorff distance between any two subsets is $\leq 1$. In particular, the Hausdorff distance between the subsets $X$ and $Y$ is $\leq 1$. So $d_{GH}(X, Y) \leq 1$.

(Sorry if you already knew all that. It's hard to tell from your question how much you know. If you did already know what I wrote, maybe it would be useful to edit your question to tell us how far you've got in this problem: e.g. what upper and lower bounds do you have?)