# Doubt in the solution provided to an inequality question

I have the following question with me:

The numbers $$x_1, x_2, . . . , x_n$$ obey $$−1 \leq x_1, x_2, . . . , x_n \leq 1$$ and $$x_1^3 + x_2^3 + ... + x_n^3 = 0$$ Prove that $$x_1 + x_2 + · · · + x_n ≤ \frac{n}{3}$$

They provide the following solution:

Substitute $$y_i = x_i^3$$ so that $$y_1 + ... + y_n = 0$$ and we want to maximize $$y_1^{1/3} + y_2^{1/3} + ... + y_n^{1/3}$$ we observe the concavity/convexity of the function $$f(y) = y^{1/3}$$ and hence we may put $$y_1=...=y_k=-1$$

From here I could not follow the solution. How can we just put the above numbers? How does it help in the solution?

Source of question and solution : https://robertkosova.files.wordpress.com/2018/09/olympiad-inequalities-thomas-mildorf-2006.pdf Question number 15 solution 1

With this function that's neither concave nor convex, we want to push the values apart in some places and together in others. We're pushing them apart for negative $$x$$, and $$-1$$ is as far as we can go in that case.

Now, what I would do with this one? Start with that same substitution $$y_i=x_i^3$$. We wish to maximize $$\sum_i y_i^{1/3}$$ given $$\sum_i y_i = 0$$ and $$-1\le y_i\le 1$$.

To do so, we will find a linear (affine) function $$g$$ so that $$y^{1/3}\ge g(y)$$ for all $$y\in[-1,1]$$, and $$g$$ is as large as possible. This $$g$$ will touch the graph of $$y^{1/3}$$ twice, crossing at $$-1$$ and being tangent to it at some positive $$c$$. Now, $$g(y)-y^{1/3}=ay-y^{1/3}+b$$ is a cubic polynomial in $$y^{1/3}$$. We know it has a root at $$y=-1$$ and a double root at $$y=c$$, so we can write down its factored form: $$ay-y^{1/3}+b = g(y) = a(y^{1/3}+1)(y^{1/3}-c^{1/3})^2 = a\left(y+(1-2c^{1/3})y^{2/3}+\cdots\right)$$ Equating the $$y^{2/3}$$ coefficients, $$1-2c^{1/3}=0$$ and $$c=\frac18$$. The line between $$(-1,-1)$$ and $$(\frac18,\frac12)$$ has slope $$\frac{3/2}{9/8} = \frac43$$, so $$g(y)=\frac43y+\frac13$$.

All right, now we have that $$\frac43y + \frac13 \ge y^{1/3}$$ for all $$y\in [-1,1]$$. Apply this to each $$y_i$$ and take the sum: $$\sum_{i=1}^n y_i^{1/3} \le \sum_{i=1}^n \left(\frac43y_i+\frac13\right) = \frac43\left(\sum_{i=1}^ny_i\right) +\frac n3 = \frac n3$$ And that's it. Equality occurs when each $$y_i$$ is equal to either $$-1$$ or $$\frac18$$, which is possible if $$n$$ is divisible by $$9$$; for other $$n$$, there's a slightly stronger bound that's difficult to calculate exactly.

I'm pretty sure I've seen this problem before. Looking back - that substitution didn't really make much difference. I'm pretty sure I didn't use it the first time I dealt with this one.

• I've corrected the equality case - but it's still something that happens for infinitely many $n$. Your claimed bound can't possibly be uniformly true. – jmerry Mar 21 at 12:01
• (+1) This bound is right. I had miscomputed the best $\lambda$ in my answer. – robjohn Mar 21 at 12:18
• I have some trouble understanding the first statement of your solution... – saisanjeev Mar 25 at 14:06
• It's not critical to anything else; that first statement is a heuristic for why the maximum should occur in the place it does, and is not used directly in the material that follows. If we're trying to maximize $\sum_i f(x_i)$ for fixed $\sum x_i$ and a concave function $f$, Jensen's inequality means that the $x_i$ should all be as close together as possible. If $f$ is convex instead, the opposite of Jensen's inequality means that the $x_i$ should be as far apart as possible. For a function that mixes convexity and concavity, we get a mix of the two behaviors instead. – jmerry Mar 25 at 18:49

