🔢 mathematics

The lattice packing problem in dimension 9 by Voronoi's algorithm

By applying Voronoi's algorithm to enumerate all 2,237,251,040 perfect lattices in dimension 9, this paper proves that the laminated lattice $\Lambda_9$ provides the densest lattice packing, determines the Hermite constant $\gamma_9 = 2$ , and characterizes the possible kissing numbers in that dimension.

Original authors: Mathieu Dutour Sikirić, Wessel van Woerden

Published 2026-02-10

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Mathieu Dutour Sikirić, Wessel van Woerden

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to pack a suitcase with as many oranges as possible. If you just throw them in, you’ll have big gaps of air. But if you arrange them in a very specific, tight pattern, you can fit more.

In mathematics, this is called the Sphere Packing Problem. For centuries, mathematicians have been trying to find the "perfect pattern" for different dimensions. We know the best patterns for 1D (a line), 2D (hexagons), 3D (like oranges in a crate), and a few others like 8D and 24D.

But Dimension 9? That has been a massive, dark mystery. This paper is the story of how two researchers finally "turned on the lights" in Dimension 9 using a massive computational sledgehammer.

Here is the breakdown of how they did it and what they found.

1. The Problem: The Infinite Library of Patterns

Imagine an infinite library containing every possible way to arrange spheres in 9-dimensional space. Most of these arrangements are messy and inefficient. However, mathematicians know that the "winners"—the densest patterns—belong to a special club called "Perfect Lattices."

Think of a "Perfect Lattice" as a master blueprint. If you find a perfect blueprint, you know you’ve found a pattern that is incredibly stable and tight. The problem is that even in just 9 dimensions, there are billions of these blueprints. Before this paper, we only had a rough guess of how many there were.

2. The Tool: Voronoi’s "Map-Making" Algorithm

To solve this, the authors used an algorithm invented over 100 years ago by Georges Voronoi.

Think of Voronoi’s algorithm like a high-tech explorer in a mountain range.

The explorer starts at one known peak (a known perfect pattern).
The explorer looks at the ridges leading away from that peak to find the next closest peak.
They climb to that new peak, look for more ridges, and keep going.
Eventually, they will have visited every single peak in the entire mountain range.

The catch? In Dimension 9, the "mountain range" is so vast and the "ridges" are so complex that previous explorers got lost or ran out of supplies. The number of peaks to visit is 2,237,251,040. That is over two billion peaks!

3. The Breakthrough: Supercomputing and "Symmetry Shortcuts"

How do you visit two billion peaks without spending a thousand years doing it? The authors used two main tricks:

The Symmetry Shortcut: Imagine you are exploring a snowflake. Instead of measuring every single tiny point on the snowflake, you realize the snowflake is symmetrical. You only measure one small slice, and then you use math to "copy-paste" your findings to the rest of the flake. The authors used "Symmetry Groups" to avoid doing the same work twice.
The Digital Sledgehammer: They wrote incredibly fast code and used massive supercomputers (running for millions of "core hours") to crunch the numbers.

4. The Discovery: What’s at the Top?

After the dust settled, they had mapped the entire 9D landscape. Here is what they found:

The Champion: They finally proved that a specific pattern called the Laminated Lattice ( $\Lambda_9$ ) is the absolute densest way to pack spheres in 9D. It is the "Gold Medalist" of Dimension 9.
The Kissing Number: They solved the "Kissing Number" problem. Imagine a central orange in a crate; the "kissing number" is how many other oranges can touch it at once. In 9D, they proved exactly which numbers are possible (it’s not just any number; it follows a very specific, strange set of rules).
The Oddballs: They found "hollow" lattices—patterns that are perfect but have strange "empty" spots inside them, like a beautiful piece of lace that is structurally sound but full of holes.

Summary

In short: For a long time, Dimension 9 was a mathematical wilderness. By using a century-old map-making strategy, modern supercomputing, and clever symmetry shortcuts, these authors mapped every single "peak" in that wilderness, found the highest mountain, and proved exactly how the landscape is shaped.

