ON WEAKLY EUTACTIC FORMS

ANNE-MARIE BERGÉ AND JACQUES MARTINET (^{∗})

Abstract. We make precise some properties of the Hermite function in relation with Morse theory introduced by Avner Ash in his papers [Ash1] and [Ash2] and with the cellular decomposition of the space of positive definite quadratic forms. We also establish a link between Ash’s and Bavard’s mass formulae.

1. Introduction

The space Sym_{n}(ℝ) of n × n real symmetric matrices is equipped with the scalar product

⟨A, B⟩ = Tr(AB).

With any column vector x ∈ ℝ^{n} we associate the matrix x^{t}x ∈ Sym_{n}(ℝ), and for a symmetric subset S of ℝ^{n}, the perfection rank perf rk S of S is the dimension, often denoted by r, of the span V_{S} of x^{t}x, x ∈ S/± .

Let C ⊂ Sym_{n}(ℝ) be the open cone of positive definite matrices. With a matrix A ∈ C we associate the quadratic form Q

x ∈ ℝ^{n} ↦ ^{t}xAx = ⟨A, x^{t}x⟩ ,

its minimum min A on non-zero integral vectors, the set

S = S(A) = {x ∈ ℤ^{n} | ⟨A, x^{t}x⟩ = min A}

of its minimal vectors, and the (half) kissing number s = \frac{1}{2} |S|. We shall often denote by V_{A} the space V_{S(A)}. Set

K = {M ∈ C | min M ≥ 1}.

Let A ∈ ∂K (the boundary of K) be a matrix with minimum 1 and set of minimal vectors S = S(A). The cell C_{A} of A is the following subset of ∂K:

C_{A} = {M ∈ C | min M = 1 and S(M) = S} ,

with closure

\overline{C_{A}} = \{M ∈ C | min M = 1 and S(M) ⊃ S\} .

Key words and phrases. Quadratic forms, Eutaxy, Morse theory, (*) Laboratoire A2X (UMR 5465, FR 2254), C.N.R.S et Université Bordeaux 1 December 1st, 2005.

We say that the cell C_{A′} is below the cell C_{A} (notation: C_{A′} ≺ C_{A}) if S(A′) ⊂ S(A). The cell C_{A} is open in its closure \overline{C_{A}} = ∪_{C_{A}≺C_{A′}} C_{A′}. The cells and the faces of K are intimately related: the faces of K are the closures of the cells; see Proposition 2.2.

With A ∈ ∂K, we also associate its Voronoi domain D_{A}, the convex hull of the half-lines ℝ_{≥0} x^{t}x, x ∈ S(A). All matrices in a given cell C have the same Voronoi domain, that we denote by D_{C}. We shall see that given A ∈ ∂K, the map C ↦ D_{C} is a one-to-one correspondence between cells C ≺ C_{A} and the faces of the polyhedral cone D_{A}; see Lemma 2.1. Note that M belongs to the affine span of C_{A} if and only if ⟨M − A, x^{t}x⟩ is zero on x^{t}x, x ∈ S(A), i.e. if and only if M − A is orthogonal to D_{A}. Thus, the perfection rank of A is

dim D_{A} = \frac{n(n + 1)}{2} − dim C_{A} .

Eventually, recall that A is called weakly eutactic (resp. semieutactic, resp. eutactic) if there are real numbers (resp. non-negative numbers, resp. strictly positive numbers) a_{x}, x ∈ S, such that

A^{−1} = ∑_{x∈S/±} a_{x}x^{t}x .

In practice, we shall essentially consider well-rounded matrices (and cells), those whose minimal vectors span ℝ^{n}. Weakly eutactic matrices are well rounded; see Proposition 3.8 for a more precise statement.

Let

γ(A) = \frac{min A}{(det A)^{1/n}}

be the Hermite function. In [Ash1], Ash proves that the “packing function” P (A) = γ(A)^{−n} is a topological Morse function whose nondegenerate critical points are exactly the eutactic matrices A. In [B-M1] we proved that each cell contains at most one weakly eutactic matrix which (if any) is exactly the matrix at which the strictly convex function γ (or \frac{1}{det}) attains its minimum on the cell. Our first aim is to specify which kind of topological ordinary points are the weakly eutactic, non-eutactic matrices. We make use of the notions of semi- and weak eutaxy, which were introduced after Ash’s paper was written (in [C-S], 1988, and [B-M1], 1996, respectively).

Theorem 1.1. Let A ∈ ∂K be a matrix of minimum 1, with set of minimal vectors S. Let

H_{A} = {M ∈ Sym_{n}(ℝ) : ⟨M − A, A^{−1}⟩ = 0}

be the tangent hyperplane to the determinant surface at A, and define the open half-spaces

H_{A}^{+} = {M ∈ Sym_{n}(ℝ) | ⟨M − A, A^{−1}⟩ > 0} ,
H_{A}^{−} = {M ∈ Sym_{n}(ℝ) | ⟨M − A, A^{−1}⟩ < 0} .

Then:

(1) A is weakly eutactic if and only if its cell C_{A} is contained in H_{A}.

(2) A is semi-eutactic if and only if H_{A} supports K (i.e. K ⊂ \overline{H_{A}^{+}}).

(3) A is eutactic if and only if H_{A} supports K and K ∩ H_{A} = \overline{C}_{A}. More precisely, if A is weakly eutactic but not semi-eutactic, H_{A}^{−} contains a cell below that of A, and if A is semi-eutactic but not eutactic, H_{A} contains a cell strictly below that of A, and indeed a unique maximal one, namely the relative interior of K ∩ H_{A}.

[Note that an example of a matrix A with H_{A} supporting K but K∩H_{A} ⫌ \overline{C_{A}} was given by Ash in [Ash1] (it is the unique semi-eutactic, non-eutactic matrix for n ≤ 4).]

Our second aim is to study the connection between the two known “mass formulae with signs” which occur in our context (Ash, [Ash2]; Bavard, [Bv]). Both formulae take the form (for n ≥ 2)

