.de HXS .if \\$1=3 .ds } .. .fp 4 M2 UnivMath2 .fp 5 M5 UnivMath5 .fp 6 M6 UnivMath6 .fp 7 M4 UnivMath4 .fp 8 M3 UnivMath3 .nr Pt 1 .EQ delim $$ gsize 11 define Subbase % .3 % define Supshift % .5 % define lpar % left ( % define rpar % right ) % define lp % left ( % define rp % right ) % define lbr % left "{" % define rbr % right "}" % define llb % left "{" % define lrb % right"}" % define lb % roman "{" % define rb % roman "}" % define cup % font M4 "\N'60'" % define cap % font M4 "\N'62'" % define => % font S "\N'222'" % define le % ^<=^ % define ge % ^>=^ % define ne % ^!=^ % define dd % "..." % define spr % sup prime % define sppr % sup {prime prime} % define sst % sup star % define smf % sum from % define SGf % size +2 SIGMA from % define SG % size +2 SIGMA % define mem % member % define RR % font M6 R % define ZZ % font M6 Z % define LA % LAMBDA % define LAs % LAMBDA sub % define cd % ^cdot^ % define bS % / % define vs % v sub % define xs % x sub % define ps % p sub % define ys % y sub % define ws % w sub % define As % A sub % define sb % ^!subset^ % define Sb % {S bar} % define ms % m sub % define ns % n sub % define cH % size +2 chi % define cHs % size +2 chi sub % define us % u sub % define ep % epsilon % define eps % epsilon sub % define ga % gamma % define gas % gamma sub % define be % beta % define bes % beta sub % define af % alpha % define afs % alpha sub % define Fs % F sub % define ds % d sub % define es % e sub % .EN .S 11 .nr Df 3 .WC -FB .am DE .ls 2 .sp .. .ds HP 11 11 11 .ds HF 3 3 3 .ND "March 5, 1991" .TL "311401-1807" "20878" Low-Dimensional Lattices VI: Voronoi Reduction of Three-Dimensional Lattices* .AU "J. H. Conway" JHC "Princeton University" "" "Princeton, NJ" .AU "N. J. A. Sloane" NJAS MH 11218 "" "2C-376 (908) 582-2005" .TM 11218-910305-07\|TM .ig .AS 1 .. .ig .AE .. .FS * A slightly different version of this paper appeared in Proceedings Royal Society of London, Series A, Vol. 436 (1992), 55-68. .FE .MT 4 1 .ce .B ABSTRACT .sp .P The aim of this paper is to describe how the Voronoi cell of a lattice changes as that lattice is continuously varied. The usual treatment is simplified by the introduction of new parameters called the vonorms and conorms of the lattice. The present paper deals with dimensions $n le 3$; a sequel will treat four-dimensional lattices. An elegant algorithm is given for the Voronoi reduction of a three-dimensional lattice, leading to a new proof of Voronoi's theorem that every lattice of dimension $n le 3$ is of the first kind, and of Fedorov's classification of the three-dimensional lattices into five types. There is a very simple formula for the determinant of a three-dimensional lattice in terms of its conorms. .ls 2 .H 1 "Introduction" Our aim in this paper and its sequel is to describe how the Voronoi cell of a lattice changes as that lattice is continuously varied. We simplify the usual treatment by introducing new parameters which we call the vonorms and conorms of the lattice. The present paper studies lattices in one, two and three dimensions, ending with the theorem of Fedorov (1885,\|1891) on the five types of three-dimensional lattices. The sequel will use the same machinery to give a simple proof of the theorem of Delone (1929, 1937-1938), as corrected by Stogrin (1973), that there are 52 types of four-dimensional lattices. .P The main theorem of the present paper is the following. .H 3 "Theorem\ 1." .I Each three-dimensional lattice is uniquely represented by a projective plane of order $2$ labeled with seven numbers, the conorms of the lattice, whose minimum is $0$ and whose support is not contained in a proper subspace. Two lattices are isomorphic if and only if the corresponding labelings differ only by an automorphism of the plane. .R .P As we shall see, in three dimensions our seven ``conorms'' are just 0 and the six ``Selling parameters.'' However, this apparently trivial replacement of six numbers by seven numbers whose minimum is zero leads to several valuable improvements in the theory. .AL .LI (i) The conorms vary continuously with the lattice. (For the Selling parameters the variation is usually continuous but requires occasional readjustments.) .LI (ii) The definition of the conorms makes it apparent that they are invariants of the lattice. (The Selling parameters are almost but not quite invariant.) .LI (iii) All symmetries of the lattice arise from symmetries of the conorm function. (Again, this is false for the Selling parameters.) .LE .P There are several reasons for studying Voronoi cells of lattices. Besides the applications to packing, covering and quantizing problems (see for example Barnes & Sloane 1983; Conway & Sloane 1988a; Gruber & Lekkerkerker 1987; Ryskov & Baranovskii 1976, 1979) there are connections with the theory of tilings. Following Gruber & Lekkerkerker (1987 p.\ 168) we define an $n$-dimensional \f2parallelotope\f1 (or \f2parallelohedron\f1 if $n=3$) be a convex body $S$ which admits a lattice tiling (in other words there is a lattice $LA$ such that the translates $S+ u$, $u mem LA$ cover $RR sup n$ while their interiors are disjoint). Voronoi (1907-1908) conjectured that every parallelohedron is the affine image of the Voronoi cell of some lattice. This was proved for $n le 4$ by Delone (1929), while for $n ge 5$ the question remains open. In particular there are five three-dimensional parallelohedra, the affine images of the five Voronoi cells described in Fig.\ 7 (see Theorem\ 9). .P Voronoi vectors are defined in Section\ 2, and vonorms and conorms in Sections\ 3-5. All of these quantities are particularly simple in the case of lattices of the ``first kind,'' defined in Section\ 2. Sections\ 6-7 will establish that every lattice of dimension $n le 3$ is of the first kind. In particular the proof that every three-dimensional lattice is of the first kind is accomplished by means of a new algorithm given in Section\ 7 for the ``Voronoi reduction'' of the lattice, that is, for finding a specification of the lattice that makes its Voronoi vectors apparent. Figure\ 5 shows an example. This algorithm is also used to prove Theorem\ 1. The last section of the paper applies the preceding theory to derive the five types of three-dimensional Voronoi cells (summarized in Figure\ 7, Theorem\ 9 and Table\ I). At the beginning of Section\ 8 we give especially simple formulae (involving the conorms) for the vertices, edges and faces of the generic Voronoi cell of a three-dimensional lattice, for its edge-lengths and for the determinant of the lattice (see Eqs.\ (15), (17)). .H 1 "Voronoi vectors" Let $LA^subset^RR sup n$ be a real $n$-dimensional lattice (as in Conway & Sloane 1988a). The \f2Voronoi cell\f1 $V(u)$ for $u mem LA$ is the set of points of $RR sup n$ that are at least as close to $u$ as to any other lattice point: .DS 2 .EQ V(u) ~=~ lb x mem RR sup n :~ N(x-u) le N(x-v)^, ~~~roman {"all"}~~~v mem LA rb ^, .EN .DE where $N(x) = x cd x$ denotes the norm of a vector. All the $V(u)$ for $u mem LA$ are congruent convex polytopes. They partition $RR sup n$ into the \f2Voronoi honeycomb\f1 of $LA$. .P A vector $v mem LA$ is called a \f2Voronoi vector\f1 if the hyperplane .DS 2 .EQ lb x mem RR sup n :~ x cd v ^=^ \(12 ^v cd v rb .EN .DE has a nonempty intersection with $V(0)$ (the Voronoi cell containing the origin). A Voronoi vector is \f2relevant\f1 (or \f2strict\f1) if this intersection is an $(n-1)$-dimensional face of $V(0)$, and is otherwise \f2irrelevant\f1 (or \f2lax\f1). .P By the \f2Voronoi reduction\f1 of $LA$ we mean finding a description of $LAMBDA$ from which its Voronoi vectors are apparent. .P The starting point for this investigation is the following theorem. .H 3 "Theorem\ 2." .I A nonzero vector $v mem LA$ is $(i)$\ a Voronoi vector if and only if $v$ is a shortest vector in the class $v+ 2 LA$; $(ii)$\ a strict Voronoi vector if and only if $v$ and $-v$ are the only shortest vectors in $v+ 2 LA$. .R .P The usual version of this theorem only gives part (ii) (Voronoi 1908-1909, vol.\ 134, p.\ 277; Venkov 1983; Engel 1986, p.\ 35; Gruber & Lekkerkerker 1987, p.\ 95; Conway & Sloane 1988a, where however due to an unfortunate printer's error the statement of the theorem was omitted from the foot of page\ 474). .H 3 \f2Proof\f1. (i)\ Suppose $v$ is a Voronoi vector yet there is a vector $w mem LA$ with $v- w mem 2 LA$, $N(w) ^<^ N(v)$. Then $t= \(12 (v+w)$ and $u = \(12 (v-w)$ belong to $LA$. Let $P$ satisfy $P cd v = \(12 v cd v$, $P cd t le \(12 t cd t$, $P cd u le \(12 u cd u$. These equations imply $N(v) le N(w)$, a contradiction. On the other hand, suppose $v$ is a shortest vector in its class $v + 2 LA$, but is not a Voronoi vector. Then for some $w mem LA$, $\(12 v cd w ^>^ \(12 w cd w$, so $N( v-2w) ^<^ N(w)$, a contradiction. The proof of (ii) (see for example page\ 475 of Conway & Sloane 1988a) is similar. .P Since there are $2 sup n -1$ nonzero classes of $LA / 2 LA$, from part (i) of the theorem there are at least $2(2 sup n -1)$ Voronoi vectors. In a generic (or random) lattice there are no coincidences between the lengths of vectors in distinct classes, and hence there are exactly $2 ( 2 sup n -1 )$ Voronoi vectors, all strict. .P A lattice $LA$ is said to be of \f2Voronoi's\f1 \f2first kind\f1 if it has what we shall call an \f2obtuse superbase\f1; that is to say, a set of vectors $vs 0$, $vs 1 ,^dd ,^vs n$ such that $vs 1 ,^dd ,^vs n$ is an integral basis for $LA$ and .DS 2 .EQ vs 0 + vs 1 +^...^+ vs n ~=~ 0 .EN .DE (this is a \f2superbase\f1), and in addition .DS 2 .EQ (1) ps ij ~=~ vs i cd vs j le 0 , ~~~for ~~~i,^j^=^0 ,^dd ,^n,^i ne j ^, .EN .DE (this is the \f2obtuse\f1 condition). The superbase is \f2strictly\f1 obtuse if .DS 2 .EQ (2) vs i cd vs j ^<^0 , ~~~for ~~~ i,^j ^=^0, ^dd ,^n , ^i ne j ^. .EN .DE .P For example, the root lattice $As n$ ($n ge 1$) and its dual $As n sst$ are of the first kind. The $n+1$ cyclic shifts of $(1,^-1 ,^0,^dd ,^0)$ are an obtuse superbase for $A sub n$, and the vectors $lpar n over n+1 , ~ -1 over n+1 ,~"...",~ -1 over n+1 rpar$ are a strictly obtuse superbase for $A sub n sup star$. .P The numbers $ps ij$ are traditionally called the \f2Selling parameters\f1 for the superbase or lattice (Selling, 1874; Baranovskii, 1980), and if we define .DS 2 .EQ (3) ps {i| jk dd l} ~=~ ps ij + ps ik +^...^+ ps il .EN .DE then the inner product matrix for the superbase is .DS 2 .EQ (4) left [ matrix { ccol {ps {0| 12 dd n} above - ps 10 above "" above - ps n0} ccol {- ps 01 above ps {1| 02 dd n} above ^...^ above - ps n1} ccol {- ps 02 above - ps 12 above "" above - ps n2} ccol {^...^ above ^...^ above ^...^ above ^...^} ccol {- ps 0n above - ps 1n above "" above ps {n| 01 dd n-1}} } right ] ^. .EN .DE .H 3 "Theorem\ 3." .I $(i)$\ If $LA$ is of the first kind with superbase $vs 0 ,^dd ,^vs n$ then the $2 sup n+1 -2$ subsums .DS 2 .EQ vs S ~=~ smf {i mem S} ^vs i ^, ~~~ S sb lb 0,^1,^dd ,^n rb ^, .EN .DE $0 ^<^ |S| ^<^ n$, are Voronoi vectors. Also $vs S$ and $vs {S bar} = - vs S$ are congruent modulo $2 LA$, but otherwise these vectors are in distinct classes of $LA bS 2 LA$. $(ii)$\ The vectors $vs S$ are all strict if and only if the superbase is strict. .R .H 3 Remark. Here $S bar$ is the set complementary to $S$. We write $v sub ijk...$ for $v sub {lb i,j,k, dd rb}$. .H 3 \f2Proof\f1. (i)\ The norm of any vector $v = SGf i=0 to n ^ms i vs i mem LA$, $ms i mem ZZ$, is plainly given by Selling's formula .DS 2 .EQ (5) N lp sum from i=0 to n ^ms i vs i rp ~=~ sum from {pile {i,j=0 above i < j}} to n ^ps ij ( ms i - ms j ) sup 2 .EN .DE (Selling, 1874). Now $v$ is unchanged if the $ms i$ are all increased by the same amount, and unchanged modulo $2 LA$ if the $ms i$ are changed by even integers. So within a given coset of $LA bS 2 LA$ the norm is minimized when all even $ms i$ are replaced by 0 and all odd $ms i$ by 1. (ii)\ If all $ps ij ^>^0$ and we suppose, as we may, that $min ^lb ms 0 ,^dd ,^ms n rb =0$, then the norm is minimized \f2only\f1 if all $ms i$ are 0 or 1.$~~~~blot$ .H 1 "Vonorms" The \f2Voronoi norm\f1, or \f2vonorm\f1, $roman vo ( v bar )$, of a class $v bar = v+ 2 LA$ of $LA bS 2 LA$ is the least norm of any vector in that class. Thus the vonorms are the norms of the Voronoi vectors (the \f2proper\f1 vonorms), together with zero (the \f2improper\f1 vonorm). By ``the vonorms'' we usually mean ``the proper vonorms''. The vonorm map from $LA bS 2 LA$ to $RR$ is obviously an invariant of $LA$; we shall see in dimensions $n le 4$ (and we conjecture in general) that it also characterizes $LA$. The quotient $LAMBDA bS 2 LAMBDA$ can obviously be regarded as a vector space over the field of order 2. Since this important space is the domain of the vonorms we call it \f2vonorm space\f1. .H 3 "Theorem\ 4." .I The vonorms of a lattice of the first kind are the numbers .DS 2 .EQ (6) N( vs S ) ~=~ smf {i mem S ,^j mem Sb} ^ps ij ~=~ ps {ab dd c | d e dd f} ~~{(say)} ^, .EN .DE where $S = lb a, b,^dd ,^c rb$, $Sb = lb d, e, ^dd ,^f rb$. .R .H 3 \f2Proof\f1. This follows immediately from Theorem\ 3.$~~~~blot$ .H 1 Characters As usual we define a \f2real character\f1 on an $n$-dimensional lattice $LA$ to be a function $cH$ from $LA$ to $lb +- 1 rb$ with the property that $cH (u+v) = cH (u) cH (v)$ for all $u,^v mem LA$. The $2 sup n$ real characters form a group which is abstractly isomorphic to the vector space dual of the vonorm space $LAMBDA bS 2 LAMBDA$. We call this dual space \f2conorm space\f1. From now on, ``character'' will always mean ``real character.'' .H 3 "Theorem\ 5." .I The characters of a lattice of the first kind correspond to the subsets $S$ of $lb 0 ,^dd ,^n rb$ for which $| S|^$ is even. They are defined by .DS 2 .EQ (7) cHs S ( vs i ) ~=~ left { matrix { ccol {-1 ^, above "" above +1 ^,} lcol {~~~i mem S ^, above "" above ~~~i nomem S^.} } .EN .DE .R .H 3 \f2Proof\f1. It is easy to check that these are characters, and since there are $\(12 cd 2 sup n+1 = 2 sup n$ of them, there is no other.$~~~~blot$ .H 1 Conorms The \f2conjugate norm\f1, or \f2conorm\f1, $roman co ( cH )$ corresponding to a character $cH$ is defined by .DS 2 .EQ (8) roman co ( cH ) ~=~ - ^ 1 over {2 sup n-1} ^sum from {v bar mem LA bS 2 LA} ^cH ( v bar ) ^roman vo ( v bar ) ^. .EN .DE The conorm $roman co (1)$ corresponding to the trivial character $cHs 0 =1$ is called the \f2improper\f1 conorm. By ``the conorms'' we usually mean ``the proper conorms.'' The conorms are, apart from a scale factor, the Fourier transforms of the vonorms, and so carry exactly the same information as the vonorms. In fact .DS 2 .EQ (9) roman vo ( v bar ) ~=~ sum ^roman co ( cH ) ^, .EN .DE where the sum is taken over all $cH$ with $cH ( v bar ) = -1$. Since $roman vo ( v bar ) ^>^0$ if $v bar$ is not the zero class, (9) implies that the support of the conorm function cannot be contained in a proper subspace of conorm space. .H 3 "Theorem\ 6." .I For a lattice of the first kind the proper conorms are given by .DS 2 .EQ co ( cHs S ) ~=~ left { matrix { ccol {ps ij ^, above "" above 0^,} ccol {~~ i f ~~ S = lb i,j rb ^, above "" above ~~ otherwise^.} } .EN .DE So for a lattice of the first kind the conorms are the Selling parameters supplemented by 0's. .R .P 0 The proof is an easy calculation. .H 1 "One- and two-dimensional lattices" An $n$-dimensional lattice is represented by a point in a vector space of dimension $N = \(12 n (n+1)$, the space of Gram matrices. On the other hand there are $2 sup n -1$ proper vonorms (or conorms), a number which is always greater than or equal to $N$: .DS .TS center; c c c c n n n n. $n$ $N= \(12 n(n+1)$ $2 sup n -1$ difference .sp .5 1 1 1 0 2 3 3 0 3 6 7 1 4 10 15 5 5 15 31 16 \&. . . . .TE .DE .P In this section we briefly discuss the one- and two-dimensional cases, and show that there the vonorms are exactly enough to parametrize the space of lattices and that every lattice is of the first kind. .H 3 "Dimension\ 1." Let $LA$ have Gram matrix $(a)$, and generator $vs 1$, with $N( vs 1 ) =a$. Then $vs 0 = - vs 1$ and $vs 1$ form an obtuse superbase, the proper vonorm is $a$, and the proper conorm is $- vs 0 cd vs 1 = ps 01 = a$. .H 3 "Dimension\ 2." Suppose $LA$ is generated by vectors $vs 1$, $vs 2$ having Minkowski-reduced Gram matrix $left [ rpile {a above -h}~~ rpile {-h above b} right ]$, with $0 le 2h le a le b$. Then $vs 0 =- ( vs 1 + vs 2 )$, $vs 1$, $vs 2$ form an obtuse superbase, with Selling parameters $p sub ij$ determined by .DS 2 .EQ a ~=~ ps 01 + ps 12 , ~~h ~=~ ps 12 , ~~ b = ps 02 + ps 12 ^. .EN .DE The Voronoi vectors are $+- vs 0$, $+- vs 1$, $+- vs 2$, and if $h = ps 12 ne 0$ there is no other, while if $ps 12 =0$ there is an additional pair of Voronoi vectors $+- ( vs 1 - vs 2 )$. The corresponding Voronoi cells are shown in Figure\ 1. .P The proper vonorms are $a= ps 01 + ps 12$, $b = ps 02 + ps 12$, $c = ps 01 + ps 02 = a+b-2h$. These may be any three positive numbers satisfying the triangle inequalities .DS 2 .EQ (10) b+c ge a , ~~ c + a ge b , ~~ a + b ge c ^. .EN .DE The proper conorms $ps 01$, $ps 02$, $ps 12$ may be any three nonnegative numbers, although at least two must be strictly positive for $LA$ to be a proper lattice. Note that .DS 2 .EQ det ^LA ~=~ ab - h sup 2 ~=~ ps 01 ps 02 + ps 01 ps 12 + ps 02 ps 12 .EN .DE (compare Eq.\ (15) below). .P The vonorms have also a geometric interpretation. .H 3 "Theorem\ 7." .I The vonorms $ps {i|jk}$ of a two-dimensional lattice $LA$ are the three smallest norms of primitive vectors $($ignoring the distinction between vectors and their negatives$)$. .R .H 3 \f2Proof\f1. If the conorms are $ps ij$ then the norm of $v = SGf i ms i vs i$ is $SGf {i ^0$, by $af - 2 ep$, $be - 2 ep$, $ga + 2 ep = ep$, adding $2 ep$ to one conorm and subtracting $2 ep$ from the other two. .FS Since $size -2 {af + be}$, $size -2 {be + ga}$, $size -2 {ga + af}$ are positive, at most one conorm is negative. .FE After a finite number of such steps all the putative conorms are nonnegative and the algorithm terminates. .H 3 "Remark." The algorithms described here are theoretical rather than practical. In practice a reduction algorithm such as that of Lenstra, Lenstra and Lova\*'sz 1982 (see also Lagarias 1996) would be used before applying our algorithm. .H 1 "The five parallelohedra" In this section we study the Voronoi cells of three-dimensional lattices and prove Fedorov's theorem. .P Let $LA$ be an arbitrary three-dimensional lattice, with obtuse superbase $vs 0$, $vs 1$, $vs 2$, $vs 3$ and conorms $ps ij$. A vector $t mem RR sup 3$ will be specified by its inner products .DS 2 .EQ (13) ( t cd vs 0 ,^t cd vs 1 ,^t cd vs 2 ,^t cd vs 3 ) ~=~ ( ys 0 ,^ys 1 ,^ys 2 ,^ys 3 ) ~=~ y .EN .DE say, where $ys 0 + ys 1 + ys 2 + ys 3 =0$. .P We first show that the Voronoi cell for a generic three-dimensional lattice $LA$ is a truncated octahedron, or permutohedron, as in Fig.\ 6. Corresponding to each Voronoi vector $vs S$, $S sb lb 0,1,2,3 rb$, $1 le |S| le 3$, there is a face $F sub {S| Sb}$ (say), where $Sb = lb 0,1,2,3 rb ^"\e"^S$, of the Voronoi cell. The face $Fs {i|jkl}$ (where $lb i,j,k,l rb$ is any permutation of $lb 0,1,2,3 rb$) contains the points with $ys i = \(12^ ps i|jkl$, the face $Fs ij|kl$ contains the points with $ys i + ys j = - ys k - ys l = \(12^ ps ij|kl$, and the face $Fs ijk|l$ contains the points with $ys i + ys j + ys k = - ys l = \(12^ ps l|ijk$. Then $Fs {Sb | S} = - Fs {S| Sb}$ and $Fs {S| Sb}$ are opposite faces. .P We assert that the vertices of the Voronoi cell are the 24 points $ps ijkl$ (where again $lb i,j,k,l rb$ is any permutation of $lb 0,1,2,3 rb$) with coordinates .DS 3 .EQ ys i mark ~=~ \(12 ^( + ps ij + ps ik + ps il ) ^, .EN .sp .75 .EQ ys j lineup ~=~ \(12 ^( - ps ji + ps jk + ps jl )^, .EN .sp .75 .EQ ys k lineup ~=~ \(12 ^( - ps ki - ps kj + ps kl ) ^, .EN .sp .75 .EQ (14) ys l lineup ~=~ \(12 ^( - ps li - ps lj - ps lk )^. .EN .DE (Note that $ps klji = - ps ijkl$ and $ps ijkl$ are opposite vertices.) In fact, each such point $ps ijkl$ belongs to the three faces $Fs i|jkl$, $Fs ij|kl$ and $Fs ijk|l$. (In Fig.\ 6 $ps ijkl$ is strictly labeled $ijkl$.) Also $Fs i|jkl$ is a hexagonal face containing the six vertices $ps {i af be ga}$, where $lb af ,^be ,^ga rb = lb j,k,l rb$, and $Fs ij|kl$ is a rhombic face containing the four vertices $ps ijkl$, $ps ijlk$, $ps jikl$, $ps jilk$. .P Similar (although less symmetrical) coordinates for the Voronoi cell were given by Barnes (1956) and Barnes & Sloane (1983). .P The determinant of $LA$, the squared volume of the Voronoi cell, is the determinant of the Gram matrix .DS 2 .EQ left [ matrix { ccol {ps 1|023 above "" above - ps 12 above "" above - ps 13} ccol {- ps 12 above "" above ps 2|013 above "" above - ps 23} ccol {- ps 13 above "" above - ps 23 above "" above ps 3|012} } right ] ^, .EN .DE which is equal to .DS 3 .EQ mark ps 01 ^ps 02^ps 03 ^+^ ps 01^ps 02 ^ps 13 ^+^ ps 01 ^ps 02 ^ps 23 ^+^ ps 01^ps 03^ps 12 .EN .sp .75 .EQ +^lineup ps 01^ps 03 ^ps 23 ^+^ ps 01 ^ps 12 ^ps 13 ^+^ ps 01 ^ps 12 ^ps 23 ^+^ ps 01 ^ps 13 ^ps 23 .EN .sp .75 .EQ +^lineup ps 02 ^ps 03 ^ps 12 ^+^ ps 02 ^ps 03 ^ps 13 ^+^ ps 02 ^ps 12 ^ps 13 ^+^ ps 02 ^ps 12 ^ps 23 .EN .sp .75 .EQ +^lineup ps 02 ^ps 13 ^ps 23 ^+^ ps 03 ^ps 12 ^ps 13 ^+^ ps 03 ^ps 12 ^ps 23 ^+^ ps 03 ^ps 13 ^ps 23 ^. .EN .DE Upon examination of Fig.\ 3(b) we see that this can be written as .DS 2 .EQ (15) det ^LA ~=~ smf {lb P,Q,R rb = DELTA} ^roman co (P) ^roman co (Q) ^roman co (R) ^, .EN .DE where $lb P, Q, R rb$ runs through all 28 \f2triangles\f1 in Fig.\ 3(b), that is to say, through all bases for the conorm space. (For 12 of these triangles the product is 0.) .P If a vector $t$ is specified by $y = ( ys 0 , ys 1 , ys 2 , ys 3 )$, as in (13), then its norm is given by .DS 2 .EQ (16) N(t) ~=~ 1 over {det ^LA} ^y sup tr Dy ^, .EN .DE where $D = ( d sub ij )$, $d sub ii = ps jk ps kl + ps kl ps lj + ps lj ps jk$, $d sub ij = -\(12^ ( ps ik ps jl + ps il ps jk )$ $( i ne j )$, $0 le i,j le 3$. .P The Voronoi cell has six families of parallel edges. If we denote the vector along a typical edge by $es ij$ $( 0 le i ^<^ j le 3 )$, as in Fig.\ 6, then $es ij$ has coordinates $ys i = ps ij = - ys j$, $ys k = ys l =0$. From (16) we find that .DS 2 .EQ (17) N( es ij ) ~=~ 1 over {det ^LA} ~smf{lb P,Q,R rb = DELTA} ^roman co sup 2 (P) ^roman co (Q) ^roman co (R) ^, .EN .DE where the sum is over all triangles in Fig.\ 3(b) containing that node $P$ for which $roman co (P) = ps ij$. Note that (17) vanishes only when $roman co (P)$ does, since otherwise the support of the conorm function includes at least one base containing $P$. .P It follows that two lattices in which the same conorms are zero have combinatorially equivalent Voronoi cells (since one can be continuously deformed into the other without any edges being lost). There are only five choices for the locations of the zeros (see top of Fig.\ 7): .DS .TS center; l. one zero, .sp .25 two zeros, .sp .25 three collinear zeros, .sp .25 three noncollinear zeros, .sp .25 four zeros, .TE .DE since the nonzero conorms may not be collinear. Thus we have established the following theorem of Fedorov (1885,\|1891). .H 3 "Theorem\ 9." .I There are just five combinatorially distinct possibilities for the shape of the Voronoi cell of a three-dimensional lattice. .R .P The five cases are obviously distinct, for we see from (17) that if the conorms are varied in such a way that $roman co (P)$ approaches 0 then the corresponding family of parallel edges all shrink to points and the polyhedron simplifies. Figure\ 7 shows the effects of successive simplifications.\*F .FS During these simplifications the remaining edges may change their lengths and directions, but we ignore this in the figures. .FE The labels on the edges are the corresponding conorms, taken from the top row of diagrams. .P If we shrink its edges labeled $a$, the truncated octahedron of Fig.\ 7(i) becomes the hexa-rhombic dodecahedron\*F of Fig.\ 7(ii). .FS Abbreviating ``hexagonal-rhombic dodecahedron.'' We prefer this to the less specific name ``elongated dodecahedron'' of (Fejes To\*'th, 1964), (Coxeter, 1973). .FE This has one family of four parallel edges labeled $af^$, whose shrinkage leads to a rhombic dodecahedron (Fig.\ 7(iii)), and four families of six parallel edges such as those labeled $c$, whose shrinkage leads to a hexagonal prism (Fig.\ 7(iv)). .P Shrinking any of the families of parallel edges in Figs.\ 7(iii) or (iv) leads to a cuboid (Fig.\ 7(v)) or to a polyhedron of zero volume. .H 3 "The Delone diagram." An $n$-dimensional lattice of the first kind may also be described by its \f2Delone diagram\f1 (after Delone 1937-1938; see also Ryskov 1972 and Ryskov & Baranovskii 1979). This has $n+1$ nodes labeled $0,1,^dd ,^n$, with an edge labeled with the Selling parameter $ps ij$ joining nodes $i$ and $j$ whenever $ps ij ne 0$. The Delone diagrams for the five types of three-dimensional lattices are given in the bottom row of Fig.\ 7 (cf. Fig.\ 37 of Delone 1937-1938, p. 138). These diagrams are very useful, but have the disadvantage of not displaying all the symmetries of the situation. For example in Fig.\ 7(ii) it is possible to interchange $b$ and $ga$ independently of $c$ and $beta$: this is obvious from the conorm picture but not from the Delone diagram. Similarly in Fig.\ 7(iii) it is possible to permute all four parameters $b,c, be , ga$ freely, and in Fig.\ 7(iv) to permute $b, af , ga$. There is however a simple mnemonic: a permutation of the parameters that does not affect the circuits of the Delone diagram to which they belong leads to another specification of the same lattice. .P The conorm representation has no such defect. Two projective planes labeled with conorms represent the same lattice precisely when there is a conorm-preserving collineation between them. .P We call a three-dimensional lattice \f2primitive\f1 (or \f2primary\f1), \f2secondary\f1, \f2tertiary\f1, etc., according as it has $1,2,3,^dd$ conorms equal to 0. Table\ I lists the five types of three-dimensional lattices, together with the corresponding section of Fig.\ 7, the name of the Voronoi cell, and in the final column the (classically) integral lattice of smallest determinant of each type. The latter are obtained by setting all nonzero conorms in Fig.\ 7 equal to 1; the notation is that of Conway & Sloane 1988b. .DS .TS center; c s s s | c | c | c | c | | c | c | c | c |. Table I. The five types of three-dimensional lattices .sp _ .sp .25 Type Figure Voronoi Canonical cell example .sp .15 _ .sp .25 Primary Fig. 7(a) Truncated $2A sub 3 sup star$ octahedron $det = 16 $ .sp .15 _ .sp .25 Secondary Fig. 7(b) Hexa-rhombic $( As 1 sup 2 8 sub 1 ) sup +2$ dodecahedron $det = 8 $ .sp .15 _ .sp .25 Indecomposable Fig. 7(c) Rhombic $As 3$ tertiary dodecahedron $det = 4 $ .sp .15 _ .sp .25 Decomposable Fig. 7(d) Hexagonal $As 2 ^I sub 1$ tertiary or prism $det =3 $ simply decomposable .sp .15 _ .sp .25 Quaternary or Fig. 7(e) Cuboid $I sub 3$ fully decomposable $det = 1 $ _ .TE .sp .DE .H 3 "The dual lattice." If the conorms of a three-dimensional lattice $LA$ are as shown in Fig.\ 3(b), then those of its dual $LA sst$ are, after multiplication by $det ^LA$, as shown in Fig.\ 8, where we set .DS 3 .EQ (18) p p mark ~=~ min ^lb ps 01 ^ps 23 , ~ ps 02 ^ps 13 , ~ ps 03 ^ps 12 rb ^, .EN .sp .EQ (19) p p sub ijk lineup ~=~ ps ij ^ps jk ^+^ ps jk ^ps ki ^+^ ps ki ^ps ij ^. .EN .DE From this it is immediate that the dual of a .DS 3 fully decomposable lattice is fully decomposable, .sp .5 simply decomposable lattice is simply decomposable, .sp .5 secondary or indecomposable tertiary lattice is primary, .DE .P 0 while the dual of a primary lattice is primary, secondary or indecomposable tertiary according as the minimum in (18) is attained once, twice or thrice. .P There is an analogous classification to Table\ I in every dimension. In two dimensions the primary or indecomposable lattices are those with hexagonal Voronoi cells (Fig.\ 1(a)), and the others are secondary or decomposable with rectangular Voronoi cells (Fig.\ 1(b)). .P Delone (1929, 1937-1938), as corrected by Stogrin (1973), enumerated the Voronoi cells of four-dimensional lattices. There are three primary ones and 52 in all. In a sequel to the present paper we shall show that the conorm method enables us to enumerate these very simply, and we shall also give a detailed account of their properties. .PH "" .bp .ls 2 .ce .B References .sp .VL 3 .LI Baranovskii, E.\ P. 1980. ``The Selling reduction domain of positive quadratic forms in five variables'' (in Russian), Trudy Mat. Inst. V.\ A. Steklova, \f3152\f1, 5-33. English translation in Proc. Steklov Inst. Math., Issue\ 3, 1982, pp.\ 5-35. .pn 2 .PH "''- R-% -''" .LI Barnes, E.\ S. 1956. ``The covering of space by spheres,'' Canad. J. Math., \f38\f1, 293-304. .LI Barnes, E.\ S. and Sloane, N.\ J.\ A. 1983. ``The optimal lattice quantizer in three dimensions,'' SIAM J. Algebraic and Discrete Methods, \f34\f1, 30-41. .LI Conway, J.\ H. and Sloane, N.\ J.\ A. 1988a. ``Sphere Packings, Lattices and Groups,'' Springer-Verlag, NY. Third edition, Springer-Verlag, NY, 1999. .LI Conway, J.\ H. and Sloane, N.\ J.\ A. 1988b. ``Low-dimensional lattices I: Quadratic forms of small determinant,'' Proc. Royal Soc. London, Series A, \f3418\f1, 17-41. .LI Coxeter, H.\ S.\ M. 1973. ``Regular Polytopes,'' Dover, New York. .LI Delone, B.\ N. 1929. ``Sur la partition regulie\*`re de l'espace a\*` 4-dimensions,'' Izv. Akad. Nauk SSSR Otdel. Fiz.-Mat. Nauk, pp.\ 79-110 and 145-164. .LI Delone, B.\ N. 1937-1938. ``Geometry of positive quadratic forms'' (in Russian), Uspehi Mat. Nauk \f33\f1, 16-62; \f34\f1, 102-164. .LI Engel, P. 1986. ``Geometric Crystallography,'' Reidel, Dordrecht, Holland. .LI Fedorov, E.\ S. 1885. ``Elements of the study of figures'' (in Russian), Zap. Mineralog. Obsc. (2) \f321\f1, 1-279. Reprinted by Izdat. Akad. Nauk SSSR, Moscow, 1953. .LI Fedorov, E.\ S. 1891. ``The symmetry of regular systems of figures'' (in Russian), Zap. Mineralog. Obsc. (2) \f328\f1, 1-146. English translation in ``Symmetry of crystals,'' ACA Monograph no.\ 7, Amer. Crystallographic Assoc., New York, 1971, pp.\ 50-131. .LI Fejes To\*'th, L. 1964. ``Regular Figures,'' Pergamon, Oxford. .LI Gruber, P.\ M. and Lekkerkerker, C.\ G. 1987. ``Geometry of Numbers'', North-Holland, Amsterdam, 2nd ed. .LI Lagarias, J.\ C. 1996. ``Point lattices,'' in \f2Handbook of Combinatorics\f1, ed. R. L. Graham et al., North-Holland, Amsterdam, 1996, pp. 919-966. .LI Lenstra, A.\ K., Lenstra, H.\ W.\ Jr. & Lova\*'sz, L. 1982. ``Factoring polynomials with rational coefficients,'' Math. Ann. \f3261\f1, 515-534. .LI Ryskov, S.\ S. 1972. ``Maximal finite groups of integral $n^times^n$ matrices and full groups of integral automorphisms of positive quadratic forms (Bravais models)'' (in Russian), Trudy Mat. Inst. V.\ A. Steklova, \f3128\f1, 183-211. English translation in Proc. Steklov Inst. Math., \f3128\f1 (1972), 217-250. .LI Ryskov, S.\ S. and Baranovskii, E.\ P. 1976. ``$C$-types of $n$-dimensional lattices and 5-dimensional primitive parallelohedra (with application to the theory of covering)'' (in Russian), Trudy Mat. Inst. V.\ A. Steklova, \f3137\f1. English translation in Proc. Steklov Inst. Math., Issue 4, 1978. .LI Ryskov, S.\ S. and Baranovskii, E.\ P. 1979. ``Classical methods in the theory of lattice packings'' (in Russian), Uspekhi Mat. Nauk \f334\f1, No.\ 4, 3-63. English translation in Russian Math. Surveys \f334\f1 (No.\ 4, 1979), 1-68. .LI Selling, E. 1874. ``Ueber die bina\*:ren und terna\*:ren quadratischen Formen,'' J. Reine Angew. Math., \f377\f1, 143-229. .LI Stogrin, M.\ I. 1973. ``Regular Dirichlet-Voronoi partitions for the second triclinic group'' (in Russian), Trudy Math. Inst. V.\ A. Steklova, No.\ 123. English translation in Proc. Steklov Inst. Math., No.\ 123 (1973). .LI Venkov, B.\ B. 1983. ``Voronoi parallelohedra for certain unimodular lattices'' (in Russian), Zap. Nauch. Sem. Leningrad. Otdel. Mat. Inst. V.\ A. Steklova, \f3132\f1 (1983), 57-61. English translation in J. Soviet Math., \f330\f1 (1985), 1833-1836. .LI Voronoi, G.\ F. 1908-1909. ``Nouvelles applications des parame\*`tres continus a\*` la the\*'orie des formes quadratiques,'' J. Reine Ang. Math., \f3133\f1, 97-178; \f3134\f1, 198-287; \f3136\f1, 67-181. .LE .PH "" .bp .ce .B "Figure Captions" .sp 2 .DF .fi Figure\ 1. Voronoi cells (heavy lines) of 2-dimensional lattices. (a)\ If $ps 12 ne 0$ there are three pairs $+- vs 0$, $+- vs 1$, $+- vs 2$ of Voronoi vectors, all strict, and the cell is a hexagon. (b)\ If $ps 12 =0$ there are four pairs $+- vs 1$, $+- vs 2$, $+- ( vs 1 + vs 2 )$, $+- ( vs 1 - vs 2 )$ of Voronoi vectors, but only $+- vs 1$, $+- vs 2$ are strict, and the cell is a rectangle. .sp .DE .DS .fi Figure\ 2. Two dual projective planes. The lines $roman {A,^B,^dd ,^G}$ of vonorm space (a) correspond to the points of conorm space (b). .DE .DF .fi Figure\ 3. (a)\ Projective plane labeled with putative vonorms; (b)\ dual plane labeled with putative conorms. .sp .25 .DE .DF .ce Figure\ 4. Putative vonorms\ (a) and conorms\ (b) for superbase adjacent to that described by Fig.\ 3. .sp .DE .DF .fi Figure\ 5. Illustration of algorithm for Voronoi reduction of three-dimensional lattice. Figure (f), which gives the conorms corresponding to an obtuse superbase, is the final answer. .sp .DE .DS Figure\ 6. Voronoi cell for generic three-dimensional lattice. .DE .DS .fi Figure\ 7. The five parallelohedra (top), together with conorms (middle) and Delone graphs (bottom) for the corresponding lattices. .DE .DS .fi Figure\ 8. Conorms (multiplied by $det ^LA$) for $LA sst$, where $LA$ is defined by the conorms in Fig.\ 3(b). .DE .DS .ce The figures themselves will be found in separate jpg files .DE