Codes and Expansions (CodEx) Seminar

Chris Cox (Carnegie Mellon University / Ohio State University)
Nearly Orthogonal Vectors

How can \(d+k\) vectors in \(\mathbb R^d\) be arranged so that they are as close to orthogonal as possible? In particular, define \(\theta(d,k):=\min_X\max_{x\neq y\in X}|\langle x,y\rangle|\) where the minimum is taken over all collections of \(d+k\) unit vectors \(X\subseteq\mathbb R^d\). In this work, we focus on the case where \(k\) is fixed and \(d\to\infty\). In establishing bounds on \(\theta(d,k)\), we find an intimate connection to the existence of systems of \({k+1\choose 2}\) equiangular lines in \(\mathbb R^k\). Using this connection, we are able to pin down \(\theta(d,k)\) whenever \(k\in\{1,2,3,7,23\}\) and establish asymptotics for general \(k\). The main tool is an upper bound on \(\mathbb E_{x,y\sim\mu}|\langle x,y\rangle|\) whenever \(\mu\) is an isotropic probability mass on \(\mathbb R^k\), which may be of independent interest. Our results translate naturally to the analogous question in \(\mathbb C^d\). In this case, the question relates to the existence of systems of \(k^2\) equiangular lines in \(\mathbb C^k\), also known as SIC-POVM inphysics literature. Joint work with Boris Bukh.