The following norms are standard norms in $\mathbb{R^n}$ $$||x||_1 = \sum_{i=1}^{n} |x_i|,\quad ||x||_2 = \left(\sum_{i=1}^{n} |x_i|^2\right)^{1/2},\quad ||x||_\infty = \max_{1\leq i\leq n} |x_i|$$ associated with the metric $d_1$, $d_2$, $d_\infty$ in $\mathbb{R^n}$. Show that $(a)$ We always have, for $x\in \mathbb{R^n}$, $$||x||_\infty \leq ||x||_1 \leq \sqrt{n} ||x||_2 \leq n||x||_\infty$$ $(b)$ For $E\in \mathbb{R^n}$ bounded and $\delta$ > 0, denote by $N_1(E, \delta)$, $N_2(E, \delta)$, $N_\infty(E, \delta)$ the metric entropy numbers of E associated with $d_1$, $d_2$, $d_\infty$, respectively. Then, $$N_\infty(E, \delta) \leq N_2(E, \delta) \leq N_1(E, \delta) \leq N_2(E, \delta / \sqrt{n}) \leq N_\infty(E, \delta / n).$$ $(c)$ Let $Q$ = [0,1]$^n$ be the unit cube in $\mathbb{R^n}$. Find its metric dimension with respect to the metrics $d_1, d_2, d_\infty$.

Sorry for the long problem. I just wanted to make sure all of the information that I have at my disposal is available here as well!

I'm not really sure how to prove any of these. For $(a)$ do I need to use the distance metrics at all, or should I be able to prove this inequality from the definition itself?

Sorry if I seem clueless - I just had a midterm for this class and am dead tired and thus not thinking straight. However, a push in the right direction with any part of this problem is much appreciated.

edit: I have figured out part $(a)$, but am still a little stuck on $(b)$ and $(c)$.


For $(a)$ :

  • $||x||_\infty \le ||x||_1$ : If $\max_{1\le i \le n}|x_i| = |x_k|$ then $$||x||_\infty = |x_k| \le |x_1| + \ldots + |x_k| + \ldots + |x_n| = ||x||_1$$
  • $||x||_1 \le \sqrt{n}||x||_2$ : Apply the Cauchy-Schwarz Inequality to the vectors $(|x_1|,\ldots,|x_n|)$ and $(1,\ldots,1)$.
  • $\sqrt{n}||x||_2 \le n||x||_\infty$ : For all $i\in \{1,\ldots,n\}$ we have $|x_i| \le \max_{1\le i \le n}|x_i| = ||x||_\infty$ so $$\sqrt{n}||x||_2 = \sqrt{n}\left(\sum_{i=1}^{n} |x_i|^2\right)^{1/2} \le \sqrt{n}\left(\sum_{i=1}^{n} ||x||_\infty^2\right)^{1/2} = \sqrt{n}\left(n||x||^2_\infty\right)^{1/2} = n||x||_\infty.$$

I might be able to help you for $(b)$ and $(c)$ but I'm not familiar with the terms "metric entropy" and "metric dimension".

Edit :

  • $N_\infty(E,\delta) \le N_2(E,\delta)$ : Note that we have $\forall x \in \mathbb{R}^n, ||x||_2 \ge ||x||_\infty $ so that $$ \{ y \in \mathbb{R}^n \mid ||x-y||_2 \le \delta \} \subset \{ y \in \mathbb{R}^n \mid ||x-y||_\infty \le \delta \}.$$ So if you have $N_2$ $d_2$-balls covering $E$ you just have to keep their center but consider them as $d_\infty$-balls to cover $E$ with $d_\infty$-balls and because $N_\infty$ is the minimum number of such balls you need we have $N_\infty \le N_2$.
  • $N_2(E,\delta) \le N_1(E,\delta)$ : Same reasoning as above because $\forall x\in \mathbb{R}^n,||x||_2 \le ||x||_1$.
  • $N_1(E,\delta) \le N_2(E,\frac {\delta} {\sqrt{n}})$ : Again the same thing because $\forall x\in \mathbb{R}^n,||x||_1 \le \sqrt{n}||x||_2$.
  • $N_2(E,\frac {\delta} {\sqrt{n}}) \le N_\infty(E,\frac \delta n$) : $\forall x\in \mathbb{R}^n,\sqrt{n}||x||_2 \le n||x||_\infty$.

And for $(c)$ maybe you have seen some theorems that can help ? because it might be possible to solve it "by hand" but it seems difficult.

  • $\begingroup$ Thank you for your response! For $(b)$ and $(c)$, $\delta$ → $N(E, \delta)$ is called the metric entropy function of $E$ where $N(E, \delta)$ is the minimum number of balls with radius $\delta$ needed to cover $E$. Further, define $dim(E)$ = lim sup ($\delta$ → 0) log $N(E,\delta)$ / log(1/$\delta$), and $\underline{dim(E)}$ = lim inf ($\delta$ → 0) log $N(E,\delta)$ / log(1/$\delta$). The terms $dim(E)$ and $\underline{dim(E)}$ are the upper and lower metric dimension of $E$. If $dim(E)$ = $\underline{dim(E)}$ = $\alpha$, we call $\alpha$ the metric dimension of $E$. $\endgroup$ – mizichael Mar 1 '17 at 19:10
  • $\begingroup$ Ahh, this makes sense - I was having trouble understanding the use of $d_p$ metrics in the problem but you've cleared that right up! For $(c)$ I may have to talk to my professor for help - I've been sick recently and had to miss a lecture, so they may have covered it in that lecture. Thank you for all of your help! $\endgroup$ – mizichael Mar 1 '17 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.