First edition: November 29th, 2004 Updated (J. M.) January 8th, 2010

File divided into two parts, January 16th, 2017 (see end of file)

WEB PAGES ON THE VORONOI ALGORITHM

C. BATUT, J. MARTINET (^{∗})

Abstract. The first 2 PARI-GP files below give the sets of vertices and edges of the Voronoi graph first in dimensions 2 to 6, then in dimension 7. The numerical data are extracted from Jaquet’s thesis [Ja]. The third file, based on Chapters 9 and 14 of [M], is devoted to minimal classes in dimensions 2 to 4. We present below a short account of Voronoi’s theory and minimal classes.

1. The perfection rank

Let S ⊂ ℝ^{n} (n ≥ 2) be a set of non-zero vectors viewed as columnmatrices, invariant under the symmetry x ↦ −x. Unless otherwise stated, we assume that S is finite, and we set s = \frac{1}{2} |S|. With S we associate the set of the s matrices M = X^{t}X for X ∈ S (note that X and −X define the same matrix M) and its span V_{S} in the space Sym_{n}(ℝ) of real, n × n symmetric matrices

[The symmetric matrices X^{t}X may be viewed as projection matrices: indeed, let E be an n-dimensional Euclidean vector space equipped with a basis B; if X is the set of components on B of some vector x ∈ E, then X^{t}X is the matrix in the \underline{pair} of bases (B^{∗}, B) of the orthogonal projection p_{x} ∈ End^{s}(E) to x.]

Definition 1.1. The rank in Sym_{n}(ℝ) of the set {X^{t}X}_{X∈S} is called the perfection rank of S and denoted by perf S The perfection rank of a lattice Λ or a positive definite quadratic form Q on ℝ^{n} (or the symmetric matrix A such that Q(X) = ^{t}XAX) is the perfection rank of its set of minimal vectors.

We say that Λ or Q (or A) is perfect if its perfection rank attains its maximal possible value, namely dim Sym_{n}(ℝ) = \frac{n(n+1)}{2}.

Key words and phrases. Perfect Lattices, Voronoï Graph, Minimal Classes.

(*) Université de Bordeaux, I.M.B, (UMR 5251), équipe A2X..

2. The facets

In what follows, the space Sym_{n}(ℝ) is equipped with the Voronoi scalar product ⟨M, N⟩ = Tr(MN). We consider a set S as above and we set r = perf S.

Definition 2.1. We say that a subset T of S is admissible if it is maximal among the subsets T′ of S with perf T′ = perf T.

We denote by W the orthogonal of V_{T} in V_{S}:

