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.
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$.
Best Answer
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 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.