×

Another 80-dimensional extremal lattice. (English. French summary) Zbl 1285.11099

Summary: We show that the unimodular lattice associated to the rank 20 quaternionic matrix group \(\mathrm{SL}_2(\mathbb F_41) \otimes\tilde S_3 \subset \mathrm{SL}_{80}(\mathbb Z)\) 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 (the first two by C. Bachoc and G. Nebe [J. Reine Angew. Math. 494, 155–171 (1998; Zbl 0885.11043)] and the third one by D. Stehlé and the author [ANTS-IX, Lect. Notes Comput. Sci. 6197, 340–356 (2010; Zbl 1260.11048)]), 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 G. Nebe [J. Algebra 199, No. 2, 472–498 (1998; Zbl 0897.11022)], this fourth lattice has an additional 2-extension in its automorphism group.

MSC:

11H55 Quadratic forms (reduction theory, extreme forms, etc.)
11H56 Automorphism groups of lattices
20G35 Linear algebraic groups over adèles and other rings and schemes

Software:

Magma
PDFBibTeX XMLCite
Full Text: DOI Numdam

References:

[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 · Zbl 0537.20023
[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 · Zbl 0885.11043
[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. · Zbl 1061.11035
[5] C. Batut, H.-G. Quebbemann, R. Scharlau, Computations of cyclotomic lattices. Experiment. Math. 4 (1995), no. 3, 177-179. Available from · Zbl 0873.11026
[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 · Zbl 0898.68039
[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. · Zbl 0634.52002
[8] R. Coulangeon, Tensor products of Hermitian lattices. Acta Arith. XCII, no. 2 (2000), 115-130. Online at · Zbl 0951.11023
[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
[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 · Zbl 1285.94056
[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 · Zbl 0541.12001
[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 · Zbl 1280.94056
[13] M. Harada, M. Kitazume, M. Ozeki, Ternary Code Construction of Unimodular Lattices and Self-Dual Codes over \({\bf Z}_6\). J. Alg. Combin. 16, no. 2 (2002), 209-223. Online from · Zbl 1027.94022
[14] M. Hentschel, On Hermitian theta series and modular forms. Dissertation, RWTH Aachen University 2009. Online at
[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 and · Zbl 0979.20012
[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
[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. · Zbl 0697.20004
[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 · Zbl 0488.12001
[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 · Zbl 1053.20008
[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 · Zbl 0311.94002
[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 · JFM 19.0189.01
[22] G. Nebe, Some cyclo-quaternionic lattices. J. Algebra 199 (1998), no. 2, 472-498. Available from · Zbl 0897.11022
[23] G. Nebe, Finite quaternionic matrix groups. Represent. Theory 2 (1998), 106-223. Online at · Zbl 0901.20035
[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. · Zbl 0970.11025
[25] G. Nebe, An even unimodular 72-dimensional lattice of minimum 8. Preprint, 2010. · Zbl 1270.11066
[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. · Zbl 0686.10025
[27] M. Peters, Siegel theta series of degree \(2\) of extremal lattices. J. Number Theory 35 (1990), no. 1, 58-61. Available from · Zbl 0701.11015
[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 · Zbl 0882.11042
[29] X. Pujol, LatEnum 0.3, implementation of parallel enumeration code. Online at
[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 · Zbl 1206.94086
[31] H.-G. Quebbemann, A construction of integral lattices. Mathematika 31 (1984), 137-140. Online at · Zbl 0538.10028
[32] C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53 (1987), 201-224. See · Zbl 0642.10030
[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 · Zbl 0829.90099
[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 · Zbl 1260.11048
[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. · Zbl 1139.11320
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.