Number Theory: An Introduction to Mathematics

344 VIII The Geometry of Numbers

In the representation (3) it may be possible to omit some closed half-spacesG ̄xi
without affecting the validity of the representation. By omitting as many half-spaces as
possible we obtain anirredundant representation, which by suitable choice of notation
we may take to be

V(x 0 )=

l

∩

i= 1

G ̄xi

for somel≤m. The intersectionsV(x 0 )∩Hxi( 1 ≤i≤l)are then the distinct facets
ofV(x 0 ). Any nonempty proper face ofV(x 0 )is contained in a facet and is the inter-
section of those facets which containit. Furthermore, any nonempty face ofV(x 0 )is
the convex hull of those vertices ofV(x 0 )which it contains.
It follows that for eachxi( 1 ≤i≤l)there is a vertexviofV(x 0 )such that

d(x 0 ,vi)=d(xi,vi).

For d(x 0 ,v)≤d(xi,v)for every vertexvofV(x 0 ). Assume that d(x 0 ,v)<d(xi,v)
for every vertexvofV(x 0 ). Then the open half-spaceGxicontains all verticesvand
hence also their convex hullV(x 0 ). But this is a contradiction, sinceV(x 0 )∩Hxiis a
facet ofV(x 0 ).
To illustrate these results take X =Znandx 0 = O. Then the Voronoi cell
V(O)is the cube consisting of all pointsy=(η 1 ,...,ηn)∈Rnwith|ηi|≤ 1 / 2
(i= 1 ,...,n). It has the minimal number 2nof facets.
In fact any latticeΛinRnis discrete and has the property (†).For a latticeΛwe
can restrict attention to the Voronoi cell V(Λ):=V(O), since an arbitrary Voronoi
cell is obtained from it by a translation:V(x 0 )=V(O)+x 0. The Voronoi cell of
a lattice has extra properties. Sincex ∈ Λimplies−x ∈ Λ,y ∈ V(Λ)implies
−y∈V(Λ).Furthermore,ifxiis a lattice vector determining a facet ofV(Λ)and if
y∈V(Λ)∩Hxi,then‖y‖=‖y−xi‖.Sincex∈Λimpliesxi−x∈Λ, it follows
thaty∈V(Λ)∩Hxiimpliesxi−y∈V(Λ)∩Hxi. Thusthe Voronoi cell V(Λ)and
all its facets are centrosymmetric.
In addition, any orthogonal transformation ofRnwhich maps onto itself the lattice
Λalso maps onto itself the Voronoi cellV(Λ). Furthermore the Voronoi cellV(Λ)
has volume d(Λ), by Proposition 11, since the lattice translates ofV(Λ)form a tiling
ofRn.
We d e fi n e afacet vectoror ‘relevant vector’ of a latticeΛtobeavectorxi∈Λ
such thatV(Λ)∩Hxiis a facet of the Voronoi cellV(Λ).IfV(Λ)is contained in the
closed ballBR={x∈Rn:‖x‖≤R}, then every facet vectorxisatisfies‖xi‖≤ 2 R.
For, ify∈V(Λ)∩Hxithen, by Schwarz’s inequality (Chapter I,§4),

‖xi‖^2 = 2 (xi,y)≤ 2 ‖xi‖‖y‖.

The facet vectors were characterized by Voronoi (1908) in the following way:

Proposition 13A nonzero vector x∈Λis a facet vector of the latticeΛ⊆Rnif and
only if every vector x′∈x+ 2 Λ, except±x , satisfies‖x′‖>‖x‖.

Proof Suppose first that‖x‖<‖x′‖for allx′=±xsuch that(x′−x)/ 2 ∈Λ.If
z∈Λandx′= 2 z−x,then(x′−x)/ 2 ∈Λ. Hence ifz=O,xthen