Inhomogeneous extreme forms

Dutour Sikirić, Mathieu; Schürmann, Achill; Vallentin, Frank

Annales de l'Institut Fourier, Tome 62 (2012) no. 6, pp. 2227-2255.

G.F. Voronoi (1868–1908) a écrit deux mémoires dans lesquels il décrit deux théories de réduction pour les réseaux, l’une adaptée aux empilements de sphères et l’autre aux recouvrements de sphères. Dans son premier mémoire une charactérisation des empilements de sphères qui sont localement les plus économiques est donnée. Dans cet article, nous relions ces deux mémoires classiques.

En considérant le problème sous un autre angle, nous faisons apparaître l’analogue manquant. Au lieu de considérer les réseaux donnant des recouvrements localement économiques, nous considérons les réseaux qui sont localement les moins économiques. Nous classifions ces réseaux jusqu’à la dimension 6 et nous prouvons leur existence dans les dimensions suivantes.

De nouveaux phénomènes apparaissent  : de nombreux réseaux de haute symétrie donnent des réseaux non économiques  ; la fonction de densité de recouvrement n’est pas une fonction topologique de Morse. Ces deux phénomènes sont en contraste frappant avec le cas des empilements de sphères.

G.F. Voronoi (1868–1908) wrote two memoirs in which he describes two reduction theories for lattices, well-suited for sphere packing and covering problems. In his first memoir a characterization of locally most economic packings is given, but a corresponding result for coverings has been missing. In this paper we bridge the two classical memoirs.

By looking at the covering problem from a different perspective, we discover the missing analogue. Instead of trying to find lattices giving economical coverings we consider lattices giving, at least locally, very uneconomical ones. We classify local covering maxima up to dimension $6$ and prove their existence in all dimensions beyond.

New phenomena arise: Many highly symmetric lattices turn out to give uneconomical coverings; the covering density function is not a topological Morse function. Both phenomena are in sharp contrast with the packing problem.

Classification : 11H55, 52C17
Keywords: lattices, Delone polytopes, spherical $t$-designs, sphere packing, sphere covering, Voronoi reduction theory
Mot clés : réseaux, polytopes de Delaunay, designs sphériques, empilements de sphères, recouvrements de sphères, théorie de réduction de Voroni

[1] Ash, Avner On eutactic forms, Canad. J. Math., Volume 29 (1977) no. 5, pp. 1040-1054 | MR | Zbl

[2] Barnes, E. S.; Dickson, T. J. Extreme coverings of $n$-space by spheres, J. Austral. Math. Soc., Volume 7 (1967), pp. 115-127 | MR | Zbl

[3] Bergé, Anne-Marie; Martinet, Jacques On weakly eutactic forms, J. Lond. Math. Soc. (2), Volume 75 (2007) no. 1, pp. 187-198 | DOI | MR | Zbl

[4] Blichfeldt, H. F. The minimum values of positive quadratic forms in six, seven and eight variables, Math. Z., Volume 39 (1935) no. 1, pp. 1-15 | DOI | MR | Zbl

[5] Boyd, Stephen; Vandenberghe, Lieven Convex optimization, Cambridge University Press, Cambridge, 2004 | MR | Zbl

[6] Cohn, Henry; Kumar, Abhinav Universally optimal distribution of points on spheres, J. Amer. Math. Soc., Volume 20 (2007) no. 1, pp. 99-148 | DOI | MR | Zbl

[7] Cohn, Henry; Kumar, Abhinav Optimality and uniqueness of the Leech lattice among lattices, Ann. of Math. (2), Volume 170 (2009) no. 3, pp. 1003-1050 | DOI | MR | Zbl

[8] Conway, John H.; Sloane, Neil J. A. The cell structures of certain lattices, Miscellanea mathematica, Springer, Berlin, 1991, pp. 71-107 | MR | Zbl

[9] Conway, John H.; Sloane, Neil J. A. Sphere packings, lattices and groups, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 290, Springer-Verlag, New York, 1999 (With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov) | MR | Zbl

[10] Coxeter, H. S. M. Regular polytopes, Dover Publications Inc., New York, 1973 | MR

[11] Delone, B.N.; Dolbilin, N.P.; Ryshkov, S.S.; Shtogrin, M.I. A new construction in the theory of lattice coverings of an n-dimensional space by equal spheres., Math. USSR, Izv., Volume 4 (1970), pp. 293-302 | DOI | Zbl

[12] Delsarte, P.; Goethals, J. M.; Seidel, J. J. Spherical codes and designs, Geometriae Dedicata, Volume 6 (1977) no. 3, pp. 363-388 | MR | Zbl

[13] Deza, Michel Marie; Laurent, Monique Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer-Verlag, Berlin, 1997 | MR | Zbl

