ON LATTICES OF MAXIMAL INDEX TWO

ANNE-MARIE BERGÉ

Abstract. The maximal index of a Euclidean lattice L of dimension n is the maximal index of the sublattices of L spanned by n independent minimal vectors of L. In this paper, we prove that a perfect lattice of maximal index two which is not provided by a cross-section has dimension at most 5.

1. Introduction

Korkine and Zolotareff proved that an n-dimensional lattice containing at least \frac{n(n+1)}{2} pairs ±x of minimal vectors, and spanned by any subset of n independent minimal vectors, is similar to the root lattice 𝔸_{n}.

Here we consider in an n-dimensional Euclidean space E well rounded lattices, i.e. lattices L the minimal vectors of which span E. To such a lattice L, Martinet attached some invariants related to the sublattices M of L generated by n independant minimal vectors of L, in particular the set of possible indices [L : M], and for a given sublattice M, the group structure of the quotient L/M.

The maximal index of L is :

max_{M}[L : M] ,

where M runs through sublattices of L spanned by n independent minimal vectors of L. (Korkine-Zolotareff’s result deals with lattices of maximal index 1.)

In this paper, we consider lattices with maximal index 2. For such lattices, the notion of length introduced in [M] can be defined as follows:

The length ℓ ≤ n of a lattice L of maximal index 2 is the minimal cardinality |X| of a set X of independent minimal vectors of L such that ∑_{x∈X} x ≡ 0 mod 2L. □

Up to dimension 7, there are six perfect lattices with maximal index 2: in Conway-Sloane’s notation (see [C-S] p. 56), P_{4}^{1} and P_{5}^{1} have length ℓ = 4, while P_{5}^{2}, P_{6}^{5}, P_{6}^{6} and P_{7}^{32} have length ℓ = 5. In dimension 8, a computation by Batut and Martinet based on the classification result by Dutour-Schürmann-Vallentin (see [D-S-V]) showed that no 8-dimensional perfect lattice has maximal index 2.

Key words and phrases. Euclidean lattices, perfection Université de Bordeaux, UMR 5251, Bordeaux, F-33000, France .

In [M], Martinet conjectured that a perfect lattice of maximal index 2, generated by its minimal vectors, has dimension at most 7.

In the present work, we prove this conjecture in the case ℓ = n.

Theorem 1.1. A lattice of dimension n ≥ 6, of maximal index 2 and length ℓ = n, has less than \frac{n(n+1)}{2} pairs ±x of minimal vectors, and in particular is not perfect.

Actually, we shall obtain in 8.1 an asymptotic bound

s ≤ \frac{2n^{2}}{9}

for the number s of pairs of minimal vectors much smaller than the (lower) perfection bound \frac{n^{2}}{2} .

2. Notation

Let L be a lattice of dimension n ≥ 6, maximal index 2 and length n. Let S = S(L) and s(L) = \frac{|S(L)|}{2} denote the set and number of pairs ±x of minimal vectors of L.

Let L_{0} ⊂ L be a sublattice of index 2 generated by n independent minimal vectors e_{1}, … e_{n} of L. We have L = ⟨L_{0}, e⟩, where, by possibly reducing e modulo L_{0}, and using the definition of the length, we may prescribe

e = \frac{e_{1} + ⋯ + e_{n}}{2} .

The hypotheses on the maximal index and the length of L imply that the minimal vectors of L_{0} are just the ±e_{i}, and that the other possible minimal vectors of L are of the form

\frac{±e_{1} ± e_{2} ± ⋯ ± e_{n}}{2} .

(See [M], Proposition 2.1.) In order to prove Theorem 1.1, we may and shall assume that s(L) ≥ n+1, and in particular, by negating some e_{i} if necessary, we shall suppose e itself minimal (unless otherwise specified in Section 3). The next sections are devoted to the other minimal vectors x ∈ S(L)∖S(L_{0}), that we represent by their set I of minus signs:

x = x_{I} = e − ∑_{i∈I} e_{i} .

We call type of x the number |I| of minus signs in the expression of x (e is of type 0). Of course the types of x and −x add to n, therefore by possibly negating x we shall suppose |I| ≤ \frac{n}{2}, and if |I| = \frac{n}{2} we shall

prescribe 1 ∈ I. [The index set I associated to the minimal vector x, and a fortiori its type, depend on the choice of e ∈ L∖L_{0}.]

The following notation is relative to a given set of r ≥ 3 minimal vectors x_{1}, x_{2}, …, x_{r} in L \ L_{0} identified to their index sets I_{1}, I_{2}, … I_{r}

x_{k} = x_{I_{k}} = e − ∑_{i∈I_{k}} e_{i}, I_{k} ⫋ \{1, …, n\}, |I_{k}| ≤ \frac{n}{2} .

We denote by

m = | ∪_{k} I_{k}| (m ≤ n)

the number of indices involved in the expression of the x_{k}. Actually, we may and shall suppose that

⋃_{k} I_{k} = {1, 2, …, m} .

For i = 1, …, n we call weight of i the number w(i) = 0, …, r of subsets I_{k} it belongs to; we thus have

∑_{k=1}^{r} x_{k} = r e − ∑_{i=1}^{n} w(i)e_{i} .  (1)

We also introduce the partition of ∪I_{k} = {1, …, m} into sets of indices of given weights

W_{k} = {i ∈ ∪_{k}I_{k} | w(i) = k} (1 ≤ k ≤ r) ,

that we regroup into the sets of indices of even and odd weights

W_{0} = W_{2} ∪ W_{4} ∪ … and W_{1} = W_{1} ∪ W_{3} ….

Section 3 gives properties about the weights in families of 3, 4 or 5 minimal vectors; these results are used in Sections 4 to 7 to give an upper bound for the number t_{p} of minimal vectors of a given type p.

[The bounds for t_{1}, t_{2} and t_{1} + t_{2} given in Sections 3 and 4 were obtained by Martinet and the author while giving a classification of the sixdimensional perfect lattices based on their maximal index, work previously done by Baranovskii and Ryshkov in [B-R].]

Section 8 concludes by an estimation of the “kissing number” s(L) = n + t_{0} + t_{1} + ⋯ + t_{⌊ \frac{n}{2} ⌋} of L (t_{0} = 1) strictly smaller than the dimension \frac{n(n+1)}{2} of the space of lattices.

3. Properties of a set of minimal vectors

3.1. Minimal vectors of type 1. The following property derives from the hypothesis “no n independent vectors of L span a sublattice of index 3 of L” and does not suppose e minimal.

Proposition 3.1. Suppose n ≥ 5. Then there exist at most four minimal vectors of the form e − e_{i} (i.e. t_{1} ≤ 4).

Proof. Let x_{i} = e − e_{i}, i = 1, …, 5 be five minimal vectors of type 1 of L; using (1) we obtain

∑_{i=1}^{5} x_{i} − ∑_{i=6}^{n} e_{i} = 5e − ∑_{i=1}^{n} e_{i} = 3e;

Clearly the n vectors x_{1}, …, x_{5}, e_{6}, …, e_{n} are linearly independent, and generate a sublattice L′ of index 3 in L, a contradiction. □

3.2. Weights in a set of minimal vectors. These properties of a set of r = 3, 4 or 5 minimal vectors of the form x_{k} = e − ∑_{i∈I_{k}} e_{i} make essential use of the assumption that ℓ = n, i.e. that any set X ⊂ S(L) of independent minimal vectors satisfying a congruence ∑_{x∈X} x ≡ 0 mod 2L has cardinality |X| = n. We first focus on the case r = 4, and here again e is not supposed to be minimal.

Lemma 3.2. If every set I_{1}, I_{2}, I_{3} and I_{4} contains at least one index of weight 1, then this index is unique, and there is no index of weight 3.

Proof . From (1) follows

∑_{k=1}^{r} x_{k} + ∑_{i∈W_{0}} e_{i} = re − ∑_{i∈W_{1}} w(i)e_{i} − ∑_{i∈W_{0}}(w(i) − 1)e_{i}

= 4e − ∑_{i∈W_{1}∪W_{2}} e_{i} − 3 ∑_{i∈W_{3}∪W_{4}} e_{i}

= 4e − ∑_{i=1}^{m} e_{i} − 2 ∑_{i∈W_{3}∪W_{4}} e_{i} ,

where ∑_{i=1}^{m} e_{i} = 2e − ∑_{i=m+1}^{n} e_{i}, and thus we obtain

∑_{k=1}^{4} x_{k} + ∑_{i∈W_{0}} e_{i} − ∑_{i=m+1}^{n} e_{i} = 2e − 2x ,

with x = ∑_{i∈W_{3}∪W_{4}} e_{i} ∈ L. Thus the set

X = {x_{1}, x_{2}, x_{3}, x_{4}} ∪ {e_{i}, i ∈ W_{0} or i ≥ m + 1}

of minimal vectors of L (which does not include the vector e) satisfies the congruence

∑_{k=1}^{4} x_{k} + ∑_{i∈W_{0}} e_{i} + ∑_{i=m+1}^{n} e_{i} ≡ 0 mod 2L .

Its cardinality is

|X| = 4 + |W_{0}| + (n − m) = n − (|W_{1}| − 4) − |W_{3}|

where |W_{1}| ≥ 4 since for k = 1, …, 4, W_{1} ∩ I_{k} ≠ ∅. To complete the proof of the lemma, it remains to prove that X is free. Suppose

∑_{k=1}^{4} λ_{k}x_{k} + ∑_{i∈W_{0}∪{m+1,...,n}} μ_{i}e_{i} = 0  (2)

where the λ_{k}, μ_{i} are real numbers. Fix k ∈ {1, …, 4}; by assumption, there exists i_{k} ∈ I_{k} of weight 1, hence belonging to no other I_{h}. With respect to the basis e_{1}, …, e_{n} for E the coefficient a_{i_{k}} of the left hand side of (2) on the corresponding e_{i_{k}} reads a_{i_{k}} = ^{\frac{∑_{h} λ_{h}}{2}} −λ_{k}. Its vanishing implies that the λ_{k} have a common value λ satisfying 2λ = λ, hence λ = 0. Now (2) reduces to ∑_{i∈W_{0}∪{m+1,...,n}} μ_{i}e_{i} = 0, and all μ_{i} are zero. The set X is free, which completes the proof. □

