For any metric space $X$ and $\varepsilon>0$, let $$\text{cov}(X,\varepsilon)=\min\{n\,|\,X\text{ has a cover by }n\text{ many closed }\varepsilon\text{-balls}\},$$

be the ordinary covering numbers. For any $D>0$ and $N:(0,\infty)\rightarrow \mathbb{N}$, let $$U(D,N)=\{X\,|\,X\text{ is a compact metric space, diam}(X)\leq D,\,\text{cov}(X,\varepsilon)\leq N(\varepsilon)\},$$

be the set of compact metric spaces with uniformly bounded diameter and covering numbers. Gromov's compactness theorem implies that $U(D,N)$ is totally bounded with respect to the Gromov-Hausdorff distance for any $D$ and $N$, so in particular $\text{cov}_{GH}(U(D,N),\varepsilon)$ is always finite.

Are there any known bounds on $\text{cov}_{GH}(U(D,N),\varepsilon)$ in terms of $N$ (everything clearly scales with $D$, so setting $D=1$ is sufficient)?


Given a metric space $X$ with $\operatorname{cov}(X,\epsilon) \leq N(\epsilon)$, there exist $N(\epsilon_1)$ points such that each point is within $\epsilon_1$ of each of them. That set of $N(\epsilon_1)$ points is itself a metric space $Y$, with Gromov-Hausdorff distance at most $\epsilon_1$ to $X$. That metric space is determined by ${N(\epsilon_1) \choose 2}$ real numbers at most $D$. If we adjust each of these real numbers by at most $2\epsilon_2$, forming a metric space $Y'$, that represents a move of at most $\epsilon_2$ in Gromov-Hausdorff distance, since we can put a metric on $Y \cup Y'$ where the distance between a point in $Y$ and a point in $Y'$ is the average between the distance of the corresponding points in $Y$ and the distance of the corresponding points in $Y'$, plus $\epsilon_2$.

Let $Y'$ be $Y$ with all the distances rounded up to the nearest positive integer multiple of $2\epsilon_2$. This rounding process preserves the triangle inequality, because $\lceil a+b \rceil \leq \lceil a\rceil + \lceil b\rceil$, so we always obtain a metric space of distance $\leq \epsilon_2$ for $y$. There are $ \left\lceil \frac{D}{2 \epsilon_2} \right\rceil $ possible choices for each distance, so there are at most $\left\lceil \frac{D}{2 \epsilon_2} \right\rceil^{{N(\epsilon_1) \choose 2}}$ possible metric spaces $Y'$. This gives an $\epsilon_1+\epsilon_2$ covering, so the number of $\epsilon$-coverings is at most $$\min_{\epsilon_1+\epsilon_2=\epsilon} \left\lceil \frac{D}{2 \epsilon_2} \right\rceil^{{N(\epsilon_1) \choose 2}}$$

  • $\begingroup$ Great. This might be a much tougher question but do you have any idea how tight the bound is? $\endgroup$ Dec 11 '16 at 17:46
  • $\begingroup$ @Exomnium It might be hard to give lower bounds without an explicit function $N$. Is there a particular class of functions you're interested in (e.g. power laws?) $\endgroup$
    – Will Sawin
    Dec 11 '16 at 18:14

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.