New upper bounds for kissing numbers from semidefinite programming

Lecturer: Frank Vallentin

In geometry, the kissing number problem asks for the maximum number k(n) of unit spheres that can simultaneously touch the unit sphere in n-dimensional Euclidean space without overlapping. It is trivial that k(1) = 2, k(2) = 6, and the question whether k(3) = 12 or k(3) = 13 was the subject of a famous discussion between Isaac Newton and David Gregory in 1694. This question was finally solved only in 1953 by Schuette and van der Waerden. Today the kissing number is only known for n = 1, 2, 3, 4, 8, 24, where the k(4) = 24 was proved by O. Musin in 2003.

In this lecture I will explain a general method based on semidefinite programming to find upper bounds for packing problems of this kind. This method is a strengthening of the linear programming method which P. Delsarte developed in the seventies and it is an adaption of A. Schrijver's approach who derived new upper bounds for binary codes using semidefinite programming.

We implemented this approach and we found computationally, but rigorously, new upper bounds for k(n) in several dimensions. In particular we found a unified proof for all cases when the kissing number is known.

This is joint work with Christine Bachoc. See also the preprints "New upper bounds for kissing numbers from semidefinite programming" ( and "Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps" (

back to EIDMA Seminar Combinatorial Theory announcements