# Asymptotic bound on minimum epsilon cover of arbitrary manifolds

Let $$M \subset \mathbb{R}^d$$ be a compact smooth $$k$$-dimensional manifold embedded in $$\mathbb{R}^d$$. Let $$\mathcal{N}(\varepsilon)$$ denote the minimal cardinal of an $$\varepsilon$$-cover $$P$$ of $$M$$; that is for every point $$x \in M$$ there exists a $$p \in P$$ such that $$\| x - p\|_{2}<\varepsilon$$.

Is it the case that $$\mathcal{N}(\varepsilon) \in \Theta\left(\frac{1}{\varepsilon^k}\right)$$? If so, is there a reference?

It turns out that this statement can be rephrased as: The Minkowski-Bouligand dimension of $$M$$ is equal to $$k$$ (this is immediate from the definition). Another word for this is the box dimension, and we will write it as $$\mathrm{dim}_\mathrm{B}$$. Here's a proof sketch that $$\mathrm{dim}_\mathrm{B}(M^k)=k$$.

By the inverse function theorem and compactness, we can write $$M$$ as a collection of finitely many smooth graphs over its tangent spaces. More precisely, there exists a $$\rho>0$$, points $$x_1,\dotsc, x_N\in M$$, smooth functions $$u_1,\dotsc,u_N$$ with $$u_i:B_{\rho}(x_i)\cap T_{x_i}M\to\Bbb R^{d-k}$$ and $$\mathrm{Lip}(u_i)\le L$$ such that $$M=\bigcup_{i=1}^N\mathrm{graph}(u_i).$$ It suffices to check the claim for each graph.

So let $$B$$ now be the $$k$$-dimensional unit ball and $$u:B\to\Bbb R^{d-k}$$ a Lipschitz function. It is clear by considering grids of spacing $$\varepsilon$$ that $$\mathrm{dim}_\mathrm{B}(B)=k$$. Let $$\mathcal N_B(\varepsilon)$$ be the covering number of $$B$$. Then $$\mathcal N_{\mathrm{graph}(u)}(L\varepsilon)\le \mathcal N_B(\varepsilon)$$. Therefore, $$\mathrm{dim}_\mathrm{B}(\mathrm{graph}(u))\le \mathrm{dim}_\mathrm{B}(B).$$

For the other inequality, we may assume that our graphical parametrization is in fact bi-Lipschitz by making the original balls smaller (but still having finitely many). That is, we may assume that $$B_{\rho}(x_i)\cap T_{x_i}M$$ is a Lipschitz graph over a subset of $$B_{\rho}(x_i)\cap M$$. This gives $$\mathrm{dim}_\mathrm{B}(\mathrm{graph}(u))\ge \mathrm{dim}_\mathrm{B}(B)$$, which completes the proof.