Lattices

A.E. Brouwer

2002-01-17

Abstract

Some lattice stuff for the current EIDMA course.

1 Intro

For many applications one needs dense arrangements of balls in Euclidean space. Parameters to be optimized are e.g. packing density, covering density, kissing number (the number of balls that touch a given ball). Just as in coding theory, where the best codes sometimes are nonlinear but most of the theory concerns the linear case, here the best arrangements sometimes are non-lattice, but most of the theory concerns lattice arrangements.

2 Lattices

Lattice

A lattice Λ is a discrete additive subgroup of R^{n}. Equivalently, it is a finitely generated free Z-module with positive definite symmetric bilinear form.

Basis

Assume that our lattice Λ has dimension n, i.e., spans R^{n}. Let {a_{1}, ..., a_{n}} be a Z-basis of Λ. Let A be the matrix with the vectors a_{i} as rows. If we choose a different Z-basis {b_{1}, ..., b_{n}}, so that b_{i} = ∑ s_{ij}a_{j}, and B is the matrix with the vectors b_{i} as rows, then B = SA, with S = (s_{ij}). Since S is integral and invertible, it has determinant ±1. It follows that | det A| is uniquely determined by Λ, independent of the choice of basis.

Volume

R^{n}/Λ is an n-dimensional torus, compact with finite volume. Its volume is the volume of the fundamental domain, which equals | det A|.

If Λ′ is a sublattice of Λ, then vol(R^{n}/Λ′) = vol(R^{n}/Λ).|Λ/Λ′|.

Gram matrix

Let G be the matrix (a_{i}, a_{j}) of inner products of basis vectors for a given basis. Then G = AA^{⊤}, so vol(R^{n}/Λ) = \sqrt{det G}.

Dual lattice

The dual Λ^{∗} of a lattice Λ is the lattice of vectors having integral inner products with all vectors in Λ: Λ^{∗} = {x ∈ R^{n}|(x, r) ∈ Z for all r ∈ Λ}.

It has a basis {a_{1}^{∗}, ..., a_{n}^{∗}} defined by (a_{i}^{∗}, a_{j}) = δ_{ij}.

Now A^{∗}A^{⊤} = I, so A^{∗} = (A^{−1})^{⊤} and Λ^{∗} has Gram matrix G^{∗} = G^{−1}. It follows that vol(R^{n}/Λ^{∗}) = 1/vol(R^{n}/Λ). We have Λ^{∗∗} = Λ.

Integral lattice

The lattice Λ is called integral when the inner products of lattice vectors are all integral.

For an integral lattice Λ one has Λ ⊆ Λ^{∗}.

The lattice Λ is called even when (x, x) is an even integer for each x ∈ Λ. An even lattice is integral. An integral lattice that is not even is called odd.

Discriminant

The determinant, or discriminant, disc Λ of a lattice Λ is defined by disc Λ = det G. When Λ is integral, we have disc Λ = |Λ^{∗}/Λ|.

A lattice is called self-dual or unimodular when Λ = Λ^{∗}, i.e., when it is integral with discriminant 1. An even unimodular lattice is called Type II, the remaining unimodular lattices are called Type I.

If there is an even unimodular lattice in R^{n}, then n is divisible by 8. (This follows by studying the associated theta series and modular forms. See also below under Leech lattice.)

3 Examples

3.1 Z^{n}

[figure]

Unimodular, type I.

3.2 A_{2}

[figure: 0; r; s; 2r + s; p; q]

Basis \{r, s\}. Gram matrix G = ( \begin{matrix}2 & −1 \\ −1 & 2 \end{matrix} ), so that det G = 3. A fundamental region for A_{2} is the parallelogram on 0, r, s. A fundamental region for A_{2}^{∗} is the parallelogram on 0, p, q. Note that the area of the former (\sqrt{3}) is thrice that of the latter (1/\sqrt{3}).

