REDUCTION MODULO 2 AND 3

OF EUCLIDEAN LATTICES

by Jacques Martinet

Abstract. Let Λ be a Euclidean lattice, We study upper bounds for the norm of shortest representatives of Λ modulo dΛ, d = 2 or 3, as well as the structure of the sets of such vectors with the same norm and the same image modulo d. Root systems appear in connection with this last problem. Résumé. Soit Λ un réseau euclidien. Nous étudions des majorations de la norme des représentants les plus courts des classes de Λ modulo dΛ, d = 2 ou 3, ainsi que la structure des ensembles de tels vecteurs qui ont même norme et même image modulo d. Les systèmes de racines interviennent en liaison avec ce dernier problème. Titre français : Réduction modulo 2 et 3 des réseaux euclidiens.

In this paper, we prove some results which are useful for the determination of the classes Λ/dΛ where Λ is a lattice in some real vector space E and d ≥ 2 an integer. For any λ > 0, we denote by S_{λ} = S_{λ}(Λ) (resp. S′_{λ} = S′_{λ}(Λ)) the set of vectors (resp. of primitive vectors) of norm λ in Λ and we set s_{λ} = \frac{1}{2} |S_{λ}| and s′_{λ} = \frac{1}{2} |S′_{λ}|. We write simply S and s when λ is the norm (or minimum) N(Λ) of Λ. We denote by m this norm and by m′ the norm of the second layer of Λ.

Our aim is to study congruences modulo d among vectors of Λ and deduce from this a system of representatives of Λ/dΛ ∖ {0} up to the sign. We wish to find vectors which are as short as possible. To this end, we may choose in each class modulo dΛ one of the shortest possible vectors. The results to be proved below assert in particular that for d = 2 (resp. for d = 3), one must consider vectors of norm up to the greatest number r ≤ 2m (resp. r ≤ 2m + m′) such that the layer S_{r}(Λ) is not empty. We also give conditions under which two vectors of norm N ≤ 2m (resp. N ≤ 2m + m′) may be congruent modulo 2 (resp. modulo 3). Once more, root systems play an important rôle.

We develop some general results in section 1, then turn to results modulo 2 in section 2 and modulo 3 in section 3. Section 4 is devoted to the study of the Leech lattice modulo 3. We describe briefly some applications (mainly to 𝔼_{8} and Λ_{24}) in section 5.

I thank Christine Bachoc, Heinz-Georg Quebbemann, and Nils Skoruppa for various comments on this paper.

Key words and phrases. Lattices, short vectors, reduction modulo 2 and 3.

Laboratoire associé au C.N.R.S. (UMR 5465) – Université Bordeaux 1

§ 1. Basic results. We shall only consider non-zero vectors x, y such that y ≠ ±x. Moreover, we shall enumerate classes of Λ mod dΛ in pairs c, −c. They reduce to a single element if and only if d = 2 (or if c = {0}).

1.1. Proposition. Let x and y ≠ ±x be two non-zero vectors of Λ, such that y − x = dz for some z ∈ Λ. Then, the following three identities hold:

(1) N(y) + (d − 1)N(x) = d((d − 1)N(z) + N(x + z)).

(1’) N(x) + (d − 1)N(y) = d((d − 1)N(z) + N(y − z)).

(2) N(y) + N(x) = 2(d − 1)N(z) + N(x + z) + N(y − z). Moreover, if Λ is integral, we have N(y) ≡ N(x) mod d, and even N(y) ≡ N(x) mod 4 if d = 2.

Proof. We have

N(y) = N(x) + 2d x · z + d^{2}N(z) = N(x) + d(d − 1) N(z) + d(N(x + z) − N(x)) ,

which proves (1). We then derive (1’) from (1) by using the double exchange y ↔ x and z ↔ −z and finally prove (2) by adding (1) and (1’) and dividing out both sides by d. The last two assertions are consequences of the formula displayed above. □

1.2. Proposition. We keep the hypotheses of Proposition 1.1. Let a = N(z), b = N(x + z) and c = N(y − z).

(1) If d = 2, then c = b.

(2) If d > 2, then

N(x) = (d − 1)a + b + \frac{b − c}{d − 2} and N(y) = (d − 1)a + c − \frac{b − c}{d − 2} ;

Moreover, 2 x · z = −da − \frac{b − c}{d − 2}, N(y) − N(x) = \frac{d(c − b)}{d − 2} and

2 x · y = −(d^{2} − 2d + 2)a + b + c.

Proof. We have y − z = x + (d − 1) z, hence y − z = x + z if d = 2. If d > 2, the calculation of the norms of x + z and of x + (d − 1)z yields N(x) + 2 x · z = b − a and N(x) + 2(d − 2) x · z = −(d − 1)^{2}a + c, which gives us first the values of N(x) and x · z, then that of N(y) by Proposition 1.1, and finally the other values we need. □

1.3. Theorem. Let x, y ∈ Λ such that y = x+dz for some z ∈ Λ and that none of the vectors x, y, y ± x is zero. If d = 3, suppose moreover that none of the equalities x = −2y and y = −2x hold. Then, we have N(y) + N(x) ≥ 2d m, and equality holds if and only if d = 2 or d = 3 and if moreover:

(1) When d = 2, x and y are of the form x = e − f and y = e + f where e and f are orthogonal minimal vectors.

(2) When d = 3, x and y are of the form x = e − f and y = e + 2f where e, f and e + f are minimal vectors.

If d = 2, x and y, of norm 2m, are orthogonal, and {±x, ±y} is the second layer of the square lattice generated by e and f. If d = 3, ±x, ±y and ±(x + y), of norm 3m, constitute the second layer of the hexagonal lattice of minimum m whose minimal vectors are ±e, ±f and ±(e + f).

Proof. By Proposition 1.1, (2), since z ≠ 0, we have N(x) + N(y) ≥ 2(d − 1)m + N(x + z) + N(y − z). If x + z = 0, then y = 2z = −2x, y − z = x + 2z = −x and N(x) + N(y) = 5m whereas 2(d − 1)N(z) + N(y − z) = (2d − 1)m. By Proposition 1.1, we must have d = 3. Similarly, y − z = 0 implies x = −2y and again d = 3. Consequently, x+z and y −z are non-zero, which implies the required inequality.

Suppose now that equality holds, i.e. that N(x) + N(y) = 2d m. Then, z, x + z and y−z = x+2z are minimal. Now, x+z and z are not proportional, for x+z = z implies x = 0 and x + z = −z implies y − z = 0. We thus have |(x + z) · z| ≤ \frac{m}{2}, whence

N(x) ≤ N(x + z) + N(z) + 2|z · (x + z)| ≤ 3m

and similarly N(y) ≤ 3m. Since N(x) + N(y) ≥ 2d m, we have d ≤ 3.

Set e = x + z and f = z.

If d = 2, we have e−f = x, e+f = x+2z = y. This implies x·y = N(e)−N(f) = 0 and also e · f = 0 since N(e + f) = 2m = N(e) + N(f).

If d = 3, we again have e−f = x, but now y = x+3z = e+2f, and e+f = y −z is minimal. This last property implies e · f = −\frac{m}{2}, hence N(x) = N(e) + N(f) − 2e · f = 3m, N(y) = N(e) + 4N(f) + 4e · f = m + 4m − 2m = 3m and similarly N(x + y) = N(2e + f) = 3m.

Conversely, if x and y have the form given in the theorem above, it is easily seen that the equality N(x) + N(y) = 2d m holds in both the cases d = 2 and d = 3. □

1.4. Remark. If Λ is integral, more restrictions can be derived from the proof of Theorem 1.3. For instance, if d = 3 and if N(x) + N(y) = 6m, then the norm m of Λ must be even, since −2e · f = m.

Since vectors which are independent modulo dΛ are a fortiori independent in Λ, a sequence e_{1}, …, e_{n} of representatives of the successive minima m_{1} = m ≤ m_{2} ≤ ⋯ ≤ m_{n} of Λ must occur among a set of short representatives of L/dL.

For the applications to the classification up to isometry of sublattices with cyclic quotients of order d, it suffices to consider the classes of Λ^{∗} mod dΛ^{∗} up to an automorphism of Λ. Exchanging Λ and Λ^{∗}, we go back to Λ itself. Let us say that two orbits o and o′ in Λ are d-equivalent (denoted o ∼_{d} o′) if there exist x ∈ o and x′ ∈ o′ such that x′ ≡ x mod dΛ. We denote by T a set of representatives of the non-zero orbits modulo d-equivalence. (We represent the null class by {0}.) To an orbit o, we attach its (d-)weight wt(o), which is the number of elements

within a class modulo d of o. Of course, we have the relation \frac{1}{wt(o)} |o| = \frac{1}{wt(o′)} |o′| whenever o′ ∼_{d} o. (Even if we choose the orbits so as to minimize the norm, we cannot exclude the possibility that two orbits of vectors having the same norm be d-equivalent.)

Now, a description of Λ/dΛ corresponds to a weighted formula

(1.5)  ∑_{o∈T} \frac{1}{wt(o)} |o| = d^{n} − 1 .

Examples for d = 2 and d = 3 will be given in the forthcoming sections.

