# Can I replace one inequality with another?

Suppose I have a collection of real numbers $x_b$ where $b \in \{1, ..., n\}$, and a constant $C$ with $1/n \le C \le 1$. Further suppose that

for all $b$, $x_b \le C \sum_{a} x_a$

for all $b$, $|x_b| \le C \sum_{a} |x_a|$

Certainly if all the $x_b$ are positive then the result holds, and it suffices to check the implication when exactly one of the $x_b$ is negative. I checked for a large random sample, but I can't get any futher than this. I've tried comparing the $l^1$ and $l^\infty$ norms to no avail.

This problem can't be very hard to solve one way or the other. Does any one have any ideas?

-
@Sivaram: I don't think so; in general an inequality of (not necessarily positive) real numbers $a\leq b$ tells us nothing about whether $|a|\leq |b|$, $|a|=|b|$, or $|a|\geq|b|$. For example, if $C\sum_a x_a$ is negative, then $C\sum_ax_a\geq x_b$ implies $|C\sum_ax_a|\leq|x_b|$, which we can't combine with the triangle inequality's $C\sum_a|x_a|\geq |C\sum_ax_a|$. I just posted an incorrect answer (now deleted) where I made the same error. – Zev Chonoles Aug 17 '11 at 18:27
@Zev: Oops... I think I need to go to bed now. I have deleted my previous comment – user17762 Aug 17 '11 at 18:31
@Tom: it suffices to check the implication when exactly one of the $x_b$ is negative... Why? – Did Aug 17 '11 at 18:44
@Didier: the idea was that the former inequality becomes easier to satisfy whilst the latter stays the same, but perhaps I didn't think that through properly ... anyway with the good answers of Ronaldo and Willie it's a moot point. – Tom Ellis Aug 17 '11 at 20:20

(I hope I understood well because the $a$ seem to come out of nowhere).

Take $x_1=x_2=\ldots =x_7=\frac{1}{4}$, $x_8=-1$ and $C=\frac{1}{3}$ (so we have $\frac{1}{8}\leq C\leq 1$). If $X=\sum_a x_a$ and $Y=\sum_a|x_a|$, you have $CX=\frac{1}{4}$ so it is OK for the first equation.

On the other hand $Y=\frac{11}{4}$ and so $CY=\frac{11}{12}$ is lesser than $|a_8|=1$.

-

The inequality is false in general. A counterexample:

Let $n = 7$. Let $x_1 = -1$. Let $x_2 = \cdots = x_7 = \frac{\sqrt{2}+1}{6}$. And let $C = \frac{\sqrt{2}+1}{6\sqrt{2}}$. Then $$\sum x_a = -1 + \sqrt{2} + 1 = \sqrt{2}$$ so $C\sum x_a \geq x_b$ for any $b$.

But $$\sum |x_a| = \sqrt{2} + 2$$ so $$C\sum |x_a| = \frac{3+2\sqrt{2}}{6} < 1 = |x_1|$$

Interestingly, for $n \leq 6$ the inequality is true. A sketch of proof goes something like this:

The inequality is trivially true if all of $x_a$ are non-negative, or if $C = 1/n$ (since in that case we must have all the $x_a$ are identical). So we assume that $C>1/n$, and that there are $k>0$ elements which are negative. We can assume that those are the first $k$. Then the given inequality implies $$x_b \leq C \sum_{k+1}^n x_a - C \sum_1^k |x_a|$$ we sum $b$ from $k+1$ to $n$, and we have that $$C(n-k)\sum_1^k |x_a| \leq [C(n-k)-1] \sum_{k+1}^n x_a$$ notice that this puts a restriction on $k$ such that $C(n-k)-1 > 0$. Denote by $\delta = C(n-k)-1$. We can re-write the above as $$(2\delta + 1)\sum_1^k |x_a| \leq \delta \sum_1^n |x_a|$$

So if $C(2\delta + 1)/\delta \geq 1$, the above expression will imply the desired inequality. But $C = (1+\delta)/(n-k)$, so we have $$\frac{C(2\delta + 1)}{\delta} = \frac{\sqrt{2}}{n-k}(\frac{1}{\sqrt{2}\delta} + \sqrt{2}\delta) + \frac{3}{n-k}$$ Using that $x + x^{-1} \geq 2$, we have that $$\geq \frac{2\sqrt{2} + 3}{n-k}$$

So if $n \leq 6$, the above is guaranteed to be at least 1 (since $k \geq 1$ and $2\sqrt{2} > 2$).

Remark Interestingly, the crucial number is $n-k$. If a priori you know that no more than 5 of the $x_a$ are positive, then the desired inequality will hold.

1. Yes, I did the proof first before writing down the example. Hence the near-optimum constants.
2. We see that the constraint on $n-k$ can be relaxed if we know a priori that $\delta = C(n-k) - 1 \leq n-k-1$ is large. Of course, in the case that $C = 1$, the conclusion is a triviality for any $n$. A computation shows the following crude asymptotic lower-bound: the inequality is true whenever $n < \frac{3 - \sqrt{2}}{1-C}$ (the inequality can be true even for some $n$ bigger than that; but as $C\to 1$ from below, this should give the right grow rate).
-
Great analysis, thanks Willie! – Tom Ellis Aug 17 '11 at 20:20

Let $m = \min_i x_i$ and $M = \max_i x_i$. If $m \geq 0$ then the claim is trivial, so suppose that $m < 0$.

If $M < 0$ then we can rewrite the givens as $$|x_i| \geq C\sum_j |x_j|.$$ Adding all these inequalities, $$\sum_i |x_i| \geq nC \sum_j |x_j|,$$ and therefore $nC \leq 1$. Thus $nC=1$, and so all $x_i$ are equal, and the required inequalities trivially hold.

So the interesting case is when $m < 0 \leq M$. Intuitively, it is clear that the hardest case is when $$x_1=m, \; x_2=\cdots=x_n=M, \; M = C\sum_i x_i = C((n-1)M + m).$$ We have to check when $$-m \leq C\sum_i |x_i| = C(\sum_i x_i - 2m) = M - 2Cm.$$ Since everything is homogeneous, we can assume that $M = 1$. This implies that $Cm = 1-C(n-1)$. Therefore the required inequality is $$-m \leq 1 -2(1-C(n-1)) = 2C(n-1) - 1.$$ Multiplying by $C$ and substituting $Cm$, $$C(n-1) - 1 \leq 2C^2(n-1) - C.$$ We get the quadratic inequality $$0 \leq 2(n-1)C^2 - nC + 1.$$ The critical points of the quadratic are $$C_{+,-} = \frac{n \pm \sqrt{n^2 - 8(n-1)}}{4(n-1)}.$$ The inequality holds when $C \leq C_-$ or $C \geq C_+$. Note that roughly, $$C_- \approx \frac{2}{n}, \; C_+ \approx 1-\frac{1}{n}.$$

When $C_- < C < C_+$, we can construct an example of the form discussed in which the required inequality fails to hold. The other case is left as an exercise to the reader.

-