From now on, we suppose that e is a minimal vector of L.

Proposition 3.3. If every I_{k}, 1 ≤ k ≤ r, contains at least one index of weight 1, and if moreover when r = 3 there is an index of weight 3, then r is equal to 3 or 4, the index of weight 1 in every I_{k} is uniquely determined, and for r = 3 (resp. 4) we have |W_{3}| = 1 (resp. |W_{3}| = |W_{4}| = 0).

Proof. The case r ≥ 5 follows from the case r = 4 and Proposition 3.1.

(a) Case r = 3. By assumption, there exists an index of weight 3, say 1 ∈ I_{1} ∩ I_{2} ∩ I_{3}. We change e_{1} into e′_{1} = −e_{1} and e into e′ = e − e_{1} = \frac{e′_{1}+e_{2}+···+e_{n}}{2} (not necessarily minimal), and we consider the four minimal vectors x_{0} = e, x_{1}, x_{2} and x_{3} which, relatively to e′, read x_{k} = e′ − ∑_{i∈I′_{k}} e_{i} with I′_{0} = {1}, and I′_{k} = I_{k} \ {1} for k = 1, 2, 3. The weights w(i) and w′(i) of an index i relative to the sets (I_{1}, I_{2}, I_{3}) and (I′_{0}, I′_{1}, I′_{3}, I′_{4}) coincide, except for i = 1: w(1) = 3 and w′(1) = 1. Thus the four minimal vectors x_{i}, 0 ≤ i ≤ 3 satisfy the hypotheses of Lemma 3.2: there is no index i ≥ 2 of weight 3, and the indices of weight 1 in I_{1}, I_{2}, I_{3} are uniquely determined, as announced.

(b) Case r = 4. It remains to prove that W_{4} = ∅. Otherwise, any subset of three I_{k} should satisfy the hypotheses of (a), hence |W_{4}| = 1, and by considering convenient ones we should obtain |W_{2}| = 0 (if W_{2} ∩ I_{1} ∩ I_{2} ≠ ∅, we consider the subset {I_{2}, I_{3}, I_{4}}, where I_{2} has too many indices of weight one). Since by the lemma we already know that |W_{1}| = 4 and |W_{3}| = 0, every I_{k} should contain just one index of weight 1, say i_{k}, and one index of weight 4, say 1: the x_{k} are of the form x_{k} = e − e_{1} − e_{i_{k}}, where the i_{k} ≥ 2 are pairwise distinct. By the same substitution e_{1} ↦ e′_{1} = −e_{1}, e ↦ e′ = e−e_{1}, (e′ is not necessarily minimal), we obtain five vectors of type 1, namely x_{0} = e′ − e′_{1} and the four x_{k} = e′ − e_{i_{k}}, a contradiction with Proposition 3.1.

□

Application 3.4. • Four pairwise disjoint sets I_{k} are singletons.

• Let x_{0} = e − ∑_{i∈I_{0}} e_{i} be a minimal vector of type p = |I_{0}| ≥ 3, and let A ⊂ I_{0}, with 1 ≤ |A| ≤ p − 1. There exists at most one vector x_{I} of type p such that I ∩ I_{0} = A.

We now interchange the parts of even and odd weights, and focus on weight 2.

Proposition 3.5. Let x_{1}, …, x_{r} be r ≥ 3 minimal vectors, of the form x_{k} = e − ∑_{i∈I_{k}} e_{i}. For 1 ≤ k < k′ ≤ r we define the relation

I_{k} ∼ I_{k′} ⟺ I_{k} ∩ I_{k′} ∩ W_{2} ≠ ∅ .

We suppose that the graph of the relation ∼ is a cycle of length r = 3 or 5, or a star of valency 3 (with r = 4).

Then the dimension n is equal to m or m + 1, where m = | ⋃_{k=1}^{r} I_{k}|; moreover, if n = m + 1, then |W_{2}| = r (resp. r − 1 = 3) in the case of a cycle (resp. star).

Proof. Note that the cycle (resp. star) contains r (resp. r − 1) edges, and thus that the number |W_{2}| of indices of weight 2 is ≥ r (resp. r − 1). Since there is nothing specific to prove in the case n = m, we shall suppose n ≥ m + 1 and show that then all equalities about n and |W_{2}| hold.

We consider the set

X = {x_{1}, …, x_{r}, e_{i} (i ∈ W_{1}), ρe}

of minimal vectors, where ρ ∈ {0, 1} is the remainder of r modulo 2, i.e. ρ = 1 in the case of the cycle, and 0 in the case of the star. Using (1) we obtain that the vectors of X add to a congruence modulo 2L:

∑_{k=1}^{r} x_{k} + ∑_{i∈W_{1}}(w(i) − 2)e_{i} + (4 − r)e = ∑_{i∈W_{0}}(2 − w(i))e_{i} + 2 ∑_{i=m+1}^{n} e_{i} . (4)

We now prove that the assumption n ≥ m + 1 implies that X is free. Let λ_{k} (k = 1, …, r), μ_{i} (i ∈ W_{1}), μ (equal to zero in the case of the star) be real numbers such that

∑_{k=1}^{r} λ_{k}x_{k} + μe + ∑_{i∈W_{1}} μ_{i}e_{i} = 0 .  (5)

Put a = ^{\frac{∑_{k=1}^{r} λ_{k}+μ}{2}}. With respect to the basis (e_{i}) Condition (5) reads:

