Another 80-dimensional extremal lattice

Watkins, Mark

Journal de théorie des nombres de Bordeaux, Tome 24 (2012) no. 1, pp. 237-255.

Nous montrons que le réseau unimodulaire associé au groupe de matrices quaternioniques ${\mathbf{SL}}_2\left({\mathbf{F}}_{41}\right)\otimes {\tilde{S}}_3\subset {\mathbf{GL}}_{80}\left(\mathbf{Z}\right)$ de rang $20$ donne un quatrième exemple d’un réseau extrémal en dimension $80$. Notre méthode utilise la positivié de la série $\Theta$ ainsi que l’énumération des vecteurs de norme $10$. L’utilisation du théorème d’Aschbacher sur les sous-groupes de groupes finis classiques (qui dépend de la classification des groupes finis simples) permet de démontrer que ce réseau est différent des trois précédents. Une autre méthode est de calculer la distribution du produit scalaire des vecteurs minimaux. Cette dernière méthode nous permet également de déterminer complètement le groupe des automorphismes de ces quatre réseaux. Comme cela a déjà été noté par Nebe, ce quatrième réseau possède une $2$-extension supplémentaire de son groupe d’automorphismes.

We show that the unimodular lattice associated to the rank 20 quaternionic matrix group ${\mathbf{SL}}_2\left({\mathbf{F}}_{41}\right)\otimes {\tilde{S}}_3\subset {\mathbf{GL}}_{80}\left(\mathbf{Z}\right)$ is a fourth example of an 80-dimensional extremal lattice. Our method is to use the positivity of the $\Theta$-series in conjunction with an enumeration of all the norm 10 vectors. The use of Aschbacher’s theorem on subgroups of finite classical groups (reliant on the classification of finite simple groups) provides one proof that this lattice is distinct from the previous three, while computing the inner product distribution of the minimal vectors is an alternative method. We give details of the latter, and this method also enables us to find the full automorphism group for each of the four lattices. As already noted by Nebe, this fourth lattice has an additional 2-extension in its automorphism group.

[1] Z. Abel, N. D. Elkies, S. D. Kominers, On 72-dimensional lattices, in preparation.

[2] M. Aschbacher, On the maximal subgroups of the finite classical groups. Invent. Math. 76 (1984), no. 3, 469–514. Available from | DOI | MR | Zbl

[3] C. Bachoc, G. Nebe, Extremal lattices of minimum 8 related to the Mathieu group $M_{22}$. J. Reine Angew. Math. 494 (1998), 155–171. Available from | DOI | MR | Zbl

[4] C. Bachoc, B. Venkov, Modular forms, lattices and spherical designs. In Réseaux euclidiens, designs sphériques et formes modulaires. Autour des travaux de Boris Venkov. Edited by J. Martinet, Monogr. Enseign. Math., 37, Enseignement Math., Geneva (2001), 87–111. | MR

[5] C. Batut, H.-G. Quebbemann, R. Scharlau, Computations of cyclotomic lattices. Experiment. Math. 4 (1995), no. 3, 177–179. Available from http://www.expmath.org/restricted/4/4.3/batut.ps | MR | Zbl

[6] W. Bosma, J. Cannon, C. Playoust, The Magma algebra system. I. The user language. In Computational algebra and number theory, Proceedings of the 1st Magma Conference (London 1993). Edited by J. Cannon and D. Holt, Elsevier Science B.V., Amsterdam (1997), 235–265. Cross-referenced as J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Available from http://magma.maths.usyd.edu.au | MR | Zbl

[7] J. H. Conway, N. J. A. Sloane, Sphere packings, lattices and groups. With contributions by E. Bannai, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 290. Springer-Verlag, New York, 1988. xxviii+663pp. | MR | Zbl

[8] R. Coulangeon, Tensor products of Hermitian lattices. Acta Arith. XCII, no. 2 (2000), 115–130. Online at http://matwbn.icm.edu.pl/ksiazki/aa/aa92/aa9224.pdf | MR

[9] Ö. Dagdelen, M. Schneider, Parallel Enumeration of Shortest Lattice Vector. In Proceedings of EURO-PAR 2010 (Ischia 2010), Part II. Edited by P. D‘Ambra, M. R. Guarracino, and D. Talia, Lecture Notes in Computer Science 6272, Springer (2010), 211–222. Available from | DOI

[10] J. Detrey, G. Hanrot, X. Pujol, D. Stehlé, Accelerating Lattice Reduction with FPGAs. In Progress in Cryptology - LATINCRYPT 2010, Proceedings of the First International Conference on Cryptology and Information Security in Latin America (Puebla 2010). Edited by M. Abdalla and P. S. L. M. Barretto, Lecture Notes in Computer Science 6212, Springer (2010), 124–143. Available from | DOI | MR

[11] U. Fincke, M. Pohst, A procedure for determining algebraic integers of given norm. In Computer Algebra (London 1983), Proceedings of the European computer algebra conference (EUROCAL). Edited by J. A. van Hulzen, Lecture Notes in Computer Science 162, Springer-Verlag, Berlin (1983), 194–202. Online at | DOI | MR | Zbl

[12] N. Gama, P. Q. Nguyen, O. Regev, Lattice Enumeration Using Extreme Pruning. In Advances in Cryptology - EUROCRYPT 2010, Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques (French Riviera 2010). Edited by H. Gilbert, Lecture Notes in Computer Science 6110, Springer (2010), 257–278. Online at | DOI | MR

