This post describes the notions of \(\varepsilon\)-entropy and \(\varepsilon\)-capacity.
Let \((X,d)\) be a metric space. The (open) \(\varepsilon\)-ball \(\mathcal{B}_\varepsilon(x)\) centered at \(x\) is defined by
\[ \mathcal{B}_\varepsilon(x) := \{y \in X : d(x,y) < \varepsilon\}. \]
Let \(S \subset X\), and let \(\varepsilon > 0\). We now introduce the notions of \(\varepsilon\)-covering and \(\varepsilon\)-packing.
Definition (\(\varepsilon\)-covering).
A set \(A \subset S\) is said to be an \(\varepsilon\)-covering of \(S\) if
\[ S \subset \bigcup_{x \in A} \mathcal{B}_\varepsilon(x) \subset X. \]
Definition (\(\varepsilon\)-packing).
A set \(A \subset S\) is said to be an \(\varepsilon\)-packing of \(S\) if
\[ \bigcup_{x \in A} \mathcal{B}_\varepsilon(x) \subset S \quad \text{and} \quad \bigcap_{x \in A} \mathcal{B}_\varepsilon(x) = \emptyset. \]
Roughly speaking, an \(\varepsilon\)-covering of \(S\) is a collection of \(\varepsilon\)-balls which covers \(S\), and an \(\varepsilon\)-packing of \(S\) is a collection of \(\varepsilon\)-balls which are disjoint from each other. Note that the definitions are slightly different depending on the context.
The minimal cardinality of \(\varepsilon\)-coverings of \(S\) is denoted by \(N(S,\varepsilon)\).
Definition (\(\varepsilon\)-entropy).
The \(\varepsilon\)-entropy of \(S\) is the number \(\log_2 N(S,\varepsilon)\).
The maximal cardinality of \(\varepsilon\)-packings of \(S\) is denoted by \(M(S,\varepsilon)\).
Definition (\(\varepsilon\)-capacity).
The \(\varepsilon\)-capacity of \(S\) is the number \(\log_2 M(S,\varepsilon)\).