More than $n$ approximately orthonormal vectors in $R^n$

Question

This question was asked at math.stackexchange, where it got several upvotes but no answers.

---

It is impossible to find $n+1$ mutually orthonormal vectors in $R^n$.

However, it is well established that the central angle between legs of a regular simplex with $n$-dimensional volume goes as $\theta = \mathrm{arccos}(-1/n)$. This approaches $90$ degrees as $n \rightarrow \infty$, so since there are $n+1$ vertices of a simplex with $n$-dimensional volume, we can conclude

Given $\epsilon > 0$, there exists a $n$ such that we can find $n+1~$ approximately mutually orthogonal vectors in $\mathbb{R}^n$, up to tolerance $\epsilon$. (Unit vectors $u$ and $v$ are said to be approximately orthogonal to tolerance $\epsilon$ if their inner product satisfies $\langle u,v \rangle < \epsilon$)

My question is a natural generalization of this - if we can squeeze $n+1$ approximately mutually orthonormal vectors into $\mathbb{R}^n$ for $n$ sufficiently large, how many more vectors can we squeeze in? $n+2$? $n+m$ for any $m$? $2n$? $n^2$? $e^n$?

---

Actually the $n+m$ case is easy to construct from the $n+1$ case. Given $\epsilon$, one finds the $k$ such that you can have $k+1$ $\epsilon$-approximate mutually orthogonal unit vectors in $\mathbb{R}^k$. Call these vectors $v_1, v_2, ..., v_k$. Then you could squeeze $mk+m$ vectors in $\mathbb{R}^{mk}$, by using the vectors $$\begin{bmatrix} v_1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} v_2 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} v_{k+1} \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ v_1 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ v_2 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ v_{k+1} \\ \vdots \\ 0 \end{bmatrix}, \dots \begin{bmatrix} 0 \\ 0 \\ \vdots \\ v_1 \\ \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ \vdots \\ v_2 \\ \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ \vdots \\ v_{k+1} \\ \end{bmatrix}. $$ So, setting $n = mk$, we have found an $n$ such that we can fit $n + m$ $\epsilon$-orthogonal unit vectors in $\mathbb{R}^n$.

I haven't been able to construct anything stronger than $n+m$, but I also haven't been able to show that this is the upper bound.

Answer 1

A set of points on the unit sphere in ${\Bbb R}^n$ with $\langle x,y\rangle \le \cos \theta$ for all distinct $x$ and $y$ is called a spherical code with minimum angle $\theta$. For $0<\theta < \pi/2$, Kabatiansky and Levenshtein gave an exponential upper bound (of the form $\exp(C(\theta)n)$) for the maximum number of points in such a spherical code. There is also an exponential lower bound. This is related to sphere packings. See for example the recent paper by Cohn and Zhao, which will have more references: http://arxiv.org/pdf/1212.5966v2.pdf

Answer 2

From the area estimates you get that that for fixed $\varepsilon>0$ this number, say $M_\varepsilon(n)$, grows quite fast.

Direct calculations show that the total area of the locus of unit vectors in $\mathbb{R}^{n}$ which are not $\varepsilon$-perependicular to the given vector $u$ is about $$2\cdot e^{-(n-2)\cdot\varepsilon^2/2}\cdot\mathop{\rm area}\mathbb{S}^{n-1}.$$

In particular, $$M_\varepsilon(n)>\tfrac12\cdot e^{(n-2)\cdot\varepsilon^2/2}>\tfrac{1}{100}\cdot\lambda^n$$ where $\lambda=e^{\varepsilon^2/2}>1$

Answer 3

Terry Tao has a nice blog post on a 'cheap version' of the Kabatjanskii-Levenstein bound mentioned in Lucia's answer, using the so-called 'tensor product trick'.

Answer 4

This is also related to equiangular tight frames (ETFs). A frame is a kind of "overcomplete basis" of an inner product space; more precisely a family $(f_1,\dots,f_n)$ of vectors of an inner product space $V$ is a frame if there exist constants $A,B>0$ such that for all $f\in V$ it holds that $$A\|f\|^2\leq \sum |\langle f,f_k\rangle|^2\leq B\|f\|^2.$$ The frame is called tight, if $A=B$ and it is called equiangular if there is some $c$ such that for all $k,l$: $|\langle f_k,f_l\rangle|=c$.

"Equiangular tight frame" usually also means that the vector $f_k$ are normalized.

If you have an equiangular tight frame consisting of $n$ vectors in $\mathbb{R}^d$ (or $\mathbb{C}^d$) then it holds that $$|\langle f_k,f_l\rangle| = \sqrt{\frac{n-d}{d(n-1)}}.$$ Note that for $n=d+m$ and also for $n=d^m$ this number always goes to zero for $d\to\infty$ saying that the vectors become asymptotically orthogonal.

The only catch is, that equiangular tight frames do not always exist…

There are several construction, such as the Mecedes-Benz-frame (with $n=d+1$), see here . A pretty recent preprint on the existence of ETFs is "On the existence of equiangular tight frames" by Sustika, Tropp, Dhillon and Heath. In that paper you find the result that "maximal ETFs" (i.e. ones with the largest number of vectors) exist (not in all dimensions) but have the size $N=d(d+1)/2$ in the real case and $N=d^2$ in the complex case.