\(f_\emptyset = \mathrm{id}\).

\(f_{(i, u)} = f_u \circ f_i\).

\(f_{(i,u)}(x) = f_u(f_i(x))\).

\(S_0(\Lambda ) = 0\).

\(S_1(\Lambda ) = 1\).

As a real number, \(S_m(\Lambda ) = \sum _{i{\lt}m} \Lambda ^i\).

\(\alpha (e) = \mathrm{id}\).

\(\alpha (gh) = \alpha (g) \circ \alpha (h)\).

\(X = E^{\mathbb N}\) is nonempty (it contains \(0\)).

If \(a \le b + c\) in \([0,\infty ]\) then \(\min \{ 1,a\} \le \min \{ 1,b\} + \min \{ 1,c\} \).

\(d_X(x,y) = \sup _j \min \{ 1, \| x_j - y_j\| _E\} \).

\(d_X(x,y) \le 1\).

\(r(x)_j = 0\).

\(g_u(x)_0 = u\).

\(g_u(x)_{i+1} = x_i\).

\(A(x)_j = \lambda x_j\).

\(w_{()} = r\).

\(w_u = A \circ g_{u_k} \circ w_{u|_{k}}\) for \(u \in E^{k+1}\).

(Sub-multiplicativity.) Let \(F, G \subseteq \mathcal X^{\mathcal X}\) and suppose every \(f \in F\) is \(\lambda \)-Lipschitz. Then for all \(\varepsilon , \delta \ge 0\),

(This is the paper’s \(N(FG, \varepsilon + \delta ) \le N(F, \varepsilon /\rho ) N(G, \delta /\lambda )\) with \(\rho = 1\), since right composition is \(1\)-Lipschitz for \(d_\infty \); we write \(\lambda \delta \) in place of \(\delta /\lambda \) to avoid dividing by \(\lambda = 0\).)

The evaluation map \(\mathrm{ev}_P\) is \(1\)-Lipschitz from \(d_\infty \) to the sup-metric on \(\mathcal X^J\).

(Probes and packing.) Let \(A \subseteq (\mathcal X^{\mathcal X}, d_\infty )\), let \(P\) be a finite family of probes and let \(T \subseteq \mathrm{ev}_P(A)\) be \(\delta \)-separated: \(d_{\max }(y,z) \ge \delta \) for all distinct \(y, z \in T\). Then for every \(\varepsilon \) with \(2\varepsilon {\lt} \delta \), \(|T| \le N^{\mathrm{ext}}(A, d_\infty , \varepsilon )\).

Under the hypotheses of the previous lemma, also \(|T| \le N(A, d_\infty , \varepsilon )\) (internal covering number).

(Indexed form of ‘lem:probes-packing‘.) Let \((g_i)_{i \in I}\) be a family of maps in \(A \subseteq (\mathcal X^{\mathcal X}, d_\infty )\) and \(P\) a finite family of probes such that \(d_{\max }(\mathrm{ev}_P(g_i), \mathrm{ev}_P(g_j)) \ge \delta {\gt} 0\) for all \(i \ne j\). Then \(|I| \le N^{\mathrm{ext}}(A, d_\infty , \varepsilon )\) whenever \(2\varepsilon {\lt} \delta \).

If \(\mathcal X\) is complete then \((\mathcal X^{\mathcal X}, d_\infty )\) is complete (uniform limits of Cauchy sequences). This is Mathlib’s instance on ‘X →ᵤ X‘.

(Metric modulus criterion.) Let \((\mathcal X, d)\) be a totally bounded (pseudo)metric space. If \(H \subseteq \mathcal X^{\mathcal X}\) has a common modulus of continuity, namely there is \(\omega : \mathbb R \to \mathbb R\) with \(\omega (r) \to 0\) as \(r \downarrow 0\) (for every \(\varepsilon {\gt} 0\) there is \(r {\gt} 0\) with \(\omega (t) \le \varepsilon \) for \(0 \le t \le r\)) and

then \(H\) is totally bounded in \(d_\infty \).

(Modulus extraction on compact domains.) Let \((\mathcal X,d)\) be compact and \(H \subseteq \mathcal X^{\mathcal X}\) equicontinuous. Then \(H\) admits a common monotone modulus of continuity \(\omega \) with \(\omega (r) \to 0\) as \(r \downarrow 0\) and \(d(f(x), f(y)) \le \omega (d(x,y))\) for all \(f \in H\), \(x, y \in \mathcal X\). In particular ‘thm:maa‘ applies.

(Forward direction of ‘thm:caa‘.) If \(\mathcal X\) is compact and \(H \subseteq \mathcal X^{\mathcal X}\) is equicontinuous, then \(H\) is totally bounded in \(d_\infty \).

(Converse direction of ‘thm:caa‘.) If \(H \subseteq C(\mathcal X, \mathcal X)\) is totally bounded in \(d_\infty \) then \(H\) is equicontinuous. (Continuity of the members of \(H\) is needed; compactness of \(\mathcal X\) is not.)

