# Do strongly equivalent metrics have the same covering numbers?

Let $$(X,d)$$ be a metric space. Then for any $$r>0$$, the $$r$$-covering number of $$X$$ is the minimum number of open balls of radius $$r$$ needed to cover $$X$$. And if $$d_1$$ and $$d_2$$ be two metrics on the same set $$X$$, then $$d_1$$ and $$d_2$$ are called strongly equivalent if there exist constants $$\alpha,\beta>0$$ such that $$\alpha d_1(x,y)\leq d_2(x,y)\leq\beta d_1(x,y)$$ for all $$x,y\in X$$.

My question is, if two metrics are strongly equivalent, then do they have the same $$r$$-covering number for all $$r>0$$? If not, do they at least have the same box dimension?

• Do you allow $r = \infty$? And what is the box dimension? – Paul Frost Dec 25 '18 at 11:31
• @PaulFrost No, infinity is not allowed. Here is what box dimension is: en.wikipedia.org/wiki/Minkowski–Bouligand_dimension In any case, I found the answer to that part of my question here: math.stackexchange.com/a/964025/71829 – Keshav Srinivasan Dec 25 '18 at 15:09
• So you only consider totally bounded metric spaces. – Paul Frost Dec 25 '18 at 15:13
• @PaulFrost What gave you that idea? – Keshav Srinivasan Dec 25 '18 at 15:13
• Two of my comments are nonsense. What I wanted to ask is this. If $n(r)$ is the $r$-covering number of $X$, do you allow $n(r) = \infty$? Only if you do not, my comment concerning totally bounded metric spaces makes sense. – Paul Frost Dec 26 '18 at 9:06

Let $$X = [0,2]$$ with the usual metric $$d(x,y) = \lvert x - y \rvert$$. Then the $$1$$-covering number is $$2$$.

Define $$d'(x,y) = \min(1/2,d(x,y))$$. This is a metric such that $$d'(x,y) \le d(x,y) \le 4 d'(x,y) .$$ (If $$d(x,y) \le 1/2$$, then $$d(x,y) = d'(x,y)$$, otherwise $$d(x,y) \le 2 = 4 \cdot 1/2 = 4 d'(x,y)$$.)

Its $$1$$-covering number is $$1$$.

Edited:

Here is a more general answer.

Let $$n(r) = n(r,d)$$ denote the $$r$$-covering number of $$X$$. If the metric $$d$$ is unbounded (i.e. $$diam(X,d) = \sup_{x,y \in X} d(x,y) = \infty$$), then all $$n(r) = \infty$$.

Let $$d,d'$$ be strongly equivalent.

(1) $$d$$ is bounded if and only idf $$d'$$ is bounded.

This is obvious.

(2) If $$d$$ is unbounded, then $$n(r,d) = n(r,d') = \infty$$ for all $$r$$.

This is again obviuos.

(3) If $$d$$ is bounded, then there exists a metric $$d'$$ strongly equivalent to $$d$$ and $$r$$ such that $$n(r,d) > n(r,d') = 1$$.

Let $$\rho = diam(X,d)$$. Define $$d'(x,y) = \min(\rho /4, d(x,y))$$. This is a metric such that $$d'(x,y) \le d(x,y) \le 4 d'(x,y) .$$ (If $$d(x,y) \le \rho /4$$, then $$d(x,y) = d'(x,y)$$, otherwise $$d(x,y) \le \rho = 4 \cdot \rho /4 = 4 d'(x,y)$$.)

Let $$\rho/4 < r < \rho/2$$.

Then $$n(r,d) > 1$$ because a single open ball of radius $$r$$ cannot cover $$X$$ (Assume $$B(x,r) = X$$ for some $$x \in X$$. Then for all $$y,z \in X$$ one has $$d(y,z) \le d(y,x) + d(y,z) < 2r$$, hence $$diam(X,d) \le 2r < \rho$$.)

On the other hand $$n(r,d') = 1$$. For any $$x \in X$$ we have $$B(r,d') = X$$ because for any $$y \in Y$$ we have $$d'(x,y) \le \rho/4 < r$$.