Equiangular lines and regular graphs
share
In 1973, Lemmens and Seidel posed the problem of determining N_α(r), the maximum number of equiangular lines in ℝ^r with common angle arccos(α). Recently, this question has been almost completely settled in the case where r is large relative to 1/α, with the approach relying on Ramsey's theorem. In this paper, we use orthogonal projections of matrices with respect to the Frobenius inner product in order to overcome this limitation, thereby obtaining upper bounds on N_α(r) which significantly improve on the only previously known universal bound of Glazyrin and Yu, as well as taking an important step towards determining N_α(r) exactly for all r, α. In particular, our results imply that N_α(r) = Θ(r) for α≥Ω(1/r^1/5). Our arguments rely on a new geometric inequality for equiangular lines in ℝ^r which is tight when the number of lines meets the absolute bound r+12. Moreover, using the connection to graphs, we obtain lower bounds on the second eigenvalue of the adjacency matrix of a regular graph which are tight for strongly regular graphs corresponding to r+12 equiangular lines in ℝ^r. Our results only require that the spectral gap is less than half the number of vertices and can therefore be seen as an extension of the Alon-Boppana theorem to dense graphs. Generalizing to ℂ, we also obtain the first universal bound on the maximum number of complex equiangular lines in ℂ^r with common Hermitian angle arccos(α). In particular, we prove an inequality for complex equiangular lines in ℂ^r which is tight if the number of lines meets the absolute bound r^2 and may be of independent interest in quantum theory. Additionally, we use our projection method to obtain an improvement to Welch's bound.
READ FULL TEXT