A milestone for the solution to the lattice sphere covering problem in dimension n = 6

The complete classification of (primitive, generic) parallelohedra in a given dimension is a challenging computational task. Nearly 50 years have passed since the classification for the last dimension, n = 5, was completed. One application of such a classification is in solving the lattice sphere covering problem for the corresponding dimension. The paper by Dutour Sikirić & van Woerden [Acta Cryst. (2025), A81, https://doi.org/10.1107/S2053273324010143] marks a milestone in the classification effort for dimension n = 6. It provides a complete classification of all primitive iso-edge domains; here primitive parallelohedra are identified based on their facet vectors.

1. A question about tiling space

The question `How can a space be tiled by replicas of a set?' may appear innocent at first glance. However, a closer look reveals that it raises several fundamental questions: What is `space'? What is meant by `tiled'? What are `replicas'? What is a `set'?

Even when restricting the question to the most basic version, it yields fascinating answers. Restrict the space to n-dimensional (Euclidean) space; restrict the sets to be a single prototile, an n-dimensional convex polytope; restrict the replicas to be congruent copies of the prototile; restrict the tiling procedure so that only lattice translates are allowed which result in a facet-to-facet tiling. Then the question becomes `How can n-dimensional Euclidean space be tiled by lattice translates of congruent convex polytopes, in a facet-to-facet manner?'

This specific question has a long history and allows for relevant, complete, mathematically rigorous answers.

Such convex polytopes that tile space, facet-to-facet, through lattice translates are called parallelohedra. It has been known since antiquity that in two dimensions there are only two parallelohedra: the square and the hexagon (see Fig. 1).

Figure 1 Parallelohedra in dimension 2.

For three dimensions, the question was first posed and answered by the Russian mathematician, crystallographer and mineralogist Evgraf Stepanovich Fedorov in 1885. He showed that there are exactly five three-dimensional parallelohedra: the cube, the hexagonal prism, the rhombic dodecahedron, the elongated dodecahedron and the truncated octahedron (see Fig. 2). As Boris Nikolayevich Delaunay remarked in 1956: `Tradition ascribes to Plato the discovery of the five regular convex polyhedra, to Archimedes the thirteen convex semi-regular polyhedra, to Kepler and Poinsot the four regular nonconvex solids, and Fedorov found the five parallelohedra' [taken from Senechal & Galiulin (1984); see Austin (2013) for a modern derivation of Fedorov's result using an approach by Conway and Sloane].

Figure 2 Parallelohedra in dimension 3: the cube, the hexagonal prism, the rhombic dodecahedron, the elongated dodecahedron and the truncated octahedron.

2. Geometry of parallelohedra

Before classifying all possible parallelohedra in a given dimension n, it is essential to gather more geometric information about parallelohedra.

A characterization of parallelohedra was discovered by Venkov, Alexandrov and McMullen (see Zong, 1996). It uses the concept of belts. A ridge [that is an -dimensional face, so, if , we talk about the edges] defines a belt of a polytope. A belt is a collection of the polytopes' facets [-dimensional faces] that contains, as a translate, either the given ridge or its negative. The characterization is as follows: a convex polytope is a parallelohedron if and only if (a) it is centrally symmetric, (b) all its facets are centrally symmetric, (c) if each belt contains either four or six facets.

The n-dimensional generalization of the truncated octahedron serves as the model case for n-dimensional parallelohedra. It is called the permutahedron and can be defined as the Voronoi cell of the dual of the root lattice A_n^* (Fig. 3).

Figure 3 Three permutahedra in dimension 3.

Generally, the Voronoi cell of a lattice L = , defined by a vector space basis , is the set of points

that are closer to the origin than to any of the other lattice points. Voronoi cells are fundamental in discrete geometry – Dirichlet, for instance, investigated them as early as 1850, more than 50 years before Voronoi's comprehensive study (Voronoi, 1908, 1909) of Voronoi cells of lattices. Voronoi cells are known by various names. In crystallography, for example, Voronoi cells are also referred to as Wigner–Seitz cells or Brillouin zones.

Voronoi cells are parallelohedra. However, the converse is currently not known, it is only conjectured. In fact, it is a famous question of Voronoi, Voronoi's conjecture, whether every parallelohedron is the affine image of the Voronoi cell of a lattice.

The number of k-dimensional faces f_k of an n-dimensional permutahedron is

where S(n,k) are the Stirling numbers of the second kind, counting the number of k-element partitions of an n-element set.

In particular, the number of vertices equals and the number of facets equals . The latter also follows from a famous characterization of the facets of Voronoi cells, proved by Voronoi: a lattice vector , , determines a facet of V(L) by the linear equality if and only if are the unique shortest vectors in the coset v+L/2L. Voronoi further showed that the number of k-dimensional faces of a general n-dimensional parallelohedron never exceeds f_k (Table 1).

Table 1
Number of k-dimensional faces of the n-dimensional permutahedron

n	f0	f1	f2	f3	f4	f5	f6
1	2	1
2	6	6	1
3	24	36	14	1
4	120	240	150	30	1
5	720	1800	1560	540	62	1
6	5040	15120	16800	8400	1806	126	1

