An inequality $||x_1+\dots+x_n|| \le 2\ \text{Avg}||\pm x_1\pm\dots\pm x_n||$.

Question

Let $X$ be a Banach space, $x_1,...,x_n\in X$. I want to know if the following is true or not: $$ ||x_1+\dots+x_n|| \le 2\ \text{Avg}||\pm x_1\pm\dots\pm x_n||, $$ where the average is taken over all possible assignment of $2^n$ plus/minus signs.

For $n=1$ this is trivial. For $n=2$ we have $$\begin{align} ||x+y|| &= \frac12\left(||+x+y||+||-x-y|| \right) \\ &\le 2\cdot\frac14\left(||+x+y||+||-x-y||+||+x-y||+||-x+y|| \right) \end{align}$$

which is simple enough since there are $2$ superficial terms on the RHS. However, for $n=3$ we need all the terms $$\begin{align} ||x+y+z|| &= ||+x+y+z|| \\ ||x+y+z|| &= ||-x-y-z|| \\ ||x+y+z|| &\le ||+x+y-z|| +||+x-y+z|| +||-x+y+z|| \\ ||x+y+z|| &\le ||-x-y+z|| +||-x+y-z|| +||+x-y-z|| \\ \end{align}$$ summing over the LHS and RHS gives the result.

From this observation, it'd seem that math induction might not be the way to go. So how should we prove/disprove the inequality here?

Remark: Since the RHS is symmetric in plus/minus signs, the inequality in question actually implies something stronger(if it is true) namely $$ \text{max}||\pm x_1\pm\dots\pm x_n|| \le 2\ \text{Avg}||\pm x_1\pm\dots\pm x_n||. $$

Answer 1

The inequality is false for $n=4$. Let's consider the well-studied Banach space $\mathbb R$ and take $x_1 = x_2 = x_3 = x_4 = 1$. The average value of $|\pm1 \pm1 \pm1 \pm1|$ is $$\frac1{16}\left(\binom40 \cdot 4 + \binom41 \cdot 2 + \binom42 \cdot 0 + \binom43 \cdot2 + \binom44 \cdot 4\right) = \frac{24}{16} = \frac32,$$ but the maximum value is $4$.

Answer 2

Let $X$ be any Banach space. Let $x_1\in X$ with $\|x_1\|=1$, and put $x_j=x_1\ne0$ for all $j$. Then $$ \|x_1+\cdots+x_n\|=n. $$ On the other hand, $$ \|\pm x_1\pm \cdots\pm x_n\|=|p-m|=|n-2p|, $$ where $p,m$ are respectively the number of plus and minus signs. For each choice of $p$, there are $n\choose p$ possible orderings. So the right-hand-side in your inequality is $$ \frac2{2^n}\,\sum_{p=0}^n {n\choose p}\,|n-2p|. $$ For simplicity, let us assume $n$ is even, i.e., $n=2k$. Then \begin{align} \frac2{4^k}\,\sum_{p=0}^{2k} {2k\choose p}\,|2k-2p| &=\frac1{4^{k-1}}\,\sum_{p=0}^{2k} {2k\choose p}\,|k-p|\\ \ \\ &=\frac1{4^{k-1}}\,\left(\sum_{p=0}^{k-1} {2k\choose p}\,(k-p)+\sum_{p=k+1}^{2k} {2k\choose p}\,(p-k)\right)\\ \ \\ &=\frac1{4^{k-1}}\,\left(\frac k2\,{2k\choose k} +\frac{k+1}2\,{2k\choose k+1}\right) \end{align}

So your inequality would be (cancelling a 2 on each side) $$ k\leq \frac1{4^{k-1}}\,\left(\frac k2\,{2k\choose k} +\frac{k+1}2\,{2k\choose k+1}\right), $$ that is $$ 1\leq \frac1{4^{k-1}}\,\left(\frac 12\,{2k\choose k} +\frac{k+1}{2k}\,{2k\choose k+1}\right). $$ But already for $k=5$ the expression on the right is less than $1$ (and goes to zero as $k\to\infty)$.