ε-Entropy and Hausdorff Measures

A set $E \subset \mathbb {R}^{n}$ is called $\varepsilon$-separated if the distance between any two of its points is not less than $\varepsilon$. Let

be the maximal cardinality of an $\varepsilon$-separated subset of the set $A$. Prove that

Let $A$ be a bounded subset of the space $\mathbb {R}^{n}$.

Find the asymptotics (as $\varepsilon \rightarrow +0$) of the $\varepsilon$-entropy of the sets:

Let $E \subset \mathbb {R}^{n}$ be a bounded set, $0<\lambda_{n}(E)<\infty$, and let $M(E, \varepsilon )$ be the maximal number of $\varepsilon$-separated points lying in $E$. Prove that

where $E_{\varepsilon / 2}$ is the $(\varepsilon / 2)$-neighborhood of the set $E, \quad \alpha_{n}$ is the volume of the $n$-dimensional unit ball.

The metric dimension $M-\operatorname {dim}(A)$ and the metric order $r(A)$ of a bounded subset $A$ of the space $\mathbb {R}^{n}$ are the quantities $M-\operatorname {dim}(A)=\varlimsup_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, $r(A)=\varliminf_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, where $H(A, \varepsilon )=\log_{2} N(A, \varepsilon )$ is the $\varepsilon$-entropy of the set $A$, and $N(A, \varepsilon )$ is the minimal cardinality of an $\varepsilon$-net for $A$, i.e. of a set $C$ such that $A \subset \bigcup_{x \in C} B(x, \varepsilon )$. Find the metric dimensions and metric orders of the graphs of the following functions:

The metric dimension $M-\operatorname {dim}(A)$ and the metric order $r(A)$ of a bounded subset $A$ of the space $\mathbb {R}^{n}$ are the quantities $M-\operatorname {dim}(A)=\varlimsup_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, $r(A)=\varliminf_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, where $H(A, \varepsilon )=\log_{2} N(A, \varepsilon )$ is the $\varepsilon$-entropy of the set $A$, and $N(A, \varepsilon )$ is the minimal cardinality of an $\varepsilon$-net for $A$, i.e. of a set $C$ such that $A \subset \bigcup_{x \in C} B(x, \varepsilon )$. Find the metric dimensions and metric orders of the following sets:

The metric dimension $M-\operatorname {dim}(A)$ and the metric order $r(A)$ of a bounded subset $A$ of the space $\mathbb {R}^{n}$ are the quantities $M-\operatorname {dim}(A)=\varlimsup_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, $r(A)=\varliminf_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, where $H(A, \varepsilon )=\log_{2} N(A, \varepsilon )$ is the $\varepsilon$-entropy of the set $A$, and $N(A, \varepsilon )$ is the minimal cardinality of an $\varepsilon$-net for $A$, i.e. of a set $C$ such that $A \subset \bigcup_{x \in C} B(x, \varepsilon )$. Find the metric dimensions and metric orders of the following sets:

The metric dimension $M-\operatorname {dim}(A)$ and the metric order $r(A)$ of a bounded subset $A$ of the space $\mathbb {R}^{n}$ are the quantities $M-\operatorname {dim}(A)=\varlimsup_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, $r(A)=\varliminf_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, where $H(A, \varepsilon )=\log_{2} N(A, \varepsilon )$ is the $\varepsilon$-entropy of the set $A$, and $N(A, \varepsilon )$ is the minimal cardinality of an $\varepsilon$-net for $A$, i.e. of a set $C$ such that $A \subset \bigcup_{x \in C} B(x, \varepsilon )$. Find the metric dimension and metric order of the Cantor set (see Problem I.1.29).

Find the asymptotics of the $\varepsilon$-entropy of the set

The metric dimension $M-\operatorname {dim}(A)$ and the metric order $r(A)$ of a bounded subset $A$ of the space $\mathbb {R}^{n}$ are the quantities $M-\operatorname {dim}(A)=\varlimsup_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, $r(A)=\varliminf_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, where $H(A, \varepsilon )=\log_{2} N(A, \varepsilon )$ is the $\varepsilon$-entropy of the set $A$, and $N(A, \varepsilon )$ is the minimal cardinality of an $\varepsilon$-net for $A$, i.e. of a set $C$ such that $A \subset \bigcup_{x \in C} B(x, \varepsilon )$.

