2
$\begingroup$

I want to show that in $\mathbb{R^n}$ the following two inequalities hold:

$\lVert x \rVert_2 \leq \lVert x \rVert_1 \leq \sqrt n \lVert x \rVert_2$

$\frac{1}{\sqrt n} \lVert x \rVert_2 \leq \lVert x \rVert_{\infty} \leq \lVert x \rVert_2$

So here is my try:

First a definition: Two norm $\lVert . \rVert_{a}$ and $ \lVert . \rVert_{b}$ are equivalent if there exists numbers $0<m \leq M$ such that for all $x \in \mathbb{R^n}$:

$m\lVert x \rVert_a \leq \lVert x \rVert_{b} \leq M \lVert x \rVert_a $

I want to show that any norm $\lVert . \rVert$ on $\mathbb{R^n}$ is equivalent to the euclidean norm.

$\lVert x \rVert =\lVert \lambda_1 e_1+...+\lambda_n e_n \rVert $

Let $A := \mathrm{max} \{\lVert e_1 \rVert,...,\lVert e_n \rVert \}$

We have $\lVert x \rVert \leq |\lambda_1| \lVert e_1 \rVert +...+|\lambda_n| \lVert e_n \rVert$

by the holder inequality I further get:

$\leq \sqrt{|\lambda_1|^n+...+|\lambda_n|^2} \sqrt{\lVert e_1 \rVert ^2+...+\lVert e_n \rVert^2 }$

$\lVert x\rVert \leq A \sqrt{n} \lVert x \rVert_2$

This means that $\lVert . \rVert$ is continous with respect to $\lVert . \rVert_2$ because if $\lVert x_k-x \rVert_2 \rightarrow 0 $ then

$|\lVert x_k \rVert - \lVert x \rVert| \leq \lVert x_k -x \rVert \leq A \sqrt n \lVert x_x-x \rVert_2 \rightarrow 0 $ (1)

Define the set $S:={x \in \mathbb{R} : \lVert x \rVert_2=1}$.

Since $S= \lVert . \rVert_{2} ^{-1}({1})$ $S$ is closed in $\mathbb{R}, \lVert . \rVert_2$ Further, $S$ is also bounded, this means that $S$ is a compact set.

Because of (1), $\lVert . \rVert$ is also continuous. This means that $min_{s \in S} \lVert s \rVert=:m$

Now the vector $\frac{x}{\lVert x \rVert_2}$ is a unit vector, hence $\frac{x}{\lVert x \rVert_2} \in S$.

So we get: $m \leq \lVert \frac{x}{\lVert x \rVert_2} \rVert$

Thus I get: $m \lVert x \rVert_2 \leq \lVert x \rVert $

My prolem:

I don't really know how to argue that $m>0$ (or if this is even possible in my attempt).

If my calculation is possible I would get with ease:

$m\lVert x \rVert_2 \leq \lVert x \rVert_1 \leq \sqrt n \lVert x \rVert_2$

And would just need to show that $m=1$

While doing this I came up with the following question:

Are $m$ and $M$ in the two inequalities above chosen in an "optimal" way, e.g. for which constants would I get $m \lVert x \rVert_2 < \lVert x \rVert_1 < M \lVert x \rVert_2$

$\endgroup$

1 Answer 1

1
$\begingroup$

Here's the argument that you want in the end.

Suppose you have an arbitrary norm on $\mathbb R^n$, call it $\| \cdot \|_{\alpha}$ (I don't know why you put $\mathbb n$ in the exponent here, that's not necessary). Write $\| \cdot \|_2$ for the standard Euclidean norm (the $2$-norm of the $L^p$-norms).

You need to be careful with topological arguments, especially when discussing normed spaces, because different norms induce different topologies. But for the sake of discussion, we only endow $\mathbb R^n$ with the topology coming from the $\| \cdot \|_2$ norm, so there's only one topology involved and Heine-Borel's theorem (compact $\Leftrightarrow$ closed and bounded) holds just fine as it's the classical topology in which it is usually proven.

So you've shown that $\| \cdot \|_{\alpha}$ is a continuous function on the unit sphere (that's your set $S$, namely $\{ x \in \mathbb R^n : \|x\|_2 = 1 \}$):

$$ |\|x\|_{\alpha} - \|y\|_{\alpha}| \le \|x-y\|_{\alpha} \le A \sqrt n \|x\|_2 $$ where $A = \max\{\|e_1\|_{\alpha}, \cdots, \|e_n\|_{\alpha}\}$ (kudos for seeing the argument there!). This shows that $\|x\|_{\alpha}$ is a $K$-Lipschitz function with $K = A \sqrt n$, and therefore is continuous. You used the sequential argument for that, but it's always cool to see the properties our functions have, just in case it's useful.

The function $x \mapsto \|x\|_{\alpha}$ is continuous on a compact, thus attains its minimum and maximum on $S$. Call them $m$ and $M$ respectively. Therefore, $$ m \le \left\| \frac {x}{\left\| x \right\|_2} \right\|_{\alpha} \le M $$ and so $$ m \left\| x \right\|_2 \le \left\| x \right\|_{\alpha} \le M \left\| x \right\|_2. $$ Your remaining question: why is $m > 0$? Well, $m = \|x\|_{\alpha}$ for $x \in S$. If $m=0$, then since $\|x\|_{\alpha}$ is a norm, that would imply $x = 0$, but $x \in S$, a contradiction.

