Equiangular lines with a fixed angle. (English) Zbl 1478.52015

Jiang, Zilin; Tidor, Jonathan; Yao, Yuan; Zhang, Shengtong; Zhao, Yufei

Ann. Math. (2) 194, No. 3, 729-743 (2021).

Summary: Solving a longstanding problem on equiangular lines, we determine, for each given fixed angle and in all sufficiently large dimensions, the maximum number of lines pairwise separated by the given angle.
Fix \(0<\alpha<1\). Let \(N_\alpha (d)\) denote the maximum number of lines through the origin in \(\mathbb{R}^d\) with pairwise common angle \(\operatorname{arccos}\alpha\). Let \(k\) denote the minimum number (if it exists) of vertices in a graph whose adjacency matrix has spectral radius exactly \((1-\alpha)/(2\alpha)\). If \(k<\infty\), then \(N_\alpha(d)=\lfloor k(d-1)/(k-1)\rfloor\) for all sufficiently large \(d\), and otherwise \(N_\alpha (d)=d+o(d)\). In particular, \(N_{1/(2k-1)}(d)=\lfloor k(d-1)/(k-1)\rfloor\) for every integer \(k\ge 2\) and all sufficiently large \(d\).
A key ingredient is a new result in spectral graph theory: the adjacency matrix of a connected bounded degree graph has sublinear second eigenvalue multiplicity.

MSC:

52C35	Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

equiangular lines; spectral graph theory; eigenvalue multiplicity

References:

[1]	Balla, Igor; Dr\"{a}xler, Felix; Keevash, Peter; Sudakov, Benny, Equiangular lines and spherical codes in {E}uclidean space, Invent. Math.. Inventiones Mathematicae, 211, 179-212 (2018) · Zbl 1383.51035 · doi:10.1007/s00222-017-0746-0
[2]	Barg, Alexander; Yu, Wei-Hsuan, New bounds for equiangular lines. Discrete geometry and algebraic combinatorics, Contemp. Math., 625, 111-121 (2014) · Zbl 1333.52027 · doi:10.1090/conm/625/12494
[3]	Bukh, Boris, Bounds on equiangular lines and on related spherical codes, SIAM J. Discrete Math.. SIAM Journal on Discrete Mathematics, 30, 549-554 (2016) · Zbl 1333.05309 · doi:10.1137/15M1036920
[4]	de Caen, D., Large equiangular sets of lines in {E}uclidean space, Electron. J. Combin.. Electronic Journal of Combinatorics, 7, 55-3 (2000) · Zbl 0966.51010 · doi:10.37236/1533
[5]	Colding, Tobias H.; Minicozzi, II, William P., Harmonic functions on manifolds, Ann. of Math. (2). Annals of Mathematics. Second Series, 146, 725-747 (1997) · Zbl 0928.53030 · doi:10.2307/2952459
[6]	Davidoff, Giuliana; Sarnak, Peter; Valette, Alain, Elementary Number Theory, Group Theory, and {R}amanujan Graphs, London Math. Soc. Stud. Texts, 55, x+144 pp. (2003) · Zbl 1032.11001 · doi:10.1017/CBO9780511615825
[7]	Glazyrin, Alexey; Yu, Wei-Hsuan, Upper bounds for {\(s\)}-distance sets and equiangular lines, Adv. Math.. Advances in Mathematics, 330, 810-833 (2018) · Zbl 1394.52026 · doi:10.1016/j.aim.2018.03.024
[8]	Godsil, Chris; Royle, Gordon, Algebraic Graph Theory, Grad. Texts in Math., 207, xx+439 pp. (2001) · Zbl 0968.05002 · doi:10.1007/978-1-4613-0163-9
[9]	Gowers, W. T., Quasirandom groups, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 17, 363-387 (2008) · Zbl 1191.20016 · doi:10.1017/S0963548307008826
[10]	Greaves, Gary; Koolen, Jacobus H.; Munemasa, Akihiro; Sz\"{o}ll\H{o}si, Ferenc, Equiangular lines in {E}uclidean spaces, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 138, 208-235 (2016) · Zbl 1330.51006 · doi:10.1016/j.jcta.2015.09.008
[11]	Gromov, Mikhael, Groups of polynomial growth and expanding maps, Inst. Hautes \'{E}tudes Sci. Publ. Math.. Institut des Hautes \'{E}tudes Scientifiques. Publications Math\'{e}matiques, 53, 53-73 (1981) · Zbl 0474.20018 · doi:10.1007/BF02698687
[12]	Haantjes, J., Equilateral point-sets in elliptic two- and three-dimensional spaces, Nieuw Arch. Wiskunde (2), 22, 355-362 (1948) · Zbl 0037.21703
[13]	Jiang, Zilin; Polyanskii, Alexandr, Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines, Israel J. Math.. Israel Journal of Mathematics, 236, 393-421 (2020) · Zbl 1439.05138 · doi:10.1007/s11856-020-1983-2
[14]	Jiang, Zilin; Tidor, Jonathan; Yao, Yuan; Zhang, Shengtong; Zhao, Yufei, Spherical two-distance sets and eigenvalues of signed graphs (2020)
[15]	Kleiner, Bruce, A new proof of {G}romov’s theorem on groups of polynomial growth, J. Amer. Math. Soc.. Journal of the American Mathematical Society, 23, 815-829 (2010) · Zbl 1246.20038 · doi:10.1090/S0894-0347-09-00658-4
[16]	Lee, James R.; Makarychev, Yury, Eigenvalue multiplicity and volume growth (2008)
[17]	Lemmens, P. W. H.; Seidel, J. J., Equiangular lines, J. Algebra. Journal of Algebra, 24, 494-512 (1973) · Zbl 0255.50005 · doi:10.1016/0021-8693(73)90123-3
[18]	van Lint, J. H.; Seidel, J. J., Equilateral point sets in elliptic geometry, Nederl. Akad. Wetensch. Proc. Ser. A, 69, 335-348 (1966) · Zbl 0138.41702
[19]	Neumaier, A., Graph representations, two-distance sets, and equiangular lines, Linear Algebra Appl.. Linear Algebra and its Applications, 114/115, 141-156 (1989) · Zbl 0724.05043 · doi:10.1016/0024-3795(89)90456-4
[20]	Renes, Joseph M.; Blume-Kohout, Robin; Scott, A. J.; Caves, Carlton M., Symmetric informationally complete quantum measurements, J. Math. Phys.. Journal of Mathematical Physics, 45, 2171-2180 (2004) · Zbl 1071.81015 · doi:10.1063/1.1737053
[21]	Strohmer, Thomas; Heath, Jr., Robert W., Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal.. Applied and Computational Harmonic Analysis. Time-Frequency and Time-Scale Analysis, Wavelets, Numerical Algorithms, and Applications, 14, 257-275 (2003) · Zbl 1028.42020 · doi:10.1016/S1063-5203(03)00023-X