Maximum number of unit vectors with bounded pairwise dot products

363 Views Asked by At

Let $n\in\mathbb{Z}^+$ and $t\in(0,\tfrac{1}{2})$. Upper bound $m$ such that there exist $v_1,...,v_m\in\mathbb{R}^n$ with $\|v_i\|=1$ and $|v_i\cdot v_j|\le t$ for all $i\neq j$.

If $t=0$, $v_i\cdot v_j=0$, so $v_1,...,v_m$ are linearly independent, so $m\le n$. This is tight using the standard basis. I came up with nothing for $t>0$. I suppose you could bound the distance between $v_i$ and $v_j$, but I don't see how that's useful.

1

There are 1 best solutions below

0
On

Here is a crude approach:

(1) $|v_i-v_j|=\sqrt{2-2v_i\cdot v_j}\geq \sqrt{2-2t}$.

(2) The balls $B_{i}:=\{x\in \mathbb{R}^{n}: |x-v_i|< \frac{1}{2}\sqrt{2-2t}\}$, $1\leq i\leq m$ are disjoint subsets of $B_0:=\{x\in\mathbb{R}^n: |x|< 1+\frac{1}{2}\sqrt{2-2t}\}$, hence $\sum_{i=1}^{m}|B_i|\leq |B_0|$

(3) Since the volume of balls in $\mathbb{R}^n$ scales like $r^n$, you may deduce that $$ m(\frac{1}{2}\sqrt{2-2t})^n\leq (1+\frac{1}{2}\sqrt{2-2t})^n $$

or

$$ m\leq \left(\frac{1+\frac{1}{2}\sqrt{2-2t}}{\frac{1}{2}\sqrt{2-2t}}\right)^n $$

As shown by the Johnson--Lindenstrauss lemma, any upper bound must grow at least exponentially with respect to $n$ for fixed $t>0$. An obvious flaw of the bound is that it doesn't recover (not even remotely so) the bound $m\leq n$ for $t=0$. For $t\to 1$ it becomes vacuous ($m\leq \infty$), as it should.