Geodesic
New upper bounds for kissing numbers from semidefinite programming
Bachoc, Christine1 ; Vallentin, Frank2
1 Laboratoire A2X, Université Bordeaux I, 351, cours de la Libération, 33405 Talence, France
2 Centrum voor Wiskunde en Informatica (CWI), Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
Journal of the American Mathematical Society, Tome 21 (2008) no. 3, pp. 909-924

Voir la notice de l'article provenant de la source American Mathematical Society

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$.
DOI : 10.1090/S0894-0347-07-00589-9

Bachoc, Christine 1 ; Vallentin, Frank 2

1 Laboratoire A2X, Université Bordeaux I, 351, cours de la Libération, 33405 Talence, France
2 Centrum voor Wiskunde en Informatica (CWI), Kruislaan 413, 1098 SJ Amsterdam, The Netherlands 
@article{10_1090_S0894_0347_07_00589_9,
     author = {Bachoc, Christine and Vallentin, Frank},
     title = {New upper bounds for kissing numbers from semidefinite programming},
     journal = {Journal of the American Mathematical Society},
     pages = {909--924},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2008},
     doi = {10.1090/S0894-0347-07-00589-9},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-07-00589-9/}
}
TY  - JOUR
AU  - Bachoc, Christine
AU  - Vallentin, Frank
TI  - New upper bounds for kissing numbers from semidefinite programming
JO  - Journal of the American Mathematical Society
PY  - 2008
SP  - 909
EP  - 924
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-07-00589-9/
DO  - 10.1090/S0894-0347-07-00589-9
ID  - 10_1090_S0894_0347_07_00589_9
ER  - 
%0 Journal Article
%A Bachoc, Christine
%A Vallentin, Frank
%T New upper bounds for kissing numbers from semidefinite programming
%J Journal of the American Mathematical Society
%D 2008
%P 909-924
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-07-00589-9/
%R 10.1090/S0894-0347-07-00589-9
%F 10_1090_S0894_0347_07_00589_9
Bachoc, Christine; Vallentin, Frank. New upper bounds for kissing numbers from semidefinite programming. Journal of the American Mathematical Society, Tome 21 (2008) no. 3, pp. 909-924. doi: 10.1090/S0894-0347-07-00589-9

[1] Andrews, George E., Askey, Richard, Roy, Ranjan Special functions 1999

[2] Borchers, Brian CSDP, a C library for semidefinite programming Optim. Methods Softw. 1999 613 623

[3] Bannai, Eiichi, Sloane, N. J. A. Uniqueness of certain spherical codes Canadian J. Math. 1981 437 449

[4] Bã¶Rã¶Czky, Kã¡Roly, Szabã³, Lã¡Szlã³ Arrangements of 13 points on a sphere 2003 111 184

[5] Bã¶Rã¶Czky, K., Szabã³, L. Arrangements of 14, 15, 16 and 17 points on a sphere Studia Sci. Math. Hungar. 2003 407 421

[6] Casselman, Bill The difficulties of kissing in three dimensions Notices Amer. Math. Soc. 2004 884 885

[7] Conway, J. H., Sloane, N. J. A. Sphere packings, lattices and groups 1988

[8] Delsarte, P. An algebraic approach to the association schemes of coding theory Philips Res. Rep. Suppl. 1973

[9] Delsarte, P., Goethals, J. M., Seidel, J. J. Spherical codes and designs Geometriae Dedicata 1977 363 388

[10] Duffin, R. J. Infinite programs 1956 157 170

[11] Gijswijt, Dion, Schrijver, Alexander, Tanaka, Hajime New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming J. Combin. Theory Ser. A 2006 1719 1731

[12] Lasserre, Jean B. Global optimization with polynomials and the problem of moments SIAM J. Optim. 2000/01 796 817

[13] Levenå¡Teä­N, V. I. Boundaries for packings in 𝑛-dimensional Euclidean space Dokl. Akad. Nauk SSSR 1979 1299 1303

[14] Odlyzko, A. M., Sloane, N. J. A. New bounds on the number of unit spheres that can touch a unit sphere in 𝑛 dimensions J. Combin. Theory Ser. A 1979 210 214

[15] Parrilo, Pablo A. Semidefinite programming relaxations for semialgebraic problems Math. Program. 2003 293 320

[16] Pfender, Florian, Ziegler, Gã¼Nter M. Kissing numbers, sphere packings, and some unexpected proofs Notices Amer. Math. Soc. 2004 873 883

[17] Putinar, Mihai Positive polynomials on compact semi-algebraic sets Indiana Univ. Math. J. 1993 969 984

[18] Vsemirnov, M. A., Rzhevskiä­, M. G. An upper bound for the contact number in dimension 9 Uspekhi Mat. Nauk 2002 149 150

[19] Schrijver, Alexander New code upper bounds from the Terwilliger algebra and semidefinite programming IEEE Trans. Inform. Theory 2005 2859 2866

[20] Schã¼Tte, K., Van Der Waerden, B. L. Das Problem der dreizehn Kugeln Math. Ann. 1953 325 334

[21] Vilenkin, N. Ja., Klimyk, A. U. Representation of Lie groups and special functions. Vol. 2 1993

Cité par Sources :