The Sphere Packing Problem

N. J. A. Sloane

Abstract. A brief report on recent work on the sphere-packing problem.

1991 Mathematics Subject Classification: 52C17

Keywords and Phrases: Sphere packings; lattices; quadratic forms; geometry of numbers

1 Introduction

The sphere packing problem has its roots in geometry and number theory (it is part of Hilbert’s 18th problem), but is also a fundamental question in information theory. The connection is via the sampling theorem. As Shannon observes in his classic 1948 paper [37] (which ushered in the age of digital communication), if f is a signal of bandwidth W hertz, with almost all its energy concentrated in an interval of T secs, then f is accurately represented by a vector of 2W T samples, which may be regarded as the coordinates of a single point in ℝ^{n}, n = 2W T. Nearly equal signals are represented by neighboring points, so to keep the signals distinct, Shannon represents them by n-dimensional ‘billiard balls’, and is therefore led to ask: what is the best way to pack ‘billiard balls’ in n dimensions?

This talk will report on a few selected developments that have taken place since the appearance of Rogers’ 1964 book on the subject, proceeding upwards in dimension from 2 to 128. The reader is referred to [16] (especially the third edition, which has 800 references covering 1988-1998) for further information, definitions and references. See also the lattice data-base [31].

2 Dimension 2

The best packing in dimension 2 is the familiar ‘hexagonal lattice’ packing of circles, each touching six others. The centers are the points of the root lattice A_{2}. The density Δ of this packing is the fraction of the plane occupied by the spheres: π/\sqrt{12} = 0.9069 . . ..

In general we wish to find Δ_{n}, the highest possible density of a packing of equal nonoverlapping spheres in ℝ^{n}, or Δ_{n}^{(L)}, the highest density of any packing in which the centers form a lattice. It is known (Fejes Tóth, 1940) that Δ_{2} = Δ_{2}^{(L)} = π/\sqrt{12}. An n-dimensional lattice Λ of determinant d and minimal nonzero squared length (or norm) μ has packing radius ρ = \sqrt{μ}/2 and density Δ = V_{n}ρ^{n}/\sqrt{det Λ}, where V_{n} = π^{n/2}/(n/2)! is the volume of a unit sphere. The center density of a packing is δ = Δ/V_{n}.

We are also interested in packing points on a sphere, and especially in the ‘kissing number problem’: find τ_{n} (resp. τ_{n}^{(L)}), the maximal number of spheres that can touch an equal sphere in ℝ^{n} (resp. in any lattice in ℝ^{n}). It is trivial that τ_{2} = τ_{2}^{(L)} = 6.

3 Dimension 3

In spite of much recent work ([20], [21]) Δ_{3} is still unknown; nor is Δ_{n} known in any dimension above 2. It is conjectured that Δ_{3} = π/\sqrt{18} = 0.74048 …, as in the facecentered cubic (f.c.c.) lattice A_{3}. Muder [28] has shown that Δ_{3} ≤ 0.773055 . . .. It is worth mentioning, however, that there are packings of congruent ellipsoids with density considerably greater than π/\sqrt{18} [3].

In two dimensions the hexagonal lattice is (a) the densest lattice packing,

(b) the least dense lattice covering, and (c) is geometrically similar to its dual lattice. There is a little-known three-dimensional lattice that is similar to its dual, and, among all lattices with this property, is both the densest packing and the least dense covering. This is the m.c.c. (or mean-centered cuboidal) lattice [11] with Gram matrix

\frac{1}{2} [ \begin{matrix}1 + \sqrt{2} & 1 & 1 \\ 1 & 1 + \sqrt{2} & 1 − \sqrt{2} \\ 1 & 1 − \sqrt{2} & 1 + \sqrt{2} \end{matrix} ] .

