Optimising $x_1x_2+x_2x_3+\cdots+x_nx_1$ given certain constraints

To seek the maximum value of $S=x_1x_2+x_2x_3+\cdots+x_nx_1$ on this domain:

$x_1+x_2+\cdots+x_n=0$ and $x_1^2+x_2^2+\cdots+x_n^2=1$.

I have made some trivial observations:

1) $S\in[-1,1)$ by the rearrangement inequality.

2) We can make $S$ arbitrarily close to $1$ by increasing $n$.

3) An equivalent problem is to minimise $(x_1-x_2)^2+\cdots+(x_n-x_1)^2$.

But does the maximum have a meaningful closed form for each $n$?

Solution 1:

I propose to do a discrete Fourier transform. To this end put $\omega:=e^{2\pi i/n}$. In the following all sums are over ${\mathbb Z}_n$, unless indicated otherwise. Let $$y_k:={1\over n}\sum_l x_l\omega^{-kl}\ .$$ Since the $x_l$ are real we have $$y_{-k}=\overline{y_k}\tag{1}$$ for all $k$, furthermore $y_0=\sum_lx_l=0$. One has Parseval's formula $$n\sum_k y_k\overline{ y_k}=\sum_l x_l^2=1\tag{2}$$ and the inversion formula $$x_j=\sum_k y_k\omega^{jk}\ .\tag{3}$$ Using $(3)$ one computes $$S=\sum_j x_jx_{j+1}=\ldots=n\sum_k|y_k|^2\omega^k\ .\tag{4}$$ At this point we have to distinguish the cases (a) $n=2m$, and (b) $n=2m+1$.

(a) If $n=2m$ then $\omega^m=-1$, and $(4)$ gives $$\eqalign{S&=n\left(\sum_{k=1}^{m-1}|y_k|^2(\omega^k+\omega^{-k}) \ +|y_m|^2\omega^m\right)\cr &=n\left(\sum_{k=1}^{m-1}|y_k|^2\>2\cos{2k\pi\over n} \ -|y_m|^2\right)\ .\cr}$$ Given the conditions $(1)$ and $(2)$ it is easily seen that the optimal admissible choice of the $y_k$ is $$y_1=y_{-1}={1\over\sqrt{2n}}\>,\qquad y_k=0\quad(k\ne\pm1)\ .\tag{5} $$ This leads to $$S_{\rm opt}=\cos{2\pi\over n}\ .$$ In particular when $n=4$ one obtains $S_{\rm opt}=0$, as indicated in Zubzub's answer.

(b) If $n=2m+1$ then $(4)$ gives $$S=2n\sum_{k=1}^m |y_k|^2\cos{2k\pi\over n}\ ,$$ and the choice $(5)$ leads again to $$S_{\rm opt}=\cos{2\pi\over n}\ .$$ In particular when $n=3$ one obtains $S_{\rm opt}=-{1\over2}$, and when $n=5$ one obtains $S_{\rm opt}=\cos{2\pi\over5}\doteq0.309$, as indicated in Zubzub's answer.