I have the following set of equations



$-1 \leq x_i \leq 1$

Then what is the bound for the |$x_1|+|x_2|+|x_3|+....+|x_n$|

The trivial bound is $n$ as each variable value is less than $1$. But I know this is a very bad bound. So can we get better than this..? Thank You.


Does $1 \le \sum |x_i| \le \sqrt{n}$ suffice?

The lower bound can be obtained by noting that $f(x) = |x|$ is convex in the interval and applying Jensen's inequality, or using extending triangle inequality.

The upper bound using Cauchy-Schwarz with $a_i = |x_i|$ and $b_i = 1$. Then we have:
$\sum a_i b_i \le (\sum a_i^2)^{1/2}(\sum b_i^2)^{1/2}$

$\implies \sum \lvert x_i \rvert \cdot 1 \le (\sum \lvert x_i \rvert ^2)^{1/2}(\sum 1)^{1/2}$

$\implies \sum \lvert x_i \rvert \le (\sum x_i^2)^{1/2}(n)^{1/2} = 1 \cdot \sqrt{n}$

The lower bound can be achieved by $x_1 = 1$ and all other $x_i = 0$, so that's tight. The upper bound however is not tight, hence there is possibility of improving it, using the fact that $\sum x_i = 1$.

| cite | improve this answer | |
  • $\begingroup$ The lower bound is clear for me. But for the upper bound if we apply cauchy-schwarz then I think we will get the bound $n$. I couldn't understand the last line i.e., using the fact that $\sum |x_i| = 1$ $\endgroup$ – Kumar Mar 4 '13 at 6:20
  • $\begingroup$ I have clarified the Cauchy-Schwarz application in the edit above. As mentioned, the upper bound is loose, but I meant $\sum x_i = 1$ should prove helpful in tightening it. $\endgroup$ – Macavity Mar 4 '13 at 6:39
  • $\begingroup$ @Macavity as my answer shows, the upper bound of $\sqrt{n}$ is actually quite tight, and is attainable whenever $n=m^2$ is a perfect square, via $x_1=x_2= \ldots =x_{\frac{m^2+m}{2}}=\frac{1}{m}, x_{\frac{m^2+m}{2}+1}=x_{\frac{m^2+m}{2}+2}= \ldots =x_{m^2}=-\frac{1}{m}$ $\endgroup$ – Ivan Loh Mar 4 '13 at 15:47
  • $\begingroup$ @IvanLoh: Yes - did not specifically consider case of n being perfect square, where its tight. Even otherwise it looks good! $\endgroup$ – Macavity Mar 5 '13 at 8:49

Overview: I shall prove the bounds

$$1 \leq \sum\limits_{i=1}^{n}{|x_i|} \leq \frac{2(k+\sqrt{(n-k)k(n-1)})}{n}-1$$

, where $k=\lceil \frac{n-1+\sqrt{n}}{2} \rceil$

Equality is achievable for both bounds, so they are the best possible bounds.

Some numbers for illustration: Let's take for example $n=2013$. Then $k=\lceil \frac{2013-1+\sqrt{2013}}{2} \rceil=1029$, and we get $$\sum\limits_{i=1}^{2013}{|x_i|} \leq \frac{2(1029+\sqrt{(984)(1029)(2012)})}{2013}-1 \approx 44.86646844<44.86646854=\sqrt{2013}$$.

Thus the simple upper bound $\sqrt{n}$ is actually quite tight. In fact, my upper bound agrees with $\sqrt{n}$ whenever $n$ is a perfect square.

Lower bound: Note that $x_i^2 \leq |x_i|$, so $1=\sum\limits_{i=1}^{n}{x_i^2} \leq \sum\limits_{i=1}^{n}{|x_i|}$, with equality when 1 of $x_i$ is $1$ and the others are $0$.

Proof of upper bound: It is easy to check $n=1, 2$. Take $n \geq 3$.

