Htykuut

This is from a Brazilian math contest for college students (OBMU):

Given a positive integer $n$, find the maximum value of

$$x_1^3+x_2^3+ cdots + x_n^3$$

where $x_j$ is a real number for all $j in {1,2,cdots, n}$ such that $x_1 + x_2 + cdots + x_n = 0$ and $x_1^2 + x_2^2 + cdots + x_n^2 = 1$ .

One could indeed use Lagrange multipliers, but I thought I'd try to get geometric intuition in three dimensions.

This shows the constraint sphere $x_1^2 + x_2^2 + x_3^2=1$ and the constraint plane $x_1 + x_2 + x_3 = 0$, and the locus of their intersection, a (black) ring. The plane is perpendicular to the normalized vector ${bf a} = (1/sqrt{3}, 1/sqrt{3}, 1/sqrt{3})$. One (normalized) vector perpendicular to ${bf a}$ is ${bf b} = left( frac{1}{sqrt{6}},frac{1}{sqrt{6}},-frac{2}{sqrt{6}} right)$. Another (normalized) vector perpendicular to both is ${bf c} = left( -frac{1}{sqrt{2}},frac{1}{sqrt{2}},0right)$, determined by ${bf c} = {bf a} times {bf b}$.

Thus any potential solution point can be described as $(x_1, x_2, x_3) = cos (theta) {bf b} + sin (theta) {bf c}$.

Direct substitution, cubing the components and simplification yields $x_1^3 + x_2^3 + x_3^3 = -frac{cos (3 theta )}{sqrt{6}}$.

It is a simple matter to maximize this function of a single variable $theta$ and find that the solution is $1/sqrt{6}$.

Not surprisingly there are three equivalent solutions, corresponding to the permutation of the three variables.

As a check, I find the solution vector with $theta = 1$ (from the graph) to be ${bf s} = (-0.374432, 0.815587, -0.441155)$ indeed obeys the constraints and leads to the criterion sum-of-cubes to be $0.404163$, as visible on the graph.

Hint: Try to use the technique of Fourier Analysis. We can reasonably guess that the maximum occurs when $x_i = -frac{1}{sqrt{n(n-1)}}, forall i<n$ and $x_n = sqrt{1-frac{1}{n}}.$

