Journal de Théorie des Nombres de Bordeaux 00 (XXXX), 000–000

On extreme forms in dimension 8

par Cordian Riener

Résumé. Par un théoreme de Voronoi, un réseau est extrême si et seulement s’il est parfait et eutactique. La classification des réseaux parfaits a été récemment obtenue en dimension 8 ([5]). Il y a 10916 réseaux parfaits. En utilisant des méthodes de programmation linéaire, nous obtenons la liste de ceux de ces réseaux qui sont eutactiques. En petite dimension, presque tous les résaux parfaits sont également eutactiques. Ce n’est plus le cas à partir de la dimension 8 : il n’y a que 2408 réseaux extrêmes de dimension 8.

Abstract. A theorem of Voronoi asserts that a lattice is extreme if and only if it is perfect and eutactic. Very recently the classification of the perfect forms in dimension 8 has been completed [5]. There are 10916 perfect lattices. Using methods of linear programming, we are able to identify those that are additionally eutactic. In lower dimensions almost all perfect lattices are also eutactic (for example 30 out of the 33 in dimension 7). This is no longer the case in dimension 8: up to similarity, there are only 2408 extreme 8-dimensional lattices.

1. Introduction

A lattice Λ is a discrete subgroup of rank n of the Euclidean vector space ℝ^{n} endowed with a scalar product ( · ). For details on the theory of lattices we refer to Martinet’s book [7]. We note N(x) the squared norm of an element x of ℝ^{n}. The norm or minimum of Λ is defined as N(Λ) = min_{x∈Λ,x≠0} x · x and the set S(Λ) := {x ∈ Λ : x · x = N(Λ)} is the set of minimal vectors of Λ.

Given a family F of vectors x_{1}, ..., x_{n} ∈ ℝ^{n}, the Gram matrix of F is Gram(F) := ((x_{i}·x_{j})) and we call a em Gram matrix of Λ the Gram matrix of any ℤ-base B = (b_{1}, ..., b_{n}) of Λ. The determinant of such a matrix is the determinant det(Λ) of Λ. Given a pair (Λ, B), we attach to it the quadratic from q(x) = N(∑_{i} x_{i}b_{i}), which depends only on the isometry class of (Λ, B). This dictionary gives a one-to-one correspondence between similarity classes of lattices and equivalence classes over ℤ of quadratic forms having the same minimum.

One important invariant of these similarity classes was introduced by Hermite in 1845. It is defined as:

γ(Λ) = \frac{N(Λ)}{det(Λ)^{\frac{1}{n}}} .

Geometrically γ(Λ) is a measure for the density of the sphere packing attached to Λ. Its maximum γ_{n} := max_{Λ⊂E} γ(Λ), the so called Hermite constant, leads therefore to the densest lattice sphere packing in dimension n. Following the approach of Korkine and Zolotareff, we call a lattice extreme if γ(Λ) attains a local maximum in Λ, i.e., one has γ(Λ′) ≤ γ(Λ) for any Λ′ close enough to Λ. In order to find the local maxima of the Hermite function one uses the properties of perfection and eutaxy, which are defined as follows: with 0 ≠ x ∈ E we associate the rank one symmetric matrix P_{x} := xx^{t}. A lattice is called perfect if the P_{x}, x ∈ S(Λ) span the space of all symmetric matrices Sym_{n}. Let Λ be a lattice with Gram-Matrix A. A eutaxy relation for Λ is a set of coefficients λ_{x} ∈ ℝ, x ∈ S(Λ) such that A^{−1} = ∑_{x∈S(Λ)} λ_{x}P_{x}. A lattice is called weakly eutactic if there exists a eutaxy relation. Furthermore it is called semi-eutactic if the λ_{x} are ≥ 0 and eutactic if they may be chosen strictly positive. Note that perfection already implies weak eutaxy. Using the notions of perfection and eutaxy, Voronoi ([8]) has shown:

Theorem 1. (Voronoi) A lattice Λ is extreme if and only if it is both perfect and eutactic.

Using the algorithm developed by Voronoi himself, one can obtain a complete classification of all perfect lattices in a given dimension. This work has been carried out up to dimension 8. In the next section we will describe how to use methods of linear programming in order to decide whether a lattice is eutactic.

2. Eutactic perfect lattices

