Skip to main content
2 of 3
reformatted, including change $\theta/2$ to $\theta$ for easier readability
user avatar
user avatar

Having scalar product above $\rho$ is equivalent to having spherical distance above $2\theta$, where $\theta=\arccos(\rho)/2$. Suppose that you have points $x_1,\ldots,x_N$ on the surface of the $(d-1)$-sphere, at spherical distance at least $2\theta$ from each other.

Then there are disjoint open cones $C_i$ in the unit $d$-sphere, where $C_i$ is the interior of the convex hull of:

  • the vertex $0$
  • the points $y$ on the $(d-1)$-sphere with $\langle x_i,y\rangle=\cos(\theta)$

The cones $C_i$ and $C_j$ are disjoint whenever $i \neq j$, because points in $C_i$ have angles with $x_i$ of less than $\theta$, and points in $C_j$ have angles with $x_j$ or less than $\theta$, but the angle between $x_i$ and $x_j$ is $2\theta$.

This means that $N\cdot|C_1|_d\leq |\mathbb B^d|_d$, where $|\cdot|_d$ denotes the Lebesgue volume in dimension $d$ and $\mathbb B^d$ is the unit ball in $\mathbb R^d$. But the volume of the cone is $$|C_1|_d=\frac1d|\mathbb B^{d-1}|_{d-1}\cdot\cos(\theta)^{d-1}\cdot\sin(\theta).$$ and therefore $$N \le \frac{|\mathbb B^d|_d}{|\mathbb B^{d-1}|_{d-1}}\cdot\frac{d}{\sin(\theta)}\cdot\cos(\theta)^{1-d}.$$ Since the first ratio goes to zero (I think as $1/\sqrt d$, up to constant), $N$ has to be asymptotically less than $\lambda^d$ for all $\lambda>1/\cos(\theta)$.

Pierre PC
  • 3.7k
  • 10
  • 24