4
$\begingroup$

Let $X\subseteq Y$ be a dense subset of a metric space $(Y,\rho)$. Let $\varepsilon>0$, $A\subseteq Y$ and let $N(A,\varepsilon)$ denote the external $\varepsilon$-covering number of $A$; i.e. the minimum number of open $\varepsilon$-balls covering $A$ *centered at points in $Y$, but possibly not centered at points in $A$). Is it true that $$ c N(Y,\varepsilon) \le N(X,\varepsilon) \le C N(Y,\varepsilon)? $$ for constants $0<c\le C$ not depending on $\varepsilon$.

In other words: is metric entropy characterized by dense subsets?

$\endgroup$
5
  • 1
    $\begingroup$ Do you mean the internal or external covering number of $X$? By closed or open balls? $\endgroup$ Commented Mar 30 at 16:29
  • 1
    $\begingroup$ @IosifPinelis external covering number, or else I'm not sure it would be true $\endgroup$ Commented Mar 30 at 16:59
  • $\begingroup$ This is probably obvious to others, but what does $\smilefrown$ mean or the significance of its use? $\endgroup$ Commented Mar 30 at 17:25
  • 1
    $\begingroup$ Covering by closed or open balls? $\endgroup$ Commented Mar 30 at 18:20
  • $\begingroup$ @IosifPinelis Open balls and TheoOtherTerry up to constants independant of $\varepsilon$ $\endgroup$ Commented Mar 30 at 19:16

1 Answer 1

5
$\begingroup$

$\newcommand{\supp}{\mathop{supp}}$ The answer to the question as stated is negative, let $Y$ be a closed $\ell_{\infty}$ ball of radius $\varepsilon$ in $\mathbb{R}^d$ (equipped with metric $\ell_\infty$) and let $X$ be the interior of $Y$ (so that indeed $X$ is dense in $Y$).

Then $N(X, \varepsilon) = 1$ (we can cover $X$ by a single open ball in the origin). Whenever $X \subset Y$ we have $N(X, \varepsilon) \leq N(Y, \varepsilon)$, so this inequality is satisfied, but $N(Y, \varepsilon) \geq 2^d$ - all corners $\{\pm 1\}^d$ need to be covered by a different open ball.

On the other hand, when $X$ is dense in $Y$ we have for every $\varepsilon' > \varepsilon$ we have $N(Y, \varepsilon') \leq N(X, \varepsilon)$, which for many practical purposes is enough.

EDIT: As I understand now from comments, the constants $c$ and $C$ are not supposed to be universal -- they are allowed to depend on $X$ and $Y$. We will use the observation above, to show a counterexample for this statement as well, and moreover one where $Y$ is compact.

Indeed, let us consider $Y$ a disjoint union of $\frac{1}{k} B_\infty^{f(k)}$ over $k \in \mathbb{N}$ -- a $f(k)$-dimensional $\ell_\infty$ balls of radius $1/k$, and glue them along the common $0$. Now take $X$ --- a union of all interiors of $\frac{1}{k} B_{\infty}^{f(k)}$, for some fast growing function $f(k)$.

Concretely, taking $F(k) := \sum_{j < k} f(j)$, we can define $Y$ as a subset of $\ell_{\infty}$ given by $$ Y = \bigcup_k \{ x \in \ell_{\infty} : \supp(x) \subset [F(k), F(k) + f(k)), \|x\|_{\infty} \leq 1/k \}, $$ and $$ X = \bigcup_k \{ x \in \ell_{\infty} : \supp(x) \subset [F(k), F(k) + f(k)), \|x\|_{\infty} < 1/k \}, $$ with the induced metric from $\ell_{\infty}$. (Above $\supp(x) := \{ i : x_i \not= 0\}$.)

Then $$N(X, 1/k) = 1 + \sum_{j < k} N(\frac{1}{j} B_{\infty}^{f(j)}, 1/k) \leq 1 + \sum_{j < k} (2k)^{f(j)},$$ and $$N(Y, 1/k) \geq N(B_{\infty}^{f(k)}, 1) \geq 2^{f(k)}.$$

We can now pick $f(k)$ growing fast enough, so that for every possible $C$, there is $f(k)$ s.t. $$ 2^{f(k)} > C \sum_{j < k} (2k)^{f(j)}, $$ for example $f(1) = 1$ and for $k > 1$, $$ f(k) := \log_2 ( k \sum_{j < k} (2k)^{f(j)}). $$

$\endgroup$
6
  • 1
    $\begingroup$ The OP asked about constants $c$ and $C$ not depending on $\varepsilon$, but I think they may depend on $X$ and $Y$. $\endgroup$ Commented Mar 30 at 21:03
  • 1
    $\begingroup$ Thanks, I misunderstood the question. Updated the answer now to handle this case. $\endgroup$ Commented Mar 30 at 22:09
  • 1
    $\begingroup$ I think the metric on $Y$ should be explicitly specified. Also, apparently you mean $(2k)^{f(j)}$ in place of $(1/k)^{f(j)}$. $\endgroup$ Commented Mar 31 at 1:52
  • 1
    $\begingroup$ Thanks, yes, I fixed the typo and specified explicitly the metric now. $\endgroup$ Commented Mar 31 at 17:22
  • 1
    $\begingroup$ Thanks I just finished reading the proof, amazing explanation of both interpretations; Thanks Jarosław :) $\endgroup$ Commented Apr 8 at 2:23

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.