Packing Spheres in High Dimensions
Veit Elser of Cornell University has just described a new way to elucidate a problem that has baffled mathematicians for over a century: How densely can identical spheres be packed as the dimension of the spheres and of the space they occupy grow ever larger [1]? Schemes for densely packing spheres have been worked out in low dimensions and for two special cases: 8 and 24 dimensions. (A sphere in n-dimensional space is a set of points that are the same fixed distance away from a given center point.) Surprisingly, some schemes in high dimensions are little better than a random approach. What’s more, a century of research has failed to improve on the result from Hermann Minkowski, a German mathematician who came up with the concept of four-dimensional spacetime, that with each additional dimension, the highest fraction of space that can be occupied by spheres falls by a factor of 2. Intuitively, the rate of decrease should be slower.
Elser turned to the relaxed-reflect-reflect (RRR) algorithm, which originated in diffraction microscopy and other imaging applications. In the case of sphere packing, RRR works by a procedure known as divide and concur. By making multiple copies of the spheres, the packing constraints can be divided into simpler constraints between pairs of spheres. Once that’s done, RRR compels the sphere copies to “concur”—that is, to be the same.
Elser’s numerical experiments showed that RRR doubles the density of the best general result established by mathematician Keith Ball of the University of Warwick, UK, at least up to the highest dimension Elser attempted, which was 22. A more intensive series of simulations suggested that Minkowski’s factor-of-2 rule can also be improved.
–Charles Day
Charles Day is a Senior Editor for Physics Magazine.
References
- V. Elser, “Packing spheres in high dimensions with moderate computational effort,” Phys. Rev. E 108, 034117 (2023).