Inhomogeneous extreme forms
Annales de l'Institut Fourier, Volume 62 (2012) no. 6, p. 2227-2255
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.
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.
DOI : https://doi.org/10.5802/aif.2748
Classification:  11H55,  52C17
Keywords: lattices, Delone polytopes, spherical t-designs, sphere packing, sphere covering, Voronoi reduction theory
@article{AIF_2012__62_6_2227_0,
     author = {Dutour Sikiri\'c, Mathieu and Sch\"urmann, Achill and Vallentin, Frank},
     title = {Inhomogeneous extreme forms},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {62},
     number = {6},
     year = {2012},
     pages = {2227-2255},
     doi = {10.5802/aif.2748},
     zbl = {pre06159911},
     mrnumber = {3060757},
     language = {en},
     url = {https://aif.centre-mersenne.org/item/AIF_2012__62_6_2227_0}
}
Dutour Sikirić, Mathieu; Schürmann, Achill; Vallentin, Frank. Inhomogeneous extreme forms. Annales de l'Institut Fourier, Volume 62 (2012) no. 6, pp. 2227-2255. doi : 10.5802/aif.2748. https://aif.centre-mersenne.org/item/AIF_2012__62_6_2227_0/

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

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

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

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

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

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

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

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

[9] Conway, John H.; Sloane, Neil J. A. Sphere packings, lattices and groups, Springer-Verlag, New York, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Tome 290 (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 1662447 | Zbl 0634.52002

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

[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., Tome 4 (1970), pp. 293-302 | Article | Zbl 0217.18601

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

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

[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., Tome 25 (2004) no. 4, pp. 535-548 | Article | MR 2069380 | Zbl 1046.52009

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

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

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

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

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

[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 1962573 | Zbl 1116.52006

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

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

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

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

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

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

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

[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., Tome 40 (1988) no. 5, pp. 1058-1073 | Article | MR 973509 | Zbl 0653.10027

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

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

[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 | Article | MR 2173600 | Zbl 1156.11324

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

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

[36] Vallentin, F. Sphere coverings, lattices, and tilings (in low dimensions), Center for Mathematical Sciences, Munich University of Technology (2003) (Ph. D. Thesis)

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

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

[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., Tome 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., Tome 134 (1908), pp. 198-287 (and 136 (1909), 67–181)