Technical Summary: The Lattice Packing Problem in Dimension 9 by Voronoi’s Algorithm

Authors: Mathieu Dutour Sikirić and Wessel van Woerden
Subject: Discrete Geometry, Lattice Theory, Computational Number Theory

1. The Problem

The paper addresses the Lattice Packing Problem in dimension 9. The fundamental goal is to find the lattice $L \subset \mathbb{R}^n$ that maximizes the packing density $\delta(L)$ , or equivalently, maximizes the Hermite invariant $\gamma(L)$ . While the sphere packing problem has been solved for dimensions 1, 2, 3, 8, and 24, dimension 9 has remained computationally out of reach due to the exponential growth of the number of "perfect lattices" that must be checked.

2. Methodology

The authors employ Voronoi’s Algorithm, a graph-traversal method that enumerates all perfect lattices (lattices uniquely determined by their minimal vectors) in a given dimension. The algorithm works by navigating the edges of the Ryshkov polyhedron, where vertices correspond to perfect forms.

To make the computation feasible in dimension 9, the authors implemented several high-level algorithmic and computational breakthroughs:

Dual Description Problem under Symmetry: The primary bottleneck in Voronoi's algorithm is the "dual description problem"—recovering the facet representation (H-representation) of a polyhedral cone from its extreme rays (V-representation). In dimension 9, the number of facets can reach trillions. The authors solved this by computing only the facet orbits under the action of the cone's automorphism group, significantly reducing the search space.
Recursive Adjacency Decomposition Method (ADM): They utilized a recursive version of the ADM to traverse the face lattice of polyhedral cones, allowing them to handle high-incidence cases (where the number of minimal vectors is large).
Canonical Functions: To handle billions of lattices, the authors developed highly optimized canonical functions for quadratic forms and polytopes. By reducing the problem of lattice isomorphism to the problem of weighted graph isomorphism (using libraries like Traces), they turned expensive pairwise equivalence checks into efficient equality checks via hashing.
Parallelization: The implementation was scaled using the Message Passing Interface (MPI), distributing the workload across hundreds of processes. They used a hash-based partitioning scheme to ensure that equivalent lattices found by different processes were correctly identified and merged.
Memoization (Saving Bank): To avoid redundant computations, the authors implemented a "saving bank" to store and reuse the dual descriptions of complex, high-incidence ridges and facets.

3. Key Contributions and Results

The paper provides a complete classification of perfect lattices in dimension 9, yielding several landmark results:

Complete Enumeration: The authors successfully enumerated all 2,237,251,040 non-similar perfect lattices in dimension 9.
Optimality of $\Lambda_9$ : They proved that the laminated lattice $\Lambda_9$ is the densest lattice packing in dimension 9. Consequently, they determined the Hermite constant for dimension 9 to be $\gamma_9 = 2$ .
Kissing Numbers: They provided a complete classification of the possible kissing numbers (the number of minimal vectors) for 9-dimensional lattices, showing the set is precisely $2 \cdot \{1, \dots, 91, 99, 120, \dots, 129, 136\}$ .
Structural Properties:
- They proved that, with the sole exception of Coxeter’s lattice $A_9^2$ , all perfect lattices in dimension 9 possess a basis of minimal vectors.
- They identified Coxeter’s lattice $A_9^5$ as the unique hollow perfect lattice in dimension 9.
Bergé-Martinet Invariant: They identified 18 dual-extreme lattices and determined the maximum value of the Bergé-Martinet invariant $\gamma'(L)$ in this dimension.

4. Significance

This work represents a massive computational milestone in geometry. By successfully applying Voronoi's algorithm to dimension 9, the authors have bridged a significant gap in the known landscape of sphere packings. The methodologies developed—specifically regarding the dual description of high-incidence polyhedra under symmetry and the use of canonical graph-based hashing for billions of objects—provide a blueprint for future attempts to solve lattice packing problems in even higher dimensions. The release of their 150GB dataset and open-source implementations further contributes to the mathematical community's ability to study high-dimensional discrete structures.