# Maximizing a sum of inner products

Someone asked this question on a French maths forum here and it caught my attention.

The question is the following: let $(E, \langle \cdot, \cdot \rangle)$ be a Euclidean vector space. Find the minimum and maximum possible values of the sum $$\langle u_1, u_2 \rangle + \langle u_2, u_3 \rangle + \dots + \langle u_{n-1}, u_n \rangle + \langle u_n, u_1 \rangle$$ when the $u_k$ are unit vectors whose sum is zero.

 

Edit: Okay, since there is no answer so far, let me write here what I came up with, maybe someone will know how to follow. Of course, there could be a much better approach!

Let's introduce a couple of notations. Let $E^n$ denote the $n$-fold space with its inner product derived from $E$ (*) and let $\varphi$ and $\psi$ denote the functions defined by: $$\varphi: \left\{ \begin{array}{ccc} E^n & \rightarrow &\mathbb{R} \\ u = (u_1, \dots, u_n) &\mapsto & \langle u_1, u_2 \rangle + \dots + \langle u_n, u_1 \rangle \end{array} \right.$$ $$\psi: \left\{ \begin{array}{ccc} E^n & \rightarrow &\mathbb{R}^n \times E \\ u = (u_1, \dots, u_n) &\mapsto & \left((||u_i||^2 - 1)_{k= 1 \dots n}\,,\, \sum_{k=1}^n u_k\right)\\ \end{array} \right.$$

So the question is: find the extrema of $\varphi$ on the level set $K := \{\psi = 0\}$. Note that $K$ is compact (NB: it looks like a "slice" of an $n$-fold product of hyperspheres, whatever) so $\varphi$ has a minimum and a maximum on $K$ indeed. What are their values?

Let's see what differential calculus tells us (**). Let $u = (u_1, \dots, u_n)$ be a local extremum of $\varphi_{|K}$. The derivative of $\varphi$ at $u$ must kill tangent vectors to $K$, which amounts to say that $\mathrm{Ker}\, D_u \psi \subset \mathrm{Ker}\, D_u \varphi$. It is straightforward to compute these derivatives and their kernels, they are given by: $$\mathrm{Ker}\, D_u \varphi = \{v\}^\perp$$ where $v = (u_n + u_2, u_1 + u_3, \dots, u_{n-1} + u_1) \in E^n$, and $$\mathrm{Ker}\, D_u \psi = ({L_1}^\perp \times \dots \times {L_n}^\perp) ~ \cap ~ \Delta^\perp$$ where $L_k$ denotes the line through $u_k$ in $E$ and $\Delta$ denotes the diagonal in $E^n$.

The condition $\mathrm{Ker}\, D_u \psi \subset \mathrm{Ker}\, D_u \varphi$ then amounts to saying that $v \in ({L_1}\times \dots \times {L_n}) ~ + ~ \Delta$.

In conclusion: if $u = (u_1, \dots, u_n)$ is a local extremum of $\varphi$ restricted to $K$, then there exists scalars $\lambda_1, \dots, \lambda_n$ and a vector $a \in E$ such that: \begin{align*} u_n + u_2 &= \lambda_1 u_1 + a \\ u_1 + u_3 &= \lambda_2 u_2 + a \\ & \cdots \\ u_{n-1} + u_1 & = \lambda_n u_n + a \end{align*}

What can we derive from that? First, note that $a$ is given by $0 = \sum_{k=1}^n \lambda_k u_k + na$ (sum all the equations). Also, the value of $\varphi$ at this point $u$ is given by $\sum_{k=1}^n \lambda_k / 2$. More importantly, it is easy to see inductively that all the $u_k$ lie in a same $3$-dimensional subspace of $E$.

