Covering, packing, bracketing numbers, and metric entropy

A pseudometric $d$ on a set $T$ is a nonnegative symmetric function $d:T\times T\to [0,\mathrm{\infty })$ with $d(t,t)=0$ and $d(s,t)\le d(s,u)+d(u,t)$; distinct points may have distance zero. For a nonempty subset $\mathcal{F}\subseteq T$ and $ϵ>0$, the covering number $N(ϵ,\mathcal{F},d)$ is the least finite $k$ for which there are centers $f_1,\dots ,f_k\in \mathcal{F}$ such that every $f\in \mathcal{F}$ satisfies $d(f,f_j)\le ϵ$ for some $j$. It is $+\mathrm{\infty }$ if no finite cover exists. Set $N(ϵ,\mathrm{\varnothing },d)=1$.

The packing number $D(ϵ,\mathcal{F},d)$ is the largest size of a finite subset $\{f_1,\dots ,f_k\}\subseteq \mathcal{F}$ whose distinct members have pairwise distance strictly greater than $ϵ$. If the sizes of such finite subsets are unbounded, put $D=+\mathrm{\infty }$; put $D(ϵ,\mathrm{\varnothing },d)=0$. These conventions give the radius comparison proved in Packing and covering numbers with explicit radius conventions ↗. The metric entropy is $H(ϵ,\mathcal{F},d):=\log N(ϵ,\mathcal{F},d)$ for nonempty classes, with $\log (+\mathrm{\infty })=+\mathrm{\infty }$.

For a probability measure $Q$ on $(\mathcal{X},\mathcal{A})$ and a measurable real function $g$, set $\mathrm{\parallel }g{\mathrm{\parallel }}_{Q,r}:=(\int \mathrm{\mid }g{\mathrm{\mid }}^{r}dQ{)}^{1\mathrm{/}r}$ for $1\le r<\mathrm{\infty }$ when the integral is finite, using the real-power convention, including $0^{1\mathrm{/}r}=0$, of Real powers for positive bases, with the zero-base positive-exponent convention. If the integral is $+\mathrm{\infty }$, define $\mathrm{\parallel }g{\mathrm{\parallel }}_{Q,r}:=+\mathrm{\infty }$ directly. The function $\mathrm{\mid }g\mathrm{\mid }$ is measurable by Arithmetic and lattice operations preserve measurability whenever they are defined, and Positive real powers preserve measurability makes $\mathrm{\mid }g{\mathrm{\mid }}^r$ measurable, so this nonnegative extended integral is well-defined. On a class of functions with finite such norms, $d_{Q,r}(f,g):=\mathrm{\parallel }f-g{\mathrm{\parallel }}_{Q,r}$ is a pseudometric: nonnegativity, symmetry, and zero diagonal follow from the absolute value, and the triangle inequality is Minkowski's inequality for integrals, including $p=\mathrm{\infty }$. Functions that agree $Q$-almost everywhere have distance zero. We write $N(ϵ,\mathcal{F},L^r(Q))$ for this covering number.

For measurable real endpoints $\mathrm{\ell }\le u$ $Q$-almost everywhere, the bracket $[\mathrm{\ell },u]$ is the set of measurable functions $f$ satisfying $\mathrm{\ell }\le f\le u$ $Q$-almost everywhere. Its $L^r(Q)$ width is $\mathrm{\parallel }u-\mathrm{\ell }{\mathrm{\parallel }}_{Q,r}$. The bracketing number $N_{[]}(ϵ,\mathcal{F},L^r(Q))$ is the least number of such brackets of width at most $ϵ$ that cover $\mathcal{F}$, or $+\mathrm{\infty }$ if no finite cover exists; for the empty class set it equal to $1$. Centers of metric covers are in $\mathcal{F}$; bracket endpoints need not be.