In a sense this lattice is the geometric mean of the f.c.c. lattice and its dual the body-centered cubic (b.c.c.) lattice. Consider the lattice generated by the vectors (±u, ±v, 0) and (0, ±u, ±v) for real numbers u and v. If the ratio u/v is respectively 1, 2^{1/2} or 2^{1/4} we obtain the f.c.c., b.c.c. and m.c.c. lattices. The m.c.c. lattice also recently arose in a different context, as the lattice corresponding to the period matrix of the hyperelliptic Riemann surface w^{2} = z^{8} − 1

4 Dimensions 4–8

Table 1 summarizes what is presently known about the sphere packing and kissing number problems in dimensions ≤ 24. Entries enclosed inside a solid line are known to be optimal, those inside a dashed line optimal among lattices.

The large box in the ‘density’ column refers to Blichfeldt’s 1935 result that the root lattices ℤ ≃ A_{1}, A_{2}, A_{3} ≃ D_{3}, D_{4}, D_{5}, E_{6}, E_{7}, E_{8} achieve Δ_{n}^{(L)} for n ≤ 8. It is remarkable that more than 60 years later Δ_{9}^{(L)} is still unknown.

The large box in the right-hand column refers to Watson’s 1963 result that the kissing numbers of the above lattices, together with that of the laminated lattice Λ_{9}, achieve τ_{n}^{(L)} for n ≤ 9. Odlyzko and I [16, Ch. 13] and independently Levenshtein determined τ_{8} and τ_{24}. The packings achieving these two bounds are unique [16, Ch. 14].

K_{12}  (306 from P_{9a}) (500 from P_{10b}) (840 from P_{12a}) BW_{16} ≃ Λ_{16} Leech ≃ Λ_{24} Λ_{9}  4320 16  Λ_{10} (P_{10c}) D_{4} ≃ Λ_{4} D_{5} ≃ Λ_{5} E_{6} ≃ Λ_{6} E_{7} ≃ Λ_{7} E_{8} ≃ Λ_{8} A_{3} ≃ D_{3} ≃ Λ_{3} ℤ ≃ Λ_{1} A_{2} ≃ Λ_{2}

Table 1: Densest packings and highest kissing numbers known in low dimensions. (Parenthesized entries are nonlattice arrangements that are better than any known lattice.)

The ‘Low Dimensional Lattices’ project Some years ago Conway and I noticed that there were several places in the literature where the results could be simplified if they were described in terms of lattices rather than quadratic forms. (It seems clearer to say ‘the lattice E_{8}’ rather than ‘the quadratic form 2x_{1}^{2} +2x_{2}^{2} +4x_{3}^{2} +4x_{4}^{2} +20x_{5}^{2} +12x_{6}^{2} +4x_{7}^{2} +2x_{8}^{2} +2x_{1}x_{2} +2x_{2}x_{3} +6x_{3}x_{4} +10x_{4}x_{5} + 6x_{5}x_{6} + 2x_{6}x_{7} + 2x_{7}x_{8}’.) This led to a series of papers [7], [10], [13].

Integral lattices of determinant d = 1 (‘unimodular’ lattices) have been classified in dimensions ≤ 25, dimensions 24, 25 being due to Borcherds. In [16, Ch. 15] and [7, (I)] we extended this to d ≤ 25 for various ranges of dimension.

[7, (II)] is based on the work of Dade, Plesken, Pohst and others, and describes the lattices associated with the maximal irreducible subgroups of GL(n, ℤ) for n = 1, …, 9, 11, 13, 17, 19, 23. Nebe, and Nebe and Plesken (see [29], [32]) have recently completed the enumeration of the maximal finite irreducible subgroups of GL(n, ℚ) for n ≤ 31, together with the associated lattices.

[7, (IV)] gives an improved version of the mass formula for lattices, and [7, (V)] studies when an n-dimensional integral lattice can be represented as a sublattice of ℤ^{m} for some m ≥ n, or failing that, by a sublattice of s^{−1/2}ℤ^{m} for some integer s. [10] describes the Voronoi and Delaunay cells of all the root lattices and their duals, and [7, (VI), (VIII)] discusses how the Voronoi cell of a 3- or 4-dimensional lattice changes as the lattice is continuously varied.

