Almost orthogonal vectors

Question

This is to do with high dimensional geometry, which I'm always useless with. Suppose we 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 https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma or Google "Johnson-Lindenstrauss lemma".

Answer 2

The following has always been one of my favourite facts in extremal combinatorics.

• If you want to pick unit vectors in $\mathbb 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 largest 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 3

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 4

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 5

At least in the real case the buzzword is "spherical codes".
https://mathworld.wolfram.com/SphericalCode.html
http://neilsloane.com/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.

Answer 6

This was too long to be a comment, my apologies:

Further to Tim Gowers' comment and the following discussion, Chapter 6 of Bollobas' lovely white book "Combinatorics - set systems hypergraphs, families of vectors, and combinatorial probability" studies exactly this kind of question,.

In fact Tim's comment corresponds to Theorem 6 in that chapter of the book, I believe. The language of that theorem uses symmetric difference of subsets of $\{1,2,..,n\}$, which can be converted to inner products of normalized $n$ dimensional vectors with entries $\pm 1/\sqrt{n}$.

Let $\epsilon>0$ be small. The second case of Theorem 6 essentially states that if the normalized inner product is allowed to be in $[-1,\epsilon]$, equivalently, if the pairwise symmetric differences of the sets in the family are all slightly less than $n/2$ in relative terms, then the number of sets in the family, and hence the number of vectors with entries $\pm 1/\sqrt{n}$ can be as large as $2^{\epsilon n}.$

The proof of this part of the Theorem is given as an exercise with a nice hint in the book: Focus on subsets of size $k=\lceil n/2 \rceil$ and do sphere packing in the Hamming space.

The variation with the OPs question is that the allowed range for the normalized inner product is $[-\epsilon, +\epsilon]$ in the OPs question. From Jelani Nelson's answer, it seems that the penalty for restricting the inner product to a band is perhaps not as severe as one might expect. We go from $\epsilon n$ down to $\epsilon^2 \log(1/\epsilon)n$ in the exponent.