Sphere packing problem

[Dragonfall]

How many n-dimensional unit vectors from $\mathbb{C}^n$ can you pack in a set such that for any two vectors, $\left<a, b\right>\leq\delta$ for some delta between 0 and 1?
(<a,b> denotes the inner product).

This reduces to packing of n-2 dimensional spheres on a n-1 dimensional sphere, if that helps.

EDIT: on second thought I'm not sure if this reduces to a sphere packing problem.

 

[Dragonfall]

Anyone?

 

[quadraphonics]

Without specifying what the set is, it's hard to comment. Also, I've only ever seen sphere packing conisdered for real numbers; not sure how the extension to complex would play out...

 

[Dragonfall]

The max size of the set depends only on $\delta$, which determins how close two vectors from the set can be. $\delta =0$ then the max size is the dimension; $\delta =1$ then it's infinite.

EDIT: I made a typo in my first post. The requirement is that

$$\left|\left< a,b\right>\right| \leq\delta$$. Note the modulus operator.

 

[Dragonfall]

Anyone?

 

[maze]

Supposing we restrict it to R^3 and are interested in the limiting case where delta -> 1. Obviously this is not your full problem, but at least I can say something about it, whereas the full out problem seems pretty hard. What I say can be generalized to R^n as well.

Suppose you are adding unit vectors one by one, trying to keep their tips spaced as far apart as possible on the unit sphere (or equivalently, trying to keep their angles as big as possible for a given number of vectors). For 2 vectors, you would place them at antipodes (opposite points on the sphere), 180 degrees. For 3 vectors, 120 degrees in the plane. 4 vectors, tetrahedron (~109 degrees). 5 vectors, a more complicated shape, 12 vectors, the points on a dodecahedron, etc etc.

For small numbers of vectors, adding each additional vector causes massive changes in the configuration of all previous vectors, and the angle jumps drastically (180 -> 120 -> 109 ..). However, when there are already a ton of vectors on there, say, 100, then the ball looks like a prickly sea urchin, and if you add one more vector, then the other vectors on there can accommodate it by all shifting very slightly. Everything from now on is assuming a large number of vectors.

Thus for large numbers of vectors, the the surface area of the unit sphere is uniformly sprinkled by the different vector tips. Further, if the vector tips are used to triangulate the surface of the sphere (Delaunay triangulization would work nicely), then as the number of vectors becomes large the triangles will become approximately equilateral.

You can use the Euler characteristic to find that the number of triangular faces is f=2(v-2) where v is the number of vectors. (v-e+f=2, and e=3f/2 since each face has 3 edges, which would double count each edge)

Since the triangles take up roughly equal surface area on the sphere, f*A = 4*pi, or A = 4*pi/f where A is the area of a single triangle. Additionally, since the triangle is approximately equilateral, the area is related to the edge length by A = d^2*sqrt(3)/4, or d = sqrt(4A/sqrt(3)).The angle between 2 neighboring vectors is then θ ~= arcsin(d) ~= d for small angles.

Putting this all together,
in the limit as v-> infinity, θ = sqrt(4*(4*pi/2(v-2))/sqrt(3))

You can invert this and find
in the limit as θ -> 0, v = 8*pi/(sqrt(3)*θ^2) + 2

assuming I didn't make any algebra mistakes in there...

your delta, by the way, is cos(θ), as that is the way the inner product relates to angle.

 

[Dragonfall]

If I understood correctly, you gave an approximate answer in the limiting case using a greedy packing algorithm. That's interesting. Do you know whether the greedy algorithm in this case will produce an optimal unit vector packing?

 

[maze]

I think it is optimal. To be rigorous, you would have to prove that: given an optimal packing algorithm, the delaunay triangulization (or any other triangulization) of the configuration will produce triangles that approach equilateral triangles in the limit as θ -> 0.

If there are multiple optimal packing algorithms aside from rotations of the original algorithm (I doubt it), then you only need to prove it for one algorithm.