Let $a$ be the number of positive $x_i$. Since $\sum\limits_{i=1}^{n}{x_i}=1$, clearly $a \not =0$. Also if $a=n$ then $0<\sum\limits_{symm}{x_ix_j}=\left(\sum\limits_{i=1}^{n}{x_i}\right)^2-\sum\limits_{i=1}^{n}{x_i^2}=0$, a contradiction. Thus $1 \leq a \leq n-1$.

Since the conditions and the expression to be maximised are symmetric, we may safely assume $x_1, x_2, \ldots , x_a>0$ and $x_{a+1}, x_{a+2}, \ldots , x_n \leq 0$. Thus $\sum\limits_{i=1}^{a}{|x_i|}=\sum\limits_{i=a+1}^{n}{|x_i|}+1$, so $\sum\limits_{i=1}^{n}{|x_i|}=2\sum\limits_{i=1}^{a}{|x_i|}-1$.

$$1=\sum\limits_{i=1}^{a}{x_i^2}+\sum\limits_{i=a+1}^{n}{x_i^2} \geq \frac{\left(\sum\limits_{i=1}^{a}{|x_i|}\right)^2}{a}+\frac{\left(\sum\limits_{i=a+1}^{n}{|x_i|}\right)^2}{n-a}=\frac{\left(\sum\limits_{i=1}^{a}{|x_i|}\right)^2}{a}+\frac{\left(\sum\limits_{i=1}^{a}{|x_i|}-1\right)^2}{n-a}$$

Here we have used Cauchy Schwarz inequality.

We can rewrite this as $$n\left(\sum\limits_{i=1}^{a}{|x_i|}\right)^2-2a\left(\sum\limits_{i=1}^{a}{|x_i|}\right)-a(n-a-1) \leq 0$$

Thus $$\sum\limits_{i=1}^{a}{|x_i|} \leq \frac{2a+\sqrt{4a^2+4a(n-a-1)n}}{2n}=\frac{a+\sqrt{(n-a)a(n-1)}}{n}$$.

This gives an upper bound of $$\sum\limits_{i=1}^{n}{|x_i|}=2\sum\limits_{i=1}^{a}{|x_i|}-1 \leq \frac{2(a+\sqrt{(n-a)a(n-1)})}{n}-1$$

Note that equality is attainable at $x_1=x_2= \ldots =x_a=\frac{a+\sqrt{(n-a)a(n-1)}}{an}$ and $x_{a+1}=x_{a+2}= \ldots =x_n=\frac{1-\frac{a+\sqrt{(n-a)a(n-1)}}{n}}{n-a}$.

It thus suffices to maximise $$\sum\limits_{i=1}^{n}{|x_i|}=2\sum\limits_{i=1}^{a}{|x_i|}-1 \leq \frac{2(a+\sqrt{(n-a)a(n-1)})}{n}-1$$

over $1 \leq a \leq n$. Let $k$ be the value of $a$ which maximises this expression (if there is more than 1 such $a$, pick the smallest such one.)

First note that if $a<\frac{n}{2}$, then $a+\sqrt{(n-a)a(n-1)}<n-a+\sqrt{(n-(n-a))(n-a)(n-1)}$. Thus we must have $k \geq \frac{n}{2}$.

Clearly, $k$ must be a positive integer solution of the inequality $x+\sqrt{(n-x)x(n-1)}\geq x+1+\sqrt{(n-x-1)(x+1)(n-1)}$, and $k-1$ must not satisfy that inequality.

Manipulating, $$(n-x)x(n-1) \geq 1+(n-x-1)(x+1)(n-1)+2\sqrt{(n-x-1)(x+1)(n-1)}$$

$$(2x+1-n)(n-1)-1 \geq 2\sqrt{(n-x-1)(x+1)(n-1)}$$

We have already determined $k \geq \frac{n}{2}$, so $(2k+1-n)(n-1)-1 \geq n-2>0$, so we don't lose any information by squaring.

$$ (2x+1-n)^2(n-1)^2-2(2x+1-n)(n-1)+1 \geq 4(n-x-1)(x+1)(n-1)$$

