7
$\begingroup$

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$

Does it follow that

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?

  • 0
    @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.2011-08-17

3 Answers 3

5

(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$.

4

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.


A few additional comments:

  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).
  • 0
    Great analysis, thanks Willie!2011-08-17
2

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.