[13] M. Harada, M. Kitazume, M. Ozeki, Ternary Code Construction of Unimodular Lattices and Self-Dual Codes over ${\mathbf{Z}}_6$. J. Alg. Combin. 16, no. 2 (2002), 209–223. Online from | DOI | MR

[14] M. Hentschel, On Hermitian theta series and modular forms. Dissertation, RWTH Aachen University 2009. Online at http://darwin.bth.rwth-aachen.de/opus3/volltexte/2009/ 2903/pdf/Hentschel_Michael.pdf

[15] G. Hiss and G. Malle, Low-dimensional representations of quasi-simple groups. LMS J. Comput. Math. 4 (2001), 22–63. Corrigenda: LMS J. Comput. Math. 5 (2002), 95–126. See http://www.lms.ac.uk/jcm/4/lms2000-014/sub/lms2000-014.pdf and http://www.lms.ac.uk/jcm/5/lms2002-025/sub/lms2002-025.pdf | MR

[16] R. Kannan, Improved algorithms for integer programming and related lattice problems. In Proceedings of the fifteenth annual ACM symposium on the Theory of computing (Boston MA, STOC 1983), 99–108, ACM order #508830. Available from http://doi.acm.org/10.1145/800061.808749

[17] P. B. Kleidman, M. W. Liebeck, The subgroup structure of the finite classical groups. London Mathematical Society Lecture Note Series, 129. Cambridge University Press, Cambridge, 1990. x+303 pp. | MR | Zbl

[18] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász, Factoring polynomial with rational coefficients. Math. Ann. 261, no. 4 (1982), 515–534. See | DOI | MR | Zbl

[19] F. Lübeck, Small degree representation of finite Chevalley groups in defining characteristic. LMS Journal of Computation and Mathematics 4 (2001), 135–169. Available from | DOI | MR

[20] C. L. Mallows, A. M. Odlyzko, N. J. A. Sloane, Upper bounds for modular forms, lattices, and codes. J. Algebra 36 (1975), no. 1, 68–76. Available from | DOI | MR | Zbl

[21] H. Minkowski, Zur Theorie der positiven quadratischen Formen. (German) [On the Theory of positive quadratic Forms]. J. reine angew. Math. 101 (1887), 196–202. See http://resolver.sub.uni-goettingen.de/purl?GDZPPN002160390

[22] G. Nebe, Some cyclo-quaternionic lattices. J. Algebra 199 (1998), no. 2, 472–498. Available from | DOI | MR | Zbl

[23] G. Nebe, Finite quaternionic matrix groups. Represent. Theory 2 (1998), 106–223. Online at http://www.ams.org/ert/1998-002-05/S1088-4165-98-00011-9 | MR | Zbl

[24] G. Nebe, Construction and investigation of lattices with matrix groups. In Integral quadratic forms and lattices, Proceedings of the International Conference on Integral Quadratic Forms and Lattices (Seoul 1998). Edited by M.-H. Kim, J. S. Hsia, Y. Kitaoka, and R. Schulze-Pillot, Contemp. Math. 249, Amer. Math. Soc., Providence, RI (1999), 205–219. | MR | Zbl

[25] G. Nebe, An even unimodular 72-dimensional lattice of minimum 8. Preprint, 2010.

[26] M. Ozeki, Ternary code construction of even unimodular lattices. In Théorie des nombres [Number theory]. Proceedings of the International Conference at the Université Laval (Quebec 1987). Edited by J.-M. De Koninck and C. Levesque, de Gruyter (1989), 772–784. | MR | Zbl

[27] M. Peters, Siegel theta series of degree $2$ of extremal lattices. J. Number Theory 35 (1990), no. 1, 58–61. Available from | DOI | MR | Zbl

[28] W. Plesken, B. Souvignier, Computing isometries of lattices. In Computational algebra and number theory, Proceedings of the 1st Magma Conference (London 1993). Edited by J. Cannon and D. Holt, Elsevier Science B.V., Amsterdam (1997), 327–334. Cross-referenced as J. Symbolic Comput. 24 (1997), no. 3-4, 327–334. Available from | DOI | MR | Zbl

[29] X. Pujol, LatEnum 0.3, implementation of parallel enumeration code. Online at http://perso.ens-lyon.fr/xavier.pujol/latenum/latenum-0.3.tar.gz

[30] X. Pujol, D. Stehlé, Rigorous and Efficient Short Lattice Vectors Enumeration. In Advances in Cryptology - ASIACRYPT 2008. Proceedings of the 14th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Melbourne 2008). Edited by J. Perprzyk, Lecture Notes in Computer Science 5350, Springer (2008), 390–405. Online at | DOI | MR

[31] H.-G. Quebbemann, A construction of integral lattices. Mathematika 31 (1984), 137–140. Online at | DOI | MR | Zbl

[32] C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53 (1987), 201–224. See | DOI | MR | Zbl

[33] C. P. Schnorr and M. Euchner, Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems. Math. Program. 66 (1994), 181–191. Available from | DOI | MR | Zbl

[34] D. Stehlé, M. Watkins, On the Extremality of an 80-Dimensional Lattice. In Algorithmic Number Theory, Ninth International Symposium, ANTS-IX (Nancy 2010). Edited by G. Hanrot, F. Morain, and E. Thomé, Lecture Notes in Computer Science 6197, Springer (2010), 340–356. Available from | DOI | MR

[35] B. Venkov, Réseaux et designs sphériques. (French) [Lattices and spherical designs]. In Réseaux euclidiens, designs sphériques et formes modulaires. Autour des travaux de Boris Venkov. Edited by J. Martinet, Monogr. Enseign. Math., 37, Enseignement Math., Geneva (2001), 10–86. | MR