∑_{C/∼} \frac{(−1)^{dim C}}{|Aut^{+}(C)|} = χ(SL_{n}(ℤ)) ,

but have distinct ranges of summation: all well-rounded cells up to equivalence in Bavard’s formula, only those which contain a eutactic form in Ash’s formula; see Section 3. (The right hand side is equal to −\frac{1}{12} for n = 2 and to 0 for n ≥ 3.) We remark that on a well-rounded cell without a weakly eutactic matrix, inf_{C} γ is attained at a unique matrix A ∈ ∂C. We shall prove that this matrix is weakly eutactic, but not eutactic. Consequently, the difference of the left-hand sides of the formulae above may be written in the form

∑_{A} ∑_{C/∼} \frac{(−1)^{dim C}}{|Aut^{+}(C)|} = 0 ,

where A runs through the set of (equivalence classes of) weakly eutactic, non-eutactic matrices, and C through the set E_{A} of cells such that inf_{C} γ is attained on A. This strongly suggests the following theorem:

Theorem 1.2. For every weakly eutactic, non-eutactic matrix A,

∑_{C∈ E_{A}/∼} \frac{(−1)^{dim C}}{|Aut^{+}(C)|} = 0 .

This theorem results in dimensions n ≤ 5 from Batut’s paper [Bt] where he classifies cells and weakly eutactic matrices.

Theorem 1.1 is proved in Section 2, together with some complements. In Section 3, we reduce Theorem 1.2 to a purely combinatorial statement, that we prove by applying a generalized Euler formula for polytopes to an extension D′_{A} of the Voronoi domain D_{A}. Finally, a short fourth section is devoted to algorithmic remarks.

2. Weak eutaxy and Morse theory

We still consider a positive definite matrix A, that we scale to minimum 1 (i.e., A ∈ ∂K), and denote by S = S(A) its set of minimal vectors. Recall that the Voronoi domain of A is the convex hull D_{A} of the half-lines ℝ_{≥0} x^{t}x, x ∈ S. Thus A is weakly eutactic if A^{−1} lies in V_{A}, the real span of D_{A}, and semi-eutactic (resp. eutactic) if A^{−1} lies in D_{A} (resp. in the relative interior of D_{A}).

Lemma 2.1 below shows that there is a one-to-one correspondence between the set of non-zero faces of D_{A} and the set of cells C ≺ C_{A}.

Lemma 2.1. Let A ∈ ∂K with Voronoi domain D_{A}, and let C ≺ C_{A}. Then its Voronoi domain D_{C} is a face of D_{A}; more precisely, if C ≠ C_{A}, for every M ∈ C, the hyperplane H = (M − A)^{⊥} supports D_{A} and H ∩ D_{A} = D_{C}. Conversely, any face F of D_{A} is the Voronoi domain D_{C} of the cell C ≺ C_{A} of any matrix M = A+εF where F is orthogonal to a supporting hyperplane of C_{A} for F and ε > 0 is small enough. [In the correspondence above, the improper face D_{A} corresponds to C_{A}.]

Proof. Let C ⪵ C_{A}, M ∈ C, F = M − A and H = F^{⊥}. For x ∈ S(A), we have ⟨F, x^{t}x⟩ = ⟨M, x^{t}x⟩ − 1 ≥ 0 and equality holds if and only if x ∈ S(M). For v = ∑_{x∈S(A)/±} a_{x} x^{t}x ∈ D_{A} (a_{x} ≥ 0),

⟨v, F ⟩ = ∑_{x∈S(A)∖S(M)} a_{x} ⟨x^{t}x, F ⟩

vanishes if and only if the a_{x} are zero on S(A)∖S(M), i.e. if and only if v ∈ D_{M}. This shows that H supports D_{A} with corresponding face

D_{M} = D_{C}. [Replacing M − A by its orthogonal projection to V_{A}, we could have assumed that F ∈ V_{A}.]

Conversely, let F be a proper face of D_{A} with supporting hyperplane H = F^{⊥} for some F with ⟨F, D_{A}⟩ ≥ 0. Let M = A + εF where ε > 0 is small enough to ensure that S(M) ⊂ S(A). For x ∈ S(A), we have ⟨M, x^{t}x⟩ = 1 + ε⟨F, x^{t}x⟩ ≥ 1, with equality if and only if x^{t}x ∈ H∩D_{A} = F. Hence F is the Voronoi domain of the cell of M. □

Proposition 2.2. The closures of the cells are the faces of K. In particular, the smallest face of K containing a given matrix A ∈ ∂K is the closure \overline{C_{A}} of its cell.

Proof. (1) Let C = C_{A} the cell of a matrix A ∈ ∂K (thus min A = 1), and let S = S(A). Set F = \frac{1}{s} ∑_{x∈S/±} x^{t}x and let H = A + F^{⊥} the affine hyperplane through A orthogonal to F. For all M ∈ K, we have

⟨M − A, F ⟩ = \frac{1}{s} ∑_{x∈S/±}(⟨M, x^{t}x⟩ − 1) ≥ 0  (∗)

(because M ∈ K), which shows that K ⊂ \overline{H^{+}}, i.e. that H supports K. Moreover, (∗) shows that M belongs to H if and only if ⟨M, x^{t}x⟩ = 1 for all x ∈ S, i.e. min M = 1 and S(M) ⊃ S, or otherwise stated, that M belongs to \overline{C}. Finally, \overline{C} = K ∩ H is a face of K.

(2) Let F be a face of K, H a supporting hyperplane of K such that F = K ∩ H, and F ∈ H^{⊥} pointing towards K. Let A ∈ F, with Voronoi domain D_{A} and set of minimal vectors S. We first prove that F belongs to D_{A}.

