Suppose $\theta$ and $d$ are given.

How big can a set of $d$-dimensional vectors be such that no pair of them are at angle less than theta?

I particularly want an upper bound; that is, an $n=n(\theta,d)$ such that given $n$ $d$-dimensional vectors, there must be at least $2$ with angle less than theta between them.

Of course, the question can be rewritten in all sorts of ways, for example, coverings of the surface of the d-dimensional sphere by $(d-1)$-dimensional caps of given radius etc.

The bound doesn't need to be tight. Something out by a factor of $(constant)^d$ might be fine (although something more exact would be interesting too).

  • $\begingroup$ I guess you know the argument for the easy case $\theta = \pi/2$? Or should I post it anyway in an answer? $\endgroup$ – Andrea Ferretti Mar 2 '10 at 17:24
  • $\begingroup$ Actually for $\theta = \pi/2$ the sharp bound is d+1. I don't think you can get something esponential for other values of $\theta$. $\endgroup$ – Andrea Ferretti Mar 2 '10 at 17:34
  • $\begingroup$ Do you work with unit vectors? (becasuse for unit vectors a volumetric argument gives something proportional to $\theta^{-d}$ if my calculation is correct) $\endgroup$ – Pandelis Dodos Mar 2 '10 at 17:35
  • $\begingroup$ Thanks Andrea - pi/2 I can do! but smaller values are what I really need. For example fix theta=pi/4 Pandelis - yes please! - unit vectors would certainly be fine (I am just considering the angle between them). $\endgroup$ – Matt Richards Mar 2 '10 at 18:01
  • $\begingroup$ @ Matt: Bill and Anton gave detailed answers and I don't have something to add. What I meant before was essentially what Anton described. $\endgroup$ – Pandelis Dodos Mar 2 '10 at 18:48

The subject name you are looking for is spherical codes. A good reference for this subject is Conway and Sloane's "Sphere Packings, Lattices, and Groups." In chapter 9 they give the details of the proof for the best bounds (I believe it is due to Levenstein, but don't have the book with me).

This ends up being related to density of sphere packings. There's a very elegant proof in the book which relates the answer to your question in dimension $n+1$ to the maximal density of sphere packing in dimension $n.$

Sorry I don't have my references with me, but this is all in chapter 9 of the book.

| cite | improve this answer | |

One way of obtaining a lower bound is to apply the Johnson-Lindenstrauss lemma to an orthonormal basis. This gives exponentially many vectors such that the angles between all pairs are arbitrarily close to $\pi/2$.


| cite | improve this answer | |

This is a standard construction based on the fact that maximal $\theta$-packing is also an $\theta$-net.

Fix $d$. Given $\theta>0$, consider $\theta$-packing of $S^d$; i.e. a set of $n=n(\theta)$ points $x_1,x_2,\dots,x_n$ in $S^d$ such that $|x_ix_j|>\theta$ (we measure intrinsic distances in the sphere). Note that

  • $B(\tfrac\theta2,x_i)\cap B(\tfrac\theta2,x_i)=\varnothing$ for $i\not=j$ and

  • $\bigcup\limits_i B(\theta,x_i)=S^d$ (i.e. $\{x_1,x_2,\dots,x_n\}$ form a $\theta$-net in $S^d$)

Set $v(r)=\mathop{\rm vol}\{B(r,x)\subset S^d\}$. Then $$n \cdot v(\tfrac\theta2) < \mathop{\rm vol}S^d < n\cdot v(\theta).$$ Clearly $1\le \tfrac{v(\theta)}{v(\theta/2)}\le 2^d$. Thus, $\mathop{\rm vol}S^d/v(\theta)$ gives $n$ up to factor $2^d$.

| cite | improve this answer | |
  • 1
    $\begingroup$ P.S. Set $m=\mathop{\rm vol} S^d/v(\theta)$. Then $m/n$ should conerge (as $\theta\to0$) to the density of the densest packings in dimension $d$. $\endgroup$ – Anton Petrunin Mar 2 '10 at 18:46
  • $\begingroup$ Thanks Anton! This is the sort of thing I had in mind when mentioning covering the d-sphere by spherical caps. But to apply it, how best to get a handle on how your v(theta) behaves as a function of d (with theta fixed, say)? $\endgroup$ – Matt Richards Mar 3 '10 at 12:23
  • $\begingroup$ @Matt. $\mathrm{vol} S^d/v(\theta)=\int_0^\pi\sin^{d-1}tdt/\int_0^\theta\sin^{d-1}tdt\approx \sqrt{\tfrac{2\pi}{n}}/\int_0^\theta\sin^{d-1}tdt$. $\endgroup$ – Anton Petrunin Mar 3 '10 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.