\{ \begin{matrix}a − ∑_{k|i∈I_{k}} λ_{k} & = 0 ∀i ∈ W_{0} \\ a − ∑_{k|i∈I_{k}} λ_{k} + μ_{i} & = 0 ∀i ∈ W_{1} \\ a & = 0 ∀i ≥ m + 1. \end{matrix}  (5′)

Since n ≥ m + 1, we can write Condition (5’) for i = n, and we obtain a = 0, i.e. ∑ λ_{k} = −μ.

Now, if I_{k} ∼ I_{k′} are adjacent, we obtain λ_{k} = −λ_{k′} by writing Condition (5’) for some i ∈ W_{2} ∩ I_{k} ∩ I_{k′}. In the case of the 3-star with node I_{1}, it follows λ_{2} = λ_{3} = λ_{4} = −λ_{1}, with ∑ λ_{k} = 0 since μ = 0, and thus λ_{k} = 0 for all k. In the case of the odd cycle say (I_{1}, I_{2}, …, I_{r}), the λ_{k} takes the values λ_{1} and λ_{2} = −λ_{1} alternatively; since r is odd, all λ_{k} vanish again, and so do ∑ λ_{k} and μ.

Eventually, in both cases (star or cycle), the conditions (5’) give μ_{i} = 0 for all i ∈ W_{1}. Thus, when n ≥ m + 1, the set X is free. Since its vectors add to a congruence modulo 2L, we must have |X| = n, where

n − |X| = (|W_{2}| − r) + (n − m − 1) in the case of the odd cycle

(|W_{2}| − (r − 1)) + |W_{4}| + (n − m − 1) in the case of the star .

The terms between brackets in the right-hand sides are non-negative, and since n − |X| = 0 they vanish, as stated. □

4. Sets of minimal vectors of type at most two

The type 1 was dealt with in Proposition 3.1. We now focus on the type 2, i.e. on minimal vectors of the form x = e−e_{i}−e_{j}, 1 ≤ i < j ≤ n.

Theorem 4.1. We define on the set {1, 2, …, n} the relation

i ≡ j if and only if e − e_{i} − e_{j} is a minimal vector .

Then, if n ≥ 6, the graph of the relation ≡ is a subgraph of the complete bipartite graph with 9 edges, except for n = 6 where it can also be a cycle of length 5.

Proof. We discard isolated vertices. By 3.3 we know that the valencies of the vertices are at most equal to 3, and that a disconnected graph contains no vertex of valency 3. By Proposition 3.5, the graph of the relation ≡ contains no triangle (since n > 4) and no pentagon except for n = 6. If the graph is connected (resp. disconnected), it contains no path of length ≥ 6 (resp. ≥ 4) and no cycle of length ≥ 7 (resp. 5): otherwise, we could extract four minimal vectors whose graph has 3 connected components, a contradiction with 3.3. Now we conclude that every possible linear graph has at most 6 (non-isolated vertices) say V = {1, 2, 3, 4, 5, 6}, and that except the pentagon, they are bipartite: we can define a partition V = V_{0} ∪ V_{1}, |V_{0}| = |V_{1}| = 3 such that no two vertices in the same V_{k} are adjacent. It remains to consider a connected graph with at least one vertex of valency 3, say 1. Denote by V_{0} = {2, 4, 6} the set of its adjacent vertices. By Proposition 3.3, any other edge must be connected to this star, i.e. one of its end-points belongs to V_{0}, but not the other one (triangles are forbidden). Let V_{1} denote the set vertices adjacent to vertices in V_{0}. It contains at most 3 vertices, as we shall now prove. If a vertex in V_{0}, say 2, has valency 3, exchanging the roles of the vertices 1 and 2, we see that V_{1} is the set of the vertices adjacent to 2, and thus |V_{1}| = 3. If no vertex in V_{0} has valency 3, distinct vertices in V_{1} \ {1} are adjacent to distinct vertices in V_{0}. Suppose that there are three of them, say 3, 5, 7, respectively adjacent to 2, 4, 6. We have then four edges, namely 1 2, 3 2, 5 4 and 7 6 in three connected components, a contradiction. Thus |V_{1}| = 3. □

Corollary 4.2. Let t_{1} and t_{2} be the number of minimal vectors of types 1 and 2 respectively. Then t_{1} + t_{2} ≤ 9, where equality holds only if the graph of the relation ≡ is the complete bipartite graph ((t_{1}, t_{2}) = (0, 9)) or if it consists of two non-adjacent nodes of valency 3 and their common adjacent vertices ((t_{1}, t_{2}) = (3, 6)).

Proof. Since by Proposition 3.1 we know that t_{1} ≤ 4, we only need to consider the graphs (in the sense of the theorem) with t_{2} ≥ 5 edges. We first note that if i is an isolated point of the graph, e − e_{i} cannot be minimal: we could extract from the t_{2} ≥ 5 edges of the graph three disjoint ones, or two secant and a third one disjoint, which, together with i, would contradict Proposition 3.3. We now consider the case of a pentagon say (1, 2, 3, 4, 5, 1). If there are 4 vectors of type 1, three of them correspond to consecutive vertices, say e − e_{1}, e − e_{2} and e − e_{3}, which together with e − e_{4} − e_{5}, contradicts again 3.3. Thus t_{1} ≤ 3 and t_{1} + t_{2} ≤ 8. The other graphs to consider are included in the complete bipartite graph associated with, say, the partition {2, 4, 6} ∪ {1, 3, 5}. We first consider a path of length 5, say 1−2−3−4−5−6, and suppose e − e_{i} minimal (i = 1, …, 6). Then i = 1 is not possible, because the four sets I_{1} = {1}, I_{2} = {2, 3}, I_{3} = {4, 5}, I_{4} = {5, 6} contradict Proposition 3.3. The same argument, with I_{2} = {1, 2} instead of {2, 3}, forbids i = 3. So the only possible values of i are i = 2 and i = 5, and t_{1} ≤ 2, t_{1} + t_{2} ≤ 7. Now consider the cycle (1, 2, 3, 4, 5, 6, 1). By considering the path 1−2−3−4−5−6, we see that e−e_{1} is not minimal, and since all vertices play the same role, we conclude that t_{1} = 0. This conclusion extends to any subgraph of the complete bipartite graph containing such a cycle, i.e. the complete graph itself, and the ones obtained by suppressing one edge, two disjoint edges or three pairwise disjoint edges.

One more graph with 5 edges contains no node of valency 3: the disjoint union of a cycle of length 4, say (1, 2, 3, 4), and a path of length 1. Suppose e − e_{1} minimal; the four sets I_{1} = {1}, I_{2} = {2, 3}, I_{3} = {3, 4}, I_{4} = {5, 6} contradict 3.3. Thus there are at most two minimal vectors of type 1, namely e − e_{5} and e − e_{6}, and t_{1} + t_{2} ≤ 7.

We are left with graphs which contain at least one node of valency 3, say 1, with adjacent vertices 2, 4, 6. If e − e_{i} is minimal, we must have i ∈ {1, 2, 4, 6} (otherwise, the four sets of indices {1, 2}, {1, 4}, {1, 6} and {i} should contains indices of weight one–respectively 2, 4, 6 and i– but also an index of weight 3, which contradicts Proposition 3.3). Note that the four values i = 1, 2, 4, 6 are never simultaneously possible: since there are more than four edges, one of the vertices 2, 4, 6, say 2, has another adjacent vertix, say 3. Then if e − e_{1}, e − e_{4}, e − e_{6} were minimal vectors, the sets {1}, {4}, {6} and {2, 3} would contradict Proposition 3.3. We then have t_{1} ≤ 3, which completes the case t_{2} = 5.

If there are, in the graph we consider, two adjacent nodes of valency 3, say 1 and 2, the only possible minimal vectors of type 1 are thus e − e_{1} and e − e_{2}. In particular, the graph of t_{2} = 7 edges obtained by suppression from the complete bipartite graph two secant edges, say 3 − 2 and 3 − 4 contains three nodes of valency 3, namely 1, 5 and 6, where 6 is adjacent to 1 and 5. The unique minimal vector of type 1 is thus e − e_{6}, and t_{1} + t_{2} ≤ 8. This completes the case t_{2} = 7.

We are left with 3 non-isomorphic graphs with 6 edges. If it is obtained by suppressing (from the complete graph) the three edges of a path of length 3, it contains two adjacent nodes of valency 3, and t_{1} ≤ 2, as announced. The same conclusion is valid for the graph obtained by suppression of three edges, two of them secant, for instance 4 − 5, 5 − 6 and 2 − 3. The resulting graph contains the disjoint union of the cycle (14361) with the edge 2−5, and we have seen that the only possible minimal vectors are e − e_{2} and e − e_{5}, and again t_{1} ≤ 2. But for the graph obtained by suppressing three secant edges, say 5 − 2, 5 − 4 and 5 − 6, it contains two non-adjacent nodes, and it is consistent with t_{1} = 3 minimal vectors of type 1, namely e − e_{2}, e − e_{4}, e − e_{6}. The proof of the corollary is now complete. □

5. Configurations of three vectors of type p ≥ 3

The graph we consider is that of the relation ∼ introduced in Proposition 3.5: I_{k} ∼ I_{k′} if I_{k} ∩ I_{k′} contains an index of weight 2.

Proposition 5.1. Let x_{1} = e − ∑_{i∈I_{1}} e_{i}, x_{2} = e − ∑_{i∈I_{2}} e_{i}, x_{3} = e − ∑_{i∈I_{3}} e_{i} be three vectors of the same type p ≥ 3. We suppose that W_{3} = ∩I_{k} is not empty. Then, if (p, n) ≠ (4, 8), one at least of the sets I_{1}, I_{2} and I_{3} has no index of weight one, and the ∼-graph is a path.

Proof. For all k = 1, 2, 3 we put a_{k} = |W_{1} ∩ I_{k}|, b_{k} = W_{2} ∩_{h≠k} I_{h}, and c = |W_{3}|. We have p = |I_{k}| = a_{k} + (|W_{2}| − b_{k}) + c, and thus the a_{k} − b_{k} have a common value p − |W_{2}| − c.

• Suppose first a_{k} ≥ 1 for all k. Then by Proposition 3.3, we have a_{1} = a_{2} = a_{3} = c = 1. Thus, the b_{k} have a common value |W_{2}|/3, where 2|W_{2}| = 3p − |W_{1}| − 3|W_{3}| = 3p − 6; p is even, |W_{2}| = \frac{3(p−2)}{2}, and the b_{k} = \frac{p−2}{2} are non-zero. We conclude that the ∼-graph is a cycle, and by Proposition 3.5 we must have n ≤ m + 1, where m = ∑ |W_{i}| = \frac{3}{2}p + 1. The unique solution for the inequalities 2p ≤ n ≤ \frac{3}{2}p + 2 is p = 4, n = 8.

• Now we suppose a_{1} = 0, and thus p = b_{2} + b_{3} + c. Since |I_{1} ∩ I_{2}| = b_{3} + c is < p, b_{2} is non-zero, and so is b_{3}. From |W_{2}| = b_{1} + p − c follow 3p − m = |W_{2}| + 2|W_{3}| = b_{1} + p + c and m = 2p − c − b_{1}. If the graph were a cycle, i.e. if b_{1} ≥ 1, we should obtain m ≤ 2p − 2 (since c = |W_{3}| ≥ 1), and thus m + 1 < 2p, a contradiction with Proposition 3.5. We conclude that the graph is the path I_{2} ∼ I_{1} ∼ I_{3}. □

Corollary 5.2. We suppose (p, n) ≠ (4, 8), and we consider three distinct minimal vectors x_{0} = x_{I_{0}}, x = x_{I} and x′ = x_{I′} of the same type p ≥ 3 such that I and I′ both intersect I_{0}. We put

I = A ∪ X with A = I ∩ I_{0}, X = I ∖ A ,
I′ = A′ ∪ X′ with A′ = I′ ∩ I_{0}, X′ = I ∖ A .

Then:

(i) The ∼-graph (I, I′, I_{0}) is a cycle if and only if A ∩ A′ = ∅ and X ∩ X′ ≠ ∅.

(ii) If A and A′ satisfy an inclusion, so do X and X′.

(iii) If A and A′ satisfy no inclusion and if (I, I′, I_{0}) is not a cycle, then X and X′ are disjoint; if moreover A ∩ A′ ≠ ∅, then I_{0} = A ∪ A′.

Proof. The sets of indices of weight one in I_{0}, I and I′ are respectively I_{0} \ (A ∪ A′), X \ X′ and X′ \ X; the sets of indices of weight two in I_{0} ∩ I, I_{0} ∩ I′ and I ∩ I′ are respectively A \ A′, A′ \ A and X ∩ X′; eventually the set W_{3} of indices of weight three is A ∩ A′.

(i) We see directly that (I, I′, I_{0}) is a cycle if and only if A and A′ satisfy no inclusion and X and X′ intersect. From Hypothesis (p, n) ≠ (4, 8), Proposition 5.1 shows that it can only happen when A ∩ A′ = ∅.

(ii) Assume A′ ⊂ A. Then W_{3} = A′ is not empty. From Proposition 5.1, one at least of the sets I, I′ and I_{0} contains no index of weight one. Since I_{0} \ (A ∪ A′) = I_{0} \ A is not empty (since I ≠ I_{0} have the same cardinality), X and X′ satisfy an inclusion, namely X ⊂ X′ (since |A| + |X| = |A′| + |X′| = p). In particular, if A = A′, we have X ⊂ X′ and |X| = |X′|, thus X = X′ and I = I′.

(iii) Now we assume that A and A′ satisfy no inclusion, i.e. I ∼ I_{0} and I′ ∼ I_{0}. As already noted in (i), we must have I ≁ I′, i.e. X ∩X′ = ∅. If moreover A ∩ A′ ≠ ∅, by Proposition 5.1 one at least of the sets W_{1} ∩ I = X, W_{1} ∩ I′ = X′ and W_{1} ∩ I_{0} = I_{0} \ (A ∪ A′) is empty, thus I_{0} = A ∪ A′. □

The end of the section is devoted to the special case (p, n) = (4, 8).

Proposition 5.3. If n = 8, then t_{4} ≤ 6.

Proof. Indeed, since n = 2p we may and shall assume that all index sets contain 1. Let I_{0} = {1, 2, 3, 4} be one of them; from 3.4 we know that there is at most one I ≠ I_{0} for a given I ∩ I_{0}. Let I be such that |I ∩ I_{0}| = 3. For instance, put I_{1} = {1, 2, 3, 5}, and let I_{2} = {1, 2, 4, a}, with a ∈ {5, 6, 7, 8}. Actually, if a = 5, the configuration {I_{0}, I_{1}, I_{2}} is a cycle in the sense of 3.5, which is absurd since n = 8 > 5 + 1. Thus for instance I_{2} = {1, 2, 4, 6} and similarly I_{3} = {1, 3, 4, 7}. Now, let x_{I} be a minimal vector such that |I ∩ I_{0}| = 1, i.e. I = {1, a, b, c}, with {a, b, c} ⊂ {5, 6, 7, 8}. Actually, by Proposition 3.3 we must have {a, b, c} = {5, 6, 7}. Otherwise, if for instance 5 ∉ {a, b, c}, the configuration {I_{0}, I_{1}, I} would contain too many indices of weight 1. Now we have I ∼ I_{k} for k = 1, 2, 3 and the configuration {I_{1}, I_{2}, I_{3}, I} contradicts Proposition 3.5 (n = 8, m = 7, |W_{2}| = 6 > 3). We conclude that there are at most 3 minimal vectors x_{I} such that |I ∩ I_{0}| = 1 or 3. Now, we shall prove that there are at most 2 minimal vectors x_{I} such that |I ∩ I_{0}| = 2. Otherwise, let I = {1, 2} ∪ X, I′ = {1, 3} ∪ X′ and I” = {1, 4} ∪ X” be three solutions (X, X′ and X” subsets of {5, 6, 7, 8}). In their configuration (I, I′, I”), 2, 3 and 4 have weight 1, and by 5.1 the elements of X, X′ and X” must have weight ≠ 1, 3, i.e. they have weight 2, wich leads (up to permutation) to I = {1, 2, 5, 6}, I′ = {1, 3, 6, 7} and I” = {1, 4, 5, 7}. Now the configuration I_{0}, I, I′, I” satisfies the hypotheses of Proposition 3.5, with m = 7 and n = 8, but |W_{2}| = 6, a contradiction. □

Taking into account Proposition 5.3, we discard in the next sections the case (p, n) = (4, 8).

6. Families without cycles of length 3

Theorem 6.1. Let {x_{I}, I ∈ F} be a set of minimal vectors of the same type p ≥ 3, such that F contains no cycles of length 3.

If p ≥ 4 and n ≥ 2p + 2, then |F| ≤ p + 6.

If p ≥ 4 and n = 2p + 1, or p = 3 and n ≥ 8, then |F| ≤ p + 5. If (p, n) = (3, 7), then |F| ≤ 7. If p ≥ 3, p ≠ 4 and n = 2p, then |F| ≤ p + 1.

[Note that the bound p + 6 is indeed reached, as checked for (p, n) = (4, 10), (5, 12), . . ..]

The whole section is devoted to the proof of this theorem. We first consider the case when all elements of F intersect a given one, which includes the case p = \frac{n}{2}, since then we may prescribe that all I contain a given index.

Proposition 6.2. We suppose that there exists I_{0} ∈ F such that for all I ∈ F, I ∩ I_{0} ≠ ∅.

If p ≥ 4 (resp. p = 3) and n ≥ 2p + 1, then |F| ≤ p + 3 (resp. 5); if p ≥ 3 and n = 2p, then |F| ≤ p + 1.

Proof. For I ∈ F, we write

I = A ∪ X, with A = I ∩ I_{0} ≠ ∅ and X = I ∖ A .

From 3.4 it follows that I is uniquely specified by A (or equivalently by X). We shall now describe the set

F_{0} = {I ∩ I_{0}, I ∈ F}

in one-to-one correspondence with F, and prove that it consists of one or two totally ordered sequences, except in the following case.

Lemma 6.3. Let I = A ∪ X, I′ = A′ ∪ X′ and I” = A” ∪ X” be three elements of F ∖ {I_{0}} such that A, A′ and A” satisfy no pairwise inclusions. Then |F| = 4.

Proof of the lemma. From Corollary 5.2 we see that the sets X, X′ and X′′ are pairwise disjoint. First, we prove that A, A′ and A′′ are pairwise disjoint. Otherwise suppose for instance A∩A′ ≠ ∅, and thus, by Corollary 5.2, I_{0} = A ∪ A′, i.e. I_{0} ∖ A ⊂ A′; since A” is not included in A′, it is no more included in I_{0} ∖A i.e. A”∩A ≠ ∅; and of course we also have A” ∩ A′ ≠ ∅. In the configuration {I, I′, I”}, the indices in X, X′ and X′ have weight one, thus by Proposition 5.1 I ∩ I′ ∩ I” = ∅, so that the indices in A ∩ A′, A′ ∩ A” and A ∩ A” have weight 2, and {I, I′, I”} is a cycle, a contradiction: A, A′ and A” are pairwise disjoint as announced. Now in the configuration {I, I′, I”, I_{0}}, the sets of weight one in I, I′, I” and I_{0} are respectively equal to X ≠ ∅, X′ ≠ ∅, X” ≠ ∅ and I_{0} ∖(A∪A′ ∪A”). If this last set were not empty, we should obtain from Proposition 3.3 |X| = |X′| = |X”| = |I_{0} ∖(A∪A′ ∪A”)| = 1, thus |A∪A′ ∪A”| = 3(p−1) = p−1, i.e. p = 1, absurd. So I_{0} = A∪A′ ∪A” is a partition of I_{0}. Let J = B ∪ Y be another element of F. Then B = J ∩ I_{0} satisfies an inclusion with at most one of the sets A, A′, A” (since these sets are mutually disjoint, and so are their complements X, X′ and X”). Thus B satisfies no inclusion with at least two among A, A′, A”, say A and A′. Thus I_{0} = A ∪ A′ ∪ B is a partition of I_{0}, and B = A”, a contradiction. Thus F = {I_{0}, I, I′, I”}. □

If F_{0} = {I ∩ I_{0}, i ∈ F} is a totally ordered family, we have |F_{0}| = |F| ≤ |I_{0}| = p, and Proposition 6.2 is proved. The same conclusion holds in the situation of Lemma 6.3. We therefore consider in F

I = A ∪ X and J = B ∪ Y such that A ⊄ B and A ⊅ B ,

and may suppose that for any K = C ∪ Z ∈ F, C ∈ F_{0} satisfies an inclusion with A or B, or equivalently (by 5.2), Z satisfies an inclusion with X or Y, which are disjoint. If Z satisfies an inclusion with both X and Y, i.e. if Z ⊃ X ∪ Y, then by Proposition 5.1 applied to {I, J, K} (since the indices of C ≠ ∅ have weight 3, and those of A∖B ≠ ∅ and B∖A ≠ ∅ have weight 1), Z coincides with X ∪ Y, and C with A ∩ B.

Now choose a pair (A, B) with |A| and |B| minimal: if C ≠ A ∩ B satisfies an inclusion with A (resp. B), it contains A (resp. B). [If

C ⊊ A, from the minimality of the pair (A, B), C satisfies an inclusion with B too, and we just saw that C = A ∩ B.] Thus, apart from I_{0} and

(possibly) A ∩ B, F_{0} is union of two disjoint sets

A = {C ∈ F_{0} | A ⊂ C ⊊ I_{0}} and B = {C ∈ F_{0} | B ⊂ C ⊊ I_{0}} .

These sets are totally ordered by inclusion, as we now prove. Consider for instance in F two distinct elements K = C ∪ Z ∈ F and K′ = C′ ∪ Z′ ∈ F with C ⊃ A and C′ ⊃ A, i.e. by 5.2, Z and Z′ included in X. Thus Z and Z′ are disjoint from Y, and by 5.2 again, B satisfies no inclusion with C or C′. Since |F| ≥ 5, Lemma 6.3 implies that C and C′ satisfy an inclusion: the set A is totally ordered by inclusion, and so is B. We then have

|A| ≤ p − |A| and |B| ≤ p − |B| .

We have to consider two cases:

case A ∩ B ≠ ∅, in particular n = 2p. It follows from Corollary 5.2 that I_{0} = A ∪ B and then |A| + |B| = p + |A ∩ B| ≥ p + 1. It implies |A| + |B| ≤ 2p − |A| − absB ≤ p − 1, and taking into account I_{0} and A ∩ B, F = F_{0} ≤ p + 1 as required.

case A ∩ B = ∅. We then have F_{0} = {I_{0}} ∪ A ∪ B, where A and B are totally ordered sequences A = A_{1} ⊊ A_{2} ⊊ ⋯ ⊊ A_{k} ⊊ I_{0} and B = B_{1} ⊊ B_{2} ⊊ ⋯ ⊊ B_{h} ⊊ I_{0} (every pair (A_{i}, B_{j}) without inclusion),with for instance 1 ≤ k ≤ h ≤ p − 1. We then have |F| ≤ 1 + h + k. If k = 1, we obtain |F| ≤ p + 1, and Proposition 6.2 is proved in this case. The same conclusion holds if h ≤ 2, for instance if p = 3, since then we obtain |F| ≤ 5. We thus suppose h ≥ 3 and k ≥ 2. and consider the four elements of F corresponding to A, B, A_{3} and B_{2}, say I = A ∪ X, J = B ∪ Y, I_{3} = A_{3} ∪ X_{3} and J_{2} = B_{2} ∪ Y_{2}, with X and Y disjoint and X_{3} ⊊ X and Y_{2} ⊊ Y. Their respective subsets of weight 1 are X∖X_{3} ≠ ∅, Y ∖Y_{2} ≠ ∅, A_{3}∖(A ∪ B_{2}) and B_{2}∖(A_{3} ∪ B). If A_{3} ∩ B_{2} were empty, we should have |A_{3}∖(A ∪ B_{2})| = |A_{3}∖A| ≥ 2 and |B_{2}∖(A_{3} ∪B| = |B_{2}∖B| ≥ 1, a contradiction with Proposition 3.3. Thus A_{3} ∩ B_{2} is not empty, and from 5.2, it follows that |A_{3}| + |B_{2}| ≥ p+1. Now from h = |A| ≤ 2+(p−A_{3}) and k ≤ 1+(p−B_{2}) we obtain F ≤ 4 + 2p − (|A_{3}| + |B_{2}|) ≤ p + 3 as required. □

We know that (for p > 1), the family F contains at most three pairwise disjoint elements. We examine now this case.

Proposition 6.4. If F contains three pairwise disjoint elements, then F ≤ p + 3.

Proof. This will follow from the more precise result 6.5, for which we need some more notation.

Let I_{1}, I_{2}, I_{3} be three elements of F pairwise disjoint. For every I ∈ F distinct from the I_{j} we consider the partition I = A_{1} ∪ A_{2} ∪ A_{3} ∪ X, where A_{j} = I ∩ I_{j}. Actually, X is empty. Otherwise, we could apply Proposition 3.5 to the subset {I_{1}, I_{2}, I_{3}, I} ∈ F^{4}, whose sets of indices of weight one I_{j} ∖ A_{j}, j = 1, 2, 3 and X should have just one element, and I should have p = 3(p−1)+1 elements, i.e. p = 1, a contradiction. We thus have

I = A_{1} ∪ A_{2} ∪ A_{3}, where A_{j} = I ∩ I_{j}.

We introduce the following subsets of F:

For i = 1, 2, 3, F_{i} is the set of I ∈ F with only A_{i} non-empty. We have just proved that F_{i} = {I_{i}}.

For 1 ≤ i < j ≤ 3, F_{ij} is the set of I ∈ F with only A_{i} and A_{j} non-empty.

Eventually, F_{123} is the set of I ∈ F intersecting I_{1}, I_{2} and I_{3}.

Lemma 6.5. The four subsets F_{ij} and F_{123} are empty but one. We have |F_{ij}| ≤ p − 1 and |F_{123}| ≤ 3.

Proof of 6.5. We may suppose that |F| ≥ 5. Let I ≠ I′ be two elements of F distinct from I_{1}, I_{2}, I_{3}. There exists i ∈ {1, 2, 3} such that both A_{i} and A′_{i} are non-empty, for instance we suppose A_{1} and A′_{1} non-empty, and we are in the situation described by Corollary 5.2 with I_{1} in the rôle of I_{0}. We have to consider two cases.

Case 1. A′_{1} ⊊ A_{1}. Then by 5.2 we have A_{2} ∪ A_{3} ⊂ A′_{2} ∪ A′_{3}, i.e. A_{2} ⊂ A′_{2} and A_{3} ⊂ A′_{3}. As I is distinct from I_{1}, A_{2} for instance is non-empty, and so is A′_{2}. Then by 5.2, the inclusion A_{2} ⊂ A′_{2} implies now A′_{3} ⊂ A_{3}, and thus A_{3} = A′_{3}. Since I and I′ are distinct, from 3.4 we conclude that A_{3} and A′_{3} are empty, i.e. that I and I′ both lie in F_{12}.

Case 2. A_{1} and A′_{1} satisfy no inclusion. Then by 5.2 A_{2} ∪ A_{3} and A′_{2} ∪ A′_{3} are disjoint, i.e A_{2} ∩ A′_{2} = A_{3} ∩ A′_{3} = ∅. Then I and I′ do not belong to distinct F_{ij}, as we now prove. If (I, I′) lies in F_{12} × F_{13}, Proposition 3.3, applied to the four elements I, I′, I_{2}, I_{3}, gives |I_{2} ∖ A_{2}| = |I_{3} ∖ A′_{3}| = 1, thus A_{1} and A′_{1} are disjoint singletons, and the same proposition applied to {I, I′, I_{1}, I_{3}} gives, since p ≥ 3 ( I_{1} ⊋ A_{1} ∪ A′_{1}) |A_{2}| = 1 and thus |I| = p = 1 + 1, a contradiction.

We may assume for instance that A_{2} and A′_{2} are both non-empty. Then permuting I_{1} and I_{2} we conclude that A_{1} and A′_{1} are disjoint two. We then have, for i = 1, 2, 3, |A_{i}| + |A′_{i}| ≤ p. Since ∑_{i}(|A_{i}| + |A′_{i}|) = |I| + I′| = 2p, we have two possibilities.

1) |A_{1}| + |A′_{1}| = |A_{2}| + |A′_{2}| = p, and thus A_{3} = A′_{3} = ∅: I and I′ lie in F_{12}. Note that in this case, F_{12} reduces to the pair I, I′, since I′ = (I_{1}∖A_{1}) ∪ (I_{2}∖A_{2}) is uniquely determined by I.

2) Otherwise, there are at least two sums |A_{i}|+|A′_{i}| < p, say for i = 2 and i = 3. By use of Proposition 3.3 applied to the set {I, I′, I_{2}, I_{3}}, we obtain (since A_{1} ∩ A′_{1} = ∅) |A_{1}| = |A′_{1}| = |I_{2} ∖ (A_{2} ∪ A′_{2})| = |I_{3} ∖ (A_{3} ∪ A′_{3})| = 1; since the third sum |A_{1}| + |A′_{1}| = 2 is also < p, we obtain |A_{i}| + |A′_{i}| = p − 1 for all i. We then have p = 3, and for all i, A_{i} and A′_{i} are disjoint singletons. Thus I and I′ both lie in F_{123}. [Note

that Proposition 3.5 applied to the star I, I_{1}, I_{2}, I_{3} shows that in this case, n = 9 or 10]