Despite being a model case, permutahedra are also quite special among parallelohedra. They are zonotopes, meaning that all faces – not just the facets – are centrally symmetric. However, starting from dimension n = 4, parallelohedra are not necessarily zonotopes. For example, the Voronoi cell of the root lattice D₄ is the 24-cell, a Platonic solid in four dimensions with 24 vertices and 24 octahedral facets. Notably, all ridges are regular triangles.

3. Applications of parallelohedra

The example of the permutahedron demonstrates that studying even a single class of n-dimensional parallelohedra can be quite fruitful. The combinatorial structure of permutahedra is extremely rich. An alternative definition, as the convex hull of all coordinate permutations of the vector , shows its close connection to the symmetric group. We have already seen that the face numbers are related to Stirling numbers. Another interesting connection is that one can naturally subdivide the permutahedron into small cubes having identical volume, with a one-to-one correspondence between the cubes and spanning trees of the complete graph on n+1 vertices. In particular, the volume of the n-dimensional permutahedron is , which provides a geometric proof of Cayley's formula in graph theory, for the number of trees on n+1 labeled vertices. Postnikov (2009) surveyed many other relations between the permutahedron and enumerative combinatorics.

Studying all n-dimensional parallelohedra in a given dimension is also highly useful, especially when one aims to solve extremal geometric lattice problems. Prime examples include the lattice sphere covering problem, the lattice quantization problem (Conway & Sloane, 1988) and the new lattice coloring problem (Dutour Sikirić et al., 2021).

For instance, the lattice sphere covering problem asks one to find a collection of solid spheres which cover space so that the collection of sphere centers forms a lattice. The goal is to find a covering which is as economical as possible, minimizing overlap. To measure the overlap, one can pick a random point in space and count how many spheres the point is contained within on average (Fig. 4). Alternatively, one can consider the geometry of the Voronoi cell of a lattice. In this case, the lattice is normalized so that the Voronoi cell has unit volume and the objective is to minimize the circumradius of the Voronoi cell. To perform this optimization procedure, one needs detailed knowledge on how the combinatorial and metric data of the Voronoi cell change if one varies the lattice basis . Currently, optimal lattice sphere coverings are known only up to dimension n = 5. In all these dimensions, the lattice A_n^* is the optimum. However, it is known (see Schürmann & Vallentin, 2006) that starting from dimension n = 6, the lattice A_n^* is only locally optimal, not globally optimal. So far, completing the required computation in six dimensions has been impossible; this is mainly due to a combinatorial explosion in the number of cases to consider, which means that current methods require far too many computational resources.

Figure 4 The hexagonal lattice determines the most economic (lattice) sphere covering in dimension 2. For the lattice coloring problem, its chromatic number equals 3.

4. Classification of parallelohedra

The paper by Dutour Sikirić & van Woerden (2025) is an important step towards classifying all (primitive) parallelohedra in dimension 6.

A primitive parallelohedron defines a lattice tiling in which every vertex is contained in exactly n+1 lattice translates. Equivalently, this means that the Delaunay subdivision, which is the polytopal sub­division geometrically dual to the sub­division given by the parallelohedra, consists only of simplices. Primitive parallelohedra are the generic parallelohedra. For example, in dimension 2 the hexagon is primitive whereas the square is not. In dimension 3 there is again only one primitive parallelohedron, namely the truncated octahedron. The dimensions 2 and 3 give a somewhat misleading picture of primitive parallelohedra. In addition to the permutahedron, there are many other primitive parallelohedra, and their number grows quite quickly with the dimension n. Voronoi (1908, 1909) showed that in dimension n = 4 there are exactly three primitive parallelohedra. Ryshkov & Baranovskii (1978) determined the classification in dimension n = 5. There are 222 types. (Ryshkov & Baranovskii reported that there are 221 types, the missing type was later found by Engel.) Currently, the classification in dimension 6 has not yet been achieved.

The paper by Dutour Sikirić & van Woerden is a milestone for this open classification task. They provide a complete classification of all generic, primitive iso-edge domains in dimension 6. This is a coarser notion, where primitive parallelohedra are identified when they possess the same facet vectors. This results in a reduction of complexity, where instead of (n+1)! many vertices, `only' many facets need to be considered. Use of the term `iso-edge' is motivated by the geometric dual view: the facets of the parallelohedra determine edges in the Delaunay subdivision.

Interestingly, only starting from dimension 5 there are primitive parallelohedra which have the same facet vectors but different, non-equivalent combinatorial structures. This was recognized by Ryshkov & Baranovskii, who found that there are 76 iso-edge domains yielding 222 primitive parallelohedra.

Using sophisticated algorithmic techniques, Dutour Sikirić & van Woerden determined all 55083357 iso-edge domains in dimension 6. To do this, they subdivided the convex cone of positive-definite quadratic forms (which is the natural parameter space of lattices) into polyhedral cones, in which the Delaunay subdivision has the same edges – these are the iso-edge domains. Up to the action of the group there are only finitely many iso-edge domains and two iso-edge domains are adjacent whenever they differ by a small, geometric flip (Dutour Sikirić & Kummer, 2022). The main technical hurdle to complete the classification was a fast isomorphism test using canonical forms and fast polyhedral computations.

With this milestone, I sincerely hope that now the solution of the lattice sphere covering problem in dimension n = 6 is within reach.