Números de cobertura del espacio métrico

Question

Actualmente estoy leyendo un artículo "On the foundations of machine learning" de F.Cucker y S.Smale y me he atascado en un problema aparentemente sencillo.

Para demostrar una desigualdad que da un límite al número de cobertura de un espacio de Banach de dimensión finita, los autores introdujeron dos números:

Dejemos que $S$ sea un espacio métrico. Para $k\geq1$ definir:

$ \varepsilon_{k}(S) = \inf \left\lbrace \varepsilon >0 : \exists \text{ closed balls $ D_{1}, _{puntos}, D_{k} $ with radius $ \N -varepsilon $ covering S}\right\rbrace $

$ \varphi_{k}(S) =\sup \left\lbrace \delta>0 : \exists \; x_{1}, ..., x_{k+1} \in S \text{ such that for $ i \neq j $, $ d(x_{i}, x_{j})>2\Ndelta $} \right\rbrace $

Y entonces, escribieron un lema:

Para todos $ k \geq 1$ , $\varphi_{k}(S) \leq \varepsilon_{k}(S) \leq 2\varphi_{k}(S)$ .

La demostración de este lema se reduce a la afirmación "es fácil de demostrar", pero desgraciadamente no lo he conseguido. Agradecería cualquier ayuda o pista.

Además, es mi primera exposición a los números de cobertura y ni siquiera sé cuáles son los nombres de los números definidos anteriormente, por lo que tengo problemas para encontrar recursos útiles sobre este tema.

Answer 1

Para mostrar $\varphi_k(S) \le \varepsilon_k(S)$ Supongamos que $\varepsilon > 0$ es tal que hay bolas cerradas $D_1, \dots, D_k$ de radio $\varepsilon$ que cubren $S$ . Supongamos ahora que $x_1, \dots, x_{k+1}$ son cualquier $k+1$ puntos en $S$ . Por el principio de encasillamiento, dos de esos puntos deben estar contenidos en uno de los $D_i$ por lo que por la desigualdad del triángulo la distancia entre esos dos puntos es menor que $2\varepsilon$ . Por lo tanto, no existen $k+1$ puntos con distancias entre pares mayores que $2\varepsilon$ Así que $\varphi_k(S) \le \varepsilon$ . Tomando el ínfimo de todos esos $\varepsilon$ muestra $\varphi_k(S) \le \varepsilon_k(S)$ .

Para la segunda desigualdad, supongamos $\varepsilon < \varepsilon_k(S)$ . Eso significa que no se puede cubrir $S$ con $k$ bolas de radio $\varepsilon$ . Así que construye una secuencia de puntos $x_1, \dots, x_{k+1}$ de la siguiente manera. Elija $x_1 \in S$ de forma arbitraria. Entonces, recursivamente, si $n \le k$ y $x_1, \dots, x_n$ ya han sido elegidos, por la suposición de que las bolas $B(x_i, \varepsilon)$ , $i=1,\dots, n$ no cubren $S$ , por lo que podemos elegir $x_{n+1} \in S \setminus \left(\bigcup_{i=1}^n B(X_i, \varepsilon)\right)$ . Esta construcción produce $k+1$ puntos con distancias entre pares de al menos $\varepsilon$ Así que $\varphi_k(S) \ge \varepsilon/2$ o en otras palabras $2 \varphi_k(S) \ge \varepsilon$ . Ahora dejemos que $\varepsilon \uparrow \varepsilon_k(S)$ para obtener el resultado.