Kissing number in non-Euclidean spaces of constant sectional curvature
HTML articles powered by AMS MathViewer
- by Maria Dostert and Alexander Kolpakov;
- Math. Comp. 90 (2021), 2507-2525
- DOI: https://doi.org/10.1090/mcom/3622
- Published electronically: April 13, 2021
- HTML | PDF
Abstract:
This paper provides upper and lower bounds on the kissing number of congruent radius $r > 0$ spheres in hyperbolic $\mathbb {H}^n$ and spherical $\mathbb {S}^n$ spaces, for $n\geq 2$. For that purpose, the kissing number is replaced by the kissing function $\kappa _H(n, r)$, resp. $\kappa _S(n, r)$, which depends on the dimension $n$ and the radius $r$.
After we obtain some theoretical upper and lower bounds for $\kappa _H(n, r)$, we study their asymptotic behaviour and show, in particular, that $\kappa _H(n,r) \sim (n-1) \cdot d_{n-1} \cdot B(\frac {n-1}{2}, \frac {1}{2}) \cdot e^{(n-1) r}$, where $d_n$ is the sphere packing density in $\mathbb {R}^n$, and $B$ is the beta-function. Then we produce numeric upper bounds by solving a suitable semidefinite program, as well as lower bounds coming from concrete spherical codes. A similar approach allows us to locate the values of $\kappa _S(n, r)$, for $n= 3, 4$, over subintervals in $[0, \pi ]$ with relatively high accuracy.
References
- Christine Bachoc and Frank Vallentin, New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc. 21 (2008), no. 3, 909–924. MR 2393433, DOI 10.1090/S0894-0347-07-00589-9
- Károly Bezdek, Contact numbers for congruent sphere packings in Euclidean 3-space, Discrete Comput. Geom. 48 (2012), no. 2, 298–309. MR 2946449, DOI 10.1007/s00454-012-9405-9
- Károly Bezdek and Samuel Reid, Contact graphs of unit sphere packings revisited, J. Geom. 104 (2013), no. 1, 57–83. MR 3047448, DOI 10.1007/s00022-013-0156-4
- K. Böröczky, Packing of spheres in spaces of constant curvature, Acta Math. Acad. Sci. Hungar. 32 (1978), no. 3-4, 243–261. MR 512399, DOI 10.1007/BF01902361
- Lewis Bowen, Circle packing in the hyperbolic plane, Math. Phys. Electron. J. 6 (2000), Paper 6, 10. MR 1797777
- Claude Chabauty, Résultats sur l’empilement de calottes égales sur une périsphère de $R^n$ et correction à un travail antérieur, C. R. Acad. Sci. Paris 236 (1953), 1462–1464 (French). MR 53975
- Bill Casselman, The difficulties of kissing in three dimensions, Notices Amer. Math. Soc. 51 (2004), no. 8, 884–885. MR 2145822
- H. S. M. Coxeter, An upper bound for the number of equal nonoverlapping spheres that can touch another of the same size, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, RI, 1963, pp. 53–71. MR 164283
- L. Danzer, Finite point-sets on $S^2$ with minimum distance as large as possible, Discrete Math. 60 (1986), 3–66. MR 852097, DOI 10.1016/0012-365X(86)90002-6
- P. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), no. 3, 363–388. MR 485471, DOI 10.1007/bf03187604
- M. Dostert, A. Kolpakov, and F. M. de Oliveira Filho, Semidefinite programming bounds for the average kissing number, arXiv:2003.11832, 2020. To appear in Israel J. Math.
- M. Dostert, D. de Laat, and P. Moustrou, Exact semidefinite programming bounds for packing problems, arXiv:2001.00256, 2020. To appear in SIAM J. Optim.
- Patrick Du Val, Recent Publications and Presentations: Regular Figures, Amer. Math. Monthly 73 (1966), no. 7, 799. MR 1533941, DOI 10.2307/2314022
- L. Fejes, Über eine Abschätzung des kürzesten Abstandes zweier Punkte eines auf einer Kugelfläche liegenden Punktsystems, Jber. Deutsch. Math.-Verein. 53 (1943), 66–68 (German). MR 17539
- L. Fejes Tóth, Über die dichteste Horozyklenlagerung, Acta Math. Acad. Sci. Hungar. 5 (1954), 41–44 (German, with Russian summary). MR 63062, DOI 10.1007/BF02020385
- L. Fejes Tóth, Lagerungen in der Ebene, auf der Kugel und im Raum, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete, Band LXV, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1953 (German). MR 57566
- Alexey Glazyrin, Contact graphs of ball packings, J. Combin. Theory Ser. B 145 (2020), 323–340. MR 4113184, DOI 10.1016/j.jctb.2020.05.007
- R. H. Hardin, W. D. Smith, N. J. A. Sloane, et al., Spherical Codes, http://neilsloane.com/packings/
- Matthew Jenssen, Felix Joos, and Will Perkins, On kissing numbers and spherical codes in high dimensions, Adv. Math. 335 (2018), 307–321. MR 3836667, DOI 10.1016/j.aim.2018.07.001
- G. A. Kabatjanskiĭ and V. I. Levenšteĭn, Bounds for packings on the sphere and in space, Problemy Peredači Informacii 14 (1978), no. 1, 3–25 (Russian). MR 514023
- V. I. Levenšteĭn, Boundaries for packings in $n$-dimensional Euclidean space, Dokl. Akad. Nauk SSSR 245 (1979), no. 6, 1299–1303 (Russian). MR 529659
- V. I. Levenshteĭn, Bounds for packings of metric spaces and some of their applications, Problemy Kibernet. 40 (1983), 43–110 (Russian). MR 717357
- Fabrício Caluza Machado and Fernando Mário de Oliveira Filho, Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry, Exp. Math. 27 (2018), no. 3, 362–369. MR 3857670, DOI 10.1080/10586458.2017.1286273
- Hans D. Mittelmann and Frank Vallentin, High-accuracy semidefinite programming bounds for kissing numbers, Experiment. Math. 19 (2010), no. 2, 175–179. MR 2676746, DOI 10.1080/10586458.2010.10129070
- Oleg R. Musin, The kissing number in four dimensions, Ann. of Math. (2) 168 (2008), no. 1, 1–32. MR 2415397, DOI 10.4007/annals.2008.168.1
- O. R. Musin, Towards a proof of the 24-cell conjecture, Acta Math. Hungar. 155 (2018), no. 1, 184–199. MR 3813634, DOI 10.1007/s10474-018-0828-5
- A. M. Odlyzko and 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), no. 2, 210–214. MR 530296, DOI 10.1016/0097-3165(79)90074-8
- John G. Ratcliffe, Foundations of hyperbolic manifolds, 2nd ed., Graduate Texts in Mathematics, vol. 149, Springer, New York, 2006. MR 2249478
- Claude E. Shannon, Probability of error for optimal codes in a Gaussian channel, Bell System Tech. J. 38 (1959), 611–656. MR 103137, DOI 10.1002/j.1538-7305.1959.tb03905.x
- K. Schütte and B. L. van der Waerden, Das Problem der dreizehn Kugeln, Math. Ann. 125 (1953), 325–334 (German). MR 53537, DOI 10.1007/BF01343127
- W. A. Stein, et al., Sage Mathematics Software (Version 6.6), The Sage Development Team, 2012, http://www.sagemath.org
- Jenő Szirmai, The densest geodesic ball packing by a type of nil lattices, Beiträge Algebra Geom. 48 (2007), no. 2, 383–397. MR 2364797
- Jenő Szirmai, Geodesic ball packings in $\bf S^2\times \bf R$ space for generalized Coxeter space groups, Beitr. Algebra Geom. 52 (2011), no. 2, 413–430. MR 2842640, DOI 10.1007/s13366-011-0023-0
- Jenő Szirmai, Horoball packings to the totally asymptotic regular simplex in the hyperbolic $n$-space, Aequationes Math. 85 (2013), no. 3, 471–482. MR 3063882, DOI 10.1007/s00010-012-0158-6
- A. D. Wyner, Capabilities of bounded discrepancy decoding, Bell System Tech. J. 44 (1965), 1061–1122. MR 180417, DOI 10.1002/j.1538-7305.1965.tb04170.x
Bibliographic Information
- Maria Dostert
- Affiliation: Department of Mathematics, Royal Institute of Technology (KTH), SE-100 44 Stockholm, Sweden
- MR Author ID: 1165370
- ORCID: 0000-0002-0393-8286
- Email: dostert@kth.se
- Alexander Kolpakov
- Affiliation: Institut de Mathématiques, Université de Neuchâtel, 2000 Neuchâtel, Suisse/ Switzerland; and Laboratory of combinatorial and geometric structures, Moscow Institute of Physics and Technology, Dolgoprudny, Russia
- MR Author ID: 774696
- Email: kolpakov.alexander@gmail.com
- Received by editor(s): April 11, 2020
- Received by editor(s) in revised form: October 9, 2020, and November 23, 2020
- Published electronically: April 13, 2021
- Additional Notes: The first author was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. The second author was partially supported by the Swiss National Science Foundation (project no. PP00P2-170560) and the Russian Federation Government (grant no. 075-15-2019-1926).
- © Copyright 2021 by the authors
- Journal: Math. Comp. 90 (2021), 2507-2525
- MSC (2020): Primary 05B40; Secondary 52C17, 51M09
- DOI: https://doi.org/10.1090/mcom/3622
- MathSciNet review: 4280309