Almost orthogonal vectors in subsets of euclidean space

Question

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

Answer 1

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.

Answer 2

There is a variety of related results in the coding theory/sequence design for CDMA literature. The chapter by Helleseth and Kumar, in Vol. II, of the Handbook of Coding Theory (Pless and Huffman eds.) has an extensive discussion under Welch bounds, Sidelnikov Bounds, Levenshtein bounds and the like. Some of these are general, others focus on your scenario of signal set $\{\pm 1\}$ (the tradition is to not normalize to unit vectors) or the signal set of $k^{th}$ roots of unity ($k=4$ is a popular choice due to technological reasons). In the language of the chapter $\theta=\sqrt{n}\epsilon.$

Some sample bounds on maximal $m$:

1. Welch (applies to arbitrary complex vectors)

$$\theta^2\geq \frac{m-n}{n(m-1)},$$ which needs $m>n$ for nontriviality but is then quite strong.

2. Levenshtein

$$m\leq \frac{n^2-\theta^2}{n(n-\theta^2)},\quad 0\leq \theta^2 \leq n-2.$$

3. Sidelnikov (for roots of unity sequences only)

This is for $\{\pm 1\}^n:$

$$\theta^2 > \max_k (2k+1)(n-k)+\binom{k}{2}-\frac{2^k n^{2k+1}}{m(2k)!\binom{n}{k}},\quad 0\leq k\leq \frac{2n}{5}.$$

Explicit Designs

Due to applications in wireless, consider $\{\pm 1\}^n$ as your ambient space. If you include a vector in a set, you have to include all of its cyclic shifts as well, since synchronisation is not assumed but is in fact the goal of these vectors. This makes no difference to the bounds, of course. So, by counting all the shifts as distinct we can have [only for $n$ of special form $n=2^k-1,$ due to the Galois Field or Galois Ring based algebraic designs:

1. A collection of $m=n^2+n$ vectors for $n=2^k-1,$ $k$ odd, with $\epsilon=\sqrt{2/n},$ which essentially optimal for binary sequences [Gold Sequences [1], Gold-like sequences [2] are the terminology used].

2. For $r\geq 2$ a collection of $m\geq 2^{(r+1)k}=O(n^{r+1})$ vectors with length $n=2^k-1,$ and with $$\epsilon=\frac{2^{(r+1)/2}}{\sqrt{n}}=\frac{C(r)}{\sqrt{n}}$$ so much larger families are possible subject to a correlation penalty. These designs get very complicated since they use degree $r$ polynomials [3].

If we choose the space $\{\pm 1,\pm i\}$ using Galois rings we can have

3. A collection of $m=n^2+n$ vectors with length $n$ and $\epsilon=\sqrt{1/n},$ which is essentially optimal for non-binary sequences. The Family A, see [2] showed that the discrepancy between a tighter binary bound and a looser nonbinary bound derived by Sidelnikov was not an anomaly but a geometric fact and was the first to use Galois rings in sequence design. This quickly led to the $\mathbb{Z}_4$ linearity of the Kerdock and Preparata codes (they are nonlinear over binary) [4] which mysteriously obeyed the McWilliams identities, which linear codes obey.

References:

1. R. Gold, Maximal recursive sequences with 3-valued recursive cross-correlation function, IEEE Trans. Information Theory, 1968

2. S Boztas, PV Kumar Binary sequences with Gold-like correlation but larger linear span IEEE Transactions on Information Theory 40(2), 532-537, 1994.

3. U Parampalli, XH Tang, S Boztas On the Construction Families of Binary Sequences with Low Correlation and Large Sizes IEEE Transactions on Information Theory 59(2), 1082-1089, 2013

4. A. R. Hammons, Jr., P. Vijay Kumar, A.R. Calderbank, N.J.A. Sloane, P. Solé, The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes, IEEE Trans. Inform. Theory, 40 (1994), 301-319