The perfect lattices of dimension 8 have been found by Bergé, Martinet and their students and very recently Dutour, Schürmann and Vallentin[5] have been able to show that this classification is complete. An interesting question still remains: Which are the eutactic forms within those 10916 perfect forms? In low dimensions almost all perfect lattices are also eutactic. Martinet conjectures in his book [7] that this no longer is the case from dimension 8 onwards. In order to transfer the question of eutaxy into the language of linear programming, we just present some simple facts about convex cones. Let E be a Euclidean vector space of dimension m. A set C ⊂ E is called a cone if for x, y ∈ C we have x + y ∈ C and furthermore αx ∈ C for 0 ≤ α.

Moreover C is called pointed if C ⋂(−C) = {0}. For X ⊂ E the set

cone (X) := {∑ a_{i}x_{i} : 0 ≤ a_{i}, x_{i} ∈ X}

is called the cone induced by X.If X is finite cone (X) is called polyhedral. For every convex cone C, we can form its dual cone, which is defined as

C^{∗} := {u ∈ E | ∀ x ∈ C : ⟨u, x⟩ ≤ 0}.

This is again a convex cone and if C is closed we have C = C^{∗∗}. If C := cone(x_{1}, .., x_{n}) is a polyhedral cone, the dual cone is just

C^{∗} := {y ∈ E | ⟨x_{i}, y⟩ ≤ 0 ∀ 1 ≤ i ≤ n}.

On the space Sym_{n} we consider the scalar product ⟨A, B⟩ := T r(AB). Now we want to express eutaxy and perfection in the language of cones. For this aim we give the following definition:

Definition 2. Let Λ ⊂ ℝ^{n} be a lattice. Then

D_{Λ} := cone (P_{x})_{x∈S(Λ)}

is called the Voronoi domain of Λ.

For a lattice Λ we can now translate the notions of perfection and eutaxy:

(1) A lattice Λ is perfect if D_{Λ}^{∗} is pointed.

(2) A lattice Λ is semi-eutactic if A^{−1} ∈ D_{Λ} and eutactic if A^{−1} ∈ ri(D_{Λ})

(ri stands for the relative interior). Now to say that a perfect form is only weakly eutactic is equivalent to say that A^{−1} is not inside the Voronoi domain. This is the case when A^{−1} can be separated from the Voronoi domain by a hyperplane. We have the following:

Theorem 3. Let C be a closed cone in E. Then p ∈ V \C if and only if there exists u ∈ C^{∗} such that ⟨p, u⟩ > 0.

Now the distinction between semi-eutaxy and eutaxy necessitates that we winnow the interior and the boundary of a convex cone:

For u ∈ E we define the hyperplane H(u) := {x ∈ V |⟨u, x⟩ = 0} and the half space H^{−}(u) := {x ∈ V |⟨u, x⟩ ≤ 0}. We say that such a hyperplane is a supporting hyperplane if H(u)∩C ≠ ∅ and C ⊂ H^{−}(u). Such a support is called non-trivial if C ∩H ≠ C. If C is a polyhedral cone, only the boundary points can be in a hyperplane that defines a non-trivial support. Thus we have

Theorem 4. Let C be a closed cone then x ∈ int(C^{∗}) if and only if H(u) is a supporting hyperplane and x ∈ H(u) implies u ∈ C^{⊥}.

With these properties of polyhedral cones we want to decide the question whether a perfect lattice is eutactic or not using linear programming methods. Linear programming (abbreviated by (LP)) is a technique to find a maximizer or minimizer of a linear function subject to linear inequalities More precisely:

Definition 5. Let A ∈ ℝ^{m×n} a m × n matrix, c ∈ ℝ^{n} and b ∈ ℝ^{m}. A linear problem (LP) is of the form

c^{tr}x → max
subject to Ax ≥ b

The convex polyhedron P := {x ∈ ℝ^{n}|Ax ≥ b} is called the feasible region.

A efficient algorithm to solve such problems is the so called Simplex Algorithm introduced by Danzig [4]. It uses the fact that among the feasible solutions of an (LP), there is always one that is a vertex of P. Using the separation theorems for polyhedral cones, we are now able to investigate the list of perfect lattices in dimension 8. To this end we proceed in three steps:

(1) We try to find a separating hyperplane. If we find one, the lattice is only weakly eutactic and we are done

(2) When we do not find a separating hyperplane, we look for a supporting hyperplane which contains A^{−1}. If there is such a supporting hyperplane, the lattice is semi-eutactic.

(3) If we are not able to find neither a separation nor a supporting hyperplane, the lattice must be eutactic. To prove this, we look for a eutaxy relation.