(Compact Arzelà–Ascoli for self-maps.) Let \((\mathcal X, d)\) be a compact (pseudo)metric space and let \(H \subseteq C(\mathcal X, \mathcal X)\). Then \(H\) is totally bounded in \(d_\infty \) if and only if \(H\) is equicontinuous.

(Consequence of ‘thm:caa‘.) If \(\mathcal X\) is compact and \(H \subseteq \mathcal X^{\mathcal X}\) is equicontinuous, then the closure of \(H\) in \((\mathcal X^{\mathcal X}, d_\infty )\) is compact.

(Saturation for compact equicontinuous semigroups.) Let \((\mathcal X, d)\) be compact and \(F \subseteq \mathcal X^{\mathcal X}\). If the generated semigroup \(\langle F \rangle \) is equicontinuous, then for every \(\varepsilon {\gt} 0\) and every \(k\)

In particular the covering number of the word ball does not grow with the depth \(k\).

(Internal version of ‘cor:aa-semigroup-saturation‘.) Under the same hypotheses, for every \(\varepsilon {\gt} 0\) and every \(k\), \(N\bigl(B(k,F), d_\infty , \varepsilon \bigr) \le N\bigl(\overline{\langle F\rangle }^{d_\infty }, d_\infty , \varepsilon /2\bigr) {\lt} \infty \) (internal covering numbers are not monotone in the set, whence the loss of a factor \(2\) in the radius).

\(f \in B(k,F)\) if and only if \(f \in F^l\) for some \(l \le k\).

Every word of length \(n + L\) factors as \(w = w_2 \circ w_1\) with \(w_2 \in F^n\) and \(w_1 \in F^L\).

If \(f(A) \subseteq A\) for every \(f \in F\), then \(w(a) \in A\) for every word \(w \in F^m\) and every \(a \in A\).

If every \(f \in F\) is \(c\)-Lipschitz then every word \(w \in F^m\) is \(c^m\)-Lipschitz.

If the generators are non-expanding (\(1\)-Lipschitz) then every element of \(B(k,F)\) is non-expanding.

If the generators are non-expanding then the whole semigroup \(\langle F \rangle \) is non-expanding: \(\mathrm{lip}\, F \le 1\) implies \(\mathrm{lip}\, \langle F \rangle \le 1\).

(P1: equicontinuous semigroup on a compact domain saturates, hypothesis 1.) Assume \(\mathcal X\) is compact and the semigroup \(\langle F \rangle \) is precompact (totally bounded) in \(d_\infty \). Then, with \(G := \overline{\langle F\rangle }^{d_\infty }\), for all \(\varepsilon {\gt} 0\) and all \(k\),

hence no dependence on \(k\). (Compactness of \(\mathcal X\) is not needed for this hypothesis.)

(P1, hypothesis 2a.) Assume \(\mathcal X\) is compact and the semigroup \(\langle F \rangle \) is equicontinuous. Then for all \(\varepsilon {\gt} 0\) and all \(k\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F\rangle }, d_\infty , \varepsilon ) {\lt} \infty \).

(P1, hypothesis 2b.) Assume \(\mathcal X\) is compact and the semigroup \(\langle F \rangle \) is uniformly Lipschitz: every \(g \in \langle F \rangle \) is \(K\)-Lipschitz for a common \(K\). Then for all \(\varepsilon {\gt} 0\) and all \(k\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F\rangle }, d_\infty , \varepsilon ) {\lt} \infty \).

(P1, hypothesis 2c.) Assume \(\mathcal X\) is compact and the generators are non-expanding: \(\mathrm{lip}\, F \le 1\). Then for all \(\varepsilon {\gt} 0\) and all \(k\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F\rangle }, d_\infty , \varepsilon ) {\lt} \infty \).

If \(0 {\lt} c {\lt} 1\), \(\varepsilon {\gt} 0\) and \(m(\varepsilon ) \le n + L\) then \(c^n \, \mathrm{diam}(K) \le \varepsilon /2\).

(Long words are almost constant.) Under the hypotheses of ‘cond:p1-ucont‘, for every word \(w \in F^l\) with \(l \ge m(\varepsilon )\) and all \(x, y \in \mathcal X\),

In particular \(d_\infty (w, \mathrm{const}_{w(a_0)}) \le \varepsilon /2\) for every \(a_0\).

(Long words.) Under the hypotheses of ‘cond:p1-ucont‘, the set of all words of length \(\ge m(\varepsilon )\) satisfies

Indeed each such word \(w\) is \(\varepsilon /2\)-close to the constant map \(\mathrm{const}_{w(a_0)}\) with \(w(a_0) \in A\), so the constant maps at the points of an \(\varepsilon /2\)-net of \(A\) form an \(\varepsilon \)-cover.

(Short words; subadditivity over finitely many sets.) For a finite family \((A_i)_{i \in s}\), \(N^{\mathrm{ext}}\bigl(\bigcup _{i \in s} A_i, \varepsilon \bigr) \le \sum _{i \in s} N^{\mathrm{ext}}(A_i, \varepsilon )\). Applied to \(A_l = F^l\), \(l {\lt} m(\varepsilon )\), this covers the short words.