That's all that I could derive from these equations unfortunately. But I think it should be possible to make them confess more, maybe using a symmetry argument. Here is what I suspect: $a$ must be $0$ and all the $\lambda_k$ must be equal. It follows that all the $u_k$ are coplanar and that the angle between $u_k$ and $u_{k+2}$ is constant. Finally, in a nutshell, break into cases according to whether $n$ is even or odd. In both cases, the maximum is achieved when the $u_k$ lie like $n$-th roots of unity on the circle, and it is given by $n \cos (2\pi / n)$. When $n$ is even, the minimum is $-n$ (just take $u_1 = u_3 = \dots = u_{n-1} = -u_2 = -u_4 = \dots = -u_n$) and when $n$ is odd, $-n \cos(2\pi/n)$ (not totally sure about that last one).

Wow, this is much longer than I expected, hope I didn't bore too many people to death.

 

(*) It is given by $\langle u, v \rangle = \sum_{k=1}^n \langle u_k, v_k \rangle$.

(**) in what follows, I recover some version of Lagrange's multiplier "manually". You may skip that part and jump to the set of linear equations if you don't like what you see :)

• What do you mean by "tangent" vectors? – Siméon Nov 25 '13 at 12:38
• Could you specify the dimension of vector space? – Shuchang Nov 25 '13 at 15:32
• @Seub So $n$ is irrelavent to $d$? – Shuchang Nov 28 '13 at 3:59
• @Seub $\dim E \neq n$ in general? – cactus314 Dec 1 '13 at 13:10
• @john mangual : yes, no assumption on dim E – Seub Dec 1 '13 at 20:39

For $d={\rm dim}(E)\ge2$ and $n\ge2$ we have bounds $$L_n\le\langle u_1,u_2\rangle+\langle u_2,u_3\rangle+\cdots+\langle u_n,u_1\rangle\le U_n$$ where \begin{align} L_n&=\begin{cases} -n,&{\rm for\ }n{\rm\ even},\\ -n\cos(\pi/n),&{\rm for\ }n{\rm\ odd} \end{cases} \cr\cr U_n&=n\cos(2\pi/n). \end{align} For convenience, I'll use $Q(u)$ to denote the sum $\sum_{k=1}^n\langle u_k,u_{k+1}\rangle$, and the subscript $k$ in $u_k$ will be taken modulo $n$ so that, in particular, $u_{n+1}=u_1$. The bounds above can be attained by taking $u_k$ of the form $$u_k=\cos(2\pi jk/n)e_1+\sin(2\pi jk/n)e_2$$ where $e_1,e_2\in E$ is an orthogonal pair of unit vectors and $j$ is a fixed integer. Then, $\langle u_k,u_{k+1}\rangle = \cos(2\pi j/n)$ and $Q(u)=n\cos(2\pi j/n)$. Furthermore, $\sum_ku_k=0$ as long as $j$ is not a multiple of $n$. Taking $j=1$ gives $Q(u)=U_n$. The lower bound is attained by $j=n/2$ for even $n$ and $j=(n-1)/2$ for odd $n$.

It just remains to show that the bounds $L_n\le Q(u)\le U_n$ do indeed hold for any choice $u_k$ of unit vectors with $\sum_{k=1}^nu_k=0$.

