Mutual сoherence II

Arthur Gilmullin, a friend of mine, recently came up with another solution of the mutual coherence problem. It also works for $n > 2$  (where $n$  is the space dimension). The reformulation of the bound is also due to him.

Here is the general problem: we have $p$ distinct vectors $a_1,\, ...,\, a_p$  on the $n$-dimensional unit sphere and are interested in proving that for any such configuration there is a pair $(a_i, a_j),$ $i \ne j,$  such that $|\cos (a_i, a_j)| \ge A_{n,p}$  where $A_{n,p}$  is some predefined number. As I wrote, for $n = 2$  it holds $\displaystyle A_{2, p} = \left|\cos \frac{\pi}{p}\right|.$

Let us now prove that $\displaystyle A_{n, p} = \left|\cos \frac{\pi(n-1)}{\lfloor p^{1/(n-1)} \rfloor }\right|.$

To describe the position of a vector on a unit sphere on $\mathbb{R}^n$  we need $n-1$  angles $\varphi_1,\, ...,\, \varphi_{n-1}.$  Divide the range $[0, 2\pi]$  of possible values of $\varphi_1$  to $k$  equal (subsequent) half-intervals. Due to Dirichlet’s principle, there is at least one of them containing $\lceil \frac{p}{k} \rceil$ vectors. For these vectors the same argument works with $\varphi_2,$  etc. Finally, we have $\ge \frac{p}{k^{n-1}}$ vectors for which each angular coordinate differ not more than by $2\pi/k.$  Now choose $k$ such that $|\cos 2\pi/k|$  is as big as possible but still providing $\frac{p}{k^{n-1}} \ge 1,$ so that Dirichlet principle still works. That is, $k = \lfloor p^{1/(n-1)} \rfloor.$  So there is a pair of vectors with all angles $\varphi_i$ differing not more than by $\pi/\lfloor p^{1/(n-1)}\rfloor.$  Finally, apply spherical triangle inequality concluding that there must be 2 points with angular distance not more than $\pi(n-1)/\lfloor p^{1/(n-1)} \rfloor.$  Note also that for any $\varphi_i$  we can actually identify the opposite intervals, since the corresponding change of $\varphi_i$  in one term doesn’t affect the absolute value of the dot product. 