Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 40 (1999), No. 2, 331-342.

On the Boundary of an Extremal Body

Ákos G. Horváth^{∗}

Budapesti Muszaki Egyetem, Geometria Tanszeke Egry J. u. 1, H–1521 Budapest XI, Hungary

Abstract. In this paper we shall investigate the boundary of an extremal body K. Using the characterization of the extremal bodies proved by Venkov and McMullen (Theorem 1) we give two theorems (Theorems 4, 5) determining the relative position of the lattice vectors on the boundary of K. These statements are analogues of Theorem 2 and Theorem 3 proved for Dirichlet-Voronoi cells in [5]. In the third pharagraph we investigate the connection between the simplicity of a face and the property that it contains lattice points in its relative interior (Theorems 6, 7, 8).

1. Introduction

This section contains a short survey of the results connecting to the theory of Dirichlet-Voronoi cells and extremal bodies. Other interesting results related to this theme can be found in Gruber’s survey article on Geometry of Numbers in [6]. Theorems 1–3 were proved in papers [13], [9], [5], respectively. Theorems 4–8 contain the new results of this paper.

A lattice L of the Euclidean n-space E^{n} is defined as the set of all integer linear combinations of the elements of a basis of E^{n}. The vector m is a minimal one if it is one of the shortest non-zero vectors of L. (The length of a vector is considered with respect to the usual Euclidean norm of E^{n}.) The Dirichlet-Voronoi cell (briefly D-V cell) D(x) of a lattice point x is the collection of those points of the space which are not farther to x than to any other point of the lattice. It is clear from the definition above that L is invariant under the translations by the lattice vectors, and the reflections in a lattice point or in the midpoint of any lattice segment, respectively. From this immediately follows that any two D-V cells are translated copies of each other and, moreover, any cell and its (n − 1)-dimensional faces (called facets) are centrally symmetric convex sets, respectively. The definition of D(0) implies (using the fact that a lattice is a discrete point system) that it is a polyhedron defined as a finite intersection of certain half-spaces each of which contains the origin and is bounded by the midhyperplane of a lattice segment connecting the origin with a lattice point. The collection of the cells D(x) for x ∈ L forms a so-called lattice tiling of the space E^{n}. Tiling means that their union covers the space and their interiors are mutually disjoint. This tiling is face-to-face, so in particular, any facet of the tile D(x) is also a facet of another tile. It is obvious that the D-V cell D is bounded and we assume in this paper that D also is closed, so this region is compact. The volume of D is equal to the volume of a basic parallelepiped of L which is spanned by the vectors of a basis of the lattice, v(D) = | det L|. Minkowski proved in [10] that a (bounded) centrally symmetric convex body K in E^{n} with centre at the origin 0 and volume v(K) > 2^{n}v(D) contains at least one lattice point different from 0. From this theorem immediately follows that a 0-symmetric convex body which does not contain nonzero lattice points in its interior has a volume at most 2^{n}v(D). He introduced the concept of an extremal body with respect to the lattice L. This is an 0-symmetric (closed) convex body which does not contain non-zero lattice points in its interior and has volume 2^{n}v(D) . An important example is 2D, where D is the D-V cell of L. He investigated this class of bodies and proved some interesting theorems on it. First of all he characterized the elements of this class as follows ([11]): The 0-symmetric (bounded) convex body K is extremal if and only if the following two properties hold:

∗Supported by Hung.Nat.Found for Sci. Reseaerch (OTKA) grant no.T020498 (1996)

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1999 Heldermann Verlag

a. The space E^{n} is covered by the bodies \frac{1}{2}K + u where u ∈ L.

b. Each point x ∈ E^{n} belongs to at most one body \frac{1}{2}intK + u, where intK means the interior of the body K. (\frac{1}{2}K + L is a tiling of the n-space.)

Secondly he proved in [12] that if the body K is an extremal one (with respect to a lattice L) then K satisfies the conditions:

1. K is a polytope.

2. K is centrally symmetric.

3. Each facet of K is centrally symmetric.

Finally in [12] he showed that for an extremal body some important properties hold. He proved that at most 2(2^{n} − 1) lattice points belong to the relative interiors of the facets of the body K, it has at most 2(2^{n} − 1) facets, on the boundary of K there lie at least 2(2^{n} − 1) lattice points and the relative interiors of the facets of K contain lattice points.

In his works [14] and [15] G. F. Voronoi also studies this class of polyhedra. He introduced the concept of parallelohedron as a convex polyhedron P whose translates by a lattice L cover E^{n} and they have disjoint interiors. So a polyhedron P is a parallelohedron if and only if 2P is extremal with respect to a lattice L. It is clear that e.g. the D-V cell D of the lattice L is a parallelohedron.

