Wessel van Woerden

In 1908 Voronoi introduced an algorithm that solves the lattice packing problem in any dimension in finite time.

Voronoi showed that any lattice with optimal packing density must correspond to a so-called perfect (quadratic)

form and his algorithm enumerates the finitely many perfect forms up to similarity in a fixed dimension.

However, the number of non-similar perfect forms grows quickly in the dimension and as a result

Voronoi’s algorithm has only been completely executed up to dimension 8.

We prove an upper bound of $\exp(O(d^^2 \log(d)))$ on the number of similarity classes [1]. The proof is mostly

geometric and concludes by a volumetric argument.

Additionally we discuss some practical challenges and progress for completing Voronoi's algorithm in dimension 9,

e.g. how to efficiently remove redundant similar quadratic forms from a large set [2].

[1] https://arxiv.org/abs/1901.04807
[2] https://arxiv.org/abs/2004.14022