Tutte seminar - Stefan van Zwam

Sphere Packing with SDP

Abstract:

The sphere packing problem in dimension $n$ asks for the maximum fraction of $\mathbb{R}^n$ that can be covered by (infinitely many) disjoint, equal-sized, $n$-dimensional spheres. We will study a special case in which the spheres are required to be centered on the vertices of a \emph{lattice}, the set of integer linear combinations of a vector basis of $\mathbb{R}^n$. The optimal density is known for $n \leq 8$ and $n = 24$.

We will model the problem as a semidefinite programming problem with additional constraints on the ranks of the matrices. By relaxing these rank constraints we obtain a proper SDP to approximate the optimum. We will then use a branch-and-bound technique to compute upper bounds. Finally we round to fractional solutions to make these bounds mathematically rigorous. Our results reproduce the known bounds up to dimension 8 (up to a small margin), and yield some new insights in the theory of Korkin-Zolotarev reduced lattice bases.