§ 2. Reduction modulo 2. It results from Theorem 1.3 that vectors of norm N ≤ 2m represent distinct classes in Λ/dΛ except for pairs (x, −x) and possibly for orthogonal vectors x, y of norm 2m. For x ∈ S_{2m}, assuming S_{2m} ≠ ∅, let ℓ_{2}(x) = ℓ(x) be the number of lines containing a vector y ∈ S_{2m} with y ≡ x mod 2Λ (or y ≡ x mod 2S_{m}, this amounts to the same). Note that ℓ(x) in an invariant of the class C of x in Λ/2Λ, which allows us to define ℓ(C) for any class C mod 2Λ which contains elements of S_{2m}. We have for ℓ the obvious bounds 1 ≤ ℓ(x) ≤ n. The following statement is now clear:

2.1. Theorem. Any complete set of representatives of Λ/2Λ whose elements are vectors whose norms are minimal in their class modulo 2Λ contains elements of all the spheres S_{k} with k ≤ 2m. Moreover, we have

∑_{0<k<2m} s_{k} + ∑_{x∈S_{2m} mod 2Λ} \frac{1}{ℓ(x)} ≤ 2^{n} − 1 ,

and equality holds if and only if all classes modulo 2Λ possess representatives of norm at most 2m. □

When ℓ(x) is constant on S_{2m}, for instance when Aut(Λ) acts transitively on S_{2m}, the formula of Theorem 2.1 can be written in the simplified form

(2.2)  ∑_{0<k<2m} s_{k} + \frac{1}{ℓ} s_{2k} ≤ 2^{n} − 1 .

Taking into account the upper bound ℓ(x) ≤ n, we immediately obtain:

2.3. Theorem. We have

∑_{0<k<2m} s_{k} + \frac{1}{n} s_{2m} ≤ 2^{n} − 1 .

If equality holds, vectors of norm 2m in Λ appear in systems of 2n vectors lying on n pairwise orthogonal lines, and one obtains a system of representatives of Λ/dΛ∖{0} by taking one vector out of each such system and one vector in each pair ±x of nonzero vectors of norm N < 2m. □

The formula above plays a crucial rôle in Conway’s characterization of the Leech lattice, see [C-S], chapter 12. Computing s_{4}, s_{6}, s_{8} by means of Theta series, Conway obtains the formula

s_{4} + s_{6} + \frac{1}{24} s_{8} = 98280 + 8386560 + \frac{199017000}{24} = 16777215 = 2^{24} − 1 ,

valid a priori for any even 24-dimensional unimodular lattice without roots.

Suppose that there exists an orthogonal frame of n vectors of norm 2m, and let

L be the lattice they generate. Then, the ratio \frac{(2m)^{n}}{det(Λ)} is the square of an integer,

namely of the index [Λ : L]; in particular, if Λ is integral and if n is even, det(Λ) must be a square. When this condition is not satisfied, there may be at most n − 1 directions of pairwise orthogonal vectors defining the same class modulo 2. Thus:

2.4. Theorem. Suppose that there does not exist in Λ any orthogonal frame of vectors of norm 2m. We then have

∑_{0<k<2m} s_{k} + \frac{1}{n − 1} s_{2m} ≤ 2^{n} − 1 .

If equality holds, vectors of norm 2m in Λ appear in systems of 2(n − 1) vectors lying on n−1 pairwise orthogonal lines, and one obtains a system of representatives of Λ/dΛ ∖ {0} by taking one vector out of each such system and one vector in each pair ±x of non-zero vectors of norm N < 2m. □

As was pointed out to me by Quebbemann on the example of K_{12}, it is interesting to consider examples with constant ℓ(x) ≤ n − 2. Indeed, some examples can be easily handled via Theorem 2.1, by first proving sharper bounds for ℓ other that ℓ(x) ≤ n or ℓ(x) ≤ n − 1. The following proposition can be used to derive such bounds. We denote by A A A_{n} (n ≥ 1), D D D_{n} (n ≥ 2) , E E E_{n} (n = 6, 7, 8) the irreducible root systems whose vectors all have norm 2 and by 𝔸_{n}, 𝔻_{n}, 𝔼_{n} the corresponding root lattices. Recall that D D D_{2} ≃ A A A_{1} ⊥ A A A_{1} and A A A_{3} ≃ D D D_{3}.

2.5. Theorem. A set T_{r} = {±x_{1}, …, ±x_{r}} of r ≥ 2 vectors of S_{2m} is contained in a single class modulo 2Λ if and only if the set \{\frac{±x_{i}±x_{j}}{2} \} is a (rescaled) root system R of type D D D_{r} contained in S_{m}, and the map T_{r} → R is one-to-one if r ≠ 4, and three-to-one if r = 4.

Proof. Given pairwise non-proportional vectors x_{1}, …, x_{r} ∈ S_{2m}, set

ε_{i} = \frac{x_{i}}{2} , (i = 1, …, r) and e_{i,j}^{+} = \frac{x_{i} + x_{j}}{2} , e_{i,j}^{−} = \frac{x_{i} − x_{j}}{2} (1 ≤ i < j ≤ r) .

If x_{1}, …, x_{r} represent the same class modulo 2, they are pairwise orthogonal. Then, the system of vectors ±ε_{i}, all of norm \frac{m}{2}, is an orthogonal frame in some r-dimensional subspace of E, and the vectors e_{i,j}^{+} and e_{i,j}^{−} belong to Λ if and only if x_{1} ≡ ⋯ ≡ x_{r} mod 2Λ. If it is the case, they lie in S_{m}, and the set {±e_{i,j}^{+}, ±e_{i,j}^{−}} is a root system of type D D D_{r}, since e_{i,j}^{±} = ε_{i} ± ε_{j}. The converse is clear, since e_{i,j}^{+} belongs to Λ if and only if x_{i} ≡ x_{j} mod Λ.

The map T_{r} → R is clearly onto by the proof of the first assertion. Now, consider the lattice 𝔻_{r} scaled to its natural norm 2; it is the even sublattice of ℤ^{r}, whose canonical basis we denote by (ε_{1}, …, ε_{r}). If another orthogonal frame (±ε′_{1}, …, ±ε′_{r}) generates a lattice L isometric to ℤ^{r} containing 𝔻_{r}, we have 𝔻_{r} ⊂ L ⊂ 𝔻_{r}^{∗}. The quotient 𝔻_{r}/𝔻_{r}^{∗} is cyclic if r is odd and of type (2, 2) if r is even, and in this last case, the other two lattices are 𝔻_{r}^{±} = 𝔻_{r} ∪ \frac{1}{2} (±ε_{1} + ε_{2} + ⋯ + ε_{r}), of norm min(2, \frac{r}{4}). Hence, T_{r} → R is injective if r ≠ 4. If r = 4, both lattices 𝔻_{r}^{+} and 𝔻_{r}^{−} are isometric to ℤ^{4}, so that there are two more systems T′_{r} = {±x′_{1}, …, ±x′_{r}} and T′′_{r} = {±x′′_{1}, …, ±x′′_{r}} which define the same class modulo 2, namely the sets \{\frac{1}{2} (x_{1} ± x_{2} ± x_{3} ± x_{4})\} with an even and and odd number of minus signs respectively. It is easily verified that they define distinct elements of Λ/2Λ: for instance, if \{\frac{1}{2} (x_{1} ± x_{2} ± x_{3} ± x_{4})\} − x_{1} = 2z, then N(z) = \frac{m}{2}, so that z cannot belong to Λ. □

2.6. Corollary. If Λ is an integral lattice of odd norm, one has ℓ(x) ≤ 2 for all x ∈ S_{2m}, and even ℓ(x) = 1 if no two minimal vectors of Λ are orthogonal.

Proof. The lattice 𝔻_{r} scaled to norm m contains minimal vectors with scalar product \frac{m}{2} for all r ≥ 3 and orthogonal minimal vectors for all r ≥ 2. □

2.7. Remark. Given a root system R of type D D D_{r}, r ≥ 2 inside S(Λ), we recover the orthogonal frame(s) T_{r} ⊂ S_{2m}(Λ) in the following way: let r ∈ R; let R′ = R∩r^{⊥}; one selects an r′ ∈ R′ such that cR′′ = ⟨r, r′⟩^{⊥} ∩R is a root system of type D D D_{r−2} (it could be of type 2A A A_{1} +D D D_{r−4}; this amounts to the same only if r = 4); then, T_{r} is the union of the set T_{r−2} attached to R′′ with {±r, ±r′}. We reduce ourselves in this way to the easy cases of dimensions 2 and 3.

We shall come back later on properties of classes of Λ modulo 2Λ related to root systems contained in Λ. For the while, we give an application of Theorem 2.5:

2.8. Theorem. Suppose that Λ is integral. Let p be a prime number and let t be the number of elementary divisors of (Λ^{∗}, Λ) which are divisible by p. Let x ∈ S_{2m}.

(1) If p is odd and does not divide m, we have ℓ(x) ≤ max(2, n − t).

(2) If p = 2 and if m ≡ 2 mod 4, we have ℓ(x) ≤ max(2, n + 2 − t).

Proof. Let x ∈ S_{2m} with ℓ(x) ≥ 3 and let r = ℓ(x). By Theorem 2.5 and Corollary 2.6, the norm m of Λ is even and there exists inside S(Λ) a root system R of type D D D_{r}. Let L ∼ 𝔻_{r} be the lattice generated by R and let F be the subspace of E spanned by R. Then, F^{⊥} ∩ Λ^{∗} is an (n − r)-dimensional lattice contained in Λ^{∗}.

