Growth rate of bounded Lipschitz functions on compact finite-dimensional space

Question

Let $\mathcal X$ be a metric space of diameter $D$ and "dimension" (e.g doubling dimension) $d$. Let $L \in [0, \infty]$ and $M \in [0, \infty)$ and consider the class $\mathcal H_{M,L}$ of $L$-Lipschitz functions on $\mathcal X$ whose image is contained in the interval $[0, M]$. For an integer $n \ge 1$, define the growth rate of the function class $\mathcal H_{M,L}$ by $$G_n := \sup_{(x_1,\ldots,x_{2n}) \in \mathcal X^{2n}}\mathcal N(1/n,\mathcal H_{M,L}(x_1,\ldots,x_{2n})), $$ where $\mathcal H_{M,L}(x_1,\ldots,x_m):= \{(h(x_1),\ldots,h(x_m))|h \in \mathcal H_{M,L}\} \subseteq [0,M]^m$.

N.B.: For every $\epsilon > 0$ and $A \subseteq X$, $\mathcal N(\epsilon,A)$ is the least number of spheres of radius $\epsilon$ needed to cover the subset $A$, i.e the covering number of $A$.

Question

• Given these data, what are good bounds for $G_n$ ?
• What about the non-Lipschitz special case where $L = \infty$ ?

Answer 1

Fine estimates of covering and packing numbers of several metric spaces of functions have been obtained in the paper:

A.N. Kolmogorov, V.M. Tihomirov. $\epsilon$-entropy and $\epsilon$-capacity of sets in functional space. Amer. Math. Soc. Transl. (2) 17, 1961, 277-364.

I reproduce below a (particular case of a) result from that paper that seems related to your question. I keep the original notations, and specify the corresponding page numbers.

[p.279-280] If $A$ is a totally bounded (e.g. compact) metric space and $\epsilon>0$ then $\mathcal{N}_\epsilon(A)$ denotes the minimal number of sets of diameter $\le 2\epsilon$ that cover $A$, and $\mathcal{M}_\epsilon(A)$ denotes the maximal cardinality of an $\epsilon$-separated set. The $\epsilon$-entropy and the $\epsilon$-capacity of $A$ are defined as: $$ \mathcal{H}_\epsilon(A) := \log \mathcal{N}_\epsilon(A) , \qquad \mathcal{C}_\epsilon(A) := \log \mathcal{M}_\epsilon(A) \, . $$ (where $\log = \log_2$). Note [p. 282] that $\mathcal{C}_{2\epsilon}(A) \le \mathcal{H}_\epsilon(A) \le \mathcal{C}_\epsilon(A)$.

[p. 296] The metric dimension of $A$ (also called box-counting dimension or Minkowski dimension) is defined as: $$ \mathrm{dm}(A) := \lim_{\epsilon \to 0} \frac{\mathcal{H}_\epsilon(A)}{\log(1/\epsilon)} = \lim_{\epsilon \to 0} \frac{\mathcal{C}_\epsilon(A)}{\log(1/\epsilon)}. $$

[p.307-308] Let $K$ be a compact subset of a finite-dimensional Banach space. Given $C_0,C>0$, let $F_1^K(C_0,C)$ denote the space of functions $f : K \to \mathbb{R}$ that are $C$-Lipschitz and satisfy an uniform bound $|f(x)| \le C_0$. We endow this set with the uniform metric $\rho(f,g):=\sup_{x\in K}|f(x)-g(x)|$, and so it is compact.

[p.308] Theorem. If $K$ has well-defined metric dimension $\mathrm{dm}(K) = n$ (not necessarily an integer!) and $A:=F_1^K(C_0,C)$ then: $$ \mathcal{H}_\epsilon(A) \asymp \mathcal{C}_\epsilon(A) \asymp \frac{1}{\epsilon^n} , $$ where [p.295] $f \asymp g$ means that $f/g$ is bounded away from $0$ and $\infty$.