Equiangular lines with a fixed angle

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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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},
      }
  • [GR01] Go to document C. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001, vol. 207.
    @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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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},
      }

Authors

Zilin Jiang

Arizona State University, Tempe, AZ

Jonathan Tidor

Massachusetts Institute of Technology, Cambridge, MA

Yuan Yao

Massachusetts Institute of Technology, Cambridge, MA

Shengtong Zhang

Massachusetts Institute of Technology, Cambridge, MA

Yufei Zhao

Massachusetts Institute of Technology, Cambridge, MA