We conclude that two distinct elements I and I′ of F belong to the same subset F_{ij} or F_{123}, therefore only one of them is non-empty. Moreover, the elements of F_{123} are pairwise disjoint, thus by 3.4 there are at most three of them. Eventually, if F_{ij} is not empty, it consists either of a disjoint pair (I, (I_{i} ∪ I_{j})∖I), or of at most p − 1 elements I = A_{i} ∪ A_{j}, where the set {A_{i}} is totally ordered by inclusion. This completes the proof of 6.5 and thus of Proposition 6.4.

We now come back to the proof of Theorem 6.1. Taking into account the result of 6.2 and 6.4, we may and will assume now that F contains two disjoint elements, say I_{1} and I_{2}, such that every I ∈ F intersects at least one of them.

In other terms, there is a partition F = F_{1} ∪ F_{2} ∪ F_{1,2}, with F_{1} = {I ∈ F | I ∩ I_{1} ≠ ∅ and I ∩ I_{2} = ∅}, F_{2} = {I ∈ F | I ∩ I_{2} ≠ ∅ and I ∩ I_{1} = ∅}, F_{1,2} = {I ∈ F | I ∩ I_{1} ≠ ∅ and I ∩ I_{2} ≠ ∅}. Since by Proposition 6.2 we know that |F_{1} ∪ F_{1,2}| ≤ p + 3 (p + 2

if p = 3), the proof of Theorem 6.1 will result from the following proposition.

