This question was [asked at math.stackexchange](https://math.stackexchange.com/questions/651260/more-approximately-orthogonal-vectors-than-the-dimension-of-the-space), 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.



More than $n$ approximately orthonormal vectors in $R^n$
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>


