Lattice packing and covering of convex bodies

Peter M. Gruber

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Classical and modern mathematics in the wake of Boris Nikolaevich Delone, Tome 275 (2011), pp. 240-249.

Résumé

The aim of this article is twofold. First, to indicate briefly major problems and developments dealing with lattice packings and coverings of balls and convex bodies. Second, to survey more recent results on uniqueness of lattice packings and coverings of extreme density, on characterization of local minima and maxima of the density and on estimates of the kissing number. Emphasis is on results in general dimensions.

Bibliographie

[1] Ball K., “A lower bound for the optimal density of lattice packings”, Intern. Math. Res. Not., 1992, no. 10, 217–221 | DOI | MR | Zbl

[2] Bambah R.P., “On lattice coverings by spheres”, Proc. Nat. Inst. Sci. India., 20 (1954), 25–52 | MR | Zbl

[3] Barnes E.S., “On a theorem of Voronoĭ”, Proc. Cambridge Philos. Soc., 53 (1957), 537–539 | DOI | MR | Zbl

[4] Barnes E.S., Dickson T.J., “Extreme coverings of $n$-space by spheres”, J. Aust. Math. Soc., 7 (1967), 115–127 | DOI | MR | Zbl

[5] Bergé A.-M., Martinet J., “Sur un problème de dualité lié aux sphères en géométrie des nombres”, J. Number Theory., 32 (1989), 14–42 | DOI | MR | Zbl

[6] Bergé A.-M., Martinet J., “Sur la classification des réseaux eutactiques”, J. London Math. Soc. Ser. 2., 53 (1996), 417–432 | DOI | MR | Zbl

[7] Betke U., Henk M., “Densest lattice packings of 3-polytopes”, Comput. Geom., 16 (2000), 157–186 | DOI | MR | Zbl

[8] Blichfeldt H.F., “The minimum value of quadratic forms, and the closest packing of spheres”, Math. Ann., 101 (1929), 605–608 | DOI | MR | Zbl

[9] Blichfeldt H.F., “The minimum value of positive quadratic forms in six, seven and eight variables”, Math. Ztschr., 39 (1934), 1–15 | DOI | MR | Zbl

[10] Cohn H., Kumar A., “The densest lattice in twenty-four dimensions”, Electron. Res. Announc. Amer. Math. Soc., 10 (2004), 58–67 | DOI | MR | Zbl

[11] Conway J.H., Sloane N.J.A., Sphere packings, lattices and groups. 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, Grundl. math. Wissensch., 290, 3rd ed., Springer, New York, 1999 | DOI | MR | Zbl

[12] Coulangeon R., “Spherical designs and zeta functions of lattices”, Intern. Math. Res. Not., 2006, no. 25, 49620 | MR | Zbl

[13] Delaunay B., “Sur la sphère vide”, Proc. Intern. Math. Congr., Toronto, 1924, V. 1, Univ. Toronto Press, Toronto, 1928, 695–700

[14] Delone B.N., Dolbilin N.P., Ryškov S.S., Štogrin M.I., “A new construction in the theory of lattice coverings of an $n$-dimensional space by equal spheres”, Math. USSR. Izv., 4:2 (1970), 293–302 | DOI | MR | Zbl | Zbl

[15] Delone B.N., Ryshkov S.S., “Solution of the problem of the least dense lattice covering of a four-dimensional space by equal spheres”, Sov. Math. Dokl. 1964, 4, 1333–1334 | MR | Zbl

[16] Delone B.N., Ryshkov S.S., “A contribution to the theory of the extrema of a multidimensional $\zeta $-function”, Sov. Math. Dokl., 8 (1967), 499–503 | MR | Zbl

[17] Dutour Sikirić M., Schürmann A., Vallentin F., “Classification of eight-dimensional perfect forms”, Electron. Res. Announc. Amer. Math. Soc., 13 (2007), 21–32 | DOI | MR | Zbl

[18] Erdös P., Gruber P.M., Hammer J., Lattice points, Longman Scientific Technical, Harlow, 1989

[19] Erdös P., Rogers C.A., “The star number of coverings of space with convex bodies”, Acta arith., 9 (1964), 41–45 | MR | Zbl

[20] Fejes Tòth L., Lagerungen in der Ebene, auf der Kugel und im Raum, Grundl. math. Wissensch., 65, 2. Aufl., Springer, Berlin, 1972 | MR | Zbl

[21] Gauss C.F., “Recension der “Untersuchungen über die Eigenschaften der positiven ternären quadratischen Formen von Ludwig August Seeber, 1831””, J. reine und angew. Math., 20 (1840), 312–320; Werke, Bd. 2, Kön. Ges. Wissensch., Göttingen, 1863, 188–196

[22] Gruber P.M., “Typical convex bodies have surprisingly few neighbours in densest lattice packings”, Stud. sci. math. Hung., 21 (1986), 163–173 | MR | Zbl