Since Λ is integral, L′ = F ∩ Λ is an (n − r)-dimensional lattice contained in Λ. We have the inclusions

L ⊥ L′ ⊂ Λ ⊂ Λ^{∗} ⊂ L^{∗} ⊥ L′^{∗}

which induce an injective homomorphism Λ^{∗}/Λ → L^{∗}/L ⨁ L′^{∗}/L′.

Let u and u′ be the number of elementary divisors divisible by p in L and in L′ respectively. One has t ≤ u + u′. Since L is isometric to \sqrt{\frac{m}{2}} 𝔻_{r} and p does not divide \frac{m}{2}, the value of u is 0 if p is odd, 1 if p = 2 and r is odd, and 2 if p = 2 and r is even. Using the trivial upper bound u′ ≤ n − r, we see that r is bounded above by n + u − t.

If p is odd, this is precisely the bound of the proposition.

If p is even, we have u = 2 if r is even and u = 1 if r is odd, whence the bound r ≤ n + 2 − t. □

For some small values of n (certainly for all n ≤ 6, see below, table 2.10), it may happen that representatives of norm N ≤ 2m exist on an open set in the set of ndimensional lattices. Examples are easily obtained using the following proposition:

2.9. Proposition. Suppose that there exists for some n an n-dimensional lattice Λ such that all classes in Λ/2Λ possess representatives of norm N < 2m (strict inequality). Then, there exists a neighbourhood of Λ on which all lattices satisfy this condition.

Sketch of proof. Let

m_{1}(Λ) = min_{x∈Λ∖{0}} N(x) and m_{2}(Λ) = max_{x∈Λ, N(x)≤2m_{1}} N(x) ,

and let ε > 0. Since the set T of vectors in Λ of norm N ≤ 2m is finite, we can find a neighbourhood N_{ε} of the identity in GL(E) such that

∀ u ∈ N_{ε} and ∀ x ∈ u(T), m_{1} − ε < N(u(x)) < m_{2} + ε ,

and moreover that all vectors x with N(x) < m_{2} + ε belong to u(T). (Compare [M], Chapter III, proof of Lemma 4.2.) Since u is injective, u(T) and T have the same cardinality, indeed 2^{n} − 1. Choosing ε < 2m_{1} − m_{2}, we obtain 2^{n} − 1 vectors in u(Λ) of norm N < 2 N(Λ). The proposition to be proved is now a consequence of Theorem 2.1. □

We now give some examples, beginning with irreducible root lattices.

We define as usual 𝔸_{n} and 𝔻_{n}, n ≥ 4 using orthogonal bases (ε_{0}, ε_{1}, …, ε_{n}) and (ε_{1}, …, ε_{n}) of ℤ^{n}, by the respective conditions ∑_{0≤i≤n} x_{i} = 0 and ∑_{1≤i≤n} x_{i} ≡ 0 mod 2. For L = 𝔸_{n} (resp. L = 𝔻_{n}, n ≥ 5), we then consider for every k with 0 ≤ k ≤ \frac{n+1}{2} (resp. with 0 ≤ k ≤ \frac{n}{2}) the orbit o_{2k} of sums of 2k distinct vectors ±ε_{i}, and moreover in case L = 𝔻_{n} the orbit o′_{4} = {±2ε_{i}}. (For 𝔻_{4}, there is a single orbit of vectors of norm 4.) Then, shortest representatives of L/2L need the consideration of all orbits o_{2k} if L = 𝔸_{n} and of moreover o′_{4} if L = 𝔻_{n}, n ≥ 5. In particular, L/2L possesses representatives of norm N ≤ 2m = 4 if and only if L is one of the lattices 𝔸_{n}, n ≤ 4, 𝔻_{n}, n ≤ 5, 𝔼_{6} or 𝔼_{8}.

The cases of 𝔼_{6} and 𝔼_{8} are easily dealt with, using Theorems 2.4 and 2.3 respectively. For 𝔼_{7}, vectors of norm N ≤ 4 represent all classes but one, which is represented by any vector of one among two orbits of norm 6 vectors.

As for the duals of irreducible root lattices which are not similar to a root lattice, it can be verified that all classes modulo 2 possess representatives of norm N ≤ 2m exactly for the lattices 𝔸_{n}^{∗} (3 ≤ n ≤ 6), 𝔻_{5}^{∗}, and 𝔼_{6}^{∗}. (For 𝔼_{7}^{∗} scaled to norm 3, one must make use of vectors of norm 3, 4, 7.)

The following three tables contain some classical lattices. We do not define them here, referring to [C-S], Chapter 6 for the laminated lattices Λ_{n}, to [M], chapter VIII, for Barnes’s series L_{n}^{r} (section 4) and for both the series K_{n}, K′_{n} contained in the Leech lattice Λ_{24} (sections 5 and 7; in particular, Proposition 7.9), and to [C-S], Chapter 8, section 6 or [M], Chapter V, section 4 for the Craig lattices 𝔸_{n}^{(r)}. The lattices which are displayed are rescaled to the smallest norm which makes them integral. Indeed, 𝔸_{n}^{∗} stands for \sqrt{n + 1} 𝔸_{n}^{∗} and 𝔻_{5}^{∗} for 2 𝔻_{5}^{∗}.

Table 2.10. Some lattices with representatives of norm N < 2m.

n = 1 ℤ  s_{1} = 1
n = 2 𝔸_{2} s_{2} = 3
n = 3 𝔸_{3}^{∗} s_{3} = 4  s_{4} = 3
n = 3 K′_{3} s_{4} = 5  s_{6} = 2
n = 4 𝔸_{4}^{∗} s_{4} = 5  s_{6} = 10
n = 4 K′_{4} s_{4} = 9  s_{6} = 6
n = 5 𝔸_{5}^{∗} s_{5} = 6 s_{8} = 15 s_{9} = 10
n = 6 K′_{6} s_{4} = 27 s_{6} = 36

[K′_{3} is the 3-dimensional eutactic lattice with s = 5; one has K′_{4} ≃ 𝔸_{2} ⨂ 𝔸_{2} and K′_{6} ∼ 𝔼_{6}^{∗}.]

I do not know of any lattice of dimension n ≥ 7 possessing representatives of norm N < 2m.

In the following table, we consider lattices possessing representatives of norm N ≤ 2m for which the equality N = 2m is needed, and for which the function ℓ(x) (defined at the beginning of this section) is constant. The value of ℓ is always an easy consequence of one of the statements 2.3, 2.4, 2.6, or 2.8.

Table 2.11. Some lattices with representatives of norm N ≤ 2m and constant ℓ.

n = 2 ℓ = 2 ℤ^{2} s_{1} = 2  s_{2} = 2
n = 3 ℓ = 3 𝔸_{3} s_{2} = 6  s_{4} = 3

n = 4 ℓ = 4 𝔻_{4} s_{2} = 12  s_{4} = 12
n = 4 ℓ = 3 𝔸_{4} s_{2} = 10  s_{4} = 15
n = 4 ℓ = 2 𝔸_{2}^{⊥2} s_{2} = 6  s_{4} = 18
n = 5 ℓ = 2 𝔻_{5}^{∗} s_{4} = 5 s_{5} = 16 s_{8} = 20
n = 6 ℓ = 5 𝔼_{6} s_{2} = 36  s_{4} = 135
n = 6 ℓ = 3 𝔸_{6}^{(2)} s_{4} = 21  s_{6} = 28  s_{8} = 42
n = 6 ℓ = 1 𝔸_{6}^{∗} s_{6} = 7  s_{10} = 21  s_{12} = 35
n = 8 ℓ = 8 𝔼_{8} s_{2} = 120 s_{4} = 1080
n = 8 ℓ = 3 L_{8}^{4} s_{4} = 54 s_{6} = 120 s_{8} = 243
n = 10 ℓ = 4 K′_{10}^{∗} s_{6} = 120 s_{8} = 135  s_{10} = 648 s_{12} = 480
n = 12 ℓ = 6 K_{12} s_{4} = 378 s_{6} = 2016  s_{8} = 10206
n = 24 ℓ = 24 Λ_{24} s_{4} = 98280 s_{6} = 8386560 s_{8} = 199017000

When Aut(Λ) does not act transitively on S_{2m}, the function ℓ(x) need not be constant. For instance, the orbits named above o_{4} and o′_{4} of norm 4 vectors in 𝔻_{n}, n ≥ 5, contain s_{4,1} = 8 \binom{n}{4} and s_{4,2} = n pairs of vectors, with ℓ = 4 and ℓ = n respectively. The left hand side of the weighted formula of Theorem 2.1 for 𝔻_{n} is then of the form

s_{2} + \frac{1}{4} s_{4,1} + \frac{1}{n} s_{4,2} = n(n − 1) + \frac{n(n − 1)(n − 2)(n − 3)}{12} + 1 ;

For n = 5, it is 20 + 10 + 1 = 2^{5} − 1; from n = 6 onwards, it is strictly smaller than 2^{n} − 1.

Table 2.12. Some other lattices with representatives of norm N ≤ 2m.

