research-article

Equiangular lines and the Lemmens–Seidel conjecture

Authors:

Yen-Chi Roger Lin,

Wei-Hsuan YuAuthors Info & Claims

Volume 343, Issue 2

https://doi.org/10.1016/j.disc.2019.111667

Published: 01 February 2020 Publication History

Abstract

In this paper, claims by Lemmens and Seidel in 1973 about equiangular sets of lines with angle 1 ∕ 5 are proved by carefully analyzing pillar decomposition, with the aid of the uniqueness of two-graphs on 276 vertices. The Neumann Theorem is generalized in the sense that if there are more than 2 r − 2 equiangular lines in R r, then the angle is quite restricted. Together with techniques on finding saturated equiangular sets, we determine the maximum size of equiangular sets “exactly” in an r-dimensional Euclidean space for r = 8, 9, and 10.

References

[1]

Azarija Jernej, Marc Tilen, There is no ( 95, 40, 12, 20 ) strongly regular graph, 2016, arXiv preprint arXiv:1603.02032.

[2]

Balla Igor, Dräxler Felix, Keevash Peter, Sudakov Benny, Equiangular lines and spherical codes in Euclidean space, Invent. Math. 211 (1) (2018) 179–212.

[3]

Bannai Eiichi, Bannai Etsuko, Xiang Ziqing, Yu Wei-Hsuan, Zhu Yan, Classification problem of certain spherical embeddings of strongly regular graphs, 2018, private communication.

[4]

Bannai Eiichi, Okuda Takayuki, Tagami Makoto, Spherical designs of harmonic index t, J. Approx. Theory 195 (2015) 1–18.

[5]

Bannai Eiichi, Zhao Da, Zhu Lin, Zhu Yan, Zhu Yinfeng, Half of an antipodal spherical design, Arch. Math (2018) 1–8.

[6]

Barg Alexander, Glazyrin Alexey, Okoudjou Kasso A., Yu Wei-Hsuan, Finite two-distance tight frames, Linear Algebra Appl. 475 (2015) 163–175.

[7]

Barg Alexander, Yu Wei-Hsuan, New bounds for equiangular lines, Contemp. Math. 625 (2014) 111–121.

[8]

Boyd Stephen, Vandenberghe Lieven, Convex Optimization, Cambridge University Press, 2004.

Digital Library

[9]

Peter J. Cameron, Strongly regular graphs, in: Topics in Algebraic Graph Theory, vol. 102, Cambridge Univ. Press, 2004, pp. 203–221.

[10]

Cohn Henry, Kumar Abhinav, Universally optimal distribution of points on spheres, J. Amer. Math. Soc. 20 (1) (2007) 99–148.

[11]

Delsarte P., Spherical codes and designs, Geom. Dedicata 6 (1977) 363–388.

[12]

Delsarte Ph., Goethals J.M., Seidel J. Jacob, Orthogonal matrices with zero diagonal. II, Canad. J. Math. 23 (5) (1971) 816–832.

[13]

Fickus Matthew, Jasper John, Mixon Dustin G., Peterson Jesse, Tremain equiangular tight frames, J. Combin. Theory Ser. A 153 (2018) 54–66.

[14]

Fickus Matthew, Mixon Dustin G., Jasper John, Equiangular tight frames from hyperovals, IEEE Trans. Inform. Theory 62 (9) (2016) 5225–5236.

[15]

Flajolet Philippe, Sedgewick Robert, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.

[16]

Glazyrin Alexey, Yu Wei-Hsuan, Upper bounds for s-distance sets and equiangular lines, Adv. Math. 330 (2018) 810–833.

[17]

Godsil Chris, Royle Gordon, Algebraic Graph Theory, in: Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2013.

[18]

Goethals J.M., Seidel J.J., The regular two-graph on 276 vertices, Discrete Math. 12 (2) (1975) 143–158.

[19]

Greaves Gary R.W., Equiangular line systems and switching classes containing regular graphs, Linear Algebra Appl. 536 (2018) 31–51.

[20]

Greaves Gary, Koolen Jacobus H., Munemasa Akihiro, Szöllősi Ferenc, Equiangular lines in Euclidean spaces, J. Combin. Theory Ser. A 138 (2016) 208–235.

[21]

Greaves Gary, Suda Sho, Symmetric and skew-symmetric { 0, ± 1 }-matrices with large determinants, J. Combin. Des. 25 (11) (2017) 507–522.

[22]

Greaves Gary, Yatsyna Pavlo, On equiangular lines in 17 dimensions and the characteristic polynomial of a Seidel matrix, Math. Comp. 88 (320) (2019) 3041–3061.

[23]

Haantjes J., Equilateral point-sets in elliptic two- and three-dimensional spaces, Nieuw Arch. Wisk 22 (2) (1948) 355–362.

[24]

James E. Humphreys, Reflection Groups and Coxeter Groups, vol. 29, Cambridge University Press, 1992.

[25]

Jasper John, Mixon Dustin G., Fickus Matthew, Kirkman equiangular tight frames and codes, IEEE Trans. Inform. Theory 60 (1) (2014) 170–181.

[26]

Jiang Zilin, Polyanskii Alexandr, Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines, 2017, arXiv preprint arXiv:1708.02317.

[27]

Jiang Zilin, Tidor Jonathan, Yao Yuan, Zhang Shengtong, Zhao Yufei, Equiangular lines with a fixed angle, 2019, arXiv preprint arXiv:1907.12466.

[28]

King Emily J., Tang Xiaoxian, Computing upper bounds for equiangular lines in Euclidean spaces, 2016, arXiv preprint arXiv:1606.03259.

[29]