[23] Gruber P.M., “Minimal ellipsoids and their duals”, Rend. Circ. Mat. Palermo. Ser. 2, 37 (1988), 35–64 | DOI | MR | Zbl

[24] Gruber P.M., “Baire categories in convexity”, Handbook of convex geometry, V. B, North-Holland, Amsterdam, 1993, 1327–1346 | DOI | MR | Zbl

[25] Gruber P.M., “In many cases optimal configurations are almost regular hexagonal”, Suppl. Rend. Circ. Mat. Palermo. Ser. 2, 65 (2000), 121–145 | MR | Zbl

[26] Gruber P.M., Convex and discrete geometry, Grundl. math. Wissensch., 336, Springer, Berlin, 2007 | MR | Zbl

[27] Gruber P.M., “Application of an idea of Voronoĭ to John type problems”, Adv. Math., 218 (2008), 309–351 | DOI | MR | Zbl

[28] Gruber P.M., Application of an idea of Voronoĭ, a report. To appear

[29] Gruber P.M., “Uniqueness of lattice packings and coverings of extreme density”, Adv. Geom., 11:4 (2011), 691–710 | DOI | MR | Zbl

[30] Gruber P.M., Application of an idea of Voronoĭ to lattice packing, Submitted

[31] Gruber P.M., “Application of an idea of Voronoĭ to lattice zeta functions”, Tr. MIAN, 276, 2012 (to appear) | MR

[32] Gruber P.M., “Voronoĭ type criteria for lattice coverings with balls”, Acta arith., 149 (2011), 371–381 | DOI | MR | Zbl

[33] Gruber P.M., “John and Loewner ellipsoids”, Discr. and Comput. Geom., 46:4 (2011), 776–788 | DOI | MR | Zbl

[34] Gruber P.M., Lekkerkerker C.G., Geometry of numbers, 2nd ed., North-Holland, Amsterdam, 1987 ; Грубер П.М., Леккеркеркер К.Г., Геометрия чисел, Наука, М., 2008 | MR | Zbl | Zbl

[35] Gruber P.M., Schuster F.E., “An arithmetic proof of John's ellipsoid theorem”, Arch. Math., 85 (2005), 82–88 | DOI | MR | Zbl

[36] Hlawka E., “Zur Geometrie der Zahlen”, Math. Ztschr., 49 (1943), 285–312 | DOI | MR | Zbl

[37] Kabatyanskii G.A., Levenshtein V.I., “O granitsakh dlya upakovok na sfere i v prostranstve”, Probl. peredachi inform., 14:1 (1978), 3–25 | Zbl

[38] Kepler J., Strena seu de nive sexangula, Tampach, Frankfurt, 1611; Gesammelte Werke, Bd. 4, C.H. Beck'sche Verlag, München, 1940 ; The six-cornered snowflake, Clarendon Press, Oxford, 1966 | Zbl

[39] Kershner R., “The number of circles covering a set”, Amer. J. Math., 61 (1939), 665–671 | DOI | MR | Zbl

[40] Klein F., “Die allgemeine lineare Transformation der Liniencoordinaten”, Math. Ann., 2 (1870), 366–370 ; Gesammelte mathematische Abhandlungen, Bd. 1, Springer, Berlin, 1921, 81–86 | DOI | MR | DOI

[41] Kneser M., “Two remarks on extreme forms”, Can. J. Math., 7 (1955), 145–149 | DOI | MR | Zbl

[42] Korkine A., Zolotareff G., “Sur les formes quadratiques positives quaternaires”, Math. Ann., 5 (1872), 581–583 | DOI | MR | Zbl

[43] Korkine A., Zolotareff G., “Sur les formes quadratiques”, Math. Ann., 6 (1873), 366–389 | DOI | MR | Zbl

[44] Korkine A., Zolotareff G., “Sur les formes quadratiques positives”, Math. Ann., 11 (1877), 242–292 | DOI | MR | Zbl

[45] Leech J., Sloane N.J.A., “Sphere packings and error-correcting codes”, Can. J. Math., 23 (1971), 718–745 | DOI | MR | Zbl

[46] Martinet J., Perfect lattices in Euclidean spaces, Grundl. math. Wissensch., 325, Springer, Berlin, 2003 | DOI | MR

[47] Minkowski H., Diophantische Approximationen: Eine Einführung in die Zahlentheorie, Teubner, Leipzig, 1907 ; 1927 ; Chelsea, New York, 1957; Physica-Verlag, Würzburg, 1961 | Zbl | Zbl | Zbl

[48] Morgan F., Bolton R., “Hexagonal economic regions solve the location problem”, Amer. Math. Mon., 109 (2002), 165–172 | DOI | MR | Zbl