Lower bound: The lower bound actually holds without the constraint that $\sum_ku_k=0$. For even $n$, this is easy. As $\langle u_k,u_{k+1}\rangle\ge-1$, we have $$Q(u)\ge\sum_{k=1}^n(-1)=-n=L_n.$$ I'll now consider odd $n\ge3$. By compactness, we can find unit vectors $u_k$ minimizing $Q(u)$. For any $\eta_k$ orthogonal to $u_k$, and replacing $u_k$ by $(u_k+\epsilon\eta_i)/\sqrt{1+\epsilon^2\lvert\eta_k\rvert^2}$, the quantity $Q(u)$ varies by $\epsilon\langle\eta_k,u_{k-1}+u_{k+1}\rangle$ to first order in $\epsilon$. As this must vanish at the minimum of $Q$, we have $u_k$ parallel to $u_{k+1}+u_{k-1}$. So, $u_{k-1}+u_{k+1}=\lambda_ku_k$ for scalars $\lambda_k$.The terms in $Q(u)$ involving $u_k$ are $$\langle u_{k-1},u_k\rangle+\langle u_k,u_{k+1}\rangle=\langle u_k,u_{k-1}+u_{k+1}\rangle=\lambda_k.$$ If $\lambda_k=0$ for any $k$, then the terms involving $u_k$ vanish, so $Q(u)$ is a sum of $n-2$ inner products giving, \begin{align} Q(u)&\ge-(n-2)\ge-n+\frac{\pi^2}{6}\ge-n+\frac{\pi^2}{2n}\\ &=-n\left(1-\frac{\pi^2}{2n^2}\right)\ge-n\cos(\pi/n)=L_n \end{align} as required. It only remains to show that the lower bound holds in the case that all $\lambda_k$ are nonzero. As $u_{k+1}=\lambda_ku_k-u_{k-1}$, $u_{k+1}$ is in the subspace spanned by $u_{k-1},u_k$. By induction then, all the $u_k$ lie in the subspace spanned by $u_1,u_2$. This reduces us to the case where ${\rm dim}(E)=2$. For notational convenience, we can take $E$ to be the complex plane with inner product $\langle u,v\rangle=\Re[\bar uv]$. For any $k$, if we set $\omega_k=u_k/u_{k-1}$, then $\omega_{k+1}\omega_k+1=\lambda_k\omega_k$. In particular, $\omega_{k+1}+\bar\omega_k=\lambda_k$ is real and nonzero, giving $\omega_{k+1}=\omega_k$. Therefore, $\omega_k=\omega_1$ for all $k$ and we have $u_k=\omega^ku_0$ for fixed unit vectors $u_0,\omega$. Enforcing $u_{n+1}=u_1$ gives $\omega^n=1$, from which we see that the minimum of $Q$ is obtained at $u_k=u_0\exp(2\pi ikm/n)$ for fixed integer $m$. This gives $$Q(u)=\sum_{k=1}^n\Re[\bar u_k u_{k+1}]=\sum_{k=1}^n\cos(2\pi m/n)=n\cos(2\pi m/n).$$ For $n$ odd, this has minimum $-n\cos(\pi/n)=L_n$ at $m=(n-1)/2$.

Upper bound:

This is where things get tricky. Small values of $n$ require special treatment, and large values require some non-trivial geometry on the sphere.

Case I ($n\le6$): I'll make use of the cunning method used by poster JLT here which, for $n=5,6$, turns around the lower bounds above to obtain upper bounds on $Q(u)$. Just to unify the approach, I include cases $n=2,3,4$ using the same method (although, in those cases, the lower bounds are not needed). The method outlined below can also be applied for $n\ge7$ although, then, the upper bounds are no longer optimal. As $\sum_ku_k=0$, we can expand out \begin{align} 0=\left\lVert\sum_ku_k\right\rVert^2=n+\sum_{j\not=k}\langle u_j,u_k\rangle.&&{\rm(1)} \end{align} For $n=2$, this gives $0=2+Q(u)$, so that $Q(u)=-2=U_2$. For $n=3$ it gives $0=3+2Q(u)$, so that $Q(u)=-3/2=U_3$. For $n=4$, it gives $$0=4+\sum_{k=1}^4\langle u_k,u_{k+2}\rangle+2Q(u)\ge2Q(u).$$ So, $Q(u)\le0=U_4$. Note that alternatively, as pointed out by Peter Košinár in the comments below, we can write $Q(u)=-\lVert u_1+u_3\rVert^2\le0$.

For $n=5$, (1) gives \begin{align} 0&=5+2Q(u)+2\sum_{k=1}^5\langle u_k,u_{k+2}\rangle\\ &=5+2Q(u)+2\sum_{k=1}^5\langle u_{2k},u_{2(k+1)}\rangle\\ &\ge5+2Q(u)+2L_5. \end{align} Here, I have plugged in the lower bounds proven above so, with $L_5=-5\cos(\pi/5)$, $$Q(u)\le5\left(\cos(\pi/5)-1/2\right)=5\cos(2\pi/5)=U_5.$$