(P1’: contraction to a compact invariant set.) Assume

1. (uniform contraction) every \(f \in F\) is \(c\)-Lipschitz with \(0 {\lt} c {\lt} 1\);

2. (invariant set) there is a nonempty \(F\)-invariant set \(A \subseteq \mathcal X\) (\(f(A) \subseteq A\) for all \(f \in F\));

3. (bounded absorbing set) there are \(L \in \mathbb N\) and a bounded set \(K \subseteq \mathcal X\) with \(f(\mathcal X) \subseteq K\) for every word \(f \in F^L\) of length \(L\).

Then for every \(\varepsilon {\gt} 0\), with \(m(\varepsilon ) := L + \lceil \log _{1/c}(2\, \mathrm{diam}(K)/\varepsilon ) \rceil \), for every \(k \ge 0\),

In particular the right-hand side is independent of \(k\). (This generalizes the paper, which assumes \(A\) compact, \(K\) compact and \(k \ge m(\varepsilon )\): the proof uses of \(A\) only that it is nonempty and invariant, of \(K\) only its boundedness, and the bound holds for every \(k\). The right-hand side is finite whenever each \(N^{\mathrm{ext}}(F^l, d_\infty , \varepsilon )\), \(l {\lt} m(\varepsilon )\), is finite, which the paper does not assume.)

Let \(\alpha : H \to \mathcal X^{\mathcal X}\) be a homomorphism, assume the length \(g \mapsto d_H(e,g)\) is subadditive, \(d_H(e, gh) \le d_H(e,g) + d_H(e,h)\), and let \(S \subseteq H\) satisfy \(d_H(e,s) \le R_S\) for all \(s \in S\) and \(F \subseteq \alpha (S)\). Then for every \(k\),

If the orbit map is \(L_\alpha \)-Lipschitz, \(d_\infty (\alpha (g), \alpha (h)) \le L_\alpha d_H(g,h)\), then for every \(B \subseteq H\) and \(\delta \ge 0\),

Under the hypotheses of ‘lem:p2-wordball-subset-ball‘ and ‘lem:p2-transfer‘, for every \(k\) and \(\delta \ge 0\),

For \(\varepsilon , L_\alpha {\gt} 0\), \(R_S \ge 0\), \(k \ge 0\) and \(D \ge 0\),

(P2: nilpotent control grows polynomially.) Let \((H, d_H)\) be a group with a pseudo-emetric, identity \(e\), and assume the length \(g \mapsto d_H(e,g)\) is subadditive: \(d_H(e,gh) \le d_H(e,g) + d_H(e,h)\). Assume its balls have polynomial entropy of degree \(D \ge 0\): there is \(1 \le C_H {\lt} \infty \) such that for all \(R \ge 0\) and \(\delta {\gt} 0\),

Suppose \(H\) acts on \(\mathcal X\) through a homomorphism \(\alpha : H \to \mathcal X^{\mathcal X}\), that there is a bounded set \(S \subseteq H\) (\(d_H(e,s) \le R_S\) for \(s \in S\)) with \(F \subseteq \alpha (S)\), and that the orbit map is Lipschitz in the uniform metric: \(d_\infty (\alpha (g), \alpha (h)) \le L_\alpha d_H(g,h)\) with \(0 {\lt} L_\alpha {\lt} \infty \). Then with

one has, for every \(\varepsilon {\gt} 0\) and every \(k \ge 0\),

(In Lean the ball-entropy hypothesis and the conclusion are stated in \([0,\infty ]\) as \(N \le \operatorname {ofReal}(\cdots )\), which in particular asserts finiteness; the bound holds for \(k = 0\) as well.)

(Real-valued form of P2.) Under the hypotheses of ‘cond:p2-nilp‘, for every \(\varepsilon {\gt} 0\) and \(k \ge 0\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le C_H \max (1, R_S L_\alpha )^D (1 + k/\varepsilon )^D\) as real numbers (the covering number being finite).

(Diameter envelope.) Under the hypotheses of ‘lem:p2-wordball-subset-ball‘ and with the orbit map \(L_\alpha \)-Lipschitz, for all \(f, g \in B(k,F)\),

i.e. \(\mathrm{diam}_\infty B(k,F) \le 2L_\alpha R_S k\) (and a fortiori \(D_k(S) \le 2 L_\alpha R_S k\) for every sample \(S\)).

On a bounded state space, \(d(x,y) \le D_{\mathcal X}\) for all \(x, y \in \mathcal X\), every pair of self-maps satisfies \(d_\infty (f,g) \le D_{\mathcal X}\); in particular \(\mathrm{diam}_\infty B(k,F) \le \mathrm{diam}(\mathcal X)\) for every \(k\).

If \(w \in F^m\) and \(g \in F\) then \(w \circ g \in F^{m+1}\): the words of length \(m\) are also closed under right composition with generators.

\(f_u \in F^{|u|}\) where \(F = \{ f_1, \dots , f_r\} \).

