Minimizing the symmetric sum $xy+yz+zx$ on $[-1,1]^3$

Question

I'm solving an $n$ dimensional optimization problem and have reduced the problem down to finding the minima of expressions like $xy+yz+zx$ or $wx+wy+wz+xy+xz+yz$ on the cube $[-1,1]^n$ for the appropriate $n$. For the first one, there is an easy (and tight) upper bound of 3 by repeated application of AM-GM. From a few numerical simulations I see that the minimum occurs when half of the variables are at -1 and the other half are at +1, but I'm not sure how to rigourously show this.

Answer 1

Let $n\geq2$ be given, let $Q:=[-1,1]^n$, and let $$\Phi(x):=\sum\nolimits_{1\leq j<k\leq n}x_j\,x_k\qquad(x\in Q)$$ be our objective function. Let $M\subset Q$ be the set of points $x\in Q$ where $\Phi$ assumes its minimal value. We now seek to characterize the points of $M$.

${\bf 1.}$ If $x$ has two entries $u$, $v\in\ ]{-1},1[\ $ then $x\notin M$.

Proof. Keep the other entries fixed, and let $s$ be their sum. The dependence of $\Phi$ on $u$ and $v$ is encaptured in the function $$\phi(u,v)=uv+(u+v) s\ .$$ Since the Hessian of $\phi$ has determinant $-1$ this function does not have a local minimum on $\ ]{-1},1[\,^2\>.\qquad\square$

${\bf 2.}$ It follows that an $x\in M$ has at most one entry $u\in\ ]{-1},1[\ $. The dependence of $\Phi$ on this entry is encaptured in the function $\phi(u)=s\,u$, where $s$ denotes the sum of the remaining entries. Unless $s=0$ we better choose $u\in\{{-1},1\}$ in order to minimize $\Phi$.

${\bf 3.}$ If $n$ is even then we cannot have $s=0$ with $n-1$ summands $\pm1$. It follows that in fact $x_i\in\{{-1},1\}$ for all $i$. Let $p$ of them be ${+1}$ and $q$ of them be ${-1}$. Then $$\Phi={p\choose 2}+{q\choose 2}-pq={1\over2}(p-q)^2-{1\over2}(p+q)\geq-{n\over2}\ .$$ It follows that the minimum is taken when $p=q={n\over2}$.

${\bf 4.}$ If $n$ is odd then we may have an $u\in\ ]{-1},1[\ $, and the rest of the $x_i$ are in $\{{-1},1\}$. Let $p$ of them be ${+1}$ and $q$ of them be ${-1}$. Then $$\Phi=(p-q)u+{1\over2}(p-q)^2-{1\over2}(p+q)\ .$$ The analysis of this case shows that the minimum is attained when $p=q={n-1\over2}$, while $u\in[{-1},1]$ may be chosen arbitrarily. I leave that to you.