Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Numerical search methods for dense sphere packings in higher dimensions

Mathematical Physics & Probability

Speaker: Yoav Kallus, Santa Fe Institute
Related Webpage:
Location: 2112 MSB
Start time: Wed, Apr 5 2017, 4:10PM

The sphere packing problem is solved in 2, 3, 8, and 24 dimensions, but still wide open in other dimensions and increasingly important for our understanding of physical phenomena. How can we best use computers to search for packings that might beat the best currently known packing? Naive annealing methods run not only into the curse of dimensionality, but also the increasing rarity of crystallization with dimension. A promising approach is to restrict attention to packings with at most N spheres per unit cell, with N small. The N=1 case corresponds to Bravais lattices and Voronoi gave an algorithm to exhaustively enumerate all local optima, which has been carried out for d<=8. For larger dimensions, various stochastic search methods have been devised and are successful at finding the densest known lattice for d<=20.

I will present a generalization of the Voronoi algorithm for N>1 and show results of complete enumeration for N=2, d<6. I will also present improvements on current stochastic search methods for Bravais lattices based on population annealing and molecular dynamics in the space of lattices.With these improvements, the range of accessible dimensions is extended.