Later B. A. Venkov [13] and P. McMullen [9] independently examined the class of those polyhedra whose translates cover E^{n} and have disjoint interiors. They introduced the concept of a belt of facets of such a polytope. This can be defined in the following way: If G is an (n−2)-face of K, then G lies in two facets of K, say F and F′. Since F is centrally symmetric, it has an (n − 2)-face G′ opposite to G, which is the intersection of F′ with another facet F′′, say. Going on in this way, we find a belt of facets F, F′, F′′, …, F^{(k)} = F, say, such that each F^{(i−1)} ∩ F^{(i)} is a translate of G or of −G. The following theorem ([13],[9]) characterizes the parallelohedra:

Theorem 1. (Venkov, McMullen) The conditions 1. K is a polytope,

2. K is centrally symmetric,

3. each facet of K is centrally symmetric,

4. each belt of K contains 4 or 6 facets, are necessary and sufficient for a convex body to tile E^{n} with translations.

To show that the conditions are sufficient the authors described a suitable candidate for tiling of E^{n} by translates of K. Then they proved that the given candidate is a tiling, and from the definition it was clear that it is also a face-to-face and lattice-like one. This can be given by the following simple way: if F denotes a facet of K then there is a translation vector t_{F} carrying −F into F, and the tiling is the family K of certain translates of K defined by K = {K + t | t ∈ T }, where T = {∑_{F} n_{F} t_{F} | n_{F} ∈ Z}.

G. F. Voronoi raised one of the most important questions of this area:

Is each parallelohedron an affine image of a D-V cell?

This problem is open. For dimensions n ≤ 4 this conjecture was proved by B. H. Delone [3] while in the papers [14] and [15] G. F. Voronoi showed that in the space E^{n} each parallelohedron which is the prototile of a primitive lattice tiling is an affine image of a D-V cell. (A tiling is primitive if at each vertex exactly (n+1) tiles meet.) This result was refined later on by Zitomirski (see [16]), he has shown that every (n − 2)-primitive tile has also this property. (An n-tile is (n − 2)-primitive iff each of its belts is a 6-belt.)

Now we turn to the problem of lattice points on the boundary of an extremal body. G. F. Voronoi in [14] proved that the lattice vectors ±x are the unique pair of minima of their coset with respect to the group 2L if and only if their endpoints are in the interiors of opposite facets of the body 2D. The author has generalized this result as follows:

Theorem 2. ([5]) If a lattice vector x is in the relative interior of an (n − k)-dimensional face of the body 2D (for certain k = 1, …, n − 1) then it is a minimum vector of its coset x + 2L. Conversely if the rank of the set

M_{x} := {m ∈ L | m is a minimum vector of the coset x + 2L}

is equal to k then the elements of M_{x} are in the relative interiors of certain (pairwise distinct) (n − k)-dimensional faces of 2D. Furthermore in the case of k = n the lattice vector x is a vertex of the body 2D if and only if x is a minimum vector of the coset x + 2L and the rank of M_{x} is equal to n.

Here the rank of a vector set means its dimension. The following theorem gives an algebraic relation between the lattice points lying on the boundary of 2D. The relevant of a facet F of 2D is \frac{1}{2}t_{F}, with the notation introduced after Theorem 1, for K = 2D.

Theorem 3. ([5]) Let x be a lattice point in the relative interior of an (n − k)-dimensional face Π of 2D, 1 ≤ k ≤ n. Then there are q facets of 2D (denoted by Π_{1}, ⋯, Π_{q}), each containing the face Π such that the sum of their relevants y_{1}, ⋯, y_{q} is equal to x:

x = y_{1} + … + y_{q}.

The number of these facets is not greater than k. The relevants y_{i} above are orthogonal to each other and so

x^{2} = y_{1}^{2} + … + y_{q}^{2}.

In the second paragraph we give some theorems on parallelohedra, analogous to Theorem 2 and Theorem 3 and investigate similar questions in the general case. In the third paragraph we introduce the concept of weak simplicity of a face of a parallelohedron and investigate the boundary complex of the parallelohedron on the base of this property. We can see in this chapter some interesting examples illustrating the strange possibilities.

2. Lattice points on the boundary of the extremal body K.

