Maximising a sum - closed form? As a follow up to this question, I am wondering the following:
Suppose $\sum_{i=1}^n x_i=0,\;\sum_{i=1}^n x_i^2=1$. Is it there a closed form for $\max \sum_{i=1}^n x_ix_{i+1}?$ ($x_{n+1}=x_1$)
For $n=2,3$ the maximum is $-½$, for $n=4$ it is $0$. Beyond the problem becomes a bit of a drag, so I am wondering whether there is a nice, general approach.
 A: Let $M$ be the circulant matrix with $M_{i,i+1}=1$, $M_{n,1}=1$, all other entries $0$.  Let $u$ be the vector of all $1$'s.  You want to maximize $x^T M x$ subject to $u^T x = 0$ and $x^T x = 1$.  Using Lagrange multipliers, take
$$F(x,\mu,\lambda) = x^T M x + \lambda_1 u^T x + \lambda_2 (x^T x - 1)$$
From the gradient with respect to $x$ we get
$$ x^T (M + M^T) + \lambda_1 u^T + 2 \lambda_2 x^T = 0$$
Since $M u = M^T u = u$ and $x^T u = 0$, multiplying the left side by $u$ gives us
$\lambda_1 = 0$.  Then $x^T$ is a left eigenvector of $M + M^T$ for eigenvalue $-\lambda_2$. Now $M^T = M^{-1}$, and the eigenvalues of $M$ are the roots of unity $e^{2\pi ij/n}$, $j=0\ldots n-1$, so the eigenvalues of $M + M^T$ are
$e^{2\pi ij/n} + e^{-2\pi i j/n} = 2 \cos(2 \pi j/n)$.  The corresponding normalized real
eigenvectors have $x_k = n^{-1/2} \cos(2\pi jk/n)$ or $n^{-1/2}\sin(2\pi jk/n)$; they are orthogonal to $u$ (which is the eigenvector for $eigenvalue 1$) if $j \ne 0$, and they have objective value
$$ 2 n^{-1} \sum_{k=0}^{n-1} \cos(2\pi j k/n) \cos(2\pi j (k+1)/n)
= \cos(2\pi j/n)$$
The maximum for $j \ne 0$ is at $j=1$, i.e. $\cos(2\pi/n)$.
By the way, the answer for $n=2$ should be $-1$, not $-1/2$
(note that the objective should be 
$x_1 x_2 + x_2 x_3 = 2 x_1 x_2$, not just $x_1 x_2$).
A: I'd try to rewrite it as $$2\sum_{i}x_ix_{i+1} + 1=2\sum_{i}x_ix_{i+1} + \sum_i x_i^2 = \frac 12 \sum_i(x_i+x_{i+1})^2,$$
and the latter expression seems to be much easier to optimise.
