Two posts in french have already appeared on this topic, showing that the maximal number of unit vectors having pairwise negative (resp. non-positive) inner products grow linearly wit the dimension of the space \mathbb{R}^n they live in. This is good fun; however, as mentioned in a comment, it becomes even better fun when one bothers asking, for \epsilon >0 how big a family of unit vectors v_1,\cdots,v_k\in \mathbb{R}^n can be if…

  1. … for all i\neq j, one requires v_i\cdot v_j<\epsilon;
  2. … for all i\neq j, one requires v_i\cdot v_j<-\epsilon;

Let’s deal with the first question. This involves the remarkable fact that on the sphere of very large dimension, almost all the area is concentrated on a small band near the equator (or any equator). This is the phenomenon called concentration of measure ; so pick a vector v_1\in\mathbb{S}^n. To continue your family, you have to pick a vector outside the spherical ball B=\{x\mid x\cdot v_1\geq\epsilon\}. So the concentration of measure implies that the forbidden area is of order C\exp(-cn\epsilon^2). When you have picked already k vectors, the forbidden area for the choice of the next one is at most kC\exp(-cn\epsilon^2) which is strictly less than 1 until k=C^{-1}\exp(cn\epsilon^2). Then not all the sphere is forbidden, so you can accommodate certainly C^{-1}\exp(cn\epsilon^2): exponentially (in the dimension) many instead of linearly.

The second one is easier. Indeed,

0\leq \lVert \sum_{i=1}^k v_i \rVert^2=k+2\sum_{i<j}v_i\cdot v_j\leq k-\epsilon k(k-1)

which implies k\leq \epsilon^{-1}+1 so we get a constant bound, certainly much lower than n+1 for large dimensions.

Publicités