How many non-orthogonal vectors fit into a complex vector space?

Question

I am sitting on a problem, where I have a complex vector space of dimension $D$ and a set of normalized vectors $\{v_k\}$, $k\in\{1,2,\dots,N\}$ that are supposed to satisfy

$$\lvert\langle v_j\vert v_k\rangle\rvert \le \epsilon$$

for all $j$ and $k$. Question: for a given $D$ and $\epsilon$, what is the maximum number $N$ of such vectors? Remark: I'd be happy with estimates/approximations for large $D$ and/or small $\epsilon$ (addendum: this remark is made more precise below in response to some answers).

Now, if everything were in a real Euclidean vector space, I would estimate $N$ by dividing half the area of the hypersphere $\mathbb{S}^{D-1}$ by the area of a spherical cap with polar angle $\theta = \arccos(\epsilon)/2$. I am not sure whether this result would be optimal. A search in the internet revealed that people much more clever than I thought about this under the headline spherical codes and sphere packing….

But in any case, what I am interested in is a complex vector space, for which I couldn't find anything in the web so far. The difficulty is, of course, that only the real part of the scalar product of two complex vectors can be identified with an angle between two real vectors in $\mathbb{S}^{2D-1}$, whereas the imaginary part has something to do with the area of the parallelogram they span (I've read). Unfortunately, I have no idea how to include this in the calculation.

Any ideas? Many thanks!

---

For completeness, here is an updated answer based on the helpful answer of Mikhail Katz:

The ratio of the volumes of the complex plane $\mathbb{C}P^{D-1}$ to a spherical "cap" $C(\theta)$ with angle $\theta$ around vector $v$, defined as the set of all vectors $w$ that satisfy $|\langle v|w\rangle|^2\le\cos(\theta)^2$, is $$\DeclareMathOperator\vol{vol}\frac{\vol(\mathbb{C}P^{D-1})}{\vol[C(\theta)]} = \frac{1}{\sin^{2D-2}(\theta)}.$$ This can be computed using, e.g., equations from the book "The Geometry of Quantum States" by Bengtsson and Zyczkowski. Note that this result tells us how often the volume of the cap fits into the complex projective plane, but not how many caps (without deforming them or ripping them apart) fit into it.

Based on this, we can obtain lower and upper bounds on the number $N$ of non-orthogonal vectors that fit into a complex vector space. An upper bound is given by assuming that the caps remain intact and the center of the $j$'th cap belongs to vector $v_j$. In this case the centers are an angle $2\theta$ apart, so we can set $\epsilon = \cos(2\theta)$ to satisfy $|\langle v_j|v_k\rangle| \le \epsilon$ for all $j,k$. A lower bound is given by setting $\cos(\theta) = \epsilon$. In this case, starting from an intact cap $C_1$ around $v_1$, we can "glue" $v_2$ to its boundary to define a new cap $C_2$ around $v_2$ (while we keep the overlap of $C_1$ and $C_2$ and fit it into the complex plane at the end). Continuing like that distributes the vectors $v_1,v_2,\dots,v_N$ in the complex plane and ensures they are at least an angle $\theta = \arccos(\epsilon)$ apart.

Thus, to summarize, we can estimate $N$ by the upper and lower bound $$\frac{1}{\sin^{2D-2}[\arccos(\epsilon)]} \le N \le \frac{1}{\sin^{2D-2}[\arccos(\epsilon)/2]}.$$ Now, performing some Taylor expansion, and using $(1+x)^n \approx e^{nx}$ for $|x|\ll 1$, we obtain the neat estimates $$\exp[(D-1)\epsilon^2]\le N \le \exp[(D-1)(2\epsilon+\ln2)].$$

Even though these estimates are not meaningful for $\epsilon=0$, they seem useful for finite but small $\epsilon$, as they clearly show that exponentially more almost orthogonal vectors fit into a $D$ dimensional complex vector space compared to the number $D$ of orthogonal vectors that fit into it.

Update of the remark in response to the answers of Jan Nienhaus and Dustin G. Mixon: With $\epsilon$ "small" I do not mean something like $\epsilon < 1/D$ or $\epsilon < 1/\sqrt{D}$. For instance, the numbers I am interested in are more like $D = {\cal O}(10^{10^{23}})$ and $\epsilon = {\cal O}(10^{-20})$ to give you an idea. In any case, I like a result where both $\epsilon$ and $D$ can be freely varied.

Answer 1

Jan Nienhaus's answer treats the case $\epsilon<\frac{1}{D}$. Here's a generalization that works whenever $\epsilon<\frac{1}{\sqrt{D}}$:

$$ N \leq \frac{1-\epsilon^2}{1 - D\epsilon^2}\cdot D. $$

This follows from the Welch bound, and equality is achieved by equiangular tight frames. E.g., when $\epsilon=\frac{1}{\sqrt{D+1}}$, equality is the subject of Zauner's conjecture. See [arxiv.org/abs/1504.00253] for details.