[7, (VII)] determines the ‘coordination sequences’ of various lattices. Consider E_{8}, for example, and let S(k) denote the number of lattice points that are k steps from the origin, where a step is a move to an adjacent sphere (S(1) is the kissing number). Then ∑_{k=0}^{∞} S(k)x^{k} = f(x)/(1 − x)^{8}, where f(x) = 1 + 232x + 7228x^{2} + …+x^{8}. Thus the coordination sequence for E_{8} begins 1, 240, 9120, . . .. For other examples see [39]

Perfect lattices One possible approach to the determination of the densest lattices in dimensions 7 to 9 is via Voronoi’s theorem that the density of Λ is a local maximum if and only if Λ is perfect and eutactic [27].

In 1975 Stacey, extending the work of several earlier authors, published a list of 33 perfect lattices in dimension 7. Unfortunately one of the 33 was omitted from her papers and her dissertation. In [7, (III)] we reconstructed the missing lattice and ‘beautified’ all 33, computing their automorphism groups, etc. In 1991 Jaquet-Chiffelle [22] completed this work by showing that this is indeed the full list of perfect lattices in ℝ^{7}. This provides another proof that E_{7} is the densest lattice in dimension 7.

Martinet, Bergé and their students are presently attempting to classify the eight-dimensional perfect lattices, and it appears that there will be roughly 10000 of them. Whether this approach can be used to determine Δ_{9}^{(L)} remains to be seen!

5 Dimension 9. Laminated lattices

There is a simple construction, the ‘laminating’ or ‘greedy’ construction, that produces many of the densest lattices in dimensions up to 26. Let Λ_{1} denote the even integers in ℝ^{1}, and define the n-dimensional laminated lattices Λ_{n} recursively by: consider all lattices of minimal norm 4 that contain some Λ_{n−1} as a sublattice, and select those of greatest density. It had been known since the 1940’s that this produces the densest lattices known for n ≤ 10. In [6] we determined all inequivalent laminated lattices for n ≤ 25, and found the density of Λ_{n} for n ≤ 48 (Fig. 1). A key result needed for this was the determination of the covering radius of the Leech lattice and the enumeration of the deep holes in that lattice [16, Ch. 23].

What are all the best sphere packings in low dimensions? In [13] we describe what may be all the best packings in dimensions n ≤ 10, where ‘best’ means both having the highest density and not permitting any local improvement. In particular, we conjecture that Δ_{n}^{(L)} = Δ_{n} for n ≤ 9. For example, it appears that the best five-dimensional sphere packings are parameterized by the 4-colorings of ℤ. We also find what we believe to be the exact numbers of ‘uniform’ packings among these, those in which the automorphism group acts transitively. These assertions depend on certain plausible but as yet unproved postulates.

A remarkable property of 9-dimensional packings. We also show in [13] that the laminated lattice Λ_{9} has the following astonishing property. Half the spheres can be moved bodily through arbitrarily large distances without overlapping the other half, only touching them at isolated instants, the density remaining

8 10 0 6  Leech 47 48 23 21 19  E_{8} 11(2) 12(3) 13(3)  25(23) 26(> 70, 000) BW_{16} 17 20 18 14 16 2 4 22 15 9 7 5 3 1 24 ... . . . . . .  . . . . . .

Figure 1: Inclusions among laminated lattices Λ_{n}.

the same at every instant. A typical packing in this family consists of the points of D_{9}^{θ+} = D_{9} ∪ D_{9} + ((1/2)^{8}, θ/2), for θ real. D_{9}^{0+} is Λ_{9} and D_{9}^{1+} is D_{9}^{+}, the 9dimensional diamond structure. All these packings have the same density, which we conjecture is the value of Δ_{9} = Δ_{9}^{(L)}. Another result in [13] is that there are extraordinarily many 16-dimensional packings that are just as dense as the Barnes-Wall lattice BW_{16} ≃ Λ_{16}.