For $n=6$, (1) gives \begin{align} 0&=6+2Q(u)+\sum_{k=1}^6\langle u_k,u_{k+3}\rangle+2\sum_{k=1}^6\langle u_k,u_{k+2}\rangle\\ &\ge6+2Q(u)+(-6)+2\sum_{k=1}^3\langle u_{2k},u_{2(k+1)}\rangle+2\sum_{k=1}^3\langle u_{1+2k},u_{1+2(k+1)}\rangle\\ &\ge 2Q(u)+2L_3+2L_3. \end{align} The first inequality here uses $\langle u_k,u_{k+3}\rangle\ge-1$ and the second uses the lower bound proven above. Putting in $L_3=-3\cos(\pi/3)$ gives $Q(u)\le U_6$.

Case II ($n\ge7$): I'll treat large values of $n$ using a completely different approach from that used above for small $n$, and rely on the following intuitive result concerning curves on the unit sphere.

Lemma 1: Let $\gamma$ be a closed curve on the unit sphere in $E$ whose convex hull contains the origin. Then, $\gamma$ has length at least $2\pi$.

For ${\rm dim}(E)=3$, this follows from the Crofton formula, since almost every geodesic on the unit 2-sphere must intersect $\gamma$ at least twice. Alternatively, a proof is given here for curves on the 2-sphere (Lemma 2.14), and the proof generalizes directly to arbitrary dimensions.

Now, let $d(u_k,u_{k+1})$ be the distance between points $u_k,u_{k+1}$ along the unit sphere (equivalently, the angle between $u_k,u_{k+1}$), so $\langle u_k,u_{k+1}\rangle=\cos(d(u_k,u_{k+1}))$. The condition that $\sum_ku_k=0$ means that Lemma 1 applies and we have $$\sum_{k=1}^nd(u_k,u_{k+1})\ge2\pi.$$ For $n\ge7$, this implies that $$Q(u)=\sum_{k=1}^n\cos(d(u_k,u_{k+1}))\le n\cos(2\pi/n)=U_n.$$ I'll prove that this inequality follows in a lemma.

Lemma 2: For $n\ge7$, let $\theta_1,\ldots,\theta_n\in[0,\pi]$ be such that $\sum_{k=1}^n\theta_k\ge2\pi$. Then, $\sum_k\cos\theta_k\le n\cos(2\pi/n)$, with the inequality strict unless all $\theta_k$ equal $2\pi/n$.

Proof: Choose $\theta_k\in[0,\pi]$ to maximise $\varphi(\theta)=\sum_k\cos\theta_k$ subject to the constraint $\sum_k\theta_k\ge2\pi$. As $\cos$ is strictly decreasing, we have $\sum_k\theta_k=2\pi$. This implies that at least $n-4$ of the $\theta_k$ are strictly less than $\pi/2$.