Define an increasing sequence $\left\{ n_{k}\right\}$ of natural numbers by setting $n_{k}=k+m!$ if $m!\leqslant k<(m+1)!$, and consider the set

Next, let

Prove that

Let $\Psi :[0,+\infty ) \rightarrow [0,+\infty )$ be a strictly increasing function such that $\Psi (\mathbb {N}) \subset \mathbb {N}$. Consider the set

Prove that $H(A, \varepsilon ) \sim \Psi^{-1}\left(\log_{2} \frac{1}{\varepsilon }\right)$ as $\varepsilon \rightarrow +0$.

The metric dimension $M-\operatorname {dim}(A)$ and the metric order $r(A)$ of a bounded subset $A$ of the space $\mathbb {R}^{n}$ are the quantities $M-\operatorname {dim}(A)=\varlimsup_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, $r(A)=\varliminf_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, where $H(A, \varepsilon )=\log_{2} N(A, \varepsilon )$ is the $\varepsilon$-entropy of the set $A$, and $N(A, \varepsilon )$ is the minimal cardinality of an $\varepsilon$-net for $A$, i.e. of a set $C$ such that $A \subset \bigcup_{x \in C} B(x, \varepsilon )$. Find the metric dimension and metric order of the set

(the Hironaka curve).

The metric order of a bounded subset $A$ of the space $\mathbb {R}^{n}$ is the quantity $r(A)=\varliminf_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, where $H(A, \varepsilon )=\log_{2} N(A, \varepsilon )$ is the $\varepsilon$-entropy of the set $A$, and $N(A, \varepsilon )$ is the minimal cardinality of an $\varepsilon$-net for $A$, i.e. of a set $C$ such that $A \subset \bigcup_{x \in C} B(x, \varepsilon )$. Let $A \subset \mathbb {R}, A_{m}=A+\ldots +A$ ($m$ summands). Prove that

Hausdorff measures. Let $A \subset \mathbb {R}^{n}, p, \varepsilon >0$. Set

Note that in the definition of $\nu_{p}(A, \varepsilon )$ the infimum is taken over all countable coverings of the set $A$ by balls, including those whose centers do not belong to $A$. The function $\nu_{p}$, defined on the system of all subsets of the space $\mathbb {R}^{n}$ by the equality

is called the $p$-dimensional (outer) Hausdorff measure.

Let $p>0$. Prove that

Let $A \subset \mathbb {R}^{n}$. Prove that

Let $A \subset S^{n-1}, \mu_{n-1}$ be Lebesgue measure on $S^{n-1}$ ("surface area"). Prove that

Prove that

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. $H(A, \varepsilon )=\log_{2} N(A, \varepsilon )$ denotes the $\varepsilon$-entropy of the set $A$, where $N(A, \varepsilon )$ is the minimal cardinality of an $\varepsilon$-net for $A$.

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. The diameter of a bounded set $C \subset \mathbb {R}^{n}$ is the number $\operatorname {diam}(C)=\sup \left\{ \left\| x-y\right\| \mid x, y \in C\right\}$. Let $p>0, A \subset \mathbb {R}^{n}$. Define the modified $p$-dimensional Hausdorff measure $\widetilde{\nu }_{p}(A)$ as follows:

Prove that $\nu_{p}(A) \leqslant \widetilde{\nu }_{p}(A) \leqslant 2^{p} \nu_{p}(A)$ and, consequently, in the definition of Hausdorff dimension one may use $\widetilde{\nu }_{p}$ in place of $\nu_{p}$.

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. Find the Hausdorff dimension $p$ and compute the Hausdorff measure $\nu_{p}$ of the following sets:

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. Find the Hausdorff dimension $p$ and compute $\nu_{p}(C)$ for the Cantor set $C$. Prove that the function $\varphi$ defined by the equality

