# Covering number

Jump to navigation Jump to search

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 ${\displaystyle K}$ of a metric space ${\displaystyle (X,d)}$ and a parameter ${\displaystyle \varepsilon >0}$. Denote the ball of radius ${\displaystyle \varepsilon }$ centered at the point ${\displaystyle x\in X}$ by ${\displaystyle B_{\varepsilon }(x)}$. There are two notions of covering number, internal and external, along with the packing number and the metric entropy.

## 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 ${\displaystyle \varepsilon >0}$.[1]

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