Another 80-dimensional extremal lattice

Mark Watkins[1]

  • [1] Magma Computer Algebra Group Department of Mathematics, Carslaw Building University of Sydney, NSW 2006 AUSTRALIA

Journal de Théorie des Nombres de Bordeaux (2012)

  • Volume: 24, Issue: 1, page 237-255
  • ISSN: 1246-7405

Abstract

top
We show that the unimodular lattice associated to the rank 20 quaternionic matrix group SL 2 ( F 41 ) ⊗ S ˜ 3 ⊂ GL 80 ( Z ) is a fourth example of an 80-dimensional extremal lattice. Our method is to use the positivity of the Θ -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.

How to cite

top

Watkins, Mark. "Another 80-dimensional extremal lattice." Journal de Théorie des Nombres de Bordeaux 24.1 (2012): 237-255. <http://eudml.org/doc/251061>.

@article{Watkins2012,
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.},
affiliation = {Magma Computer Algebra Group Department of Mathematics, Carslaw Building University of Sydney, NSW 2006 AUSTRALIA},
author = {Watkins, Mark},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {unimodular lattice; rank 20 quaternionic matrix group; full automorphism group},
language = {eng},
month = {3},
number = {1},
pages = {237-255},
publisher = {Société Arithmétique de Bordeaux},
title = {Another 80-dimensional extremal lattice},
url = {http://eudml.org/doc/251061},
volume = {24},
year = {2012},
}

TY - JOUR
AU - Watkins, Mark
TI - Another 80-dimensional extremal lattice
JO - Journal de Théorie des Nombres de Bordeaux
DA - 2012/3//
PB - Société Arithmétique de Bordeaux
VL - 24
IS - 1
SP - 237
EP - 255
AB - 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.
LA - eng
KW - unimodular lattice; rank 20 quaternionic matrix group; full automorphism group
UR - http://eudml.org/doc/251061
ER -

References

top
  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 Zbl0537.20023MR746539
  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 Zbl0885.11043MR1604480
  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. Zbl1061.11035MR1878746
  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 Zbl0873.11026MR1387475
  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 Zbl0898.68039MR1484478
  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. Zbl0634.52002MR920369
  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 Zbl0951.11023MR1750312
  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 Zbl1285.94056MR2766433
  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 Zbl0541.12001MR774811
  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 Zbl1280.94056MR2660492
  13. M. Harada, M. Kitazume, M. Ozeki, Ternary Code Construction of Unimodular Lattices and Self-Dual Codes over  Z 6 . J. Alg. Combin. 16, no. 2 (2002), 209–223. Online from http://dx.doi.org/10.1023/A:1021185314365 Zbl1027.94022MR1943589
  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 Zbl0979.20012MR1835851
  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. Zbl0697.20004MR1057341
  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 Zbl0488.12001MR682664
  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 Zbl1053.20008MR1901354
  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 Zbl0311.94002MR376536
  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 http://dx.doi.org/10.1006/jabr.1997.7163 Zbl0897.11022MR1489922
  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 Zbl0901.20035MR1615333
  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. Zbl0970.11025MR1732361
  25. G. Nebe, An even unimodular 72-dimensional lattice of minimum 8. Preprint, 2010. Zbl1270.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. Zbl0686.10025MR1024602
  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 Zbl0701.11015MR1054558
  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 Zbl0882.11042MR1484483
  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 Zbl1206.94086MR2546107
  31. H.-G. Quebbemann, A construction of integral lattices. Mathematika 31 (1984), 137–140. Online at http://dx.doi.org/10.1112/S0025579300010731 Zbl0538.10028MR762185
  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 Zbl0642.10030MR918090
  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 Zbl0829.90099MR1297061
  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 Zbl1260.11048MR2721431
  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. MR1878745

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.