King's College London

Scientists at King’s have made the largest improvement to the problem of sphere packing in high dimensions since English mathematician Claude Ambrose Rogers in 1947.

In a paper entitled ‘A New Lower Bound to Sphere Packing’, Dr Matthew Jenssen from the Department of Mathematics and collaborators have narrowed down the optimum density of spheres packed into a volume in high-dimensional space.

The classical problem of sphere packing asks for the best, or densest, way to pack spheres in a box. It first dates to the explorer Sir Walter Raleigh, who asked scientist Thomas Harriott how he should pack cannonballs on his ships to ensure he was carrying as many as possible. Harriott then passed the problem to astronomer Johannes Kepler, who suggested in 1611 that you could do no better than ‘face-centric cubic packing’, which is akin to the square and triangle-based pyramids used when packing oranges in supermarkets. Taken together, these form a mathematical ‘lattice’ structure. 

This became known as ‘Kepler’s conjecture’ and said that the densest way to pack three-dimensional spheres would account for 74.05% of the total volume of the box. This was eventually proved by Thomas Hales in 2017.

In mathematics, there exist objects that are outside of the typical three dimensions humans see. The problem of sphere packing has only been solved in dimensions 1, 2, 3, 8 and 24, with two dimensions being a flat shape, three dimensions being an object with length, breadth and depth, and dimensions beyond that needing additional numbers to identify specific co-ordinates – for four dimensions, five for five dimensions, etc.

When dealing with very large dimensions, very little is known. Accordingly, mathematicians must use ‘bounds’ when ascertaining the optimum packing density that they know exists for packing problems in lower dimensions. These bounds function as upper and lower limits on what that optimum number might be.

Using a method that departed from a focus on neat, highly structured lattices of sphere packings which have been the dominant form of investigation, Matthew and the team made heavy use of random methods to find an unstructured sphere packing. They prove that there exist sphere packings of density roughly d log(d) / 2^{d+1}, or the logarithm of dimension, times by the dimension of the sphere, divided by two to the power of the dimension plus one.

This correlates with a prediction made by Nobel Prize winner and King’s honorary degree holder Giorgio Parisi, who with partner Francesco Zamponi predicted that any ‘unstructured’ sphere packing can have density at most d log d / 2^{d}.

Explaining what the impact of this landmark discovery might mean for disciplines beyond mathematics, Dr Jenssen said, “High dimensional sphere packings are not simply of interest to mathematicians; they have practical implications too.

“Engineers and computer scientists use them in error-correcting codes when sending information over a phone line or line of communication like WhatsApp. These error-correcting codes gives a way to encode information in such a way that it is unlikely to get ‘corrupted' when sent over a noisy communication channel with a lot of interference from other signals.’’

Sphere packings in high dimensions have also been an increasing object of study for physicists, as theoretical models such as the hard-sphere model use sphere packing to conceptualise structures of matter.

“We are still a long way off from definitively solving the sphere packing problem in high dimensions like Kepler and Hales did for 3-D spheres,” said Dr Jenssen “there has been some great progress in recent years, but there’s still plenty of work to be done!”