Consider the cone Γ defined by the conditions ⟨ − F, v⟩ ≥ 0 and ∀ x ∈ S, ⟨x^{t}x, v⟩ ≥ 0. Let v ∈ Γ. For ε > 0 small enough, M = A + εv belongs to K (we have S(M) ⊂ S(A) because ε is small and ⟨M, x^{t}x⟩ = 1 + ε⟨v, x^{t}x⟩ ≥ 1 for all x ∈ S). Since H supports K, we have ⟨F, v⟩ ≥ 0, hence Γ is included in H. Since the dimension of Γ is not maximal, Voronoi’s principe fondamental ([V], § 8, p. 113) shows that the vectors −F, x^{t}x, x ∈ S satisfy a relation of the form ρ(−F) + ∑ ρ_{x} x^{t}x = 0 with non-negative, not all zero coefficients ρ, ρ_{x}. If ρ were zero, we would have ∑ ρ_{x} = ⟨A, ∑ ρ_{x}x^{t}x⟩ = 0 and ρ and the ρ_{x} would be zero. Finally, we obtain a relation

F = ∑_{x∈S} α_{x} x^{t}x

with non-negative α_{x}, which shows that F ∈ D_{A}.

Let F′ be the smallest face of D_{A} containing F (maybe, D_{A} itself), and let S′ = {x ∈ S | x^{t}x ∈ F′}. Actually F belongs to the relative interior of F′, and hence there is a relation F = ∑_{x∈S′} λ_{x} x^{t}x with strictly positive coefficients λ_{x}. Let M be a matrix in K. Then we have ⟨M − A, F ⟩ = ∑_{x∈S′} λ_{x} ⟨M − A, x^{t}x⟩ with all terms ⟨M − A, x^{t}x⟩ ≥ 0 (because M ∈ K), so that

H ∩ K = {M ∈ K | ∀ x ∈ S′, ⟨M − A, x^{t}x⟩ = 0} = {M ∈ K | S(M) ⊃ S′}

is the closure of the cell C′ ≺ C_{A} associated with the face F′. □

Remark 2.3. It results from the proof above that, with its notation, we have

A ∈ Int(H ∩ K) ⟺ H ∩ K = \overline{C_{A}} ⟺ F ∈ Int(D_{A}) .

[The notation Int stands for the relative interior.]

Proof of Theorem 1.1.

1. We now locate with respect to H_{A} the cell C_{A} of A or equivalently its affine span

Aff(C_{A}) = {M | ∀x ∈ S, ⟨M − A, x^{t}x⟩ = 0} = A + V_{A}^{⊥} .

(V_{A} is the span of D_{A}.) Then A is weakly eutactic if and only if A^{−1} belongs to V_{A}, i.e. (by taking the orthogonal complements) if and only if H_{A} ⊃ C_{A}, which proves the first statement of Theorem 1.1.

From now on, we assume that A is weakly eutactic.

2. (a) If A is semi-eutactic, write A^{−1} = ∑ a_{x} x^{t}x with non-negative a_{x}. Let M ∈ K. For every x ∈ S(A), we have ⟨M, x^{t}x⟩ ≥ 1, ⟨A, x^{t}x⟩ = 1, hence ⟨M − A, x^{t}x⟩ ≥ 0, whence ⟨M − A, A^{−1}⟩ ≥ 0, i.e. M lies in \overline{H_{A}^{+}}. This shows that H_{A} supports K.

(b) If A is not semi-eutactic, since the closed convex cone D_{A} is the intersection of its supporting half-spaces (see [Br], I, Th. 4.5), there exists a facet whose hyperplane separates A^{−1} and D_{A}, i.e. a vector F such that ⟨F, A^{−1}⟩ < 0 and ⟨F, x^{t}x⟩ ≥ 0 for all x ∈ S(A). The cell corresponding to the facet above by Lemma 2.1 is contained in H_{A}^{−}, and in particular, H_{A} does not support K.

From now on, we assume that A is semi-eutactic, and hence that H_{A} supports K.

3. (a) This time, we consider a eutaxy relation with strictly positive coefficients a_{x}. As in 2. (a), for any M ∈ K, we have ⟨M − A, A^{−1}⟩ = ∑_{x∈S} a_{x} ⟨M − A, x^{t}x⟩ with all ⟨M − A, x^{t}x⟩ ≥ 0. Hence,

M ∈ H_{A} ⟺ ∀ x ∈ S, ⟨M − A, x^{t}x⟩ = 0 ⟺ S(M) ⊃ S ,

which shows that K ∩ H_{A} = \overline{C_{A}}.

(b) If A is not eutactic, let F be a proper face of D_{A} containing A^{−1}. There exists a eutaxy relation A^{−1} = ∑_{x^{t}x∈F} a_{x} x^{t}x with non-negative a_{x}. The cell C ≺_{≠} C_{A} associated with F is contained in H_{A}: let M ∈ C; ⟨M −A, x^{t}x⟩ is zero if x^{t}x ∈ F, and then we have ⟨M −A, A^{−1}⟩ = 0. □

We end this section with some more precisions on semi-eutaxy.

Proposition 2.4. Suppose that A is semi-eutactic and let F be the smallest face of D_{A} containing A^{−1} (F = D_{A} if A is eutactic). Let

T = {x ∈ S(A) | x^{t}x ∉ F} .

Then for every eutaxy relation A^{−1} = ∑_{x∈S} a_{x} x^{t}x with all a_{x} ≥ 0, we have a_{x} = 0 on T, and there exists such a relation whose coefficients are strictly positive on S(A)∖T.

Proof. Let H be a supporting hyperplane of F and F ∈ H^{⊥} pointing to D_{A}. Write A^{−1} = B + C with

B = ∑_{x∈S∖T} a_{x} x^{t}x and C = ∑_{x∈T} a_{x} x^{t}x .

Then ⟨A^{−1}, F ⟩ = ⟨B, F ⟩ = 0, hence ⟨C, F ⟩ = ∑_{x∈T} a_{x} ⟨x^{t}x, F ⟩ = 0. Since the ⟨x^{t}x, F ⟩ are strictly positive on T, all a_{x} are zero on T.

