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

Information Flow in Molecular Machines
Biological Physics

Information Flow in Molecular Machines

A theoretical model shows that exchange of information plays a key role in the molecular machines found in biological cells. Read More »

Quantum Coherence Boosts Quantum Work
Atomic and Molecular Physics

Quantum Coherence Boosts Quantum Work

By manipulating a nitrogen vacancy’s single spin, researchers have shown that the more coherent the system is, the more work can be extracted from it. Read More »

Why Emus Favor Fast Walking
Computational Physics

Why Emus Favor Fast Walking

Emus inherited from their dinosaur ancestors a crouched posture that dictates the gait they adopt when moving quickly, according to a new computer simulation of bird motion. Read More »

More Articles