From now on K will denote an extremal body with respect to some lattice, and L will denote one of these lattices, namely the one described after Theorem 1, when we apply Theorem 1 to the body \frac{1}{2}K rather than K. Denote by Π_{k} a k-dimensional face of K (k = 0, 1, …, n−1). The following simple lemma is possibly folklore. As it is important for our results, we give a short proof.

Lemma 1. If the face Π_{k} contains a lattice point x in its relative interior, then Π_{k} is centrally symmetric with the lattice point as center.

Proof. Consider the parallelohedron \frac{1}{2}K as a tile of the lattice tiling with lattice L. The midpoint P of the segment [0, x] is a center of symmetry of this face-to-face tiling. This means that the reflection in P interchanges the parallelohedra \frac{1}{2}K and \frac{1}{2}K + x and the kfaces \frac{1}{2}Π_{k} and −\frac{1}{2}Π_{k} + x of these polyhedra containing the fixed point P in their relative interiors, respectively. Since the tiling is face-to-face we have that

\frac{1}{2}Π_{k} = −\frac{1}{2}Π_{k} + x

which proves the statement. □

Corollary 1. If the common face of the parallelohedra \frac{1}{2}K and \frac{1}{2}K + x is the k-face \frac{1}{2}Π_{k}, 0 ≤ k ≤ (n − 1), then \frac{1}{2}Π_{k} is centrally symmetric with the center \frac{1}{2}x.

Proof. In fact, the reflection in \frac{1}{2}x shows that \frac{1}{2}x is a common boundary point of the bodies \frac{1}{2}K and \frac{1}{2}K + x (it is the center of the convex hull of the faces \frac{1}{2}Π_{k} and its reflected image in \frac{1}{2}x), so by the above lemma the statement follows. □

Corollary 2. There are no three distinct parallelohedra \frac{1}{2}K + u, \frac{1}{2}K + v and \frac{1}{2}K + w having a common point for which the following property holds:

(\frac{1}{2}K + u) ∩ (\frac{1}{2}K + v) = (\frac{1}{2}K + u) ∩ (\frac{1}{2}K + w).

Proof. Using Corollary 1, the first equality means that \frac{1}{2}(v − u) = \frac{1}{2}(w − u) thus v = w. □

Now we prove the generalization of the first statement of Theorem 3 for extremal bodies. Let Π^{i} be a facet of \frac{1}{2}K. Denote by y_{i} the lattice vector whose midpoint is the center of Π^{i} and let a_{i} be an outer normal vector of the facet Π^{i}.

Theorem 4. Let x be a lattice point in the relative interior of an (n − k)-dimensional face Π_{(n−k)} of K, 1 ≤ k ≤ n. Then there are q facets of K (denoted by Π^{1}, ⋯, Π^{q}) each containing the face Π_{(n−k)} such that the sum of the corresponding relevant outer lattice vectors y_{1}, ⋯, y_{q} is equal to x:

x = y_{1} + … + y_{q}.

The number of these facets is not greater than k. Finally, the matrix

[a_{i} · y_{j}]_{i,j=1}^{q}

given by the normal vectors a_{i} corresponding to the facet Π^{i} is a positive definite diagonal matrix.

Proof. We may suppose k > 1. From the convexity and extremality of K it is obvious that if u and v are two lattice points on the boundary of K and the vector \frac{u+v}{2} ≠ 0 is a lattice vector then it is also on the boundary of K. Let now y_{1} be a lattice vector pointing to the center of an (n − 1)-dimensional facet Π^{1} of K containing Π_{(n−k)}. Since Π_{(n−k)} ⊂ Π^{1} and the translation through −y_{1} takes the parallelohedron \frac{1}{2}K + y_{1} into \frac{1}{2}K, we see that the polyhedron \frac{1}{2}Π_{(n−k)} − y_{1} is an (n − k)-face of \frac{1}{2}K. By Lemma 1 the face \frac{1}{2}Π_{(n−k)} is centrally symmetric with center \frac{1}{2}x, so its above translated copy is also centrally symmetric, with center \frac{1}{2}x − y_{1}. This means that the lattice point x − 2y_{1} is also on the boundary of K. Since evidently x ≠ y_{1} the vector

\frac{(x − 2y_{1}) + x}{2} = x − y_{1}

is a lattice vector lying on the boundary of K, too. Then the intersection Π = \frac{1}{2}K + (x − y_{1}) ∩ \frac{1}{2}K, that is a face of \frac{1}{2}K, contains the faces \frac{1}{2}Π_{(n−k)}, \frac{1}{2}Π_{(n−k)} − y_{1}, so dimΠ > (n − k). So for a y_{1} as above, x is the sum of the vectors y_{1} and x − y_{1}, where the second vector is the center of a face of dimension greater than (n − k). Since a facet containing this new face also contains \frac{1}{2}Π_{(n−k)} the first two statements of the theorem related to the decomposition are easy to prove by induction.

