# 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$?

#### Solutions Collecting From Web of "Optimising $x_1x_2+x_2x_3+\cdots+x_nx_1$ given certain constraints"

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.

This is too long for a comment, sorry to post that as an answer, but this question is puzzling me more than it should !
Here are more observations :

• For $n =2$, $S=-1$ with $x_1 = \frac{1}{\sqrt{2}},\ x_2 = -\frac{1}{\sqrt{2}}$ and this is the only way to satisfy the constraints.
• For $n=3$, $S=-1/2$ :
$$0^2 = (x_1 + x_2 + x_3)^2 = x_1^2 + x_2^2 + x_3^3 + 2S = 1 + 2S \implies S = -1/2$$
which is reached by $x_1 = \frac{1}{\sqrt{2}},\ x_2 = -\frac{1}{\sqrt{2}}, \ x_3 = 0$.
• For $n=4$, Mathematica says that the best $S = 0$ with $x_1 = 0,\ x_2 = \frac{1}{\sqrt{2}},\ x_3 =0,\ x_4 = -\frac{1}{\sqrt{2}}$.
• For $n=5$, Mathematica says that the best $S = \frac{\sqrt{5}-1}{4}\approx 0.309$ which is achieved by settings the $x$’s to be the root of some really ugly polynomials. Approximation are : $x_1 = -0.027,\ x_2 =-0.609,\ x_3 =-0.349,\ x_4 = 0.393, \ x_5 = 0.592$.

Usually with problem with high symmetry, the extrema occur either where the settings is also highly symmetric or highly asymmetric. Let us now consider $n = 2m$ even. Two possible symmetric assignments could be

• $x_i = \frac{1}{\sqrt{n}}\ \forall 1 \leq i \leq n/2, \ x_i = -\frac{1}{\sqrt{n}} \ \forall n/2 < i \leq n \implies S = \frac{n-4}{n}$
• $x_1 = x_{n/2} = 0,\ x_i = \frac{1}{\sqrt{n-2}}\ \forall 1 < i < n/2,\ -\frac{1}{\sqrt{n-2}}\ \forall n/2 < i < n \implies S = \frac{n-4}{n-2}$

Clearly the second is better than the first. Also as the OP mentionned, by increasing $n$ these two assignments can make $S$ arbitrarily close to $1$.

I would love to see more ideas about this problem which sounds simple and symmetric but based on the result for $n=5$ seems to hide way more complicated logic.