Covering number

In mathematics, the idea of a covering number is to count how many small spherical balls would be needed to completely cover (with overlap) a given space. There are two closely related concepts as well, the packing number, which counts how many disjoint balls fit in a space, and the metric entropy, which counts how many points fit in a space when constrained to lie at some fixed minimum distance apart.

Mathematical Definition

More precisely, consider a subset $K$ of a metric space $(X,d)$ and a parameter $\varepsilon >0$. Denote the ball of radius $\varepsilon$ centered at the point $x\in X$ by $B_{\varepsilon }(x)$. There are two notions of covering number, internal and external, along with the packing number and the metric entropy.

• The packing number $N_{\varepsilon }^{\text{pack}}(K)$ is the largest number of points $x_{i}\in K$ such that the balls $B_{\varepsilon }(x_{i})$ fit within K and are pairwise disjoint.
• The internal covering number $N_{\varepsilon }^{\text{int}}(K)$ is the fewest number of points $x_{i}\in K$ such that the balls $B_{\varepsilon }(x_{i})$ cover $K$.
• The external covering number $N_{\varepsilon }^{\text{ext}}(K)$ is the fewest number of points $x_{i}\in X$ such that the balls $B_{\varepsilon }(x_{i})$ cover $K$.
• The metric entropy $N_{\varepsilon }^{\text{met}}(K)$ is the largest number of points $x_{i}\in K$ such that the points are $\varepsilon$-separated, i.e. $d(x_{i},x_{j})\geq \varepsilon$ for all $i\neq j$.

Inequalities and Monotonicity

The internal and external covering numbers, the packing number, and the metric entropy are all closely related. The following chain of inequalities holds for any $\varepsilon >0$.

$\displaystyle N_{2\varepsilon }^{\text{met}}(K)\leq N_{\varepsilon }^{\text{pack}}(K)\leq N_{\varepsilon }^{\text{ext}}(K)\leq N_{\varepsilon }^{\text{int}}(K)\leq N_{\varepsilon }^{\text{met}}(K)$

In addition, the quantities $N_{\varepsilon }^{*}(K)$ are non-increasing in $\varepsilon$ and non-decreasing in $K$ for each of $*={\text{pack}},{\text{ext}},{\text{met}}$. However, monotonicity in $K$ can in general fail for $*={\text{int}}$.