Proposition 6.6. We have min(|F_{1}|, |F_{2})|) ≤ 3, where equality holds only when n ≥ 2p + 2.

We keep the notation I = A_{1} ∪ X for an element I ≠ I_{1} in F_{1}, where A_{1} = I ∩ I_{1} and X = I_{1} ∖ A_{1}, and similarly J = B_{2} ∪ Y (B_{2} = J ∩ I_{2}, Y = I_{2} ∖ B_{2}) for an element J ≠ I_{2} of F_{2}.

Lemma 6.7. Let I = A_{1} ∪ X be an element of F_{1}∖{I_{1}}. Then there is at most one J = B_{2} ∪ Y ∈ F_{2} such that Y satisfies no inclusion with X, and this may occur only when |X| = 1 (and obviously Y also is a singleton).

Proof of the lemma. Let J = B_{2} ∪ Y ∈ F_{2} be distinct from I_{2} such that Y ⊄ X and Y ⊅ X. With respect to the set {I_{1}, I_{2}, I, J}, the subsets of indices of weight one in I_{1}, I_{2}, I, J are respectively are I_{1} ∖ A_{1}, I_{2} ∖ B_{2}, X ∖ Y and Y ∖ X, all of them non-empty, and by Proposition 3.3 all of them singletons. From |A_{1}| = |B_{2}| = p − 1, follows |X| = |Y | = 1. Now, let J′ = B′_{2} ∪ Y′ be another solution in F_{2}, i.e. with Y′ singleton distinct from X, and also from Y since J′ ≠ J. The subsets of indices of weight one in I_{1}, I, J, J′ respectively are I_{1} ∖ A_{1} ≠ ∅, X, (B_{2} ∖ B′_{2}) ∪ Y, (B′_{2} ∖ B_{2}) ∪ Y′, the last two subsets with p − 1 > 1 elements, which contradicts Proposition 3.3. The solution J is unique. □

Proof of Proposition 6.6. For it we may and will assume that F_{1} contains at least two elements I = A_{1} ∪ X and I′ = A′_{1} ∪ X′ distinct from I_{1}. We fix such a pair I, I′ and suppose for instance |X| ≤ |X′|. We now prove that there is in F_{2} at most one J = B_{2} ∪ Y with Y satisfying an inclusion with X.

1) First suppose that A_{1} and A′_{1} satisfy an inclusion, for instance A′_{1} ⫋ A_{1}. Then with respect to the set {I, I′, J}, I and J have indices of weight one (those of A_{1}∖A′_{1} and B_{2} at least). Since I∩I′∩J = X∩Y is not empty, Proposition 5.1 implies that I′ has no index of weight one, i.e. X′ ⊂ X ∪ Y. The inclusion between X and Y is thus X ⊂ Y, and we conclude that Y contains X and X′. Now, let J′ = B′_{2} ∪ Y′ be another solution with Y′ satisfying an inclusion with X. Then Y and Y′ containing X′ should intersect, thus satisfy an inclusion, and B′_{2} and B_{2} too. Hence we might exchange the rôle of the pairs (I, I′) and (J, J′), and conclude that X and X′ must contain Y and Y′, thus X = X′ = Y′ = Y, a contradiction.

