Equiangular lines in Euclidean spaces: Dimensions 17 and 18

Greaves, Gary; Syatriadi, Jeven; Yatsyna, Pavlo

doi:10.1090/mcom/3832

Equiangular lines in Euclidean spaces: Dimensions 17 and 18
HTML articles powered by AMS MathViewer

by Gary R. W. Greaves, Jeven Syatriadi and Pavlo Yatsyna HTML | PDF

Math. Comp. 92 (2023), 1867-1903 Request permission

Abstract:

We show that the maximum cardinality of an equiangular line system in 17 dimensions is 48, thereby solving a longstanding open problem. Furthermore, by giving an explicit construction, we improve the lower bound on the maximum cardinality of an equiangular line system in 18 dimensions to 57.

References

Jernej Azarija and Tilen Marc, There is no $(75,32,10,16)$ strongly regular graph, Linear Algebra Appl. 557 (2018), 62–83. MR 3848262, DOI 10.1016/j.laa.2018.07.019
Jernej Azarija and Tilen Marc, There is no $(95, 40, 12, 20)$ strongly regular graph, J. Combin. Des. 28 (2020), no. 4, 294–306. MR 4069730, DOI 10.1002/jcd.21696
Igor Balla, Felix Dräxler, Peter Keevash, and Benny Sudakov, Equiangular lines and spherical codes in Euclidean space, Invent. Math. 211 (2018), no. 1, 179–212. MR 3742757, DOI 10.1007/s00222-017-0746-0
Boris Bukh, Bounds on equiangular lines and on related spherical codes, SIAM J. Discrete Math. 30 (2016), no. 1, 549–554. MR 3477753, DOI 10.1137/15M1036920
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
F. C. Bussemaker, W. H. Haemers, R. Mathon, and H. A. Wilbrink, A $(49,16,3,6)$ strongly regular graph does not exist, European J. Combin. 10 (1989), no. 5, 413–418. MR 1014548, DOI 10.1016/S0195-6698(89)80014-9
A.-L. Cauchy, Sur l’équation à l’aide de laquelle on détermine les inégalités séculaires des mouvements des planètes, In Œuvres complètes, IIième Série, Gauthier-Villars, Paris, 1829.
D. Cvetković, P. Rowlinson, and S. Simić, Eigenspaces of graphs, Encyclopedia of Mathematics and its Applications, vol. 66, Cambridge University Press, Cambridge, 1997. MR 1440854, DOI 10.1017/CBO9781139086547
Peter B. Denton, Stephen J. Parke, Terence Tao, and Xining Zhang, Eigenvectors from eigenvalues: a survey of a basic identity in linear algebra, Bull. Amer. Math. Soc. (N.S.) 59 (2022), no. 1, 31–58. MR 4340826, DOI 10.1090/S0273-0979-2021-01722-8
Julius Farkas, Theorie der einfachen Ungleichungen, J. Reine Angew. Math. 124 (1902), 1–27 (German). MR 1580578, DOI 10.1515/crll.1902.124.1
S. Fisk, A very short proof of Cauchy’s interlace theorem for eigenvalues of Hermitian matrices, Amer. Math. Monthly 112 (2005), no. 2, 118–118.
C. D. Godsil and B. D. McKay, Spectral conditions for the reconstructibility of a graph, J. Combin. Theory Ser. B 30 (1981), no. 3, 285–289. MR 624545, DOI 10.1016/0095-8956(81)90046-0
Chris Godsil and Gordon Royle, Algebraic graph theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. MR 1829620, DOI 10.1007/978-1-4613-0163-9
Alexey Glazyrin and Wei-Hsuan Yu, Upper bounds for $s$-distance sets and equiangular lines, Adv. Math. 330 (2018), 810–833. MR 3787558, DOI 10.1016/j.aim.2018.03.024
G. R. W. Greaves, Magma companion code and computations from the paper “Equiangular lines in Euclidean spaces: dimensions 17 and 18”, https://github.com/grwgrvs/equiangular17/, (2023).
Gary R. W. Greaves, Equiangular line systems and switching classes containing regular graphs, Linear Algebra Appl. 536 (2018), 31–51. MR 3713444, DOI 10.1016/j.laa.2017.09.008
Gary Greaves, Jacobus H. Koolen, Akihiro Munemasa, and Ferenc Szöllősi, Equiangular lines in Euclidean spaces, J. Combin. Theory Ser. A 138 (2016), 208–235. MR 3423477, DOI 10.1016/j.jcta.2015.09.008
Gary R. W. Greaves, Jeven Syatriadi, and Pavlo Yatsyna, Equiangular lines in low dimensional Euclidean spaces, Combinatorica 41 (2021), no. 6, 839–872. MR 4357433, DOI 10.1007/s00493-020-4523-0
G. R. W. Greaves, J. Syatriadi, and P. Yatsyna, Equiangular lines in Euclidean spaces: dimensions 17 and 18, arXiv:2104.04330, (2023).
Gary R. W. Greaves and Pavlo Yatsyna, On equiangular lines in 17 dimensions and the characteristic polynomial of a Seidel matrix, Math. Comp. 88 (2019), no. 320, 3041–3061. MR 3985486, DOI 10.1090/mcom/3433
J. Haantjes, Equilateral point-sets in elliptic two- and three-dimensional spaces, Nieuw Arch. Wiskunde (2) 22 (1948), 355–362. MR 0023530
Suk-Geun Hwang, Cauchy’s interlace theorem for eigenvalues of Hermitian matrices, Amer. Math. Monthly 111 (2004), no. 2, 157–159. MR 2042764, DOI 10.2307/4145217
Zilin Jiang and Alexandr Polyanskii, Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines, Israel J. Math. 236 (2020), no. 1, 393–421. MR 4093893, DOI 10.1007/s11856-020-1983-2
Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao, Equiangular lines with a fixed angle, Ann. of Math. (2) 194 (2021), no. 3, 729–743. MR 4334975, DOI 10.4007/annals.2021.194.3.3
Emily J. King and Xiaoxian Tang, New upper bounds for equiangular lines by pillar decomposition, SIAM J. Discrete Math. 33 (2019), no. 4, 2479–2508. MR 4043092, DOI 10.1137/19M1248881
David de Laat, Fabrício Caluza Machado, Fernando Mário de Oliveira Filho, and Frank Vallentin, $k$-point semidefinite programming bounds for equiangular lines, Math. Program. 194 (2022), no. 1-2, Ser. A, 533–567. MR 4445463, DOI 10.1007/s10107-021-01638-x
P. W. H. Lemmens and J. J. Seidel, Equiangular lines, J. Algebra 24 (1973), 494–512. MR 307969, DOI 10.1016/0021-8693(73)90123-3
Yen-chi Roger Lin and Wei-Hsuan Yu, Saturated configuration and new large construction of equiangular lines, Linear Algebra Appl. 588 (2020), 272–281. MR 4040139, DOI 10.1016/j.laa.2019.12.002
J. H. van Lint and J. J. Seidel, Equilateral point sets in elliptic geometry, Nederl. Akad. Wetensch. Proc. Ser. A 69=Indag. Math. 28 (1966), 335–348. MR 0200799
Wolfram Research, Inc., Mathematica, Version Number 10.0, Champaign, IL, 2014.
James McKee and Chris Smyth, Salem numbers of trace $-2$ and traces of totally positive algebraic integers, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 327–337. MR 2137365, DOI 10.1007/978-3-540-24847-7_{2}5
Takayuki Okuda and Wei-Hsuan Yu, A new relative bound for equiangular lines and nonexistence of tight spherical designs of harmonic index 4, European J. Combin. 53 (2016), 96–103. MR 3434430, DOI 10.1016/j.ejc.2015.11.003
J. J. Seidel, Graphs and two-graphs, Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974) Congressus Numerantium, No. X, Utilitas Math., Winnipeg, Man., 1974, pp. 125–143. MR 0364028
N. J. A. Sloane (editor), The On-Line Encyclopedia of Integer Sequences. Published electronically at https://oeis.org/, (2023).
Ferenc Szöllősi, A remark on a construction of D. S. Asche, Discrete Comput. Geom. 61 (2019), no. 1, 120–122. MR 3925546, DOI 10.1007/s00454-017-9933-4
D. E. Taylor, Regular $2$-graphs, Proc. London Math. Soc. (3) 35 (1977), no. 2, 257–274. MR 476587, DOI 10.1112/plms/s3-35.2.257
R. C. Thompson, Principal submatrices. V. Some results concerning principal submatrices of arbitrary matrices, J. Res. Nat. Bur. Standards Sect. B 72B (1968), 115–125. MR 244282, DOI 10.6028/jres.072B.015
Ernst Witt, Die 5-fach transitiven gruppen von mathieu, Abh. Math. Sem. Univ. Hamburg 12 (1937), no. 1, 256–264 (German). MR 3069689, DOI 10.1007/BF02948947
Wei-Hsuan Yu, New bounds for equiangular lines and spherical two-distance sets, SIAM J. Discrete Math. 31 (2017), no. 2, 908–917. MR 3651485, DOI 10.1137/16M109377X