n = 5  𝔻_{5} s_{2} = 20  s_{4} = 40
n = 7  K_{7} s_{4} = 46  s_{6} = 32  s_{8} = 218
n = 7  𝔸_{7}^{(2)} s_{4} = 36  s_{6} = 48  s_{8} = 142
n = 8  K_{8} s_{4} = 66  s_{6} = 96  s_{8} = 414
n = 9  Λ_{9} s_{4} = 136 s_{6} = 128  s_{8} = 1529
n = 10  Λ_{10} s_{4} = 168 s_{6} = 384  s_{8} = 2475

Exactly 12 lattices among the 48 perfect lattices of dimension n ≤ 7 possess mod 2 representatives of norm N ≤ 2m, that we list using Conway–Sloane’s notation in [C-S1]; see also the tables in [M], chapitre VI: the 5 lattices with n ≤ 4, 1 out of 3 for n = 5 (P_{5}^{1} ≃ 𝔻_{5}), 3 out of 7 for n = 6 (P_{6}^{1} ≃ 𝔼_{6}, P_{6}^{2} ∼ 𝔼_{6}^{∗}, and P_{6}^{5} ≃ 𝔸_{6}^{(2)}), and 3 out of 33 for n = 7 (P_{7}^{5} ≃ 𝔸_{7}^{(2)}, P_{7}^{20}, and P_{7}^{23}). Similarly, exactly 5 lattices among the 10916 known perfect lattices of dimension n = 8 possess mod 2 representatives of norm N ≤ 2m. In the notation of [Bt-M], they are lh(2) ≃ L_{8}^{4}, lh(179), lh(1172) ≃ 𝔼_{8}, np(160), and bt(5). These “no-name lattices” are not displayed in the previous tables.

Lattices belonging to one of the series Λ_{n}, K_{n}, K′_{n} contained in the Leech lattice and their duals have been tested for n ≤ 12. Only lattices which occur in one of the tables 2.10 to 2.12 do have mod 2 representatives of norm N ≤ 2m.

§ 3. Reduction modulo 3. We must first make more precise the statement in Theorem 1.3 about congruent vectors of norm 3m.

3.1. Proposition. Let x ∈ Λ of norm 3m. Then, the set of vectors of norm 3m which are congruent to x modulo 3Λ reduces to {x} or is of the form {x, y, −x−y}.

Proof. If there exists y ≡ x mod 3Λ with N(y) = N(x) = 3m, then we know by Theorem 1.3 that there exist e, f minimal in Λ such that x = e − f and y = e + 2f (and −x − y = −(2e + f)). If there exists y′ ≠ x, y, −x − y also congruent to x mod 3Λ, there exist minimal vectors e′, f′ in Λ such that x = e′−f′ and y′ = e′+2f′ and that e′ + f′ is also minimal. We have y′ ≡ y mod 3Λ, hence N(y − y′) = 9m, since \frac{1}{3}(y−y′) is minimal by Theorem 1.3. We also have y−y′ = (x+3f)−(x+3f′) = 3(f − f′), hence N(f − f′) = m. But this is not possible, for the 3-dimensional lattice generated by e, f, e′ would then contain the seven pairs of minimal vectors represented by e, f, e + f, e′, f′, e′ + f′, f − f′. □

In analogy with Theorem 2.3, we deduce from the proposition above the following inequality

(3.2)  ∑_{0<k<3m} s_{k} + \frac{1}{3} s_{3m} ≤ \frac{1}{2}(3^{n} − 1) .

and the fact that representatives of Λ/3Λ can be found among vectors of norm N ≤ 3m when equality holds. However, in practice, we must consider vectors of norm greater than 3m (e.g., 4m = 8 for 𝔼_{8}, giving the sum N(x) + N(y) the value 8m = 16).

We shall now use the notation m′ for m^{(2)} and m′′ for m^{(3)} (the norms of the second and third layers of Λ). Proposition 1.1 shows that if N(x) + N(y) > 6m, then y ≡ x mod 3Λ implies N(x) + N(y) ≥ 5m + m′, with equality if and only if N(z) = m and (N(x + z), N(y − z)) = (m, m′) or (m′, m). (Note that the transformation (x, z) ↦ (y, −z) exchanges these two possibilities.)

The next possible value of N(x) + N(y) is either 4m + 2m′, with equality if and only if N(z) = m and N(x + z) = N(y − z) = m′, or 5m + m′′ with equality if and only if N(z) = m and (N(x + z), N(y − z)) = (m, m′′) or (m′′, m). (As above, we can exchange (m, m′′) and (m′′, m).) We remark that

(3.3)  5m + m′′ = 4m + 2m′ ⟺ m′′ − m′ = m′ − m ,

a possibility which often occurs, for instance if Λ is integral and if its first three layers have norm m, m + h, m + 2h (h = 1 or 2 according to whether Λ is odd or even).

If the equality N(x) + N(y) = 5m + m′ holds for y ≡ x mod 3Λ with N(z) = N(x + z) = m, whence N(y − z) = m′, Proposition 1.2 shows that

(3.4)  N(x) = 4m − m′ and N(y) = m + 2m′ .

a congruence which does not occur among vectors of norm N < 2m + m′.

The next possible value of N(x) + N(y) is 4m + 2m′, attained for

(3.5)  N(x) = N(y) = 2m + m′ ,

or 5m + m′′, attained (assuming the inequality N(y) ≥ N(x)) for

(3.6)  N(x) = 4m − m′′ and N(y) = m + 2m′′

(or in both cases when relation 3.3 holds). Now, under conditions 3.5 (resp. 3.4, resp. 3.6), max(N(x), N(y)) has value 2m + m′ (resp. m + 2m′ > 2m + m′, resp. m + 2m′′ > m + 2m′). We have thus proved:

3.7. Proposition. Primitive vectors x, y ∈ Λ of norm N ≤ 2m + m′ which are congruent modulo 3Λ have the same norm, equal to 3m or to 2m + m′. □

To go further, we must now study how many vectors of norm 2m + m′ may represent the same class modulo 3Λ, as we previously did for vectors of norm 3m.

3.8. Proposition. Suppose that m′ < 7m. Let x ∈ S_{2m+m′}, and let y_{0} = x, y_{1}, …, y_{r} be distinct elements of S_{2m+m′} which are congruent to x modulo 3Λ. Then, S(Λ) contains a root system of type A A A_{r} and the lattice L generated by y_{0}, …, y_{r} has minimum 2m + m′ and rank r or r + 1.

Proof. For i = 1, …, r, let z_{i} such that y_{i} = x + 3z_{i}. We know that the z_{i} are minimal vectors of Λ. Because of the congruence y_{j} ≡ y_{k} mod 3Λ, the differences z_{j} −z_{k}, j < k also belong to S(Λ). Hence, the set R = {±z_{i}, ±(z_{j} −z_{k})} (1 ≤ i ≤ r, 1 ≤ j < k ≤ r) is a root system of type A A A_{r} (scaled to norm m). We have of course rk L ≤ r + 1, and also rk L ≥ r since L contains \sqrt{3} R. Let u = a_{0}y_{0} + ⋯ + a_{r}y_{r} be a non-zero element of L and let a = a_{0} + ⋯ + a_{r} ∈ ℤ. We have u ≡ ax mod 3Λ. If a ≡ ±1 mod 3, then u ≡ ±x mod 3Λ has a norm N ≥ 2m + m′ by Proposition 3.7. If a ≡ 0 mod 3, then u = 3v for some v ∈ L ∖ {0} and we have N(u) = 9N(v) ≥ 9m > 2m + m′. □

From the obvious inequality r ≤ n, we obtain:

3.9. Corollary. Under the assumption m′ < 7m, the number of elements of S_{2m+m′} which are congruent to a given x ∈ S_{2m+m′} modulo 3Λ is at most n+1. □

This corollary suffices to obtain representatives of 𝔼_{8} modulo 3. We shall prove this later, and we now look more precisely at the lattice L in Proposition 3.8. Note that the condition m′ < 7m is scarcely a restriction: in practice, m′ is much smaller than 7m.

3.10. Proposition. We keep the hypotheses and notation of Proposition 3.8. Then, L is of rank r if and only if one has

m′ < \frac{5m}{2} and r = \frac{4m + 2m′}{5m − 2m′} .

Under these conditions, one has moreover r ≡ −1 mod 3 and L is similar to 𝔸_{r}^{∗}.

Proof. Without any hypothesis on the rank of L, we have x·z_{i} = −\frac{3m}{2} for 1 ≤ i ≤ r (a consequence of the equalities N(y_{i}) = N(x)), from which we easily deduce the relations y_{i} ·z_{i} = +\frac{3m}{2} and y_{i} ·z_{j} = 0 (1 ≤ i, j ≤ r, j ≠ i) and also y_{i} ·y_{j} = −\frac{5m−m′}{2} for 0 ≤ i < j ≤ r.

Suppose now that rk L = r. There is a relation x = ∑_{j=1}^{r} λ_{j}z_{j}. Taking the r scalar products of the two sides with z_{i} and setting λ = ∑_{j} λ_{j}, we obtain the r equations λ_{i} + λ = −3, whose sum reads (r + 1)λ = −3r, whence λ_{i} = −\frac{3}{r+1} for all i ≥ 1 and finally

(∗)  x = −\frac{3}{r + 1} ∑_{j=1}^{r} z_{j} .