For the proof of the last statement we note that the scalar products a_{i}·y_{j} are not negative for each pair of indices since the corresponding facets Π^{i}, Π^{j} of K contain the face Π_{(n−k)}. In fact, for i = j this is evident. On the other hand, if i ≠ j, Π^{j} is contained in the parallel strip bounded by the hyperplanes spanned by Π^{i}, −Π^{i}. Let H_{i} be the mid-hyperplane of this strip. Then the halfspace, bounded by this hyperplane H_{i} and containing the face Π_{(n−k)}, contains the centers of all those facets which have Π_{(n−k)} as a face. If now

x = y_{1} + … + y_{q},

then for every index, i = 1, …, q we have the equality

0 = a_{i} · (x − y_{i}) = ∑_{{j=1 \atop j≠i}} a_{i} · y_{j}

which means that for each pair of indices i, j = 1, …, q, i ≠ j we have

a_{i} · y_{j} = 0.

Since the hyperplanes of the facets do not contain the origin we also have the inequalities:

a_{i} · x = a_{i} · y_{i} > 0.  □

Remark 1. We note that for each index i = 1, …, q we have

a_{i} · x = a_{i} · y_{i}.

Thus we have the equality

(∑_{I} a_{i}) · x = ∑_{I} a_{i} · x = ∑_{I} a_{i} · y_{i},

which holds for all sets I of indices of the facets containing the face Π_{(n−k)}.

Definition 1. We say that the lattice vector x is a K-short vector if the lattice point x is either in the relative interior of an (n − k)-dimensional face of the body K (for certain k = 1, …, n − 1) or it is a vertex of K (equivalently: x belongs to the boundary of K).

H. Minkowski proved (see [7]) that every non-zero congruence class in L/2L contains at least one pair of K-short vectors. We are now interested in the connection between the K-short vectors of a congruence class and the corresponding faces of K.

Theorem 5. Let x be a K-short vector and M_{x} be the set

M_{x} := {m ∈ L | m is a K-short vector of the coset x + 2L}.

Then the faces corresponding to the elements of M_{x} (i.e., that contain them in their relative interiors) are translates of each other. They have the same dimension, say (n − k). The rank of M_{x} is at least k.

Proof. Let x and y be two K-short vectors in the same congruence class. So x = y + 2z where the lattice vector z is not zero. Let Π_{x} and Π_{y} denote those faces of K whose relative interiors contain x and y, respectively, and therefore whose centers are x and y, respectively. Then the translation through the lattice vector z takes the center of the face \frac{1}{2}Π_{y} to the center of the face \frac{1}{2}Π_{x}. But a translation through a lattice vector leaves the tiling invariant, so if a face of the tiling and the translate of another face have a common relative interior point then they coincide. This means that

\frac{1}{2}Π_{y} + z = \frac{1}{2}Π_{x}

and the first statement is proved.

For the proof of the second statement we note that for x ∈ relintΠ_{(n−k)} the relevant vectors y_{i}, i ∈ I, of the facets Π^{i} containing the face Π_{(n−k)} are in the set \frac{1}{2}(x − M_{x}). In fact, this is equivalent to 2y_{i} − x ∈ M_{x}, which in turn follows from the fact that y_{i} is the center of symmetry of Π^{i}. By 0-symmetry of M_{x} ≠ the rank of \frac{1}{2}(x − M_{x}) is equal to the rank of M_{x}, so

rank{y_{i} | i ∈ I} ≤ rankM_{x}.

Since it is obvious that for the (n − k)-face Π_{(n−k)} the rank{y_{i} | i ∈ I} is not less than k, the statement is true. □

Remark 2. We have seen that the rank of the vector set M_{x} is at least k. We assert that for double D-V cells it is equal to k. To show this, first we observe that if D is the D-V cell of 0 with respect to a lattice L′, then the lattice L constructed after Theorem 1 for the body D coincides with L′. In fact, if Π^{i} is a facet of D, P^{i} the reflection of 0 in aff Π^{i}, then P^{i} ∈ L′. (aff Π^{i} denotes the affine hull of Π^{i}). Since the reflection in \frac{1}{2}P^{i} is a symmetry of the lattice L′, Π^{i} is symmetric with respect to \frac{1}{2}P^{i} as well. So each above P^{i} is the mirror image of 0 in the center of symmetry of Π^{i}, showing L′ ⊂ L. Then |detL′| = v(D) = |detL| shows L′ = L. By the above shown inclusion

