Minimizing $x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1$ Look at the expression 
$$
f(x_1,x_2,x_3) = x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1. 
$$
The numbers $x_1,x_2,x_3$ are non-negative, and I assume that $x_1+x_2+x_3=3$. This is a sum of squares and "cyclic correlations" of consecutive variables. Then you can check that $f$ is minimized for the values $x_1=x_2=x_3=1$.
Now look at
$$
g(x_1,x_2,x_3,x_4) = x_1^2+x_2^2+x_3^2+x_4^2+x_1x_2+x_2x_3+x_3x_4+x_4x_1,
$$
under the assumption that $x_1+x_2+x_3+x_4=4$. Again, this is minimized by $x_1 = x_2 = x_3 = x_4=1$.
A similar thing happens if I add "second-order cyclic correlations": Let
$$
h(x_1,x_2,x_3,x_4) = x_1^2+x_2^2+x_3^2+x_4^2+x_1x_2+x_2x_3+x_3x_4+x_4x_1+x_1x_3+x_2x_4+x_3x_1+x_4x_2,
$$
again under the assumption that $x_1+x_2+x_3+x_4=4$. This is also minimized for the values $x_1=x_2=x_3=x_4=1$.
Is there a simple explanation for this? Is there a simple argument showing that the same will happen for, say, 12 variables and correlations of order up to 3?
 A: Minimizing $f$ and $h$ subject to the given constraints are quadratic programs of the form
$$\begin{array}{ll} \text{minimize} & \frac 12 \mathrm x^{\top} \mathrm A \,\mathrm x\\ \text{subject to} & 1_n^{\top} \mathrm x = n\\ & \mathrm x \geq\mathrm 0_n\end{array}$$
where
$$\mathrm A := \mathrm I_n + 1_n 1_n^{\top}$$
Let us temporarily ignore the non-negativity constraints. The Lagrangian is
$$\mathcal{L} (\mathrm x, \lambda) := \frac 12 \, \mathrm x^{\top} \mathrm A \,\mathrm x - \lambda (1_n^{\top} \mathrm x - n)$$
Taking the partial derivatives and finding where they vanish, we obtain
$$\mathrm A \mathrm x = \lambda 1_n \qquad \qquad \qquad 1_n^{\top} \mathrm x = n$$
Hence, we conclude that the minimizers are
$$\bar{\mathrm x} := \left( \frac{n}{1_n^{\top} \mathrm A^{-1} 1_n} \right) \mathrm A^{-1} 1_n \qquad \qquad \qquad \bar{\lambda} :=  \frac{n}{1_n^{\top} \mathrm A^{-1} 1_n}$$
Using Sherman-Morrison, the inverse of $\mathrm A$ is
$$\mathrm A^{-1} = (\mathrm I_n + 1_n 1_n^{\top})^{-1} = \mathrm I_n - \left(\frac{1}{1+n}\right) 1_n 1_n^{\top}$$
Hence,
$$\mathrm A^{-1} 1_n = \frac{1}{1+n} 1_n$$
and
$$1_n^{\top} \mathrm A^{-1} 1_n = \frac{n}{1+n}$$
Thus, the minimizer is
$$\bar{\mathrm x} := \left( \frac{n}{1_n^{\top} \mathrm A^{-1} 1_n} \right) \mathrm A^{-1} 1_n = \left( \frac{n}{\frac{n}{1+n}} \right) \frac{1}{1+n} 1_n = \color{blue}{1_n}$$
which satisfies the non-negativity constraints.
A: The question is about the signature of a quadratic form
$$
\sum_{i=1}^n x_i^2 + \frac12\sum_{1 \le \mathrm{dist}(i,j) \le p} x_ix_j
$$
(or about the spectrum of the corresponding linear operator). The matrix is a circulant matrix, see Wikipedia, and its eigenvectors are
$$
v_k = (1, \omega^k, \ldots, \omega^{k(n-1)}),
$$
where $\omega = e^{\frac{2\pi i}{n}}$. The eigenvalues are easy to compute:
$$
\lambda_k = \frac12 + \frac12 \sum_{i=-p}^{i = p} \omega^{ki} = \frac12 + \frac12 \frac{\omega^{\frac{(2p+1)k}{2}} - \omega^{\frac{-(2p+1)k}{2}}}{\omega^{\frac{k}2} - \omega^{-\frac{k}2}} = \frac12 + \frac12 \frac{\sin \frac{(2p+1)k\pi}{n}}{\sin \frac{k\pi}{n}}.
$$
Unfortunately, there may be negative eigenvalues. For example, for $n=7$, $p=2$ we have
$$
\lambda_5 = \frac12 + \frac12 \frac{\sin\frac{25\pi}7}{\sin\frac{5\pi}7} < 0.
$$
Thus for seven variables and cyclic sums up to order two the minimum will not be attained at $x_1 = \cdots =x_7 = 1$.
