# Proofs regarding standard norms, $l^p$ spaces

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.

• 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$. – mizichael Mar 1 '17 at 19:10
• 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! – mizichael Mar 1 '17 at 20:08