To simplify the notation of the upcoming LPs, we will use a ∈ ℝ^{d} for the point that represents A^{−1} and p_{1}, ..., p_{s} for the points that represent the P_{x}. In order to deal with the problem of the first step, we consider the following program:

x · a → max
subject to x · p_{i} ≤ 0 ∀ i = 1, ..., s
x · a ≤ 100

The last inequality is artificially added in order that the LP should have a bounded solution. If we find any solution vector x^{∗}, for which the optimal solution of the LP is strictly positive, we get a separating hyperplane, thus the lattice is not semi-eutactic and therefore also not eutactic. For the lattices that passed the first test we now want to sort out those that are only semi-eutactic. For this aim, we investigate the following (LP):

∑ x · p_{i} → min
subject to  x · p_{i} ≤ 0 ∀ i = 1, ..., s
x · a = 0
∑ x · p_{i} ≥ −100

Here again the last inequality was added to ensure the existence of a bounded solution. As for perfect lattices D_{Λ}^{∗} is pointed, the existence of an optimal solution which is strictly negative provides a supporting hyperplane that contains A^{−1}. The lattice thus is only semi-eutactic. The lattices that passed these two tests are expected to be eutactic. In order to prove this, we look for a eutaxy relation. As in the last section the Matrix B := (p_{i})_{i=1}^{s} is the matrix whose columns are the points p_{i}. The eutaxy relation therefore has the form: a = Bx, where x should be a vector with strictly positive components. In order to find such a vector x, we subtract from each of its components a slack variable λ. We then try to maximize the value of λ, in other words we look at the following LP:

λ → max
subject to  Bx = a
x_{i} − λ ≥ 0 ∀ i = 1, .., s

If the lattice we investigate is eutactic, the optimal value of λ must be strictly positive and then the vector x provides a eutaxy relation.

3. Results

There are many implementations of the simplex algorithms available on Internet. We decided to use the one that is implemented in the lrspackage of David Avis[1]. Since it works with exact arithmetics, we can be sure to avoid rounding errors. On http://math.u-bordeaux.fr/ martinet, we provide the results of the investigation. For each of the 10916 perfect lattices we give there a separating hyperplane if the lattice is only weakly eutactic, both a supporting hyperplane and a semi-eutaxy relation for the ones that are semi-eutactic and finally a eutaxy relation for the ones that are extreme. In the following table we summarize the results for dimension 8. We order them by increasing half-kissing numbers s := \frac{1}{2}|S(Λ)|.

References

[1] D. Avis, The lrs homepage, http://cgm.cs.mcgill.ca/ avis/C/lrs.html.

[2] Ch. Batut, J. Martinet, A2x-Web-Pages on Lattices, http://math.u-bordeaux.fr/ martinet/.

[3] Ch. Batut Classification of quintic eutactic forms, Math. Comp. 70 (2001), 395-417.

[4] G. Danzig, Linear Programming and Extensions, Princeton University Press (1963).

[5] M. Dutour, A. Schürmann, F. Vallentin, Classification of eight-dimensional perfect forms, preprint (2005).

[6] D.-O. Jaquet-Chiffelle, Énumération complète des classes de formes parfaites en dimension 7, Ann. Inst. Fourier 43 (1993), 21-55.

[7] J. Martinet, Perfect Lattices in Euclidean Spaces, Springer-Verlag, Heidelberg (2003).

[8] G. Voronoi, Nouvelles applications des paramètres continus à la théorie des formes quadratiques: 1. Sur quelques propriétés des formes quadratiques parfaites, J. reine angew. Math. 133 (1908), 97-178.

s  Extreme Semi-Eutactic Only Perfect Total
36 858  8  5388  6254
37 513  1  1519  2033
38 471  6  1021  1498
39 212  1  288  501
40 156  6  180  342
41 71  3  47  121
42 44  1  24  69
43 19  0  7  26
44 20  0  4  24
45 11  1  1  13
46 10  1  1  12
47 4  0  0  4
48 4  0  0  4
49 1  0  0  1
50 2  0  0  2
51 3  0  0  3
52 1  0  0  1
54 4  0  0  4
56 1  0  0  1
58 1  0  0  1
71 1  0  0  1
120 1  0  0  1
total 2408  28  8480  10916

Table 1. Results in dimension 8

Cordian Riener Universität Ulm Abteilung Reine Mathematik D-89069 Ulm

E-mail : cordi777@gmx.de