Math 55a: Intro to SPLAG

[SPLAG = Sphere Packings, Lattices and Groups, the title of Conway and Sloane's celebrated treatise. Most of the following can be found in Chapter 1.]

Let V be a vector space of finite dimension n over R. A lattice in V is the set of integer linear combinations of a basis, or equivalently the subgroup of V generated by the basis vectors. That is, to each basis {v1,v2,...,vn} of V we associate the lattice

L = {a1 v1 + a2 v2 + ... + an vn | each ai in Z.}
For instance, the standard basis yields the lattice Zn in Rn. Once n>1, lots of bases yield the same lattice. For instance, in dimension 2, (a,b) and (c,d) generate Z2 if and only if a,b,c,d are integers with |ad-bc|=1. In general the set of linear transformations of V that permute L is a discrete subgroup of GL(V), which we might call GL(L); when we identify V with Rn and L with Zn, we get the group GLn(Z) consisting of invertible square matrices A of order n such that both A and A-1 have integer entries. (We shall see that this is equivalent to the condition that A have integer entries with determinant 1 or -1.)

The dual lattice is the subset L* of V* consisting of all functionals v* such that v*(v) is an integer for every v in L. This is indeed a lattice, because it is generated by the dual basis of the generating basis for L. It follows that L**=L, and if some lattice L' contains L then its dual is contained in L*. If we choose a basis for V, thus identifying V with Rn, then an arbitrary basis consists of the columns of an arbitrary invertible matrix M of order n; the lattice generated by this basis consists of all vectors of the form Ma where A is a column vector of n integers; and the dual lattice is generated by the vectors that constitute the inverse transpose of M (relative to the dual basis of V*).

This becomes really interesting when V has an inner product. Then it's no longer true that all lattices are equivalent, nor that Aut(L) is infinite. In fact:

Proposition. Every lattice in an inner-product space has a finite automorphism group.

Proof: The automorphism group of a lattice L in an inner-product space V is the intersection of GL(L) with O(V). We regard both of these groups as subsets of the n2-dimensional space of linear operators on V, and exploit the fact that all norms on this space yield the same topology. Using a basis for V consisting of generators of L, we see that GL(L) is a subset of the set of n-by-n integer matrices, which is discrete. Using a basis for V orthonormal with respect to the inner product, we see that O(V) is compact, since it is a closed bounded subset of a finite-dimensional real vector space. A discrete subset of a compact set is finite, so we are done.

Every lattice has at least two automorphisms: the identity 1, and -1. For ``most'' lattices, that's the full automorphism group; but there are lattices with much more interesting automorphism groups. The most striking case of this is Leech's lattice L24 in R24, with Aut(L24)/{1,-1} being Conway's sporadic simple group Co1. A more down-to-earth example is the lattice Zn generated by an orthogonal basis for Rn; its automorphism group is the ``hyperoctahedral group'' or ``signed permutation group'' of order 2nn!. This is known to be the largest possible Aut(L) for a lattice in Rn, except for the seven dimensions n=2,4,6,7,8,9,10 for which a more symmetric lattice exists (e.g., for n=2 the hexagonal lattice has 12 symmetries whereas the square lattice Z2 has only 222!=8.).

To show that Zn has no automorphisms other than the signed permutations, we can use the fact that any automorphism must permute the set of lattice vectors v such that <v,v>=1, which for Zn consists of the unit vectors and their negatives (vertices of an n-dimensional hyperoctahedron). In general, since any lattice L is discrete (and closed balls in Rn are compact), there exists a minimal value Nmin(L) of <v,v> as v ranges over nonzero lattice vectors. The number of lattice vectors v such that <v,v>=Nmin(L) is called the ``kissing number'' of the lattice (which we shall denote here by k(L) since the customary kappa is not available in HTML). The reason for this term is the sphere packing (more properly, a packing of equal balls) associated to L: open balls of radius r centered around lattice points do not overlap if and only if 4r2<=Nmin(L), and if we choose r so that 4r2=Nmin(L), then each ball in the packing is tangent to k(L) others. The configuration of k(L) minimal nonzero vectors may itself be regarded as (the configuration of centers in) a packing of equal balls on the surface of a sphere in Rn. Certain L in various low dimensions (48 is still ``low'' for this purpose) give rise to very dense sphere packings with large kissing numbers; in some cases (notably n=8,24, and conjecturally all n<8 too) there is a lattice whose minimal vectors solve the kissing-number problem in Rn.

In practice it can be quite difficult to find Nmin(L) given a set of generators for a lattice L in a high-dimensional space. Even in low dimensions (up to 8 or so), in which an exact solution of this problem is known, it is nontrivial; in higher dimensions the LLL algorithm (due to Lenstra, Lenstra, and Lovasz -- yes, the first two are brothers) is a useful approximate solution, much more useful in fact than available theorems can explain. The problem of finding short nonzero vectors in lattices has many applications, such as simultaneous rational approximation, recognizing approximate algebraic numbers, etc., as well as some less immediate uses, for instance searching efficiently for near-identities such as

34720737 + 46270117 = 47108687 * 1.00000000000000000000036...
(go here for more information about this connection). In dimension 2, Nmin(L) can be found easily with a variation of the Euclidean algorithm; LLL can be interpreted as a combination of that algorithm with the Gram-Schmidt orthogonalization method.