Stuck trying to prove an inequality
I have been trying to prove (the left half of) the following inequality:
$$ \underbrace{\sum_i \sum_j |x_i| \le \sum_i \sum_j |x_i + x_j|}_\textrm{?} \le 2 \sum_i \sum_j |x_i|$$
(All $x_i$s are arbitrary reals and sums are over $1, 2, \dots, n$)
The right half follows by a simple application of the triangle inequality, but the left half isn't as simple.
I tried induction, and I could reduce the above problem to proving the following statement:
$$ \sum_i |x_i + x_{n+1}| + \sum_{i=1}^{n+1} |x_i + x_{n+1}| \ge \sum_{i=1}^{n+1} |x_i| + n|x_{n+1}|$$ or more simply (replacing $x_{n+1}$ by $y$), $$ 2\sum_i |x_i + y| \ge \sum_i |x_i| + (n-1)|y|$$
However, I don't know if the above "reduction" is any simpler than the original problem itself!
Can I continue the above line of thought, or is there an easier way to solve this problem? Any help is appreciated! :)
I believe that some smart tricks will solve the problem (e.g. by recasting it into the form of some known inequality), but what came to my mind first was a proof inspired by the simplex method. Although it does not look smart, it may be of some interests to the readers:
- Note that by scaling the inequality, we may assume, without loss of generality, that $|x_i|\le1$ for all $i$.
- So we want to prove the inequality for all $(x_1,\ldots,x_n)$ inside the hypercube $[-1,1]^n$.
- Divide the hypercube $[-1,1]^n$ into pieces by the hyperplanes $x_i=x_j$ and $x_i=0$. For instance, when $n=2$, the four "hyperplanes" (straight lines in this case) $x=y$, $x=-y$, $x=0$ and $y=0$ will divide the square $[-1,1]^2$ into eight pieces in a manner akin to the Union Jack.
- In mathematics, we call each of these pieces a simplex.
- Note that inside each simplex, each $x_i$ or $x_i+x_j$ does not change sign.
- Therefore, inside each simplex, the function $f(x_1,\ldots,x_n)=-\sum_i \sum_j |x_i| + \sum_i \sum_j |x_i + x_j|$ is identical to $-\sum_i \sum_j s_ix_i + \sum_i \sum_j t_{ij}(x_i + x_j)$ for some constants $s_i, t_{ij}=\pm1$.
- In other words, $f$ is a linear function inside each simplex.
- In linear programming, it is well known that the extremum of a linear function can be attained at the corners of the simplex. You can imagine that when you move a plane closer and closer to a simplex, it will touch the simplex at a corner first (or it touches the whole face, with the corners of the face included).
- The corners of our simplices, however, are those points such that $x_i\in\{-1,0,1\}$.
- So, we only need to prove the inequality for these corner points.
- Let $a$ of the $x_i$s are equal to 1, $b$ of them are equal to $-1$ and $n-a-b$ of them are equal to zero. Then $$ \begin{align} &-\sum_i \sum_j |x_i| + \sum_i \sum_j |x_i + x_j|\\ =&-n(a+b) + 2a^2+2b^2+2a(n-a-b)+2b(n-a-b)\\ =&2a^2+2b^2 - 2(a+b)^2 + n(a+b)\\ \ge&2a^2+2b^2 - 2(a+b)^2 + (a+b)^2\\ =&(a-b)^2\\ \ge&0. \end{align} $$
- Hence the result.
In step 11 of the above, equality holds iff $a-b=0$ and $a+b\in\{0,n\}$. In other words, equality holds iff $a=b=0$ or $a=b=n/2$, that is, iff all $x_i$s are zero, or when $n$ is even, exactly half of the $x_i$s (before scaling) are identical to some $x$ and the other half are $-x$s. However, this condition for equality is derived using the corner points. The above proof does not indicate whether equality can hold in other cases.
Let $p$ be the number of $x_i\ge0$, $m$ be the number of $x_i<0$, and $n=p+m$. $$ \small\begin{array}{} &\sum_i\;\:\sum_j|x_i+x_j|\\ &=\sum_{x_i\ge0}\;\:\sum_{x_j\ge0}|x_i+x_j| &+\sum_{x_i\ge0}\;\:\sum_{x_j<0}|x_i+x_j| &+\sum_{x_i<0}\;\:\sum_{x_j\ge0}|x_i+x_j| &+\sum_{x_i<0}\;\:\sum_{x_j<0}|x_i+x_j|\\ &\ge\sum_{x_i\ge0}\;\:\sum_{x_j\ge0}|x_i|+|x_j| &+\left|\sum_{x_i\ge0}\;\:\sum_{x_j<0}|x_i|-|x_j|\right| &+\left|\sum_{x_i<0}\;\:\sum_{x_j\ge0}|x_j|-|x_i|\right| &+\sum_{x_i<0}\;\:\sum_{x_j<0}|x_i|+|x_j|\\ &=2p\sum_{x_i\ge0}|x_i| &+2\left|m\sum_{x_i\ge0}|x_i|-p\sum_{x_i<0}|x_i|\right| &&+2m\sum_{x_i<0}|x_i| \end{array} $$
Subtracting $\displaystyle\sum_i\;\:\sum_j|x_i|=n\sum_i\;|x_i|$ from the inequality above yields $$ \small\begin{align}{} &\sum_i\;\:\sum_j|x_i+x_j|-\sum_i\;\:\sum_j|x_i|\\ &\ge(p-m)\sum_{x_i\ge0}|x_i| +\left|2m\sum_{x_i\ge0}|x_i|-2p\sum_{x_i<0}|x_i|\right| +(m-p)\sum_{x_i<0}|x_i|\\ &=(p-m)\sum_{i}x_i +\left|(m-p)\sum_{i}|x_i|+n\sum_ix_i\right|\\ &\ge0\tag{1} \end{align} $$ In the last inequality, if $p-m$ and $\sum\limits_ix_i$ have the same sign, we can ignore the quantity in absolute values. If $p-m$ and $\sum\limits_ix_i$ have different signs, then the quantities in the absolute values have the same sign and $|m-p|\sum\limits_i|x_i|\ge(m-p)\sum\limits_ix_i$.
Therefore, $(1)$ says that $$ \sum_i\;\:\sum_j|x_i|\le\sum_i\;\:\sum_j|x_i+x_j| $$
Assume an ordering of the $x_i$ such that $x_1 \le x_2 \le \dots \le x_k < 0 \le x_{k+1} \le x_{k+2} \le \dots \le x_n$. Let's call $T_1 = \sum_{i=1}^k |x_i|$, $T_2 = \sum_{i=k+1}^n |x_i|$, and $T=\sum_i |x_i|=T_1+T_2$ so that $T, T_1, T_2 \ge 0$.
Since we only require a lower bound on the sum $\sum_{i \neq j} |x_i + x_j|$, we only consider $2\binom{k}{2} + 2\binom{n-k}{2}$ terms of the $2\binom{n}{2}$ total terms that the sum contains i.e. we only pick terms where both $x_i$ and $x_j$ have the same sign. This solves the inequality in many cases. For the other cases, we include the cross terms too later.
$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge \sum_{i=1}^k \sum_{j=1,j\neq i}^k |x_i+x_j| + \sum_{i=k+1}^n \sum_{j=k+1,j\neq i}^n |x_i+x_j|\\ &= \sum_{i=1}^k \sum_{j=1,j\neq i}^k (|x_i|+|x_j|) + \sum_{i=k+1}^n \sum_{j=k+1,j\neq i}^n (|x_i|+|x_j|)\\ &= \sum_{i=1}^k ((k-1)|x_i|+T_1-|x_i|) + \sum_{i=k+1}^n ((n-k-1)|x_i|+T_2-|x_i|)\\ &= \sum_{i=1}^k ((k-2)|x_i|+T_1) + \sum_{i=k+1}^n ((n-k-2)|x_i|+T_2)\\ &= ((k-2)T_1+kT_1) + ((n-k-2)T_2+(n-k)T_2)\\ &= 2\{(k-1)T_1 + (n-k-1)T_2\}\\ \end{align*} $$
Now, the last expression is a function of $T_1$ and $T_2$. Since we require a lower bound in terms of $T=T_1+T_2$, we can get two equivalent expressions in terms of either $T_1$ and $T$ or in terms of $T_2$ and $T$. Thus,
$$\sum_{i \neq j} |x_i + x_j| \ge 2(2k-n)T_1+2(n-k-1)T$$ $$\sum_{i \neq j} |x_i + x_j| \ge 2(n-2k)T_2+2(k-1)T$$
Adding both, we get:
$$2\sum_{i \neq j} |x_i + x_j| \ge 2\left\{(2k-n)T_1+(n-2k)T_2+(n-2)T\right\}$$ $$\implies \sum_{i \neq j} |x_i + x_j| \ge (2k-n)(T_1-T_2)+(n-2)T \ge (n-2)\sum_i |x_i|$$ $$ \text{whenever,} \; (2k-n)(T_1-T_2) \ge 0$$
For the cases when the above inequality doesn't hold, we need to consider the cross terms too. Computing the cross terms alone:
$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge \sum_{i=1}^k \sum_{j=k+1}^n |x_i+x_j| + \sum_{i=k+1}^n \sum_{j=1}^k |x_i+x_j|\\ &\ge 2\sum_{i=1}^k \sum_{j=k+1}^n |x_i+x_j|\\ &\ge 2\sum_{i=1}^k \sum_{j=k+1}^n \max\{|x_i|-|x_j|,|x_j|-|x_i|\}\\ &\ge 2 \max\{(n-k)T_1-kT_2, kT_2-(n-k)T_1\}\\ \end{align*} $$
Including the cross terms along with the terms from the previous case, we have:
$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge 2 \max\{(n-k)T_1-kT_2, kT_2-(n-k)T_1\} + 2\{(k-1)T_1 + (n-k-1)T_2\}\\ &\ge 2 \max\{(n-1)T_1+(n-2k-1)T_2, (2k-n-1)T_1+(n-1)T_2\} \; (*)\\ \end{align*} $$
The $\max$ term can go one of two ways. Using the first term we get: $$ \sum_{i \neq j} |x_i + x_j| \ge 2 \{(n-1)T_1+(n-2k-1)T_2\} $$
We can again write the above in terms of either $T,T_1$ or $T,T_2$ giving two inequalities:
$$ \begin{align} \sum_{i \neq j} |x_i+x_j| &\ge (n-2k-1)T+2kT_1\\ \sum_{i \neq j} |x_i+x_j| &\ge (n-1)T-2kT_2 \end{align} $$
Summing the above two inequalities,
$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge (2n-2k-2)T+2k(T_1-T_2)\\ &\ge (n-2)T+(n-2k)T+2k(T_1-T_2)\\ &\ge (n-2)T \quad \text{for the case} \quad (2k-n) \le 0, (T_1-T_2) \ge 0\\ \end{align*} $$
Similarly, for the other case, when $(2k-n) \ge 0, (T_1-T_2) \le 0$, we use the other $\max$ term from $(*)$ and follow the above steps routinely to prove the inequality.
Q.E.D