Sphere Packing

Sphere packing is a classic problem in mathematics. The question is: How do you stack equally sized spheres so that as little empty space as possible remains? The spheres may touch but not overlap. Everyone knows the answer from everyday life: oranges in the supermarket are arranged in layers, with each sphere sitting in the dip between three spheres below it. This arrangement fills about 74 percent of the space, the rest is air. That this cannot be improved upon in three-dimensional space was only proven in 1998, even though Johannes Kepler had already conjectured it in 1611.

Why fruit crates and radio signals face the same problem

Sphere packing becomes interesting because it can be posed not just in three dimensions. Mathematicians also ask about four, eight, or 24 dimensions. A space with many dimensions is simply a list of numbers: a point in eight dimensions is a set of eight values. This is exactly how technical signals are described. A radio transmission or a stored sequence of numbers is a point in such a space.

This turns into a practical problem in communications engineering. Anyone transmitting data chooses a set of permitted signals. Along the way, noise is added, shifting the signal slightly. The receiver picks the permitted signal that lies closest. So that it doesn’t get it wrong, the permitted signals must be far enough apart. Around each signal, then, lies a safety sphere — and one wants to fit in as many such spheres as possible. This is literally sphere packing.

Information theorist Claude Shannon formulated this connection in the 1940s. His limit states how much data a noisy channel can carry at most. Error-correcting codes in mobile networks, DVDs, and hard drives are attempts to get as close as possible to this limit.

Lattices, randomness, and the leap to dimension 8

The simplest strategy is a lattice: you place the sphere centers in a regular pattern and repeat it. In three dimensions, this yields the orange packing. In eight dimensions there is a particularly good lattice called E8, and in 24 dimensions the Leech lattice. For both of these cases it was proven in 2016 that they are optimal. Mathematician Maryna Viazovska received the Fields Medal for this in 2022, the highest honor in her field.

For almost all other dimensions, the best result is unknown. Only upper and lower bounds are known, meaning a range within which the solution must lie. A common misconception is that regular lattices are always best. In very many dimensions, randomly scattered spheres produce surprisingly good results, and no one knows for certain whether ordered patterns even win out there.

A second point is important for understanding this. In high dimensions, packing becomes dramatically worse. Already at ten dimensions, the best known packings fill less than one percent of the space. The reason: almost all the volume of a high-dimensional cube sits in its corners, and no sphere fits there.

From mobile phone connections to post-quantum cryptography

In everyday life, sphere packing is invisibly present in every stable data connection. When a video runs without glitches despite a weak Wi-Fi signal, codes are at work whose construction traces back to lattice packings. The modulation used in 5G mobile networks is likewise based on distributing signal points with maximum spacing.

In tech news, the term currently comes up mostly in connection with encryption. So-called post-quantum cryptography methods are meant to remain secure even once powerful quantum computers exist. Many of these methods rely on lattices in hundreds of dimensions. Their security depends on the fact that finding the nearest point in such a lattice is extremely difficult — precisely the question that arises when packing spheres. The US standards institute NIST standardized the first such methods in 2024.

Sphere packing should be distinguished from the related problem of gapless space partitioning. There, the question is how to divide a space completely into equal cells. In sphere packing, gaps inevitably remain because spheres cannot fill corners. Both questions arise in data compression, when measured values are rounded to a small number of levels.