The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$ Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
Clearly, if $n=d$, the minimum is attained by taking $v_i=e_i$. Could it be that for $n>d$ in order to minimize the latter expression it is still best to take the vectors $v_i=e_{i\, \text{mod}\, d}$? 
 A: In addition to fedja's clever argument for the case $d|n$, let me prove this for $d=2$ (and $n$ of arbitrary parity).
We have $|\cos x|\geqslant 1-\frac2\pi x$ for $x\in [0,\pi/2]$ by concavity of cosine. So, it suffices to prove that the sum of angles between lines $\ell_1,\dots,\ell_n$ (which are parallel to vectors $v_1,\dots,v_n$) is maximal when $\lfloor n/2\rfloor$ lines coincide with certain line $a$ and $\lceil n/2\rceil$ other lines also coincide with $b\perp a$. Induct with bases $n=1,2$. Note that if, say, $\ell_n,\ell_{n-1}$ are orthogonal, we have $\angle(\ell_i,\ell_n)+\angle(\ell_i,\ell_{n-1})\geqslant \pi/2$, and summing up these inequalities with induction proposition for $\ell_1,\dots,\ell_{n-2}$ we get the result. If no two lines are orthogonal, we may move any of them to the direction which increases the sum of angles until either two lines become orthogonal or two of them coincide. In this second case move this pair of coinciding line, etc. Finally either all lines coincide, and the sum of angles is too small, or we get a pair of orthogonal lines on some step.
A: In fact, the minimizers of the sum $\sum \langle v_i, v_j \rangle^2$ are precisely tight frames, i.e. sets such that for some $C>0$and for each $x\in \mathbb R^d$, one has $\| x \|^2 = C \sum \langle x, v_j \rangle^2$. This was proved in Benedetto, Fickus "Finite Normalized Tight Frames", Adv. Comp. Math., 18 (2003), pp. 357-385.
Thus for $n$ not a multiple of $d$, the set $v_i = e_{i\mod d}$ is not a minimizer, since it is not a tight frame. 
Although, I believe that for $\ell^1$ the answer may still be correct.
A: It is quite likely. At least, the proof for the case $d\mid n$ is easy. First of all, the restriction $i\ne j$ does not matter: adding $n$ ones changes nothing in the problem. Now notice that $|\langle v_i,v_j\rangle|\ge \langle v_i,v_j\rangle^2=\langle V_i,V_j\rangle$ where $V_i=v_i\otimes v_i$. Now, $\langle V_i,I\rangle=1$ for all $i$ ($I$ is the identity matrix, as usual), so $\langle\sum_i V_i,I\rangle=n$ and, by Cauchy-Schwarz, $\|\sum_i V_i\|^2\ge n^2/\|I\|^2=n^2/d$ (the norm here is the Frobenius norm, i.e., the square root of the sum of the squares of the matrix elements), which results in $\min_{v_i}\sum_{i,j}\langle v_i,v_j\rangle^2\ge n^2/d$. For the conjectured minimizer, both this estimate and the crude inequalities $|\langle v_i,v_j\rangle|\ge \langle v_i,v_j\rangle^2$ become identities, whence the conclusion. 
I do not see off hand how to modify this argument for the case $d\not\mid n$ but it still makes the conjecture quite plausible. In the worst case scenario, you are off by at most $d/4$ from the true minimum with your system. 
