# Quantitative questions about the size of a finite epsilon net

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

-

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

-
Well, at the moment I can only give you a reference to the old survey by Kolmogorov and Tikhomirov mathnet.ru/php/… It's in Russian though and I don't know if an English translation exists. I will update my answer as soon as find a good relevant reference. The keywords are "Kolmogorov epsilon entropy" and "metric entropy". – Andrey Rekalo May 12 '10 at 18:03
Thanks for the response. – weakstar May 12 '10 at 18:05
How about another self-promotional plug? Selection 17 in CLASSICS ON FRACTALS is a translation into English of an exerpt of that very paper of Kolmogorov and Tihomirov ... – Gerald Edgar May 12 '10 at 18:39
@Gerald Edgar: Thank you. I knew I should have paid more attention to the literature on fractals... – Andrey Rekalo May 12 '10 at 18:59
@Gerald Edgar. Thanks! – weakstar May 12 '10 at 19:07

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

-
self-promotional plug ... math.ohio-state.edu/~edgar/books/mtfg.html – Gerald Edgar May 12 '10 at 15:21