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.
3 Answers
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.
-
$\begingroup$ Oh thanks a lot for this explanation. I am wondering what exactly are "comtiguous forms"? As I understood it from the thesis, they are neighbouring vertices (neighbouring perfect forms) to a certain vertex in the Ryshkov polyhedron. Since there are infinitely many vertices in the Ryshkov polyhedron, I thought that the algorithm would continue forever if there isn't a bound on the quadratic forms? So I'm wondering what I misunderstand here about the contiguous forms? Thanks. $\endgroup$– KapJan 6, 2012 at 2:33
-
$\begingroup$ However, what I essentially need for one of my lattice problems is to enumerate all positive definite forms $Q$ such that $e_j^T Q e_j \geq 1$, $j = 1 to k$, where each element in the $N$-dimensional integer vector $e_j$ is between $-M$ and $M$, where $M$ is some finite integer (i.e. the integer vectors are only inside a finite box). So I'm wondering for how large integers $M$, dimensions $N$ and number of constraints $k$, can I expect to manage this enumeration? Thanks. $\endgroup$– KapJan 6, 2012 at 2:42
-
$\begingroup$ Forgot to mention that what I know is that the forms $Q$ must always be uniquely determined by some of the inequalities of $e_j^T Q e_j \geq 1$, so basically I want to enumerate the perfect forms on that polyhedron given by those finite number of inequalities. $\endgroup$– KapJan 6, 2012 at 2:49
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.