This relation first shows that (r + 1)x ∈ 3Λ; since x does not belong to 3Λ (because N(x) = 2m + m′ < 9m = N(3Λ)), r + 1 must be divisible by 3. Taking the norms of both sides, we obtain the equation

2m + m′ = \frac{9}{(r + 1)^{2}} \frac{r(r + 1)}{2}

which is equivalent to r(5m − 2m′) = (4m + 2m′). Using (∗), we see that x = −(y_{1} + ⋯ + y_{r}), so that (y_{1}, …, y_{r}) is a basis of L whose Gram matrix is easily seen to be proportional to the matrix M whose entries are m_{i,i} = r and m_{i,j} = −1 for i ≠ j, which is itself proportional to a standard Gram matrix for 𝔸_{n}^{∗}.

Conversely, using the value above for r, we prove first that

x + \frac{3}{r + 1}(z_{1} + ⋯ + z_{r}) = \frac{1}{r + 1}(y_{0} + ⋯ + y_{r})

and then that N(y_{0} + ⋯ + y_{r}) = 0 by making use of the known values of the scalar products y_{i} · y_{j}, which implies that L is of rank at most r. □

To study the case when L has rank r + 1, we need the following lemma:

3.11. Lemma. Let α > 0 and β be real numbers and let q be the quadratic form

q(x) = α ∑_{i=1}^{r} x_{i}^{2} + 2β ∑_{1≤i<j≤r} x_{i}x_{j} .

Then, q is positive definite with minimum α if and only if the two inequalities −\frac{α}{r} ≤ β ≤ +\frac{α}{2} hold. When these inequalities are satisfied, the minimal vectors of q (up to the sign) are the r vectors of the canonical basis of ℤ^{r}, except if β = −\frac{α}{r} or if β = \frac{α}{2} where extra minimal vectors exist: the vectors ±(ε_{1} + ⋯ + ε_{r}) in the first case (and q then corresponds to a scaled copy of 𝔸_{r}^{∗}) and the vectors ±(ε_{i} − ε_{j}), 1 ≤ i < j ≤ r in the second case (and q then corresponds to a scaled copy of 𝔸_{r}).

Proof. See [M1], where one makes use of a Voronoi like interpretation involving the symmetric group S_{r}, or use according to the sign of β one of the identities

q(x) = (α − β) ∑ x_{i}^{2} + β (∑ x_{i})^{2} = (α + (r − 1)β) ∑ x_{i}^{2} − β ∑_{i<j}(x_{i} − x_{j})^{2} . □

3.12. Proposition. With the hypotheses and notation of Proposition 3.8, if L has

rank r, then we have either m′ ≥ \frac{5m}{2} or m′ < \frac{5m}{2} and r < \frac{4m + 2m′}{5m − 2m′}.

Proof. Applying lemma 3.11 with α = 2m + m′ and β = m′ − \frac{5m}{2}, we obtain the double inequality

−\frac{2m + m′}{r} ≤ m′ − \frac{5m}{2} ≤ m + \frac{m′}{2} .

The second inequality is always satisfied, and so is the first one if m′ ≥ \frac{5m}{2}. Otherwise, the first inequality is equivalent to r ≤ \frac{4m+2m′}{5m−2m′}, and Proposition 3.11 shows that this inequality must be strict. □

I do not see how one could obtain more restrictive conditions without a detailed investigation of the root systems contained in S(Λ). For particular lattices (e.g., for the Leech lattice), we can find the exact value of r, see below.

Recall that s′_{λ} is the number of primitive pairs of vectors of norm λ; obviously, one has s′_{λ} = s_{λ} unless \frac{λ}{m} is the square of an integer. Corollary 3.9 immediately yields the following weighted formula, that we only state when the number of vectors in S_{2m+m′′} congruent to a given one of the same layer attains its maximal possible value:

3.13. Theorem. One has the inequality

∑_{0<k<3m} s′_{k} + ∑_{3m<k<2m+m′} s′_{k} + \frac{1}{3} s′_{3m} + \frac{1}{n + 1} s′_{2m+m′} ≤ \frac{1}{2} (3^{n} − 1) .

If equality holds, vectors of norm 3m (resp. 2m + m′) appear in systems of 3 (resp. n + 1) vectors with configuration S(𝔸_{2}) ∼ S(𝔸_{2}^{∗}) (resp. S(𝔸_{n}^{∗})), and one obtains a system of representatives of Λ/3Λ∖{0} by taking all vectors of norm N < 2m + m′, N ≠ 3m, and one vector out of 3 (resp. out of n + 1) in each system of 3 vectors of norm 3m (resp. of n + 1 vectors of norm 2m + m′). □

For root lattices, one has m = 2 and m′ = 4, and to apply Theorem 3.13, it suffices to consider s_{2} = s, s_{4}, s_{6} and s′_{8} = s_{8} − s_{2}. Theorem 3.13 applies with equality to 𝔸_{2} (s_{2} = s_{6} = 3, s_{4} = s′_{8} = 0), to 𝔻_{4} (s_{2} = s_{4} = 12, s_{6} = 48, s′_{8} = 0) and to 𝔼_{8}. For 𝔼_{8} one can use the identification of Θ_{𝔼_{8}} with the Eisenstein series E_{4}, which implies the formulae s_{t} = 120 ∑_{q| \frac{t}{2}} q^{3} for all even t > 0, whence s_{2} = 120, s_{4} = 120 (1^{3} + 2^{3}) = 1080, s_{6} = 120 (1^{3} + 3^{3}) = 3360 and s_{8} = 120 (1^{3} + 2^{3} + 4^{3}) = 8760, thus s′_{8} = s_{8} − s_{2} = 8640, and it is easy to check the equalities

120 + 1080 + \frac{1}{3}3360 + \frac{1}{9}8640 = 120 + 1080 + 1120 + 960 = 3280 = \frac{1}{2}(3^{8} − 1) .

We can be more precise: in the three examples above, there is zero or one orbit of primitive vectors of norm N ≤ 8. Only the case of 𝔼_{8} deserves a proof, which can be done along the following line: we first consider the Weyl group W (𝔻_{8}), which stabilizes 𝔼_{8} and is easy to handle; one finds that the number of pairs of vectors in orbits of primitive vectors are

Norm 2 :  56 + 64 = 120;
Norm 4 :  8 + 560 + 512 = 1080;
Norm 6 :  672 + 896 + 1792 = 3360;
Norm 8 :  4480 + 64 + 3584 + 512 = 8640;

one moreover proves that the orbit of an element not in 2𝔼_{8} under Aut(𝔼_{8}) = W (𝔼_{8}) cuts both 𝔻_{8} and 𝔼_{8} ∖ 𝔻_{8}; consideration of reflections defined by minimal vectors e ∈ 𝔼_{8} ∖ 𝔻_{8} quickly shows the required properties of transitivity.

A complete discussion of congruences modulo 3Λ between vectors of norm N > 2m + m′ involves the description of many possibilities. We shall nevertheless look closely at one of them, which on the one hand will be useful in the sequel, and on the other hand involves root systems of type E E E_{8}.

We shall indeed consider congruences involving vectors x, y ≠ x and z such that N(x) = N(y) = 2m + m′′, y = x + 3z and N(z) = m. We thus have N(x + z) = N(y − z) = m′′. We first state an identity, which properly belongs to the general theory of quadratic forms, and that we are going to use several times:

3.14. Lemma. Let x, z_{1}, …, z_{k} (k ≥ 1) be r + 1 vectors of E. Then, the following identity holds:

N(x+∑_{i=1}^{k} z_{i}) = −(k−1)N(x)+∑_{i=1}^{k} N(x+z_{i})+(k−1) ∑_{i=1}^{k} N(z_{i})− ∑_{1≤i<j≤k} N(z_{i}−z_{j}) .

Proof. Just develop both sides. □

3.15. Theorem. Consider a system of r + 1 vectors y_{0} = x, y_{1}, …, y_{r} of norm 2m + m′′ such that N(\frac{y_{j}−y_{i}}{3} ) = m for all i, j with 0 ≤ i < j ≤ r. Set y_{i} = x + 3z_{i} for i = 1, …, r. Then, one has r ≤ 8, and equality holds if and only if x + z_{1} + z_{2}, z_{1}, …, z_{8} generate a lattice isometric to \sqrt{\frac{m}{2}} 𝔼_{8}. Moreover, we then have m′′ = 2m, the 9 vectors y_{0}, y_{1}, …, y_{8} add to zero, and the set {±y_{0}, …, ±y_{8}} is a configuration of type 𝔸_{8}^{∗}.

Proof. One has y_{j} − y_{i} = 3(z_{j} − z_{i}). Thus, the set {±z_{i}, ±(z_{i} − z_{j})} is a system of type A A A_{r} (scaled to the norm m), whose corresponding Coxeter-Dynkin diagram may be obtained from the vectors −z_{1}, z_{2} − z_{1}, …, z_{r−1} − z_{r}.