2) We now suppose that A_{1} and A′_{1} satisfy no inclusion. We may have two types of solutions J = B_{2} ∪ Y, with Y satisfying an inclusion with X.

• Type I: Y satisfies an inclusion with X′ too. Then we must have Y ⊃ X ∪X′ since X and X′ are disjoint. Actually, if Y contains strictly X ∪ X′, we may apply Proposition 3.3 to the set {I, I′, J, I_{2}}, with sets of indices of weight one A_{1} ∖ A′_{1}, A′_{1} ∖ A_{1}, I_{2} ∖ B_{2} and Y ∖ X ∪ X′, and conclude |B_{2}| = p − 1, thus |Y | = 1, a contradiction. Hence we have Y = X ∪ X′, which determines entirely J in F_{2}.

• Type II: Y satisfies no inclusion with X′ . We know by Lemma 6.7 that such a solution is unique and implies |Y | = |X′| = 1, and thus |X| = 1 too (|X| ≤ |X′|). More precisely since Y and X satisfy an inclusion, we have Y = X = {x} and X′ = {x′}, x′ ≠ x.

It remains to prove that we cannot have simultaneously in F_{2} solutions of types I and II. We then suppose X = {x} and X′ = {x′}, x′ ≠ x, and we consider in F_{2} an element J = B_{2} ∪ Y of the first type, i.e. with Y = {x, x′}, and an element of the second type J′ = B′_{2} ∪ Y′ with Y′ = {x}. Since Y′ ⊂ Y, we have B_{2} ⊂ B′_{2}. We may thus apply the part 1) to I, J and J′ (since X satisfies an inclusion with Y), and conclude that X must contain Y and Y′, a contradiction.

We have then proved that in every case there is at most one element J = B_{2} ∪ Y in F_{2} such that Y satisfies an inclusion with X, and by Lemma 6.7 we obtain |F_{2}| ≤ 1 + 1 + 1.

In order to complete the proof of 6.6, it remains to observe that if F_{2} contains (apart from I_{2}) two elements J = B_{2} ∪ Y and J′ = B′_{2} ∪ Y′, then |Y ∪Y′| ≥ 2 (since Y ≠ Y′ by 6.7 and 5.2) and therefore |∪_{I∈F}I| ≥ |I_{1}| + |I_{2}| + 2 = 2p + 2.

□

7. Families with cycles of length 3

Theorem 7.1. Let {x_{I}, I ∈ F} be a set of minimal vectors of the same type |I| = p ≥ 3. We suppose that F contains a cycle of length 3, and that (p, n) ≠ (4, 8). Then

(1) the dimension n of the lattice satisfies 2p + 1 ≤ n ≤ 3p − 2 ;

(2) we have |F| ≤ n, and even, if n = 3p − 2 and p ≥ 4, |F| ≤ p + 2.

The section is devoted to the proof of the theorem. Let (I_{1}, I_{2}, I_{3}) be in F a fixed cycle for the relation ∼. We use for this cycle the notation and rules of Section 2. In particular W_{k} ⊂ ∪_{h=1,2,3}I_{h} is the set of indices of weight k, k = 1, 2, 3 , and m = |I_{1} ∪ I_{2} ∪ I_{3}|.

(1) Since (p, n) ≠ (4, 8) we know by 5.1 that W_{3} = I_{1} ∩ I_{2} ∩ I_{3} is empty, which allows us to prescribe n ≥ 2p + 1. We thus have

W_{2} = E_{12} ∪ E_{23} ∪ E_{13} | E_{ij} = I_{i} ∩ I_{j} ≠ ∅

since I_{i} ∼ I_{j}. From the relations m = ∑_{k}|W_{k}| and 3p = ∑_{k} k|W_{k}| we obtain

|W_{2}| = 3p − m;

hence |W_{2}| ≥ 3 reads m ≤ 3p−3, and the inequality n ≤ 3p−2 follows from 3.5 (n is equal to m or m + 1).

For every permutation (i, j, k) of {1, 2, 3}, let

E_{k} = I_{k}∖(E_{ki} ∪ E_{kj})

denote the set of indices of weight 1 in I_{k}. The condition |I_{k}| = p reads p = |E_{k}| + |E_{ki}| + |E_{kj}|, which implies |E_{k}| ≤ p − 2, and even |E_{k}| = p − 2 if n = m + 1. Moreover it proves that |E_{k}| − |E_{ij}| does not depend on k:

Δ = |E_{k}| − |E_{ij}| = p − |W_{2}| = m − 2p ≥ 0 ,

where equality holds when n = m + 1 and thus (since |W_{2}| = 3 by 3.5) (p, n) = (3, 7). We thus have |E_{k}| ≥ 1, with equality if and only if (p, n) = (3, 7).

In the following,

I = A_{1} ∪ A_{2} ∪ A_{3} ∪ A_{12} ∪ A_{23} ∪ A_{13} ∪ (I ∩ {m + 1}) ,
with | A_{i} = I ∩ E_{i}, A_{ij} = I ∩ E_{ij}

denotes an element of F distinct from I_{1}, I_{2}, I_{3}.

The discussion below is based on the A_{ij}, starting with the case when they are empty.

Lemma 7.2. If I intersects no E_{ij}, then n = m + 1 belongs to I and (p, n) is equal to (3, 7) or (4, 10). In the first case there is at most one such I, say I = E_{1} ∪ E_{2} ∪ {7}; in the second case there are at most two of them, say I = {a_{1}, a_{2}, a_{3}, 10} and I′ = {a′_{1}, a′_{2}, a′_{3}, 10}, where E_{i} = {a_{i}, a′_{i}}.

Proof. By assumption I is of the form I = A_{1} ∪ A_{2} ∪ A_{3} ∪ (I ∩ {m + 1}) and the condition |I| = p reads p = |A_{1}| + |A_{2}| + |A_{3}| + ε, where ε = |I ∩ {m + 1}|. From |A_{i}| ≤ |E_{i}| ≤ p − 2 it follows that at most two A_{i} are non-empty, say A_{1} and A_{2}. Then, (I, I_{1}, I_{2}) is a cycle. Put m_{12} = |I ∪ I_{1} ∪ I_{2}|. By Proposition 3.5, we must have n = m_{12} or m_{12} + 1, and thus |m − m_{12}| ≤ 1, where m_{12} − m = ε − |E_{3} ∖ A_{3}|.

Case m_{12} = m + 1, i.e. n = m + 1, ε = 1 and A_{3} = E_{3}. By 3.5, we have |E_{3}| = p − 2, and thus p = |A_{1}| + |A_{2}| + (p − 2) + 1 ≥ p + 1, a contradiction.

Case m_{12} = m − 1, i.e. p = |A_{1}| + |A_{2}| + |E_{3}| − 1. But now n ≥ m is equal to m_{12} + 1, and by applying 3.5 to the cycle (I, I_{1}, I_{2}) we obtain |A_{1}| = |A_{2}| = 1 and thus |E_{3}| = p − 1, a contradiction.

Case m_{12} = m, i.e. p = |A_{1}| + |A_{2}| + |E_{3}|.

If ε = 0, A_{3} = E_{3} is non-empty, and we can interchange I_{2} and I_{3}; for the cycle (I, I_{1}, I_{3}) we can discard as above the cases m_{13} = m ± 1, and thus m_{13} = m, with again ε = 0, and thus A_{2} = E_{2}, and similarly A_{1} = E_{1}. We conclude that p = |E_{1}| + |E_{2}| + |E_{3}| = |E_{1}| + |E_{2}| + |E_{12}| + Δ = p + Δ implies Δ = 0 and thus (p, m, n) = (3, 6, 7). Then the graph of {I, I_{1}, I_{2}, I_{3}} is a star of centre I with six indices of weight two, which contradicts Proposition 3.5.

We are left with the case ε = 1, |A_{3}| = |E_{3}| − 1. Since n = m + 1, we have, by 3.5, n = 3p − 2 and |E_{i}| = p − 2, and thus |A_{3}| = p − 3; from n = m_{12} + 1, we obtain |A_{1}| = |A_{2}| = 1.

If (p, n) = (3, 7), then A_{3} = ∅ and I = E_{1} ∪ E_{2} ∪ {7}. Let I′ be another solution of this type, for instance I′ = E_{1} ∪ E_{3} ∪ {7}. Then we can apply Proposition 5.1 to the set {I, I′, I_{1}}, since I ∩ I′ ∩ I_{1} = E_{1} is not empty. But I,I′ and I_{1} have indices of weight one (respectively those of E_{2}, E_{3} and E_{12}), a contradiction.

If p ≥ 4, A_{3} is not empty and we may interchange (as above) I_{3} with I_{1} or I_{2}, and obtain |A_{3}| = 1, which implies p = 4, and n = 10. Let I = A_{1} ∪ A_{2} ∪ A_{3} ∪ {10} and I′ = A′_{1} ∪ A′_{2} ∪ A′_{3} ∪ {10} be two distinct solutions, for instance A_{3} ≠ A′_{3}. If A_{1} = A′_{1}, consider as above the set {I, I′, I_{1}}. It has indices of weight 3 (those of A_{1}), and also of weight 1 in I (A_{3} ∖ A′_{3} = A_{3}), in I′ (A′_{3}) and in I_{1} (E_{12} ∪ E_{13}), a contradiction with Proposition 5.1, since (p, n) ≠ (4, 8). We conclude that for all i, A_{i} is distinct from A′_{i}, i.e. since E_{i} has two elements, A_{i} and A′_{i} are complementary in E_{i}. □

Lemma 7.3. Here we suppose that the A_{ij} = I ∩E_{ij} are not all empty. Then

(i) m + 1 does not belong to I;

(ii) there exists a pair (i, j) such that A_{ij} = E_{ij}, unique except for (p, n) = (3, 7), where I_{0} = E_{12} ∪ E_{23} ∪ E_{13} may belong to F;

(iii) we have, for (i, j, k) permutation of {1, 2, 3},

A_{ij} = E_{ij} ⟺ A_{k} = ∅;