The representation of this lattice in R^{2} has nonintegral coordinates. It is easier to work in R^{3}, on the hyperplane ∑ x_{i} = 0, and choose r = e_{1} − e_{2} = (1, −1, 0), s = e_{2} − e_{3} = (0, 1, −1). Then A_{2} consists of the points (x_{1}, x_{2}, x_{3}) with x_{i} ∈ Z and ∑ x_{i} = 0. The dual lattice A_{2}^{∗} consists of the points (x_{1}, x_{2}, x_{3}) with x_{1} ≡ x_{2} ≡ x_{3} (mod 1) and ∑ x_{i} = 0 (so that 3x_{1} ∈ Z). It contains for example p = \frac{1}{3}(2r + s) = (\frac{2}{3}, −\frac{1}{3}, −\frac{1}{3}).

4 Constructions

Let ρ : Z^{n} → 2^{n} be coordinatewise reduction mod 2. Given a binary linear code C, the lattice ρ^{−1}(C) is integral, since it is contained in Z^{n}, but never unimodular, unless it is all of Z^{n}, a boring situation.

It turns out to be more useful to look at \frac{1}{\sqrt{2}}ρ^{−1}(C). This is an integral lattice when inner products of code words are even, that is, when C is self-orthogonal. If dim C = k then vol(R^{n}/ρ^{−1}(C)) = 2^{n−k} and hence vol(R^{n}/\frac{1}{\sqrt{2}}ρ^{−1}(C)) = 2^{\frac{1}{2} n−k}. In particular, \frac{1}{\sqrt{2}}ρ^{−1}(C) will be unimodular when C is self-dual, and even when C is ”doubly even”.

Example

Let C be the [8,4,4] extended Hamming code. Then \frac{1}{\sqrt{2}}ρ^{−1}(C) is a unimodular 8-dimensional lattice known as E_{8}.

The code C has weight enumerator 1+14X^{4} +X^{8} (that is, has one word of weight 0, 14 words of weight 4, and one word of weight 8). It follows that the roots (vectors r with (r, r) = 2) in this incarnation of E_{8} are the 16 vectors ±\frac{1}{\sqrt{2}}(2, 0, 0, 0, 0, 0, 0, 0) (with 2 in any position), and the 16.14 = 224 vectors \frac{1}{\sqrt{2}}(±1, ±1, ±1, ±1, 0, 0, 0, 0) with ±1 in the nonzero positions of a weight 4 vector. Thus, there are 240 roots.

5 Root lattices

A root lattice is an integral lattice generated by roots (vectors r with (r, r) = 2). The set of roots in a root lattice is a (reduced) root system Φ, i.e., satisfies

(i) If r ∈ Φ and λr ∈ Φ, then λ = ±1.

(ii) Φ is closed under the reflection w_{r} that sends s to s − 2\frac{(r,s)}{(r,r)}r for each r ∈ Φ.

(iii) 2\frac{(r,s)}{(r,r)} ∈ Z.

For example, A_{2} and E_{8} are root lattices.

Since Φ generates Λ and Φ is invariant under W = ⟨w_{r}|r ∈ Φ⟩, the same holds for Λ, so root lattices have a large group of automorphisms.

A fundamental system of roots Π in a root lattice Λ is a set of roots generating Λ and such that (r, s) ≤ 0 for distinct r, s ∈ Π. A reduced fundamental system of roots is a fundamental system that is linearly independent. A non-reduced fundamental system is called extended.

For example, in A_{2} the set {r, s} is a reduced fundamental system, and {r, s, −r − s} is an extended fundamental system.

The Dynkin diagram of a fundamental system Π such that (r, s) ≠ −2 for r, s ∈ Π, is the graph with vertex set Π where r and s are joined by an edge when (r, s) = −1. (The case (r, s) = −2 happens only for a nonreduced system with A_{1} component. In that case we do not define the Dynkin diagram.)

Every root lattice has a reduced fundamental system: Fix some vector u, not orthogonal to any root. Put Φ^{+}(u) = {r ∈ Φ|(r, u) > 0} and Π(u) = {r ∈ Φ^{+}(u)|r cannot be written as s + t with s, t ∈ Φ^{+}(u)}. Then Π(u) is a reduced fundamental system of roots, and written on this basis each root has only positive or only negative coefficients.

(Indeed, if r, s ∈ Π(u) and (r, s) = 1, then say r − s ∈ Φ^{+}(u) and r = (r − s) + s, contradiction. This shows that Π(u) is a fundamental system. If ∑ γ_{r}r = 0, then separate the γ_{r} into positive and negative ones to get ∑ α_{r}r = ∑ β_{s}s = x ≠ 0 where all coefficients α_{r}, β_{s} are positive. Now 0 < (x, x) = ∑ α_{r}β_{s}(r, s) ≤ 0, contradiction. This shows that Π(u) is reduced. Each root in Φ^{+}(u) has an expression over Π(u) with only positive coefficients.)

