Some inequalities between 1- norm, 2- norm and infinity-norm: $\|x\|_2\leq\sqrt{\|x\|_1\| x\|_\infty}\leq\frac{1+\sqrt{n}}{2}\|x\|_2$ Let $x\in\mathbb{C}^n$. Do the following inequalities hold?
$$\lVert x\lVert_2\leq\sqrt{\lVert x\lVert_1\lVert x\lVert_\infty}\leq\frac{1+\sqrt{n}}{2}\lVert x\lVert_2.$$
I think the first inequality is the Holder inequality with $p=1$ and $q=\infty$.
 A: You correctly observed that $\|x\|_2\le \sqrt{\|x\|_1\|x\|_\infty}$ is a special (easy) case of Hölder's inequality, which essentially amounts to $|x_i|^2\le \|x\|_\infty |x_i|$. To prove the second part, first use the arithmetic-geometric means inequality. After that, use Hölder's inequality again:
$$\|x\|_1\le \sqrt{n}\|x\|_2$$
and observe that $\|x\|_\infty \le \|x\|_2$.
A: In fact the second inequality can be made tighter. For $x\in\mathbb{C}^n$:
$$\boxed{\sqrt{\|x\|_1 \, \|x\|_\infty} \le \sqrt{\tfrac{1+\sqrt n}2} \|x\|_2 }$$
Define $f(x) = \frac{1+\sqrt n}2 \|x\|_2^2 - \|x\|_1 \|x\|_\infty$. The following proof shows $f(x) \ge 0$ for all $x \in \mathbb{C}^n$.
Without loss of generality, assume each component of $x$ is real and nonnegative. No generality is lost because $\forall a, b \in \mathbb{C}^n$, $(\forall i \enspace |a_i| = |b_i|) \implies f(a) = f(b)$. The value of $f(x)$ is the same if we replace each component of $x$ by its complex magnitude, which is real and nonnegative.
Also without loss of generality, assume $x_1 = \|x\|_\infty$. The infinity norm $\|x\|_\infty$ is the maximum $|x_i|$, but the value of $f(x)$ stays the same upon reordering components of $x$ so let's have the biggest one first.
Write $e_1, \dots, e_n$ for the basis vectors of $\mathbb{R}^n$ so that $x = x_1 e_1 + \cdots + x_n e_n$. Then write $f(x)$ as the telescoping sum:
$$
\begin{align}
f(x) & = f(x_1 e_1) \\ & \qquad + \left[\vphantom{\tfrac 00}\right. f(x_1e_1+x_2e_2)-f(x_1e_1) \left.\vphantom{\tfrac 00}\right] \\ & \qquad + \left[\vphantom{\tfrac 00}\right. f(x_1e_1+x_2e_2+x_3e_3)-f(x_1e_1+x_2e_2) \left.\vphantom{\tfrac 00}\right] \\ & \qquad + \dots \\ & \qquad + \left[\vphantom{\tfrac 00}\right. \underbrace{f(x_1e_1 + \dots + x_ne_n)}_{f(x)} -f(x_1e_1 + \dots + x_{n-1}e_{n-1}) \left.\vphantom{\tfrac 00}\right]
\end{align}
$$
Since $x_1=\|x\|_\infty$, the value of $f(x_1e_1)$ is:
$$
\begin{align*}
f(x_1e_1) & = \frac{1+\sqrt{n}}2 \|x_1e_1\|_2^2-\|x_1e_1\|_1 \, \|x_1e_1\|_\infty \\
& = \frac{1+\sqrt{n}}2 x_1^2 - x_1x_1 \\
& = \frac{1+\sqrt{n}}2 \|x\|_\infty^2 - \|x\|_\infty \|x\|_\infty \\
& = \frac{\sqrt{n}-1}2 \|x\|_\infty^2
\end{align*}
$$
Since $x_i \le x_1$ for $i>1$, the term $\left[ f(x_1e_1+\dots + x_ie_i)-f(x_1e_1 + \dots + x_{i-1}e_{i-1})\right]$ in the telescoping sum is:
$$
\left[\vphantom{\tfrac 00}\right. f(x_1e_1+\dots + x_ie_i)-f(x_1e_1 + \dots + x_{i-1}e_{i-1}) \left.\vphantom{\tfrac 00}\right] = \frac{1+\sqrt{n}}2 x_i^2 - \|x\|_\infty x_i
$$
This is a quadratic expression in $x_i$ and the coefficient of $x_i^2$ is positive, so the minimum possible value of the quadratic expression is achieved at the vertex: $x_i^* = \frac{\|x\|_\infty}{1+\sqrt{n}}$. This value is less than $\|x\|_\infty$, so the assumption that $x_i \le x_1$ has not been violated. The value of the quadratic expression at this value of $x_i$ is:
$$
\begin{align*}
\frac{1+\sqrt{n}}2 \left( x_i^*\right)^2 - \|x\|_\infty \, x_i^* & = \frac{1+\sqrt{n}}2 \left( \frac{\|x\|_\infty}{1+\sqrt{n}}\right)^2 - \|x\|_\infty \left( \frac{\|x\|_\infty}{1+\sqrt{n}} \right) \\
& = -\frac 1{2\left(1+\sqrt{n}\right)} \|x\|_\infty^2
\end{align*}
$$
The smallest possible value of $f(x)$ is achieved when each of the bracketed $[\ ]$ terms in the telescoping sum is minimal, i.e. equal to $-\frac 1{2\left(1+\sqrt{n}\right)} \|x\|_\infty^2$. There are $n-1$ bracketed terms in the sum, so the smallest possible value of $f(x)$ is:
$$
\begin{align*}
f(x) & = f(x_1e_1) + (n-1) \left( -\frac 1{2\left(1+\sqrt{n}\right)} \|x\|_\infty^2 \right) \\
& = \frac{\sqrt{n}-1}2 \|x\|_\infty^2 - \frac{\left( \sqrt{n}+1\right) \left( \sqrt{n}-1\right)}{2 \left(1+\sqrt{n}\right)} \|x\|_\infty^2 \\
& = \left( \frac{\sqrt{n}-1}2 - \frac{\sqrt{n}-1}2 \right) \|x\|_\infty^2 \\
& = 0
\end{align*}
$$
Therefore $f(x) \ge 0$, so $\|x\|_1 \, \|x\|_\infty \le \frac{1+\sqrt{n}}2 \|x\|_2^2$ for all $x \in \mathbb{C}^n$. Equality is achieved when $|x_i|=\frac{\|x\|_\infty}{1+\sqrt{n}}$ for all but one of the $x_i$, that one being $\|x\|_\infty$.