$$(2x+1-n)^2(n-1)-2(2x+1-n)+\frac{1}{n-1} \geq 4(n-x-1)(x+1)$$

Before we continue, note the following trivial lemma. If $a, b$ are integers and $0<c<1$ then $a+c \geq b \Leftrightarrow a \geq b$.

Proof: If $a \geq b$, then $a+c \geq b+c \geq b$. If $a+c \geq b$ then $a \geq b-c$ so $a\geq \lceil b-c \rceil=b$.

Note that we want integer solutions, so by the lemma we have $$(2x+1-n)^2(n-1)-2(2x+1-n) \geq 4(n-x-1)(x+1)$$

$$4nx^2-4n(n-1)x+n^3-3n^2+n+1 \geq 0$$ $$4x^2-4(n-1)x+n^2-3n+1+\frac{1}{n} \geq 0$$ By lemma, $$4x^2-4(n-1)x+n^2-3n+1 \geq 0$$ $$x^2-(n-1)x+\frac{n^2-3n+1}{4} \geq 0$$. We have $k \geq \frac{n}{2} > \frac{n-1-\sqrt{(n-1)^2-(n^2-3n+1)}}{2}$, so $x$ is larger than the smaller root of the quadratic, and must thus be $\geq$ the larger root.

Thus $x \geq \frac{n-1+\sqrt{(n-1)^2-(n^2-3n+1)}}{2}=\frac{n-1+\sqrt{n}}{2}$, so $k \geq \frac{n-1+\sqrt{n}}{2}$, so $k \geq \lceil \frac{n-1+\sqrt{n}}{2} \rceil$.

Assume on the contrary that $k \geq \lceil \frac{n-1+\sqrt{n}}{2} \rceil+1$, then $k-1 \geq \lceil \frac{n-1+\sqrt{n}}{2} \rceil \geq \frac{n}{2}$, so we could use $k-1$ in place of $x$ in the inequality throughout the whole manipulation, and $k-1$ satisfies the last inequality $\geq \lceil \frac{n-1+\sqrt{n}}{2} \rceil$, so $k-1$ is a solution of the original inequality, a contradiction.

Thus $k=\lceil \frac{n-1+\sqrt{n}}{2} \rceil$, and we are done.

| cite | improve this answer | |
  • $\begingroup$ Perhaps a simpler approach could be to note the convexity of the function and the set involved - the maxima then has to be achieved on the boundary, which would mean some $k$ number of $x_i$ are identical to $x$ for some $x$, and remaining $n-k$ variables are identical to $-x$. Then it would reduce to solving for $k$ and $x$ using the boundary equations $\sum x_i^2 = 1$ and $\sum x_i = 1$. In the perfect square case it directly leads to the result, for the other case need to work out. $\endgroup$ – Macavity Mar 5 '13 at 8:54
  • $\begingroup$ Isn't that what I did (except that I used CS)? By CS inequality, I get $\frac{2(a+\sqrt{(n-a)a(n-1)})}{n}-1$, which I then need to maximise over $a$. From your comment, solving for $k, x$ using the boundary equations, as you say, would just give an expression in terms of $k$, equivalent to what I got. (except that I used $a$ as the variable) This is because there is a solution for $x$ for each $k$. This is the easy part. The harder part is to find the value of $k$ (as referenced from your comment, equivalent to my "$a$") which gives you the maximum, which is actually the bulk of my answer. $\endgroup$ – Ivan Loh Mar 5 '13 at 9:22
  • $\begingroup$ I see you mean that the negative variables have same absolute value as the positive variables, in order to maximise the expression. That is, in fact, incorrect. Take $n=3$, the maximum is achieved at $\frac{5}{3}$, with $x_1=x_2=\frac{2}{3}, x_3=-\frac{1}{3}$. $\endgroup$ – Ivan Loh Mar 5 '13 at 9:26
  • $\begingroup$ Ah - you are correct. Somehow I assumed there would be a convex feasible region of interval form $[-x, x]$ for each $x_i$, which is not true. $\endgroup$ – Macavity Mar 5 '13 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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