Since the face F is minimal among those which contain A^{−1}, A^{−1} lies in the relative interior of F, which shows that it can be written as a linear combination of the x^{t}x, x ∈ S∖T with strictly positive coefficients. □

3. Ash’s and Bavard’s mass formulae with signs.

In this section, all matrices we consider are assumed to be scaled to minimum 1, so that the determinant and Hermite functions are connected by the relation det(M) = γ(M)^{−n}.

Note that in Ash’s original formula

∑_{A eut. /∼} \frac{(−1)^{i(A)}}{|Aut^{+}(A)|} = χ(SL_{n}(ℤ)) ,

the index i(A) of the eutactic matrix A is the dimension of the smallest face of K containing A, i.e. dim C_{A}, as stated in the introduction; see Proposition 2.2.

Lemma 3.1. A cell C is well rounded if and only if the determinant is bounded above on C.

Proof. Hadamard’s inequality (see [M], Theorem 2.2.1) shows that the determinant is bounded above on any well-rounded cell. Conversely, suppose that C is not well rounded. Up to integral equivalence, we may assume that the last coordinate of every x ∈ S is zero. Let M ∈ C, and for λ ≥ 1, denote by Q_{λ} the diagonal matrix with diagonal (1, …, 1, λ). Then M_{λ} = ^{t}Q_{λ}MQ_{λ} belongs to C and we have

det M_{λ} = λ^{2} det M →_{λ→∞} ∞ . □

We know that C is well rounded if and only if \overline{C} is compact, that the Hermite invariant γ has a minimum on \overline{C} if and only if C is well rounded (by the lemma above), and that this minimum is then attained at a unique matrix M ∈ \overline{C}, which is the unique weakly eutactic matrix in its cell ([B-M1], Th. 3.4 and 3.5).

Theorem 1.1 shows that given a weakly eutactic, non-eutactic matrix A there exist cells C ⪵ C_{A} contained in the closed half-space \overline{H_{A}^{−}}. (The notation C_{A}, H_{A}, H_{A}^{−}, … is that of the previous section.) For such cells, we prove (compare [Bt]):

Theorem 3.2. With the notation above, suppose A is weakly eutactic non-eutactic, and let C ⪵ C_{A} be a cell below the cell of A. Then the (unique) minimum on \overline{C} of the Hermite function is attained at A if and only if C is included in the closed half-space \overline{H_{A}^{−}}, and then C is well rounded and contains no weakly eutactic matrix.

Conversely, for every well rounded cell C without a weakly eutactic matrix, the minimum on \overline{C} of γ is attained at a weakly eutactic, noneutactic matrix A.

Otherwise stated, there is a partition of the set of well-rounded cells without a eutactic matrix, each part of which contains a unique cell having a weakly eutactic matrix. (The parts are the sets E_{A} for A weakly eutactic, non-eutactic.)

Proof. Let A be a weakly eutactic, non-eutactic matrix. Recall the well known formula in which F stands for any symmetric matrix:

det(A+tF) = det A (1+t⟨F, A^{−1}⟩+ \frac{1}{2} (⟨F, A^{−1}⟩^{2}−⟨F A^{−1}, F A^{−1}⟩) t^{2}+O(t^{3})) .

(Formulae of this kind occur e.g. in [Ash1], Corollary to Proposition 3.) Since A is positive definite and F is symmetric, the eigenvalues of F A^{−1} are real. Hence for small enough t > 0, we have det(A + tF) > det(A) if A + tF ∈ H_{A}^{+} and det(A + tF) < det A if A + tF ∈ \overline{H_{A}^{−}}.

Let C ⪵ C_{A}. Since A ∈ \overline{C} ∩ \overline{H_{A}^{+}} the first inequality above shows that if the determinant is smaller than det A on C, then C is included in \overline{H_{A}^{−}}. In the other direction, if C ⊂ \overline{H_{A}^{−}}, by the strict log-concavity of the determinant, the inequality det M < det A holds on the whole cell. By Lemma 3.1, C is well rounded, and since A belongs to \overline{C}, the unique maximum of the determinant on \overline{C} is attained at A.

Conversely, let C be a well-rounded cell without a weakly eutactic matrix. The unique matrix A at which the determinant attains its maximum on \overline{C} is weakly eutactic (because it is a maximum in its own cell) and is not eutactic: otherwise H_{A}^{+} would contain C, and this would imply det M > det A on C, a contradiction.

The last assertion is clear. □

We now establish some properties of the automorphism groups of cells. Recall that the automorphism group Aut(C) of a cell C is the stabilizer of C in GL_{n}(ℤ). We denote by Aut^{+}(C) the subgroup of Aut(C) consisting of positive automorphisms. For every M ∈ C, Aut(M) is a subgroup of Aut(C), and is equal to the whole group Aut(C) if M is weakly eutactic ([Bt], Corollary 2.6). This accounts for the connection between Ash’s original formula and the formulae stated in the introduction.

From now on, A stands for a weakly eutactic, non-eutactic matrix of minimum 1. Recall that E_{A} = {C ≺ C_{A} | inf_{C} γ = γ(A)}. We set G = Aut(A) and G^{+} = Aut^{+}(A).

Lemma 3.3. The group G = Aut(A) stabilizes E_{A}, and every equivalence between two cells of E_{A} is the restriction of an automorphism of A. In particular, for every C ∈ E_{A}, Aut(C) can be identified with a subgroup of G.

Proof. This is easily proved, using the fact that for every cell in E_{A}, A is the unique matrix at which inf_{C} γ is attained. □

The lemma above shows that in E_{A}, two cells are equivalent under GL_{n}(ℤ) (or SL_{n}(ℤ)) if and only if they belong to the same orbit under G (or G^{+}). Now for every C_{0} ∈ E_{A}, we have