\(F^m \subseteq B(m,F)\).

If \(|u| \le k\) then \(f_u \in B(k,F)\) where \(F = \{ f_1, \dots , f_r\} \).

Let \(f = (f_1,\dots ,f_r)\) and let \(P\) be a finite family of probes such that the evaluations \(\mathrm{ev}_P(f_u)\), \(u \in [r]^k\), are pairwise at sup-distance \(\ge \delta {\gt} 0\). Then \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \ge r^k\) for every \(\varepsilon \) with \(2\varepsilon {\lt} \delta \).

(E1: free semigroup with one-point uniform separation.) Let \(F = \{ f_1, \dots , f_r\} \), \(r \ge 2\), and suppose there are a base point \(x_* \in \mathcal X\) and \(\delta {\gt} 0\) such that for every \(k\) and all distinct words \(u \ne v \in [r]^k\),

Then for every \(k\) and every \(\varepsilon {\lt} \delta /2\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \ge r^k\). (The paper’s hypothesis (1), that \(u \mapsto f_u\) is injective on \([r]^k\), follows from the separation hypothesis since \(\delta {\gt} 0\), so it is omitted; the hypothesis \(r \ge 2\) is not used in the proof.)

(E1’: equal-length coding.) Let \(F = \{ f_1, \dots , f_r\} \), \(r \ge 2\), and suppose there are \(x_* \in \mathcal X\) and \(\delta {\gt} 0\) with \(d(f_u(x_*), f_v(x_*)) \ge \delta \) for all distinct \(u, v \in [r]^k\) and all \(k\). Then \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \ge r^k\) for all \(k\) and all \(\varepsilon {\lt} \delta /2\). (This generalizes the paper, which assumes in addition that the generators are isometries, that \(d_\infty \) is finite on \(\langle F\rangle \) and that \(u \mapsto f_u\) is injective on \([r]^k\): none of these is needed for the lower bound, which follows from ‘cond:e1-free-iso‘ in one line; the isometry hypothesis only serves, in the paper, to make the covering numbers meaningful.)

If \(A \subseteq \mathcal X\) satisfies \(f_i(A) \subseteq A\) for all \(i\), then \(f_u(A) \subseteq A\) for every word \(u\).

(Probe construction for E2.) Under the hypotheses of ‘cond:e2-pingpong‘, for every word \(u\) there is a point \(x_u \in Q = \{ q\} \cup \bigcup _j V_j\) with \(f_u(x_u) = q\) and \(f_v(x_u) \in A = \{ a_1, \dots , a_r\} \) for every word \(v \ne u\) of the same length.

(E2: ping–pong coding.) Let \(F = \{ f_1, \dots , f_r\} \), \(r \ge 2\), and suppose there are sets \(V_i \subseteq U_i \subseteq \mathcal X\), anchors \(a_1, \dots , a_r \in \mathcal X\), a marker \(q \in \mathcal X\) and a constant \(\alpha {\gt} 0\) such that, with \(A = \{ a_1, \dots , a_r\} \) and \(Q = \{ q\} \cup \bigcup _j V_j\):

1. (disjoint chambers) \(U_i \cap U_j = \emptyset \) for \(i \ne j\);

2. (coding cores) \(Q \subseteq f_i(V_i)\) for every \(i\);

3. (reset) \(f_i(x) = a_i\) for \(x \notin U_i\), and \(f_i(A) \subseteq A\);

4. (marker separation) \(d(q, a_i) \ge \alpha \) for every \(i\).

Then (a) \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \ge r^k\) for every \(k\) and every \(\varepsilon {\lt} \alpha /2\), and (b) \(u \mapsto f_u\) is injective on \([r]^k\) for every \(k\). (This generalizes the paper, which assumes in (1) a uniform separation \(d(U_i, U_j) \ge \Delta {\gt} 0\) and additionally \(V_i \ne \emptyset \): the proof uses of (1) only the disjointness of the chambers, and \(V_i \ne \emptyset \) follows from (2) since \(q \in f_i(V_i)\); the hypothesis \(r \ge 2\) is not used.)

\(w_u \in B(2k+1, F)\) for every \(u \in G^k\).

\(W_k \subseteq B(2k+1, F)\).

(E3 (i).) For every \(x \in X\), \(w_u(x) = (\lambda u_{k-1}, \lambda ^2 u_{k-2}, \dots , \lambda ^k u_0, 0, 0, \dots )\): coordinate \(j {\lt} k\) of \(w_u(x)\) is \(\lambda ^{j+1} u_{k-1-j}\) and the coordinates \(j \ge k\) vanish. In particular \(w_u\) is a constant map.

\(w_u\) is constant: \(w_u(x) = w_u(y)\) for all \(x, y\).

For \(\lambda \ne 0\) the map \(u \mapsto w_u\) is injective on \(E^k\).

If \(f : \mathbb N \to [0,\infty ]\) vanishes on \(j \ge k\) then \(\sup _{j \in \mathbb N} f(j) = \max _{j {\lt} k} f(j)\).

