Given the vector space $\mathbb{R}^n$, endowed with the standard inner (dot) product $\langle\cdot,\cdot\rangle:\mathbb{R}^n\times \mathbb{R}^n\to\mathbb{R}$, the problem of **almost-orthogonal sets** asks, for each $\epsilon> 0$, for the construction (or at the very least, bounds on the cardinality) of a **maximal** subset $S$ of $U\_n$, the set of unit vectors of $\mathbb{R}^n$, such that


$\forall x,y\in S: x\ne y\implies |\langle x,y\rangle|\le\epsilon$.


For known results, see Matt Cheung's Major Qualifying Project monograph at this [link](http://users.wpi.edu/~martin/MQP/mcheung.pdf).


**Question**: What are known results, if we restrict ourselves to some subset of $U\_n$? Specifically, I am interested in the subset $\lbrace\frac{1}{\sqrt{n}},-\frac{1}{\sqrt{n}}\rbrace^n$ consisting of the vertices of the scaled-down unit cube inscribed inside the unit ball centered at $0$.



Almost orthogonal vectors in subsets of euclidean space
Nearly two months after I asked the above question, I have come across a paper where Noga Alon has given an explicit result in [Problems and results in Extremal Combinatorics, Part I](http://www.tau.ac.il/~nogaa/PDFS/extremal1.pdf) in section 9, *On ranks of perturbations of identity matrices*. He says


**Lemma 9.1.** Let $A = (a\_{ij})$ be an $n \times n$ real, symmetric matrix with $a\_{ii} = 1$ for all $i$ and $|a\_{ij}|\le\epsilon$ for all $i\ne j$. If the rank of $A$ is $d$, then $d\ge \frac{n}{1+(n-1)\epsilon^2}$. In particular, if $\epsilon\le \frac{1}{\sqrt{n}}$ then $d\ge\frac{n}{2}$.


His proof is rather pretty. I apply the lemma to the question at hand as follows.


**Application.** Suppose $S$ is an $m\times n$ matrix with row vectors $(s\_1,\ldots, s\_m)$, an $m$-element subset of $\lbrace\frac{1}{\sqrt{n}},-\frac{1}{\sqrt{n}}\rbrace^n$ such that $\forall s\_i,s\_j\in S: i\ne j\implies |\langle s\_i,s\_j\rangle|\le\epsilon$.


Let $A=(a\_{ij})$ be its Gram matrix, which is symmetric $m\times m$ with $a\_{ii} = \langle s\_i,s\_i\rangle = 1$ for all $i$ and $|a\_{ij}|=|\langle s\_i, s\_j \rangle|\le\epsilon$ for all $i\ne j$, and rank $d$. Note that the rank of $S$ also $d$.


By the lemma, since $n\ge d$, we get $\boxed{n\ge \frac{m}{1+(m-1)\epsilon^2}}$.


Assuming $\epsilon\le \frac{1}{\sqrt{n}}$, some manipulation also yields $\boxed{m\le \frac{n(1-\epsilon^2)}{1-n\epsilon^2}}$.


Bill Johnson's reference to the Johnson-Lindenstrauss lemma led me to its Wikipedia page, which had the paper as a reference.


