Synopsis

Packing Spheres in High Dimensions

Physics 16, s131
An algorithm originally developed for imaging generates useful data for a problem in pure mathematics.
Eli the Bearded/CC BY-SA 3.0/Wikimedia Commons

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

  1. V. Elser, “Packing spheres in high dimensions with moderate computational effort,” Phys. Rev. E 108, 034117 (2023).

Subject Areas

Statistical PhysicsComputational Physics

Related Articles

Quantum Emulsion Predicted in BEC
Statistical Physics

Quantum Emulsion Predicted in BEC

A phase that shares some properties with mayonnaise can form in a Bose-Einstein condensate. Read More »

Model Reveals Reptilian Scale Pattern
Biological Physics

Model Reveals Reptilian Scale Pattern

Researchers have predicted—and confirmed—a secondary pattern on the ocellated lizard’s scales that is too subtle for our eyes to see. Read More »

Collective Organization of Spaghetti-like Bacteria
Biological Physics

Collective Organization of Spaghetti-like Bacteria

Lab experiments and theoretical models elucidate how chains of light-harvesting bacteria assemble into various density-dependent structures. Read More »

More Articles