# Gromov-Hausdorff distance between p-adic integers.

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.

-
You might want to look at Cornelia Drutu's survey article in IJAC Volume 12, Number 1-2, February & April 2002. She computes the Gromov Hausdorff distance between $\mathbb R$ and a circle, I believe. One trick is that if both your spaces are homogeneous, as is the case for your spaces, then you can use the based version of the Gromov-Hausdorff distance. That is look at both spaces as based at 0 and start looking for the largest neighborhoods of 0 that look like each other. –  Benjamin Steinberg Dec 1 '11 at 19:48
the distance between $\mathbb R$ and the circle is obviously infinite because $\mathbb R$ has infinite diameter and the circle has finite diameter. –  Vitali Kapovitch Dec 1 '11 at 22:51
That's not what she gets, see google.com/… The point is neighborhoods of the origin in $\mathbb R$ look like neighborhoods of the identity in the circle if we don't go too far out. Here she looks at circles of any radius with the length metric. –  Benjamin Steinberg Dec 1 '11 at 23:02
ok, I looked at the paper and she is looking at a modified Gromov-Hausdorff distance (her definition is a rather nonstandard btw) which is basically the best pointed Gromov-Haudorff aproximation between large balls around all possible base points. It's somewhat different from the classical Gromov-Hausdorff distance which is certainly infinite between any two spaces where one has finite and the other infinite diameter –  Vitali Kapovitch Dec 1 '11 at 23:36
Ah, my bad. I should have looked closer. –  Benjamin Steinberg Dec 2 '11 at 1:41

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.

-
Not that I'm disagreeing, but do you have any particular justification for your first sentence? –  Mark Meckes Dec 2 '11 at 14:29
I'd like to ask the same question as Mark. I was thinking that diameter is reasonably important and is a special case of GH distance: the diameter of a metric space is twice its GH distance from the one-point space. –  Tom Leinster Dec 2 '11 at 15:54
The justification comes from practice: The only application of GH-metric (which I know) is to define GH-convergence and GH-convergence has many applications. –  Anton Petrunin Dec 2 '11 at 17:57
I think the GH distance is of great importance, but applications (other than concerning convergence) are hard to find because is so difficult to estimate it. Indeed, with Anton definition of the GH distance, it represents the best accuracy one can have of a map of the space X into the space Y. –  Marius Buliga Dec 3 '11 at 9:50

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.

-
Many thanks, Terry, that was helpful. As Anton noticed what is important in G-H is convergence issues, not the metric per se, so this covering-bound-techniques is what I will need in real life I guess. –  Dmitry K Dec 2 '11 at 17:54
Lower bounds on GH distance are harder to obtain than upper bounds, so this covering argument may be useful for other situations as well. –  Marius Buliga Dec 3 '11 at 9:55

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?)

-
I am missing something. Didn't you just prove that the GH distance between two spaces of diameter 1 is at most 1/2 ? –  Joël Dec 1 '11 at 19:42
Tom, thank you for your answer, thinking about disjoint union as an ambient space is much more comfortable. You are right it's a "where to start" type of question, I know next to nothing behind the definition. and +1 to Joël's remark, your argument don't use the metric structure of $\mathbb{Z}_p$ so it holds for any pair of bounded spaces. The lower bound is less clear, it seems that it is also 1 for $p1\neq p2$ (the maximal distance) but I don't now how to prove it. –  Dmitry K Dec 1 '11 at 20:07
Joël: yes, looks like it. –  Tom Leinster Dec 2 '11 at 15:55