When $\epsilon<\sqrt{\frac{2}{D+1}}$, Levenshtein's bound implies

$$ N\leq \frac{1-\epsilon^2}{2-(D+1)\epsilon^2}\cdot D(D+1). $$

E.g., when $\epsilon=\frac{1}{\sqrt{D}}$, equality occurs when there is a set of $D+1$ mutually unbiased bases.

Additional bounds of this form can be obtained using Delsarte's linear program.

EDIT: While the above treats $\epsilon=O(\frac{1}{\sqrt{D}})$, we consider larger $\epsilon$ in the following.

Given $F\in\{\mathbb{R},\mathbb{C}\}$, let $N_F(D,\epsilon)$ denote the largest $N$ for which there exist unit vectors $v_1,\ldots,v_N\in F^D$ such that $|\langle v_j,v_k\rangle|\leq \epsilon$ for all $j,k\in\{1,\ldots,N\}$ with $j\neq k$. You are interested in the case where $F=\mathbb{C}$, but as you mention, most write about the case where $F=\mathbb{R}$. Of course, $\mathbb{R}^D\subseteq\mathbb{C}^D$, and so

$$N_\mathbb{C}(D,\epsilon)\geq N_\mathbb{R}(D,\epsilon).$$

On the other hand, the $\mathbb{R}$-linear isometry $f\colon\mathbb{C}^D\to\mathbb{R}^{2D}$ defined by

$$f(z)=(\operatorname{Re}z,\operatorname{Im}z)$$

has the property that

$$|\langle f(u),f(v)\rangle|=|\operatorname{Re}\langle u,v\rangle|\leq|\langle u,v\rangle|,$$

from which it follows that

$$N_\mathbb{C}(D,\epsilon) \leq N_\mathbb{R}(2D,\epsilon).$$

As such, bounds on $N_\mathbb{R}(D,\epsilon)$ can be transferred to bounds on $N_\mathbb{C}(D,\epsilon)$. For example, the Johnson-Lindenstrauss lemma and Theorem 9.3 in Alon's "Problems and results in extremal combinatorics—I" give the bounds

$$2^{\Omega(\epsilon^2\cdot D)} \leq N_\mathbb{R}(D,\epsilon)\leq 2^{O(\epsilon^2\log(1/\epsilon)\cdot D)}$$

in the regime $\frac{1}{\sqrt{D}}\leq\epsilon<\frac{1}{2}$. By the above discussion, these bounds also hold for $N_\mathbb{C}(D,\epsilon)$, but with the constant in the $O$ doubled.

Answer 2

While volume comparison will give you a rough estimate for any value of $\varepsilon$, the sharp estimate is that, for small enough $\varepsilon$, $N\le D$.

One way to get this is by showing that your vectors must be linearly independent by orthonormalizing them:

Starting with normalized vectors $v_1, \ldots, v_N$ satisfying $|\langle v_i, v_j\rangle|\le \varepsilon$ for $i\ne j$, we replace each $v_i, i\ne N$, by $v_i - \langle v_i, v_N\rangle v_N$. This will give us a new set of $N-1$ vectors orthogonal to $v_N$ with length $\ge 1 - \varepsilon$ (In particular, nonzero if $\varepsilon <1$). Let $\tilde{v}_i$ be the normalized rescalings of these. Then $\tilde{v}_i$ are orthogonal to $v_N$ and $|\langle\tilde{v}_i, \tilde{v}_j\rangle|\le (1-\varepsilon)^{-2}(1+\varepsilon)\varepsilon.$

This now lets us give inductive bounds on $\varepsilon$ in terms of $n$, since in dimension one there can not be two unit length vectors with $|\langle v, w\rangle|<1$. Quick calculations show that for example $|\langle v_i, v_j\rangle | \le \frac{1}{3D}$ is maintained under the induction, so any $\varepsilon \le \frac{1}{3D}$ forces linear independence. Note that while the constant isn't sharp (in fact, the sharp constant should be $\varepsilon < \frac{1}{D}$, with any counterexample with equality being isometric to a standard simplex), the $\frac{const.}{D}$-scaling is optimal.

The only loss in our estimates is the step 'with length $\ge 1-\varepsilon$'. The sharp bound here is $\sqrt{1-\varepsilon^2}$, leading to the sharp bound $\frac{1}{D}$ in the end.

Answer 3

This is a packing problem in the complex projective space $CP^{D-1}$ of dimension $D-1$ with its Fubini-Study metric. Since the volume of $CP^{D-1}$ is known, you can use the same argument by estimating the volume of a distance ball using curvature comparison.

One elegant way to figure out the volume of the Fubini-Study metric of $CP^n$ is to use the fact that it is optimal for Gromov's stable systolic inequality, so that the volume can be calculated as from the equality $\text{area}(CP^1)^n= n! \,\text{vol}(CP^n)$.