(E3 (ii).) For \(u, v \in E^k\), \(d_\infty (w_u, w_v) = \max _{0 \le j {\lt} k} \min \{ 1, \lambda ^{j+1} \| u_{k-1-j} - v_{k-1-j}\| _E\} \) (the paper’s \(\max _{1 \le j \le k} \min \{ 1, \lambda ^{k-j+1}\| u_j - v_j\| \} \) after reindexing).

The same identity for the extended distance of \((\mathcal X^{\mathcal X}, d_\infty )\).

(E3 (iii), upper bound.) For every \(\varepsilon \ge 0\) (and \(\lambda \ne 0\)),

(Product packing.) Let \(2\varepsilon {\lt} 1\), \(\lambda \ne 0\), and let \(P_j \subseteq G\) be \(2\varepsilon /\lambda ^{j+1}\)-separated (\(0 \le j {\lt} k\)). Then \(\prod _j |P_j| \le M(W_k, d_\infty , 2\varepsilon )\).

In \(\mathbb N \cup \{ \infty \} \), a finite product of suprema over nonempty index types is the supremum of the products: \(\prod _{i \in s} \sup _{a \in A_i} g_i(a) = \sup _{x \in \prod _i A_i} \prod _{i \in s} g_i(x_i)\).

(E3 (iii), lower bound.) For every \(0 \le \varepsilon {\lt} 1/2\) (and \(\lambda \ne 0\)),