\frac{1}{|Aut(C_{0})|} = \frac{1}{|Aut(A)|} ∑_{C∈E_{A}, C∼C_{0}} 1 .

Thus Theorem 1.2 is equivalent to Theorem 3.4 below:

Theorem 3.4. For every weakly eutactic, non-eutactic matrix A,

∑_{C∈E_{A}} (−1)^{dim C} = 0 ,

where E_{A} denotes the set of cells C such that inf_{C} γ is attained at A.

The proof of Theorem 3.4 will rely on Euler-type formulae for convex polytopes. Traditionally one writes Euler’s formula for a p-dimensional polytope P in the form

∑_{i=0}^{p−1} (−1)^{i}n_{i} = 1 − (−1)^{p}

where n_{i} denotes the number of i-dimensional proper faces. The consideration of the improper two faces P and ∅, of dimensions p and −1 respectively, allows us to write down this formula in a form which no longer depends on p, namely

∑_{i=−1}^{p} (−1)^{i}n_{i} = 0 .

This latter form has the following generalization:

Theorem 3.5. Let F_{1} and F_{2} ⫌ F_{1} be two faces of a given convex polytope P. Then

∑_{F_{1}⊂F⊂F_{2}}(−1)^{dim F} = 0 .

Proof. This is Theorem 16.4 of [Br]. □

The theorem above has an evident counterpart for cones in vector spaces, simply replacing the empty face by the origin, as one immediately sees by considering sections by a transverse hyperplane. Using this device, we easily dispose of the case of semi-eutactic matrices. Proof of Theorem 3.4 for semi-eutactic matrices. Proposition 2.4 and Lemma 2.1 show that if A is semi-eutactic but not eutactic, there is in H_{A} a unique maximal cell C ⪵ C_{A}, so that Theorem 3.5 applies directly, taking F_{1} = D_{C} and F_{2} = D_{A} and using the correspondence of Lemma 2.1. □

The existence of unique maximal cell C ≺ C_{A} in \overline{H_{A}^{−}} is no longer true for general weakly eutactic matrices. To handle this case, we first introduce an enlargement of the Voronoi domain.

Definition 3.6. Let D′_{A} be the convex hull of the Voronoi domain D_{A} of A and the half-line ℝ_{≥0} A^{−1}.

Since A is assumed to be weakly eutactic, A^{−1} belongs to the span of D_{A}. Hence D_{A} and D′_{A} ⊃ D_{A} have the same dimension, and D′_{A} = D_{A} if and only if A is semi-eutactic. As above, the consideration of a transverse hyperplane through A^{−1} allows us to apply Theorem 3.5 to D′_{A}.

In the remaining of this section, we assume that A is weakly eutactic, but not semi-eutactic. We first give a new characterization of the set E_{A}.

Proposition 3.7. Suppose that A is weakly eutactic, but not semieutactic, and let C ≺ C_{A}. Then C is contained in \overline{H_{A}^{−}} if and only if D_{C} is not a face of D′_{A}.

Proof. Suppose first that D_{C} is not a face of D′_{A}. If C ⊄ \overline{H_{A}^{−}}, there exists M ∈ C ∩ H_{A}^{+}. By Lemma 2.1, there exists a supporting hyperplane H of D_{A}, orthogonal to F = M − A, and such that H ∩ D_{A} = D_{C}. Since M ∈ H_{A}^{+}, we have ⟨F, A^{−1}⟩ > 0. We then have D′_{A} ⊂ \overline{H_{A}^{+}}, which shows that H supports D′_{A}. Let X′ = λA^{−1} + X ∈ D′_{A} (with λ ≥ 0 and X ∈ D_{A}). Then ⟨X′, F ⟩ = λ⟨A^{−1}, F ⟩ + ⟨X, F ⟩ (where ⟨X, F ⟩ ≥ 0 and ⟨A^{−1}, F ⟩ > 0) vanishes if and only if X′ = X belongs to D_{A} ∩ H = D_{C}. In other words, D′_{A} ∩ H = D_{C}, a contradiction.

Conversely, suppose that D_{C} is a face of D′_{A}, and let H′ be a supporting hyperplane for D′_{A} such that D′_{A}∩H′ = D_{C}. Let F′ ∈ H^{′⊥} such that ⟨F′, D′_{A}⟩ ≥ 0. By Lemma 2.1, for ε > 0 small enough, M = A + ε F′ lies in C. We have ⟨F′, A^{−1}⟩ ≥ 0, and indeed ⟨F′, A^{−1}⟩ > 0 (otherwise, A^{−1} would belong to D′_{A} ∩ H′ = D_{C}, and A would be semi-eutactic), hence M belongs to H_{A}^{+}, and the cell is not included in \overline{H_{A}^{−}}. □

Proof of Theorem 3.4 for weakly eutactic, non-semi-eutactic matrices. The cone D′_{A} is the convex hull of the extreme edges of D_{A} and of the half-line ℝ_{≥0} A^{−1}. Hence its faces are either faces of D_{A} or contain A^{−1}. We must show that the sum

Σ = ∑_{F face of D_{A} F not a face of D′_{A}} (−1)^{dim F}

is zero. To this end, we introduce the sums

Σ′ = ∑_{F face of D_{A} ; F face of D′_{A}}(−1)^{dim F} and Σ′′ = ∑_{\begin{matrix}F face of D′_{A} \\ A^{−1}∈F \end{matrix}}(−1)^{dim F} .

Applying thrice Euler’s generalized theorem3.5 to convenient cones and faces, we successively obtain Σ′′ = 0, Σ′ + Σ′′ = 0, and Σ + Σ′ = 0. □

To finish this section, we generalize to D′_{A} a well-known result of Voronoi, namely that all edges ℝ_{≥0} x^{t}x, x ∈ S(A) are extreme for D_{A}. We first prove a result about eutaxy relations:

Proposition 3.8. In any eutaxy relation A^{−1} = ∑_{x∈S(A)/±} a_{x} x^{t}x, the set of x ∈ S(A) with a_{x} > 0 spans ℝ^{n}.

