# $L_1$ norm and $L_2$ norm inequalities

I need your expertise in the understanding the following problem:

Given a convex set $C \subseteq \mathbb{R}^n$, and let $a,b \in C$ such that: $$a = \arg\max_{x \in C} \left\| x\right\|_2 \\ b = \arg\max_{x \in C} \left\| x \right\|_1$$

Its known that: (same for $b$) $$\left\| a\right\|_2 \leq \left\| a \right\|_1 \leq \sqrt{n} \left\| a\right\|_2$$

Is it possible that: $$\left\| a \right\|_2 > \left\| b \right\|_2$$

Please advise and thanks in advance.

• What do you understand under $\|\cdot\|_1$ and $\|\cdot\|_2$? Two arbitrary norms, or the usual $\sum_i |x_i|$ and $\sqrt{\sum_ix_i^2}$? – TZakrevskiy Apr 24 '17 at 14:13
• Right. I cant think of an example where that occurs i.e. $\left\| a \right\|_2 > \left\| b \right\|_2$ – user3492773 Apr 24 '17 at 14:20
• You can think of $L_1$ as the Manhattan distance and $L_2$ as the euclidean distance. – user3492773 Apr 24 '17 at 14:36

## 1 Answer

Just take two points, $x=(1,0)$ and $y=\left(\frac{0.99}{\sqrt 2},\frac{0.99}{\sqrt 2}\right)$, and let $C$ be a convex hull of these two points.

Clearly, $$\|y\|_2 = 0.99<\|x\|_2=1,\quad \|y_1\|=0.99\cdot \sqrt 2>1=\|x\|_1.$$ Hence $$\arg\max_{z\in C} \|z\|_2 = x,\\\arg\max_{z\in C} \|z\|_1 = y,$$ and $\|y\|_2<\|x\|_2$.

The idea is to look at level sets of your two norms and choose the points where supremums are attained.

• Can we bound the maximum distance between $x$ and $y$ disregarding what $C$ contains (it must be convex though)? – user3492773 Apr 24 '17 at 15:24
• @Michael the distance in which norm? Given the symmetry of the norms, I'd say that the best estimation that you can get without additional hypothesis is $\|x-y\|_2\le 2\|x\|_2$. – TZakrevskiy Apr 24 '17 at 15:27