\(N^{\mathrm{ext}}(W_k, d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(B(2k+1,F), d_\infty , \varepsilon )\) (monotonicity of the external covering number under \(W_k \subseteq B(2k+1,F)\)).

(E3: memory-preserving expansion grows super- or double-exponentially.) Let \(E\) be a normed space, \(G \subseteq E\), \(\lambda {\gt} 1\), \(X = E^{\mathbb N}\) with the bounded sup metric, \(F = \{ r, A\} \cup \{ g_u : u \in G\} \) and \(W_k = \{ w_u : u \in G^k\} \subseteq B(2k+1, F)\). Then (i) each \(w_u\) is the constant map with value \((\lambda u_{k-1}, \dots , \lambda ^k u_0, 0, \dots )\) (‘cond:e3-i‘), (ii) \(d_\infty (w_u, w_v) = \max _{j{\lt}k} \min \{ 1, \lambda ^{j+1}\| u_{k-1-j} - v_{k-1-j}\| \} \) (‘cond:e3-ii‘), and (iii) for every \(0 {\lt} \varepsilon {\lt} 1/2\),

Consequently \(N^{\mathrm{ext}}(B(2k+1,F), d_\infty , \varepsilon ) \ge N^{\mathrm{ext}}(W_k, d_\infty , \varepsilon )\).

For finite nonzero \(n_i \in \mathbb N \cup \{ \infty \} \), \(\log \prod _i n_i = \sum _i \log n_i\) (with the coercion to \([0,\infty ]\) and ‘toReal‘).

If \(G \ne \emptyset \) and all \(N^{\mathrm{ext}}(G, \varepsilon /\lambda ^{j+1})\) are finite, then \(\log N^{\mathrm{ext}}(W_k, \varepsilon ) \le \sum _{j{\lt}k} \log N^{\mathrm{ext}}(G, \varepsilon /\lambda ^{j+1})\).

If \(G \ne \emptyset \), \(\varepsilon {\lt} 1/2\), all \(M(G, 2\varepsilon /\lambda ^{j+1})\) and \(N^{\mathrm{ext}}(W_k, \varepsilon )\) are finite, then \(\sum _{j{\lt}k} \log M(G, 2\varepsilon /\lambda ^{j+1}) \le \log N^{\mathrm{ext}}(W_k, \varepsilon )\).

\(\sum _{j{\lt}k} \log \bigl(\lambda ^{j+1}/a\bigr) = \frac{k(k+1)}{2}\log \lambda - k \log a\) for \(a, \lambda {\gt} 0\).

If \(0 \le a {\lt} \lambda \delta _0\) and \(\lambda {\gt} 1\) then \(a/\lambda ^{j+1} {\lt} \delta _0\) for every \(j\).

If \(c_- \log (1/\delta ) \le \log M(G, \delta )\) for all small \(\delta {\gt} 0\) with \(c_- {\gt} 0\), then \(G \ne \emptyset \).

(Upper bound in sum form.) Suppose \(N^{\mathrm{ext}}(G,\delta ) {\lt} \infty \) for all \(\delta {\gt} 0\), \(G \ne \emptyset \), and \(\log N^{\mathrm{ext}}(G, \delta ) \le \varphi (\delta )\) for \(0 {\lt} \delta {\lt} \delta _0\). If \(0 {\lt} \varepsilon {\lt} \lambda \delta _0\) then \(\log N^{\mathrm{ext}}(W_k, \varepsilon ) \le \sum _{j{\lt}k} \varphi (\varepsilon /\lambda ^{j+1})\) for every \(k\).

If \(N^{\mathrm{ext}}(G,\delta ) {\lt} \infty \) for all \(\delta {\gt} 0\) then \(N^{\mathrm{ext}}(W_k, \varepsilon ) {\lt} \infty \) for all \(\varepsilon {\gt} 0\).

(Lower bound in sum form.) Suppose \(N^{\mathrm{ext}}(G,\delta ) {\lt} \infty \) for all \(\delta {\gt} 0\), \(G \ne \emptyset \), and \(\varphi (\delta ) \le \log M(G, \delta )\) for \(0 {\lt} \delta {\lt} \delta _0\). If \(0 {\lt} \varepsilon {\lt} 1/2\) and \(2\varepsilon {\lt} \lambda \delta _0\) then \(\sum _{j{\lt}k} \varphi (2\varepsilon /\lambda ^{j+1}) \le \log N^{\mathrm{ext}}(W_k, \varepsilon )\) for every \(k\).

(Super-exponential regime.) Assume there are \(c_-, c_+, \delta _0 {\gt} 0\) with \(c_- \log (1/\delta ) \le \log M(G, \delta )\) and \(\log N^{\mathrm{ext}}(G, \delta ) \le c_+ \log (1/\delta )\) for all \(0 {\lt} \delta {\lt} \delta _0\), and that \(N^{\mathrm{ext}}(G, \delta ) {\lt} \infty \) for all \(\delta {\gt} 0\) (automatic for compact \(G\)). Then for every fixed \(\varepsilon \) with \(0 {\lt} \varepsilon {\lt} 1/2\) and \(\varepsilon {\lt} \lambda \delta _0/2\) there are \(C_1, C_2 {\gt} 0\) and \(k_0\) such that \(C_1 k^2 \le \log N^{\mathrm{ext}}(W_k, d_\infty , \varepsilon ) \le C_2 k^2\) for all \(k \ge k_0\). (The smallness condition \(\varepsilon {\lt} \lambda \delta _0/2\) makes every radius \(2\varepsilon /\lambda ^{j+1} \le 2\varepsilon /\lambda \) fall below \(\delta _0\); it cannot be replaced by "large \(k\)" since the \(j = 0\) radius does not shrink with \(k\).)

\(\sum _{j{\lt}k} (a/\lambda ^{j+1})^{-p} = a^{-p} \sum _{j{\lt}k} (\lambda ^p)^{j+1}\) for \(a, \lambda {\gt} 0\).

For \(q {\gt} 1\) and \(k \ge 1\): \(q^k \le \sum _{j{\lt}k} q^{j+1} \le \frac{q}{q-1} q^k\).

If \(c_- \delta ^{-p} \le \log M(G, \delta )\) for all small \(\delta {\gt} 0\) with \(c_- {\gt} 0\), then \(G \ne \emptyset \).

(Double-exponential regime.) Assume there are \(p, c_-, c_+, \delta _0 {\gt} 0\) with \(c_- \delta ^{-p} \le \log M(G, \delta )\) and \(\log N^{\mathrm{ext}}(G, \delta ) \le c_+ \delta ^{-p}\) for all \(0 {\lt} \delta {\lt} \delta _0\), and that \(N^{\mathrm{ext}}(G, \delta ) {\lt} \infty \) for all \(\delta {\gt} 0\). Then for every fixed \(\varepsilon \) with \(0 {\lt} \varepsilon {\lt} 1/2\) and \(\varepsilon {\lt} \lambda \delta _0/2\) there are \(C_1, C_2 {\gt} 0\) and \(k_0\) such that \(C_1 \lambda ^{pk} \le \log N^{\mathrm{ext}}(W_k, d_\infty , \varepsilon ) \le C_2 \lambda ^{pk}\) for all \(k \ge k_0\).

\(S_{m+1}(\Lambda ) = 1 + \Lambda \, S_m(\Lambda )\).

\(m \mapsto S_m(\Lambda )\) is nondecreasing.

\(S_m(\Lambda ) \ge 1\) for \(m \ge 1\).

\(S_m(\Lambda ) {\gt} 0\) for \(m \ge 1\).

With \(\Lambda _+ := \max \{ 1, \Lambda \} \), \(S_k(\Lambda ) \le k\, \Lambda _+^k\) (since \(\Lambda ^i \le \Lambda _+^k\) for \(i {\lt} k\)).

If all layers of \(u\) lie in \(F\) then \(f_u \in F^{|u|}\).

Every \(g \in F^m\) is \(f_u\) for a list \(u\) of elements of \(F\) with \(|u| = m\).

\(B(k, \emptyset ) = \{ \mathrm{id}\} \).

If \(N {\lt} \infty \) then \(1 + kN {\lt} \infty \) (in \(\mathbb N \cup \{ \infty \} \)).

For natural numbers \(k, N\): \(\log (1 + kN) \le \log (k+1) + \log N\) (with \(\log 0 = 0\)): \(1 + kN \le (k+1)N\) when \(N \ge 1\), and \(\log 1 = 0\) when \(N = 0\).

If \(A \le 1 + kN\) in \(\mathbb N \cup \{ \infty \} \) with \(N {\lt} \infty \), then \(\log A \le \log (k+1) + \log N\) (as real numbers, with \(\log \infty = \log 0 = 0\)).

(Uniform form of the telescoping estimate ‘lem:impl-word-error‘.) If every \(f \in F\) is \(\Lambda \)-Lipschitz and \(d_\infty (f, \tilde f) \le \delta \) for \(f \in F\), then \(d_\infty (f_u, \tilde f_u) \le \delta \sum _{i{\lt}|u|} \Lambda ^i\) for every list \(u\) of layers in \(F\).

(Covering the words of length \(m\).) If every \(f \in F\) is \(\Lambda \)-Lipschitz then for every \(\varepsilon \ge 0\) and \(m \ge 0\),

The \(M^m\) compositions \(c_{i_m} \circ \cdots \circ c_{i_1}\) of the centres of an \(\varepsilon /S_m(\Lambda )\)-cover \(\{ c_1, \dots , c_M\} \) of \(F\) form an \(\varepsilon \)-cover of \(F^m\) by the telescoping estimate.

(First inequality of ‘prop:envelope‘.) If every \(f \in F\) is \(\Lambda \)-Lipschitz then for every \(k \ge 0\) and \(\varepsilon \ge 0\),

(Second inequality of ‘prop:envelope‘.) For every \(k \ge 0\) and \(\varepsilon \ge 0\),

because \(S_m(\Lambda ) \le S_k(\Lambda )\) for \(m \le k\), covering numbers are nonincreasing in the radius, and \(N^m \le N^k\) for \(N \ge 1\) (or \(N = 0\), \(m, k \ge 1\)).

(Simplified envelope.) If every \(f \in F\) is \(\Lambda \)-Lipschitz then for every \(k \ge 0\) and \(\varepsilon \ge 0\),

(Covering envelope, ‘prop:envelope‘ restated.) Let \(F \subseteq \mathcal X^{\mathcal X}\) consist of \(\Lambda \)-Lipschitz maps, \(\Lambda \ge 0\), and \(S_m(\Lambda ) = \sum _{i=0}^{m-1}\Lambda ^i\). For every \(k \ge 0\) and \(\varepsilon \ge 0\),

The centres of the covers of \(F\) need not belong to \(F\) nor be Lipschitz; only the Lipschitz constant of the maps in \(F\) is used. (In Lean \(\varepsilon /S_0 = 0\) and the statement holds for \(k = 0\) as well.)

If \(N^{\mathrm{ext}}(F, \varepsilon /S_k(\Lambda )) {\lt} \infty \) then \(N^{\mathrm{ext}}(B(k,F), \varepsilon ) {\lt} \infty \).

(Logarithmic form of the envelope.) If every \(f \in F\) is \(\Lambda \)-Lipschitz, \(k \ge 1\) and \(N := N^{\mathrm{ext}}(F, \varepsilon /S_k(\Lambda )) {\lt} \infty \), then \(\log N^{\mathrm{ext}}(B(k,F), \varepsilon ) \le \log (k+1) + k\log N\) (using \(1 + kN^k \le (k+1)N^k\) for \(N \ge 1\); for \(N = 0\) both sides are \(\ge 0 = \log 1\)).

(Parametric layers, entropy form of ‘cor:envelope-profiles‘(a).) Let every \(f \in F\) be \(\Lambda \)-Lipschitz and suppose \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le p\log (C/\varepsilon )\) for all \(0 {\lt} \varepsilon \le C\), with \(p \ge 0\). Then for \(k \ge 1\) and \(0 {\lt} \varepsilon \le C\),