Also note that norm equivalence is an equivalence: since we've proven that $\| \cdot \|_{\alpha} \sim \|\cdot \|_2$, we don't have to prove $\| \cdot \|_2 \sim \|\cdot \|_{\alpha}$; it immediately follows that $$ (1/M) \left\| x \right\|_{\alpha} \le \left\| x \right\|_2 \le (1/m) \left\| x \right\|_{\alpha}. $$

Edit: As requested in the comments, you wanted to compute $m$ and $M$ in the case where $\| \cdot \|_{\alpha}$ is the $1$-norm. If you follow the steps of the proof, we have to minimize/maximize the $1$-norm over the unit sphere (in the $2$-norm, so the standard unit sphere that looks like an actual sphere!).

So were looking to find extrema of $\sum_{i=1}^n |\lambda_i|$ on the surface $\sum_{i=1}^n \lambda_i^2 = 1$. By symmetry, we can assume all $\lambda_i \ge 0$. Since they are now positive, we can also replace $\lambda_i$ by their squares. So we now have a smooth problem: we try to find extremas of $f(\lambda_1, \cdots, \lambda_n) = \sum_{i=1}^n \lambda_i^2$ on the surface $g(\lambda_1,\cdots,\lambda_n) = \sum_{i=1}^n \lambda_i^4 = 1$. We still want $\lambda_i \ge 0$, but the same symmetry is present, so we don't need to worry about boundary conditions; we can literally ignore them. Note that even in the new problem, we'll still find the same extremal values (i.e. minimum and maximum value taken), although the inputs won't be the same, but we don't care about that right now since we are computing $m$ and $M$.

Now we compute the gradients of both functions $f$ and $g$: $$ \nabla f(\lambda_1,\cdots,\lambda_n) = 2(\lambda_1,\cdots,\lambda_n), \qquad \nabla g(\lambda_1,\cdots,\lambda_n) = 4(\lambda_1^3, \cdots, \lambda_n^3). $$ so we know that at extremal points, there exists $c$ with $$ 2(\lambda_1,\cdots,\lambda_n) = \nabla f = c \nabla g = 4c (\lambda_1^3, \cdots, \lambda_n^3) $$ This now leads to the set of $n$ equations $$ 2c \lambda_i^3 - \lambda_i = 0. $$ We cannot have all $\lambda_i$ equal to zero, so one of them is not. Say it is $\lambda_1$. This leads to $$ 2c \lambda_1^2 - 1 = 0 \quad \Rightarrow \quad \lambda_1 = \frac{\pm 1}{\sqrt{2c}}. $$ This means that each $\lambda_i$ can only take the values $- \frac 1{\sqrt{2c}}$, $0$, or $\frac 1{\sqrt{2c}}$.

The sign doesn't affect the values of $f$, so we'll omit the negative case moving forward.

To compute $c$, take all the indices $i$ for which $\lambda_i \neq 0$, call $I$ the set of such $i$'s and notice that $$ 1 = \sum_{i=1}^n \lambda_i^4 = \sum_{i \in I} \lambda_i^4 = \sum_{i \in I} \left( \frac 1{\sqrt{2c}} \right)^4 = \frac{|I|}{4c^2} $$ so that $c = \frac{\sqrt{|I|}}2$. For each value of $|I|$, we get the values of $f$ corresponding to potential extremas: $$ \sum_{i=1}^{|I|} \lambda_i^2 = \sum_{i=1}^{|I|} \left(\frac 1{\sqrt {2c(|I|)}} \right)^2 = \sum_{i=1}^I \frac 1{2c(|I|)} = \frac{|I|}{2 \frac{\sqrt{|I|}}2 } = \sqrt{|I|}. $$ Since $|I|$ takes values ranging from $1$ to $n$, we see that $m=1$ and $M=\sqrt n$.

Hope that helps,

$\endgroup$
4
  • 1
    $\begingroup$ Yes this helped, thank you. There remains one question. If one now considers $\lVert x\rVert_2 \leq \lVert x\rVert_1 \leq \sqrt n \lVert x \rVert_2$. Are the constants $m=1$ and $M=\sqrt n$ the optimal choice, i.e. are there smaller constants $m_1, M_2$ such that the inequality would stil hold? I think the answer is no, but I am not really sure. To show this I would (I think) have to show that for smaller constants the "less or equal" would be just "less". $\endgroup$
    – John.W
    May 1 at 17:21
  • 1
    $\begingroup$ @John.W I'll need some space for that. $\endgroup$ May 1 at 17:43
  • 1
    $\begingroup$ @John.W: That took some extra work, gimme that green check! $\endgroup$ May 1 at 18:27
  • 1
    $\begingroup$ Thank you very very much! $\endgroup$
    – John.W
    May 1 at 20:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .