Fall 2016, problem 26

Let $x_i\ge -1$ and $\sum^n_{i=1}x_i^3=0$. Show that $\sum^n_{i=1}x_i \le \frac{n}{3}$.


5 years ago

Hello, I am a german mathematical physicist m.sc, ph.d Cambridge University. Hans R. Zimmermann

My solution is very simple. :

  1. substitute $z_i = x_i + 1$

  2. The summation reads now as: $\sum_{i=1}^n ( z_i^3 - 3z_i^2 + 3z_i - 1 ) = 0$

  3. So we have a polynomial of degree 3 and $\sum_{i=1}^n$ stands for summation from 1 to n . We now bring the -1 in the bracket to the right side and factor $z_i$ in the polynomial expression on the left. This leaves us with

    $\sum_{i=1}^n (z_i(z_i^2 -3z_i + 3))= n$

  4. We observe that a quadratic in z appears which is factored by z. The quadratic has a minimum value of 3/4 at its vertex. It follows that the expressun is aleays larger then $\sum_{i=1}^n \frac{3z_i}{4}$. Substituting again $z_i$ by $x_i+1$ leads to the unequality which we had to prove.

    $\sum_{i=1}^n x_i \le \frac{n}{3}$

I enjoy to contribute in honor of your founder.

EDIT: Moderator added in latex to make the answer easier to read.

Sorry, but my proof is perfectly valid. I used the substituion Z = X + 1. Go through my proof step by step. If I have an email I can send my writing. Regards, H. Zimmermann

DrHansZimmermann 5 years ago

I had a third solution based on splitting the x's into negative and nonnegative sets and using the convexity of x^3 but it is not worth detailing here because HRZ solution is simply brilliant !

Michel 5 years ago

The main reason we do not see more elegant solutions like the solution of HRZ is that the potential contributors are bound to enter LaTeX by hand. Is there a way to post a PDF or TIFF or a link to them ?

rubs 5 years ago

I apologize humbly to HRZ, who I wronged in an earlier comment in a lapse of judgement. Finally some welcome activity on the board and I decide it's my time for being discouraging. Honest mistake, I swear. I claim the opposite, of what I said and agree that your solution - contrary to mine - is indeed brilliant.

@rubs: While composing your post, you can insert an image file conveniently via a button right above the text draft. Right next to it there is a button for inserting html links. Just upload you PDF to your favorite free file hosting service and link it. I too would like to see more solutions - be they elegant or not - or discussions.

Nelix 5 years ago

The quadratic has a minimum value of 3/4 at its vertex. It follows that the expressun is aleays larger then ∑ni=13zi4.

richardsrobinso880 1 month ago
5 years ago

I apologize for the lengthiness of this proof. I'm probably making this seem harder than it actually is.

The basic idea behind it all is that the set $$S:=\{(x_1, ..., x_n) \in \mathbb{R}^n : \sum {x_i}^3 = 0 \textrm{ and } \forall i : x_i >= 1\}$$ is a compact subset of $\mathbb{R}^n$ and so $\sum x_i$ assumes a maximum on $S$, which we try to find in an explicit form as much as possible. What makes this approach kind of technical is that $S$ is not a smooth manifold, in which case you could maybe hope to find the maximum by a more straightforward variational calculation.

Anyway, here's the

Proof: If possible, pick $i$ and $j$, such that none of the numbers $x_i$ and $x_j$ is equal to -1 or 0. Define $$\begin{eqnarray*} s &:=& {x_i}^3 + {x_j}^3 \\ S &:=& x_i + x_j \\ x_i' &>=& 1 \textrm{ arbitrary} \\ x_j' &:=& (s - {x_i'}^3)^{\frac{1}{3}} \\ S' &:=& x_i' + x_j' \end{eqnarray*}$$

Then we have: $$ {x_i'}^3 + {x_j'}^3 = {x_i}^3 + {x_j}^3 = s$$

Here's how $S'$ changes, as we vary $x_i'$: $$\frac{dS'}{dx_i'} = \frac{d}{d x_i'} (x_i' + x_j') = 1 + \frac{dx_j'}{d x_i'} = 1 - \frac{{x_i'}^2}{{x_j'}^2}$$ Note that $\frac{dS'}{dx_i'} >= 0$ if $|x_i'| \leq |x_j'|$.

That means, that if we start with $x_i' = x_i$ and $x_j' = x_j$, we may increase the one with the smaller absolute value continuously without changing $s'$, without violating the restriction $x_i'$, $x_j' >= -1$ and without making $S'$ any smaller until one of two things happens:

  • One of $x_i'$ and $x_j'$ becomes 0 or -1
  • $|x_i'|$ becomes equal to $|x_j'|$

Since $S' >= S$ it always suffices to prove the estimate $\sum x_i \leq \frac{n}{3}$ for the tuple of numbers $(x_k)$ with $x_i$ and $x_j$ replaced by $x_i'$ and $x_j'$.

Using the arguments above you can reduce the problem to the case where the first $l$ numbers in the tuple $(x_k)$ are either equal to 0 or -1 and the remaining $(n -l)$ numbers all have the same absolute value. Moreover you can discard the $x_k$ that are equal to zero (say there are $z$ of them), since they they don't contribute to either $\sum x_i^3$ or $\sum x_i$ and $\sum_{i=1}^n x_i \leq \frac{n-z}{3}$ is an even better estimate then required.

Our situation has become considerably simpler now:

  • There are $a$ numbers equal to -1.
  • There are $b \neq 0$ numbers equal to $u > 0$.
  • There are $c = n - a - b$ numbers equal to $-u$.

The case $b = c$ can be excluded as trivial, since it would mean, that $\sum x_i = 0$. Therefore: $$ 0 = -a + b u^3 - c u^3 \implies u = \left (\frac{a}{b - c} \right )^{\frac{1}{3}}$$

So $$\sum_{i=1}^n x_i = -a + b u - c u = -a + (b - c)^{\frac{2}{3}} a^{\frac{1}{3}}$$

When you hold $a$ fixed, this expresion becomes largest for $b = n-a$ and $c=0$: $$\sum_{i=1}^n x_i \leq -a + (n - a)^{\frac{2}{3}} a^{\frac{1}{3}} = n \left (-\alpha + (1 - \alpha)^{\frac{2}{3}} \alpha^{\frac{1}{3}} \right )$$

Here we have defined $\alpha := \frac{a}{n}$, so $0 \leq \alpha \leq 1$. It is standard to show, that the function $f$ defined by $$\begin{eqnarray*} &&f: [0, 1] \to \mathbb{R} \\ &&\alpha \mapsto -\alpha + (1 - \alpha)^{\frac{2}{3}} \alpha^{\frac{1}{3}} \end{eqnarray*}$$ assumes a maximum of $\frac{1}{3}$ at $\alpha = \frac{1}{9}$. This concludes the proof.

3 years ago

Hans' proof is elegant! I came at the problem in a slightly different way, but the proof is essentially the same as Hans'.

Start with $\sum_{i=1}^n(x_i - \frac{1}{2})^2 (x_i+1) \ge 0$ since both $(x_i - \frac{1}{2})^2$ and $(x_i+1)$ are never negative.

This expands to $\sum_{i=1}^n(-\frac{3}{4}x_i+\frac{1}{4}) \ge 0$ where the identity $\sum_{i=1}^nx_i^3=0$ has been used.

Then do the sum over $\frac{1}{4}$ and rearrange to get $ \sum_{i=1}^nx_i \le \frac{n}{3}$