Rigidity of spherical codes

Cohn, Henry¹ ; Jiao, Yang² ; Kumar, Abhinav³ ; Torquato, Salvatore⁴

¹ Microsoft Research New England, One Memorial Drive, Cambridge, MA 02142
² Physical Sciences–Oncology Center, Princeton University, Princeton, New Jersey 08544
³ Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139
⁴ Department of Chemistry, Princeton University, Princeton, New Jersey 08544

Geometry & topology, Tome 15 (2011) no. 4, pp. 2235-2273.

Résumé

A packing of spherical caps on the surface of a sphere (that is, a spherical code) is called rigid or jammed if it is isolated within the space of packings. In other words, aside from applying a global isometry, the packing cannot be deformed. In this paper, we systematically study the rigidity of spherical codes, particularly kissing configurations. One surprise is that the kissing configuration of the Coxeter–Todd lattice is not jammed, despite being locally jammed (each individual cap is held in place if its neighbors are fixed); in this respect, the Coxeter–Todd lattice is analogous to the face-centered cubic lattice in three dimensions. By contrast, we find that many other packings have jammed kissing configurations, including the Barnes–Wall lattice and all of the best kissing configurations known in four through twelve dimensions. Jamming seems to become much less common for large kissing configurations in higher dimensions, and in particular it fails for the best kissing configurations known in $25$ through $31$ dimensions. Motivated by this phenomenon, we find new kissing configurations in these dimensions, which improve on the records set in 1982 by the laminated lattices.

Détail

DOI : 10.2140/gt.2011.15.2235

Keywords: rigidity, jamming, packing, spherical codes, kissing problem

Bibliographie

[1] D L Applegate, W Cook, S Dash, D G Espinoza, Exact solutions to linear programming problems, Oper. Res. Lett. 35 (2007) 693

[2] E Bannai, N J A Sloane, Uniqueness of certain spherical codes, Canad. J. Math. 33 (1981) 437

[3] J A Barrau, On the combinatory problem of Steiner, Proc. Section of Sciences, Koninklijke Akademie van Wetenschappen te Amsterdam 11 (1908) 352

[4] M R Best, $A[11,4,4]=35$ or some new optimal constant weight codes, (1977)

[5] M R Best, Binary codes with minimum distance four, (1978)

[6] M R Best, Binary codes with a minimum distance of four, IEEE Trans. Inform. Theory 26 (1980) 738

[7] A Bezdek, K Bezdek, R Connelly, Finite and uniform stability of sphere packings, Discrete Comput. Geom. 20 (1998) 111

[8] K Böröczky Jr., Finite packing and covering, Cambridge Tracts in Mathematics 154, Cambridge University Press (2004)

[9] H Cohn, Order and disorder in energy minimization, from: "Proceedings of the International Congress of Mathematicians, Hyderabad, August 19–27, 2010, Volume IV", Hindustan Book Agency, New Delhi (2010) 2416

[10] H Cohn, A Kumar, Universally optimal distribution of points on spheres, J. Amer. Math. Soc. 20 (2007) 99

[11] H Cohn, A Kumar, Counterintuitive ground states in soft-core models, Phys. Rev. E $(3)$ 78 (2008)

[12] H Cohn, A Kumar, Optimality and uniqueness of the Leech lattice among lattices, Ann. of Math. $(2)$ 170 (2009) 1003

[13] R Connelly, The rigidity of certain cabled frameworks and the second-order rigidity of arbitrarily triangulated convex surfaces, Adv. Math. 37 (1980) 272

[14] R Connelly, H Servatius, Higher-order rigidity—what is the proper definition?, Discrete Comput. Geom. 11 (1994) 193

[15] J H Conway, N J A Sloane, Laminated lattices, Ann. of Math. $(2)$ 116 (1982) 593

[16] J H Conway, N J A Sloane, The Coxeter–Todd lattice, the Mitchell group, and related sphere packings, Math. Proc. Cambridge Philos. Soc. 93 (1983) 421

[17] J H Conway, N J A Sloane, The cell structures of certain lattices, from: "Miscellanea mathematica", Springer (1991) 71

[18] J H Conway, N J A Sloane, What are all the best sphere packings in low dimensions?, Discrete Comput. Geom. 13 (1995) 383