By lemma 3.14, the vector v = x + z_{1} + z_{2} is of norm 4. Calculating the norm of y_{i}−x, we obtain successively equalities x·y_{i} = −\frac{5m}{2} +m′′ and x·z_{i} = −\frac{3m}{2}, and then v · (−z_{1}) = 0, v · (z_{i} − z_{i+1}) = 0 if i = 1 or if i ≥ 3 and v · (z_{2} − z_{3}) = −\frac{m}{2} (because z_{i} · z_{i} = \frac{m}{2} for i ≠ j). Thus, extending with v the previous diagram, we obtain a diagram of type E E E_{r+1}. This is impossible if r + 1 > 9, for the corresponding quadratic form is then of signature (r, 1), and may occur for r + 1 = 9 only if v, z_{1}, …, z_{8} are linearly dependent, for the quadratic form attached to E_{9} is positive semi-definite of rank 8. When this is the case, the lattice generated by v, z_{1}, …, z_{8} is also generated by v, z_{1}, …, z_{7}, whose Coxeter-Dynkin diagram is of type E E E_{8}.

Consider now a linear relation λ_{1}z_{1} +⋯+λ_{r}z_{r} = λx. Taking the scalar products with z_{1}, …, z_{r} yields the linear system

2λ_{i} + ∑_{j≠i} λ_{j} = −3λ

whose unique solution is λ_{1} = ⋯ = λ_{r} = −\frac{3}{r + 1} λ. We thus must have x =

−\frac{3}{r + 1} (z_{1} + ⋯ + z_{r}). Taking the norm of both sides, we first obtain the relation

2m + m′′ = \frac{9r}{2(r + 1)} m ,

whence m′′ = 2m if r = 8, and then

y_{0} + y_{1} + ⋯ + y_{r} = (r + 1)x + 3(z_{1} + ⋯ + z_{r}) = 0 .

Finally, we saw above that y_{0} · y_{i} = x · y_{i} = −\frac{5m}{2} + m′′, which implies the further equalities y_{i} · y_{j} = (x + 3z_{i}) · (x + 3z_{j}) = −\frac{5m}{2} + m′′. The Gram matrix M of the system (y_{1}, …, y_{r}) has entries 2m + m′′ on the diagonal and −\frac{5m−2m′′}{2} outside. When m′′ = 2m′, M is proportional to the matrix with entries 8 on the diagonal and −1 outside, which is a standard Gram matrix for A_{8}^{∗}. □

[Here is an alternative argument to the use of Coxeter-Dynkin diagrams. By lemma 3.14, the vectors x + z_{i} + z_{j} and x + z_{i} + z_{j} + z_{k} have norm m. Together with the z_{i} and z_{i} − z_{j}, we obtain s_{r} = \binom{r}{3} + 2\binom{r}{2} + r = \frac{r(r+1)(r+2)}{6} vectors of norm m in the lattice generated by x, z_{1}, …, z_{r}. But it is easily checked that s_{r} is strictly larger that s(L) for any root lattice L of rank r if r > 8. We must thus have r ≤ 8, and L ∼ 𝔼_{8} when r = 8 since s_{8} = 120.]

§ 4. Orbits and congruences in the Leech lattice. We find in [ATLAS] a description of the orbits in the Leech lattice Λ = Λ_{24} of all vectors of norm N ≤ 32. (In the notation of [ATLAS], \frac{N}{2} is the type.) We shall make use of it up to N = 18. Each orbit is written either as a ℤ-linear combination au_{t} + a′v_{t′} where the indices t, t′ are the types of u_{t}, v_{t′} and u_{t} +v_{t′} is a vector w_{t′′} of type t′′, or on the standard orthogonal frame made of vectors of norm 8. The first (resp. second) case occurs for vectors which are congruent modulo 2 to a vector of norm 0, 4 or 6 (resp. to a vector of norm 8). In this last case, we shall provide a description in terms of short vectors. For instance, vectors of norm 8, since they constitute a single orbit, are the sums e + f where e and f are orthogonal minimal vectors.

As we know, an exact system of representatives of non-zero classes modulo 2 is provided by one vector of norm 4 or 6 out of each pair ±x and one vector of norm 8 out of systems of 48 vectors lying on 24 pairwise orthogonal lines. Proposition 1.1 shows that vectors which are congruent modulo 2Λ have norms which are congruent modulo 4. Hence, a vector of Λ ∖ 2Λ is congruent to a vector of norm 6 (resp. of norm 4 or 8) if its norm is congruent to 2 mod 4 (resp. to 0 mod 4).

We shall denote the orbits of vectors of norm m by a_{m}, b_{m}, etc., choosing the letter a, b, … in the order of the ATLAS. Thus, the first non-zero orbits are a_{4}, a_{6}, a_{8}, a_{10}, a_{12}, b_{12}, a_{14}, a_{16}, b_{16}, c_{16}, a_{18}, b_{18}, a_{20}, b_{20}, … (The orbit a_{16} is the imprimitive orbit 2a_{4}; for m ≥ 16, there are at least two orbits of vectors of norm m.)

We are going to prove the following theorem:

4.1. Theorem. Representatives of Λ/3Λ may be found among vectors of norms up to 18, according to the weighted equality

|a_{4}| + |a_{6}| + |a_{8}| + |a_{10}| + |a_{12}| + \frac{|b_{12}|}{3} + \frac{|a_{14}|}{2} + \frac{|b_{16}|}{9} + \frac{|b_{18}|}{36} = 3^{24} − 1 .

The cardinality of any orbit in Λ is actually divisible by 65520 ([ATLAS], p. 181).

One has \frac{3^{24} − 1}{65520} = \frac{38795266}{9}. Dividing out by 65520 both sides of the formula in Theorem 4.1, we obtain the following explicit weighted formula:

3 + 256 + 6075 + 70656 + 518400 + \frac{6900}{3} + \frac{2861568}{2} + \frac{12295800}{9} + \frac{32972800}{36} =

\frac{38795266}{9} ; (4.2)

the denominators 3, 9 and 36 in the left hand side correspond to configurations A A A_{2} ∼ A A A_{2}^{∗}, A A A_{8}^{∗} and A A A_{2}^{⊥12} ∼ A A A_{2}^{∗}^{⊥12} respectively, the second one being related to an E E E_{8} configuration contained in S(Λ).

To prove Theorem 4.1, we shall examine which orbits are to be used to find representatives of Λ/3Λ of minimal length, prove upper bounds for their weights, and verify that the left hand side of 4.2, which is a priori known not to be greater than the right hand side, is indeed equal to the right hand side.

No problem arises with vectors of norm 4, 6, 8, 10 which all represent distinct classes by Proposition 3.7. The first difficulty occurs for norm 12, where (Proposition 3.1) a vector may be congruent to 1 or 3 vectors having the same norm.

Now, by Theorem 1.3, a system (x, y, z) of vectors of norm 12 which are congruent modulo 3Λ is of the form (e − f, e + 2f, −2e − f) where e, f, e + f are minimal. Modulo 2Λ, these vectors are congruent to a vector of norm 4 (respectively, e + f, e, f). They thus belong to the orbit b_{12}. Conversely, given x = u_{2} + 2v_{2} ∈ b_{12}, y = u_{2} − v_{2} and z = −2u_{2} − v_{2} belong to b_{12} and are congruent to x modulo 3Λ.

Hence, the orbits a_{12} and b_{12} must be considered with the respective weights 1 and 3.

Let e, f, g be minimal vectors with e·f = e·g = −1 and f ·g = 2, e.g. e_{2}, −e_{1}, e_{9} in the notation of 5.1 below. Set x = e + f + g, y = e − f + g and z = e + f − 2g. We have N(x) = 12, x ≡ y mod 2Λ, and N(y) = 8. Hence, x belongs to a_{12}. Moreover, we have x ≡ z mod 3Λ and N(z) = 18. Writing z = u_{3} + 2v_{2} with u_{3} = e + f and v_{2} = −g, we see that z belongs to a_{18}. Otherwise stated, with the notation of section 1, we have a_{18} ∼_{3} a_{12}. Hence, we need not consider a_{18}. (This

shows that |a_{12}| divides |a_{18}|; indeed, \frac{|a_{18}|}{|a_{12}|} = 24.)

Similarly, u_{3} + 2v_{2} ∈ a_{10} is congruent to u_{3} − v_{2} of norm 16. Since \frac{|c_{16}|}{|a_{10}|} = 2

whereas \frac{|b_{16}|}{|a_{10}|} = \frac{22275}{128} is not integral, we have c_{16} ∼_{3} a_{10} (and the two vectors of

c_{16} which are congruent to u_{3} + 2v_{2} modulo 3Λ are u_{3} − v_{2} and −2u_{3} − v_{2}).

Applying Propositions 3.10 and 3.12, we see that the number r of vectors y ∈ S_{2m+m′} = S_{14} which are congruent modulo 3Λ to a given x ∈ S_{14} cannot exceed

⌊\frac{2 (2m + m′)}{5m − 2m′}⌋ = 3. Any element of S_{14} may be written in the form x = u_{3} + 2v_{2}.

Now, this representation of x is unique:

u_{3} + 2v_{2} = u′_{3} + 2v′_{2} ⟹ u′_{3} ≡ u_{3} mod 2Λ ⟺ u′_{3} = ±u_{3} ;