6 Dimension 10. Construction A.

In dimension 10 we encounter for the first time a nonlattice packing that is denser than all known lattices. This packing, and the nonlattice packing with the highest known kissing number in dimension 9, are easily obtained from ‘Construction A’ (cf. [24]). If C is a binary code of length n, the corresponding packing is P (C) = {x ∈ ℤ^{n} : x (mod 2) ∈ C}.

Consider the vectors abcde ∈ (ℤ/4ℤ)^{5} where b, c, d ∈ {+1, −1}, a = c − d, e = b + c, together with all their cyclic shifts, and apply the ‘Gray map’ 0 → 00, 1 → 01, 2 → 11, 3 → 10 to obtain a binary code C_{10} containing 40 vectors of length 10 and minimal distance 4. This is our description [12] of a code first

ROGER’S BOUND Q_{32} Ks_{36}  Λ_{n} LEECH LATTICE Λ_{24} 2 -2 -3  DIMENSION  Λ_{48} D_{4}  BW_{16}  Λ_{n}  P_{48q} D_{3}  Λ_{n} K_{12} Λ_{8} = E_{8}  K_{n} 1  12 16  44 4  24  40  48 -1 0  36 32 8  20  28 (SCALED) DENSITY

Figure 2: Densest sphere packings known in dimensions n ≤ 48.

discovered by Best. The code is unique [25]. Then P (C_{10}) = P_{10c} is the record 10-dimensional packing.

Figure 2 shows the density of the best packings known up to dimension 48, rescaled to make them easier to read. The vertical axis gives log_{2} δ +n(24−n)/96. The figure also shows the upper bounds of Muder (for n = 3) and Rogers (n ≥ 4). Lattice packings are indicated by small circles, nonlattices by crosses (however, the locations of the lattices are only approximate). The figure is dominated by the two arcs of the graph of the laminated lattices Λ_{n}, which touch the zero ordinate at n = 0, 24 (the Leech lattice) and 48. K_{12} is the Coxeter-Todd lattice.

7 Dimensions 18–22

Record nonlattice packings in dimensions 18, 20 and 22 have recently been given in [4], [14], [40]. Vardy’s construction [40], ‘Construction B^{∗}’, also uses binary codes. Let B and C be codes of length n such that c·(1+b) = 0 for all b ∈ B, c ∈ C, and set P^{∗}(B, C) = {0+2b+4x, 1+2c+4y : b ∈ B, c ∈ C, x, y ∈ ℤ^{n}, ∑ x_{i} even, ∑ y_{i} odd}. For example, by taking B to be the quadratic residue code of length 18 and C to be its dual, Bierbrauer and Edel [4] obtain a new record packing in ℝ^{18}.

8 Dimension 24. The Leech lattice

The Leech lattice Λ_{24} is a remarkably dense packing in ℝ^{24} (as can be seen from Fig. 2). Here are four constructions. (i) As a laminated lattice: start in dimension 1 with the lattice Λ_{1} = ℤ and apply the greedy algorithm (see Fig. 1). (ii) Apply Construction A to the Golay code of length 24 to obtain a lattice L_{24}. Then Λ_{24} is spanned by (−3/2, 1/2, …, 1/2) and {x ∈ L_{24} : ∑ x_{i} ≡ 0 (mod 4)}. (iii) Hensel lift the Golay code to an extended cyclic (and self-dual) code over ℤ/4ℤ and apply ‘Construction A mod 4’ [5]. (iv) There is a unique unimodular even lattice II_{25,1} in Lorentzian space ℝ^{25,1}, consisting of the points (x_{0}x_{1} ⋯ x_{24}|x_{25}) with all x_{i} ∈ ℤ or all x_{i} ∈ ℤ+1/2 and satisfying x_{0} +⋯+x_{24} −x_{25} ∈ 2ℤ. Let w = (0 1 ⋯ 24|70), a vector of zero length. Then (w^{⊥} in II_{25,1})/w is Λ_{24} [16, Ch. 26].

