Workshop E1: Linear and semidefinite programming bounds
Date: February 25 - 29, 2008
Organizers: Henry Cohn, Mathieu Dutour Sikiric, Achill Schürmann, Frank Vallentin
The linear programming bounds (LP bounds), established by Delsarte in 1973, and their recent extension, the semidefinite programming bounds (SDP bounds), give the strongest known upper bounds for packing problems in metric spaces.
Topics and Goal:
The LP and SDP bound technique amounts to proving an upper bound for a packing problem by finding an optimal solution of a specific LP or SDP problem. It turned out that although the LP and the SDP bounds are obtained from convex optimization problems they are usually very difficult to solve numerically. Where does this numerical instability come from and how can one deal with it? Under which conditions do LP/SDP bounds give sharp results? One very specific case is the kissing number in dimension 4. In 2003 Musin used the LP bound together with some geometric insight to show that the kissing number in dimension 4 equals 24. Bachoc and Vallentin showed that one can get a simpler proof of this fact by using the SDP bound. It is widely believed that the kissing configuration in dimension 4 is unique. Is it possible to use the SDP bound to show that the vertices of the 24-cell give the unique optimal kissing configuration in dimension 4? Cohn and Elkies showed in 2003 that the LP bound also applies to the non-compact Euclidean space Rn. They found new best-known upper bounds for the sphere packing density in dimension 4, ..., 36. Is it possible that the LP bound of Cohn and Elkies can be used to give asymptotic results? Can one use SDP bounds to give asymptotic results?