[14] Dutour Sikirić, Mathieu Polyhedral package (http://www.liga.ens.fr/~dutour/polyhedral/)

[15] Dutour Sikirić, Mathieu The six-dimensional Delaunay polytopes, European J. Combin., Volume 25 (2004) no. 4, pp. 535-548 | DOI | MR | Zbl

[16] Dutour Sikirić, Mathieu Infinite series of extreme Delaunay polytope, European J. Combin., Volume 26 (2005), pp. 129-132 | MR | Zbl

[17] Dutour Sikirić, Mathieu; Erdahl, Robert; Rybnikov, Konstantin Perfect Delaunay polytopes in low dimensions, Integers, Volume 7 (2007), pp. A39, 49 | MR | Zbl

[18] Dutour Sikirić, Mathieu; Schürmann, Achill; Vallentin, Frank A generalization of Voronoi’s reduction theory and its application, Duke Math. J., Volume 142 (2008) no. 1, pp. 127-164 | MR | Zbl

[19] Dutour Sikirić, Mathieu; Schürmann, Achill; Vallentin, Frank Complexity and algorithms for computing Voronoi cells of lattices, Math. Comp., Volume 78 (2009) no. 267, pp. 1713-1731 | DOI | MR | Zbl

[20] Erdahl, Robert M. A cone of inhomogeneous second-order polynomials, Discrete Comput. Geom., Volume 8 (1992) no. 4, pp. 387-416 | DOI | MR | Zbl

[21] Erdahl, Robert M.; Rybnikov, Konstantin On Voronoi’s two tilings of the cone of metrical forms, Rend. Circ. Mat. Palermo (2) Suppl. (2002) no. 70, part I, pp. 279-296 IV International Conference in “Stochastic Geometry, Convex Bodies, Empirical Measures & Applications to Engineering Science”, Vol. I (Tropea, 2001) | MR | Zbl

[22] Erdahl, Robert M.; Ryshkov, S. S. The empty sphere, Canad. J. Math., Volume 39 (1987) no. 4, pp. 794-824 | DOI | MR | Zbl

[23] Lempken, Wolfgang; Schröder, Bernd; Tiep, Pham Huu Symmetric squares, spherical designs, and lattice minima, J. Algebra, Volume 240 (2001) no. 1, pp. 185-208 (With an appendix by Christine Bachoc and Tiep) | DOI | MR | Zbl

[24] Martinet, Jacques Perfect lattices in Euclidean spaces, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 327, Springer-Verlag, Berlin, 2003 | MR | Zbl

[25] McMullen, Curtis T. Minkowski’s conjecture, well-rounded lattices and topological dimension, J. Amer. Math. Soc., Volume 18 (2005) no. 3, p. 711-734 (electronic) | DOI | MR | Zbl

[26] Minkowski, H. Diskontinuitätsbereich arithmetischer Äquivalenz, J. Reine Angew. Math., Volume 129 (1905), pp. 220-274

[27] Morse, Marston Topologically non-degenerate functions on a compact $n$-manifold $M$., J. Analyse Math., Volume 7 (1959), pp. 189-208 | MR | Zbl

[28] Nebe, Gabriele; Venkov, Boris Low-dimensional strongly perfect lattices. I. The 12-dimensional case, Enseign. Math. (2), Volume 51 (2005) no. 1-2, pp. 129-163 | MR | Zbl

[29] Nottebaum, J. Sphärische 4-designs in Gittern, Universität Oldenburg, 1995

[30] Ryshkov, S. S.; Erdahl, R. M. The empty sphere. II, Canad. J. Math., Volume 40 (1988) no. 5, pp. 1058-1073 | DOI | MR | Zbl

[31] Schrijver, Alexander Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons Ltd., Chichester, 1986 (A Wiley-Interscience Publication) | MR | Zbl

[32] Schürmann, Achill Computational geometry of positive definite quadratic forms, University Lecture Series, 48, American Mathematical Society, Providence, RI, 2009 (Polyhedral reduction theories, algorithms, and applications) | MR | Zbl

[33] Schürmann, Achill; Vallentin, Frank Local covering optimality of lattices: Leech lattice versus root lattice $E_8$, Int. Math. Res. Not. (2005) no. 32, pp. 1937-1955 | DOI | MR | Zbl

[34] Schürmann, Achill; Vallentin, Frank Computational approaches to lattice packing and covering problems, Discrete Comput. Geom., Volume 35 (2006) no. 1, pp. 73-116 | DOI | MR | Zbl

[35] Štogrin, M. I. Locally quasidensest lattice packings of spheres, Dokl. Akad. Nauk SSSR, Volume 218 (1974), pp. 62-65 | MR | Zbl

[36] Vallentin, F. Sphere coverings, lattices, and tilings (in low dimensions), Center for Mathematical Sciences, Munich University of Technology (2003) (Ph. D. Thesis http://tumb1.biblio.tu-muenchen.de/publ/diss/ma/2003/vallentin.html)

[37] Venkov, B. B. Réseaux euclidean, designs sphériques, et formes modulaires, Monogr. Enseign. Math., Volume 37 (2001), p. 10-86. (Enseignement Math., Geneva) | MR | Zbl

[38] Vetčinkin, N. M. Uniqueness of classes of positive quadratic forms, on which values of Hermite constants are reached for $6\le n\le 8$, Trudy Mat. Inst. Steklov., Volume 152 (1980), p. 34-86, 237 (Geometry of positive quadratic forms) | MR | Zbl

[39] Voronoi, G. F. Nouvelles applications des paramètres continues à la théorie des formes quadratiques 1: Sur quelques propriétés des formes quadratiques positives parfaites, J. Reine Angew. Math., Volume 133 (1908), pp. 97-178

[40] Voronoi, G. F. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxiéme Mémoire. Recherches sur les parallélloedres primitifs, J. Reine Angew. Math., Volume 134 (1908), pp. 198-287 and 136 (1909), 67–181