ON CERTAIN COXETER LATTICES WITHOUT PERFECT SECTIONS

ANNE-MARIE BERGÉ

Abstract. In this paper, we compute the kissing numbers of the sections of the Coxeter lattices 𝔸n^{\frac{n+1}{2}} , n odd, and in particular we prove that for n ≥ 7 they cannot be perfect. The proof is merely combinatorial and relies on the structure of graphs canonically attached to the sections.

1. Introduction

A problem of recent interest is to construct integral perfect lattices with odd norm. By lattice we mean an additive subgroup L of a Euclidean space (E, ·) which is additively generated by some ℝ-basis for E. Such a lattice is integral if the inner product x · y takes integral values on it. The norm of a lattice L is the minimal value M of x · x for x ∈ L, x ≠ 0, and the vectors ±x ∈ L for which x · x = M are the minimal vectors of L. Their number 2s is the kissing number of L, terminology which refers to the sphere packing classically associated to the lattice L.

Perfect lattices arise in determining the densest lattice packing of spheres. A lattice L is perfect if it is uniquely determined up to similarity by the coordinates of its minimal vectors in one of its ℤ-bases. In 1877 Korkine and Zolotareff proved that all lattices whose packing density is a local maximum (extreme lattices) are perfect. They also proved that a perfect lattice can be rescaled so as to be integral, and that its kissing number 2s satisfies

s ≥ \frac{n(n + 1)}{2} ,