(iv) if A_{12} = E_{12} and if ∅ ⊊ A_{13} ⊊ E_{13}, then (A_{1}, A_{23}) = (E_{1}, ∅).

Proof. We suppose for instance A_{12} ≠ ∅. By Proposition 5.1, we know that the graph of {I, I_{1}, I_{2}} is a path (since I ∩ I_{1} ∩ I_{2} = A_{12} ≠ ∅), and that its vertex of valency 2 has no index of weight 1. The sets of indices of weight one in I, I_{1} and I_{2} are respectively (I ∩{m+1})∪A_{3}, (E_{1}∖A_{1}) ∪ (E_{13}∖A_{13}) and (E_{2}∖A_{2}) ∪ (E_{23}∖A_{23}). The sets of indices of weight two in I ∩ I_{1}, I ∩ I_{2} and I_{1} ∩ I_{2} are respectively A_{1} ∪ A_{13}, A_{2} ∪ A_{23}, and E_{12}∖A_{12}.

First suppose A_{12} ≠ E_{12}. Then in the path above I_{1} and I_{2} are adjacent, and one of them has valency two and thus contains no index of weight one, the other one is not adjacent to I. Thus

∅ ⊊ A_{12} ⊊ E_{12} ⟹ (A_{1}, A_{2}, A_{13}, A_{23}) = \begin{matrix}(E_{1}, ∅, E_{13}, ∅) or \\ (∅, E_{2}, ∅, E_{23}) \end{matrix} ,

which establishes the “existence part” of (ii), and (up to exchange of 2 and 3) the item (iv).

Suppose for instance A_{12} = E_{12} . Then, we have a path I_{1} ∼ I ∼ I_{2} (since I_{1} and I_{2} are no more adjacent), I has no index of weight one: m + 1 does not belong to I as stated in (i), and A_{3} is empty, as stated in the part ⇒ of(iii).

Conversely, suppose A_{3} = ∅. If ∅ ⊊ A_{12} ⊊ E_{12}, we obtain I = E_{1} ∪ E_{13} ∪ A_{12} ⊂ I_{1}, thus I = I_{1}, a contradiction. If A_{12} = ∅, we may suppose (by (ii)) for instance A_{13} = E_{13}, and by the part ⇒ of (iii), A_{2} = ∅: I = A_{1} ∪ A_{23} ∪ E_{13}, with A_{1} and A_{23} ≠ ∅ (otherwise, I should be a strict subset or I_{3} or I_{1}). Then, the set {I, I_{1}, I_{2}} is a cycle, with m′ = |I ∪ I_{1} ∪ I_{2}| = m − |E_{3}| ≤ m − 1. By Proposition 3.5, we must have m′ = m−1 and n = m′ +1. By 3.5 again, the last equality implies |I ∩ I_{1}| = 1, i.e. |A_{1} ∪ E_{13}| = 1, a contradiction. Thus, A_{12} = E_{12}, as announced.

It remains to discuss the “unicity” in (ii). Suppose A_{12} = E_{12} and A_{13} = E_{13} for instance. We then have A_{2} = A_{3} = ∅, and I = A_{1} ∪E_{12} ∪ E_{13} ∪A_{23}, with A_{23} ≠ ∅ (since I ⊄ I_{1}). By (iv), we conclude A_{23} = E_{23}, since A_{12} and A_{13} are non empty. Thus all A_{i} are empty and I coincides with E_{12} ∪ E_{13} ∪ E_{23} i.e. the set W_{2} of indices of weight 2 in the cycle (I_{1}, I_{2}, I_{3}). Equaling the cardinalities we obtain p = |W_{2}| = 3p − m, thus m = 2p and (p, n) = (3, 7). □

Apart from the two “exotic” solutions for (p, n) = (3, 7) or (4, 10) exhibited in 7.2 and 7.3, we just have proved that the set F∖{I_{1}, I_{2}, I_{3}} is a disjoint union of three components F_{1}, F_{2} and F_{3}, where F_{i} = {I ∈ F, I ≠ I_{1}, I_{2}, I_{3} | I ∩ E_{i} = ∅}. We now evaluate their cardinality.

Lemma 7.4. The set F_{3} = {I ∈ F, I ≠ I_{1}, I_{2} | (A_{3}, A_{12}) = (∅, E_{12})} contains at most p − |E_{12}| − 1 elements.

Proof. Let

I = A_{1} ∪ A_{2} ∪ E_{12} ∪ A_{13} ∪ A_{23} ,

with A_{1}, A_{2}, E_{13}∖A_{13} and E_{23}∖A_{23} non-empty, be an element of F_{3}. Its intersection B_{1} = A_{1} ∪ E_{12} ∪ A_{13} with I_{1} contains E_{12} thus is not empty.

We now prove that when I runs through F_{3} the sequence B_{1} = I ∩I_{1} is totally ordered. Let I′ = A′_{1}∪A′_{2}∪E_{12}∪A′_{13}∪A′_{23} be another element of F_{3}. Put B′_{1} = I′∩I_{1}, X = I_{1}∖B_{1} and X′ = I_{1}∖B′_{1}. We suppose that B_{1} and B′_{1} satisfy no inclusion. Since they both contain E_{12}, Corollary 5.2 shows that I_{1} = B_{1} ∪ B′_{1} and that X ∩ X′ = ∅. In particular we obtain E_{13} = A_{13} ∪ A′_{13} and A_{2} ∩ A′_{2} = ∅. Since A_{13} and A′_{13} are distinct from E_{13}, the first relation proves that there are not empty, thus by Lemma 7.3, that A_{1} = A′_{1} = E_{1}. Now we observe that the intersections A_{2} ∪ E_{12} ∪ A_{23} and A′_{2} ∪ E_{12} ∪ A′_{23} of I and I′ with I_{2}, satisfy no inclusion, since A_{2} and A′_{2} are non-empty and disjoint. By exchanging I_{1} and I_{2} we deduce that A_{1} and A′_{1}, which both coincide with E_{1}, must be disjoint, a contradiction. We conclude (by Corollary 5.2) that B_{1} and B′_{1} satisfy a strict inclusion, for instance B′_{1} ⫋ B_{1}, i.e.

A′_{1} ⊂ A_{1} and A′_{13} ⊂ A_{13} ,

equality holding in at most one inclusion. In particular, suppose A′_{1} = A_{1}, then A_{13} ⫌ A′_{13} is not empty, and by the lemma above, A_{1} = E_{1}. The totally ordered sequence (A_{1})_{I∈F_{3}} contains a strictly increasing sequence of non-empty, strict subpaces of E_{1} (with at most |E_{1}| − 1 terms) and of at most |E_{13}| terms A_{1} equal to E_{1} (associated with a strictly increasing sequence of strict subspaces A_{13} of E_{13}). We have then |F_{3}| ≤ |E_{1}| + |E_{13}| − 1 = p − |E_{12}| − 1 as announced. □

Coming back to the proof of Theorem 7.1, we conclude that the family F contains apart from I_{1}, I_{2}, I_{3} at most 3p − 3 − |W_{2}| = m − 3 non-exotic terms. The proof is complete for n ≤ 3p − 3, i.e. n = m.

Case n = m + 1, i.e. n = 3p − 2. Since n = m + 1, the E_{ij} are singletons, and their strict subspaces are empty. The elements of F_{3} for instance are of the form I = A_{1} ∪ A_{2} ∪ E_{12}, with A_{1} and A_{2} non-empty. Actually, we have seen in the above proof that the sequence (A_{1})_{I∈F_{3}} contains at most |E_{13}| = 1 term equal to E_{1}, so is a strictly totally ordered sequence of non-empty subspaces of E_{1}, with at most |E_{1}| = p − 2 terms. Of course similar remarks are valid for the subspaces A_{2} of E_{2}. We now prove that if two families F_{i} are nonempty, one of them at least is a singleton. Let I = A_{1} ∪ A_{2} ∪ E_{12} and I′ = A′_{1} ∪ A′_{3} ∪ E_{13} be elements of F_{3} and F_{2} respectively. First, A_{1} and A′_{1} must satisfy an inclusion. Otherwise, (I, I_{1}, I′, I_{3}, I_{2}) should be a cycle for the relation ∼. Indeed, the sets of indices of weight 2 in I ∩ I_{1}, I′ ∩ I_{1}, I′ ∩ I_{3}, I_{3} ∩ I_{2} and I ∩ I_{2} (respectively A_{1}∖A′_{1}, A′_{1}∖A_{1}, A′_{3}∖A_{3} = A′_{3}, E_{23}∖(A_{23} ∪ A′_{23}) = E_{23} and A_{2}∖A′_{2} = A_{2}), should be all non-empty. Now, since |I ∪ I′ ⋃_{j} I_{j}| = |⋃_{j} I_{j}| = m = n − 1, by 3.5, the subsets above should all be singletons, in particular A_{2} and A′_{3}, implying that A_{1} and A′_{1} should contains p − 2 elements, i.e. both coincide with E_{1}, a contradiction. Therefore we may suppose A′_{1} ⊂ A_{1}. The intersections B_{1} = A_{1} ∪ E_{12} and B′_{1} = A′_{1} ∪ E_{13} of I and I′ with I_{1} satisfy B_{1} ∩B′_{1} = A′_{1} ≠ ∅, and thus, by Corollary 5.2, E_{1} = A_{1} ∪A′_{1}, i.e. A_{1} = E_{1}, which specifies uniquely I = E_{1} ∪ {a_{2}} ∪ E_{12} in F_{3}: |F_{3}| = 1 as announced.

If F_{1} is empty, we have |⋃ F_{i}| ≤ 1 + (p − 2), and F contains at most p + 2 non-exotic elements.

Otherwise, let I” = A”_{2} ∪ A”_{3} ∪ E_{23} be an element of F_{1}. By exchanging I” with I′ or I, we know that A”_{2} and A_{2} on the one hand, A”_{3} and A′_{3} on the other hand, must satisfy an inclusion, and that the larger of the subsets coincides with E_{2} or E_{3} respectively. We thus have