(Nonparametric layers, entropy form of ‘cor:envelope-profiles‘(b).) Let every \(f \in F\) be \(\Lambda \)-Lipschitz and suppose \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le c\, \varepsilon ^{-q}\) for all \(\varepsilon {\gt} 0\), with \(c \ge 0\). Then for \(k \ge 1\) and \(\varepsilon {\gt} 0\),

(Transfer to the empirical metric.) If every \(f \in F\) is \(\Lambda \)-Lipschitz and \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon /(2S_k(\Lambda ))) {\lt} \infty \), then \(\log N(B(k,F), d_S, \varepsilon ) \le \log N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon /2)\) for every sample \(S\) (‘lem:covering-empSpace-le-external-unifMaps‘).

(Profiles from the envelope: parametric layers, ‘cor:envelope-profiles‘(a).) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, let \(\overline D {\gt} 0\), \(C \ge \overline D\), \(p \ge 0\), and suppose \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le p\log (C/\varepsilon )\) for all \(0 {\lt} \varepsilon \le C\). If \(D_k(S) \le \overline D\) then, for \(k \ge 1\), with \(\Lambda _+ := \max \{ 1,\Lambda \} \),

(The paper has \(C\) in place of \(2C\): the factor \(2\) is the price of comparing the internal covering number in \(d_S\) defining \(\mathsf V_k(S)\) with the external one in \(d_\infty \), ‘lem:covering-empSpace-le-external-unifMaps‘.)