{y_{i} | i ∈ I} =

\{y_{i} | y_{i} is the relevant vector of a facet Π^{i} of D, containing Π_{(n−k)}\} ⊂ \frac{1}{2}(x − M_{x}),

and orthogonality of y_{i} to Π^{i} (that follows from the above considerations) we have rankM_{x} = rank(\frac{1}{2}(x − M_{x})) ≥ rank\{y_{i} | i ∈ I\} ≥ k. On the other hand, by Theorem 3 x is orthogonal to aff Π_{(n−k)}, and then by Theorem 5 each y ∈ M_{x} is orthogonal to a translate of aff Π_{(n−k)}, i.e., to aff Π_{(n−k)}. Therefore each \frac{1}{2}(x − y), where y ∈ M_{x}, lies in a k-subspace, so rankM_{x} ≤ k, and therefore rankM_{x} = k. Since an affinity is a linear mapping, for a Voronoi parallelohedron (which is an affine image of a D-V cell) this number is also k. This motivates the conjecture that in all cases the rank of M_{x} is equal to k. In fact, a counterexample for this conjecture is also a counterexample for the Voronoi conjecture.

Now we introduce the concept of dual polyhedron strongly connected to this problem.

Definition 2. Let an (n − k)-face be \frac{1}{2}Π_{(n−k)} with the center \frac{1}{2}x, where x ∈ L \ \{0\}. Define for each elements y ∈ M_{x} the translated copy \frac{1}{2}K + z = \frac{1}{2}K + \frac{x−y}{2} of \frac{1}{2}K. The convex hull of the centers of these parallelohedra (i.e., of the points \frac{x−y}{2}) is a centrally symmetric convex polyhedron P (\frac{1}{2}Π_{(n−k)}) , that we call the dual of \frac{1}{2}Π_{(n−k)} with respect to the tiling.

On the structure of the dual polyhedron of a face containing a lattice point \frac{1}{2}x we have a nice observation. By a diagonal of a convex polyhedron we mean any segment joining two of its vertices.

Theorem 6. The vertices of P (\frac{1}{2}Π_{(n−k)}) are the centers of those parallelohedra from the body lattice L + \frac{1}{2}K, that contain \frac{1}{2}Π_{(n−k)}. The center of each diagonal of P (\frac{1}{2}Π_{(n−k)}) is the center of some (proper or trivial) face of P (\frac{1}{2}Π_{(n−k)}), containing the diagonal in question.

Proof. Let x be a K-short vector, and y ∈ M_{x}. Then \frac{1}{2}x is in the relative interior of a face \frac{1}{2}Π_{(n−k)}, hence is the centre of it. Thus z = \frac{1}{2}(x − y) ∈ P (\frac{1}{2}Π_{(n−k)}) = conv\{\frac{1}{2}(x − y_{i}) | y_{i} ∈ M_{x}\}. We assert that z is a vertex of P (\frac{1}{2}Π_{(n−k)}). In fact, y ∈ conv\{y_{i} | y_{i} ∈ M_{x}\}, and it suffices to show that y is a vertex of conv{y_{i} | y_{i} ∈ M_{x}}. Since the faces containing the points y_{i} ∈ M_{x} in their relative interiors are translates of each other, the projection of the points y_{i} ∈ M_{x} to the linear k-subspace orthogonal to Π_{(n−k)} are vertices of the projection of conv{y_{i} | y_{i} ∈ M_{x}}. If y were not a vertex of conv{y_{i} | y_{i} ∈ M_{x}}, then y would be a convex combination of the other y_{i}. Hence the projection of y would be a convex combination of the projections of the other y_{i} which is impossible, since they are vertices of the projection.

It remains to show that, for a lattice vector v ∈ L, the properties \frac{1}{2}K + v ⊃ \frac{1}{2}Π_{(n−k)}, and v = \frac{1}{2}(x − y), for some y ∈ M_{x}, are equivalent. The cell decomposition property of the lattice tiling \frac{1}{2}K + L implies that \frac{1}{2}K + v ⊃ \frac{1}{2}Π_{(n−k)} is equivalent to \frac{1}{2}x ∈ \frac{1}{2}K + v. If now v = \frac{1}{2}(x − y), for some y ∈ M_{x}, then \frac{1}{2}K + v = \frac{1}{2}K + \frac{1}{2}(x − y) ∋ \frac{1}{2}x follows from K ⊃ M_{x} ∋ y. Conversely, let \frac{1}{2}K + v ∋ \frac{1}{2}x. Then v = \frac{1}{2}(x − y) with y ∈ E^{n}, and v ∈ L implies y ∈ x + 2L. To show y ∈ M_{x} still we have to show that y is a K-short vector. We have