If there exists $i,j$ with distinct $\theta_i,\theta_j$ in $[0,\pi/2]$ then, strict concavity of $\cos$ on this range gives $$\cos\left((\theta_i+\theta_j)/2\right)+ \cos\left((\theta_i+\theta_j)/2\right) > \cos\theta_i+\cos\theta_j.$$ So, all $\theta_k$ in $[0,\pi/2]$ are equal. This shows that there is an $\alpha\in[0,\pi]$ such that $\theta_k$ all lie in the set $\{\alpha\}\cup(\pi/2,\pi]$. Now, suppose that $\theta_k\in(\pi/2,\pi)$ for some $k$. Choose distinct $i,j$ with $\theta_i=\theta_j=\alpha$, \begin{align} \cos(\theta_i+\epsilon)+\cos(\theta_j+\epsilon)+\cos(\theta_k-2\epsilon)=&\cos\theta_i+\cos\theta_j+\cos\theta_k\\ &+2(\sin\theta_k-\sin\alpha)\epsilon\\ &-(\cos\alpha+2\cos\theta_k)\epsilon^2+O(\epsilon^3)&&{\rm(2)} \end{align} As we are at an local maxima of $\varphi(\theta)$, this implies that $\sin\theta-\sin\alpha=0$ and $\cos\alpha+2\sin\theta_k\ge0$. However, the first equality gives $\theta_k=\pi-\alpha$, then $\cos\alpha+2\cos\theta_k=-\cos\alpha$ is strictly negative. This gives a contradiction, so all $\theta_k$ lie in the set $\{\alpha,\pi\}$. Furthermore, if $\alpha=0$ and $\theta_k=\pi$ then the right hand side of (2) is $1+\epsilon^2+O(\epsilon^3)$, again contradicting the condition that $\varphi(\theta)$ is at a local maxima. This means that no more than one of the $\theta_k$ can equal $\pi$. Otherwise, as they sum to $2\pi$, we would have to have $\alpha=0$.

So, the following are the only local maxima of $\varphi(\theta)$.

1. None of the $\theta_k$ equal $\pi$. Then, they all equal $\alpha$. So, $n\alpha=2\pi$. So, $theta_1=\cdots=\theta_n=2\pi/2$ and $\varphi(\theta)=n\cos(2\pi/n)$.
2. One $\theta_k$ equals $\pi$ and the rest equal $\alpha$. So, $\alpha=\pi/(n-1)$ and, $$\varphi(\theta)=(n-1)\cos(\pi/(n-1))-1.$$ This is bounded by $n-2$, which is less than $n\cos(2\pi/n)\ge n-2\pi^2/n$ for $n\ge10$, and can be checked directly that it is bounded by $n\cos(2\pi/n)$ for $n=7,8,9$.
• OK, I agree with the lower bound. I'm a little bit ashamed I didn't think of that myself! I mean the idea of dropping the sum condition, which amounts to saying that $a=0$ in my computations. You present things a bit differently but I think we are basically doing the same thing. Then you "finish the job" nicely. Well done. I'm waiting for the upper bound now, since it appears this is the hard part. – Seub Dec 4 '13 at 1:10
• (continued) - If I understand correctly, the argument is much simpler (and works for all $n$) if we knew that the inner products are positive for a maximum. (just use cos instead of $f$). I don't know how to prove it but it seems obvious that this is true (in particular, the bound should be correct for all $n$). - It would be nice to also conclude that the vectors are coplanar for a maximum. It is enough to say that if the spherical perimeter of the polygon is $2\pi$, it has to be contained in an equator. This also seems obvious, is there a simple argument? – Seub Dec 4 '13 at 1:54
• Yes, this proves that they lie on a line of length $2\pi$. A curve which is not on a perimeter can be shortened by replacing an arbitrarily short segment of it by a geodesic. By the fact mentioned, it will lie (not strictly) in a hemisphere. You can conclude that none of the points can be strictly inside the hemisphere, otherwise they wouldn't sum to 0. So, the maximum is obtained only by coplanar points. Also, for $n=4$ the value of $U_n$ is zero, so the inner products are not strictly positive. – George Lowther Dec 4 '13 at 1:59
• Well, I agree that for $n=4$ they are not strictly positive. Let me say that it seems inuitively true that all the inner products should be equal for a maximum "by symmetry". – Seub Dec 4 '13 at 2:07
• The upper bound for $n=4$ should be trivial: $\langle u_1, u_2\rangle + \langle u_2, u_3\rangle + \langle u_3, u_4\rangle + \langle u_4, u_1\rangle = \langle u_1+u_3, u_2+u_4\rangle = \langle u_1+u_3, -(u_1+u_3)\rangle = -||u_1+u_3||^2 \leq 0$. Since the value of zero is attained by the standard configuration, it's the actual upper bound of the sum. – Peter Košinár Dec 4 '13 at 21:53

