Covering number

Not to be confused with Winding number or degree of a continuous mapping, sometimes called "covering number" or "engulfing 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^{\text{pack}}_\varepsilon(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^{\text{int}}_\varepsilon(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^{\text{ext}}_\varepsilon(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^{\text{met}}_\varepsilon(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)\ge \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$ .^[1]

$\displaystyle N^{\text{met}}_{2\varepsilon}(K) \leq N^{\text{pack}}_\varepsilon(K) \leq N^{\text{ext}}_\varepsilon(K) \leq N^{\text{int}}_\varepsilon(K) \leq N^{\text{met}}_\varepsilon(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}$ .

References

↑ Tao, Terrance. "Metric entropy analogues of sum set theory". Retrieved 2 June 2014.