Proof. Let E be the span of x ∈ S(A), a_{x} > 0, and let y ∈ E^{⊥}. We have

tyA^{−1}y = ∑_{x} a_{x} (^{t}yx)^{2} = ∑_{a_{x}<0} a_{x} (^{t}yx)^{2} .

The left hand side is ≥ 0 while the right hand side is ≤ 0, hence both are zero, which implies y = 0 since A^{−1} is positive definite. This shows that E = ℝ^{n}. □

Proposition 3.9. The extreme edges of D′_{A} are ℝ_{≥0} A^{−1} and the ℝ_{≥0} x^{t}x, x ∈ S(A).

Proof. It is clear that every extreme edge of D′_{A} belongs to the set {ℝ_{≥0} A^{−1}} ∪ {ℝ_{≥0} x^{t}x, x ∈ S(A)}. Conversely, since A is not semieutactic, ℝ_{≥0} A^{−1} is an extreme edge. Let now x ∈ S(A). If ℝ_{≥0} x^{t}x were not extreme, there would exist a relation

x^{t}x = λ A^{−1} + ∑_{y≠x} λ_{y} ^{t}yy

with non-negative coefficients λ, λ_{y}. By Voronoi’s theorem, λ is strictly positive, so that we have a eutaxy relation with exactly one positive coefficient (that of x^{t}x), which contradicts Proposition 3.8. □

4. Algorithmic remarks.

In the preceding two sections, the eutaxy property was studied using convexity. We now return to the notation introduced at the beginning of the introduction, considering eutaxy for a matrix A through the eutaxy coefficients a_{x}, x ∈ S(A)/±. A perfection relation on S is an equality ∑_{x∈S/±} u_{x} x^{t}x = 0. The set of perfection relations is a real vector space P_{S} of dimension s − r (r denotes the perfection rank of S), that we also denote by P_{A} when S = S(A). If A is weakly eutactic, the set R_{A} of eutaxy relations for A is an affine space over P_{A}.

To carry out calculations, we use an arbitrary basis for P_{A}, say, ∑_{x∈S/±} u_{x}^{(i)} x^{t}x = 0, i = 1, …, s − r. For short, we write these relations ∑_{x∈S/±} U_{x} x^{t}x = 0, where U_{x} ∈ ℝ^{s−r} is the column-matrix with components u_{x}^{(i)}.

We denote by S_{0} the set of vectors x ∈ S such that U_{x} = 0. When A is weakly eutactic, the eutaxy coefficients a_{x}, x ∈ S_{0} do not depend on the choice of a eutaxy relation. Thus the conditions a_{x} < 0, a_{x} = 0, a_{x} > 0 respectively define a partition S_{0} = S_{0}^{−} ∪ S_{0}^{0} ∪ S_{0}^{+} of S_{0}.

We intend to return somewhere else to the algorithmic aspects of extractions of cells and just state below without a proof our main result, which we shall use to construct cells of co-rank one below a given cell. As we shall see in Proposition 4.2, these cells play a crucial rôle in the determination of the set E_{A} (defined above Theorem 1.2).

Theorem 4.1. Let A , r , s, S_{0} and {U_{x}, x ∈ S} ⊂ ℝ^{s−r} be as above, and let x_{1}…. , x_{k} ∈ S (k ≥ 1) be k minimal vectors. The following conditions are equivalent:

(1) S′ = S∖{±x_{1}, …, ±x_{k}} is the set of minimal vectors for a cell C′ of perfection rank r − 1.

(2) The set {U_{x_{1}}, …, U_{x_{k}}} has rank k−1 and there exists a relation

∑_{i=1}^{k} ρ_{i} U_{x_{i}} = 0 with strictly positive coefficients ρ_{i}. Moreover, for any x ∈ S, there exist k − 1 ≥ 0 vectors x_{2}, …, x_{k} such that x_{1} = x, x_{2}, …, x_{k} satisfy the conditions above, and k is equal to 1 if and only if x ∈ S_{0}. □

The subset S_{0} of S plays a special rôle in various respects. First Theorem 3.4 has an easy proof for any weakly eutactic, non-eutactic matrices A with S_{0}^{−} ∪ S_{0}^{0} ≠ ∅: indeed, given x_{0} ∈ S_{0}^{−} ∪ S_{0}^{0}, cells below C_{A} belonging to \overline{H_{A}^{−}} occur in pairs (C, C′) with S(C) = S(C′) ∪ \{±x_{0}\}, which cancel in Theorem 3.4.

Actually, given C ⊂ \overline{H_{A}^{−}}, for any set x_{1}, …, x_{ℓ} ∈ (S_{0}^{−} ∪ S_{0}^{0})∖S(C), the cell C′ ≺ C with S(C′) = S(C)∖\{±x_{1}, …, ±x_{ℓ}\} belongs to \overline{H_{A}^{−}}. In particular, if there exists a eutaxy relation whose coefficients a_{x} are strictly positive for all x ∈ S∖S_{0}, then there is a unique maximal cell C′ ≺ C_{A}, namely the cell with minimal vectors S∖(S_{0}^{−}∪S_{0}^{0}). In general, such a cell does not exist when A is not semi-eutactic; see the end of this section.

Moreover, it is an experimental fact that very often, there exists a eutaxy relation R for which S^{−}(R) = S_{0}^{−} and S^{0}(R) = S_{0}^{0}. This is true for n ≤ 5 (because all cells with s > r contain a eutactic matrix whereas S = S_{0} if s = r), and for all perfect matrices with n ≤ 7.

However semi-eutactic matrices with T ⫌ S_{0} (see Proposition 2.4) exist in dimension 6, where an example is provided by a matrix with s = 21, r = 17 and equal non-zero eutaxy coefficients (so that the corresponding minimal vectors constitute a spherical 3-design), found by Elbaz-Vincent, Gangl and Soulé; see the talk by Elbaz-Vincent in [Ob].