Suppose we have a set of values of $$y_1,\ldots,y_n$$ summing to $$0$$ which maximise $$\sqrt[3]{y_1}+\cdots +\sqrt[3]{y_n}$$.

Suppose $$-1. If $$y_i+y_j<0$$ then subtracting a small amount from $$y_i$$ and adding it to $$y_j$$ increases the sum of cube roots, contradiction. If $$y_i+y_j>0$$ then we can subtract from $$y_j$$ and add to $$y_i$$, increasing the sum of cube roots, again a contradiction. Finally, if $$y_i+y_j=0$$ we can replace them both by $$0$$ without changing the sum of cube roots - then there must be a new pair $$y_i with sum $$>0$$, which we deal with as above.

Thus to maximise the sum of cube roots we must have some number $$k$$ of $$-1$$ terms and all others equal. The order doesn't matter, so we may assume the first $$k$$ are $$-1$$ and the rest equal - clearly this means each of the others is $$\frac{k}{n-k}$$. Now we just need to check which value of $$k$$ works best.

• can you please explain that step where you subtract a small amount from one of them and add it to the other... – saisanjeev Mar 25 at 14:18
• @saisanjeev if you change $x$ by a small value $\delta$, then $\sqrt[3]{x}$ changes by about $\delta$ times the derivative, i.e. $\frac13x^{-2/3}\delta$ (for $x\neq 0$). This is a bigger change the closer $x$ gets to $0$. So if you add a small amount to whichever of $y_i,y_j$ is closer to zero, and subtract it from the other one, the addition makes a bigger difference to $\sqrt[3]{y_i}+\sqrt[3]{y_j}$ than the subtraction, so the total increases. – Especially Lime Mar 25 at 15:27
• Thanks! But in the solution why has he assigned arbitrary value for $y_{k+1}$? – saisanjeev Mar 29 at 9:55

We want $$\sum_{k=1}^n\delta x_k=0\tag1$$ for all $$\delta x_k$$ so that $$\sum_{k=1}^nx_k^2\,\delta x_k=0\tag2$$ On the edge, $$x_k^2=1$$, and in the interior, orthogonality requires $$x_k^2=\lambda^2$$, for some $$0\le\lambda\lt1$$.

Let $$k$$ be the sum of the signs of the $$x_k^2=1$$ and $$m$$ be the sum of the signs of the $$x_k^2=\lambda^2$$. Then given $$k+m\lambda^3=0\tag3$$ we want to maximize $$k+m\lambda=m\!\left(\lambda-\lambda^3\right)\tag4$$ From which, we can see that $$m\ge0$$ and $$k\le0$$. We also have $$j=m-k\le n$$.

From $$(3)$$, we have $$k=-j\frac{\lambda^3}{1+\lambda^3}$$ and $$m=j\frac1{1+\lambda^3}$$. Thus, the maximum of $$(4)$$ is $$\sum_{k=1}^nx_k=k+m\lambda\le\frac{\lambda-\lambda^3}{1+\lambda^3}\,j\le\frac13\,n\tag5$$ where the maximum $$\frac{\lambda-\lambda^3}{1+\lambda^3}=\frac13$$ is attained at $$\lambda=\frac12$$.

• A counterexample to your claimed inequality: $n=1$, $x_1=-1$, $x_2=x_3=\cdots=x_9=\frac12$. The sum of the $x_n$ in that case is exactly $3=\frac n3$. – jmerry Mar 21 at 12:02
• I have fixed where $\lambda$ is optimized. I get the same $\lambda=\frac12$ now. – robjohn Mar 21 at 12:20
• $\frac{\lambda-\lambda^3}{1+\lambda^3}=\frac13-\frac{4(2\lambda-1)^2}{3(2\lambda-1)^2+9}$ – robjohn Mar 21 at 12:50
• For a given $n$, choose $m\approx\frac{8n}9$ and $k\approx-\frac{n}9$ and set $\lambda=\left(-\frac km\right)^{1/3}$. – robjohn Mar 21 at 18:04