Fejes Toth Lecture

One of the classic problems in discrete geometry is the construction of good codes in familiar spaces, such as Euclidean space, spheres, Hamming space, projective spaces, etc. A basic invariant of a spherical code (i.e. a finite collection of points on a sphere) is the minimal angular separation between distinct points. For instance, the kissing problem asks to maximize the size of a spherical code subject to the constraint that the minimal angle be at least 60 degrees. Another important characteristic a code is whether it is jammed or unjammed: whether it can be deformed (modulo isometries) by continuously moving its points, without decreasing the minimal distance. Unjamming a code usually leads to an improvement in its minimal distance. We describe a simple linear programming algorithm to check jamming of spherical codes, and its application to detect whether many of the best known kissing configurations in low dimensions are jammed. As an interesting by-product, we improve the kissing numbers in dimensions 25 through 31. This is joint work with Henry Cohn, Yang Jiao and Salvatore Torquato.