9 Dimensions 26–31

New packings in these dimensions have been discovered by Bacher, Borcherds, Conway, Vardy, Venkov — see [16] for details.

10 Dimension 32. Modular lattices

An N-modular lattice [34] is an integral lattice that is similar to its dual, under a similarity that multiplies norms by N. A unimodular lattice is 1-modular. The interest in this family arises because many of the densest known lattices are Nmodular: ℤ, A_{2}, D_{4}, E_{8}, K_{12}, BW_{16}, Λ_{24}, Q_{32}, P_{48q}, . . ..

Quebbemann’s lattice Q_{32}, for example, is 2-modular, and can be constructed from a Reed-Solomon code of length 8 over 𝔽_{9} [33], [16, Ch. 8].

Shadow theory. The concept of the shadow of a lattice or code was introduced in [8], [9] (see also [15]) and has proved to be very useful ([9] has stimulated over 50 sequels in the coding literature).

Let Λ be an n-dimensional unimodular lattice. If Λ is even then the shadow S(Λ) = Λ, otherwise S(Λ) = (Λ_{0})^{∗} \ Λ, where the subscript 0 denotes even sublattice. The set 2S(Λ) = {2s : s ∈ S(Λ)} is precisely the set of parity vectors for Λ, i.e. the vectors u ∈ Λ such that u · x ≡ x · x (mod2) for all x ∈ Λ. Such vectors have been studied by many authors from Braun (1940) onwards, but their application to obtaining bounds on lattices seems to have been overlooked.

If the theta series of Λ is Θ_{Λ}(z) then [8] the shadow has theta series

(\frac{e^{πi/4}}{\sqrt{z}} )^{n} Θ_{Λ} (1 − \frac{1}{z}) .  (1)

One of the most satisfying properties of integral lattices is the classical theorem that (a) if Λ is a unimodular lattice then Θ_{Λ} belongs to the graded ring ℂ[Θ_{ℤ}, Θ_{E_{8}}], and (b) if Λ is even then Θ belongs to ℂ[Θ_{E_{8}}, Θ_{Λ_{24}}].

To illustrate the use of the shadow, let us prove there is no 9-dimensional unimodular lattice of minimal norm 2. If so then from (a) Θ_{Λ} = −Θ_{ℤ}/8+9Θ_{E_{8}}/8 = 1 + 252q^{2} + 456q^{3} + ⋯, where q = e^{πiz}. But then (1) implies Θ_{S(Λ)} = \frac{9}{4}q^{1/4} + \frac{1913}{4}q^{9/4} + ⋯, a contradiction since Θ_{S(Λ)} must have integer coefficients.

In [26] we used (a), (b) to show that the minimal norm μ of an n-dimensional odd unimodular lattice satisfies

μ ≤ [\frac{n}{8}] + 1 ,  (2)

and for an even unimodular lattice

μ ≤ 2 [\frac{n}{24}] + 2 .  (3)

In [36] we used shadow theory to strengthen (2) by showing that odd lattices satisfy

μ ≤ 2 [\frac{n}{24}] + 2 ,  (4)

except that μ ≤ 3 when n = 23. In view of the similarity between (3) and (4) we propose that a lattice satisfying either bound with equality be called extremal (the old definition of this term was based on (2) and (3)).

Quebbemann [35] has generalized (3) to certain families of even N-modular lattices, and analogous bounds for odd N-modular lattices (using an appropriate generalization of the shadow) were given in [36]. One can then define extremal N-modular lattices.

11 Higher dimensions