then u′_{3} = u_{3} ⇒ (u′_{3}, v′_{2}) = (u_{3}, v_{2}) and u′_{3} = −u_{3} ⇒ v′_{2} = u_{3} + v_{2} ⇒ N(v′_{2}) = 6. We have x = u_{3} + 2v_{2} ≡ y = u_{3} − v_{2} = (u_{3} + v_{2}) + (−2v_{2}) mod 3Λ. The map x ↦ y defined by (u_{3}, v_{2}) ↦ (u_{3} + v_{2}, −v_{2}) is an involution without fixed points of S_{14} which preserves congruences modulo 3Λ. Hence, r is even. Since r is at most 3, we have r = 2. Consequently, the orbit a_{14} must be considered with the weight 2.

4.3. Lemma. The only vectors of norm N ≤ 18 which are congruent modulo 3Λ to a shorter vector are those of the orbits a_{16}, c_{16}, a_{18}.

Proof. We know by Proposition 3.7 that such a congruence may occur only for vectors of norm N > 2m + m′ = 14, and we have previously proved equivalences a_{16} ∼_{3} 0, c_{16} ∼_{3} a_{14} and a_{18} ∼_{3} a_{12}. We shall now prove that given y of norm N = 16 or N = 18, a congruence y ≡ x mod 3Λ with N(x) < N(y) cannot hold unless y belongs to a_{16}, c_{16}, a_{18}.

By Proposition 1.1, we have N(x) ≡ N(y) mod 6. Define δ by N(y) − N(x) = 6δ. We have N(z) ≥ 4, hence δ = 1 or δ = 2. By Proposition 1.1, for primitive y, we have N − 4δ = 2N(x) + N(x + y) ≥ 12, hence δ ≤ \frac{18 − 12}{4}, i.e. δ = 1, and we are left with the two possibilities:

(1) N(y) = 16, N(x) = 10, N(z) = N(x + z) = 4, N(y − z) = 6 ;

(2) N(y) = 18, N(x) = 12, N(z) = 4, N(x + z) = 6, N(y − z) = 8.

Now, if N(y) = 16 (resp. if N(y) = 18), y = (x + z) + 2z is of the form u_{2} + 2v_{2} (resp. u_{3} + 2v_{2}) with u_{2} = x + z (resp. u_{3} = x + z) and v_{2} = z, which proves that y ∈ c_{16} (resp. that y ∈ a_{18}). □

We are now faced with the problem of calculating the number of vectors in b_{16} and in b_{18} which are congruent modulo 3Λ to a vector of the same orbit. Evaluating the weighted sum of Theorem 4.1 on vectors of norm up to 14, we see that the complement to 3^{24} − 1 is the sum \frac{|b_{16}|}{9} + \frac{|b_{18}|}{36}. It thus suffices now to prove the bounds wt(b_{16}) ≤ 9 and wt(b_{18}) ≤ 36.

For a pair (x, y) with N(y) = N(x) = N ∈ {16, 18}, we have by Proposition 1.1 N(x + z) = N(y − z) and 2N(z) + N(x + z) = N, which leaves a priori the four possibilities

(1) N=16, N(z) = 6, N(x + z) = 4 ;

(2) N=16, N(z) = 4, N(x + z) = 8 ;

(3) N=18, N(z) = 6, N(x + z) = 6 ;

(4) N=18, N(z) = 4, N(x + z) = 10 ; the first one must be rejected, since we have y ≡ x + z mod 2Λ and the vectors of b_{16} are not congruent modulo 2Λ to a vector of norm 4.

Because of the congruence modulo 2 above, all the hypotheses of Theorem 3.15 are fulfiled. This proves the first upper bound wt(b_{16}) ≤ 9, from which the structure of the sets of vectors which are congruent modulo 3Λ will follow once the equality wt(b_{16}) = 9 is proved.

The proofs of Theorem 4.1 and formula 4.2 now reduce to the inequality wt(b_{18}) ≤ 36. We thus finally consider a vector x ∈ b_{18} and look for systems of vectors y_{1}, …, y_{r} ≡ x mod 3Λ, writing as above y_{i} = x + 3z_{i} and y_{0} = x; we must prove that r + 1 is bounded above by 36.

We consider now more generally a lattice of dimension n whose first three nonzero norms are m = 4, m′ = 6 and then some number m′′ > 7, and a vector x of norm 18 in Λ such that any y ≡ x mod 3Λ is of norm N ≥ 18, and we look for systems of vectors y_{1}, …, y_{r} ≡ x mod 3Λ of norm 18, writing as previously y_{i} = x + 3z_{i} and y_{0} = x.

4.4. Theorem. Under the hypotheses above, the set T (x) of vectors of norm 18 which lie in the class of x in Λ/3Λ contains at most ⌊\frac{3n}{2}⌋ pairs ±x, and if equality holds, ±T (x) contains a root system of type \frac{n}{2} A A A_{2} when n is even, and \frac{n−1}{2} A A A_{2} +A A A_{1} when n is odd. Moreover, S_{6}(Λ) then contains a root system of the same type, and the set ±T (x) is the second layer of the lattice they generate.

Proof. The result is obvious if n ≤ 2. We shall prove the general statement by induction.

By Proposition 1.1, we have N(x + z_{i}) = N(y − z_{i}) and 2N(z_{i}) + N(x + z_{i}) = N(x) = 18 for all i. Given an index i, we are left with the following two possibilities:

(1) N(z_{i}) = 4, N(x + z_{i}) = 10, or

(2) N(z_{i}) = N(x + z_{i}) = 6, for N(z_{i}) ≥ m′′ implies N(x + z_{i}) ≤ 18 − 2m′′ ≤ 2 < m.

The transposition x = y_{0} ↔ y_{i} transforms z_{i} into −z_{i} and z_{j} into z_{j} − z_{i} for j ≠ i. This proves that all vectors of the set S = {±z_{i}, ±(z_{j} − z_{k})} are of norm 4 or 6 and that S is invariant under the permutations of y_{0}, y_{1}, …, y_{r}.

If all vectors of S are of norm 4, S is a root system of type A A A_{r}, hence of rank r. There are thus at most r + 1 ≤ n + 1 elements in the class of x modulo 3Λ, whence the result in this case, since n + 1 ≤ \frac{3n}{2} for n ≥ 2.

We now suppose that S contains at least one vector of norm 6. Under a convenient permutation of y_{0}, …, y_{r}, this vector can be transformed into z_{1}. We have y_{1} = x + 3z_{1} and N(y_{1}) = N(x), hence x · z_{1} = −\frac{9}{6} N(z_{1}) = −9, whence x · y_{1} = x · x + 3x · z_{1} = −9. This shows that x, y_{1} and y′ = −x − y_{1} are three minimal vectors with sum 0 in a hexagonal lattice of norm 18. But we have

y′ = −2x − 3z_{1} ≡ x mod 3Λ ,

which implies that y′ is some y_{i}, say y′ = y_{2}. We thus have −2x − 3z_{1} = x + 3z_{2}, i.e. x = −z_{1} − z_{2}, whence z_{1} · z_{2} = 3, which shows that ±z_{1}, ±z_{2}, ±(z_{1} − z_{2}) are the minimal vectors of a hexagonal lattice contained in S_{6}(Λ) whose second layer is {±y_{0}, ±y_{1}, ±y_{2}}.

We now apply lemma 3.15 to a system (x, z_{i}, z_{j}) first with N(z_{i}) = N(z_{j}) = 6, and then with N(z_{i}) = 6, N(z_{j}) = 4. In the first case, we obtain N(x + z_{i} + z_{j}) = 6 − N(z_{i} − z_{j}) ≤ 2, hence N(x + z_{i} + z_{j}) = 0, i.e. x = −z_{i} − z_{j}. This shows that there are at most two vectors z_{ℓ} of norm 6, for if N(z_{k}) = 6, we also have x = −z_{i} − z_{k}, i.e. z_{j} = z_{k}. Next, if N(z_{i}) = 6 and N(z_{4}) = 4, thenN(x + z_{i} + z_{j}) = 8 − N(z_{i} − z_{j}). We have 4 ≤ N(z_{i} − z_{j}) ≤ 6, hence 2 ≤ N(x + z_{i} + z_{j}) ≤ 4, and finally N(x + z_{i} + z_{j}) = N(z_{i} − z_{j}) = 4. We deduce successively from the last equality the following equalities z_{i}·z_{j} = 3, x·z_{j} = −6 (because N(x+3z_{j}) = N(x)), x · y_{j} = x · x + 3x · z_{j} = 0 and y_{i} · y_{j} = x · x + 3x · z_{i} + 3x · z_{j} + 9z_{i} · z_{j} = 0.

The fact that the last two scalar products are zero shows that the hexagonal lattice generated by y_{0} = x, y_{1}, y_{2} = x − y_{1} is orthogonal to y_{3}, …, y_{r}. By the induction hypothesis, the number of elements in the class of x in Λ/3Λ is at most 3 + ⌊\frac{3(n−2)}{2}⌋ = ⌊\frac{3n}{2}⌋. Moreover, when equality holds, we can factor out in the set {±y_{0}, …, ±y_{r}} a direct sum of root systems A A A_{2} (scaled to norm 18) until we reach a system {z_{i}, z_{j} − z_{k}} (1 ≤ i ≤ t) without any vector of norm 6, for which the bound ⌊\frac{3n}{2}⌋ is not attained unless t ≤ 1. □

§ 5. Applications. The set of sublattices L of a given lattice Λ such that Λ/L is cyclic of order d is in one-to-one correspondence with the set of elements of order d in Λ^{∗}/dΛ^{∗} modulo the operation of (ℤ/dℤ)^{∗}, via the map