[19] J H Conway, N J A Sloane, Sphere packings, lattices and groups, Grundlehren der Mathematischen Wissenschaften 290, Springer (1999)

[20] P Delsarte, J M Goethals, J J Seidel, Spherical codes and designs, Geom. Dedicata 6 (1977) 363

[21] A Donev, S Torquato, F H Stillinger, R Connelly, A linear programming algorithm to test for jamming in hard-sphere packings, J. Comput. Phys. 197 (2004) 139

[22] Y Edel, E M Rains, N J A Sloane, On kissing numbers in dimensions 32 to 128, Electron. J. Combin. 5 (1998)

[23] N D Elkies, Mordell–Weil lattices in characteristic 2 II: The Leech lattice as a Mordell–Weil lattice, Invent. Math. 128 (1997) 1

[24] V Elser, S Gravel, Laminating lattices with symmetrical glue, Discrete Comput. Geom. 43 (2010) 363

[25] R L Griess Jr., Pieces of $2^d$: existence and uniqueness for Barnes–Wall and Ypsilanti lattices, Adv. Math. 196 (2005) 147

[26] R L Griess Jr., Corrections and additions to: “Pieces of $2^d$: existence and uniqueness for Barnes–Wall and Ypsilanti lattices” [Adv. Math. 196 (2005) 147–192], Adv. Math. 211 (2007) 819

[27] J Leech, Five dimensional non-lattice sphere packings, Canad. Math. Bull. 10 (1967) 387

[28] J Leech, Six and seven dimensional non-lattice sphere packings, Canad. Math. Bull. 12 (1969) 151

[29] V I Levenšteĭn, On bounds for packings in $n$–dimensional Euclidean space, Dokl. Akad. Nauk SSSR 245 (1979) 1299

[30] L Lovász, M D Plummer, Matching theory, AMS Chelsea Publishing, Providence, RI (2009)

[31] F J Macwilliams, N J A Sloane, The Theory of Error-correcting Codes, North-Holland Mathematical Library 16, North-Holland Publishing Co. (1977)

[32] H D Mittelmann, F Vallentin, High-accuracy semidefinite programming bounds for kissing numbers, Experiment. Math. 19 (2010) 175

[33] C Musès, The dimensional family approach in (hyper)sphere packing: a typological study of new patterns, structures, and interdimensional functions, Appl. Math. Comput. 88 (1997) 1

[34] O R Musin, The kissing number in four dimensions, Ann. of Math. $(2)$ 168 (2008) 1

[35] G Nebe, N J A Sloane, Table of the highest kissing numbers presently known

[36] A M Odlyzko, N J A Sloane, New bounds on the number of unit spheres that can touch a unit sphere in $n$ dimensions, J. Combin. Theory Ser. A 26 (1979) 210

[37] P R J Östergård, Classification of binary constant weight codes, IEEE Trans. Inform. Theory 56 (2010) 3779

[38] B Roth, W Whiteley, Tensegrity frameworks, Trans. Amer. Math. Soc. 265 (1981) 419

[39] K Schütte, B L Van Der Waerden, Das Problem der dreizehn Kugeln, Math. Ann. 125 (1953) 325

[40] D V Shtrom, The Delsarte method in the problem of the contact numbers of Euclidean spaces of high dimensions, Proc. Steklov Inst. Math. (2002)

[41] T Tarnai, . Gáspár, Improved packing of equal circles on a sphere and rigidity of its graph, Math. Proc. Cambridge Philos. Soc. 93 (1983) 191

[42] A Tarski, A decision method for elementary algebra and geometry, University of California Press (1951)

[43] S Torquato, F H Stillinger, Multiplicity of generating, selection, and classification procedures for jammed hard-particle packings, J. Phys. Chem. B 105 (2001) 11849

[44] S Torquato, F H Stillinger, Jammed hard-particle packings: from Kepler to Bernal and beyond, Rev. Modern Phys. 82 (2010) 2633

[45] G L Watson, The number of minimum points of a positive quadratic form, Dissertationes Math. (Rozprawy Mat.) 84 (1971)

[46] V A Zinoviev, T Ericson, New lower bounds for contact numbers in small dimensions, Problemy Peredachi Informatsii 35 (1999) 3