An Efficient Linear Programming Algorithm to Generate the Densest Lattice Sphere Packings

Abstract

Finding the densest sphere packing in $d$-dimensional Euclidean space ${\mathbb{R}}^d$ is an outstanding fundamental problem with relevance in many fields, including the ground states of molecular systems, colloidal crystal structures, coding theory, discrete geometry, number theory, and biological systems. Numerically generating the densest sphere packings becomes very challenging in high dimensions due to an exponentially increasing number of possible sphere contacts and sphere configurations, even for the restricted problem of finding the densest lattice sphere packings. In this paper, we apply the Torquato-Jiao packing algorithm, which is a method based on solving a sequence of linear programs, to robustly reproduce the densest known lattice sphere packings for dimensions 2 through 19. We show that the TJ algorithm is appreciably more efficient at solving these problems than previously published methods. Indeed, in some dimensions, the former procedure can be as much as three orders of magnitude faster at finding the optimal solutions than earlier ones. We also study the suboptimal local density-maxima solutions (inherent structures or "extreme" lattices) to gain insight about the nature of the topography of the "density" landscape.

23 pages, 3 figures

References in corpus (5)

• Robust Algorithm to Generate a Diverse Class of Dense Disordered and Ordered Sphere Packings via Linear Programming
• Dense Packings of Superdisks and the Role of Symmetry
• Toward the Jamming Threshold of Sphere Packings: Tunneled Crystals
• Maximally dense packings of two-dimensional convex and concave noncircular particles
• Estimates of the optimal density and kissing number of sphere packings in high dimensions

Cited by in corpus (7)

• Basic Understanding of Condensed Phases of Matter via Packing Models
• Complexity in surfaces of densest packings for families of polyhedra
• Characterization of maximally random jammed sphere packings: Voronoi correlation functions
• Jammed lattice sphere packings
• Statistical mechanics of the lattice sphere packing problem
• Confined disordered strictly jammed binary sphere packings
• Marginal stability in jammed packings: quasicontacts and weak contacts