4 Voronoi Cells 345‖x/ 2 ‖<‖z−x/ 2 ‖,i.e.x/ 2 ∈Gz.Since‖x/ 2 ‖=‖x−x/ 2 ‖, it follows thatx/ 2 ∈V(Λ)andxis a facet
vector.
Suppose next that there existsx′ =±xsuch thatw =(x′−x)/ 2 ∈Λand
‖x′‖≤‖x‖.Thenalsoz=(x′+x)/ 2 ∈Λandz,w=O.Ify∈G ̄z∩G ̄−w,then
2 (z,y)≤‖z‖^2 , − 2 (w,y)≤‖w‖^2.Hence, by the parallelogram law (Chapter I,§10),
2 (x,y)= 2 (z,y)− 2 (w,y)≤‖z‖^2 +‖w‖^2
=‖x‖^2 / 2 +‖x′‖^2 / 2 ≤‖x‖^2.That is,y∈G ̄x. ThusG ̄xis not needed to defineV(Λ)andxis not a facet vector.
Any latticeΛcontains a nonzero vector with minimal square-norm. Such a vector
will be called aminimal vector. Its square-norm will be called theminimumofΛand
will be denoted bym(Λ).
Proposition 14IfΛ⊆Rnis a lattice with minimum m(Λ), then any nonzero vector
inΛwith square-norm< 2 m(Λ)is a facet vector. In particular, any minimal vector is
a facet vector.
Proof Putr=m(Λ)and letxbe a nonzero vector inΛwith‖x‖^2 < 2 r.Ifxis not
a facet vector, there existsy=±xwith(y−x)/ 2 ∈Λsuch that‖y‖≤‖x‖.Since
(y±x)/ 2 ∈Λ,‖x±y‖^2 ≥ 4 r. Thus
4 r≤‖x‖^2 +‖y‖^2 ± 2 (x,y)< 4 r± 2 (x,y),which is impossible.
Proposition 15For any latticeΛ⊆Rn, the number of facets of its Voronoi cell V(Λ)
is at most 2 ( 2 n− 1 ).
Proof Letx 1 ,...,xnbe a basis forΛ. Then any vectorx∈Λhas a unique represen-
tationx=x′+x′′,wherex′∈ 2 Λand
x′′=α 1 x 1 +···+αnxn,withαj∈{ 0 , 1 }forj= 1 ,...,n. Thus the number of cosets of 2ΛinΛis 2n.But,
by Proposition 13, each coset contains at most one pair±yof facet vectors. Since 2Λ
itself does not contain any facet vectors,the total number of facet vectors is at most
2 ( 2 n− 1 ).
There exist latticesΛ ⊆ Rnfor which the upper bound of Proposition 15 is
attained, e.g. the latticeΛ={Tz:z∈Zn}withT =I+βJ,whereJdenotes
then×nmatrix every element of which is 1 andβ={( 1 +n)^1 /^2 − 1 }/n.
Proposition 16Every vector of a latticeΛ⊆Rnis an integral linear combination of
facet vectors.