Space does not permit more than a mention of the following: Kschischang and Pasupathy’s lattice Ks_{36} in ℝ^{36} [23]; the three extremal unimodular lattices P_{48q}, P_{48p}, P_{48n} in ℝ^{48}, the latter being a recent discovery of Nebe [30]; Bachoc’s extremal 2-modular lattice in ℝ^{48} [1]; Nebe’s extremal 3-modular lattice in ℝ^{64} [30]; and Bachoc and Nebe’s extremal unimodular lattice in ℝ^{80} [2].

The existence of the following extremal lattices is an open question: 3-modular in ℝ^{36} (determinant d = 3^{18}, minimal norm μ = 8); 2-modular in ℝ^{64} (d = 2^{32}, μ = 10); unimodular in ℝ^{72} (d = 1, μ = 8).

From dimensions 80 to about 4096 the densest lattices known are the Mordell-Weil lattices discovered by Elkies [19], and Shioda [38]. But we know very little about this range, as evidenced by the recent construction of record kissing numbers in dimensions 32 to 128 [17] from binary codes. In dimension 128, for example, the Mordell-Weil lattice has kissing number 218044170240 [18], whereas in our construction (which admittedly is not a lattice) some spheres touch 8812505372416 others.

It would also be desirable to have better upper bounds, especially in low dimensions (see Fig. 2). The Kabatiansky-Levenshtein bound is asymptotically better than the Rogers’ bound, but not until the dimension is above about 40. We know very little about these problems!

In short, many beautiful packings have been discovered, but there are few proofs that any of them are optimal.

References

[1] C. Bachoc, Applications of coding theory to the construction of modular lattices, J. Combin. Theory A 78 (1997), 92–119.

[2] C. Bachoc and G. Nebe, Extremal lattices of minimum 8 related to the Mathieu group M_{22}, J. reine angew. Math. 494 (1998), 155–171.

[3] A. Bezdek and W. Kuperberg, Packing Euclidean space with congruent cylinders and with congruent ellipsoids, in Victor Klee Festschrift, ed. P. Gritzmann et al., Amer. Math. Soc., 1991, pp. 71–80.

[4] J. Bierbrauer and Y. Edel, Dense sphere packings from new codes, preprint, 1998.

[5] A. Bonnecaze, A. R. Calderbank and P. Solé, Quaternary quadratic residue codes and unimodular lattices, IEEE Trans. Inform. Theory 41 (1995), 366– 377.

[6] J. H. Conway and N. J. A. Sloane, Laminated lattices, Ann. Math. 116 (1982), 593–620.

[7] J. H. Conway and N. J. A. Sloane, Low-dimensional lattices: Proc. Royal Soc. Ser. A. I: 418 (1988), 17–41; II: 419 (1988), 29–68; III: 418 (1988), 43–80; IV: 419 (1988), 259–286; V: 426 (1989), 211–232; VI: 436 (1991), 55–68; VII: 453 (1997), 2369–2389; VIII (in preparation).

[8] J. H. Conway and N. J. A. Sloane, A new upper bound for the minimum of an integral lattice of determinant one, Bull. Am. Math. Soc. 23 (1990), 383–387; 24 (1991), 479.

[9] J. H. Conway and N. J. A. Sloane, A new upper bound for the minimal distance of self-dual codes, IEEE Trans. Inform. Theory 36 (1990), 1319–1333.

[10] J. H. Conway and N. J. A. Sloane, The cell structures of certain lattices, in Miscellanea mathematica, ed. P. Hilton et al., Springer-Verlag, NY, 1991, pp. 71–107.

[11] J. H. Conway and N. J. A. Sloane, On lattices equivalent to their duals, J. Number Theory 48 (1994), 373–382.

[12] J. H. Conway and N. J. A. Sloane, Quaternary constructions for the binary single-error-correcting codes of Julin, Best and others, Designs, Codes, Crypt. 4 (1994), 31–42.

