Covering number

• Definition
  • Let $(T, d)$ be a semi-metric space. For $\varepsilon > 0$, an $\varepsilon$-net of T is a subset $T_\varepsilon$ of $T$ such that for every $t ∈ T$ there exists a $t_\varepsilon ∈ T_\varepsilon$ with $d(t, t_\varepsilon) ≤ \varepsilon.$ The $\varepsilon$-covering number $N(T, d, \varepsilon)$ of $T$ is the infimum of the cardinality of $\varepsilon$-nets of $T$, that is, $$ N(T, d, \varepsilon) := \text{inf}\{\text{Card}(T_\varepsilon) : T_\varepsilon \text{ is an }\varepsilon \text{-net of } T\} $$ where $\text{inf } \emptyset = + \infty$ by convention.
• Related concept
  • Packing number
    For any semi-metric space $(T, d)$, a collection of points in $T$ is said to be $\varepsilon$-separated if the $d$-distance between each pair of points is greater than $\varepsilon$. The packing number $D(T, d, \varepsilon)$ is the maximum number of $\varepsilon$-separated points in $T$.
• Lemma
  • For every $\varepsilon > 0$, $$ N(T, d, \varepsilon) \leq D(T, d, \varepsilon) \leq N(T, d, \varepsilon / 2). $$