Classification of eight-dimensional perfect forms

Sikirić, Mathieu; Schürmann, Achill; Vallentin, Frank

doi:10.1090/S1079-6762-07-00171-0

Previous volume | This volume | All volumes | Previous article | Next article

Classification of eight-dimensional perfect forms

Authors: Mathieu Dutour Sikirić, Achill Schürmann and Frank Vallentin
Journal: Electron. Res. Announc. Amer. Math. Soc. 13 (2007), 21-32
MSC (2000): Primary 11H31, 11H55; Secondary 52B55
DOI: https://doi.org/10.1090/S1079-6762-07-00171-0
Published electronically: April 11, 2007
MathSciNet review: 2300003
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we classify the perfect lattices in dimension $8$. There are $10916$ of them. Our classification heavily relies on exploiting symmetry in polyhedral computations. Here we describe algorithms making the classification possible.

M. M. Anzin, On the density of a lattice covering for $n=11$ and $n=14$, Tr. Mat. Inst. Steklova 239 (2002), no. Diskret. Geom. i Geom. Chisel, 20–51 (Russian, with Russian summary); English transl., Proc. Steklov Inst. Math. 4(239) (2002), 13–44. MR 1975133
A. Ash, D. Mumford, M. Rapoport, and Y. Tai, Smooth compactification of locally symmetric varieties, Math. Sci. Press, Brookline, Mass., 1975. Lie Groups: History, Frontiers and Applications, Vol. IV. MR 0457437

[Av93]lrs D. Avis, A C-implementation of the reverse search vertex enumeration algorithm, School of Computer Science, McGill University, Montreal, Canada 1993, http://www-cgrl.cs.mcgill.ca/˜avis/C/lrs.html.

M. L. Balinski, On the graph structure of convex polyhedra in $n$-space, Pacific J. Math. 11 (1961), 431–434. MR 126765

[Ba96]baril J-L. Baril, Autour de l’algorithme de Voronoi: Construction de réseaux Euclidiens, Thèse, Bordeaux (1996).

E. S. Barnes, The complete enumeration of extreme senary forms, Philos. Trans. Roy. Soc. London Ser. A 249 (1957), 461–506. MR 86833, DOI https://doi.org/10.1098/rsta.1957.0005

[BaMa05]batutmartinet C. Batut and J. Martinet, A catalogue of perfect lattices, http://www.math. u-bordeaux.fr/˜martinet/.

H. F. Blichfeldt, The minimum values of positive quadratic forms in six, seven and eight variables, Math. Z. 39 (1935), no. 1, 1–15. MR 1545485, DOI https://doi.org/10.1007/BF01201341
Gunnar Brinkmann, Isomorphism rejection in structure generation programs, Discrete mathematical chemistry (New Brunswick, NJ, 1998) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 51, Amer. Math. Soc., Providence, RI, 2000, pp. 25–38. MR 1762931
Clara S. Chan and David P. Robbins, On the volume of the polytope of doubly stochastic matrices, Experiment. Math. 8 (1999), no. 3, 291–300. MR 1724161

[ChLo97]porta T. Christof and A. Löbel, PORTA: Polyhedron representation transformation algorithm (ver 1.3.1), 1997, http://www.zib.de/Optimization/Software/Porta/.

T. Christof and G. Reinelt, Combinatorial optimization and small polytopes, Top 4 (1996), no. 1, 1–64. With discussion. MR 1404262, DOI https://doi.org/10.1007/BF02568602
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206

[CoKu04]cohn H. Cohn and A. Kumar, Optimality and uniqueness of the Leech lattice among lattices, http://www.arxiv.org/math.MG/0403263.

J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups, 3rd ed., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 290, Springer-Verlag, New York, 1999. With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov. MR 1662447
J. H. Conway and N. J. A. Sloane, Low-dimensional lattices. III. Perfect forms, Proc. Roy. Soc. London Ser. A 418 (1988), no. 1854, 43–80. MR 953277
H. S. M. Coxeter, Extreme forms, Canad. J. Math. 3 (1951), 391–441. MR 44580, DOI https://doi.org/10.4153/cjm-1951-045-8

[DeDu03]mining M. Deza and M. Dutour, Cones of metrics, hemi-metrics and super-metrics, Annals of the European Academy of Sciences (2003) 141–162.

Antoine Deza, Komei Fukuda, Dmitrii Pasechnik, and Masanori Sato, On the skeleton of the metric polytope, Discrete and computational geometry (Tokyo, 2000) Lecture Notes in Comput. Sci., vol. 2098, Springer, Berlin, 2001, pp. 125–136. MR 2043643, DOI https://doi.org/10.1007/3-540-47738-1_10

[Fu95]cdd K. Fukuda, cdd+ reference manual, Institute for operations research, Swiss Federal Institute of Technology, Zurich, Switzerland, 1995, http://www.ifor.math.ethz.ch/ ˜fukuda/cdd_home/cdd.html.

[Ga40]gauss C.F. Gauss, Untersuchungen über die Eigenschaften der positiven ternären quadratischen Formen von Ludwig August Seeber, J. Reine Angew. Math. 20 (1840) 312–320.

[GAP05]GAP The GAP Group, GAP — Groups, Algorithms, and Programming, Version 4.4.6; 2005. http://www.gap-system.org.

