Geometry of Lattices and Algorithms

Activities

September 2010: Achill Schürmann and Thomas Rehn move to Rostock. (This webpage is no longer maintained.)

June 2010: Release of preliminary versions of new C++ tools PermLib and SymPol for work with symmetric polyhedra. Talks on these tools are given at the Oberwolfach Mini-Workshop on Exploiting Symmetry in Optimization and at the International Congress of Mathematical Software (ICMS) 2010.

May 2009: We meet with Mathieu Dutour Sikiric in Oberwolfach for Research in Pairs.

January 2009: Book on Computational Geometry of Positive Definite Quadratic Forms appears in the AMS University Lecture Series.

February - April 2008: We take part in the HIM Junior Trimester Program on Computational Mathematics, focusing on Extreme Geometric Structures. In two workshops on ''Linear and semidefinite programming bounds'' (February 26 - February 29) and ''Experimentation with, construction of, and and enumeration of optimal geometric structures'' (March 25 - March 28) we will address the basic tasks of finding constructions of extreme geometric structures and finding obstructions for their existence.

Computational Highlights

With Mathieu Dutour Sikiric the classification of perfect forms (lattices) in dimension 8 was completed on 4th October 2005. There are no more than the 10916 forms found before (see Jacques Martinet's homepage). The file perfect-forms-dim8.txt contains a complete list in human readable format, together with their contiguities. We will report on this in our paper Classification of eight dimensional perfect forms. In dimension 9 we found more than 500000 perfect forms (see the compressed file perfect-forms-dim9.txt.gz). We believe there are many many more... :-(

With Mathieu Dutour Sikiric we found new best known sphere coverings in dimension 9, 10, 11, 12, 13, 14, 15, 17, 19, 20, 21. See our updated table of best known sphere coverings. We also found new best known sphere packing-coverings. See our paper "A Generalization of Voronoi's Reduction Theory and Applications" and our paper "Complexity and algorithms for computing Voronoi cells of lattices".

Description

Lattices (and more general periodic point sets) are ubiquitous objects in mathematics and in its applications. Frequently, lattices are used as discrete models for more complicated geometric spaces. It is important that the lattice is chosen in a way that it approximates the space as good as possible. In our research project we want to understand the interplay between lattices and their surrounding spaces. Central object of our studies is the Euclidean space and the search for new optimal lattices for diverse geometric questions, such as classical sphere packing and covering problems.

Many of these problems can be formulated as optimization problems having a combinatorial and geometrical flavour. By using appropriate algorithms and software they can be solved in this framework. It turns out that special polyhedral subdivisions (Voronoi and Delone subdivisions) of the surrounding space which are induced by the considered periodic point sets play an important role.

Publications

Abstract C++ Tools for Exploiting Polyhedral Symmetries (Thomas Rehn and Achill Schürmann), in Mathematical Software -- ICMS 2010, Springer LNCS 6327 (2010), 295-298

Abstract PS PDF Ground states and formal duality relations in the Gaussian core model (Henry Cohn, Abhinav Kumar and Achill Schürmann), Phys. Rev. E 80, 061116 (2009)

Abstract PS PDF The contact polytope of the Leech lattice (Achill Schürmann, Frank Vallentin, Mathieu Dutour Sikiric), Discr. Comp. Geom., 44 (2010), 904-911

Abstract PS PDF On classifying Minkowskian sublattices (Wolfgang Keller, Jacques Martinet and Achill Schürmann), submitted

Abstract PS PDF High accuracy semidefinite programming bounds for kissing numbers (Hans Mittelmann, Frank Vallentin), Experiment. Math. 19 (2010), 174-178

Abstract PS PDF Point configurations that are asymmetric yet balanced (Henry Cohn, Noam Elkies, Abhinav Kumar and Achill Schürmann), Proc. Amer. Math. Soc., 138 (2010), 2863-2872

Abstract PS PDF Enumerating perfect forms (Achill Schürmann), AMS Contemporary Mathematics, 437 (2009), 359-378

Computational Geometry of Positive Definite Quadratic Forms (Achill Schürmann), AMS University Lecture Series, 2009.

Abstract PS PDF Lecture notes: Semidefinite programs and harmonic analysis (Frank Vallentin), Workshop HPOPT 2008 - 10th International Workshop on High Performance Optimization Techniques (Algebraic Structure in Semidefinite Programming), June 11th to 13th, 2008, Tilburg University, The Netherlands.

Abstract PS PDF Perfect, strongly eutactic lattices are periodic extreme (Achill Schürmann), Advances in Mathematics, 225 (2010), 2546-2564

Abstract PS PDF Fourier analysis, linear programming, and densities of distance avoiding sets in R^n (Fernando Mario de Oliveira Filho, Frank Vallentin), J. Eur. Math. Soc. 12 (2010), 1417-1428

Abstract PS PDF Complexity and algorithms for computing Voronoi cells of lattices (Achill Schürmann, Frank Vallentin, Mathieu Dutour Sikiric), Math. Comp. 267 (2009), 1713-1731

Abstract PS PDF Lower bounds for measurable chromatic numbers (Christine Bachoc, Gabriele Nebe, Fernando Mario de Oliveira Filho, Frank Vallentin), Geom. Funct. Anal. 19 (2009), 645-661

Abstract PS PDF Block-diagonal semidefinite programming hierarchies for 0/1 programming (Nebojsa Gvozdenovic, Monique Laurent, Frank Vallentin), Oper. Res. Lett., 37 (2009), 27-31

Abstract PS PDF The isodiametric problem with lattice-point constraints (Maria Hernandez Cifre, Achill Schürmann, Frank Vallentin), Monatsh. Math. 155 (2008), 125-134.

Abstract PS PDF Optimality and uniqueness of the (4,10,1/6) spherical code (Christine Bachoc, Frank Vallentin), J. Comb. Theory Ser. A 116 (2009), 195-204

Abstract PS PDF Symmetry in semidefinite programs (Frank Vallentin), Linear Algebra and Appl. 430 (2009), 360-369

Abstract PS PDF Polyhedral representation conversion up to symmetries (David Bremner, Achill Schürmann and Mathieu Dutour Sikiric), in Proceedings of the 2006 CRM workshop on polyhedral computation, AMS/CRM Lecture Notes 48 (2009), 45-71

Abstract PS PDF Experimental study of energy-minimizing point configurations on spheres (Brandon Ballinger, Grigoriy Blekherman, Henry Cohn, Noah Giansiracusa, Elizabeth Kelly and Achill Schürmann), Experiment. Math. 18 (2009), 257-283

Abstract PS PDF Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps (Christine Bachoc, Frank Vallentin), Europ. J. Comb. 30 (2009), 625-637

Abstract PS PDF Classification of eight dimensional perfect forms (Achill Schürmann, Frank Vallentin, Mathieu Dutour Sikiric), Electron. Res. Announc. Amer. Math. Soc., 13 (2007), 21-32

Abstract PS PDF New upper bounds for kissing numbers from semidefinite programming (Christine Bachoc, Frank Vallentin), J. Amer. Math. Soc. 21 (2008), 909-924.

Abstract PS PDF A generalization of Voronoi's reduction theory and its application (Achill Schürmann, Frank Vallentin, Mathieu Dutour Sikiric), Duke Math. J. 142 (2008), 127-164.

Abstract PS PDF Optimal Embeddings of Distance Regular Graphs into Euclidean Spaces (Frank Vallentin), J. Comb. Theory Ser. B (2008), 95-104.

Abstract PS PDF Lattice Delone simplices with super-exponential volume (Francisco Santos, Achill Schürmann, Frank Vallentin), European J. Combin, 28 (2007), 801-806

Abstract PS PDF Methods in the Local Theory of Packing and Covering Lattices (Achill Schürmann, Frank Vallentin), Proceedings of "COE Workshop on Sphere Packings", Fukuoka, Japan, 2004.

Abstract PS PDF Local Covering Optimality of Lattices: Leech Lattice versus Root Lattice E8 (Achill Schürmann, Frank Vallentin), Int. Math. Res. Notices 32 (2005), 1937-1955.

Abstract PS PDF Computational Approaches to Lattice Packing and Covering Problems (Achill Schürmann, Frank Vallentin) Discr. Comp. Geom. 35 (2006), 73-116.

Abstract PS PDF Some six-dimensional rigid forms (Mathieu Dutour, Frank Vallentin), pages 102-108 in Voronoi's Impact on Modern Science, Book 3 (H. Syta, A. Yurachivsky, P. Engel eds.; Institute of Math., Kyiv 2005 = Vol.55 of Proc. Inst. Math. Nat. Acad. Sci. Ukraine).

Abstract PDF Sphere Coverings, Lattices, and Tilings (in Low Dimensions) (Frank Vallentin) Ph.D. thesis, Technische Universität München, 2003.

Tables

Best known lattice coverings in dimension 1--24
Best known lattice packing-coverings in dimension 1--8

For more lattices see the Catalogue of Lattices by Gabriele Nebe and Neil J. A. Sloane

Software

All our software is free software. It may be used according to the GNU General Public License

PermLib

SymPol

RMD: rigorous maxdet

SCC: secondary cone cruiser

SHVEC: shortest and closest vectors in lattices

Related Work

For more on perfect forms and many more see the homepage of Jacques Martinet .

rmd was recently used in a very interesting project on New Korkine-Zolotarev Inequalities by Stefan van Zwam and Rudi Pendavingh.

Collaborators

Student collaborators

Thanks to the support by the Deutsche Forschungsgemeinschaft (DFG) it was possible to involve students into our research.

Contact

If you found anything on this page interesting, tried to read a paper, failed or succeeded to install our software, have additions, remarks, comments, etc. please feel free to contact us.

Acknowledgements

We like to thank the Deutsche Forschungsgemeinschaft (DFG) who kindly supported our research under grant SCHU 1503/4. We like to thank David Avis, Stephen Boyd, Victor Shoup, Lieven Vandenberghe, Clive Wu for their software packages lrs, MAXDET, and NTL which we extensively use. And last but not least we like to thank Mathieu Dutour Sikiric for his many contributions to this project.