W = {M ∈ V_{S}, ∀X ∈ T, ⟨M, X^{t}X⟩ (= ^{t}XMX) = 0 .

We say that F ∈ W is a face vector for T in S the scalar products ⟨F, X^{t}X⟩ are strictly positive for all X ∈ S∖T.

The set C_{S}(T) of face vectors for T in S is a cone, called the positive cone of T in S.

In what follows, we restrict ourselves to the important case where V_{T} has codimension 1 in V_{S}. In this case, the cone C_{S}(T) is a half-line or is empty.

Definition 2.2. Suppose that C_{T} is not empty. An element of C_{T} is called a facet for T in S.

Note that any T such that s(T) = s(S) − 1 (and perf T < perf S ⇔ perf T = perf S − 1) is a facet. However, this special case is far from being general.

3. Contiguity

This time, we start with a positive definite quadratic form Q, with matrix A and minimum m. (If we are dealing with a lattice Λ, we chose a Gram matrix A for Λ and denote by Q the corresponding quadratic form.) We take for S the set S(Q) of minimal vectors of Q and we chose T as above.

Given F ∈ V_{S} and t ∈ ℝ, let R be the quadratic form with matrix F and let Q_{t} = Q+t∗R. For y ∈ ℤ^{n}, the function t ↦ Q_{t}(y) is increasing, constant or decreasing according to whether R(y) is positive, zero, or negative.

Chose F ∈ V_{T}^{⊥}. Then we have Q_{t}(x) = m for all x ∈ T. If C_{T} = ∅, then for every t ≠ 0, there exists y ∈ S such that Q_{t}(y) < m. Otherwise, for F ∈ C_{T} and t > 0 and small enough, we have min Q_{t} = m (and S(Q_{t}) = T).

Let θ ∈ (0, +∞) be the least upper bound of t for which min Q_{t} = m. If θ is finite, we can consider the form Q_{θ}.

Definition 3.1. The form Q_{θ} above is the contiguous (or neighbour) form of Q relative to T (or along F).

Then S(Q_{θ}) contains strictly T. Since T is maximal among the subsets of S of perfection rank r−1, we have perf S(Q_{θ}) ≥ r. The form R is proportional to the difference Q − Q_{θ}. Denoting by B the matrix of Q_{θ} and rescaling the parameter t, we may put the the matrices of Q_{t} in the interval 0 ≤ t ≤ θ in the form

A_{t′} = B + t′ (B − A) , 0 ≤ t′ ≤ 1

to be used in the PARI-GP files.

So far the theory has been established (by Voronoi) only for perfect forms. In this case, the contiguous form exists for all facets and is again perfect. Also, and this is the fundamental result of Voronoi, the contiguity graph is connected. The proofs can be read in [M], Chapter 7, Sections 1, 2, 3.

4. Voronoi Graphs: the Results

The references are those of the bibliography of [M], which can be found on this WEB page.

Perfect lattices were classified up to dimension 5 by Korkine and Zolotareff in [K-Z3] (1877). Their results were recovered by Voronoi ([Vo1], 1907), using the construction of the contiguity graph.

Dimension 6 was dealt with 50 years later by Barnes ([Bar4], 1957), who determined directly the contiguity graph. A direct classification of perfect lattices was produced later by Baranovskii and Ryshkov ([Br-R], 1985). However, they did not published the details of their proof.

Finally the results for dimension 7 were first published by Stacey ([Sta1], 1975), but her proof was not considered as definitive, in particular because the lattices she found were not tested for isometry. The first recognized proof was produced by Jaquet in his Neuchâtel thesis ([Ja2], 1991; see also [Ja5] for a published proof). The reference [Ja2] contains the complete data for dimensions 2 to 7.

In their Bordeaux PhD theses, M. Laïhem (1992), J.-L. Baril and H. Napias (19967) obtained a list of 10770 perfect lattices, which was completed a few months later by C. Batut to a list of 10916 perfect lattices; see [M] and the file “Perfection: An introductory paper about perfect lattices.” in this WEB page. To obtain the complete classification of 8-dimensional perfect lattices looked out of scope of any existing method. Nevertheless, M. Dutour Sikirić, A. Schürmann and F. Vallentin ([D-S-V]) were able to prove in 2005 that the list above is complete, by constructing the Voronoi graph. This Voronoi graph can be obtained on request from the authors.

The 48 perfect lattices in dimensions n≤7.

Dimension 1 2 3 4 5 6 7
Perfect 1 1 1 2 3 7 33
Edges  1 1 2 4 18 357

5. Voronoi Graphs: the Files

In the two PARI-GP files, devoted to dimensions 2–6 and 7 respectively, Gram matrices for the 47 perfect lattices in dimensions n from 2 to 7 are given as vectors pn[i].

For n = 2, 3, 4, 5, 6, the contiguous forms are displayed as a vector V n[j] with one index j for each edge of the contiguity graph with endpoint some pn[k] with k ≥ i.

For n = 7, the contiguous forms are displayed as a vector V 7[i][j] for n = 7, where the index i is that of a perfect form whose neighbour is equivalent to some p7[k] with k ≥ i, and there is one index j for each edge starting form p7[i]. However, the components of the vectors V 7[i] are such that j ≥ j_{0}, the least index for which the contiguous form is a p7[k] for some k ≥ i.

Finally, for n ≤ 6, the path A + t ∗ (B − A) defined by V n[j] is directly available using the command VRn[j].

As usual, the files contain other informations which can be read under an editor, for instance emacs.

End of File except for the reference list

Note. The former file from January 2010 cotained three more sections:

6. Minimal Classes and (Weak) Eutaxy.

7. Minimal Classes: the Results.

8. Minimal Classes: the Files.

The content of theses three sections has been extended in 2017, and is now part of the file domains.txt below.

The reference list below contains only five items. For the other papers cited in the text, see the updated reference list of [Mar] on this home page.

References

[Bt] C. Batut, Classification of quintic eutactic forms, Math. Comp. 70 (2001), 395–417.

[D-S-V] M. Dutour Sikirić, A. Schürmann, F. Vallentin, Classification of eight dimensional perfect forms, Electron. Res. Announc. Amer. Math. Soc. 13 (2007), 21–32.

[E-G-S] P. Elbaz-Vincent, H. Gangl, C. Soulé, Perfect Lattices, Homology of Modular Groups and Algebraic K-theory, Oberwolfach Reports 1/2005 (2005), 36–39.

[Ja] D-O. Jaquet, Énumération complète des classes de formes parfaites en dimension 7, Thèse, Neuchâtel (1991).

[This is reference [Ja2] of Section 4.]

[M] J. Martinet, Perfect Lattices in Euclidean Spaces, Grundlehren 327, Springer-Verlag, Heidelberg (2003). Other items are given in Section 4 above.