Optimizar $x_1x_2+x_2x_3+\cdots+x_nx_1$ dadas ciertas restricciones

Question

Para buscar el valor máximo de $S=x_1x_2+x_2x_3+\cdots+x_nx_1$ en este dominio:

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

He hecho algunas observaciones triviales:

1) $S\in[-1,1)$ por la desigualdad de reordenamiento.

2) Podemos hacer que $S$ se acerque arbitrariamente a $1$ aumentando $n$.

3) Un problema equivalente es minimizar $(x_1-x_2)^2+\cdots+(x_n-x_1)^2$.

¿Pero tiene el máximo una forma cerrada significativa para cada $n$?

Answer 1

Propongo hacer una transformada discreta de Fourier. Para ello, colocamos $\omega:=e^{2\pi i/n}$. En lo siguiente, todas las sumas son sobre ${\mathbb Z}_n$, a menos que se indique lo contrario. Sea $$y_k:={1\over n}\sum_l x_l\omega^{-kl}\ .$$ Dado que los $x_l$ son reales, tenemos que $$y_{-k}=\overline{y_k}\tag{1}$$ para todo $k$, además $y_0=\sum_lx_l=0$. Se tiene la fórmula de Parseval $$n\sum_k y_k\overline{ y_k}=\sum_l x_l^2=1\tag{2}$$ y la fórmula de inversión $$x_j=\sum_k y_k\omega^{jk}\ .\tag{3}$$ Usando $(3)$ se obtiene $$S=\sum_j x_jx_{j+1}=\ldots=n\sum_k|y_k|^2\omega^k\ .\tag{4}$$ En este punto hay que distinguir los casos (a) $n=2m$, y (b) $n=2m+1.

(a) Si $n=2m$ entonces $\omega^m=-1$, y $(4)$ da $$\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}$$ Dadas las condiciones $(1)$ y $(2)$ se ve fácilmente que la elección óptima admisible de los $y_k$ es $$y_1=y_{-1}={1\over\sqrt{2n}}\>,\qquad y_k=0\quad(k\ne\pm1)\ .\tag{5} $$ Esto conduce a $$S_{\rm opt}=\cos{2\pi\over n}\ .$$ En particular, cuando $n=4$ se obtiene $S_{\rm opt}=0$, como se indica en la respuesta de Zubzub.

(b) Si $n=2m+1$ entonces $(4)$ da $$S=2n\sum_{k=1}^m |y_k|^2\cos{2k\pi\over n}\ ,$$ y la elección $(5)$ lleva nuevamente a $$S_{\rm opt}=\cos{2\pi\over n}\ .$$ En particular, cuando $n=3$ se obtiene $S_{\rm opt}=-{1\over2}$, y cuando $n=5$ se obtiene $S_{\rm opt}=\cos{2\pi\over5}\doteq0.309$, como se indica en la respuesta de Zubzub.

Answer 2

¡Esto es demasiado largo para un comentario, lamento publicarlo como respuesta, pero esta pregunta me desconcierta más de lo que debería! Aquí hay más observaciones :

• Para $n =2$, $S=-1$ con $x_1 = \frac{1}{\sqrt{2}},\ x_2 = -\frac{1}{\sqrt{2}}$ y esta es la única forma de satisfacer las restricciones.
• Para $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 $$ lo cual se alcanza con $x_1 = \frac{1}{\sqrt{2}},\ x_2 = -\frac{1}{\sqrt{2}}, \ x_3 = 0$.
• Para $n=4$, Mathematica dice que el mejor $S = 0$ con $x_1 = 0,\ x_2 = \frac{1}{\sqrt{2}},\ x_3 =0,\ x_4 = -\frac{1}{\sqrt{2}}$.
• Para $n=5$, Mathematica dice que el mejor $S = \frac{\sqrt{5}-1}{4}\approx 0.309$ lo cual se logra configurando los $x$ como raíces de algunos polinomios realmente feos. Las aproximaciones son : $x_1 = -0.027,\ x_2 =-0.609,\ x_3 =-0.349,\ x_4 = 0.393, \ x_5 = 0.592$.

Por lo general, con problemas de alta simetría, los extremos ocurren donde la configuración también es altamente simétrica o altamente asimétrica. Ahora consideremos $n = 2m$ par. Dos posibles asignaciones simétricas podrían ser

• $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}$

Claramente, la segunda es mejor que la primera. Además, como mencionó el OP, al aumentar $n$ estas dos asignaciones pueden hacer que $S$ sea arbitrariamente cercano a $1$.

Me encantaría ver más ideas sobre este problema que parece simple y simétrico, pero según el resultado para $n=5$, parece esconder una lógica mucho más complicada.