Dual Linear Programming Bounds for Sphere Packing via Discrete Reductions

Abstract

The Cohn-Elkies linear program for sphere packing, which was used to solve the 8 and 24 dimensional cases, is conjectured to not be sharp in any other dimension $d>2$. By mapping feasible points of this infinite-dimensional linear program into a finite-dimensional problem via discrete reduction, we provide a general method to obtain dual bounds on the Cohn-Elkies linear program. This reduces the number of variables to be finite, enabling computer optimization techniques to be applied. Using this method, we prove that the Cohn-Elkies bound cannot come close to the best packing densities known in dimensions $3 \leq d \leq 13$ except for the solved case $d=8$. In particular, our dual bounds show the Cohn-Elkies bound is unable to solve the 3, 4, and 5 dimensional sphere packing problems.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.