Journal of the American Mathematical Society

Author(s): Christine Bachoc; Frank Vallentin
Journal: J. Amer. Math. Soc. 21 (2008), 909-924.
MSC (2000): Primary 52C17, 90C22
Posted: November 29, 2007
Retrieve article in: PDF DVI PostScript

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

1.: G.E. Andrews, R. Askey, R. Roy, Special functions, Cambridge University Press, 1999. MR 1688958 (2000g:33001)
2.: B. Borchers, CSDP, A C Library for Semidefinite Programming, Optimization Methods and Software 11 (1999), 613-623. MR 1778432
3.: E. Bannai, N.J.A. Sloane, Uniqueness of certain spherical codes, Canad J. Math. 33 (1981), 437-449. MR 617634 (83a:94020)
4.: K. Böröczky, L. Szabó, Arrangements of 13 points on a sphere, In: Discrete Geometry, A. Bezdek (ed.), Dekker, 2003, pp. 111-184. MR 2034713 (2005g:52043)
5.: K. Böröczky, L. Szabó, Arrangements of 14, 15, 16 and 17 points on a sphere, Studi. Sci. Math. Hung. 40 (2003), 407-421. MR 2037326 (2005g:52044)
6.: B. Casselman, The difficulties of kissing in three dimensions, Notices Amer. Math. Soc. 51 (2004), 884-885. MR 2145822 (2006a:52016)
7.: J.H. Conway, N.J.A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag, 1988. MR 920369 (89a:11067)
8.: P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. (1973), vi+97. MR 0384310 (52:5187)
9.: P. Delsarte, J.M. Goethals, J.J. Seidel, Spherical codes and designs, Geom. Dedicata 6 (1977), 363-388. MR 0485471 (58:5302)
10.: R.J. Duffin, Infinite Programs, in: Linear inequalities and related systems (H.W. Kuhn, A.W. Tucker eds.), Princeton Univ. Press, 1956, 157-170. MR 0087573 (19:374a)
11.: D.C. Gijswijt, A. Schrijver, H. Tanaka, New upper bounds for nonbinary codes, J. Combin. Theory Ser. A 13 (2006), 1717-1731. MR 2269550 (2007g:94105)
12.: G.A. Kabatiansky, V.I. Levenshtein, Bounds for packings on a sphere and in space, Problems of Information Transmission 14 (1978), 1-17.
13.: J.B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2001), 796-817. MR 1814045 (2002b:90054)
14.: V.I. Levenshtein, On bounds for packing in -dimensional Euclidean space, Soviet Math. Dokl. 20 (1979), 417-421. MR 0529659 (80d:52017)
15.: O.R. Musin, The kissing number in four dimensions, to appear in Annals of Mathematics.
16.: 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-214. MR 530296 (81d:52010)
17.: P.A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Math. Program. B 96 (2003), 293-320. MR 1993050 (2004g:90075)
18.: F. Pfender, Improved Delsarte bounds for spherical codes in small dimensions, J. Combin. Theory Ser. A 114 (2007), 1133-1147.
19.: F. Pfender, G.M. Ziegler, Kissing numbers, sphere packings and some unexpected proofs, Notices Amer. Math. Soc. 51 (2004), 873-883. MR 2145821 (2006a:52015)
20.: M. Putinar, Positive polynomials on compact semi-algebraic sets, Ind. Univ. Math. J. 42 (1993), 969-984. MR 1254128 (95h:47014)
21.: M.G. Rzhevskii, M.A. Vsemirnov, An upper bound for the contact number in dimension 9, Russ. Math. Surv. 57 (2002), 1015-1016. MR 1992089 (2004d:11054)
22.: A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005), 2859-2866. MR 2236252 (2007a:94147)
23.: K. Schütte, B.L. van der Waerden, Das Problem der dreizehn Kugeln, Math. Ann. 125 (1953) 325-334. MR 0053537 (14:787e)
24.: N.Ja. Vilenkin, A.U. Klimyk, Representation of Lie Groups and Special Functions, Volume 2, Kluwer Academic Publishers, 1993. MR 1220225 (94m:22001)

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 52C17, 90C22

Christine Bachoc
Affiliation: Laboratoire A2X, Université Bordeaux I, 351, cours de la Libération, 33405 Talence, France
Email: bachoc@math.u-bordeaux1.fr

Frank Vallentin
Affiliation: Centrum voor Wiskunde en Informatica (CWI), Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
Email: f.vallentin@cwi.nl

DOI: 10.1090/S0894-0347-07-00589-9
PII: S 0894-0347(07)00589-9
Keywords: Spherical codes, kissing number, semidefinite programming, orthogonal polynomials
Received by editor(s): October 17, 2006
Posted: November 29, 2007
Additional Notes: The second author was supported by the Netherlands Organization for Scientific Research under grant NWO 639.032.203 and by the Deutsche Forschungsgemeinschaft (DFG) under grant SCHU 1503/4-1.
Copyright of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN: 1088-6834(e) ISSN: 0894-0347(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS