# How find the minmum of the value $f=x^2_{1}+x^2_{2}+\cdots+x^2_{n}-x_{1}x_{2}-x_{2}x_{3}-\cdots -x_{n}x_{1}$

Assume the $$n$$ is give postive integer,let the pairwise distinct integers $$x_{1},x_{2},\cdots,x_{n},n\ge 0$$. find the minmum of the value $$f=x^2_{1}+x^2_{2}+\cdots+x^2_{n}-x_{1}x_{2}-x_{2}x_{3}-\cdots -x_{n}x_{1}$$

I know $$2f=\sum_{i=1}^{n}(x_{i}-x_{i+1})^2 =\sum_{i=1}^{n-1}(x_{i+1}-x_{i})^2+(x_{n}-x_{1})^2\ge (n-1)+(n-1)^2=n^2-n?$$ I fell this reslut is not true,so How to slove it?

• but I think $(x_{n}-x_{1})^2\ge (n-1)^2$ maybe some wrong. Commented Nov 1, 2019 at 13:32
• Indeed, that may not be the minimum. For $n=4$ and $(x_i) = (1, 2, 4, 3)$ the expression is $1^2+2^2+1^2+2^2 = 10 < 12$. Commented Nov 1, 2019 at 13:40
• yes,so how to solve this problem? Commented Nov 1, 2019 at 13:51
• Possible duplicate of Minimum sum of the squares Commented Nov 1, 2019 at 14:13
• It looks as if it's not yet proved then?
– user502266
Commented Nov 1, 2019 at 14:26

With $$y_i=x_{i+1}-x_i$$ (and $$y_n=x_1-x_n$$), you showed that $$\tag12f=\sum_{i=1}^n y_i^2.$$ If there is an integer $$m$$ with $$\min x_i, then replacing all $$x_i>m$$ with $$x_i-1$$ still leaves us with distinct integers, none of the summands in $$(1)$$ increases, at least two summands decrease. We conclude that in the minimal case, the $$x_i$$ are consecutive integers (in some order). Also, $$(1)$$ shows that replacing all $$x_i$$ with $$x_i+d$$ leaves $$f$$ unchanged. Thus we may assume that $$x_1,x_2,\ldots, x_n$$ is a permutation of $$1,2,\ldots, n$$.

Assume $$(x_1,\ldots,x_n)$$ is a minimizer. Pick $$i,j$$ with $$j-i\ge 3$$. Then the value of $$(x_1,x_2,\ldots, x_i,x_{j-1},x_{j-2}\ldots, x_{i+1},x_j,x_{j+1},\ldots, x_n)$$ (i.e., the terms between $$x_i$$ and $$x_j$$ reversed) differs from that of $$(x_1,\ldots, x_n)$$ by $$x_{j-1}x_i+x_{i+1}x_j-x_ix_{i+1}-x_{j-1}x_j=(x_{j-1}-x_{i+1})(x_i-x_j).$$ As this must be non-negative, we conclude that

$$(2)$$ In a minimizer, the sign of $$x_{j-1}-x_{i+1}$$ is the same as the sign of $$x_j-x_i$$ for $$j\ge i+3$$.

Assume that $$\{x_1,\ldots x_r\}=\{1,\ldots r\}$$. Assume $$x_k=r+1$$ with $$r+1< k. Then $$x_{r+1}>x_k$$, hence by $$(2)$$, we have $$r\ge x_r>x_{k+1}>r$$, contradiction. It follows that $$x_{r+1}=r+1$$ or $$x_n=r+1$$. If additionally $$x_1>x_r$$ and $$r, it follows from $$(2)$$ that $$x_{r+1} so that only the case $$x_{r+1}=r+1$$ remains. As the sequence can be cyclically rearranged, we conclude by induction that it can be constructed as follows: Start with $$1,2$$, and then for $$i=3,\ldots, n$$, append $$i$$ to the end with the smaller number (which is $$i-2$$). Clearly, this leads to all odd numbers appended to the left of $$1$$ and all even numbers appended to the right of $$2$$. We end up with a minimizer with $$|x_{i+1}-x_i|=2$$ (cyclically) for all $$i$$ except that $$|x_{i+1}-x_i|=1$$ for two $$i$$ (once near $$1$$ and once near $$n$$). By $$(1)$$, this leads to $$2f=(n-2)\cdot 2^2+2\cdot 1^2$$, or $$f=2n-3.$$

For the integers from $$1$$ to $$n$$ you can make two differences $$1$$ and all other differences $$2$$ by arranging the numbers as:-

$$..., 5,3,1,2,4,6....$$ with $$n$$ eventually reached on one side or another.

This gives a total of $$4n-6$$.

Note that there is no loss of generality in assuming that integers are from $$1$$ to $$n$$ because:

they can be translated until the smallest $$x_i$$ is $$1$$;

if the largest $$x_i$$ were greater than $$n$$ then we could simply reduce $$2f$$ by subtracting 1 from some of the larger $$x_i$$ without making two of the $$x_i$$ equal.

Proof

In general, we have two chains of numbers from $$1$$ to $$n$$ and therefore we have $$n$$ integers (the differences) such that$$d_1+d_2+...+d_n=2(n-1) \;\;\;\;(1)$$ and we wish to prove that $$d_1^2+d_2^2+...+d_n^2\ge 4n-6.$$

We can assume the $$d_i$$ are non-negative. Suppose two of the $$d_i$$ were $$a$$ and $$b$$ where $$b\ge a+2$$. Then replacing $$a$$ and $$b$$ by $$a+1$$ and $$b-1$$ decreases the sum of squares.

Therefore, for the minimum, the $$d_i$$ can only take two values which differ by $$1$$. From equation (1) these values must be $$1$$ and $$2$$ giving the above solution.

Therefore the minimum value of $$f$$ is $$2n-3.$$

• That looks promising. Can you prove that it is the minimum possible value? Commented Nov 1, 2019 at 14:11
• I've tried but not yet been successful. I think one can do it by thinking of a graph connecting numbers and then switching bits of the path around if gaps are greater than 2.
– user502266
Commented Nov 1, 2019 at 14:12
• In the end it was much simpler than I had thought it was going to be.
– user502266
Commented Nov 1, 2019 at 16:39