Quantitative questions about the size of a finite epsilon net

Question

Let $X$ be a metric space, and let $U \subset X$ be any set. A finite set $N = N(\epsilon) \subset U$ is called a finite $\epsilon$-net of $U$ if every point of $U$ is at most a distance of $\epsilon$ from some point of $N$.

It is easy to show that if $U$ is compact, then for any $\epsilon>0$, a finite $\epsilon$-net exists. I am interested in the behavior of the function $|N(\epsilon)|$ as $\epsilon$ goes to zero. If there are answers in this generality, great. I am mostly interested in the particular case where $U$ is also convex, and where $X$ is also an infinite dimensional topological vector space, but any answers are of course welcome.

Edit: I'm also interested in weakening the notion of $\epsilon$-net, so instead of requiring every point of $U$ to be close to a point in $N$, we could require every point of $U$ to be close to a point in the convex hull of $N$. The motivation for this comes from looking at objects which are "convexly compact"; this means (in a metric space) that given any sequence $(f_n)$ in $U$, there exist $g_j \in \text{conv}(f_j,f_{j+1},\ldots)$ such that $g_j \rightarrow g$ in $U$.

Answer 1

This is a huge subject. The minimum sizes of $\epsilon$-nets of compacts in linear spaces were studied by Kolmogorov and his school. They showed that in general there are no good bounds for this quantity for convex compacts in infinite-dimensional Banach spaces. However, reasonable estimates can be obtained in some interesting specific cases.

Let $|N_\epsilon(U)|$ be the minimum size of an $\epsilon$-net for the set $U$. The value $\mathcal N_\epsilon(U)=\log_2 |N_\epsilon(U)|$ is called the $\epsilon$-entropy of the set $U$.

The following results are due to Kolmogorov and Tikhomirov.

Theorem 1. Let $\phi(\epsilon)$ goes to $+\infty$ (and monotonically increases) as $\epsilon\to 0$. Assume that $X$ is an infinite-dimensional Banach space. Then there is a compact $K\subset X$ such that $$ \mathcal N_\epsilon(K)\succeq\phi(\epsilon).$$

Theorem 2. Assume that $X$ is an infinite-dimensional Banach space. Let $K\subset X$ be a convex set which is not contained in any finite-dimensional subspace of $X$. Then $$ \mathcal N_\epsilon(K)\succeq\left(\frac{1}{\epsilon}\right)^n$$ for any $n\in \mathbb N$.

Answer 2

The question of box dimension or Bouligand dimension or Minkowski dimension is related to this. Write $M(\epsilon)$, say, for the minimum size of an $\epsilon$-net. Then $$ D = \limsup_{\epsilon \to 0}\frac{\log M(\epsilon)}{\log(1/\epsilon)} $$ is the upper box dimension of $U$ (or Bouligand dimension or Minkowski dimension, etc.). Thus, for any $S\gt D$ we have $M(\epsilon) \lt (1/\epsilon)^S$ for all small $\epsilon$; for any $S\lt D$ we have $M(\epsilon) \gt (1/\epsilon)^S$ for frequent small $\epsilon$.

Use liminf for lower box dimension