(Profiles from the envelope: nonparametric layers, ‘cor:envelope-profiles‘(b).) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, let \(\overline D {\gt} 0\), \(c \ge 0\), \(0 {\lt} q {\lt} 2\), and suppose \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le c\, \varepsilon ^{-q}\) for all \(\varepsilon {\gt} 0\). If \(D_k(S) \le \overline D\) then, for \(k \ge 1\),

(The paper has \(S_k(\Lambda )^{q/2}\) in place of \((2S_k(\Lambda ))^{q/2}\): the factor \(2\) is the price of comparing the internal covering number in \(d_S\) with the external one in \(d_\infty \).)

(Profiles from the envelope, ‘cor:envelope-profiles‘.) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, \(\overline D {\gt} 0\), \(k \ge 1\) and \(D_k(S) \le \overline D\).

1. (Parametric layers.) If \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le p\log (C/\varepsilon )\) for all \(0 {\lt} \varepsilon \le C\), with \(p \ge 0\) and \(C \ge \overline D\), then for \(0 {\lt} \varepsilon \le \overline D\), \(\log N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le \log (k+1) + kp[\log (C/\varepsilon ) + \log S_k(\Lambda )]\), and \(\mathsf V_k(S) \le \overline D\bigl(\sqrt{\log (k+1)} + \sqrt{kp\log k} + k\sqrt{p\log \Lambda _+} + \sqrt{kp}\, (\sqrt{\log (2C/\overline D)} + \sqrt\pi /2)\bigr)\).

2. (Nonparametric layers.) If \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le c\, \varepsilon ^{-q}\) for all \(\varepsilon {\gt} 0\), with \(c \ge 0\) and \(0 {\lt} q {\lt} 2\), then for \(\varepsilon {\gt} 0\), \(\log N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le \log (k+1) + kc\, S_k(\Lambda )^q\varepsilon ^{-q}\), and \(\mathsf V_k(S) \le \overline D\sqrt{\log (k+1)} + \sqrt{kc}\, (2S_k(\Lambda ))^{q/2}\, \overline D^{\, 1-q/2}/(1-q/2)\).

See ‘cor:envelope-profiles-a‘ and ‘cor:envelope-profiles-b‘ for the factors \(2\).

(Reachable radius, unified form.) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, \(x_0 \in \mathcal X\), \(c \ge 0\) with \(d(f(x_0), x_0) \le c\) for all \(f \in F\), and \(R \ge 0\). Then every \(g \in B(k,F)\) maps \(B(x_0, R)\) into \(B\bigl(x_0, \Lambda _+^kR + c\, S_k(\Lambda )\bigr)\), \(\Lambda _+ := \max \{ 1,\Lambda \} \): for \(d(x,x_0) \le \rho \), \(d(f(x), x_0) \le d(f(x), f(x_0)) + d(f(x_0), x_0) \le \Lambda \rho + c\); iterate.

(Reachable radius, \(\Lambda \ge 1\).) Under the hypotheses of ‘lem:reachable-radius-core‘, if \(\Lambda \ge 1\) then every \(g \in B(k,F)\) maps \(B(x_0,R)\) into \(B\bigl(x_0, \Lambda ^kR + c\, S_k(\Lambda )\bigr)\).

(Reachable radius, \(\Lambda \le 1\).) Under the hypotheses of ‘lem:reachable-radius-core‘, if \(\Lambda \le 1\) then every \(g \in B(k,F)\) maps \(B(x_0,R)\) into \(B\bigl(x_0, R + c\, S_k(\Lambda )\bigr)\).

If \(d(f(x_i), g(x_i)) \le D\) for every sample point, with \(D \ge 0\), then \(d_S(f,g) \le D\).

(Diameter of the reachable states.) Under the hypotheses of ‘lem:reachable-radius-core‘, if the sample lies in \(B(x_0, R)\) then \(D_k(S) \le 2\bigl(\Lambda _+^kR + c\, S_k(\Lambda )\bigr)\): bounded in \(k\) if \(\Lambda {\lt} 1\), at most linear if \(\Lambda = 1\), at most exponential if \(\Lambda {\gt} 1\).

(Reachable radius.) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, \(x_0 \in \mathcal X\), \(R \ge 0\), and suppose \(d(f(x_0), x_0) \le c\) for all \(f \in F\) (with \(c \ge 0\)). Then every \(g \in B(k,F)\) maps the ball \(B(x_0,R)\) into \(B\bigl(x_0, \Lambda ^kR + c\, S_k(\Lambda )\bigr)\) when \(\Lambda \ge 1\), and into \(B\bigl(x_0, R + c\, S_k(\Lambda )\bigr)\) when \(\Lambda \le 1\). Consequently, if \(S \subset B(x_0,R)\), then \(D_k(S) \le 2\bigl(\Lambda _+^kR + c\, S_k(\Lambda )\bigr)\) with \(\Lambda _+ = \max \{ 1,\Lambda \} \): bounded in \(k\) if \(\Lambda {\lt} 1\), at most linear if \(\Lambda = 1\), and at most exponential if \(\Lambda {\gt} 1\).