## 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.