# Neat/Approximate formula for maximum number of “almost orthogonal” vectors in a complex vector space?

In a $$d$$ dimensional vector space defined over $$\mathbb{C}$$, how do I calculate the largest number $$N(\epsilon, d)$$ of vectors $$\{V_i\}$$ which satisfies the following properties. Here $$\epsilon$$ is smaller but finite compared to 1.

$$\langle V_i, V_i\rangle = 1$$

$$|\langle V_i, V_j\rangle| \leq \epsilon, i \neq j$$

Some examples are as follows.

1. $$N(0, d)$$ = d

2. $$N\left(\frac{1}{2}, 2\right)$$ = 3

3. $$N\left(\frac{1}{\sqrt{2}}, 2\right) = 6$$

How do I obtain any general formula for $$N(\epsilon, d)$$. Even an approximate form for $$N(\epsilon, d)$$ in the large $$d$$ and small $$\epsilon$$ ($$\epsilon \ll 1$$) limit works fine for me.

• crossposted math.stackexchange.com/questions/3296448/… --- please don't do that, in order to avoid duplication of efforts. – Carlo Beenakker Jul 18 '19 at 8:09
• this is the content of the Johnson–Lindenstrauss lemma : $N\simeq e^{d\epsilon^2/8}$ – Carlo Beenakker Jul 18 '19 at 8:13
• Hi @CarloBeenakker, I crossposted this to increase the audience, and to avoid duplication of efforts I would edit the question on other platform if I find my answer somewhere. Regarding your comment, is there a version of JL lemma for high dimensional vector spaces defined over ℂ ? This is very close to the formula I was looking for, so thanks for pointing that out. – Bruce Lee Jul 18 '19 at 8:33
• Related question and answers. mathoverflow.net/questions/24864/almost-orthogonal-vectors/… – kodlu Jul 18 '19 at 10:40

The variant of the Johnson-Lindenstrauss lemma that you can use is derived by L. Welch in Lower bounds on the maximum cross correlation of signals (1974). This paper is behind a paywall, I quote the result from arXiv:0909.0206

Consider $$N=d^{k}$$ unit vectors $$V_i$$ in $$\mathbb{C}^d$$ with $$N>d$$. Then the maximal inner product $$\epsilon=\max_{i\neq j}|\langle V_i|V_j\rangle|$$ satisfies the inequality $$\epsilon^{2k}\geq \frac{1}{N-1}\left(\frac{N}{{{d+k-1}\choose{k}}}-1\right).$$