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 :)
 A: 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
$$
A: 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}.$$