Proposition 5.1 Let Π be a reduced fundamental system.

(i) For all x ∈ R^{n} there is a w ∈ W such that (w(x), r) ≥ 0 for all r ∈ Π.

(ii) Π = Π(u) for some u. (That is, W is transitive on reduced fundamental systems.)

(iii) If Λ is irreducible (not an orthogonal direct sum), then there is a unique r̃ ∈ Φ such that Π ∪ {r̃} is an extended fundamental system.

Proof: (i) Let G be the Gram matrix of Π, and write A = 2I − G. Since G is positive definite, A has largest eigenvalue less than 2. Using Perron-Frobenius, let γ = (γ_{r})_{r∈Π} be a positive eigenvector of A. If (x, s) < 0 for some s ∈ Π, then put x′ = w_{s}(x) = x − (x, s)s. Now

(x′, ∑_{r} γ_{r}r) = (x, ∑_{r} γ_{r}r) − (Gγ)_{s}(x, s) > (x, ∑_{r} γ_{r}r).

But W is finite, so after finitely many steps we reach the desired conclusion.

(ii) Induction on |Π|. Fix x with (x, r) ≥ 0 for all r ∈ Π. Then Π_{0} = Π ∩ x^{⊥} is a fundamental system of a lattice in a lower-dimensional space, so of the form Π_{0} = Π_{0}(u_{0}). Take u = x+ϵu_{0} for small ϵ > 0. Then Π = Π(u).

(iii) If r ∈ Φ^{+}(u) has maximal (r, u), then r̃ = −r is the unique root that can be added. It can be added, since (r̃, s) ≥ 0 means (r, s) < 0, so that r + s is a root, contradicting maximality of r. And it is unique because linear dependencies of an extended system correspond to an eigenvector with eigenvalue 2 of the extended Dynkin diagram, and by Perron-Frobenius up to a constant there is a unique such eigenvector when the diagram is connected, that is, when Λ is irreducible. □

The examples

The irreducible root lattices one finds are A_{n} (n ≥ 0), D_{n} (n ≥ 4), E_{6}, E_{7}, E_{8}. Each is defined by its Dynkin diagram.

(1) A_{n}: The lattice vectors are: x ∈ Z^{n+1} with ∑ x_{i} = 0. There are n(n+1) roots: e_{i}−e_{j} (i ≠ j). The discriminant is n+1, and A_{n}^{∗}/A_{n} ≃ Z_{n+1}, with the quotient generated by \frac{1}{n+1}(e_{1} + ... + e_{n} − ne_{n+1}) ∈ A_{n}^{∗}.

[figure: e_{2} − e_{1}; e_{3} − e_{2}; e_{n+1} − e_{n}; (e_{1} − e_{n+1})]

(2) D_{n}: The lattice vectors are: x ∈ Z^{n} with ∑ x_{i} ≡ 0 (mod 2). There are 2n(n − 1) roots ±e_{i} ± e_{j} (i ≠ j). The discriminant is 4, and D_{n}^{∗}/D_{n} is isomorphic to Z_{4} when n is odd, and to Z_{2} ×Z_{2} when n is even. D_{n}^{∗} contains e_{1} and \frac{1}{2}(e_{1} + ... + e_{n}). Note that D_{3} ≃ A_{3}.

[figure: e_{2} − e_{1}; e_{3} − e_{2}; e_{1} + e_{2}; e_{n−1} − e_{n−2}; (−e_{n−1} − e_{n}); e_{n} − e_{n−1}]

(3) E_{8}: (Recall that we already gave a construction of E_{8} from the Hamming code.) The lattice is the span of D_{8} and c := \frac{1}{2}(e_{1}+...+e_{8}). There are 240 = 112 + 128 roots, of the forms ±e_{i} ± e_{j} (i ≠ j) and \frac{1}{2}(±e_{1} ± ... ± e_{8}) with an even number of minus signs. The discriminant is 1, and E_{8}^{∗} = E_{8}.