Also, a perfect, semi-eutactic matrix with T ⫌ S_{0} is provided by a Laïhem lattice (a perfect 8-dimensional lattice having a perfect 7-dimensional section with the same minimum). Gram matrices for these lattices are displayed in [Bt-M] (use the command lh(i)), and Jaquet has listed those which are eutactic or semi-eutactic, non-eutactic (all are weakly eutactic since they are perfect). (Jaquet’s unpublished results have been recently confirmed by Cordian Riener ([Ri]), who has tested for eutaxy all perfect 8-dimensional lattices — Dutour, Schürmann and Vallentin have recently announced that the list of perfect, 8-dimensional lattices displayed in[Bt-M] is indeed complete.) There are exactly 21 semi-eutactic, non-eutactic Laïhem lattices, and for 20 of them, there exists a eutaxy relation for which S^{0} = S_{0}^{0}. For the remaining lattice, namely lh(958), with s = 40, S_{0} reduces to S_{0}^{+}, and there exist minimal vectors y, z with U_{z} + U_{y} = 0 and a eutaxy relation with coefficients a_{y} = a_{z} = 0. In this case, T = {±y, ±z}, and S∖T is the set of minimal vectors of the unique cell C ⪵ C_{A} contained in H_{A}.

Various examples of perfect, weakly eutactic, non-semi-eutactic matrices A such that H_{A}^{−} contains cells C with S(A)∖S(C) ⊄ S_{0} have been found among the Laïhem lattices. For instance, there are 154 Laïhem lattices with s = 38 among which 5 (e.g., lh(183)) provide such a cell.

Proposition 4.2. Let A be a weakly eutactic matrix and let C ⪵ C_{A}. Denote by C_{1}, …, C_{k} the cells of rank r − 1 such that C ≺ C_{i} ≺ C_{A}. Then

C ⊂ \overline{H_{A}^{−}} ⟺ ∀ i, C_{i} ⊂ \overline{H_{A}^{−}} .

Proof. If C ⊂ \overline{H_{A}^{−}}, then C_{i} ⊂ \overline{C} is also contained in \overline{H_{A}^{−}}.

Let us now prove the converse. For i = 1, …, k let F_{i} ∈ V_{A} be “facetmatrices” for C_{i} (see Lemma 2.1; we have ⟨F_{i}, x^{t}x⟩ = 0 for x ∈ S(C_{i}) and ⟨F_{i}, x^{t}x⟩ > 0 for x ∈ S(A)∖S(C_{i})). Then for any M ∈ C there exist, as we now prove, V ∈ V_{A}^{⊥} and α_{i} ≥ 0, i = 1, …, k such that

M = A + V + ∑_{i=1}^{k} α_{i}F_{i} .  (∗∗)

Indeed, let F_{i} = D_{C_{i}} (resp. F = D_{C}) be the facets of D_{A} (resp. the face of D_{A}) associated with the cells C_{i} (resp. with C); thus the F_{i} are the facets of D_{A} containing F. Denote by F the orthogonal projection to V_{A} of M − A, so that F^{⊥} is a supporting hyperplane of D_{A} for F; see Lemma 2.1. We must prove that F is a positive linear combination of the F_{i}. Let C = {v ∈ V_{A} | ∀ i, ⟨v, F_{i}⟩ ≥ 0} and let v ∈ C. Replacing v by a vector w of the form w = h v + (1 − h) u for some non-zero u ∈ F and a small enough h > 0, we may assume that v belongs to D_{A}. We then have ⟨v, F ⟩ ≥ 0, so that the cone defined by the inequalities ⟨v, F_{i}⟩ ≥ 0 and ⟨v, −F ⟩ ≥ 0 is contained in the hyperplane F^{⊥}. By Voronoi’s “fundamental principle” used in the proof of Proposition 2.2, −F and the F_{i} are positively dependent. Since the F_{i} are not positively dependent (the cone C has maximal dimension by [Br], Corollary 11.7), F is a positive combination of the F_{i}, say ∑_{i} α_{i} F_{i}, and (∗∗) holds taking V = (M − A) − F. By (∗∗), since V belongs to V_{A}^{⊥} and A^{−1} to V_{A}, we have ⟨M − A, A^{−1}⟩ = ⟨F, A^{−1}⟩ ≤ 0. □

We now make more precise the case when s = r + 1. (As above, r stands for the perfection rank of A.) There is (up to a scaling factor) a unique perfection relation ∑_{x∈S(A)/±} u_{x} x^{t}x = 0. We also chose a eutaxy relation A^{−1} = ∑_{x∈S(A)/±} a_{x} x^{t}x. The set S(A) can be written as a disjoint union S(A) = S_{0} ∪P^{+} ∪P^{−} where P^{+} = {x ∈ S(A) | u_{x} > 0} and P^{−} = {x ∈ S(A) | u_{x} < 0}. (Note that only the unordered set {P^{+}, P^{−}} is intrinsic.)

Proposition 4.3. Let A with s(A) = r + 1. A cell C ≺ C_{A} of rank r − 1 is of one of the following two types:

(1) S(C) = S(A)∖{±z}, z ∈ S_{0}.

(2) S(C) = S(A)∖{±x, ±y}, x ∈ P^{+}, y ∈ P^{−}.

The cell C is contained in H_{A}^{−} (resp. in H_{A}) if and only if z ∈ S_{0}^{−} (resp. z ∈ S_{0}^{0}) in case (1), and \frac{a_{x}}{u_{x}} < \frac{a_{y}}{u_{y}} (resp. \frac{a_{x}}{u_{x}} = \frac{a_{y}}{u_{y}}) in case (2).

Proof. The description of the possible cells C results directly from Theorem 4.1. Let F such that ⟨F, x^{t}x⟩ is zero if x ∈ S(C) and strictly positive if x ∈ S(A)∖S(C). We have

