Prove or disprove inequality between 1-norm, 2-norm and infinity norm.

Question

Prove or disprove: $$ v\in R^n \Rightarrow ||v||_1||v||_{\infty}\leq \frac{1+\sqrt n}{2}||v||^2_2. $$

Can someone help me with this? I have used several cases to verify it but cannot come up with proof.

Answer 1

Since $v$ and its entrywise absolute value $|v|$ have the same norms, we may assume that $v=(v_1,v_2,\ldots,v_n)$ with $v_1\ge v_2\ge\cdots\ge v_n\ge0$. The inequality in question can hence be rewritten as \begin{aligned} (v_1+v_2+\cdots+v_n)v_1 &\le\frac{1+\sqrt{n}}{2}(v_1^2+v_2^2+\cdots+v_n^2),\\ v_1v_2+\cdots+v_1v_n &\le\frac{\sqrt{n}-1}{2}v_1^2+\frac{\sqrt{n}+1}{2}v_2^2+\cdots+\frac{\sqrt{n}+1}{2}v_n^2\\ &=\frac12\left[\frac{v_1^2}{\sqrt{n}+1}+(\sqrt{n}+1)v_2^2\right] +\cdots+\frac12\left[\frac{v_1^2}{\sqrt{n}+1}+(\sqrt{n}+1)v_n^2\right]\\ \end{aligned} which is true because of the AM-GM inequality.

Answer 2

Here is a proof which also shows that the inequality is tight.

Instead of $|x_i|$, consider w.l.o.g. $x_i \ge 0$. Further, let $x_{\rm max} = x_n$.

Denote $\sqrt{\sum_{i=1}^{n-1} x_i^2} = ||\bar v||_2$.

First, by Cauchy-Schwarz $$||v||_1 = \sum_{i=1}^{n-1} 1 \cdot x_i + x_n\le \sqrt{\sum_{i=1}^{n-1} 1} \sqrt{\sum_{i=1}^{n-1} x_i^2} + x_n= \sqrt{n-1} ||\bar v||_2 + x_n $$

This gives $$ \frac{||v||_1||v||_{\infty}}{||v||^2_2} \le \frac{\sqrt{n-1} ||\bar v||_2 x_n+ x_n^2}{||\bar v||_2^2 + x_n^2} $$

Now the function $$ f(x_n) = \frac{ax_n + x_n^2}{b + x_n^2} $$ has a maximum value (see appendix below) of $\frac12 (\sqrt{\frac{a^2+b}{b}} +1)$. Inserting $a = \sqrt{n-1} ||\bar v||_2$ and $b = ||\bar v||_2^2$ gives $$ \frac{||v||_1||v||_{\infty}}{||v||^2_2} \le \frac12 (\sqrt{\frac{(n-1) ||\bar v||_2^2 +||\bar v||_2^2}{||\bar v||_2^2}} +1) = \frac12 (\sqrt{n} +1) $$

This proves the claim. $\qquad \Box$

Note that the bound is tight. From the appendix below, the tight bound is taken at $$x^*_n = \frac{a}{-1+\sqrt{\frac{b+a^2}{b}}} = ||\bar v||_2\frac{\sqrt{n-1}}{-1+\sqrt{n}} $$ Further, the Cauchy-Schwarz inequality above is tight for $x_1 = x_2 = \cdots = x_{n-1}$. Hence we have that $x^*_n = x_1 (1+\sqrt{n})$ is the selection of values where the claim is obeyed with equality. Indeed, one can check that both sides equal: \begin{align} {\rm LHS:}&||v||_1||v||_{\infty} = ((n-1)x_1 + x_n^*)x_n^* = x_1^2 (1+{\sqrt{n}})(n+{\sqrt{n}})\\ {\rm RHS:}&\frac{1+\sqrt n}{2}||v||^2_2 = \frac{1+\sqrt n}{2}((n-1)x_1^2+ (x_n^*)^2) \\ & = x_1^2({1+\sqrt n}) \frac{n-1 + (1+\sqrt{n})^2}{2} = x_1^2 (1+{\sqrt{n}})(n+{\sqrt{n}}) \end{align}

---

Appendix : The maximum value of the function $ f(x) = \frac{ax + x^2}{b + x^2} $ can be obtained without calculus as follows. For simplicity, let $x = ay$ and $b =a^2 c$. Then we require $ f(y) = \frac{y + y^2}{c + y^2} \le m $ or alternatively $$0 \le -(y + y^2) + m(c + y^2) = (m-1)(y - \frac{1}{2(m-1)})^2 + mc - \frac{1}{4(m-1)}$$ To guarantee this inequality, the tight case is that the square term gets zero, and also $mc - \frac{1}{4(m-1)}$ (which is unbounded w.r.t. $m$) gets zero. This gives $m = \frac12 (1 + \sqrt{\frac{c+1}{c}})$. Reinserting $c = b/a^2$ gives the highest value of $f(x)$ which is $\frac12 (\sqrt{\frac{a^2+b}{b}} +1)$, as stated above. The bound is then taken where the square term gets zero, i.e. at $x^* = a y = \frac{a}{2(m-1)} = \frac{a}{-1+\sqrt{\frac{c+1}{c}}} = \frac{a}{-1+\sqrt{\frac{b+a^2}{b}}} $