A partial result: the maximum is $n - \Theta(\frac1n)$ as $n\to\infty$.

First, if the $u_i$ are evenly distributed around a unit circle (in a 2-dimensional subspace of $E$), in the natural order, then $$\sum_{i=1}^n \langle u_i,u_{i+1}\rangle = n\cos\Big(\frac{2\pi}{n}\Big) \sim n - \frac{2\pi^2}{n}$$

On the other hand, for any choice of the $u_i$, $$\sum_{i=1}^n \langle u_i,u_{i+1}\rangle = n - \frac12 \sum_{i=1}^n \|u_{i+1}-u_i\|^2 \le n - \frac1{2n} \Big(\sum_{i=1}^n \|u_{i+1}-u_i\|\Big)^2$$ by Cauchy-Schwarz. The sum at the far right is the length of the round trip starting at $u_1$, visiting each of the $u_i$ in turn, then coming back to $u_1$. Since $\sum_{i=1}^n u_i = 0$, at least one of the $u_i$ is in the hemisphere opposite $u_1$ (that is, $H = \{x\in S^{d-1}\colon \langle x,u_1\rangle \le 0\}$), so the round trip must at least go to that hemisphere and come back; thus $\sum_{i=1}^n \|u_{i+1}-u_i\| \ge 2\,\text{dist}(u_1,H) = 2\sqrt2$, yielding $$\sum_{i=1}^n \langle u_i,u_{i+1}\rangle \le n - \frac4n$$

This is an incomplete physics motivated answer. We will show that the sum of inner products with the given constraints is equivalent to the energy of an $n$ element chain of point masses confined to a spherical surface, connected by springs. Its minimum and maximum is the physical equilibrium configuration, where the objects form a symmetric equilateral polygon.

Define the norm on the vector space in the usual way $|u|=\sqrt{\langle u, u \rangle }$. Let us label $$F = \langle u_1, u_2 \rangle + \langle u_2, u_3 \rangle + \dots + \langle u_{n-1}, u_n \rangle + \langle u_n, u_1 \rangle$$ We may realize that this is closely related to the potential energy of a chain of point masses placed on a unit sphere at $u_i$ connected by springs: $$V = \frac{1}{2}k|u_1-u_2|^2 + \frac{1}{2}k|u_2 - u_3|^2 + \dots + \frac{1}{2}k|u_n - u_1 |^2 - \sum_{i=1}^{n} \lambda_i (|u_i|^2-1) - \mu \left\langle\sum_{i=1}^{n} u_i, \epsilon\right\rangle \\ =- k F + \sum_{i=1}^n \left[(k - \lambda_i) |u_i|^2 + \lambda_i \right] - \mu \left\langle\sum_{i=1}^{n} u_i,\epsilon\right\rangle,$$ The first $n$ terms in the first equation represent the energy of the spring with spring constant $k$. The springs are attractive if $k>0$ and repulsive if $k<0$. Each term in the latter two sums vanishes when the point masses are confined to a unit sphere and when their sum is zero for arbitrary $\epsilon$ vector. These terms are introduced in Lagrangian mechanics to represent the constraint forces, where $\lambda_i$ are Lagrange multipliers. Finding the minimum/maximum of F for $|u_i|=1$ and $\sum_k u_k = 0$ is equivalent to finding the minimum of the potential energy $V$ for a spring constant $k=-1$ or $1$, respectively.

In physics, a system of objects is in static equilibrium if the potential energy is at a local minimum. The force on object $i$ is $$f_i = -\partial V / \partial u_i^* = -k(u_i - u_{i+1}) - k(u_i - u_{i-1}) + 2\lambda_i u_i + 2\mu \epsilon \\= -k(u_i - u_{i+1}) - k(u_i - u_{i-1}) + 2\lambda_i u_i -2\sum_i\lambda_i u_i.$$ (Here $^*$ denotes the dual. We identify the index $i=0$ with $n$ and $n+1$ with $i=1$.) In the top line, the first two terms represent the forces arising from the two springs attached to the object and the last two terms are the constraint forces which ensures that the objects stay on the unit sphere and that their sum is zero. In the second line we have substituted the value of $\epsilon$ after solving the equations by summing $\sum_i f_i = 0$, and using the constraint $\sum_k u_k =0$.