\frac{1}{2}K + v = \frac{1}{2}K + \frac{1}{2}(x − y) ∋ \frac{1}{2}x,

hence K ∋ y. We have y ≠ 0, since else x ∈ 2L and thus x cannot be a K-short vector. Therefore y ∈ bdK, thus y is a K-short vector, hence y ∈ M_{x}. This ends the proof of the first statement.

For the second statement about P (\frac{1}{2}Π_{(n−k)}) it is sufficient to prove its analogue for conv\{M_{x}\}. Let yz be a diagonal of conv{M_{x}}. If y + z = 0, we have the trivial face conv{M_{x}}, that is symmetric with respect to 0, and contains the diagonal yz. For y + z ≠ 0 we have L ∋ \frac{1}{2}(y + z) ≠ 0, hence \frac{1}{2}(y + z) ∈ bdK, and then by Lemma 1 the face containing \frac{1}{2}(y + z) in its relative interior is symmetric with respect to \frac{1}{2}(y + z), and evidently contains both y and z. □

Remark 3. In the two dimensional case we have two types of polygons having the second property of Theorem 6. These are the triangles and the parallelograms. The class of such polyhedra will be called weakly-neighbourly polyhedra because it is clear that for example the simplices, parallelotopes, cross-polytopes and 1-neighbourly polytopes are polyhedra having this property. It is easy to see that all the faces of a weakly-neighbourly polyhedron are also weakly-neighbourly, and the pyramids and the central symmetric bipyramids over an (n−1)- dimensional weakly-neighbourly polyhedron are weakly-neighbourly, too. The combinatorial classification problem of these polyhedra may be interesting (also in the 3-space).

3. On the simplicity

The following definition was introduced by G. F. Voronoi.

Definition 3. ([14]) The k-face F of the parallelohedron \frac{1}{2}K is simple if it is a face of precisely n − k + 1 translated copies of \frac{1}{2}K in the lattice tiling described after Theorem 1, where \frac{1}{2}K is always counted as a translated copy of itself.

It is well-known ([7]) that if the face F is simple, then each pair of parallelohedra containing F has a common facet. The author does not know whether or not this latter condition implies the simplicity. If we omit the requirement that \frac{1}{2}K is a parallelohedron we can formulate the following question: what is the maximal number of centrally symmetric convex polyhedra such that

1. they are translated copies of each other,

2. their interiors are mutually disjoint,

3. each two have a common facet and

4. all of them have a common (lower dimensional) k-face (in particular have a common point).

The set of homologous points of such a family is a so-called strictly antipodal set (see [8] 3,iii.), i.e. for any two points s_{i}, s_{j} of this set, say S, there exist different parallel supporting hyperplanes H_{ij}, H_{ji} of the convex hull of this set, such that S ∩ H_{ij} = {s_{i}}, S ∩ H_{ji} = {s_{j}} (actually 1,2,3, suffice for this property). From a strictly antipodal set one can construct a family of centrally symmetric convex polyhedra fulfilling the first and second conditions if it still satisfies the condition that the intersection of the hyperplanes parallel to the support hyperplanes H_{ij} and containing the corresponding midpoint \frac{1}{2}(s_{i} + s_{j}) of the connecting segment is not empty. In fact, the polyhedral cones K_{C}^{+} with this common point O as vertex bounded by the midhyperplanes of the segments having a common point C of the strictly antipodal set can be translated into a fix point C^{∗} through the vectors CC^{∗}, respectively. The intersection of these translated copies is a centrally symmetric convex body fulfilling the conditions above. In [4] we can find such a strictly antipodal point set whose cardinality is an exponential function of the dimension n. This set contains certain vertices of an ndimensional cube, the corresponding support hyperplanes are orthogonal to the connecting segments so the corresponding family of bodies fulfils all of our conditions (with k = 0). (However we cannot check whether it is a parallelohedron or not.) The above facts motivate the following definition.

Definition 4. The k-face \frac{1}{2}F of \frac{1}{2}K is weakly simple if each pair of parallelohedra in the above lattice tiling of \frac{1}{2}K containing \frac{1}{2}F, has a common facet.

Next we define the concept of dual polyhedron for all faces of \frac{1}{2}K. Observe that, by Theorem 6, when Π is symmetric with respect to a nonzero lattice vector x, then this definition reduces to Definition 2. The definition is the following:

