New upper bounds for kissing numbers from semidefinite programming

Bachoc, Christine; Vallentin, Frank

doi:10.1090/S0894-0347-07-00589-9

New upper bounds for kissing numbers from semidefinite programming
HTML articles powered by AMS MathViewer

by Christine Bachoc and Frank Vallentin

J. Amer. Math. Soc. 21 (2008), 909-924

DOI: https://doi.org/10.1090/S0894-0347-07-00589-9

Published electronically: November 29, 2007

PDF | Request permission

Abstract:

Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases $n = 3, 4, 8, 24$.

References

George E. Andrews, Richard Askey, and Ranjan Roy, Special functions, Encyclopedia of Mathematics and its Applications, vol. 71, Cambridge University Press, Cambridge, 1999. MR 1688958, DOI 10.1017/CBO9781107325937
Brian Borchers, CSDP, a C library for semidefinite programming, Optim. Methods Softw. 11/12 (1999), no. 1-4, 613–623. Interior point methods. MR 1778432, DOI 10.1080/10556789908805765
Eiichi Bannai and N. J. A. Sloane, Uniqueness of certain spherical codes, Canadian J. Math. 33 (1981), no. 2, 437–449. MR 617634, DOI 10.4153/CJM-1981-038-7
Károly Böröczky and László Szabó, Arrangements of 13 points on a sphere, Discrete geometry, Monogr. Textbooks Pure Appl. Math., vol. 253, Dekker, New York, 2003, pp. 111–184. MR 2034713
K. Böröczky and L. Szabó, Arrangements of 14, 15, 16 and 17 points on a sphere, Studia Sci. Math. Hungar. 40 (2003), no. 4, 407–421. MR 2037326, DOI 10.1556/SScMath.40.2003.4.3
Bill Casselman, The difficulties of kissing in three dimensions, Notices Amer. Math. Soc. 51 (2004), no. 8, 884–885. MR 2145822
J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 290, Springer-Verlag, New York, 1988. With contributions by E. Bannai, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov. MR 920369, DOI 10.1007/978-1-4757-2016-7
P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. 10 (1973), vi+97. MR 384310
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
R. J. Duffin, Infinite programs, Linear inequalities and related systems, Annals of Mathematics Studies, no. 38, Princeton University Press, Princeton, N.J., 1956, pp. 157–170. MR 0087573
Dion Gijswijt, Alexander Schrijver, and Hajime Tanaka, New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming, J. Combin. Theory Ser. A 113 (2006), no. 8, 1719–1731. MR 2269550, DOI 10.1016/j.jcta.2006.03.010

Bounds for packings on a sphere and in space

14

Jean B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2000/01), no. 3, 796–817. MR 1814045, DOI 10.1137/S1052623400366802
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

The kissing number in four dimensions

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
Pablo A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Math. Program. 96 (2003), no. 2, Ser. B, 293–320. Algebraic and geometric methods in discrete optimization. MR 1993050, DOI 10.1007/s10107-003-0387-5

Improved Delsarte bounds for spherical codes in small dimensions

114

Florian Pfender and Günter M. Ziegler, Kissing numbers, sphere packings, and some unexpected proofs, Notices Amer. Math. Soc. 51 (2004), no. 8, 873–883. MR 2145821
Mihai Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993), no. 3, 969–984. MR 1254128, DOI 10.1512/iumj.1993.42.42045
M. A. Vsemirnov and M. G. Rzhevskiĭ, An upper bound for the contact number in dimension 9, Uspekhi Mat. Nauk 57 (2002), no. 5(347), 149–150 (Russian); English transl., Russian Math. Surveys 57 (2002), no. 5, 1015–1016. MR 1992089, DOI 10.1070/RM2002v057n05ABEH000559
Alexander Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005), no. 8, 2859–2866. MR 2236252, DOI 10.1109/TIT.2005.851748
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
N. Ja. Vilenkin and A. U. Klimyk, Representation of Lie groups and special functions. Vol. 2, Mathematics and its Applications (Soviet Series), vol. 74, Kluwer Academic Publishers Group, Dordrecht, 1993. Class I representations, special functions, and integral transforms; Translated from the Russian by V. A. Groza and A. A. Groza. MR 1220225, DOI 10.1007/978-94-017-2883-6