[figure: e_{2} − e_{1}; e_{3} − e_{2}; e_{4} − e_{3}; \frac{1}{2} (1, 1, 1, −1, −1, −1, −1, 1); e_{5} − e_{4}; e_{6} − e_{5}; e_{7} − e_{6}; −e_{7} − e_{8}; (c)]

(4) E_{7}: Take E_{7} = E_{8} ∩ c^{⊥}. There are 126 = 56 + 70 roots. The discriminant is 2, and E_{7}^{∗} contains \frac{1}{4}(1, 1, 1, 1, 1, 1, −3, −3).

[figure: (e_{1} − e_{8}); e_{2} − e_{1}; e_{3} − e_{2}; e_{4} − e_{3}; \frac{1}{2} (1, 1, 1, −1, −1, −1, −1, 1); e_{5} − e_{4}; e_{6} − e_{5}; e_{7} − e_{6}]

(5) E_{6}: For the vector d = −e_{7} − e_{8}, take E_{6} = E_{8} ∩ {c, d}^{⊥}. There are 72 = 32 + 40 roots. The discriminant is 3, and E_{6}^{∗} contains the vector \frac{1}{3}(1, 1, 1, 1, −2, −2, 0, 0).

[figure: e_{2} − e_{1}; e_{3} − e_{2}; e_{4} − e_{3}; \frac{1}{2} (1, 1, 1, −1, −1, −1, −1, 1); (e_{7} − e_{8}); e_{5} − e_{4}; e_{6} − e_{5}]

That this is all, is an easy consequence of the Perron-Frobenius theorem: A = 2I −G is the adjacency matrix of a graph, namely the Dynkin diagram, and it is easy to classify the connected graphs with largest eigenvalue less than 2—they are the Dynkin diagrams of reduced fundamental systems of irreducible root systems—and the connected graphs with largest eigenvalue 2—they are the Dynkin diagrams of extended root systems.

6 The Leech lattice

Theorem 6.1 There exists a unique even unimodular lattice without roots in R^{24}. It has 196560 vectors of weight 4.

Construction: a spanning set consists of the vectors \frac{1}{\sqrt{8}}(∓3, ±1^{23}) with ∓3 in any position, and the upper signs in a code word of the extended binary Golay code.

For the vectors of weight 4 one finds the shapes 4^{2} 0^{22}, 3 1^{23}, 2^{8} 0^{16} (omitting the \frac{1}{\sqrt{8}}) with frequencies 2^{2}\binom{24}{2}, 2^{12}.24 and 2^{7}.759, respectively.

Uniqueness is proved using θ-functions and the theory of modular forms. Given a lattice Λ, define

θ_{Λ}(z) = ∑_{x∈Λ} q^{\frac{1}{2} (x,x)}

where q = e^{2πiz} and Im(z) > 0.

One has

θ_{Λ^{∗}}(z) = det(Λ)^{\frac{1}{2}} (\frac{i}{z} )^{\frac{n}{2}} θ_{Λ}(−\frac{1}{z}).

Here the Leech lattice has Λ = Λ^{∗} and det(Λ) = 1, so that θ_{Λ}(z) is a modular form of weight 12.

The space of modular forms of weight 12 has dimension 2, and the two conditions: unique vector of norm 0, no vectors of norm 2, determine θ_{Λ}(z) uniquely. Thus, any even unimodular lattice without roots in R^{24} must have the same weight enumerator as the Leech lattice.

Some more work gives the desired conclusion.

7 The Barnes-Wall lattice

Take the first order Reed-Muller code C of length 16. This is a binary linear [16,5,8] code, with weight enumerator 1 + 30X^{8} + X^{16}.

Define the Barnes-Wall lattice Λ_{16} by: \frac{1}{\sqrt{2}}x ∈ Λ_{16} iff x is an integral vector, with x mod 2 in C and ∑ x_{i} ≡ 0 (mod 4).