In equilibrium, the net force $f_i$ is zero for each $i$. If either mass is displaced, the energy of the system increases.

I am stuck at the same stage as the OP, since the latter sum may not be zero. The following arguments are valid only in the case they are zero, which turns out to be the case for even $n$.

$f_i=0$ for each $i$ implies that the three objects $u_{i-1}$, $u_{i}$, and $u_{i+1}$ are linearly dependent for each $i$. In other words, $u_{i-1}$, $u_{i}$, and $u_{i+1}$ lie in a 2D plane. Furthermore, $f_i=0$ implies that $u_i$ is parallel to $u_{i-1}+u_{i+1}$. The system in equilibrium is confined to 2 dimensions, all $u_i$ lie on an equator of the $n$-sphere, where each $u_i$ is precisely halfway between $u_{i-1}$ and $u_{i+1}$. The points span an equilateral 2D polygon. (We consider only the case where the vector space is at least 2D, otherwise the solution is trivial.) We may identify the position of each object by $$u_i = (\cos\phi_i)e_1 +(\sin\phi_i) e_2$$ where $e_1$ and $e_2$ are arbitrary orthogonal unit vectors. Thus, local equilibrium requires $$\phi_i = i \phi_1 = 2 R \pi i/n.$$ Here $R$ must be an integer to ensure $f_n=0$ and $f_1=0$. Most generally $R\in\{1,2\dots n-1\}$. Note that $R=0$ is ruled out by the constraint given in the problem that $\sum_i u_i =0$ and $R\geq n$ and $R < 0$ are equivalent to $R {\;\rm mod\;} n$.

These $n$ possible solutions comprise all the local extrema of $F$ for the given constraints. Comparing their values one can immediately see that the global maximum/minimum $F$ corresponds to $R=1$ and $[n/2]$, respectively, where $[n/2]$ denotes the integer closest to $n/2$. Thus $$F_{\max}=n \cos\frac{2\pi}{n}\quad{\rm and}\quad F_{\min}=n \cos\frac{2[n/2]\pi}{n}.$$

• This is interesting but imho you make claims that need proof. Mainly: "For a fixed R, it can be shown that the sum S can be continuously decreased by infinitesimal transformations of ui unless the points are confined to a single 2D circle in the vector space. (This is similar to showing that the equator is the shortest path on a sphere between two points, or ...)". I don't think it's easy to show as you say, I have written down the infinitesimal deformation of S etc (see question). – Seub Dec 3 '13 at 11:02
• Your input is interesting and valuable, don't get me wrong. It's just that as far as I'm concerned, it does not answer the question, which asks for an actual proof. – Seub Dec 3 '13 at 17:29
• @Seub I agree with you, and clarified the answer. I believe this is now a completely rigorous proof. – bkocsis Dec 3 '13 at 17:55
• I don't see how this works. There is a local equilibrium at $u_1=\cdots=u_n$ (for which $\sum_iu_i\not=0$). How can you be sure that it doesn't fall into that state? – George Lowther Dec 3 '13 at 21:51
• I think the argument should proceed in a slightly different order: analyze the consequences of $F_i=0$ to get that the $u_i$ lie in a plane with equal angles between them, then use the centroid condition to show that the angle isn't zero. This would address @GeorgeLowther's concern, I think; it also avoids having to figure out it means to "wrap around" the origin R times when we're not in the plane. (E.g., if you visit the vertices of a regular tetrahedron in the natural way, how many times have you wrapped around the origin?) – user21467 Dec 3 '13 at 22:22