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?

  • $\begingroup$ Do you allow $r = \infty$? And what is the box dimension? $\endgroup$ – Paul Frost Dec 25 '18 at 11:31
  • $\begingroup$ @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 $\endgroup$ – Keshav Srinivasan Dec 25 '18 at 15:09
  • $\begingroup$ So you only consider totally bounded metric spaces. $\endgroup$ – Paul Frost Dec 25 '18 at 15:13
  • $\begingroup$ @PaulFrost What gave you that idea? $\endgroup$ – Keshav Srinivasan Dec 25 '18 at 15:13
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.


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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.