Question

This is to do with high dimensional geometry, which I'm always useless with. Suppose with have some large integer n and some small $\epsilon>0$. Working in the unit sphere of $\mathbb R^n$ or $\mathbb C^n$, I want to pick a large family of vectors $(u_i)_{i=1}^k$ which is almost orthogonal, in the sense that $|(u_i|u_j)| < \epsilon$ when $i\not=j$. I guess I'm interested in how the biggest choice of $k$ grows with $n$ and $\epsilon$.

For example, we can let ${u_1,\cdots,u_n}$ be the usual basis, and then choose $u_{n+1} = (1,1,\cdots,1)/n^{1/2}$, which works if $n^{-1/2} < \epsilon$. Then you can let $u_{n+2} = (1,\cdots,1,-1,\cdots,-1)/n^{1/2}$ and so forth, but it's not clear to me how far you can go.

Answer 1

Matt, to get $k$ points, you only need $n\ge C \epsilon^{-2} \log k$. See http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma or Google "Johnson-Lindenstrauss lemma".

Answer 2

The Johnson-Lindenstrauss lemma states that you can have $k = 2^{\Omega(\epsilon^2 n)}$. It's also known that you cannot have $k$ larger than $2^{O(\epsilon^2 \log(1/\epsilon) n)}$ so that the Johnson-Lindenstrauss lemma gives you a near-tight answer. See the last section of "Problems and results in Extremal Combinatorics Part I" by Noga Alon for a proof of this latter fact.

Answer 3

The following has always been one of my favourite facts in extremal combinatorics. If you want to pick unit vectors in R^n such that the inner product between any two of them is at most 0, then the best you can do is choose 2n vectors (an orthonormal basis and minus that basis). If you relax the condition to "at most epsilon" then you can get exponentially many by a volume argument or probabilistic methods, as other people have remarked. And if you go in the other direction, insisting that the inner product is at most -epsilon, then the biggest number of vectors you can choose is bounded above independently of n -- it's of order 1/epsilon. To prove that last fact, you calculate the norm of the sum of the vectors in two different ways -- a nice exercise I won't do here. I don't know how much is known if you impose the condition that no inner product is more than epsilon(n) for some function that tends to zero from above. It's not clear that the simple probabilistic argument gives the right result in this regime. But in general I very much like the way the function has three such different behaviours.

Answer 4

Indeed, what Bill Johnson wrote can hold even for points all of whose coordinates are $\pm 1/\sqrt{n}$. First choose $k = \exp(\epsilon^2 n/4)$ vectors $v_1, \dots, v_k$ by choosing each coordinate to be $\pm 1$ with probability $1/2$ each. Then define $u_i = v_i/\sqrt{n}$. A Chernoff bound shows that the probability of $|\langle u_i, u_j \rangle| \geq \epsilon$ is at most $2 \exp(-(\epsilon^2/2)n)$. This equals $2/k^2$ by choice of $k$, and hence one can take a Union Bound over the at most $\binom{k}{2} < k^2/2$ pairs $(i,j)$ to show that there's a positive probability of $|\langle u_i, u_j \rangle| < \epsilon$ holding for all $i \neq j$.

PS: Perhaps I got the constants wrong, but they can always be adjusted to make things work out.

Answer 5

At least in the real case the buzzword is "spherical codes". http://mathworld.wolfram.com/SphericalCode.html http://www2.research.att.com/~njas/packings/

The idea is to find as large as possible a set on an $n$-sphere whose distances are at least a given amount apart. It's a spherical geometry analogue of the dense sphere-packing problem and generalizes the kissing number problem for spheres.

As with these classical problems, lots of partial results are known but rather fewer are proved to be optimal.