Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I guess you know the argument for the easy case $\theta = \pi/2$? Or should I post it anyway in an answer? –  Andrea Ferretti Mar 2 '10 at 17:24
    
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$. –  Andrea Ferretti Mar 2 '10 at 17:34
    
Do you work with unit vectors? (becasuse for unit vectors a volumetric argument gives something proportional to $\theta^{-d}$ if my calculation is correct) –  Pandelis Dodos Mar 2 '10 at 17:35
    
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). –  Matt Richards Mar 2 '10 at 18:01
    
@ Matt: Bill and Anton gave detailed answers and I don't have something to add. What I meant before was essentially what Anton described. –  Pandelis Dodos Mar 2 '10 at 18:48

3 Answers 3

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.

share|improve this answer
    
Thanks Ben! - I will get to the library... –  Matt Richards Mar 3 '10 at 12:23

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

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

share|improve this answer
1  
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$. –  Anton Petrunin Mar 2 '10 at 18:46
    
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)? –  Matt Richards Mar 3 '10 at 12:23
    
@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$. –  Anton Petrunin Mar 3 '10 at 17:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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