[49] Plücker J., Neue Geometrie des Raumes gegründet auf die Betrachtung der geraden Linie als Raumelement, I. Abth. 1868 mit einem Vorwort von A. Clebsch; II. Abth. 1869, herausgegeben von F. Klein, Teubner, Leipzig, 1868 | Zbl

[50] Rogers C.A., Packing and covering, Cambridge Univ. Press, Cambridge, 1964 | MR | Zbl

[51] Rush J.A., “A lower bound on packing density”, Invent. math., 98 (1989), 499–509 | DOI | MR | Zbl

[52] Ryshkov S.S., “On the question of final $\zeta $-optimality of lattices providing the closest lattice packing of $n$-dimensional spheres”, Sib. Math. J., 14 (1974), 743–750 | DOI | Zbl | Zbl

[53] Ryshkov S.S., “Geometriya polozhitelnykh kvadratichnykh form”, Proc. Intern. Congr. Math., Vancouver, 1974, V. 1, Can. Math. Congr., Montreal, 1975, 501–506

[54] Ryshkov S.S., Baranovskii E.P., “Solution of the problem of least dense lattice covering of five-dimensional space by equal spheres”, Sov. Math. Dokl., 16 (1975), 586–590 | MR | Zbl

[55] Ryshkov S.S., Baranovskii E.P., “Classical methods in the theory of lattice packings”, Russ. Math. Surv., 34:4 (1979), 1–68 | DOI | MR | Zbl | Zbl

[56] Saff E.B., Kuijlaars A.B.J., “Distributing many points on a sphere”, Math. Intell., 19:1 (1997), 5–11 | DOI | MR | Zbl

[57] Sarnak P., Strömbergsson A., “Minima of Epstein's zeta function and heights of flat tori”, Invent. math., 165 (2006), 115–151 | DOI | MR | Zbl

[58] Schmidt W.M., “On the Minkowski–Hlawka theorem”, Ill. J. Math., 7 (1963), 18–23 | MR

[59] Schmutz P., “Riemann surfaces with shortest geodesic of maximal length”, Geom. and Funct. Anal., 3 (1993), 564–631 | DOI | MR | Zbl

[60] Schmutz P., “Systoles on Riemann surfaces”, Manuscr. math., 85 (1994), 429–447 | DOI | MR | Zbl

[61] Schmutz Schaller P., “Geometry of Riemann surfaces based on closed geodesics”, Bull. Amer. Math. Soc., 35 (1998), 193–214 | DOI | MR | Zbl

[62] Schmutz Schaller P., “Perfect non-extremal Riemann surfaces”, Can. Math. Bull., 43 (2000), 115–125 | DOI | MR | Zbl

[63] Schürmann A., Computational geometry of positive definite quadratic forms: Polyhedral reduction theories, algorithms, and applications, Amer. Math. Soc., Providence, RI, 2009 | MR

[64] Schürmann A., Vallentin F., “Computational approaches to lattice packing and covering problems”, Discr. and Comput. Geom., 35 (2006), 73–111 | DOI | MR

[65] Sidel'nikov V.M., “On the densest packing of balls on the surface of an $n$-dimensional Euclidean sphere and the number of binary code vectors with a given code distance”, Sov. Math. Dokl., 14 (1973), 1851–1855 | MR | Zbl

[66] Siegel C.L., Lectures on the geometry of numbers, Springer, Berlin, 1989 | MR | Zbl

[67] Swinnerton-Dyer H.P.F., “Extremal lattices of convex bodies”, Proc. Cambridge Philos. Soc., 49 (1953), 161–162 | DOI | MR | Zbl

[68] Venkov B., “Réseaux et designs sphériques”, Réseaux euclidiens, designs sphériques et formes modulaires, Monogr. Enseign. Math., 37, Enseign. Math., Geneva, 2001, 10–86 | MR | Zbl

[69] Vorono\"{ı, “G.} Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premièr mémoire: Sur quelques propriétés des formes quadratiques positives parfaites”, J. reine und angew. Math., 133 (1908), 97–178 | DOI | Zbl

[70] Vorono\"{ı, “G.} Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire: Recherches sur les paralléloèdres primitifs. I, II”, J. reine und angew. Math., 134 (1908), 198–287 ; 136 (1909), 67–181 | DOI | Zbl | DOI

[71] Voronoi G.F., Sobranie sochinenii, 1–3, Izd-vo AN UkrSSR, Kiev, 1952, 1953

[72] Voronoï's impact on modern science, Books 1, 2, eds. P. Engel, H. Syta, Inst. Math. Nat. Acad. Sci. Ukraine, Kyiv, 1998

[73] Watanabe T., “A survey on Vorono\"i's theorem”, Geometry and analysis of automorphic forms of several variables, Proc. Intern. Symp., Tokyo, Sept. 14–17, 2009, World Sci., Singapore, 2011, 334 | MR

[74] Zong C., Sphere packings, Springer, New York, 1999 | MR