Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
@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
add comment

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
add comment

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).
share|improve this answer
    
Great analysis, thanks Willie! –  Tom Ellis Aug 17 '11 at 20:20
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.