My reference is the text surrounding Lemma $5.2$ in Introduction to the non-asymptotic analysis of random matrices by Roman Vershynin.
Definition. Let $(X, d)$ be a metric space and let $\varepsilon>0$. A subset $\mathcal{N}_{\varepsilon}$ of $X$ is called an $\varepsilon$-net of $X$ if every point $x \in X$ can be approximated to within $\varepsilon$ by some point $y \in \mathcal{N}_{\varepsilon}$, i.e. so that $d(x, y) \leq \varepsilon$. The minimal cardinality of an $\varepsilon$-net of $X$, if finite, is denoted $\mathcal{N}(X, \varepsilon)$ and is called the covering number of $X$ (at scale $\varepsilon)$. Equivalently, $\mathcal{N}(X, \varepsilon)$ is the minimal number of balls with radii $\varepsilon$ and with centers in $X$ needed to cover $X$.
- Suppose we have an $\varepsilon$-net that covers $X$ in the optimal way, i.e., the number of balls used is $\mathcal{N}(X, \varepsilon)$. Are these balls always disjoint? I don't think so.
The following is the text of the main lemma, concerning covering numbers of the sphere.
Lemma $5.2$ (Covering numbers of the sphere). The unit Euclidean sphere $S^{n-1}$ equipped with the Euclidean metric satisfies for every $\varepsilon>0$ that
$$
\mathcal{N}\left(S^{n-1}, \varepsilon\right) \leq\left(1+\frac{2}{\varepsilon}\right)^n
$$
Proof. This is a simple volume argument. Let us fix $\varepsilon>0$ and choose $\mathcal{N}_{\varepsilon}$ to be a maximal $\varepsilon$-separated subset of $S^{n-1}$. In other words, $\mathcal{N}_{\varepsilon}$ is such that $d(x, y) \geq \varepsilon$ for all $x, y \in \mathcal{N}_{\varepsilon}$, $x \neq y$, and no subset of $S^{n-1}$ containing $\mathcal{N}_{\varepsilon}$ has this property. One can in fact construct $\mathcal{N}_{\varepsilon}$ inductively by first selecting an arbitrary point on the sphere, and at each next step selecting a point that is at distance at least ${\varepsilon}$ from those already selected. By compactness, this algorithm will terminate after finitely many steps and it will yield a set $\mathcal{N}_{\varepsilon}$ as we required.
- How does compactness imply the algorithm's termination in finitely many steps?
The maximality property implies that $\mathcal{N}_{\varepsilon}$ is an $\varepsilon$-net of $S^{n-1}$. Indeed, otherwise there would exist $x \in S^{n-1}$ that is at least $\varepsilon$-far from all points in $\mathcal{N}_{\varepsilon}$. So $\mathcal{N}_{\varepsilon} \cup\{x\}$ would still be an $\varepsilon$-separated set, contradicting the maximality property.
Moreover, the separation property implies via the triangle inequality that the balls of radii $\varepsilon / 2$ centered at the points in $\mathcal{N}_{\varepsilon}$ are disjoint. On the other hand, all such balls lie in $(1+\varepsilon / 2) B_2^n$ where $B_2^n$ denotes the unit Euclidean ball centered at the origin. Comparing the volume gives $\operatorname{vol}\left(\frac{\varepsilon}{2} B_2^n\right) \cdot\left|\mathcal{N}_{\varepsilon}\right| \leq \operatorname{vol}\left(\left(1+\frac{\varepsilon}{2}\right) B_2^n\right)$. Since $\operatorname{vol}\left(r B_2^n\right)=r^n \operatorname{vol}\left(B_2^n\right)$ for all $r \geq 0$, we conclude that $\left|\mathcal{N}_{\varepsilon}\right| \leq\left(1+\frac{\varepsilon}{2}\right)^n /\left(\frac{\varepsilon}{2}\right)^n=\left(1+\frac{2}{\varepsilon}\right)^n$ as required.
-
This is probably straightforward, but I want to make sure I have the details correct. The conclusion follows from $\mathcal{N}(X, \varepsilon) \le \left|\mathcal{N}_{\varepsilon}\right| \leq\left(1+\frac{\varepsilon}{2}\right)^n /\left(\frac{\varepsilon}{2}\right)^n=\left(1+\frac{2}{\varepsilon}\right)^n$, right? I ask because $\mathcal{N}(X, \varepsilon) < \left|\mathcal{N}_{\varepsilon}\right|$ is a possibility.
-
Wouldn't the same proof work for $B^n_2$ also? I don't see why anything would change. I believe $\mathcal{N}\left(B^n_2, \varepsilon\right) \leq\left(1+\frac{2}{\varepsilon}\right)^n$ is also correct.
Thanks for your thoughts and help!
Best Answer
The balls are closed, so if $X$ is connected and covered by finitely many and at least two balls then the balls cannot be pairwise disjoint.
Otherwise we construct an infinite $\varepsilon$-separated set, which cannot be contained in a compact metric space.
Right.
Right, the similar proof works for $B_2^n$ too.