Question

I have a question regarding enumeration of perfect lattices/quadratic forms. In the thesis of Achill Schürmann http://fma2.math.uni-magdeburg.de/~achill/public/habil.pdf there is an algorithm called "Voronoi's algorithm" in chapter 3, used to enumerate arithmetically inequivalent perfect quadratic forms (meaning the forms cannot be obtained one from another by scaling with a constant or applying a unimodular transformation, where the latter corresponds to a change in the basis of the lattice associated to a certain quadratic form). It is denoted as Algorithm 1 in the thesis, and is on page 49. I wonder how this algorithm can stop? I suspect that the bound on a quadratic form developed at the end of the proof of Theorem 3.1.3.2 on page 48 is used to have a stopping condition. That bound basically says that all inequivalent quadratic forms have a bounded trace depending only on the dimension and the minimum distance. I wonder whether anyone knows how this algorithm can stop? Also, in a lattice problem that I have, the upper bound I have developed is much lower than the one presented in the end of the proof of Theorem 3.1.3.2 for high dimensions, so then I'm wondering whether Voronoi's algorithm can be efficient for enumerating all perfect forms for my problem? Is it so that the bottleneck of that enumeration algorithm is that it is hard to find extreme rays of polytopes in high dimensions? In that case, it might not be efficient for my problem too. Is there a faster algorithm than Voronoi's? Grateful for any comments.

Answer 1

The algorithm stops when you don't get any more perfect forms. Specifically, at each step you determine all the contiguous forms $Q_i$ and test whether they are equivalent to forms you already knew. For all the ones that aren't, you add them to the list and iterate to determine all the forms contiguous to them, etc., so your list keeps getting longer and longer. At some point all of the contiguous forms will already be on the list, and then you are done.

Theorem 3.1.3.2 shows that there are only finitely many perfect forms, so the algorithm must eventually terminate, but the specific bound is not used in the algorithm.

You are right that finding extreme rays of polytopes in high dimensions is the bottleneck. To deal with the 8-dimensional case, you need to take advantage of all available symmetries (see Appendix A), and 9 dimensions has not been completed.

Answer 2

You seem to need lots of background. See the site of MARTINET and his page of perfect lattices PERFECT. Then there is his BOOK

A colleague of Martinet not using MO is NEBE, who has published extensively on your topic. She also maintains CATALOGUE with Sloane.

Answer 3

Voronoi Algorithm is about optimal if you are interested in enumerating all perfect form. The problem is that usually one is interested in enumerating the ones with some specific property (high packing density, etc.) but there is no way that I know to restrict the enumeration.

The algorithm works by finding an initial perfect form, finding the adjacent perfect form, testing for isomorphism and finishing when all perfect forms have been enumerated. There are three key algorithm in the computation: testing for isomorphism, flipping the form to the adjacent one and computing facets of the perfect cone. Of those the first two are usually ok and the last one is the one that causes problems.

The best is probably to use an empirical approach of running the enumeration and seeing how much form it finds. Using this in dimension 9, 500000 perfect forms were found and it is likely that the number is much higher hence uncomputable. If the number is not too large, then it may be possible to prove that the list is complete by solving those hard dual description problems.