Definition 5. Let \frac{1}{2}K be a parallelohedron and let \frac{1}{2}Π a face of it of dimension r. Let P (\frac{1}{2}Π) denote the convex hull of the centers of those parallelohedra in the lattice tiling \frac{1}{2}K + L of \frac{1}{2}K, that contain the face \frac{1}{2}Π.

We note that if the dual polyhedron P (\frac{1}{2}Π) of a simple k-face \frac{1}{2}Π is n − k-dimensional then it is an (n − k)-simplex.

The following theorem contains the basic properties of weak simplicity.

Theorem 7. If the k-face \frac{1}{2}F of \frac{1}{2}K, 0 ≤ k ≤ n − 1, is weakly simple then 1. all faces containing \frac{1}{2}F are also weakly simple,

2. the vertex set of the dual polyhedron P (\frac{1}{2}F) is the collection of the centers of those parallelohedra in the lattice tiling of \frac{1}{2}K that contain \frac{1}{2}F,

3. the relative interior of \frac{1}{2}F does not contain any lattice midpoint if k ≤ n − 2.

4. If the k-face \frac{1}{2}G is maximal (with respect to inclusion) non-weakly-simple, then it contains a lattice midpoint in its relative interior.

Proof. The first statement is an easy consequence of the definition using the fact that if \frac{1}{2}G ⊃ \frac{1}{2}F, then the set of parallelohedra containing \frac{1}{2}G is a subset of the set of parallelohedra containing F.

The second statement is a consequence of the fact that vertP (\frac{1}{2}F) is a strictly antipodal set (see [8] 3,iii). In fact, for a strictly antipodal set S = {s_{1}, …, s_{m}}, for any s_{i} there is a supporting hyperplane H of convS, such that H ∩ convS = s_{i} showing that s_{i} is an extremal point, i.e. a vertex of convS.

The proof of the third statement is the following. Let \frac{1}{2}F be a weakly-simple k-face and \frac{1}{2}v be a lattice vector in its relative interior. Let k < n − 1, then \frac{1}{2}F is centrally symmetric with center \frac{1}{2}v by Lemma 1. This means that the intersection of the parallelohedra \frac{1}{2}K and \frac{1}{2}K + v is \frac{1}{2}F which is a contradiction to the weak simplicity.

The fourth statement follows from the fact that if \frac{1}{2}F is not weakly simple then there are two parallelohedra containing it and having as intersection a common l-face \frac{1}{2}G with k ≤ l < n − 1. Using Corollary 1 we get that \frac{1}{2}G is a face containing in its interior a half lattice vector, which means by the previous property that it is non-weakly-simple. But \frac{1}{2}F is maximal (with respect to inclusion) so \frac{1}{2}G = \frac{1}{2}F which ends the proof. □

Remark 4. In 3-space we can give a simple example of a non-trivial maximal non-weakly-simple face. Those vertices of the rhombic dodecahedron (that is the D-V cell of the 3dimensional regular simplex lattice A_{3}) which are halves of certain lattice vectors are nonweakly-simple faces while all of the edges are simple (and so weakly-simple) faces. So these vertices are 0-dimensional maximal non-weakly-simple faces.

Remark 5. By the above theorem we have the following situation.

1. If a face F of K is weakly-simple and dimF ≤ n − 2 then it does not contain a lattice point in its relative interior.

2. If F is maximal non-weakly-simple (all the faces containing it are weakly-simple) then there is a lattice point belonging to its relative interior.

3. If F is non-weakly-simple but not a maximal non-weakly-simple one then each of the two above possibilities can occur. In the case of the cube each face contains a lattice point in its relative interior and the faces of dimension k < n−2 are non-weakly-simple and not maximal ones, on the other hand in the case of 3-dimensional hexagonal prisms the edges of the hexagons are maximal non-weakly-simple faces and the vertices are also non-weakly-simple (but not maximal) ones and they are not lattice points with respect to the corresponding lattice-like face-to-face tiling of K.

Theorem 8. The vertices of P (\frac{1}{2}Π) are the collection of the centers of those parallelohedra which contain \frac{1}{2}Π.