David-Olivier Jaquet-Chiffelle, Description des voisines de $E_7,\;D_7,\;D_8$ et $D_9$, Sém. Théor. Nombres Bordeaux (2) 4 (1992), no. 2, 273–377 (French, with English and French summaries). MR 1208866
David-Olivier Jaquet-Chiffelle, Énumération complète des classes de formes parfaites en dimension $7$, Ann. Inst. Fourier (Grenoble) 43 (1993), no. 1, 21–55 (French, with English and French summaries). MR 1209694
Volker Kaibel and Alexander Schwartz, On the complexity of polytope isomorphism problems, Graphs Combin. 19 (2003), no. 2, 215–230. MR 1996205, DOI https://doi.org/10.1007/s00373-002-0503-y
Adalbert Kerber, Applied finite group actions, 2nd ed., Algorithms and Combinatorics, vol. 19, Springer-Verlag, Berlin, 1999. MR 1716962
A. Korkine and G. Zolotareff, Sur les formes quadratiques positives quaternaires, Math. Ann. 5 (1872), no. 4, 581–583 (French). MR 1509795, DOI https://doi.org/10.1007/BF01442912
A. Korkine and G. Zolotareff, Sur les formes quadratiques, Math. Ann. 6 (1873), no. 3, 366–389 (French). MR 1509828, DOI https://doi.org/10.1007/BF01442795
A. Korkinge and G. Zolotareff, Sur les formes quadratiques positives, Math. Ann. 11 (1877), no. 2, 242–292 (French). MR 1509914, DOI https://doi.org/10.1007/BF01442667

[La73]lagrange J.L. Lagrange, Démonstration d’un théorème d’arithmétique, Nouv. Mém. Acad. Berlin (1770), in Oeuvres de Lagrange III, 189–201.

[La92]laihem M. Laïhem, Construction algorithmique des réseaux parfaits, Thèse, Bordeaux, 1992.

A. O. L. Atkin and B. J. Birch (eds.), Computers in number theory, Academic Press, London-New York, 1971. MR 0314733
Jacques Martinet, Perfect lattices in Euclidean spaces, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 327, Springer-Verlag, Berlin, 2003. MR 1957723

[Ma97]pd A. Marzetta, pd - C-implementation of the primal dual algorithm, 1997, http://www. cs.unb.ca/profs/bremner/pd/.

[MKa05]nauty B.D. McKay, The nauty program, http://cs.anu.edu.au/people/bdm/nauty/.

L. J. Mordell, Observation on the minimum of a positive quadratic form in eight variables, J. London Math. Soc. 19 (1944), 3–6. MR 10708, DOI https://doi.org/10.1112/jlms/19.73_Part_1.3

[Na96]napias H. Napias, Étude expérimentale et algorithmique des réseaux Euclidiens, Thèse, Bordeaux, 1996.

[PlOpSc98]carat W. Plesken, J. Opgenorth, and T. Schulz, CARAT—a package for mathematical crystallography, J. Appl. Cryst. 31 (1998) 827–828.

W. Plesken and B. Souvignier, Computing isometries of lattices, J. Symbolic Comput. 24 (1997), no. 3-4, 327–334. Computational algebra and number theory (London, 1993). MR 1484483, DOI https://doi.org/10.1006/jsco.1996.0130

[Ri06]riener C. Riener, On extreme forms in dimension $8$, to appear in J. Théorie des Nombres de Bordeaux, http://www.math.u-bordeaux.fr/˜martinet/riener4.pdf.

S. S. Ryškov, The polyhedron $\mu (m)$ and certain extremal problems of the geometry of numbers, Dokl. Akad. Nauk SSSR 194 (1970), 514–517 (Russian). MR 0276873
S. S. Ryškov and E. P. Baranovskiĭ, Classical methods of the theory of lattice packings, Uspekhi Mat. Nauk 34 (1979), no. 4(208), 3–63, 256 (Russian). MR 548416
Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
N. I. Shepherd-Barron, Perfect forms and the moduli space of abelian varieties, Invent. Math. 163 (2006), no. 1, 25–45. MR 2208417, DOI https://doi.org/10.1007/s00222-005-0453-0
C. Soulé, Perfect forms and the Vandiver conjecture, J. Reine Angew. Math. 517 (1999), 209–221. MR 1728540, DOI https://doi.org/10.1515/crll.1999.095
Garret Swart, Finding the convex hull facet by facet, J. Algorithms 6 (1985), no. 1, 17–48. MR 780849, DOI https://doi.org/10.1016/0196-6774%2885%2990017-3

[Va99]vallentinSV F. Vallentin, SHVEC, http://www.math.uni-magdeburg.de/lattice_geometry/.

N. M. Vetčinkin, Uniqueness of classes of positive quadratic forms, on which values of Hermite constants are reached for $6\leq n\leq 8$, Trudy Mat. Inst. Steklov. 152 (1980), 34–86, 237 (Russian). Geometry of positive quadratic forms. MR 603814

[Vo08]voronoi G. Voronoi, Nouvelles applications des paramètres continues à la théorie des formes quadratiques 1: Sur quelques propriétés des formes quadratiques positives parfaites, J. Reine Angew. Math 133 (1908) 97–178.

G. L. Watson, The number of minimum points of a positive quadratic form, Dissertationes Math. (Rozprawy Mat.) 84 (1971), 42. MR 318061
Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028
Chuanming Zong, Sphere packings, Universitext, Springer-Verlag, New York, 1999. MR 1707318