e ∈ Λ^{∗} ↦ L = {x ∈ Λ | x · e ≡ 0 mod d} .

For reasons of complexity, it is important to represent the classes of Λ^{∗} mod dΛ^{∗} by vectors which are as short as possible. (For the same reason, it is better to use Λ^{∗} rather than Λ, even if an explicit isomorphism Λ/dΛ ≃ Λ^{∗}/dΛ^{∗} is known.)

If we want to consider L only up to isometry, it is important to know the orbits of Aut(Λ) acting on Λ/dΛ, for it then suffices to consider one vector per orbit and to test the corresponding lattices for isometry.

For 𝔼_{8} (which is unimodular), there is exactly one primitive orbit for each norm 2, 4, 6, 8. Using for d = 2 and d = 3 the description of Λ/dΛ that we have found above, we see that 𝔼_{8} contains exactly 2 (resp. 4) isometry classes of lattices of index d = 2 (resp. d = 3). For d = 2, these lattices must be the root lattices 𝔸_{1} ⊥ 𝔼_{7} and 𝔻_{8}; they are attached respectively to vectors of norm 2 (by definition of 𝔼_{7}) and 4. For d = 3, there again correspond root lattices to vectors of norm 6 and 8, namely 𝔸_{2} ⊥ 𝔼_{6} and 𝔸_{8}; lattices attached to vectors of norm 2 and 4 are not root lattices, as there root systems (E E E_{7} and D D D_{7} respectively) are only of rank 7.

We now turn to the case of the Leech lattice Λ = Λ_{24}. Explicit computations have been done on the PARI system, with the help of programs written by Batut and of its Gram matrix of a basis (e_{1}, …, e_{24}) of Λ calculated from Eva Bayer’s construction of Λ_{24} over the ring ℤ[ζ_{35}]. The entries a_{i,j} of A solely depend on the differences |j − i|; thus, A is well defined by its first row, which is

(5.1) [4, 1, −1, 0, 0, 0, 1, −1, −2, −1, −1, −1, 1, 1, −1, −1, 1, 2, 2, 1, −1, −1, 1, 1] .

Representatives of all orbits up to the norm 18 can be chosen as follows: a_{4} : e_{1} ; a_{6} : e_{1} − e_{2} ; a_{8} : e_{1} + e_{4} ; a_{10} : e_{1} + e_{2} ; a_{12} : e_{1} + e_{3} + e_{8} ; b_{12} : e_{1} − e_{9} ; a_{14} : e_{1} +e_{2} +e_{5} ; a_{16} : 2e_{1} ; b_{16} : e_{1} −2e_{2} ; c_{16} : e_{1} +e_{4} +2e_{9} ; a_{18} : e_{1} −e_{2} −2e_{7} ; b_{18} : e_{1} + e_{2} + 2e_{11} .

The three sublattices of index 2 inside the Leech lattice Λ = Λ_{24} were considered by Bachoc and Batut (see [M], Chapter V, Theorem 7.9). By Theorem 4.1, there are 9 sublattices of index 3. We give below the invariants s = s(L) and s^{∗} = s(L^{∗}) and the value N^{∗} = N(L′) of the twelve lattices of index 2 or 3 in Λ = Λ_{24} (given an integral lattice M, we denote by M′ the lattice \sqrt{a} M^{∗} where a is the annihilator of M^{∗}/M), which we characterize by their index p and the orbit o such that L is isometric to the orthogonal modulo p in Λ_{24} of a vector e ∈ o. One has det(L) = p^{2}, and the Smith invariant of L (i.e., the system of elementary divisors of L^{∗}/L) is (p, p) if p | N(e) and (p^{2}) otherwise.

[Given an integral lattice Λ of norm m, a prime p which does not divide det(Λ) and a vector

e ∈ Λ ∖ pΛ, let Λ_{e,p} = \{x ∈ Λ | e · x ≡ 0 mod pΛ\}; we have Λ_{e,p}^{∗} = ⟨Λ^{∗}, \frac{e}{p}⟩. Since

Λ^{∗}/Λ is of order prime to p, the p-component of Λ_{e,p}^{∗}/Λ_{e,p} is of order p^{2} and is generated by the class of \frac{e}{p} and that of any element of Λ ∖ Λ_{e,p}. Clearly, p \frac{e}{p} = e belongs to Λ_{e,p} if and only if e · e ≡ 0 mod p. This proves that Λ_{e,p}^{∗}/Λ_{e,p} is non-cyclic if and only if N(e) ≡ 0

mod p.]

\underline{Index 2}.

a_{4} s = 51176 s^{∗} = 1 N^{∗} = 2
a_{6} s = 49128 s^{∗} = 1 N^{∗} = 3
a_{8} s = 49128 s^{∗} = 24 N^{∗} = 4

\underline{Index 3}.

a_{4} s = 46575 s^{∗} = 1 N^{∗} = 4
a_{6} s = 38502 s^{∗} = 1 N^{∗} = 2
a_{8} s = 34938 s^{∗} = 1 N^{∗} = 8
a_{10} s = 33453 s^{∗} = 1 N^{∗} = 10
a_{12a} s = 32913 s^{∗} = 1 N^{∗} = 4
a_{12b} s = 33399 s^{∗} = 3 N^{∗} = 4
a_{14} s = 32751 s^{∗} = 2 N^{∗} = 14
a_{16b} s = 32724 s^{∗} = 9 N^{∗} = 16
a_{18b} s = 32670 s^{∗} = 36 N^{∗} = 6

The values of s^{∗} and of N^{∗} found above have the following interpretation: with the previous notation e, p, \frac{e}{p} is a minimal vector of Λ_{e,p}^{∗}, which implies that s^{∗} is the

weight of the orbit of e and that N^{∗} = \frac{N(e)}{p} if p | N(e) and N^{∗} = N(e) otherwise.

5.2. Remark. The systems of 36 vectors of norm 18 with configuration 12A A A_{2} plays for p = 3 the rôle that play the orthogonal frames of norm 8 for p = 2. This analogy could be made closer by considering the Leech lattice as a 12-dimensional module over the rings of Gaussian or Eisenstein integers.

5.3. Remark. By making use of Jacobi theta series to evaluate the repartition of the values of scalar products among vectors of norm N ≤ 18 in the Leech lattice, C. Bachoc ([Ba]) was able to prove directly that one needs to consider exactly norms up to 18 to obtain the shortest representatives of the Leech lattice modulo 3. Putting the orbit structure in her machinery yields quickly 4.2 and 4.3. One cannot deduce directly from her method the structure of the sets of congruent vectors in each orbit (i.e., the occurrence of configurations A A A_{2},E E E_{8},A A A_{8}^{∗}, 12A A A_{2}). However, these results might well follow from a more detailed study of the sets of scalar products.

APPENDIX : ON LATTICES OF MINIMUM 3

A.1. Theorem. Let Λ be a well rounded lattice of norm 3. Then, the classes of Λ/2Λ cannot be represented by vectors of norm N ≤ 2 N(Λ) = 6, except if Λ is one of the five lattices defined up to isometry by one of the following Gram matrices:

M_{1} = (3) , M_{2} = ( \begin{matrix}3 & 1 \\ 1 & 3 \end{matrix} ) , M′_{2} = ( \begin{matrix}3 & 0 \\ 0 & 3 \end{matrix} ) ,

M_{3} = ( \begin{matrix}3 & 1 & 1 \\ 1 & 3 & −1 \\ 1 & −1 & 3 \end{matrix} ) , M′_{3} = ( \begin{matrix}3 & 1 & 1 \\ 1 & 3 & 0 \\ 1 & 0 & 3 \end{matrix} ) , or M_{4} = ( \begin{matrix}3 & 0 & 1 & 1 \\ 0 & 3 & 1 & 1 \\ 1 & 1 & 3 & 0 \\ 1 & 1 & 0 & 3 \end{matrix} ) .

The lattice M_{3} is similar to 𝔸_{3}^{∗}. The inclusions between the lattices above are M_{1} ⊂ M_{2} ⊂ M_{3} and M_{1} ⊂ M′_{2} ⊂ M′_{3} ⊂ M_{4} .

The proof is not really difficult, but needs somewhat tedious verifications of various details. For this reason, I do not give it, and refer the reader to my home page http://math.u-bordeaux.fr/ martinet.

References

[ATLAS] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, R. A. Wilson, ATLAS of Finite Groups, Oxford Univ. Press, Oxford, 1985.

[Ba] C. Bachoc, Private communication, 1999. [Bt-M] C. Batut, J. Martinet, Tables of perfect lattices, http://math.u-bordeaux.fr/ martinet. [C-S] J. H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag,

Grundlehren n^{∘}290, Heidelberg, 1988, (further editions: 1993, 1999).

[C-S1] 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, Les réseaux parfaits des espaces euclidiens, Masson, Paris, 1996, (new editor: Dunod, Paris).

[M1] J. Martinet, Une famille de réseaux dual-extrêmes, J. Théor. Nombres Bordeaux 9 (1997), 169–181.

J. Martinet A2X, Institut de Mathématiques Université Bordeaux 1 351, cours de la Libération F–33405 TALENCE cedex E-mail : martinet@math.u-bordeaux.fr