# Optimization- How to show sum of cubes is minimum?

Given $n$ positive integers $x_i,i=1,2,\ldots,n,$ such that $$x_1+x_2+\cdots+x_n=q$$ The sum of their cubes is $$x_1^3+x_2^3+\cdots+x_n^3$$

With the help of some examples I found that sum of cubes is minimum when numbers are almost equal ($|x_i-x_j|\le1$). But I am unable to prove this. Please help.

• Have you tried Lagrange multipliers? If you put $g(x,y,\lambda)=\sum_{i} (x_i^3) - \lambda\left(\sum_i (x_i) - q \right)$ you will obtain that the minimum happens exactly when $\lambda=\frac{x_i}{3}$ and $x_i=\frac{q}{n}$ for all $i\leq n$. – Darío G Aug 24 '16 at 10:19
• Do you mean for the $x_i$ to be integers (as the condition $|x_i - x_j| \leq 1$ seems to suggest)? – Travis Willse Aug 24 '16 at 10:21
• Yes, $x_i$ are integers. – Camran Aug 24 '16 at 18:49
• @Wore I think $\lambda=\frac{x_i^2}{3}$??? – Camran Aug 24 '16 at 18:57
• @Camran Yes, $\lambda=\frac{x_i^2}{3}$. Although it does not matter anymore since the $x_i$ have to be integers. – Darío G Aug 25 '16 at 12:42

Here I assume, as the given condition suggests, that the $x_i$ must be integers.

Hint Suppose you have two numbers, $x_i, x_j$ in a partition of $q$ into positive integers such that $|x_i - x_j| > 1$, and w.l.o.g. suppose $x_i > x_j$. What happens to the sum of cubes if you replace $x_i$ with $x_i - 1$ and $x_j$ with $x_j + 1$ (which in particular gives another partition of $q$)?

You can use the power means inequality: if $x_1, x_2,\dots, x_n$ are positive numbers, their $p$-th power mean is $$M_p(x_1,x_2,\dots,x_n)=\Biggl(\frac{x_1^p+x_2^p+\dots+x_n^p}n\Biggr)^{\!\tfrac1p}.$$

The *power means inequality states that

if $p<r$, then $\;M_p(x_1,x_2,\dots,x_n)\le M_r(x_1,x_2,\dots,x_n)$, and both means are equal if and only if for each $1\le i,j\le n$, $\;x_i=x_j$.

Apply this inequality to the arithmetic mean $(p=1)$ and the cubic mean $(r=3)$ to obtain $$\sum_{i=1}^n x_i^3 \ge \frac{q^3}{n^2}$$ Equality happens when all $x_i$s are equal.

Theorem: If p is a positive integer greater than 1 and x_i are elements of {0, 1 , 2 , 3, …, q} i goes from 1 to n, such that the sum of the n x_i's is q, then the sum of (x_i)^p from 1 to n is minimized when the x_i's are within at most 1 of each other.

Lemma: for 0 <= a <= 1/2, g(a) = (1/2 + a)^p + (1/2 - a)^p is strictly monotonically increasing. This is because g(a) is a polynomial with non-negative coefficients.

Proof: Take n and d both positive integers and d is greater than 1.

n^p + (n+d)^p = (2n+d)^p [(n/(2n+d))^p +((n+d)/(2n+d))^p]

n^p + (n+d)^p = (2n+d)^p g(d/[2(2n+d)]) where g is define in the lemma. Note: we can add to n as we subtract from n + d until we are within 1 (if both are odd) or zero (if both are even) without effecting the denominator, 2(2n+d), and minimize the sum. Apply repeatedly. Q.E.D.