⟨F, A^{−1}⟩ = ∑_{±x∈S(A)∖S(C)} a_{x} ⟨F, x^{t}x⟩ and ∑_{±x∈S(A)∖S(C)} u_{x} ⟨F, x^{t}x⟩ = 0 .

Recall (Lemma 2.1) that the position of C with respect to H_{A} depends on the sign of ⟨F, A^{−1}⟩. In case (1), ⟨F, A^{−1}⟩ has the sign of a_{z}. In case (2), we have

⟨F, A^{−1}⟩ = (−u_{y} ⟨F, y^{t}y⟩) (\frac{a_{x}}{u_{x}} − \frac{a_{y}}{u_{y}})

so that ⟨F, A^{−1}⟩ has the sign of \frac{a_{x}}{u_{x}} − \frac{a_{y}}{u_{y}}. □

Remark 4.4. Removing from S(A) vectors of S_{0} preserves the eutaxy relation ∑_{x∈P^{+}∪P^{−}} u_{x}x^{t}x = 0, while removing one pair (±x, ±y), (x, y) ∈ P^{+} × P^{−} destroys it. Thus iterating Construction 4.2 we obtain two types of cells C ≺ C_{A} of perfection rank r_{C} = r − k, k ≥ 1: those obtained by removing from S(A) k pairs ±z of vectors of S_{0}, and those obtained by removing k + 1 pairs ±x, with at least one of them in P^{+} and one of them in P^{−}.

We now give an example for which H_{A}^{−} contains two maximal cells C ≺ C_{A}. We take for A a Gram matrix for the lattice nap(4118) (see [Bt-M] for the definition of the Napias lattices). Here, we have r = \frac{8(8+1)}{2} = 36 and s = 37.

In the following we denote by [R] the cell below C_{A} obtained by removing from S(A) the vectors of R, and we shall use this notation to describe the set E_{A} = \{C ≺ C_{A} and C ⊂ \overline{H_{A}^{−}}\}. The perfection relation of A reads ∑_{x∈P^{+}} x^{t}x − ∑_{x∈P^{−}} x^{t}x = 0, with |P^{+}| = |P^{−}| = 8 (we count the pairs ±x). With the notation of Proposition 4.3 the set S_{0}^{0} is empty, S_{0}^{−} consists of a single pair ±z_{0}, and the differences \frac{a_{x}}{u_{x}} − \frac{a_{y}}{u_{y}} for (x, y) ∈ P^{+} ×P^{−} are strictly positive except for three pairs (±x_{1}, ±y_{1}), (±x_{2}, ±y_{2}) and (±x_{1}, ±y_{2}), with respective values −44, −44 and −444. By Proposition 4.3, we see that among the 85 cells of rank 35 below C_{A}, only four are contained in \overline{H_{A}^{−}} (actually, in H_{A}^{−}): the cell [±z_{0}] of type (1) and the cells [±x_{1}, ±y_{1}], [±x_{2}, ±y_{2}] and [±x_{1}, ±y_{2}] of type (2). Let [R] ≺ C_{A} be a cell of rank ≤ 34. The cells of rank 35 above [R] are the [±z] and the [±x, ±y] with x, y, z ∈ R, x ∈ P^{+}, y ∈ P^{−} and z ∈ S_{0}. Thus by Proposition 4.2 the cell [R] belongs to E_{A} if and only if R is included in one of the sets {±z_{0}, ±x_{1}, ±x_{2}, ±y_{2}} or {±z_{0}, ±x_{1}, ±y_{1}, ±y_{2}}. [Indeed R must not contain both x_{2} and y_{1}, since the cell [±x_{2}, ±y_{1}] is contained in H_{A}^{+}.] Taking into account the general form of the cells below C_{A} (see Remark 4.4), we can complete the enumeration of the cells belonging to E_{A}. There are five cells of rank 34, namely [±z_{0}, ±x_{1}, ±y_{2}], [±z_{0}, ±x_{2}, ±y_{2}], [±x_{1}, ±x_{2}, ±y_{2}], [±z_{0}, ±x_{1}, ±y_{1}] and [±x_{1}, ±y_{1}, ±y_{2}]; two cells of rank 33, namely [±z_{0}, ±x_{1}, ±x_{2}, ±y_{2}] and [±z_{0}, ±x_{1}, ±y_{1}, ±y_{2}]; and no cell of rank ≤ 32. So, the set E_{A} contains 1+4+5+2 cells, and Theorem 3.4 enables us to check this enumeration:

1 − 4 + 5 − 2 = 0 .

References

[Ash1] A. Ash, On eutactic forms, Can. J. Math. 29 (1977), 1040–1054.

[Ash2] A. Ash, On the existence of eutactic forms, Bull. London Math. Soc. 12 (1980), 192–196.

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

[Bt-M] C. Batut, J. Martinet, A Catalogue of Perfect Lattices,

http://www.math.u-bordeaux.fr/ martinet/ .

[Bv] C. Bavard, Classes minimales des réseaux et rétractions géométriques équivariantes dans les espaces symétriques, J. London Mat. Soc. 64 (2001), 275–286.

[B-M1] A.-M. Bergé, J. Martinet, Sur la classification des réseaux eutactiques,

J. London Math. Soc. 53 (1996), 417–432.

[Br] A. Brønsted, An Introduction to Convex Polytopes, Graduate Texts in Mathematics 90, Springer-Verlag, Heidelberg (1983).

[C-S] J.H. Conway, N.J.A. Sloane, Low-Dimensional Lattices. III. Perfect Forms,

Proc. Royal Soc. London A 418 (1988), 43–80.

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

[Ri] C. Riener, personal communication.

[Ob] Oberwolfach Reports 2005, 1 (2005).

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

Anne-Marie Bergé & Jacques Martinet, A2X, Inst. Math., Université Bordeaux 1 351, cours de la Libération 33405 Talence cedex, France e-mail: berge@math.u-bordeaux.fr

martinet@math.u-bordeaux.fr