[13] J. H. Conway and N. J. A. Sloane, What are all the best sphere packings in low dimensions?, Discrete Comput. Geom. 13 (1995), 383–403.

[14] J. H. Conway and N. J. A. Sloane, The antipode construction for sphere packings, Invent. math. 123 (1996), 309–313.

[15] J. H. Conway and N. J. A. Sloane, A note on unimodular lattices, J. Number Theory (to appear).

[16] J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag, NY, 3rd edition, 1998.

[17] Y. Edel, E. M. Rains and N. J. A. Sloane, On kissing numbers in dimensions 32 to 128, Electron. J. Combin. 5 (1) (1998), paper R22.

[18] N. D. Elkies, personal communication.

[19] N. D. Elkies, Mordell-Weil lattices in characteristic 2: I. Construction and first properties, Internat. Math. Res. Notices (No. 8, 1994), 353–361.

[20] T. C. Hales, Sphere packings, Discrete Comput. Geom. I: 17 (1997), 1–51; II: 18 (1997), 135–149; III: preprint.

[21] W.-Y. Hsiang, On the sphere packing problem and the proof of Kepler’s conjecture, Internat. J. Math. 93 (1993), 739–831; but see the review by G. Fejes Tóth, Math. Review 95g #52032, 1995.

[22] D.-O. Jaquet-Chiffelle, Enumération complète des classes de formes parfaites en dimension 7, Ann. Inst. Fourier 43 (1993), 21–55.

[23] F. R. Kschischang and S. Pasupathy, Some ternary and quaternary codes and associated sphere packings, IEEE Trans. Inform. Theory 38 (1992) 227–246.

[24] J. Leech and N. J. A. Sloane, Sphere packing and error-correcting codes, Canad. J. Math. 23 (1971), 718–745.

[25] S. Litsyn and A. Vardy, The uniqueness of the Best code, IEEE Trans. Inform. Theory 40 (1994), 1693–1698.

[26] C. L. Mallows, A. M. Odlyzko and N. J. A. Sloane, Upper bounds for modular forms, lattices and codes, J. Alg. 36 (1975), 68–76.

[27] J. Martinet, Les réseaux parfaits des espaces euclidiens, Masson, Paris, 1996.

[28] D. J. Muder, A new bound on the local density of sphere packings, Discrete Comput. Geom. 10 (1993), 351–375.

[29] G. Nebe, Finite subgroups of GL_{n}(ℚ) for 25 ≤ n ≤ 31, Comm. Alg. 24 (1996), 2341–2397.

[30] G. Nebe, Some cyclo-quaternionic lattices, J. Alg. 199 (1998), 472–498.

[31] G. Nebe and N. J. A. Sloane, A Catalogue of Lattices, published electronically at http://www.research.att.com/∼njas/lattices/.

[32] W. Plesken, Finite rational matrix groups — a survey, in Proc. Conf. “The ATLAS: Ten Years After”, to appear.

[33] H.-G. Quebbemann, Lattices with theta-functions for G(\sqrt{2}) and linear codes, J. Alg. 105 (1987), 443–450.

[34] H.-G. Quebbemann, Modular lattices in Euclidean spaces, J. Number Theory 54 (1995), 190–202.

[35] H.-G. Quebbemann, Atkin-Lehner eigenforms and strongly modular lattices, L’Enseign. Math. 43 (1997), 55–65.

[36] E. M. Rains and N. J. A. Sloane, The shadow theory of modular and unimodular lattices, J. Number Theory, to appear.

[37] C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27 (1948), 379–423 and 623–656.

[38] T. Shioda, Mordell-Weil lattices and sphere packings, Am. J. Math. 113 (1991), 931–948.

[39] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/∼njas/sequences/.

[40] A. Vardy, A new sphere packing in 20 dimensions, Invent. math. 121 (1995), 119–133.

N. J. A. Sloane

AT&T Labs-Research 180 Park Avenue Florham Park NJ 07932-0971 USA njas@research.att.com