Computing Dense Hypersphere Packings in High Dimensional Space

If you've ever ordered fruits by the crate, you may be familiar with the sphere packing problem. Based on how they're arranged, the number of fruits that fit inside the crate varies; there are some arrangements that are, in some sense, denser than others. Now, instead of fruits, we're interested in figuring out how to densely pack high-dimensional hyperspheres.

The sphere packing problem is stated as follows: given some dimension , we need to determine the highest possible density in which -dimensional spheres of equal size can be arranged. In two dimensions, the maximum packing density is and can be achieved with the arrangement below:

The sphere packing problem turns out to be very difficult for arbitrary , and the densest packings are only known up to 8 dimensions. Still, it is of practical interest to identify "dense" packings in high dimensions as they have applications in error-correcting codes.

So what is a "dense" packing? To establish a baseline, let's first consider a trivial packing. If we place a sphere on every point of the integer lattice, the arrangement has a density of

(this is simply the volume of an -sphere with radius ). In high dimensions, the integer lattice turns out to produce a bad packing due to the factorial term in the denominator. A theorem due to Hermann Minkowski and Edmund Hlawka gives us a better lower bound: it states that there exist lattices with packing density satisfying

We will consider lattices that satisfy this lower bound to be "dense" packings.

The proof of Minkowski-Hlawka is nonconstructive, meaning we don't know how to construct lattices satisfying the lower bound. However, Hlawka's proof guarantees that such a lattice exists within an exponentially-sized family of lattices, so at the very least we know that we are working with a computable problem.

Project Overview

My advisor and I were interested in assessing the computability of high-dimensional "dense" packings in practice. To do so, we focused on a family of lattices given by the following construction.

Fixing a dimension and taking to be a prime, let denote the set of vectors

where are the standard basis vectors. For some vector , we construct the lattice with basis vectors

Conceptually speaking, the family of lattices is obtained by taking the -dimensional integer lattice and "sliding" one of the basis vectors around in an -dimensional space. Minkowski-Hlawka guarantees that, for any sufficiently large , there is a lattice satisfying the aforementioned lower bound.

Unfortunately, a simple brute-force search over the space is not feasible in high dimensions as there are lattices to test. Finding the actual packing density of a lattice is also difficult and involves solving an instance of the Shortest Vector Problem, which is known to be NP-hard.

However, two questions may enable us to cut down the search space significantly:

1. Can we learn from the geometry of the search space in low dimensions ro reduce the search space in high dimensions?
2. If we fix a dimension , can we learn from the geometry of the search space for small to reduce the search space for large ?

We have discovered evidence pointing to the affirmative in both cases.

Summary of Results

We begin by examining the 3-dimensional case. Since the vectors lie in a 2-dimensional space, we can visualize how the packing density of the lattice changes as a function of the "coordinate" of .

Here, ranges from 2 to 99. For each , the packing densities across all lattices is plotted as a heatmap. It becomes immediately clear that the search space is highly symmetrical; in fact, it turns out that we can identify at least axes of symmetry in dimension , leading to a reduction in the search space.

We also note that coordinates that are close to "simple fractions" produce sparse packings, although it's still unknown why this is the case.

These observations hold in four dimensions. Since the search space is 3-dimensional, we will fix a and plot 2-dimensional "slices" of the space:

Relying only on symmetry, we are able to compute dense lattice packings up to and have recovered the optimal lattice packing in dimensions. A brute force search would have taken more than years; every star in the observable universe will have died by then!

Beyond symmetries, we consider a number of search heuristics to further reduce the search space. In particular, we conjectured that vectors yielding dense lattice packings will form clusters (after appropriate scaling). Indeed, clustering analysis on data gathered up to dimensions indicates that this is the case; however, we are still working on a more careful analysis to evaluate the efficacy of clustering in higher dimensions. More to follow soon!