Abstract
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 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.
-
[BDKS18]
I. Balla, F. Dräxler, P. Keevash, and B. Sudakov, "Equiangular lines and spherical codes in Euclidean space," Invent. Math., vol. 211, iss. 1, pp. 179-212, 2018.
@ARTICLE{BDKS18,
author = {Balla, Igor and Dräxler, Felix and Keevash, Peter and Sudakov, Benny},
title = {Equiangular lines and spherical codes in {E}uclidean space},
journal = {Invent. Math.},
fjournal = {Inventiones Mathematicae},
volume = {211},
year = {2018},
number = {1},
pages = {179--212},
issn = {0020-9910},
mrclass = {94B25 (52C10)},
mrnumber = {3742757},
mrreviewer = {Kiyoshi Yoshimoto},
doi = {10.1007/s00222-017-0746-0},
url = {https://doi.org/10.1007/s00222-017-0746-0},
zblnumber = {1383.51035},
} -
[BY14]
A. Barg and W. Yu, "New bounds for equiangular lines," in Discrete geometry and algebraic combinatorics, Amer. Math. Soc., Providence, RI, 2014, vol. 625, pp. 111-121.
@INCOLLECTION{BY14,
author = {Barg, Alexander and Yu, Wei-Hsuan},
title = {New bounds for equiangular lines},
booktitle = {Discrete geometry and algebraic combinatorics},
series = {Contemp. Math.},
volume = {625},
pages = {111--121},
publisher = {Amer. Math. Soc., Providence, RI},
year = {2014},
mrclass = {52C35 (90C22)},
mrnumber = {3289408},
doi = {10.1090/conm/625/12494},
url = {https://doi.org/10.1090/conm/625/12494},
zblnumber = {1333.52027},
} -
[Bukh16]
B. Bukh, "Bounds on equiangular lines and on related spherical codes," SIAM J. Discrete Math., vol. 30, iss. 1, pp. 549-554, 2016.
@ARTICLE{Bukh16,
author = {Bukh, Boris},
title = {Bounds on equiangular lines and on related spherical codes},
journal = {SIAM J. Discrete Math.},
fjournal = {SIAM Journal on Discrete Mathematics},
volume = {30},
year = {2016},
number = {1},
pages = {549--554},
issn = {0895-4801},
mrclass = {94B25 (05D10)},
mrnumber = {3477753},
mrreviewer = {Lyuben R. Mutafchiev},
doi = {10.1137/15M1036920},
url = {https://doi.org/10.1137/15M1036920},
zblnumber = {1333.05309},
} -
[dC00]
D. de Caen, "Large equiangular sets of lines in Euclidean space," Electron. J. Combin., vol. 7, p. 55, 2000.
@ARTICLE{dC00,
author = {de Caen, D.},
title = {Large equiangular sets of lines in {E}uclidean space},
journal = {Electron. J. Combin.},
fjournal = {Electronic Journal of Combinatorics},
volume = {7},
year = {2000},
pages = {Research Paper 55, 3},
mrclass = {51M15},
mrnumber = {1795615},
doi = {10.37236/1533},
url = {https://www.doi.org/10.37236/1533},
zblnumber = {0966.51010},
} -
[CM97]
T. H. Colding and W. P. Minicozzi II, "Harmonic functions on manifolds," Ann. of Math. (2), vol. 146, iss. 3, pp. 725-747, 1997.
@ARTICLE{CM97,
author = {Colding, Tobias H. and Minicozzi, II, William P.},
title = {Harmonic functions on manifolds},
journal = {Ann. of Math. (2)},
fjournal = {Annals of Mathematics. Second Series},
volume = {146},
year = {1997},
number = {3},
pages = {725--747},
issn = {0003-486X},
mrclass = {53C21 (31B05 58G30)},
mrnumber = {1491451},
mrreviewer = {Tanya J. Christiansen},
doi = {10.2307/2952459},
url = {https://doi.org/10.2307/2952459},
zblnumber = {0928.53030},
} -
[DSV03]
G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory, and Ramanujan Graphs, Cambridge Univ. Press, Cambridge, 2003, vol. 55.
@BOOK{DSV03,
author = {Davidoff, Giuliana and Sarnak, Peter and Valette, Alain},
title = {Elementary Number Theory, Group Theory, and {R}amanujan Graphs},
series = {London Math. Soc. Stud. Texts},
volume = {55},
publisher = {Cambridge Univ. Press, Cambridge},
year = {2003},
pages = {x+144},
isbn = {0-521-82426-5; 0-521-53143-8},
mrclass = {11-01 (05C75 11E25 20G05 20G40)},
mrnumber = {1989434},
mrreviewer = {Thomas R. Shemanske},
doi = {10.1017/CBO9780511615825},
url = {https://doi.org/10.1017/CBO9780511615825},
zblnumber = {1032.11001},
} -
[GY18]
A. Glazyrin and W. Yu, "Upper bounds for $s$-distance sets and equiangular lines," Adv. Math., vol. 330, pp. 810-833, 2018.
@ARTICLE{GY18,
author = {Glazyrin, Alexey and Yu, Wei-Hsuan},
title = {Upper bounds for {$s$}-distance sets and equiangular lines},
journal = {Adv. Math.},
fjournal = {Advances in Mathematics},
volume = {330},
year = {2018},
pages = {810--833},
issn = {0001-8708},
mrclass = {52C10},
mrnumber = {3787558},
mrreviewer = {Konrad J. Swanepoel},
doi = {10.1016/j.aim.2018.03.024},
url = {https://doi.org/10.1016/j.aim.2018.03.024},
zblnumber = {1394.52026},
} -
@BOOK{GR01,
author = {Godsil, Chris and Royle, Gordon},
title = {Algebraic Graph Theory},
series = {Grad. Texts in Math.},
volume = {207},
publisher = {Springer-Verlag, New York},
year = {2001},
pages = {xx+439},
isbn = {0-387-95241-1; 0-387-95220-9},
mrclass = {05-02 (05C50 05E30)},
mrnumber = {1829620},
mrreviewer = {Robin J. Wilson},
doi = {10.1007/978-1-4613-0163-9},
url = {https://doi.org/10.1007/978-1-4613-0163-9},
zblnumber = {0968.05002},
} -
[Gow08]
W. T. Gowers, "Quasirandom groups," Combin. Probab. Comput., vol. 17, iss. 3, pp. 363-387, 2008.
@ARTICLE{Gow08,
author = {Gowers, W. T.},
title = {Quasirandom groups},
journal = {Combin. Probab. Comput.},
fjournal = {Combinatorics, Probability and Computing},
volume = {17},
year = {2008},
number = {3},
pages = {363--387},
issn = {0963-5483},
mrclass = {20P05 (20D60)},
mrnumber = {2410393},
mrreviewer = {Tatiana Smirnova-Nagnibeda},
doi = {10.1017/S0963548307008826},
url = {https://doi.org/10.1017/S0963548307008826},
zblnumber = {1191.20016},
} -
[GKMS16]
G. Greaves, J. H. Koolen, A. Munemasa, and F. SzöllHosi, "Equiangular lines in Euclidean spaces," J. Combin. Theory Ser. A, vol. 138, pp. 208-235, 2016.
@ARTICLE{GKMS16,
author = {Greaves, Gary and Koolen, Jacobus H. and Munemasa, Akihiro and Szöllősi, Ferenc},
title = {Equiangular lines in {E}uclidean spaces},
journal = {J. Combin. Theory Ser. A},
fjournal = {Journal of Combinatorial Theory. Series A},
volume = {138},
year = {2016},
pages = {208--235},
issn = {0097-3165},
mrclass = {05C50 (52C35)},
mrnumber = {3423477},
mrreviewer = {Alyssa D. Sankey},
doi = {10.1016/j.jcta.2015.09.008},
url = {https://doi.org/10.1016/j.jcta.2015.09.008},
zblnumber = {1330.51006},
} -
[Gro81]
M. Gromov, "Groups of polynomial growth and expanding maps," Inst. Hautes Études Sci. Publ. Math., vol. 53, pp. 53-73, 1981.
@ARTICLE{Gro81,
author = {Gromov, Mikhael},
title = {Groups of polynomial growth and expanding maps},
journal = {Inst. Hautes \'{E}tudes Sci. Publ. Math.},
fjournal = {Institut des Hautes \'{E}tudes Scientifiques. Publications Mathématiques},
volume = {53},
year = {1981},
pages = {53--73},
issn = {0073-8301},
mrclass = {53C20 (22E40 58F15)},
mrnumber = {0623534},
mrreviewer = {J. A. Wolf},
doi = {10.1007/BF02698687},
url = {https://doi.org/10.1007/BF02698687},
zblnumber = {0474.20018},
} -
[Haa48] J. Haantjes, "Equilateral point-sets in elliptic two- and three-dimensional spaces," Nieuw Arch. Wiskunde (2), vol. 22, pp. 355-362, 1948.
@ARTICLE{Haa48,
author = {Haantjes, J.},
title = {Equilateral point-sets in elliptic two- and three-dimensional spaces},
journal = {Nieuw Arch. Wiskunde (2)},
volume = {22},
year = {1948},
pages = {355--362},
mrclass = {48.0X},
mrnumber = {0023530},
mrreviewer = {H. Busemann},
zblnumber = {0037.21703},
} -
[JP20]
Z. Jiang and A. Polyanskii, "Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines," Israel J. Math., vol. 236, iss. 1, pp. 393-421, 2020.
@ARTICLE{JP20,
author = {Jiang, Zilin and Polyanskii, Alexandr},
title = {Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines},
journal = {Israel J. Math.},
fjournal = {Israel Journal of Mathematics},
volume = {236},
year = {2020},
number = {1},
pages = {393--421},
issn = {0021-2172},
mrclass = {05C50 (05C75 52C10)},
mrnumber = {4093893},
mrreviewer = {Pavlo Yatsyna},
doi = {10.1007/s11856-020-1983-2},
url = {https://doi.org/10.1007/s11856-020-1983-2},
zblnumber = {1439.05138},
} -
[JTYZZ2] Z. Jiang, J. Tidor, Y. Yao, S. Zhang, and Y. Zhao, Spherical two-distance sets and eigenvalues of signed graphs, 2020.
@MISC{JTYZZ2,
author = {Jiang, Zilin and Tidor, Jonathan and Yao, Yuan and Zhang, Shengtong and Zhao, Yufei},
title = {Spherical two-distance sets and eigenvalues of signed graphs},
arxiv = {2006.06633},
year = {2020},
zblnumber = {},
} -
[K10]
B. Kleiner, "A new proof of Gromov’s theorem on groups of polynomial growth," J. Amer. Math. Soc., vol. 23, iss. 3, pp. 815-829, 2010.
@ARTICLE{K10,
author = {Kleiner, Bruce},
title = {A new proof of {G}romov's theorem on groups of polynomial growth},
journal = {J. Amer. Math. Soc.},
fjournal = {Journal of the American Mathematical Society},
volume = {23},
year = {2010},
number = {3},
pages = {815--829},
issn = {0894-0347},
mrclass = {20F65 (20F67 20F69)},
mrnumber = {2629989},
mrreviewer = {François Dahmani},
doi = {10.1090/S0894-0347-09-00658-4},
url = {https://doi.org/10.1090/S0894-0347-09-00658-4},
zblnumber = {1246.20038},
} -
[LM08] J. Lee and Y. Makarychev, Eigenvalue multiplicity and volume growth, 2008.
@MISC{LM08,
author = {Lee, James~R. and Makarychev, Yury},
title = {Eigenvalue multiplicity and volume growth},
arxiv = {0806.1745},
year = {2008},
zblnumber = {},
} -
[LS73]
P. W. H. Lemmens and J. J. Seidel, "Equiangular lines," J. Algebra, vol. 24, pp. 494-512, 1973.
@ARTICLE{LS73,
author = {Lemmens, P. W. H. and Seidel, J. J.},
title = {Equiangular lines},
journal = {J. Algebra},
fjournal = {Journal of Algebra},
volume = {24},
year = {1973},
pages = {494--512},
issn = {0021-8693},
mrclass = {05C30 (52A40)},
mrnumber = {0307969},
mrreviewer = {J. J. Burckhardt},
doi = {10.1016/0021-8693(73)90123-3},
url = {https://doi.org/10.1016/0021-8693(73)90123-3},
zblnumber = {0255.50005},
} -
[LS66] J. H. van Lint and J. J. Seidel, "Equilateral point sets in elliptic geometry," Nederl. Akad. Wetensch. Proc. Ser. A, vol. 69, pp. 335-348, 1966.
@ARTICLE{LS66,
author = {van Lint, J. H. and Seidel, J. J.},
title = {Equilateral point sets in elliptic geometry},
journal = {Nederl. Akad. Wetensch. Proc. Ser. A},
volume = {69},
year = {1966},
pages = {335--348},
mrclass = {52.50},
mrnumber = {0200799},
mrreviewer = {L. M. Blumenthal},
zblnumber = {0138.41702},
} -
[Neu89]
A. Neumaier, "Graph representations, two-distance sets, and equiangular lines," Linear Algebra Appl., vol. 114/115, pp. 141-156, 1989.
@ARTICLE{Neu89,
author = {Neumaier, A.},
title = {Graph representations, two-distance sets, and equiangular lines},
journal = {Linear Algebra Appl.},
fjournal = {Linear Algebra and its Applications},
volume = {114/115},
year = {1989},
pages = {141--156},
issn = {0024-3795},
mrclass = {05C75 (05C50)},
mrnumber = {0986870},
mrreviewer = {J. J. Seidel},
doi = {10.1016/0024-3795(89)90456-4},
url = {https://doi.org/10.1016/0024-3795(89)90456-4},
zblnumber = {0724.05043},
} -
[RBSC04]
J. M. Renes, R. Blume-Kohout, A. J. Scott, and C. M. Caves, "Symmetric informationally complete quantum measurements," J. Math. Phys., vol. 45, iss. 6, pp. 2171-2180, 2004.
@ARTICLE{RBSC04,
author = {Renes, Joseph M. and Blume-Kohout, Robin and Scott, A. J. and Caves, Carlton M.},
title = {Symmetric informationally complete quantum measurements},
journal = {J. Math. Phys.},
fjournal = {Journal of Mathematical Physics},
volume = {45},
year = {2004},
number = {6},
pages = {2171--2180},
issn = {0022-2488},
mrclass = {81P15},
mrnumber = {2059685},
doi = {10.1063/1.1737053},
url = {https://doi.org/10.1063/1.1737053},
zblnumber = {1071.81015},
} -
[SH03]
T. Strohmer and R. W. Heath Jr., "Grassmannian frames with applications to coding and communication," Appl. Comput. Harmon. Anal., vol. 14, iss. 3, pp. 257-275, 2003.
@ARTICLE{SH03,
author = {Strohmer, Thomas and Heath, Jr., Robert W.},
title = {Grassmannian frames with applications to coding and communication},
journal = {Appl. Comput. Harmon. Anal.},
fjournal = {Applied and Computational Harmonic Analysis. Time-Frequency and Time-Scale Analysis, Wavelets, Numerical Algorithms, and Applications},
volume = {14},
year = {2003},
number = {3},
pages = {257--275},
issn = {1063-5203},
mrclass = {42C15 (46B15 46C05 94A12)},
mrnumber = {1984549},
mrreviewer = {Raquel Garcia Catal\'{a}n},
doi = {10.1016/S1063-5203(03)00023-X},
url = {https://doi.org/10.1016/S1063-5203(03)00023-X},
zblnumber = {1028.42020},
}