Lemmens Petrus W.H., Seidel Johan J., Equiangular lines, J. Algebra 24 (3) (1973) 494–512.

[30]

Lin Yen-chi Roger, Yu Wei-Hsuan, Saturated configuration and new construction of equiangular lines, 2018, arXiv preprint arXiv:1801.04502.

[31]

van Lint Jacobus H., Seidel Johan J., Equilateral point sets in elliptic geometry, Indag. Math. 28 (3) (1966) 335–348.

[32]

Mixon Dustin G., Solazzo James, A short introduction to optimal line packings, College Math. J. 49 (2) (2018) 82–91.

[33]

Neumaier Arnold, Some sporadic geometries related to P G ( 3, 2 ), Arch. Math 42 (1) (1984) 89–96.

[34]

Neumaier Arnold, Graph representations, two-distance sets, and equiangular lines, Linear Algebra Appl. 114 (1989) 141–156.

[35]

Okuda Takayuki, Yu Wei-Hsuan, A new relative bound for equiangular lines and nonexistence of tight spherical designs of harmonic index 4, European J. Combin. 53 (2016) 96–103.

[36]

Renes Joseph M., Blume-Kohout Robin, Scott Andrew J., Caves Carlton M., Symmetric informationally complete quantum measurements, J. Math. Phys. 45 (6) (2004) 2171–2180.

[37]

Saff Edward B., Kuijlaars Amo B.J., Distributing many points on a sphere, Math. Intelligencer 19 (1) (1997) 5–11.

[38]

The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.8), 2019, http://www.sagemath.org.

[39]

Scott Andrew J., Tight informationally complete quantum measurements, J. Phys. A: Math. Gen. 39 (43) (2006) 13507.

[40]

Scott Andrew James, Grassl Markus, Symmetric informationally complete positive-operator-valued measures: A new computer study, J. Math. Phys. 51 (4) (2010) 042203.

[41]

Smith John H., Some properties of the spectrum of a graph, in: Combinatorial Structures and their Applications, Gordon and Breach New York, 1970, pp. 403–406.

[42]

Strohmer Thomas, Heath Robert W., Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal. 14 (3) (2003) 257–275.

[43]

Taylor Donald E., Some topics in the theory of finite groups, (Ph.D. thesis) University of Oxford, 1971.

[44]

Thomson XXIV Joseph John, On the structure of the atom: an investigation of the stability and periods of oscillation of a number of corpuscles arranged at equal intervals around the circumference of a circle; with application of the results to the theory of atomic structure, Lond. Edinb. Dublin Phil. Mag. J. Sci. 7 (39) (1904) 237–265.

[45]

Waldron Shayne, On the construction of equiangular frames from graphs, Linear Algebra Appl. 431 (11) (2009) 2228–2242.

[46]

Welch Lloyd, Lower bounds on the maximum cross correlation of signals (corresp.), IEEE Trans. Inform. Theory 20 (3) (1974) 397–399.

[47]

Witt Ernst, Die 5-fach transitiven Gruppen von Mathieu, Abh. Math. Semin. Univ. Hambg. 12 (1) (1937) 256–264.

[48]

Yu Wei-Hsuan, There are no 76 equiangular lines in R 19 , 2015, arXiv preprint arXiv:1511.08569.

[49]

Zauner Gerhard, Grundzüge einer Nichtkommutativen Designtheorie, (Ph.D. thesis) University of Vienna, 1999.

[50]

Zhu Yan, Bannai Eiichi, Bannai Etsuko, Kim Kyoung-Tark, Yu Wei-Hsuan, On spherical designs of some harmonic indices, Electron. J. Combin. 24 (2) (2017) 2–14.

Cited By

Cao MKoolen JLin YYu W(2022)The Lemmens-Seidel conjecture and forbidden subgraphsJournal of Combinatorial Theory Series A10.1016/j.jcta.2021.105538185:COnline publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1016/j.jcta.2021.105538
de Laat DMachado FFilho FVallentin F(2022)k-Point semidefinite programming bounds for equiangular linesMathematical Programming: Series A and B10.1007/s10107-021-01638-x194:1-2(533-567)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10107-021-01638-x

Index Terms

Equiangular lines and the Lemmens–Seidel conjecture
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Index terms have been assigned to the content through auto-classification.

Recommendations

Constructions of complex equiangular lines from mutually unbiased bases

A set of vectors of equal norm in $$\mathbb {C}^d$$Cd represents equiangular lines if the magnitudes of the Hermitian inner product of every pair of distinct vectors in the set are equal. The maximum size of such a set is $$d^2$$d2, and it is ...
On Weyl-Heisenberg orbits of equiangular lines

An element $\mathbf {z}\in \mathbb {CP}^{d-1}$ is called fiducial if { gz : g G } is a set of lines with only one angle between each pair, where G d ý d is the one-dimensional finite Weyl-Heisenberg group modulo its centre. We give a new ...
Equiangular lines in Euclidean spaces

We obtain several new results contributing to the theory of real equiangular line systems. Among other things, we present a new general lower bound on the maximum number of equiangular lines in d dimensional Euclidean space; we describe the two-graphs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Mathematics

Discrete Mathematics Volume 343, Issue 2

Feb 2020

361 pages

ISSN:0012-365X

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 February 2020

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cao MKoolen JLin YYu W(2022)The Lemmens-Seidel conjecture and forbidden subgraphsJournal of Combinatorial Theory Series A10.1016/j.jcta.2021.105538185:COnline publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1016/j.jcta.2021.105538
de Laat DMachado FFilho FVallentin F(2022)k-Point semidefinite programming bounds for equiangular linesMathematical Programming: Series A and B10.1007/s10107-021-01638-x194:1-2(533-567)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10107-021-01638-x

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents