staple
With cedram.org

Search the site

Table of contents for this issue | Previous article
Mark Watkins
Another 80-dimensional extremal lattice
Journal de théorie des nombres de Bordeaux, 24 no. 1 (2012), p. 237-255, doi: 10.5802/jtnb.795
Article PDF | Reviews MR 2914908 | Zbl pre06075029

Résumé - Abstract

We show that the unimodular lattice associated to the rank 20 quaternionic matrix group ${\bf SL}_2({\bf F}_{41})\otimes \tilde{S}_3\subset {\bf GL}_{80}({\bf 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, 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.

Bibliography

[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 http://dx.doi.org/10.1007/BF01388470  MR 746539 |  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 http://dx.doi.org/10.1515/crll.1998.004  MR 1604480 |  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.  MR 1878746
[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 1387475 |  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 http://magma.maths.usyd.edu.au  MR 1484478 |  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.  MR 920369 |  Zbl 0634.52002
[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 1750312
[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 http://dx.doi.org/10.1007/978-3-642-15291-7_21
[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 http://dx.doi.org/10.1007/978-3-642-14712-8_8  MR 2766433
[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 http://dx.doi.org/10.1007/3-540-12868-9_103  MR 774811 |  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 http://dx.doi.org/10.1007/978-3-642-13190-5_13  MR 2660492
[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 http://dx.doi.org/10.1023/A:1021185314365  MR 1943589
[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 1835851
[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 1057341 |  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 http://dx.doi.org/10.1007/2FBF01457454  MR 682664 |  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 http://dx.doi.org/10.1112/S1461157000000838  MR 1901354
[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 http://dx.doi.org/10.1016/0021-8693(75)90155-6  MR 376536 |  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 http://resolver.sub.uni-goettingen.de/purl?GDZPPN002160390  JFM 19.0189.01
[22] G. Nebe, Some cyclo-quaternionic lattices. J. Algebra 199 (1998), no. 2, 472–498. Available from http://dx.doi.org/10.1006/jabr.1997.7163  MR 1489922 |  Zbl 0897.11022
[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 1615333 |  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.  MR 1732361 |  Zbl 0970.11025
[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 1024602 |  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 http://dx.doi.org/10.1016/0022-314X(90)90103-X  MR 1054558 |  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 http://dx.doi.org/10.1006/jsco.1996.0130  MR 1484483 |  Zbl 0882.11042
[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 http://dx.doi.org/10.1007/978-3-540-89255-7_24  MR 2546107
[31] H.-G. Quebbemann, A construction of integral lattices. Mathematika 31 (1984), 137–140. Online at http://dx.doi.org/10.1112/S0025579300010731  MR 762185 |  Zbl 0538.10028
[32] C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53 (1987), 201–224. See http://dx.doi.org/10.1016/0304-3975(87)90064-8  MR 918090 |  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 http://dx.doi.org/10.1007/BF01581144  MR 1297061 |  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 http://dx.doi.org/10.1007/978-3-642-14518-6_27  MR 2721431
[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 1878745