Fall 2016, problem 26

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.

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.

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}$