coincides with the Cantor function (see the definition before Problem III.3.14).

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. The metric dimension of a bounded set $A \subset \mathbb {R}^{n}$ is the quantity $M-\operatorname {dim}(A)=\varlimsup_{\varepsilon \rightarrow +0} \frac{H(A, \varepsilon )}{\log_{2}(1 / \varepsilon )}$, where $H(A, \varepsilon )=\log_{2} N(A, \varepsilon )$ is the $\varepsilon$-entropy of the set $A$, and $N(A, \varepsilon )$ is the minimal cardinality of an $\varepsilon$-net for $A$, i.e. of a set $C$ such that $A \subset \bigcup_{x \in C} B(x, \varepsilon )$. Find $\operatorname {dim}_{H}(A)$ and $M-\operatorname {dim}(A)$ for the following sets:

Let $E \subset [0,1]$ be a homogeneous generalized Cantor set, $0<\nu_{p}(E)<\infty , \sigma_{E}$ the corresponding Cantor function (see III.3.17). Prove that

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. Let $0<p \leqslant 1, E \subset \mathbb {R}$ be a homogeneous generalized Cantor set, $l_{n}$ the length of the intervals of rank $n$. Prove that

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. Let $E$ be a homogeneous generalized Cantor set, $\sigma$ the corresponding Cantor function (see III.3.17), and let

Prove that

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. Let $A$ be the set from problem 5.10.

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. Let $A, B$ be homogeneous generalized Cantor sets with defining sequences $\left\{ 3^{-n} /(n+1)\right\}_{n \geqslant 0}$ and $\left\{ 3^{-n} \sqrt{n+1}\right\}_{n \geqslant 0}$ respectively, and let $p=\operatorname {dim}_{H}(A), q=\operatorname {dim}_{H}(B)$. Prove that

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. Let $n \in \mathbb {N}, E \subset \left\{ 0, \ldots , n-1\right\} , m=\operatorname {card}(E), 1 \leqslant m<n$. Find the Hausdorff dimension of the set

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. Let

for any k Nright .

Find $\operatorname {dim}_{H}(A)$ and $\operatorname {dim}_{H}(A+A)$ and confirm that $\operatorname {dim}_{H}(A)>\frac{1}{2}$, but $\operatorname {dim}_{H}(A+A)<1$.

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. A set $E \subset \mathbb {R}^{n}$ is called $\theta$-uniformly superporous, $0<\theta <1$, if for any $x \in \mathbb {R}^{n}, r>0$ there is a point $y \in B(x, r)$ such that $E \cap B(y, \theta r)=\varnothing$. Prove that there exists a number $d(\theta )<n$ such that every $\theta$-uniformly superporous set has Hausdorff dimension no greater than $d(\theta )$.

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. A set $B \subset \mathbb {R}^{n}$ will be called homothetic to a set $A \subset \mathbb {R}^{n}$ if $B=x_{0}+t A$, where $t>0$. The number $t$ will be called the coefficient of homothety. Consider a centrally symmetric convex compact set $A$ with nonempty interior. We will exhaust a bounded open set $G \subset \mathbb {R}^{n}$ by sets homothetic to $A$ as follows. At the first step, consider a set $B$ homothetic to $A$, contained in $\bar{G}$, with maximal homothety coefficient (as is easily verified, such a set exists). Put $G_{1}=G \backslash B$. Replacing $G$ by $G_{1}$ and repeating the procedure, we obtain a set $G_{2}$, and so on. Consider the intersection $C=\bigcap_{k \geqslant 1} G_{k}$.

Prove that $\operatorname {dim}_{H}(C) \leqslant d(n)<n$, where $d(n)$ is some number not depending on the choice of $A$ and $G$. In other words, the set $G$ is exhausted by sets homothetic to $A$, up to a remainder whose Hausdorff dimension is "substantially less" than $n$.

The Hausdorff dimension of a set $A$ is the number $\operatorname {dim}_{H}(A)=\inf \left\{ q \mid \nu_{q}(A)=0\right\} =\sup \left\{ q \mid \nu_{q}(A)=\infty \right\}$, where $\nu_{q}$ is the $q$-dimensional (outer) Hausdorff measure. Let $K$ be a generalized homogeneous Cantor set, $\operatorname {dim}_{H}(K)>\frac{1}{2}$. Prove that there exists a continuous function $\varphi : \mathbb {C} \rightarrow \mathbb {C}$ such that $\lim_{z \rightarrow \infty } z \varphi (z)=1$ and $\varphi$ is holomorphic outside the set $K \times K$ (compare with problem 4.11).