Proof. Let S(\frac{1}{2}Π) denote the set of centers of those parallelohedra in the lattice tiling \frac{1}{2}K +L, that contain the face \frac{1}{2}Π. We have to show that each s ∈ S(\frac{1}{2}Π) is an extremal point of P (\frac{1}{2}Π). Since for \frac{1}{2}Π_{1} ⊂ \frac{1}{2}Π_{2} we have S(\frac{1}{2}Π_{1}) ⊃ S(\frac{1}{2}Π_{2}), it suffices to show this for \frac{1}{2}Π = \frac{1}{2}v a vertex. Evidently it suffices to show that each −s ∈ −S is an extremal point of −P (\frac{1}{2}v), i.e. −s+ \frac{1}{2}v is an extremal point of −P (\frac{1}{2}v) + \frac{1}{2}v. However −s + \frac{1}{2}v ∈ \frac{1}{2}K + \frac{1}{2}v, and is a vertex of it, hence is a vertex of conv\{−s_{i} + \frac{1}{2}v|s_{i} ∈ S\} = −P (\frac{1}{2}v) + \frac{1}{2}v. □

Remark 6. It is obvious that, if F ⊂ G, then P (F) ⊃ P (G), so the dual polyhedra of the vertices of the tiling contain (as certain subset) the dual of any other face of the tiling. In the case of D-V cells the dual polyhedra of the vertices, that are n-dimensional polyhedra, are the elements of the so-called L-tiling, they are the L-tiles. By applying an affinity we have that, when K is a Voronoi parallelohedron (i.e., an affine image of a D-V cell), then the system of dual polyhedra of the vertices gives another (face-to-face) tiling of the n-space, that is called the dual tiling of the space with respect to the tiling determined by the parallelohedron \frac{1}{2}K. P. McMullen in [9] proved that any two parallelohedra, in the lattice packing \frac{1}{2}K + L of any parallelohedron \frac{1}{2}K, can be connected with a chain of contiguous parallelohedra of this collection (two of these parallelohedra are contiguous, if they have a common facet). Thus we also would have a counter-example for the Voronoi conjecture if we had a parallelohedron with an edge E, for which dim P (E) ≠ n − 1.

References

[1] Delone, B. N.: Geometry of positive quadratic forms I. Uspekhi Mat. Nauk 3 (1937), 16–62. (Russian)

[2] Delone, B. N.: Geometry of positive quadratic forms II. Uspehhi Mat. Nauk 4 (1938), 102–164. (Russian)

[3] Delone, B. N.: Sur la partition réguliére de l’espace á 4 dimensions. Izv. Akad. Nauk SSSR, Otdel. Fiz.-Mat. Nauk 7 (1929), 79–110, 147–164.

[4] Erdös, P.; Füredi, Z. F.: The greatest angle among n points in the d-dimensional Euclidean space. Combinatorial Math. (Proc. Internat. Colloq. Graph Theory Combin., Marseille-Luminy, 1981). North-Holland Math. Stud. 75 North-Holland, Amsterdam-New York, (1983); Ann. Discrete Math. 17.

[5] Horváth, Á. G.: On the DIRICHLET-VORONOI cell of unimodular lattices. Geom. Dedicata 63 (1996), 183–191.

[6] Gruber, P. M.; Wills, J. M. (Hrsg.): Handbook of Convex Geometry. Volume B, North Holland, Amsterdam 1993.

[7] Gruber, P. M.; Lekkerkerker, C. G.: Geometry of numbers. North-Holland, Amsterdam-New York-Oxford-Tokyo 1987.

[8] Grünbaum, B.: Strictly antipodal sets. Israel J. Math. 1 (1963), 5–10.

[9] McMullen, P.: Convex bodies which tile space by translation. Mathematika 27 (1980), 113–121.

[10] Minkowski, H.: Über die positiven quadratischen Formen und über kettenbruchähnliche Algorithmen. Ges. Abh. I, 243–260.

[11] Minkowski, H.: Geometrie der Zahlen. Leipzig und Berlin 1910.

[12] Minkowski, H.: Allgemeine Lehrsätze über konvexe Polyeder. Nachr. K. Akad. Wiss. Göttingen, Math.–Phys. Kl. ii (1897), 198–219.

[13] Venkov, B. A.: On a class of Euclidean polytopes (in Russian). Vestnik Leningrad. Univ. (Ser. Mat. Fiz. Him.) 9 (1954), 11–31.

[14] Voronoï, G. F.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. J. Reine Angew. Math. 134 (1908), 198–287.

[15] Voronoï, G. F.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques II. J. Reine Angew. Math. 136 (1909), 67–181.

[16] Zhitomirskii, O. K.: Verschärfung eines Satzes von Voronoi. Leningr. fiz.-mat. Obshch. 2 (1929), 131–151.

Received December 29, 1997; revised version February 20, 1998