# Almost orthogonal vectors in subsets of euclidean space

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

-
For your particular subset, the first step would be to generate $S$ randomly. Here, inner products will be in terms of a binomial distribution, and then a union bound will tell you how big $S$ can be in terms of $\epsilon$. This will at least give you a (decent) lower bound on the largest possible size of $S$. –  Dustin G. Mixon May 23 '13 at 16:35
Well, for a random subset (where random can mean various things) the Johnson-Lindenstrauss lemma gives $\exp ( b \epsilon^2 m)$ for some positive constant $b$ independent of $n$ and $\epsilon$, Dustin. Presumably the OP is interested in more precise results and low dimensions. –  Bill Johnson May 23 '13 at 18:41
^ More precision, yes. Dimensions, not necessarily low. But anything is worth hearing. –  Seraj May 23 '13 at 18:54

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.

-