This is a lattice of determinant 2^{8} and minimum norm 4. The kissing number equals τ = 4320 (namely, 480 vectors of shape \frac{1}{\sqrt{2}}(±2^{2}, 0^{14}) and 3840 vectors of shape \frac{1}{\sqrt{2}}(±1^{8}, 0^{8}) with the 1’s at the positions of a code word.

(This type of construction is especially useful when d = 8, since two shapes contribute to the kissing number. For larger n chains of binary codes are used to place the 1’s, 2’s, 4’s, etc.)

8 The Coxeter-Todd lattice

Let ω = −\frac{1}{2} + \frac{1}{2} \sqrt{−3} be a cube root of unity, and put θ = ω − ω̄ = \sqrt{−3}.

Let Λ be the 6-dimensional Z[ω]-lattice spanned by the six vectors (4, 0, 0, 0, 0, 0), (2, 2, 0, 0, 0, 0), (2, 0, 2, 0, 0, 0), (2, 0, 0, 2, 0, 0), (2, 0, 0, 0, 2, 0), (θ, 1, 1, 1, 1, 1), provided with the positive definite inner product (u, v) = uv̄^{⊤}. Since θ = 2ω + 1 all inner products are divisible by 4, and we see that \frac{1}{2}Λ is a unimodular lattice Z[ω]-lattice.

This definition looks asymmetric, but in fact the group is large: the automorphism group of the 6-dimensional Z[ω]-lattice is 6.U_{4}(3).2 of order 2^{9}.3^{7}.5.7, inducing the symmetric group Sym(6) on the coordinate positions.

This 6-dimensional Z[ω]-lattice Λ is a 12-dimensional Z-lattice. If the complex lattice has coordinate positions e_{h} (1 ≤ h ≤ 6), then we can take 12 coordinate positions e_{h}, ie_{h} for the real lattice, and given a Z[ω]-basis with vectors u_{j}, we find a Z-basis with vectors u_{j}, (ω − 1)u_{j}. A diagonal 2 now becomes \binom{2}{−3 \sqrt{3}}. Consequently, K_{12} := \frac{1}{\sqrt{2}}Λ is an integral lattice with determinant 3^{6}. (One checks that (a + bi)(c − di) = ac + bd + (bc − ad)i and ((a, b), (c, d)) = ac + bd so that the real inner product is the real part of the complex inner product. Since Re(ω) = −\frac{1}{2}, we need an extra factor 2 to guarantee that the inner product is integral.)

The dual K_{12}^{∗} is spanned by the six vectors \frac{1}{\sqrt{2}}u_{j} and the six vectors \frac{1}{3\sqrt{2}}(ω − 1)u_{j}. (Thus, K_{12}^{∗}/K_{12} can be regarded as a 6-dimensional vector space over GF (3).)

The minimum norm is 4, and the kissing number is 756. (Indeed, there are 32.6.3 = 576 vectors of the form \frac{1}{\sqrt{2}}ω^{j}(±θ, ±1, ..., ±1) with an even number of minus signs, the ±θ in any position, and j = 0, 1, 2, and also 15.4.3 = 180 vectors of the form \frac{1}{\sqrt{2}}ω^{j}(±2, ±2, 0, 0, 0, 0) with the ±2 in any positions.)

There are many equivalent descriptions. A short one: take the vectors u + ωθv, with u ∈ E_{6} and v ∈ E_{6}^{∗}.

9 Records

We quote a table from Conway & Sloane giving the best lattices known in low dimensional spaces.

dimension 1 2 3 4 5 6 7  8  12 16 24

densest packing Z A_{2} A_{3} D_{4} D_{5} E_{6} E_{7} E_{8} K_{12} Λ_{16} Λ_{24}

highest kissing number

Z A_{2} A_{3} D_{4} D_{5} E_{6} E_{7} E_{8} P_{12a} Λ_{16} Λ_{24}
2 6 12 24 40 72 126 240 840 4320 196560

thinnest covering Z A_{2} A_{3}^{∗} A_{4}^{∗} A_{5}^{∗} A_{6}^{∗} A_{7}^{∗} A_{8}^{∗} A_{12}^{∗} A_{16}^{∗} Λ_{24}

best quantizer Z A_{2} A_{3}^{∗} D_{4} D_{5}^{∗} E_{6}^{∗} E_{7}^{∗} E_{8} K_{12} Λ_{16} Λ_{24}

Here K_{12} is the Coxeter-Todd lattice, Λ_{16} is the Barnes-Wall lattice, Λ_{24} is the Leech lattice, and P_{12a} is a certain non-lattice packing.