View $x_{cdot}$ as a function defined on the group $mathbf{Z}/nmathbf{Z}$. Let $zeta = exp(frac{2pi i}{n})$ be $n$-th root of unity and define its $r$-th Fourier coefficient as $s^{}(r) = frac{1}{n}sum_{k=1}^{n}x_kzeta^{-rk}.$ We note that
$$x_j = sum_{r=0}^{n-1}s(r)zeta^{rj}, quad forall j=1,ldots,n,$$ and
$$ sum_{1leq jleq n} |x_j|^2 = nsum_{1leq rleq n}|s(r)|^2,
$$ since $frac{1}{n}sum_{1leq rleq n} zeta^{rm} =1_{{m=0}}$. Express the constraints in the language of $s(r)$ (including $x$ is real-valued.) Then we get
$$s(r) =overline{s(n-r)},; s(0) = 0,; sum_{1leq rleq n}|s(r)|^2 = frac{1}{n}. $$
What is left is to express $Q = x_1^3 + cdots + x_n^3$ as a function involving $s(r)$'s. From the first identity above, we have
$$Q = nsum_{1leq r,r'leq n}s(r)overline{s(r')}s(r-r'). $$ Note that the support is
$$R = {(r,r');| ;1leq r,r'leq n-1, rneq r'}.$$ By applying Cauchy-Schwarz, we have
$$begin{eqnarray}|sum_{1leq r,r'leq n}s(r)overline{s(r')}s(r-r')|^2&leq& sum_{(r,r')in R}|s(r)|^2|s(r-r')|^2sum_{(r,r')in R}|s(r')|^2 \
&=&sum_{1 leq rleq n-1}|s(r)|^2left(frac{1}{n} - |s(r)|^2right)cdotsum_{1 leq rleq n-1}frac{1}{n} - |s(r)|^2 \
&=&left(frac{1}{n^2} - sum_{1 leq rleq n-1} |s(r)|^4right)frac{n-2}{n}\
&leq& frac{(n-2)^2}{n^3(n-1)},
end{eqnarray}$$ since $frac{1}{n^2} leq (n-1)sum_{1 leq rleq n-1} |s(r)|^4$.
Thus, we have
$$Q leq frac{n-2}{sqrt{n}sqrt{n-1}},$$ as desired.

I come up with a solution using Lagrange Multipliers (one of the comments and one of answers suggests to use this). First, we need to realize that the domain

$$ S ={ (x_1,x_2,cdots,x_n) in {mathbb{R}}^n | x_1 + x_2 + cdots + x_n = 0 text{ and } x_1^2 + x_2^2 + cdots + x_n^2 = 1} $$

is closed (since the functions $(x_1,x_2,cdots,x_n ) mapsto x_1 + x_2 + cdots + x_n$ and $(x_1,x_2,cdots,x_n ) mapsto x_1^2 + x_2^2 + cdots + x_n^2$ are continuous) and bounded (since $x_1^2 + x_2^2 + cdots + x_n^2 = 1$). Then S is compact.

Define
$$f(x_1,x_2,cdots,x_n ) = x_1^3 + x_2^3 + cdots+ x_n^3 $$
$$g(x_1,x_2,cdots,x_n ) = x_1^2 + x_2^2 + cdots+ x_n^2 -1 $$
$$h(x_1,x_2,cdots,x_n ) = x_1 + x_2 + cdots+ x_n $$

Since $S$ is compact and $f$ is continuous, then $f$ reaches a maximum value in
$S$. Using Lagrange Multiplier, we should have

$$nabla f = lambda_1 nabla g + lambda_2 nabla h$$

Thus,

$$ 3(x_1^2,x_2^2,cdots,x_n^2) = 2lambda_1(x_1,x_2,cdots,x_n ) + lambda_2(1,1,cdots,1)$$

Then,

$$3x_i^2 = 2lambda_1 x_i+ lambda_2 text{ } forall i in {1,2,cdots,n} label{1}tag{1}$$

If we add all the equations and use the constraints equations, we obtain $lambda_2= frac{3}{n}$. Then,

$$3x_i^2 = 2lambda_1 x_i+ frac{3}{n} $$

Solving for $x_i$, we obtain

$$ x_i = frac{lambda_1 pm sqrt{lambda_1^2 + frac{9}{n}}}{3} $$

Let $k$ be a natural number less or equal to $n$. Therefore we can suppose

$$ x_i = frac{lambda_1 + sqrt{lambda_1^2 + frac{9}{n}}}{3} forall i in {1,2,cdots,k}$$

$$ x_i = frac{lambda_1 - sqrt{lambda_1^2 + frac{9}{n}}}{3} forall i in {k+1,k+2,cdots,n}$$

Firtly, notice that $k$ is different of $0$ and $n$, because of the constraint $x_1+ x_2 + cdots + x_n =0$. Using the constraint $x_1^2 + x_2^2 + cdots + x_n^2 = 1$ and after some simplifications, we obtain

$$lambda_1 left(nlambda_1 + (2k-n) sqrt{lambda_1^2 + frac{9}{n}} right) = 0label{2}tag{2}$$

And using $x_1+ x_2 + cdots + x_n =0$, we get

$$ nlambda_1 + (2k-n) sqrt{lambda_1^2 + frac{9}{n}} = 0 label{3}tag{3}$$

So, we just need to satisfy ref{3}, because with that ref{2} is automatically satisfied. Then, we get

$$lambda_1 = frac{3(n-2k)}{2sqrt{(n-k)nk}} $$

Notice that we should consider the other solution with the other sign, but in the end we obtain the same maximum value for both cases. Multiplying ref{1} by $x_i$:

$$ 3x_i^3 = 2lambda_1x_i^2 + frac{3x_i}{n} $$

Adding in all i's:

$$3f = 2lambda_1 $$

Thus,

$$ f(k) = frac{n-2k}{sqrt{(n-k)nk}} = frac{1}{sqrt{n}}left(sqrt{frac{n-k}{k}}-sqrt{frac{k}{n-k}}right)$$

Remember that $k in {2,3,cdots, n-1}$. Making $x = sqrt{frac{k}{n-k}}$ and analyzing the derivative of

$$y: (0,1) rightarrow mathbb{R}$$
$$ x mapstofrac{1}{x}-x $$

We see that the maximum value of $f$ is when $k=1$, that is,

$$ frac{n-2}{sqrt{(n-1)n}} $$

However, the Lagrange Multipliers just find the local extrema. How can I guarantee (if it's possible) that the above value is indeed the maximum value of $f$?