where n = dim E. All similarity classes of perfect lattices are now known up to dimension 7. From dimension 8 onwards, the complete classification seems out of reach. Voronoi’s algorithm for perfect forms produced at this date 10916 inequivalent forms of dimension eight (for a catalogue, see http://www.math.u-bordeaux.fr/martinet/).

An intriguing property of this list is that it contains no integral lattice of odd norm. It has recently been proved by Martinet and Venkov that the lattice P_{7}^{2} (in the notation of [4]) is the unique integral perfect lattice of dimension 2 ≤ n ≤ 9 having norm 3 ([7]). Their method consists in finding for the kissing number of integral lattices of norm 3 an upper bound strictly inferior to n(n + 1). Note that a first 10dimensional example of a perfect lattice having odd norm (namely 11) was recently constructed by Martinet (see [3], Section 4).

A natural method to construct integral perfect lattices having odd norm would consist in taking sections of a known one that contain a great number of its minimal vectors. About this method by sections, note that the algorithms of Batut and Martinet to “X-ray” integral lattices ([1]) showed that out of the known perfect lattices of dimension 3 ≤ n ≤ 8, P_{7}^{2} is also the unique one without perfect sections of dimension > 1.

This remarkable lattice P_{7}^{2} belongs to an infinite sequence of perfect lattices with odd norm (when rescaled to be integral). This sequence is part of a family that Coxeter derived from the root lattices 𝔸_{n} (see [6], Section 5.2): for any dimension n ≥ 1 and any divisor q of n + 1 the lattice 𝔸_{n}^{q} is the unique sublattice of the dual lattice 𝔸_{n}^{∗} that contains 𝔸_{n} to index q. For n > 5 and q < \frac{n+1}{2}, all these lattices have the same norm as 𝔸_{n}, and are therefore perfect (and even extreme) with even norm when rescaled so as to be integral. For q = \frac{n+1}{2} (n odd, n ≥ 5), the Coxeter lattices are extreme too but with norm \frac{2n−2}{n+1} < 2, and their primitive integral copy has odd norm if and only if n ≡ 3 mod 4. The aim of this paper is to X-ray these lattices. In particular, as a direct consequence of the combinatorial Theorem 2 (stated and proved in Section 4), we find that for n ≥ 7, any section of L = 𝔸n^{\frac{n+1}{2}} of dimension r, 1 < r < n, contains at most r(r − 1) + 2 < r(r + 1) minimal vectors of L. This enables us to extend to every odd dimension the property of “emptiness” noticed for the lattice P_{7}^{2} ∼ 𝔸_{7}^{4}:

Theorem 1. In every odd dimension n ≥ 3, the Coxeter lattice 𝔸n^{\frac{n+1}{2}} has no perfect section of the same norm in dimension > 1, except the lattice 𝔸_{5}^{3} which possesses 15 planar hexagonal sections.

In Section 2 we give a description of the lattice 𝔸n^{\frac{n+1}{2}} which leads to a combinatorial approach of the determination of its sections with best kissing number; this combinatorial problem is interpreted in Section 3 in terms of graphs, and solved in Section 4.

I want to thank J. Martinet for the motivation of this work, and the Reviewers for helpful suggestions and corrections.

2. A conjecture of Martinet.

Let E be a Euclidean space of dimension n, and let (e_{1}, ⋯, e_{n}) be a basis for the dual lattice 𝔸_{n}^{∗} with Gram Matrix

\frac{1}{n+1} ( \begin{matrix}n & −1 & −1 & ··· & −1 \\ −1 & n & −1 & ··· & −1 \\ · & · & · & ··· & · \\ −1 & −1 & −1 & ··· & n \end{matrix} ) ;

the minimal vectors of 𝔸_{n}^{∗} are the ±e_{i}, 0 ≤ i ≤ n, where e_{0} = −(e_{1} + e_{2} + ⋯ + e_{n}). One possible definition of the Coxeter lattice is

𝔸n^{\frac{n+1}{2}} = \{x_{1}e_{1}+x_{2}e_{2}+⋯+x_{n}e_{n} | (x_{i}) ∈ ℤ^{n} and ∑_{i} x_{i} ≡ 0 mod 2\} ,

as the right-hand side defines a sublattice of index 2 in 𝔸_{n}^{∗} containing the root lattice 𝔸_{n} = ⟨e_{i} − e_{0}, 1 ≤ i ≤ n⟩. It then has norm \frac{2n−2}{n+1} and its minimal vectors are ±(e_{i} + e_{j}), 0 ≤ i < j ≤ n. So, to establish Theorem 1 we shall bound the number of these vectors contained in a given strict subspace of E, discarding its Euclidean structure.

In the following, E_{n} is a real vector space of dimension n ≥ 2 equipped with a basis (e_{1}, e_{2}, …, e_{n}). Put

e_{0} = −(e_{1} + e_{2} + ⋯ + e_{n}) .

For a subspace F of E_{n} we consider its subset

S_{F} = F ∩ {e_{i} + e_{j}, 0 ≤ i < j ≤ n},

with cardinality

s_{F} = |S_{F} | .

Example. A subspace F of E_{n} is said canonical if it is spanned by some vectors e_{i}, 0 ≤ i ≤ n. For a canonical subspace F ⊂ E_{n} of rank r (1 ≤ r ≤ n − 1) we have s_{F} = \frac{r(r−1)}{2} if r ≠ n − 1 and s_{F} = \frac{r(r−1)}{2} + 1 if r = n − 1. Indeed, up to permutations by the symmetric group S_{n+1} we may assume F = ⟨e_{0}, e_{1}, …, e_{r−1}⟩. It then contains the \binom{r}{2} vectors e_{i} + e_{j}, 0 ≤ i < j ≤ r − 1, and no more except if r = n − 1, when we must add the vector e_{n−1} + e_{n} = −e_{0} − e_{1} + ⋯ − e_{n−2}.

For any dimension n ≥ 3 and any integer r, 1 ≤ r ≤ n − 1, we define

s_{n}(r) = max_{F ⊂E_{n}, dim F =r} s_{F} .

Martinet ([5]) stated the following: Conjecture.

1. For r ≥ 5, s_{n}(r) is equal to either \frac{r(r−1)}{2} or \frac{r(r−1)}{2} + 1 according as r ≠ n − 1 or r = n − 1.

2. For n ≥ 5 and r ≥ 2, we have s_{n}(r) < \frac{r(r+1)}{2} except for (n, r) = (5, 2), where s_{5}(2) = 3.

The second part of this conjecture, applied to our lattice problem, implies Theorem 1, the value s_{5}(2) corresponding to the hexagonal sections of the lattice 𝔸_{5}^{3}, which are perfect indeed.

The conjecture will result of the actual determination of all values of s_{n}(r) and of the subspaces F which realize them. To state and prove these results, an interpretation in terms of graphs is needed.

3. Graphs associated with a subspace F of E_{n}.

The bounds of s_{F} are attained at subspaces F of E generated by their subsets S_{F}; from now on we only consider such subspaces.

Definitions 1. With a subspace F of E we associate the graph G = G_{F} of the relation e_{i} + e_{j} ∈ F: its vertex set is {0, 1, ⋯, n}, and two vertices i and j are joined if e_{i} + e_{j} lies in F.

To any basis B ⊂ S_{F} of F we attach the subgraph G_{B} ⊂ G_{F} obtained by keeping only the edges ij of G_{F} such that e_{i} + e_{j} ∈ B.

Our aim is to compare the number of edges s_{F} of G_{F} with the number of edges r = dim F of G_{B}.

Example. For a canonical subspace F of dimension r, 3 ≤ r ≤ n − 1, there is a basis B whose graph is a triangle linked to a path: for instance the vectors e_{0} + e_{1}, e_{1} + e_{2}, e_{2} + e_{0}, e_{2} + e_{3}, ⋯, e_{r−2} + e_{r−1} constitute a basis for F = ⟨e_{0}, …, e_{r−1}⟩.

[figure: •; •; •; •; •; •; •; •; ; n=7, s_{F} =16=\binom{6}{2}+1; •; •; •; •; •; •; •; •; •; ; n=8, s_{F} =15=\binom{6}{2}]

Fig. 1: graphs G_{B} and G_{F} for canonical subspaces of dimension 6 (the s_{F} − r edges of G_{F} ∖ G_{B} appear in dotted lines).

We now discuss the existence of cycles in the graphs G_{F} and G_{B}.

Lemma 1. 1. If the vertices i and j are connected in G_{F} by a path

of odd length, ij is an edge of G_{F}.

2. The graph G_{B} does not contain an even cycle of length ≥ 4.

3. If a connected component C of G_{F} contains an odd cycle, then all the vectors e_{i}, i ∈ C belong to F, and C is a complete graph.

Proof. By induction from the following relations, where i, j, k, l ∈ {0, 1, …, n}:

(e_{i} + e_{j}) = (e_{i} + e_{l}) + (e_{j} + e_{k}) − (e_{k} + e_{l}) ,

e_{i} = \frac{1}{2}((e_{i} + e_{j}) − (e_{j} + e_{k}) + (e_{i} + e_{k})) ,

e_{i} = (e_{i} + e_{j}) − e_{j}.

We can now characterize the canonical subspaces by their graphs.

Lemma 2. Let F be an r-dimensional subspace of E_{n} (3 ≤ r ≤ n−1). Then F is canonical if and only if its graph G_{F} contains a complete r-graph, i.e. a graph whith r vertices and \binom{r}{2} edges.

Proof. We have already seen that if F is canonical, its whole graph consists of a complete r-graph and a path of length 1 (resp. n + 1 − r isolated vertices) if r = n − 1 (resp. r < n − 1).

Conversely, suppose that there is in G_{F} a connected component C with |C| = r vertices and \binom{r}{2} edges. Since C is complete of order r ≥ 3, it contains at least one triangle; it follows from the third part of Lemma 1 that all e_{i}, i ∈ C belong to F. Since |C| = dim F, we conclude that F = ⟨e_{i}, i ∈ C⟩.

4. Calculation of s_{n}(r).

Linear type. Let F be a strict subspace of E_{n} and let G_{F} = ⋃_{C∈C} C the partition of its graph into connected components. We say that the component C ∈ C is of linear type if the subspace

F_{C} = ⟨e_{i} + e_{j} with ij edge of C⟩

of F admits a basis B_{C} whose graph is a path.

We say that F itself is of linear type if, apart from isolated vertices, every component of G_{F} is of linear type. We label the type by the sequence of the lengths of the paths, the zeros representing the isolated vertices.

For example, Fig. 2 shows the four possible graph structures for r = 2 (the graph of a basis B ⊂ ∪B_{C} appears in continuous lines).

[figure: •; •; •; •; ; n=3: s_{F} =4; •; •; •; •; •; ; n≠3 (ex n=4): s_{F} =2; \underbrace{•  •  • •  •  •}_{n=5: s_{F} =3}; \underbrace{•  • •  •  •}_{n≠5 (ex. n=4) s_{F} =2}]

Fig. 2: linear types [2], [2, 0, 0], [1, 1, 1] and [1, 1, 0]

Theorem 2 below shows in particular that the invariant s_{F} assumes its greatest value for subspaces which are either canonical or (in low dimension) of linear type.

Theorem 2. Let F be an r-dimensional (1 ≤ r ≤ n − 1) subspace of E_{n}. Then

1. For r ≥ 4, we have

s_{F} ≤ \{ \begin{matrix}\frac{r(r − 1)}{2}  if r ≠ n − 1, \\ \frac{r(r − 1)}{2} + 1 if r = n − 1, \end{matrix}  (1)

except for r = 4, n = 5, F of linear type [4] where s_{F} = 9. Equality in (1) holds only when F is either canonical or of one of the following linear types: r = 4: n ≥ 6, type [4, 0, 0, …] or n = 7, type [3, 1, 1]; r = 5: n = 7, type [5, 1]; r = 6: n = 7, type [6].

2. For r = 1, n ≠ 3: s_{n}(1) = 1 attained at type [1, 0, …], n = 3: s_{3}(1) = 2 attained at type [1, 1].

3. For r = 2, n ≠ 3, 5: s_{n}(2) = 2, at types [1, 1, 0, …] and [2, 0, …], s_{3}(2) = 4 attained at type [2], s_{5}(2) = 3 attained at type [1, 1, 1].

4. For r = 3,

n ≠ 5: s_{n}(3) = 4, attained at linear types [3, 0, 0, …] and [1, 1, 1, 1] (if n = 7), and at canonical hyperplanes (if n = 4);

n = 5: s_{5}(3) = 5 attained at type [3, 1].

Going back to Euclidean lattices we can interpret some maximal values of s in low dimensions. We first note that the value s_{3}(2) corresponds to square sections of the cubic lattice 𝔸_{3}^{2}, the set S_{F} consisting of two pairs of orthogonal vectors. The sections of 𝔸_{5}^{3} which realize the maximum s_{5}(2) = 3 (resp. s_{5}(4) = 9, resp. s_{5}(3) = 5) are similar to the perfect lattice 𝔸_{2} (resp. to 𝔸_{2} ⊗ 𝔸_{2}, resp. to the “fragile” lattice of cristallography, see [6], Section 9.5). In dimension 7, there are coincidences, due to the multiple embeddings of the lattice 𝔸_{7}^{4} ∼ 𝔼_{7}^{∗} into 𝔸_{7}^{∗}; for instance, canonical as well as linear type [6] hyperplanes correspond to sections of 𝔼_{7}^{∗} similar to the isodual lattice 𝔻_{6}^{+}. This phenomenon does not occur for n = 9.

The rest of the paper is devoted to the proof of Theorem 2. Let

G_{F} = ⋃_{C∈C} C

be the partition of the graph of F into connected components, where at most one C is complete with |C| ≥ 3 (by Lemma 2 it corresponds to the canonical subspace F_{C} = ⟨e_{i}, i ∈ C⟩ of F). For a component C ∈ C we denote by

c = |C| the number of vertices of C,

s_{C} the number of edges of C (or size of C),

r_{C} (rank of C) the dimension of F_{C} = ⟨e_{i} + e_{j}, ij edge of C⟩. (Of course for isolated vertices c = 1 and s_{C} = r_{C} = 0.)

For example there are three possible components of rank 3.

[figure: •; •; •; •; •; •; •; • •  •  •]

complete type (s_{C} = 3)  linear type (s_{C} = 4)  non-linear type (s_{C} = 3)

Fig. 3: connected components C such that r_{C} = 3

Contribution of a component. Lemma 2 settles this question for complete components. We now describe the other cases.

Lemma 3. Let C be a non-complete component of G_{F}, with c ≥ 2.

1. There exists an integer d_{C}, 0 ≤ d_{C} ≤ c − 2, d_{c} ≡ c mod 2, such that

s_{C} = \frac{c^{2} − d_{C}^{2}}{4} ≤ ⌊\frac{c^{2}}{4} ⌋ .

2. F_{C} admits a basis whose graph is a path linked to a star of degree d_{C} + 1, and its dimension is

r_{C} = \{ \begin{matrix}c − 1 if c ≤ n, \\ c − 2 if c = n + 1 (which requires n odd and d_{C} = 0). \end{matrix}

3. s_{C} = ⌊\frac{c^{2}}{4} ⌋ only if C is of linear type.

4. The following conditions are equivalent:

(i) ∑_{i∈C} e_{i} ∈ F_{C}

(ii) d_{C} = 0

(iii) C is of linear type with an even number of vertices.

Proof. 1. Since C is not complete, it does not contain odd cycles. It is thus bipartite (see [2], I.2, th. 4), and even by Lemma 1, C is a complete bipartite graph, i.e. there exists a partition C = V_{0} ∪ V_{1} of C such that ij is an edge of C if and only if i and j are in distinct sets V_{k}, as we now prove. Indeed, given i, j ∈ C, the lengths of two paths i—j are congruent modulo 2 (otherwise, they would form an odd cycle); then V_{0} and V_{1} are the equivalence classes for the equivalence relation iRj if i = j or if i and j are connected by an even path. Clearly two neighbours in C belong to distinct classes; conversely, if i and j are in distinct classes, there are connected by a path of odd length, and by Lemma 1, ij is an edge of C. We conclude that s_{C} = |V_{0}||V_{1}| = \frac{c+d_{C}}{2} \frac{c−d_{C}}{2} where d_{C} = ||V_{0}| − |V_{1}||; thus we recover Mantel’s bound ⌊c^{2}/4⌋ for graphs without triangles.

2. From Lemma 1 it follows that the subgraph G_{B} associated with any basis of F_{C} does not contain any cycle. Thus its connected components are trees, G_{B} = T_{1} ∪ T_{2} ∪ ⋯ ∪ T_{m} say. We then have r_{C} = ∑_{i}(|T_{i}| − 1) = |G_{B}| − m ≤ c − 1. Actually, in the case c = n + 1 (i.e. G_{F} = C), we must have r < n = c − 1, since otherwise F_{C} = E_{n} would be canonical. We now define for F_{C} a standard basis B_{C} whose graph is a tree depending only on d_{C}.

Put c = 2p + d_{C} so that the vertex classes of C have respectively p and p + d_{C} elements; up to permutation by S_{n+1} we may assume them to be

{2k−1, 1 ≤ k ≤ p} and {2k−2, 1 ≤ k ≤ p} ⋃{2p+k, 0 ≤ k ≤ d_{C} −1} .

Then the subspace F_{C} contains the following c − 1 vectors:

f_{i} = \{ \begin{matrix}e_{i−1} + e_{i} for 1 ≤ i ≤ 2p − 1, \\ e_{2p−1} + e_{i} for 2p ≤ i ≤ c − 1 . \end{matrix}

For any (λ_{i}) ∈ ℝ^{c−1} we have

∑_{i=1}^{c−1} λ_{i}f_{i} = λ_{1}e_{0} + ∑_{1}^{2p−2}(λ_{i} + λ_{i+1})e_{i} + (∑_{2p−1}^{c−1} λ_{i})e_{2p−1} + ∑_{2p}^{c−1} λ_{i}e_{i} .

For any λ ∈ ℝ we then have the equivalence

∑_{i=1}^{c−1} λ_{i}f_{i} = λ ∑_{i∈C} e_{i} ⇔ \{ \begin{matrix}λ_{i} = 0 if i ∈ \{1, ..., 2p − 1\} is even, \\ λ_{i} = λ if i ∈ \{1, ..., 2p − 1\} is odd \\ or if i ≥ 2p, \\ d_{C}λ = 0. \end{matrix} (^{∗})

If c ≤ n, the e_{i}, i ∈ C, are independent, thus from (^{∗}) with λ = 0 we obtain that the c − 1 vectors f_{i} are independent, and since r_{C} ≤ c − 1, they constitute a basis for F_{C}, whose rank is r_{C} = c − 1. If c = n + 1, we know that r_{C} ≤ c − 2, and the c − 1 vectors f_{i} must satisfy a non-trivial relation ∑_{1≤i≤c−1} λ_{i}f_{i} = 0. On the other hand, there exists, up to multiplication by a scalar, a unique non-trivial relation between the e_{i}, i ∈ C: e_{0} + e_{1} + ... + e_{n} = 0. Therefore, using (^{∗}) with λ ≠ 0, we obtain d_{C} = 0 and thus n = 2p − 1. Conversely, if d_{C} = 0, the n vectors f_{i} = e_{i−1} + e_{i}, i = 1, ..., n satisfy the “unique” relation f_{n} = −f_{1} − f_{3} − ... − f_{n−2}, and f_{1}, f_{2}, ..., f_{n−1} constitute a basis for F_{C} = F. Its graph is a path of c − 1 = n vertices (which does not span C).

3. It is clear from the previous parts of the lemma, as s_{C} attains Mantel’s bound if and only if d_{C} = 0 or 1.

4. It follows immediately from (^{∗}) with λ = 1.

We now compare Mantel’s bound ⌊\frac{c^{2}}{4} ⌋ to \binom{r_{C}}{2}. The differences \binom{r_{C}}{2} − ⌊\frac{(r_{C}+1)^{2}}{4} ⌋ and \binom{r_{C}}{2} − \frac{(r_{C}+2)^{2}}{4} are increasing functions of r_{C}. We can thus state the following.

Lemma 4. Let C be a non-complete component of G_{F} of positive rank. Its size s_{C} and rank r_{C} satisfy

s_{C} − \binom{r_{C}}{2} = \{ \begin{matrix}3 if (n, r_{C}) = (3, 2) or (5, 4), \\ 1 if (n, r_{C}) = (7, 6) or if r_{C} ≤ 3 (linear type), \\ 0 if C is complete, or if r_{C} = 3 (non-linear type) \\ or if r_{C} = 4 (linear type, n ≥ 6) , \end{matrix}

and s_{C} < \binom{r_{C}}{2} otherwise.

Right now, Theorem 2 is proved for subspaces F whose graphs contain exactly one component of positive rank. In particular these F realize the bounds s_{3}(2) (Fig. 2), s_{n}(4) (Fig. 4) and s_{7}(6) (Fig. 5).

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •]

Fig. 4: linear types [4] (s_{F} = 9) and [4, 0, 0] (s_{F} = 6)

[figure: •; •; •; •; •; •; •; •]

Fig. 5: linear type [6] (s_{F} = 16)

From now on, we suppose that the graph G_{F} = ⋃_{C∈C} C of F contains at least two components of positive rank.

Dimensions. Consider x = e_{i} + e_{j} ∈ S_{F}. The indices i and j belong to the same connected component C, and thus the vector x belongs to the corresponding subspace F_{C}. Since S_{F} spans F, we have F = ∑ F_{C}. We first discuss whether this sum is direct.

Lemma 5. We have r = ∑_{C} r_{C} − δ with δ = 0 or 1 , where δ = 1 if and only if all non-complete components C ∈ C have linear type and odd rank.

Proof. Note that for |C| ≥ 2 the typical vector of F_{C} can be written x_{C} = ∑_{i∈C} λ_{i}e_{i}. Since any relation of dependence between the e_{i} has the form λ(e_{0} + e_{1} + ... + e_{n}) = 0 for some λ ∈ ℝ, and since C is a partition of {0, 1, ..., n}, we have the following equivalence:

( ∑_{C∈C} x_{C} = 0, x_{C} ∈ F_{C}) ⟺ (∃λ ∈ ℝ | ∀C ∈ C : x_{C} = λ ∑_{i∈C} e_{i}) .

Using the last part of Lemma 3, we are left with two possibilities:

1) there is an isolated vertex or a non-complete component with invariant d_{C} ≠ 0: the above λ is null, and F = ⊕F_{C}.

2) every non-complete component C has order |C| ≥ 2 and invariant d_{C} = 0: then for all C ∈ C, the nonzero vector x_{C} = ∑_{i∈C} e_{i} belongs to F_{C}, and we have a non-trivial relation ∑ x_{C} = 0. As this is up to scale the only one, we have dim(∑ F_{C}) = ∑ dim F_{C} − 1.

Proof of Theorem 2. We have to compare the size s_{F} = ∑ r_{C} of G_{F} to the dimension r = ∑ r_{C} − δ of F.

Type [1, …, 1, 0, …, 0] case.: the graph G_{F} consists of 1 ≤ k ≤ \frac{n+1}{2} paths of length 1 and of n + 1 − k isolated vertices; it then has s_{F} = k edges, while by Lemma 5, r = k − δ, where δ = 1 if and only if there are no isolated vertices i.e. n = 2k − 1 = 2r + 1. Thus

s_{F} = r + δ = \{ \begin{matrix}r if n ≥ 2r, n ≠ 2r + 1 \\ r + 1 if n = 2r + 1 \end{matrix}

is < \binom{r}{2} if and only if r ≥ 4. In contrast, this linear type realizes the values s_{n}(1), s_{n}(2) (in particular s_{5}(2) = 3) and s_{7}(3).

General case: max_{C} r_{C} = r_{0} ≥ 2. From Lemma 4 we deduce

s_{F} = ∑ s_{C} ≤ ∑ \binom{r_{C}}{2} + k

where k denotes the number of components C of linear type and rank r_{C} ≤ 3. Now, writing ∑(r_{C}^{2} − r_{C}) = (∑ r_{C})^{2} − ∑ r_{C} − 2 ∑_{C≠C′} r_{C}r_{C′} where ∑ r_{C} = r + δ by Lemma 5, we obtain the inequality

\binom{r}{2} − s_{F} ≥ ∑_{C≠C′} r_{C}r_{C′} − k − δr ,  (3)

which, by Lemma 4, is strict if there is a non-complete component of rank r_{C} > 4.

If δ = 0, (3) implies s_{F} ≤ \binom{r}{2} (equality only for r = 3) as stated in Theorem 2. Indeed if k ≤ 2: ∑_{C≠C′} r_{C}r_{C′} − k ≥ r_{0} − k ≥ r_{0} − 2 ≥ 0, equality holding only for F of type [2, 1] (and r = 3); if k ≥ 3: ∑_{C≠C′} r_{C}r_{C′} − k ≥ r_{0}(k − 1) − k ≥ 2(k − 1) − k ≥ 1.

From now on we suppose δ = 1: all non-complete C ∈ C are of linear type with odd ranks. In particular, we have r_{0} ≥ 3. We write G_{F} = C_{0} ∪ C_{1} ∪ ⋯ ∪ C_{m} (m ≥ 1) with r_{0} ≥ r_{1} ≥ r_{m} ≥ 1 and ∑ |C_{i}| = n + 1.

We shall use for r + 1 = r_{0} + r_{1} + ⋯ + r_{m} and ∑ r_{C}r_{C′} = r_{0}r_{1} + ⋯ the estimations

r + 1 ≥ r_{0} + k − 1 ,  (4)
∑ r_{C}r′_{C} ≥ r_{0}(r + 1 − r_{0}) .  (5)

Note that the equality in (4) (resp. (5)) holds if and only if F is of linear type [3, 1, …, 1] (resp. m = 1). We then obtain the estimation

\binom{r}{2} − s_{F} ≥ M ,

with

M = (r − r_{0})(r_{0} − 2) − 2 ,

where r − r_{0} = r_{1} + ⋯ + r_{m} − 1 ≥ m − 1 ≥ 0 and r_{0} − 2 ≥ 1. We then have M ≥ −2. We even obtain M > 0 (i.e. s_{F} < \binom{r}{2}) if r − r_{0} ≥ 3. We now concentrate on the three cases 0 ≤ r − r_{0} ≤ 2.

(a) r = r_{0}: G_{F} = C_{0} ∪ C_{1}, with r_{1} = 1. If C_{0} is complete, F is a canonical hyperplane and s_{F} = \binom{r}{2} + 1 as asserted in Theorem 2. If C_{0} is linear of rank 3, 5, 7, …, it follows from Lemma 3 that s_{F} = 1+s_{C_{0}} is equal to 1 + (r_{0} + 1)^{2}/4 = 5, 10, 17, …, strictly smaller than \binom{r}{2} except for the cases [3, 1] (which realizes the maximum s_{5}(3)) and [5, 1] (which realizes s_{n}(5)), see figure 6.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •]

Fig. 6: linear types [3, 1] and [5, 1]

(b) r = r_{0} + 1: G_{F} = C_{0} ∪ C_{1} ∪ C_{2}, with r_{1} = r_{2} = 1. Since (5) is no more an equality, we obtain \binom{r}{2} − s_{F} ≥ M + 1 = r_{0} − 3 ≥ 0, where the equality requires that equality (4) holds, i.e. that F is of type [3, 1, 1], which indeed realizes the maximum s_{7}(4) = 6 (figure 7).

[figure: •; •; •; •; •; •; •; •]

Fig. 7: type [3, 1, 1]

(c) r = r_{0} + 2, i.e. r_{1} + ⋯ + r_{m} = 3. There are two occurrences of this situation: m = 3, r_{1} = r_{2} = r_{3} = 1, or m = 1, r_{1} = 3. In the first case, equality (5) does not hold. In the second case, (4) does not hold. Anyway, we have \binom{r}{2} − s_{F} ≥ M + 1 = 2r_{0} − 5 > 0.

This completes the proof of Theorem 2.

References

[1] C. Batut and J. Martinet, “ Radiographie des réseaux parfaits”, Experimental Math. 3 (1994), 39–49.

[2] B. Bollobás, Modern graph theory, Graduate texts in Mathematics 184, Springer-Verlag, Heidelberg, 1998.

[3] A.M. Bergé and J. Martinet, “ Symmetric Groups and Lattices”, Monatschefte für Math. 140 (2003), 179-195.

[4] J.H. Conway and N.J.A. Sloane, “ Low-dimensional lattices. III. Perfect forms”, Proc. Royal Soc. London A 418 (1988), 43–80.

[5] J. Martinet, personal communication.

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

[7] J. Martinet and B. Venkov, “On integral lattices having an odd minimum”, Algebra and Analysis, Saint-Petersburg 16,3 (2004), 198-237.

Keywords: Perfect lattice; kissing number; bipartite graph.

Anne-Marie Bergé berge@math.u-bordeaux.fr Laboratoire A2X Tel.: +33 (0)5 56 84 60 96 Mathématiques Fax: +33 (0)5 56 84 69 50 Université Bordeaux 1 351, cours de la Libération 33405 TALENCE Cedex FRANCE