×

Rigidity of spherical codes. (English) Zbl 1232.52016

Summary: 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.

MSC:

52C25 Rigidity and flexibility of structures (aspects of discrete geometry)
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D L Applegate, W Cook, S Dash, D G Espinoza, Exact solutions to linear programming problems, Oper. Res. Lett. 35 (2007) 693 · Zbl 1177.90282 · doi:10.1016/j.orl.2006.12.010
[2] E Bannai, N J A Sloane, Uniqueness of certain spherical codes, Canad. J. Math. 33 (1981) 437 · Zbl 0457.05017 · doi:10.4153/CJM-1981-038-7
[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) · Zbl 0466.94020
[6] M R Best, Binary codes with a minimum distance of four, IEEE Trans. Inform. Theory 26 (1980) 738 · Zbl 0466.94020 · doi:10.1109/TIT.1980.1056269
[7] A Bezdek, K Bezdek, R Connelly, Finite and uniform stability of sphere packings, Discrete Comput. Geom. 20 (1998) 111 · Zbl 0914.52006 · doi:10.1007/PL00009374
[8] K Böröczky Jr., Finite packing and covering, Cambridge Tracts in Mathematics 154, Cambridge University Press (2004) · Zbl 1061.52011 · doi:10.1017/CBO9780511546587
[9] H Cohn, Order and disorder in energy minimization, Hindustan Book Agency, New Delhi (2010) 2416 · Zbl 1236.05058 · doi:10.1142/9789814324359_0152
[10] H Cohn, A Kumar, Universally optimal distribution of points on spheres, J. Amer. Math. Soc. 20 (2007) 99 · Zbl 1198.52009 · doi:10.1090/S0894-0347-06-00546-7
[11] H Cohn, A Kumar, Counterintuitive ground states in soft-core models, Phys. Rev. E \((3)\) 78 (2008) · doi:10.1103/PhysRevE.78.061113
[12] H Cohn, A Kumar, Optimality and uniqueness of the Leech lattice among lattices, Ann. of Math. \((2)\) 170 (2009) 1003 · Zbl 1213.11144 · doi:10.4007/annals.2009.170.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 · Zbl 0446.51012 · doi:10.1016/0001-8708(80)90037-7
[14] R Connelly, H Servatius, Higher-order rigidity-what is the proper definition?, Discrete Comput. Geom. 11 (1994) 193 · Zbl 0793.52005 · doi:10.1007/BF02574003
[15] J H Conway, N J A Sloane, Laminated lattices, Ann. of Math. \((2)\) 116 (1982) 593 · Zbl 0502.52016 · doi:10.2307/2007025
[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 · Zbl 0518.10035 · doi:10.1017/S0305004100060746
[17] J H Conway, N J A Sloane, The cell structures of certain lattices, Springer (1991) 71 · Zbl 0738.52014
[18] J H Conway, N J A Sloane, What are all the best sphere packings in low dimensions?, Discrete Comput. Geom. 13 (1995) 383 · Zbl 0844.52013 · doi:10.1007/BF02574051
[19] J H Conway, N J A Sloane, Sphere packings, lattices and groups, Grundlehren der Mathematischen Wissenschaften 290, Springer (1999) · Zbl 0915.52003
[20] P Delsarte, J M Goethals, J J Seidel, Spherical codes and designs, Geom. Dedicata 6 (1977) 363 · Zbl 0376.05015 · doi:10.1007/BF03187604
[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 · Zbl 1106.82301 · doi:10.1016/j.jcp.2003.11.022
[22] Y Edel, E M Rains, N J A Sloane, On kissing numbers in dimensions 32 to 128, Electron. J. Combin. 5 (1998) · Zbl 0901.52019
[23] N D Elkies, Mordell-Weil lattices in characteristic 2 II: The Leech lattice as a Mordell-Weil lattice, Invent. Math. 128 (1997) 1 · Zbl 0897.11023 · doi:10.1007/s002220050133
[24] V Elser, S Gravel, Laminating lattices with symmetrical glue, Discrete Comput. Geom. 43 (2010) 363 · Zbl 1263.11065 · doi:10.1007/s00454-008-9112-8
[25] R L Griess Jr., Pieces of \(2^d\): existence and uniqueness for Barnes-Wall and Ypsilanti lattices, Adv. Math. 196 (2005) 147 · Zbl 1076.11043 · doi:10.1016/j.aim.2004.08.014
[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 · Zbl 1193.11070 · doi:10.1016/j.aim.2006.09.003
[27] J Leech, Five dimensional non-lattice sphere packings, Canad. Math. Bull. 10 (1967) 387 · Zbl 0153.51904 · doi:10.4153/CMB-1967-037-5
[28] J Leech, Six and seven dimensional non-lattice sphere packings, Canad. Math. Bull. 12 (1969) 151 · Zbl 0176.51603 · doi:10.4153/CMB-1969-014-1
[29] V I Leven, 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) · Zbl 1175.05002
[31] F J MacWilliams, N J A Sloane, The Theory of Error-correcting Codes, North-Holland Mathematical Library 16, North-Holland Publishing Co. (1977) · Zbl 0369.94008
[32] H D Mittelmann, F Vallentin, High-accuracy semidefinite programming bounds for kissing numbers, Experiment. Math. 19 (2010) 175 · Zbl 1279.11070 · doi:10.1080/10586458.2010.10129070
[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 · Zbl 0908.52007 · doi:10.1016/S0096-3003(97)00004-0
[34] O R Musin, The kissing number in four dimensions, Ann. of Math. \((2)\) 168 (2008) 1 · Zbl 1169.52008 · doi:10.4007/annals.2008.168.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 · Zbl 0408.52007 · doi:10.1016/0097-3165(79)90074-8
[37] P R J Östergård, Classification of binary constant weight codes, IEEE Trans. Inform. Theory 56 (2010) 3779 · Zbl 1366.94605 · doi:10.1109/TIT.2010.2050922
[38] B Roth, W Whiteley, Tensegrity frameworks, Trans. Amer. Math. Soc. 265 (1981) 419 · Zbl 0479.51015 · doi:10.2307/1999743
[39] K Schütte, B L van der Waerden, Das Problem der dreizehn Kugeln, Math. Ann. 125 (1953) 325 · Zbl 0050.16701 · doi:10.1007/BF01343127
[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) · Zbl 1120.43006
[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 · Zbl 0515.52008 · doi:10.1017/S0305004100060485
[42] A Tarski, A decision method for elementary algebra and geometry, University of California Press (1951) · Zbl 0044.25102
[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 · doi:10.1021/jp011960q
[44] S Torquato, F H Stillinger, Jammed hard-particle packings: from Kepler to Bernal and beyond, Rev. Modern Phys. 82 (2010) 2633 · doi:10.1103/RevModPhys.82.2633
[45] G L Watson, The number of minimum points of a positive quadratic form, Dissertationes Math. (Rozprawy Mat.) 84 (1971) · Zbl 0215.34901
[46] V A Zinoviev, T Ericson, New lower bounds for contact numbers in small dimensions, Problemy Peredachi Informatsii 35 (1999) 3 · Zbl 0983.94057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.