Question

Let \(X\) be a normed space, \(M \subset X\) and \(\varepsilon>0 .\) We say that \(A \subset M\) is an \(\varepsilon=n e t\) in \(M\) if for every \(x \in M\) there is \(y \in A\) such that \(\|x-y\|<\varepsilon\). We say that \(A \subset M\) is \(\varepsilon\) -separated in \(M\) if \(\|x-y\| \geq \varepsilon\) for all \(x \neq y \in A\). Clearly, a maximal \(\varepsilon\) -separated subset of \(M\) in the sense of inclusion is an \(\varepsilon\) -net in \(M\). Let \(X\) be an \(n\) -dimensional real normed space. Show that if \(\left\\{x_{j}\right\\}_{j=1}^{N}\) is an \(\varepsilon\) -net in \(B_{X}\), then \(N \geq \varepsilon^{-n} .\) On the other hand, there is an \(\varepsilon\) -net \(\left\\{x_{j}\right\\}_{j=1}^{N}\) for \(B_{X}\) with \(N \leq\left(\frac{2}{c}+1\right)^{n}\). Hint: Fix a linear isomorphism \(T\) of \(X\) onto \(\mathbf{R}^{n}\). For a compact subset \(C\) of \(X\), we define the volume of \(C\) by \(\operatorname{vol}(C)=\lambda(T(C))\), where \(\lambda\) is the Lebesgue measure on \(\mathbf{R}^{n}\). Let \(B(x, r)\) be the closed ball centered at \(x\) with radius \(r\). We have \(B_{X} \subset \bigcup_{j=1}^{N} B\left(x_{j}, \varepsilon\right)\), so $$ \begin{aligned} \operatorname{vol}\left(B_{X}\right) & \leq \operatorname{vol}\left(\bigcup_{j=1}^{N} B\left(x_{j}, \varepsilon\right)\right) \leq \sum_{j=1}^{N} \operatorname{vol}\left(B\left(x_{j}, \varepsilon\right)\right) \\ &=N \cdot \operatorname{vol}\left(\varepsilon B_{X}\right)=N \cdot \varepsilon^{n} \cdot \operatorname{vol}\left(B_{X}\right) \end{aligned} $$ Thus \(N \geq \varepsilon^{-n}\). On the other hand, if \(\left\\{x_{j}\right\\}_{j=1}^{N}\) is a maximal \(\varepsilon\) -separated set in \(B_{X}\), then \(\left\\{x_{j}\right\\}_{j=1}^{N}\) is an \(\varepsilon\) -net in \(B_{X}\). Since \(B\left(x_{j}, \varepsilon / 2\right) \cap B\left(x_{i}, \varepsilon / 2\right)=\emptyset\) if \(i \neq j\) and \(B\left(x_{j}, \varepsilon / 2\right) \subset(1+\varepsilon / 2) B_{X}\), we have $$ \begin{aligned} N \cdot(\varepsilon / 2)^{n} \cdot \operatorname{vol}\left(B_{X}\right) &=\operatorname{vol}\left(\bigcup_{j=1}^{N} B\left(x_{j}, \varepsilon / 2\right)\right) \\ & \leq \operatorname{vol}\left((1+\varepsilon / 2) B_{X}\right)=(1+\varepsilon / 2)^{n} \operatorname{vol}\left(B_{X}\right) . \end{aligned} $$ Thus \(N \leq\left(\frac{1+\varepsilon / 2}{\varepsilon / 2}\right)^{n}\).

Short answer

N ≥ ε^{-n} and N ≤ (2/ε + 1)^n.

Step-by-step solution

Define the Volume

Consider the volume of a compact subset in the normed space as defined using a linear isomorphism and the Lebesgue measure.

Volume Inequality Setup

Establish the inequality for the volume of the union of closed balls centered at each element of the ε-net.

Apply Volume Calculation

Apply the specific volume calculation to the union, which relates to the volume of the scaled ball based on ε.

Incorporate Summation

Express the inequality as a summation over the ε-balls and simplify to find the relationship between the volumes and N.

Derive Lower Bound

Solve the inequality to show that N is greater than or equal to ε^{-n}.

Maximal ε-Separated Set

Use the properties of a maximal ε-separated set to establish another volume-based argument.

Second Volume Argument

Consider the volume of the union of smaller balls intersected with scaled balls to create another inequality.

Simplify Second Argument

Simplify the second volume inequality to derive an upper bound on N.

Combine Results

Combine both volume arguments to conclude the upper and lower bounds for N in terms of ε and n.

Key concepts

normed spaces

A normed space is a vector space equipped with a function called a norm. This norm calculates the 'length' or 'size' of vectors. The concept is crucial in understanding different geometric and functional properties of the space. For any vector \(v\) in the normed space \(X\), the norm is written as \(\|v\|\), which represents the non-negative length of \(v\). Normed spaces generalize many aspects of Euclidean spaces, allowing us to work with infinite-dimensional vectors and more complex structures.

epsilon nets

An \(\varepsilon\)-net is a subset \(A\) of a metric space \(M\) such that every point in \(M\) is within a distance of \(\varepsilon\) from some point in \(A\). This concept is useful for approximating and covering complex sets with simpler ones. Specifically, in normed spaces, if you have a set of points that form an \(\varepsilon\)-net, you can ensure that these points are close enough to cover the entire space with small balls of radius \(\varepsilon\).

Lebesgue measure

The Lebesgue measure provides a way of assigning a 'volume' to subsets of \(\mathbb{R}^n\). For an \(n\)-dimensional normed space, we can use a linear isomorphism to map our space to \(\mathbb{R}^n\), allowing us to transfer the concept of volume. The measure is consistent with our intuitive understanding of length, area, and volume in higher dimensions. Calculations involving Lebesgue measure are vital for understanding the distribution and density of points in a normed space.

volume calculation

Volume calculations in normed spaces often make use of balls centered around points and their relationships through scaling. For instance, the volume of a ball with a scaled radius, like \(\varepsilon B_X\), can be derived from the original volume times \(\varepsilon^n\) where \(n\) is the dimension of the space. Such calculations help in deriving inequalities and covering properties, as shown in exercises involving \(\varepsilon\)-nets.

separated sets

A set \(A\) is \(\varepsilon\)-separated if the distance between any two distinct points in \(A\) is at least \(\varepsilon\). This property ensures that points are 'well-spaced'. In normed spaces, a maximal \(\varepsilon\)-separated set gives rise to an \(\varepsilon\)-net. Using \(\varepsilon\)-separated sets is crucial for constructing covering arguments and understanding how different subsets of a space interrelate, ultimately helping in approximations and bounding arguments.