8
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ I guess you know the argument for the easy case $\theta = \pi/2$? Or should I post it anyway in an answer? $\endgroup$ Mar 2, 2010 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$ Mar 2, 2010 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$ Mar 2, 2010 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$ Mar 2, 2010 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$ Mar 2, 2010 at 18:48

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
0
6
$\begingroup$

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

http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
  • 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$ Mar 2, 2010 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$ Mar 3, 2010 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$ Mar 3, 2010 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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