|A_{2}| = 1 ⇒ A”_{2} = E_{2} ⇒ |A”_{3}| = 1 ⇒ A_{3} = E_{3} .

: ⋃ F_{i} contains at most 3 elements, of the form E_{1} ∪ {a_{2}} ∪ E_{12}, {a′_{1}} ∪ E_{3} ∪E_{13} and E_{2} ∪{a”_{3}}∪E_{23}, with uniquely determined elements a_{i}, a′_{i} or a”_{i} in E_{i}.

We conclude that |⋃ F_{i}| ≤ max(3, p − 1), and thus that in the case n = 3p − 2, F contains p + 2 (resp. 6) non-exotic elements if p ≥ 4 (resp. p = 3).

To complete the proof of the theorem, it remains to discuss the occurrence of the “exotic” elements when (p, n) = (3, 7) or (4, 10). Actually, in both cases, an exotic element, say I, described by Lemma 7.2 is inconsistent with an element, say J, of ⋃ F_{j}: there exists k = 1, 2, 3 such that the set {I, J, I_{k}} contradicts Proposition 5.1. So F contains at most 6 + 1 = n (resp. 6 = p + 2) elements when p = 3 (resp. p = 4). This completes the proof of Theorem 7.1.

8. Kissing number of a lattice of index 2 , maximal length

The goal of this section is to prove Theorem 1.1 by giving an explicit upper bound for the number s of pairs ±x of minimal vectors of the lattice, bound depending on the dimension n modulo 6.

Theorem 8.1. Let L be a lattice of dimension n ≥ 6, index 2 with length ℓ = n. Bounds for the half kissing number s of L are given in the following table.

n mod 6  upper bound for s
0  19 if n = 6 ; (2n^{2} + 24n − 45)/9 if n ≥ 12
1  24 if n = 7 ; (2n^{2} + 20n − 13)/9 if n ≥ 13
2  32 if n = 8 ; (2n^{2} + 22n − 25)/9 if n ≥ 14
3  37 if n = 9 ; (2n^{2} + 24n − 54)/9 if n ≥ 15
4  44 if n = 10 ; (2n^{2} + 20n − 4)/9 if n ≥ 16
5  (2n^{2} + 22n − 34)/9 (n ≥ 11)

Proof. To compute the number s = \frac{|S(L)|}{2} of pairs of minimal vectors of the lattice L, we use the following description

S(L) = S(L_{0}) ∪ §_{0} ∪ S_{1} ∪ S_{2} ∪ ⋯ ∪ S_{⌊ \frac{n}{2} ⌋} ,

where S(L_{0}) stands for the set of minimal vectors of the lattice L_{0} = ⟨e_{1}, e_{2}, …, e_{n}⟩, and S_{p} for the set of pairs ±x where x is a minimal vectors of type p. Let t_{p} = \frac{|S_{p}|}{2} denote the number of such pairs. Since S(L_{0}) = {±e_{1}, ±e_{2}, ⋯ ± e_{n}} and S_{0} = {±e}, we obtain

s = n + 1 + ∑_{p=1}^{⌊ \frac{n}{2} ⌋} t_{p}

where we shall use of the estimations of the t_{p} given in the sections above, and the sharper one obtained for t_{1} + t_{2} in 4.2:

s ≤ n + 10 + ∑_{p=3}^{⌊ \frac{n}{2} ⌋} t_{p} .

For p ≥ 3, let T_{1} and T_{2} denote the bounds for t_{p} given by Theorems 6.1 and 7.1. If S_{p} may contain a cycle of length 3, i.e.,by 7.1, if \frac{n+2}{3} ≤ p ≤ \frac{n−1}{2}, we obtain for t_{p} the estimation t_{p} ≤ max(T_{1}, T_{2}). Otherwise, t_{p} ≤ T_{1}. Now suppose p = \frac{n+2}{3}. If (p, n) = (3, 7), T_{1} and T_{2} coincide with n = 7 ; if p ≥ 4, T_{2} = p+2 < p+5 ≤ T_{1}, and again max(T_{1}, T_{2}) = T_{1}. The bound T_{2} is to take into account for the integers p such that \frac{n+2}{3} < p ≤ \frac{n−1}{2}, i.e. for the elements of

P = \{p_{1}, p_{1} + 1, …, p_{k}\}, with p_{1} = ⌈\frac{n + 3}{3}⌉, p_{k} = ⌊\frac{n − 1}{2}⌋ .

Actually, P is empty for n = 6, n = 8 and n = 10, it contains the type p = 3 for n = 7 only (and then T_{1} = T_{2} = 7), the type p = 4 for n = 9 (and then T_{1} = T_{2} = 9). Thus, for p ∈ P and n ≤ 10, we have t_{p} ≤ T_{1} = max(T_{1}, T_{2}), while for p ∈ P and n ≥ 11, we have t_{p} ≤ T_{2} = max(T_{1}, T_{2}) (since then T_{2} = n ≥ \frac{n−1}{2} + 6 ≥ p + 6 ≥ T_{1}).

For n ≤ 10, we sum up the bounds given by 6.1 5.3 and 4.2:

n = 6: s ≤ 7 + 9 + 4 = 20 (bound to be improved below); n = 7: s ≤ 8 + 9 + 7 = 24; n = 8: s ≤ 9 + 9 + 8 + 6 = 32; n = 9: s ≤ 10 + 9 + 8 + 9 = 36; n = 10: s ≤ 11 + 9 + 8 + 10 + 6 = 44. From now on, we suppose n ≥ 11. Let Σ_{1} denote the sum of the bounds T_{1} given by 6.1 for t_{p}, 3 ≤ p ≤

⌊\frac{n}{2}⌋: Σ_{1} = 8 + ∑_{p=4}^{⌊ \frac{n}{2} ⌋}(p + 6) − ε = ⌊\frac{n}{2}⌋(\frac{⌊ \frac{n}{2} ⌋+13}{2}) − 16 − ε , with ε = 1 if n is odd, ε = 5 if n is even:

Σ_{1} = \frac{n^{2} + 24n − 161}{8} if n is odd, Σ_{1} = \frac{n^{2} + 26n − 168}{8} if n is even

For p ∈ P and n ≥ 11 (thus p ≥ 5), we must replace the bound T_{1} by the bound T_{2} = n. Let Σ_{2} denote the sum of these correcting terms T_{2} − T_{1} = n − (p + 6) (resp. n − (p + 5) for p ≠ \frac{n−1}{2} (resp. = \frac{n−1}{2}). We have

Σ_{2} = ∑_{p∈P}(n − 6 − p) + ε, with ε = 1 if n is odd
=k(n − p_{1} − 6) − 1 − 2 − ⋯ − (k − 1) + ε, with k = (p_{k} − p_{1} + 1)
=(p_{k} − p_{1} + 1)(n − \frac{p_{1} + p_{k}}{2} − 6) + ε .

One easily checks the following expressions of this correcting term, depending on n modulo 6.

\begin{matrix}n & 72Σ_{2} \\ ≡ 0 & 7n^{2} − 114n + 432 \\ ≡ 1 & 7n^{2} − 128n + 625 \\ ≡ 2 & 7n^{2} − 130n + 592 \\ ≡ 3 & 7n^{2} − 96n + 297 \\ ≡ 4 & 7n^{2} − 146n + 76 \\ ≡ 5 & 7n^{2} − 112n + 457 \end{matrix}

We now use the inequality s ≤ n + 1 + 9 + Σ_{1} + Σ_{2} to obtain the table of Theorem 8.1 for n ≥ 7. Of course the bounds for s = n + ∑ t_{p} obtained by bounding separately the t_{p} are not optimal. This is the case when (p, n) = (3, 6): the maximal value 4 of t_{3} is inconsistent with the maximal value 9 of t_{1}+t_{2}, which leads to the bound s ≤ 6+1+9+3 = 19 instead of 20.

[Suppose t_{3} = 4. The four sets I of type 3 are, up to permutation, I_{1} = {1, 2, 3}, I_{2} = {1, 3, 4}, I_{3} = {1, 4, 5}, I_{4} = {1, 5, 2}; then, no index i ∈ {1, 2, …, 6} has valency 3 for the relation “i ≡ j if e−e_{i}−e_{j} is minimal”, as we now prove. There are 3 cases to consider according as the weight of i (with respect to the I_{j}) is equal to 4, 2 or 0. First, i = 1 has at most valency 2: Proposition 3.3 prevents 1 ≡ 6, and proves that 1 ≡ 2 is inconsistent with 1 ≡ 3 or 1 ≡ 5. For i = 2, Proposition 3.3 proves that 2 ≡ 3 is inconsistent with 2 ≡ 6, and by Proposition 3.5 we see that 2 ≡ 5 is not possible, and that 2 ≡ 3 is inconsistent with 2 ≡ 1 (for instance the sets {2, 1}, {2, 3}, and I_{2} = {1, 3, 4} form a cycle of length 3 and m = 4 indices, impossible for n = 6). The same argument implies that 6 ≡ 2 is inconsistent with 6 ≡ 3 (and 6 ≡ 5). Thus, by Corollary 4.2, we have t_{1} + t_{2} ≤ 8. ] □

The difference between \frac{n(n+1)}{2} and the bound for s given in 8.1 takes the values

2, 4, 4, 9, 11, 16, 19, 26, 30, 36, 44, …

for n = 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, …, is always positive and monotone increasing, and asymptotic to 5n^{2}/18 as n → ∞. This completes the proof of Theorem 1.1.

References

[B-R] E.P. Baranovskii, S.S. Ryshkov, Derivation of perfect lattices from admis-

sible centerings, Russian Math. Survey 40,4 (1985),155–156. [C-S] J.H. Conway, N.J.A. Sloane, Low-Dimensional Lattices. III. Perfect Forms,

Proc. Royal Soc. London A 418 (1988), 43–80. [D-S-V] M. Dutour Sikiric, A. Schürmann, F. Vallentin, Classification of eight di-

mensional perfect forms, Math. arXiv, NT/0609388.

[M] J. Martinet, Bases of minimal vectors in lattices, II, Arch. Math. 89 (2007), 541–551.