text:
# On the number of facets of three-dimensional Dirichlet stereohedra II: Non-cubic Groups

## Introduction

This is the second in a series of three papers (see ) devoted to bound the number of facets that a Dirichlet stereohedron in 3-space can have.

A *stereohedron* in dimension $`d`$ is any convex polytope which tiles the Euclidean space $`^d`$ face-to-face under the action of a crystallographic group. A *Dirichlet stereohedron* for a crystallographic group $`G`$ is the Voronoi region $`\text{Vor}_{GP}(P)`$ of a point $`P`$ in the Voronoi diagram of the orbit $`GP`$.

Finding a good upper bound for the number of facets of $`d`$-dimensional stereohedra is mentioned as an important problem in  and , and it is related to Hilbert’s 18th problem . The most relevant previous results on this problem are:

* Delone  proved that a stereohedron of dimension $`d`$ for a certain crystallographic group $`G`$ cannot have more than $`2^d(a+1)2`$ facets, where $`a`$ is the *number of aspects* of $`G`$, i.e., the order of the quotient group of $`G`$ by its translational subgroup. In dimension 3, crystallographic groups can have up to 48 aspects, which gives an upper bound of 390 for the number of facets of 3-dimensional stereohedra. Non-cubic groups without reflections have up to 16 aspects (see Table 3), giving a bound of 134.
* The 3-dimensional stereohedron with the maximum number of facets known so far has 38 facets, and it was found by Engel (see  and \[7, p. 964\]). It is a Dirichlet stereohedron for a cubic group with 24 aspects.

Delone’s result contrasts with the fact that arbitrarily large families of non-overlapping congruent convex 3-polytopes exist in which the intersection of every two polytopes is a common facet .

The main results of this series of papers are summarized in Table 1. We divide the 219 affine conjugacy classes of 3-dimensional crystallographic groups in three blocks: Those which contain reflection planes (100 conjugacy classes) were studied in , non-cubic groups without reflections (97 classes) are the object of this paper and cubic groups without reflections (22 classes) will be studied in . Our methods provide different upper bounds on the number of facets for each group. The two columns in Table 1 show respectively the global upper bound obtained for each block of groups and the number of affine conjugacy classes of groups where our bound is greater than the number of facets of Engel’s stereohedron.

The results for groups with reflections are specially good, since the upper bound of 18 facets was proved to be tight in . For cubic groups we have indicated the results contained in , which might be slightly improved in the final writing of .

Table 2 gives a more detailed description of the results in this paper. It lists the 21 non-cubic groups where our bound is greater than 38, together with the specific bound for each group. The last column in the table indicates where in this paper the bound is proved. For some of the groups we have taken Delone’s upper bound of $`8a+6`$.

Theorem 1 Dirichlet stereohedra for non-cubic crystallographic groups in dimension 3 cannot have more than 80 faces.

They can not have more than 70 except perhaps in the groups $`R\overline{3}\frac{2}{c}`$, $`P6_122`$, $`P6_222`$ and $`I\frac{4_1}{g}\frac{2}{c}\frac{2}{d}`$. They can not have more than 50 except perhaps in these four and five other groups.

The upper bounds are proved in the following Sections, starting from more general methods to more specific ones. For example, Corollary 1.6 gives an upper bound derived from simple parameters of each group. This bound is globally 106, and it is higher than 38 in only 34 groups. The rest of the paper concentrates in the top and bottom parts of Table 2: lowering the upper bound for the bad groups in the bottom of the table and removing groups from the top of the table by showing that they cannot produce more than 38 facets.

Section 4 is essentially devoted to only one group, the group $`P6_122`$. We first lower the upper bound of 96 from Corollary 1.6 to a 78, and then show the existence of a stereohedron with 32 facets for this group (Example 4.4). This is the highest number of facets of a stereohedron for a non-cubic group obtained to date.

This example shows, on the one hand, that the general upper bound of 80 is at most 2.5 times worse than the actual maximum. And on the other hand, that non-cubic groups can produce stereohedra almost as complicated as cubic groups. It is worth noting that our construction method shows why it is natural to expect stereohedra with “many” facets for the group $`P6_122`$. In fact, Lemma 4.2 implies that any group whose name (in the International Crystallographic Notation, see ) contains the string $`i_12`$, produces Dirichlet stereohedra with at least $`4i+1`$ facets. We show a stereohedron with 29 facets for the group $`I4_122`$ (Example 4.5).

## 1. A first upper bound for each crystallographic group

All throughout the paper $`G`$ will denote a 3-dimensional crystallographic group without reflections and $`P^3`$ will be a base point for an orbit $`GP`$, so that the Dirichlet stereohedron we want to study is the (closed) Voronoi region $`\text{Vor}_{GP}(P)`$. We assume that $`P`$ has trivial stabilizer under the action of $`G`$, since otherwise $`GP`$ is also an orbit of a proper subgroup of $`G`$. Further, there is no loss of generality in assuming both $`P`$ and the metric parameters of $`G`$ (the parameters which identify $`G`$ in its affine conjugacy class of groups) to be sufficiently generic since a small perturbation to either $`P`$ or $`G`$ can only increase the number of facets in the Dirichlet stereohedron induced. We say that a point $`QGP`$ is a neighbor of $`P`$ if $`\text{Vor}_{GP}(P)`$ and $`\text{Vor}_{GP}(Q)`$ share a facet. Hence, the number of facets of $`\text{Vor}_{GP}(P)`$ equals the number of neighbors of $`P`$.

### 1.1. Outline of our method

Let $`v^3`$ be a vector such that the corresponding translation $`\tau _v`$ is in $`G`$. We will call vertical the direction of $`v`$ and horizontal the planes orthogonal to it. Let $`Z_P`$ denote the closed infinite band of width $`2|v|`$ bounded by the horizontal planes passing through $`\tau _vP`$ and $`\tau _vP`$.

###### Lemma 1.1.

All the neighbors of $`P`$ lie in $`Z_P`$. Moreover, the only points in the boundary of $`Z_P`$ which can be neighbors of $`P`$ are $`\tau _vP`$ and $`\tau _vP`$.

Proof: Let $`QGP`$. Suppose that $`Q`$ is outside $`Z_P`$ or that it is on its boundary but it equals neither $`\tau _vP`$ nor $`\tau _vP`$. Without loss of generality assume that $`PQv`$ is positive (otherwise change $`v`$ to $`v`$). Consider the points $`P^{}=\tau _vP`$ and $`Q^{}=\tau _vQ`$. The four points $`PP^{}QQ^{}`$, in this order, are the vertices of a planar quadrilateral whose angles at $`P^{}`$ and $`Q^{}`$ are greater or equal than 90 degrees. Since the four points are in $`GP`$, $`P`$ and $`Q`$ cannot be neighbors. ∎

In $`Z_P`$ there are only a finite family $`\alpha _1,\mathrm{},\alpha _k`$ of horizontal planes containing points of $`GP`$. Our method consists on bounding the number of neighbors of $`P`$ in each $`\alpha _i`$ separately and using the sum of the numbers obtained as a bound for the total number of neighbors. In all cases of interest to us the direction will be chosen so that the subgroup $`G_0`$ of $`G`$ consisting of horizontal motions (motions which send every horizontal plane to itself) contains two independent translations. That is to say, it is a 2-dimensional crystallographic group acting on each horizontal plane.

Since we are assuming $`P`$ to be sufficiently generic, all the intersections $`GP\alpha _i`$, $`i\{1,\mathrm{},k\}`$ are orbits of $`G_0`$. The following statement is Lemma 1.3 in .

###### Lemma 1.2.

Under these assumptions, given two different horizontal planes $`\alpha _i`$ and $`\alpha _j`$, a necessary condition for $`Q\alpha _iGP=G_0Q`$ to be a neighbor of $`P\alpha _jGP=G_0P`$ is that the two 2-dimensional Dirichlet stereohedra $`\text{Vor}_{G_0P}(P)`$ and $`\text{Vor}_{G_0Q}(Q)`$ overlap (we are implicitly projecting $`G_0P`$ and $`G_0Q`$ along the direction of $`v`$ to a common horizontal plane). ∎

If, moreover, every element of $`G`$ sends horizontal planes to horizontal planes, then we have the following result. We recall that the normalizer of a group $`G_0`$ in a bigger group $`H`$ is the subgroup of $`H`$ consisting of elements $`gH`$ such that $`g^1G_0g=G_0`$.

###### Lemma 1.3.

Let $`G`$ be a 3-dimensional crystallographic group. Let a vertical direction be chosen so that every element of $`G`$ sends horizontal planes to horizontal planes. Let $`G_0`$ be the subgroup of horizontal motions of $`G`$.

Then the orthogonal projection of any orbit of $`G`$ to a horizontal plane is contained in an orbit of the normalizer of $`G_0`$ in the group of affine isometries of that plane.

Proof: Let $`gG`$ and let $`hG_0`$. Since $`g`$ sends horizontal planes to horizontal planes and $`h`$ sends horizontal planes to themselves, $`g^1hg`$ sends horizontal planes to themselves. Hence $`g^1hgG_0`$ (i.e. $`G_0`$ is normal in $`G`$). This, together with the fact that $`g`$ composed with the projection to any horizontal plane is an affine isometry on that plane, implies the statement. ∎

The following result, most of which comes from , gives a first upper bound on the number of neighbors of $`P`$ in each $`\alpha _i`$, depending on the type of the group $`G_0`$:

###### Theorem 1.4 (\[2, Theorem 3.1\]).

Let $`G_0`$ be a planar crystallographic group and let $`G_0P`$ and $`G_0Q`$ be two orbits of points with trivial stabilizer. Then, the number of Dirichlet regions of one of the orbits overlapped by each Dirichlet region of the other orbit is bounded above by:

* one, for groups of types $`pmm`$, $`p3m1`$, $`p4m`$ and $`p6m`$.
* two, for groups of types $`cm`$, $`cmm`$, $`p31m`$ and $`p4g`$.
* four, for groups of types $`p1`$, $`p3`$, $`p4`$, $`p6`$, $`pmg`$ and $`pm`$.
* seven, for the groups $`p2`$ and $`pg`$.
* eleven, for the group $`pgg`$.
* seven, for the group $`pgg`$, if $`G_0PG_0Q`$ is contained in an orbit of the normalizer of $`G_0`$ in the affine isometries of $`^2`$ (see Proposition 3.3).

The bounds are all tight except perhaps those for $`pg`$ and $`pgg`$.

Proof: Parts (i) to (iv) appear in  as Theorem 3.1. Part (v) was also proved in , although not explicitly stated as a result (see Remark 3.2 and the paragraph before Lemma 3.5 in that paper). Part (vi) is proved as Proposition 3.3 in Section 3 of this paper. ∎

We conjecture that the upper bound for $`pgg`$ is seven even without the normalizer condition.

### 1.2. The classification of 3-dimensional crystallographic groups

The first two invariants to affinely classify a crystallographic group $`G`$ are its *translational subgroup* and its *point group*. The translational subgroup $`T`$ is the subgroup consisting of translations, and belongs to one of the 14 *Bravais lattice types*. The point group of $`G`$ is the quotient group $`[G:T]`$. The elements of $`[G:T]`$ are the *aspects* of $`G`$. The point group can be understood as a discrete group of motions in the 2-dimensional unit sphere satisfying the “crystallographic restriction”: there are no rotations of order 5 or greater than 6. There are 32 groups satisfying this, modulo isometries of the sphere, and all of them appear as point groups of some crystallographic group.

In turn, the lattices are classified into seven *crystallographic systems*: *monoclinic*, *triclinic*, *orthorhombic*, *hexagonal*, *trigonal*, *tetragonal* and *cubic*. This classification is according to the point groups of their normalizers in the group of affine isometries of $`^3`$, except that most authors include in the trigonal system some groups whose lattice is hexagonal, the distinction between the hexagonal and trigonal systems relying on properties of the point group.

Groups which contain reflection planes were studied in  and cubic groups will be dealt with in . Table 3 lists the 97 affine conjugacy classes of non-cubic 3-dimensional crystallographic groups without reflections, divided according to crystallographic systems and point groups. We use the International Crystallographic Notation to name 2-dimensional and 3-dimensional crystallographic groups and have taken the monograph  as a source for their classification. The capital letter at the beginning of a name indicates the Bravais type of the lattice within its crystallographic system. The rest of the name encodes generators for the group in a certain way.

Only 58 of the 97 groups in Table 3 have more than 4 aspects. We will deal only with these 58 groups since the Delone bound for groups with four or less aspects is already 38, matched by Engel’s example. Moreover, experimental evidence indicates that in groups with few aspects Delone’s bound is a good approximation to what can happen in the worst case: There are Dirichlet stereohedra for groups with one and two aspects having 14 and 20 facets respectively \[7, p. 963\].

The 58 groups belong to the following crystallographic systems: orthorhombic (10 groups), trigonal (13 groups), hexagonal (9 groups) and tetragonal (26 groups). They are listed in Tables 47.

There are the following 8 possible Bravais types of lattices in the 58 groups of Tables 47.

* The three primitive lattices (noted $`P`$ in Table 3), generated by a vertical translation and the following planar lattices in horizontal planes: a rectangular lattice in the orthorhombic system, a triangular lattice in the hexagonal and trigonal systems, and a square lattice in the tetragonal system (see Figure 1). Each primitive lattice has a primitive cell associated to it, which is an orthogonal prism over a rectangle, triangle or square respectively. The primitive cell tiles the space face-to-face producing as vertices of the tiling an orbit of the lattice.
* The two body-centered lattices (noted $`I`$) in the orthorhombic and tetragonal systems. They are generated by the primitive lattice and any translation sending a vertex of the primitive cell to the centroid of the cell. Hence, they contain the primitive lattice as a sublattice of index 2.
* The face-centered lattice in the orthorhombic system (noted $`F`$), generated by the primitive lattice and translations from a vertex of the primitive cell to the centroids of the three facets of the cell incident to that vertex. It contains the primitive lattice as a sublattice of index 4.
* The base-centered lattice in the orthorhombic system (noted $`C`$), generated by the primitive lattice and the translation from a vertex of the primitive cell to the centroid of one of the three facets of the cell incident to that vertex. It contains the primitive lattice as a sublattice of index 2.
* The rhombohedral lattice in the trigonal system (noted $`R`$), generated by the primitive lattice and a translation from one of the vertices of the primitive cell (a triangular prism) to a point in the axis of the primitive cell and whose distances to the two triangular bases of the prism are in the ratio 1:2. It contains the primitive lattice as a sublattice of index 4.

### 1.3. A first upper bound

Suppose that $`G`$ is one of the 58 groups of Tables 47. The lattice of $`G`$ contains as a sublattice one of the three primitive lattices, and we choose as vertical the direction of the principal axis in the corresponding primitive cell. The principal axis is well defined in the hexagonal, trigonal and tetragonal systems. In the orthorhombic system there are three perpendicular and equivalent axes. We choose one arbitrarily unless the lattice is base-centered (noted $`C`$) in which case we choose as vertical the direction perpendicular to the centered faces.

This choice fulfills the conditions required in Lemmas 1.2 and 1.3: $`G_0`$ is crystallographic and every element of $`G`$ sends horizontal planes to horizontal planes. We take as vector $`v`$ to apply Lemma 1.1 the shortest vertical translation in $`G`$. The following Lemma shows how to compute the number of horizontal planes in the band $`Z_P`$ of Lemma 1.1 which contain points of $`GP`$. This number depends only on the type of the lattice and the number of aspects of $`G`$ and $`G_0`$.

###### Lemma 1.5.

Apart of the two boundary planes and the plane containing $`P`$, there are exactly $`2al/a_02`$ horizontal planes in $`Z_P`$ containing points of the orbit $`GP`$, where:

* $`a`$ is the number of aspects of $`G`$.
* $`a_0`$ is the number of aspects of the horizontal subgroup $`G_0`$.
* $`l`$ is a number depending only on the lattice of $`G`$, and takes the value 1 in primitive and base-centered lattices, 2 in body-centered and face-centered lattices, and 3 in rhombohedral lattices.

Proof: Let $`T`$ and $`T_0`$ denote the translational subgroups of $`G`$ and $`G_0`$, respectively. The number $`l`$ is the ratio of horizontal planes containing points of $`T`$ to planes containing points of the primitive lattice, so that each orbit of $`T`$ projects to $`l`$ orbits of $`T_0`$.

The closed band $`Z_P`$ contains $`2al`$ plus $`a_0`$ orbits of $`T_0`$. Each horizontal plane containing points of $`GP`$ contains $`a_0`$ orbits of $`T_0`$. Hence, there are $`2al/a_0+1`$ such planes, including the two boundary planes and the one containing $`P`$. Subtracting 3 gives the statement. ∎

###### Corollary 1.6.

Let $`i`$ be the maximum number of intersections between two different orbits of the planar crystallographic group $`G_0`$, as stated in Theorem 1.4. Then, the number of neighbors of the point $`P`$ in an orbit $`GP`$ is bounded above by

$$2i(al/a_01)+8,$$

where $`a`$, $`a_0`$ and $`l`$ are as in Lemma 1.5.

Proof: By Theorem 1.4, $`P`$ has at most $`i`$ neighbors in each horizontal plane of $`Z_P`$ other than the two boundary ones and the one containing $`P`$. The only possible neighbors in the boundary are $`\tau _v(P)`$ and $`\tau _v(P)`$, and in the plane containing $`P`$ there are at most six neighbors, since a planar Dirichlet stereohedron has at most six facets. ∎

In Tables 47, the column “Cor. 1.6” indicates the upper bound given by this statement in each of the 58 groups of interest to us.

## 2. Influence region. Groups with a horizontal $`p2`$ or $`p3`$

Corollary 1.6 is based on using global bounds for the number of regions of $`\text{Vor}_{G_0Q}`$ which can intersect the region $`\text{Vor}_{G_0P}(P)`$. But of course the number of regions intersected depends on $`Q`$, and we are interested only in a few concrete possibilities for the point $`Q`$ in each 3-dimensional crystallographic group. To study the dependence of the number of intersections with $`Q`$ we recall the formalism of extended Voronoi regions and influence regions, already used in .

### 2.1. Influence regions in planar crystallographic groups

Let $`G_0`$ be a crystallographic group in the plane. Let $`N_0`$ be a crystallographic group containing $`G_0`$. We will call *fundamental subdomains* of $`G_0`$ (w.r.t. $`N_0`$) the fundamental domains of $`N_0`$. For a fixed fundamental subdomain $`D`$ of $`G_0`$, we call *extended Dirichlet region* of $`D`$ under $`G_0`$ (and denote it $`\text{Ext}_{G_0}(D)`$) any region containing $`_{QD}\text{Vor}_{G_0Q}(Q)`$.

Observe that, for any given $`D`$, the fundamental subdomains $`\{\tau D:\tau N_0\}`$ tile the plane. We call *influence region* of $`D`$ under $`G_0`$ (and denote it $`\text{Infl}_{G_0}(D)`$) the union of all the tiles $`\tau D`$ with $`\tau N_0`$ for which $`\text{Ext}_{G_0}(\tau D)`$ and $`\text{Ext}_{G_0}(D)`$ overlap.

###### Lemma 2.1.

Let $`P`$ and $`Q`$ be two points in the plane and let $`D`$ be a fundamental subdomain containing $`P`$. A necessary condition for $`\text{Vor}_{G_0P}(P)`$ and $`\text{Vor}_{G_0Q}(Q)`$ to overlap is that $`Q`$ lies in $`\text{Infl}_{G_0}(D)`$.

Proof: Let $`\tau N_0`$ be such that $`Q\tau D`$. By construction, $`\text{Vor}_{G_0P}(P)\text{Ext}_{G_0}(D)`$ and $`\text{Vor}_{G_0Q}(Q)\text{Ext}_{G_0}(\tau D)`$. This proves the statement. ∎

Observe finally that the action of $`G_0`$ divides the fundamental subdomains in a finite number of orbits. Then, for each point $`Q^2`$, the number of regions of $`\text{Vor}_{G_0Q}`$ which intersect $`\text{Vor}_{G_0P}(P)`$ can be bounded above by counting how many fundamental subdomains in the orbit of fundamental subdomains containing $`Q`$ intersect the influence region $`\text{Infl}_{G_0}(D)`$.

In this section we apply this formalism to 2-dimensional crystallographic groups of types $`p2`$ and $`p3`$:

#### Groups of type $`p3`$:

Let $`G_0`$ be a group of type $`p3`$, generated by an order 3 rotation and two translations of equal length with angle $`\pi /6`$ to one another. The order-3 rotation centers of the group form a triangular lattice, and any two adjacent elementary triangles of the lattice form a fundamental domain. Our choice of $`N_0`$ is generated by $`G_0`$ together with any reflection on one of the sides of an elementary triangle. Each elementary triangle is a fundamental subdomain, and there are two $`G_0`$-orbits of fundamental subdomains, which we call $`B`$ and $`W`$ for “black” and “white”. The three neighbors of a black triangle are white and vice-versa. We assume the subdomain containing $`P`$ to be white.

The extended Dirichlet region of an elementary triangle consists of this triangle and the three adjacent to it. This is shown in the left part of Figure 2 in the following way: a base point $`P`$ in a fundamental subdomain $`D`$ and other six points of the orbit $`G_0P`$ are drawn. Let $`\tau P`$ be one of the six points. The region of the plane consisting of points closer to $`\tau P`$ than to $`P`$ for any choice of $`P`$ in the central fundamental subdomain is clearly disjoint with $`\text{Ext}_{G_0}(D)`$. What is left is precisely the union of $`D`$ and its three adjacent subdomains.

Hence, the influence region consists of the fundamental subdomains which are either in $`\text{Ext}_{G_0}(D)`$ or adjacent to a fundamental subdomain in $`\text{Ext}_{G_0}(D)`$. This gives the 10 fundamental subdomains in the right part of Figure 2.

In total, there are seven white and three black triangles in the influence region.

###### Lemma 2.2.

Let $`G_0`$ be a group of type $`p3`$. Let $`P`$ and $`Q`$ be two points in the plane and suppose that $`P`$ lies in a white triangle, in the sense explained above. Then, the number of regions of $`\text{Vor}_{G_0Q}`$ which overlap $`\text{Vor}G_0P(P)`$ is at most three if $`Q`$ is in a black triangle and at most four if it is in a white triangle.

Proof: The bound of three for black triangles is obvious since there are only three black triangles in the influence region. For the white triangles we would in principle have a bound of seven, but part (iv) of Theorem 1.4 gives four. ∎

#### Groups of type $`p2`$ with rectangular grid:

Let $`G_0`$ be a group of type $`p2`$, generated by two independent translations and a rotation of order two. We assume further that the two generating translations are orthogonal to one another, which implies that the order-2 rotation centers form a rectangular grid. Any two adjacent elementary rectangles in this grid form a fundamental domain for $`G_0`$. Our choice of $`N_0`$ is generated by $`G_0`$ together with any reflection on one of the sides of an elementary rectangle. Then, each elementary rectangle is a fundamental subdomain and there are two $`G_0`$-orbits of fundamental subdomains which we call $`B`$ and $`W`$ for “black” and “white”. The four neighbors of a black rectangle are white and vice-versa. We assume the rectangle containing $`P`$ to be white.

The extended Dirichlet region of an elementary rectangle consists of this rectangle and the four adjacent to it. The influence region consists of the extended Dirichlet region and the eight elementary rectangles adjacent to it. See Figure 3. In total, there are nine white and four black rectangles in the influence region.

###### Lemma 2.3.

Let $`G_0`$ be a group of type $`p2`$ with a rectangular grid. Let $`P`$ and $`Q`$ be two points in the plane and suppose that $`P`$ lies in a white rectangle, with the meaning explained above. Then, the number of regions of $`\text{Vor}_{G_0Q}`$ which overlap $`\text{Vor}G_0P(P)`$ is at most four if $`Q`$ is in a black rectangle and at most seven if it is in a white rectangle.

Proof: The bound of four for black rectangles comes from the influence region. The bound of seven for white rectangles comes from Theorem 1.4. ∎

We are interested in the case where $`G_0`$ is the horizontal subgroup of a 3-dimensional crystallographic group $`G`$. We will always make sure that $`N_0`$ is a group of horizontal motions that not only contains $`G_0`$ but is also contained in the normalizer of $`G`$ in the isometry group of $`^3`$. The following lemma implies that if this happens then there is no loss of generality in assuming that our base point $`P`$ lies over any fixed fundamental subdomain $`D`$, since if this is not the case then there will be an orbit $`GP^{}`$ isometric to $`GP`$ (in particular, with congruent Dirichlet stereohedra) and with $`P^{}`$ over $`D`$.

###### Lemma 2.4.

Let $`G`$ be a 3-dimensional crystallographic group. Let $`G_0`$ be its horizontal subgroup and let $`N_0`$ be a horizontal group containing $`G_0`$ and contained in the normalizer of $`G`$. Let $`D`$ be a fundamental subdomain of $`G_0`$. Let $`P`$ be any point in $`^3`$. Then, there is an isometry $`\tau `$ sending $`P`$ to a point $`P^{}`$ over $`R`$ and with $`\tau (GP)=G(\tau P)`$.

Proof: Let $`\tau N_0`$ be a horizontal motion sending $`P`$ to a point $`P^{}`$ over $`D`$. This exists since $`D`$ is a fundamental domain of $`N_0`$. Since $`\tau `$ is in the normalizer of $`G`$, $`\tau GP=G\tau P=GP^{}`$. This finishes the proof. ∎

### 2.2. Groups with a horizontal $`p2`$ of rectangular type

###### Proposition 2.5.

The four orthorhombic and seven tetragonal groups with 8 aspects displayed in Figure 4 have a horizontal group $`G_0`$ of type $`p2`$ with rectangular grid. The reflections on vertical planes containing edges of elementary rectangles of the grid lie in the normalizer of $`G`$.

In each case, the band $`Z_P`$ contains six horizontal planes (not counting the boundary and middle ones) of a generic orbit $`GP`$, four which produce black orbits and two which produce white orbits. Hence, their Dirichlet stereohedra cannot have more than 38 facets.

Proof: The bound of 38 follows from the rest of the statement by a counting argument, using Lemma 2.3: to the 6 neighbors in the plane of $`P`$ and 2 in the boundary of $`Z_P`$ we have to add four in each of the four “black” planes of orbits and seven in the two “white” ones.

The rest of the statement can be easily checked in the graphical representation of each group displayed in Figure 4. Let us first explain this representation.

In each picture, a horizontal projection of a generic orbit appears. The black ovals in the corners of the rectangles/squares represent the order-2 rotation centers of the horizontal group $`p2`$. Hence, any of the four rectangles is a fundamental subdomain, any adjacent two are a fundamental domain of $`G_0`$, and the four together are a fundamental domain of the translational subgroup of $`G_0`$. In each picture, the black circle in the bottom-right quadrant represents the base point $`P`$ for the 3-d orbit $`GP`$. The other seven circles represent points in the other seven aspects of $`G`$, with their heights indicated in the following way: let $`z`$ be the height of the base point and assume that the shortest vertical translation in $`G`$ has length 1. Then, black circles with a number $`\alpha `$ represent horizontal orbits at heights $`z+\alpha `$ (and hence at $`z+\alpha +m`$ for any integer $`m`$) while white circles with a number $`\alpha `$ represent orbits at height $`z+\alpha `$ (and hence at $`z+\alpha +m`$ for any integer $`m`$). The absence of a number means $`\alpha =0`$ (as happens in the base point itself).

To make all this clearer, let us describe generators for the group $`P\frac{2}{n}\frac{2}{n}\frac{2}{n}`$ deduced from its graphical representation. First, there is the translational subgroup, generated by horizontal translations on the sides of the big rectangle and a vertical translation of length 1. Then, we have to describe how to get the other seven points in the figure from the base point. The white point in the bottom-right rectangle is obtained by a rotation of order two around the vertical axis of the bottom-right rectangle, followed by a reflection on the horizontal plane at height zero. The two points on the upper-left rectangle are obtained from the two in the bottom-right rectangle by a rotation of order two on the vertical line through the middle black oval. The other four points are obtained from the first four by a rotation of order two around the line at height 1/4 over any of the two horizontal axes of the big rectangle.

Let us also see how to check in the picture the conditions of the statement. An isometry $`\tau `$ is in the normalizer of $`G`$ if and only if for any generic orbit $`GP`$, $`\tau GP`$ is again an orbit of $`G`$ (if this happens, let $`P^{}=\tau P`$ and let $`P^{\prime \prime }`$ be such that $`\tau GP=P^{\prime \prime }`$. Then $`\tau G\tau ^1P^{}=GP^{\prime \prime }`$ which implies $`P^{}GP^{\prime \prime }`$ and, since $`P`$ is generic, $`\tau G\tau ^1=G`$). In each figure it is easy to check that a reflection in any of the displayed lines produces a new orbit of $`G`$.

As for the number of planes in the band $`Z_P`$, each horizontal orbit of $`G`$, except for the one containing $`P`$, produces exactly two planes in $`Z_P`$, since $`Z_P`$ has width 2 and the minimal vertical translation has length one. In the Figures, the left-top and right-bottom quadrants are “white” fundamental subdomains and the other two are “black”. ∎

More or less the same technique can be applied to the group $`P4_122`$, depicted in Figure 5. Part (a) is its standard graphical representation, showing the eight points of a generic orbit $`GP`$ which lie inside the translational primitive cell of the tetragonal system, projected onto the $`XY`$ plane and with their heights ($`Z`$-coordinates) indicated. Part (b) shows the projection of these same points to the $`YZ`$ coordinate plane. The black ovals indicate order-2 rotations of $`G`$ with axes in lines parallel to the $`X`$ axis. They can also be read as order-2 rotation centers in the planar subgroup of $`G`$ which preserves planes parallel to $`YZ`$. This subgroup, hence, is of type $`p2`$ with a rectangular grid.

###### Corollary 2.6.

Dirichlet stereohedra for the group $`P4_122`$ cannot have more than 50 facets.

Proof: Let $`G`$ be a group of type $`P4_122`$. Let $`G_1`$ be the subgroup of $`G`$ which preserves planes parallel to $`YZ`$. Let $`Z_P`$ be the band centered at the $`YZ`$-plane containing our base point $`P`$ and of width two times the shortest translation of $`G`$ (and of $`G_1`$) in the $`X`$-direction. Only seven $`G_1`$-orbits intersect the interior of the band. Although we cannot say here that the $`G_1`$-orbits are related by the normalizer of $`G_1`$, still we can apply Lemma 1.1, Lemma 1.2 and Theorem 1.4 to conclude that each $`G_1`$ orbit produces at most 7 neighbors except $`G_1P`$ which produces at most 6. This gives at most 48 neighbors in the interior of $`Z_P`$ and we have to add the two translates of $`G_1`$ in the $`X`$-direction.

Observe that the choice of $`P`$ shown in Figure 5 produces four $`G_1`$-orbits in “black” fundamental subdomains, for which the number of neighbors is at most 4. But there are choices of $`P`$ in which all the $`G_1`$-orbits lie in white subdomains. ∎

### 2.3. Groups with a horizontal $`p3`$

###### Proposition 2.7.

The four trigonal groups displayed in Figure 6 have a horizontal group of type $`p3`$. The first three have ten horizontal planes (not counting the boundary and middle ones) in the region $`Z_P`$, six of which lie over black subdomains and four over white subdomains, in the sense of Lemma 2.2. Hence, their Dirichlet stereohedra cannot have more than 42 facets.

The last group has 22 horizontal planes (not counting the boundary and middle ones) in the region $`Z_P`$, 12 which produce black orbits and ten which produce white orbits. Hence, their Dirichlet stereohedra cannot have more than 84 facets.

Proof: As in Proposition 2.5, the stated bound follows from the rest of the statement. The statement on horizontal planes follows from the graphical representation of each group in Figure 6. For each group, the small black triangles represent centers of rotation of order three. The region displayed is a fundamental domain for the horizontal group and the six (in the first three groups) or twelve (in the last one) black or white points represent a generic orbit of $`G`$, with the same conventions as in the proof of Proposition 2.5. ∎

For the trigonal group $`R\overline{3}\frac{2}{c}`$ the upper bound of 84 neighbors obtained in Proposition 2.7 can still be lowered a bit if we take into account that not only horizontal planes but also vertical planes contain many points of each orbit. Observe that the bound of Proposition 2.7 can be stated more precisely as saying that $`P`$ can have at most 48 neighbors which project to white triangles in the influence region and at most 36 neighbors which project to black triangles. We will be interested in the latter ones. Figure 7 shows the projection of a generic orbit to the union of 4 fundamental subdomains forming a triangle. If we assume $`P`$ to project to the central triangle, colored white, then the other three triangles are the three black triangles contained in the influence region.

The dashed lines in Figure 7 represent nine vertical planes $`A`$, $`B`$, $`C`$, $`A^{}`$, $`B^{}`$, $`C^{}`$, $`A^{\prime \prime }`$, $`B^{\prime \prime }`$ and $`C^{\prime \prime }`$ with the property that any black neighbor of $`P`$ lies in two of them. On the other hand, the subgroup of $`G`$ fixing each of those planes is a planar crystallographic group of type $`p2`$ and, by Theorem 1.4, produces at most seven neighbors. Hence the number of black neighbors cannot exceed $`9\times 7/2=31.5`$. This implies the following:

###### Corollary 2.8.

A Dirichlet stereohedron for a group of type $`R\overline{3}\frac{2}{c}`$ cannot have more than 31+48=79 neighbors.

## 3. Reduced influence region. Groups with a horizontal $`pgg`$ or $`pg`$

### 3.1. How two orbits of $`pgg`$ related by the normalizer intersect

We recall the following result from  (Theorem 3.1):

###### Lemma 3.1.

Let $`G_0`$ be a planar crystallographic group of type $`pgg`$ and let $`P`$ and $`Q`$ be two points in the plane. Assuming that $`G_0PG_0Q`$ is an orbit of a certain crystallographic group, the number of Dirichlet regions of $`\text{Vor}_{G_0Q}`$ which overlap $`\text{Vor}_{G_0P}(P)`$ is at most seven. ∎

A case study shows that under the hypotheses of the lemma we must have $`Q=\tau P`$ where $`\tau `$ is an element of the normalizer of $`G_0`$ in the group of Euclidean isometries of the plane. We intend to extend the lemma to this more general case, thus proving part (vi) of Theorem 1.4.

Recall that $`pgg`$ is generated by two perpendicular translations

together with a rotation of order two and a glide reflection of vector half of one of the translations. There are two possibilities for the normalizer:

* If the generating translations have different lengths, then the normalizer $`N_0`$ is generated by $`G_0`$ together with reflections on the lines supporting the rectangles of the grid of rotation centers. $`G_0`$ has index four in $`N_0`$ and we have that for any $`\tau N_0`$, $`\tau ^2`$ is in $`G_0`$. In particular, $`G_0\tau G_0`$ is a crystallographic group for every $`\tau N_0`$, and hence Lemma 3.1 already implies what we want to prove.
* If the generating translations have the same length, then the normalizer $`N_0`$ is generated by $`G_0`$ together with the reflections mentioned above and rotations of order four in the rotation centers of $`G_0`$. This is the case we will be interested in.

$`G_0`$ has index eight in $`N_0`$. More precisely, we can take as fundamental domains of $`G_0`$ squares with vertices in rotation centers and as fundamental subdomains (i.e. fundamental domains of $`N_0`$) the eight triangles in which the symmetries of the square divide the fundamental domains. The influence region is computed in Figure 8. The left part is an extended Dirichlet region of the initial fundamental subdomain $`D`$, computed as in Figure 2. The right part is the union of all the fundamental subdomains whose extended Dirichlet region overlaps the one on the left part. The extended Dirichlet region of a fundamental subdomain $`\tau D`$ is obtained applying $`\tau `$ to the extended Dirichlet region $`\text{Ext}_{G_0}(D)`$, for each $`\tau N_0`$.

We have labeled the eight elements of $`N_0/G_0`$ (and hence the fundamental subdomains) with the letters A, B, C, D, A’, B’, C’ and D’. A represents $`G_0`$ itself and A, B, C and D would form the normalizer of $`G_0`$ in case that the two generating translations had different length. The number of fundamental subdomains of each type in the influence region is shown on the right part of Figure 8. This number never exceeds nine. This implies:

###### Lemma 3.2.

Let $`G_0`$ be a planar crystallographic group of type $`pgg`$ whose generating translations have equal length. Let $`G_0P`$ and $`G_0Q`$ be two orbits with trivial stabilizer. Then, the number of Dirichlet regions of one of the orbits overlapped by each Dirichlet region of the other orbit is at most nine.

So far we have not used the fact that we are interested in orbits related by the normalizer. How to use this property is exhibited in Figure 9. In part (a), our base orbit of $`G_0`$ is shown (in black) together with the corresponding orbit of type “B” (in white). One point of this latter orbit has been crossed out, meaning that its corresponding Dirichlet region can never overlap the region of the base point. The reason is in the four points joined by a dashed quadrilateral: the movement of the normalizer sending the black vertices of this quadrilateral to the white ones is an order-2 rotation, hence the quadrilateral is a parallelogram. The bisectors of the two black vertices and the two white vertices of the quadrilateral will be parallel and will separate the Dirichlet regions of the base point $`P`$ and the point crossed out.

The same argument applies to the point crossed out on the top end of Figure 9(b), where the “A” and “C” orbits are shown. But we have crossed out also two other points, one on the top-right end and one on the bottom-left end. The proof that the Dirichlet regions of these two points cannot overlap the one of our base point is in  (paragraph $`[A,C]`$ and, in particular, Figure 19). Hence, instead of 7 and 9 fundamental subdomains of types B and C which potentially could produce Dirichlet regions overlapping the base Dirichlet region we have now 6 of each type. As a conclusion:

###### Proposition 3.3.

Let $`G_0`$ be a planar crystallographic group of type $`pgg`$ and let $`P`$ and $`Q`$ be any two points in the plane. Assuming that $`Q=\tau P`$ for some element $`\tau `$ in the normalizer of $`G_0`$, the number of Dirichlet regions of $`\text{Vor}_{G_0Q}`$ which overlap $`\text{Vor}_{G_0P}(P)`$ is at most seven. ∎

### 3.2. Groups with a horizontal $`pgg`$

The reduced influence region of Figure 9 can be used to lower the upper bounds given by Corollary 1.6 for the groups whose horizontal subgroup $`G_0`$ is a $`pgg`$ with a square grid. This follows from the fact that only one type of planar orbits of those produced by the normalizer give seven neighbors (the one we have labeled $`D`$), and the rest only six.

More precisely, Figure 10 shows the graphical representation of the four groups in question. The square displayed is a fundamental domain of $`G_0`$, divided into eight fundamental subdomains. In the first three groups the “bad” planar orbit, labeled with a D in Figure 8, does not appear. Hence we can take $`i=6`$ in the computations of Corollary 1.6 for these groups. In $`I\frac{4_1}{g}\frac{2}{c}\frac{2}{d}`$ the bad orbit appears, but still we can count six neighbors for 12 of the planes in the band $`Z_P`$ and seven for only two of them. This gives:

###### Proposition 3.4.

Dirichlet stereohedra for the groups $`I4_1cd`$, $`I\overline{4}c2`$ and $`P\frac{4_2}{n}\frac{2}{g}\frac{2}{c}`$ cannot have more than 44 facets. Dirichlet stereohedra for the group $`I\frac{4_1}{g}\frac{2}{c}\frac{2}{d}`$ cannot have more than 94 facets.

But we can use vertical planes to refine this result a bit. Figure 11 shows the projection of a generic orbit $`GP`$ to the influence region computed above, where $`G`$ is of type $`I\overline{4}c2`$ or $`P\frac{4_2}{n}\frac{2}{g}\frac{2}{c}`$ in part (a) of the Figure and of type $`I\frac{4_1}{g}\frac{2}{c}\frac{2}{d}`$ in part (b). The number 44 or 94 stated in Proposition 3.4 is obtained counting 2 possible neighbors over each fundamental subdomain, except in the six grey subdomains (those containing points at the same height as $`P`$ except the one containing $`P`$ itself) where only one neighbor over each fundamental subdomain is possible. The dashed line in part (a) of the figure represents a vertical plane containing the base point $`P`$ where we have counted ten possible neighbors while there are at most six real neighbors (since in a planar Dirichlet tiling each region is a neighbor of at most other six). Hence, instead of 44 we can take 40 as an upper bound for $`I\overline{4}c2`$ or $`P\frac{4_2}{n}\frac{2}{g}\frac{2}{c}`$.

Similarly, the five dashed lines in part (b) of Figure 11 represent five vertical planes $`A`$, $`B`$, $`C`$, $`D`$ and $`E`$ where we have counted 12, 12, 10, 10 and 12 possible neighbors respectively, giving a total of 50 because two of them are common to $`A`$, $`B`$ and $`C`$, and other two common to $`B`$ and $`D`$. As before, $`A`$, $`B`$ and $`C`$ can produce at most six neighbors each, because they all contain $`P`$.

Let $`G_1`$ denote the subgroup of $`G`$ preserving planes parallel to $`A`$, in particular preserving $`D`$ and $`E`$. $`G_1`$ is of type $`pgg`$ (although it does not have its two translations of equal length). According to Theorem 1.4 each plane parallel to $`A`$ can contain at most 11 neighbors, and only seven if the $`G_1`$-orbits in that plane and in $`A`$ are related by the normalizer. The latter happens in the plane $`D`$; the orbits in the planes $`A`$ and $`D`$ are related by a glide reflection in the bisecting plane, which projected to any of them becomes a translation lying in the normalizer of the corresponding $`pgg`$.

Hence, the planes $`A`$, $`B`$, $`C`$, $`D`$ and $`E`$ can contain in total at most $`6+6+6+11+7=36`$ neighbors, instead of the 50 which we have counted.

###### Corollary 3.5.

Dirichlet stereohedra for the groups $`I\overline{4}c2`$ and $`P\frac{4_2}{n}\frac{2}{g}\frac{2}{c}`$ cannot have more than 40 facets. Those for $`I\frac{4_1}{g}\frac{2}{c}\frac{2}{d}`$ cannot have more than 80 facets.

###### Remark 3.6.

Using the methods of \[2, Section 3.3\] in a more sophisticated way, the number appearing for $`pgg`$ in part (v) of Theorem 1.4 can be lowered to nine instead of eleven (see \[2, Remark 3.2\]). In the preceeding argument, this would lower the number of possible neighbors in the plane $`E`$ by two as well, giving a bound of 78 instead of 80. But this small improvement does not seem to be worth the effort of giving a proof here.

### 3.3. Groups with a horizontal $`pg`$

We will now compute the influence region of a planar group of type $`pg`$, in order to lower the bound for the groups $`P\frac{2_1}{n}\frac{2}{c}\frac{2_1}{a}`$ and $`P\frac{2_1}{a}\frac{2_1}{b}\frac{2_1}{c}`$. Remember that $`pg`$ is generated by two perpendicular translations and a glide reflection on a line parallel to one of them. Let $`a`$ and $`b`$ be the vectors of the two translations, $`a`$ being parallel to the glide-reflection line. Observe that $`G`$ consists of translations and glide-reflections on a family of lines parallel to $`a`$ and distant $`\frac{|b|}{2}`$ to one another. Any rectangle of sides $`a`$ and $`\frac{b}{2}`$ placed between two consecutive such lines is a fundamental domain for $`G_0`$. See Figure 12(a).

We take as $`N_0`$ the group generated by $`G_0`$, a reflection on a line parallel to $`b`$ and reflections on the glide-reflection lines of $`G_0`$ and the midlines between any two consecutive glide reflection lines. Each fundamental domain of $`G_0`$ gets divided into 8 fundamental domains of $`N_0`$, which are rectangles of sides $`\frac{a}{4}`$ and $`\frac{b}{4}`$. See again Figure 12(a), where one of these fundamental subdomains has been shaded.

Part (b) of Figure 12 shows the extended Dirichlet region of a fundamental subdomain, and part (c) the corresponding influence region. The shadowed rectangles in part (c) are the fundamental subdomains lying in the influence region but which cannot produce overlapping regions if the two orbits of $`G_0`$ are related by $`N_0`$, with the same argument as in part (a) of Figure 9. Hence, the interior of the thick polygon is the reduced influence region. We label the eight $`G_0`$-cosets in $`N_0`$ with the letters A, B, C, D, E, F, G and H where A is $`G_0`$ itself, and get for the orbits in each class the number of overlapping regions shown on the right of Figure 12(c). This number equals four in the cosets obtained from A by a translation in the direction of $`a`$ (coset C), reflection on a line parallel to $`b`$ (cosets B and D), or glide-reflection with axis in the direction of $`a`$ (coset G). It equals six in the coset E obtained by any of the other of reflections of $`N_0`$, and seven in the other two cosets F and G, obtained by order-two rotations or vertical translation.

We now look at the two orthorhombic groups in Table 4 having a horizontal $`pg`$. They are depicted in Figure 13. As usual, the picture shows the projection of a translational cell, which in this case consists of two fundamental domains of $`G_0`$. In the group $`P\frac{2_1}{n}\frac{2}{c}\frac{2_1}{a}`$ we see that the horizontal planes contain orbits of types D, E and H, while in $`P\frac{2_1}{a}\frac{2_1}{b}\frac{2_1}{c}`$ we have of types D, F and G.

###### Proposition 3.7.

Dirichlet stereohedra for the groups $`P\frac{2_1}{n}\frac{2}{c}\frac{2_1}{a}`$ and $`P\frac{2_1}{a}\frac{2_1}{b}\frac{2_1}{c}`$ cannot have more than 38 facets, respectively.

Proof: In $`P\frac{2_1}{a}\frac{2_1}{b}\frac{2_1}{c}`$, the band $`Z_P`$ contains two horizontal orbits of each of types D, F and G, which produce at most $`2\times (4+7+4)=30`$ neighbors. These, added to the six neighbors in the base horizontal orbit and the two vertical translates of $`P`$, provides the upper bound.

For the group $`P\frac{2_1}{a}\frac{2_1}{b}\frac{2_1}{c}`$ we will use vertical planes, and Figure 14 which shows the projection of a generic orbit of $`G`$ to the reduced influence region computed above.

Counting 2 points over each white rectangle and one over each grey rectangle gives 44 possible neighbors.

Let us concentrate in the $`G_0`$-orbit containing $`P`$, whose intersection with the reduced influence region consists of $`P`$ and the eight points in grey rectangles, labeled $`X_1`$, $`X_2`$, $`Y_1`$, $`Y_2`$, $`Z_1`$, $`Z_2`$, $`Z_3`$ and $`Z_4`$ in Figure 14. $`X_1`$, $`X_2`$, $`Y_1`$ and $`Y_2`$ are obtained from $`P`$ by translations of $`G_0`$. The other four by glide reflections. In the planar Dirichlet tiling produced by this orbit we have:

1. $`P`$ is a neighbor of the point $`X_1`$ if and only if it is a neighbor of $`X_2`$, because $`P`$ being a neighbor of $`Q`$ implies $`\tau P`$ being a neighbor of $`\tau Q`$ for any $`\tau G_0`$.
2. $`P`$ is a neighbor of the point $`Y_1`$ if and only if it is a neighbor of $`Y_2`$, for the same reason.
3. The four points $`X_1`$, $`X_2`$, $`Y_1`$ and $`Y_2`$ cannot be all neighbors of $`P`$. This is a topological argument: If $`X_1`$ and $`X_2`$ are neighbors of $`P`$ then $`Z_1`$ is a neighbor of $`Z_2`$ and $`Z_3`$ is a neighbor of $`Z_4`$. There is no “room left” for $`Y_1`$ or $`Y_2`$ being neighbors of $`P`$.

Let us say that we are in the “X” case if $`Y_1`$ and $`Y_2`$ are not neighbors of $`P`$ and in the “Y” case if $`X_1`$ and $`X_2`$ are not neighbors of $`P`$. Statement (iii) above implies that we are always in one of the two cases (maybe in the two of them).

The dashed lines in Figure 14 represent four vertical planes $`R`$, $`S`$, $`X`$ and $`Y`$. The number 44 implied counting 8 possible neighbors in each of them and 30 points in total in the four planes, since the two points counted over $`P`$ are common to $`X`$ and $`Y`$. We will see that the four planes can contain at most 26 neighbors of $`P`$ in total, which finishes the proof.

$`R`$ and $`S`$ can contain at most seven neighbors each by Theorem 1.4, since the planar subgroup of $`G`$ with respect to the planes parallel to $`R`$, $`S`$ and $`X`$ is of type $`pg`$.

$`X`$ and $`Y`$ contain $`P`$ and hence each of them gives at most six neighbors. But we can be more precise: in the “X” case, $`X`$ gives at most six neighbors and $`Y`$ gives at most four neighbors not contained in $`X`$. In the “Y” case, $`Y`$ gives at most six neighbors and $`X`$ gives at most four neighbors not contained in $`Y`$. ∎

## 4. The group $`P6_122`$

### 4.1. An upper bound using vertical planes

We now deal with a group $`G`$ of type $`P6_122`$, whose horizontal subgroup $`G_0`$ is generated by two translations of equal length forming an angle of $`60^{}`$. The whole group is generated by $`G_0`$ together with

* a screw rotation of order 6 and of vertical axis and
* any rotation of order 2 with axis parallel to one of the generating horizontal translations and intersecting the screw-rotation axis.

See a graphical representation of the group in Figure 15(a).

###### Proposition 4.1.

Dirichlet stereohedra for the group $`P6_122`$ cannot have more than 78 facets.

Proof: Remember that Corollary 1.6 gave an upper bound of 96 for the number of neighbors in this group. We first show a different way of deriving this same upper bound which will be more appropriate for our purposes here.

Let $`l`$ denote the minimal length of a horizontal translation in $`G`$, so that the horizontal group $`G_0`$ generates a triangular lattice with equilateral triangles of side $`l`$. Each such triangle has height $`a=\sqrt{3}l/2`$. Then, for any point $`P`$ we have that $`\text{Vor}_{G_0P}(P)`$ is an infinite prism over a regular hexagon of side $`2a/3=l/\sqrt{3}`$. Since this happens for every point, the condition necessary and sufficient for $`\text{Vor}_{G_0P}(P)\text{Vor}_{G_0Q}(Q)\mathrm{}`$ is than that $`Q`$ lies in the prism over $`2\text{Vor}_{G_0P}(P)`$, i.e., over the regular hexagon of side $`4a/3=2l/\sqrt{3}`$ centered at $`P`$ and with sides orthogonal to the primitive translations of $`G_0`$. This is the thick hexagon in Figure 15(b). Moreover, if $`Q`$ is not in the same horizontal plane as $`P`$, a necessary condition for a $`QGP`$ being a neighbor of $`P`$ in $`\text{Vor}_{GP}(P)`$ is that the projection of $`Q`$ to the horizontal plane containing $`P`$ lies strictly inside that hexagon. For the points in the same horizontal plane as $`P`$ it is allowed, however, to lie in the boundary of the hexagon. Then, the possible neighbors of $`P`$ in $`\text{Vor}_{GP}(P)`$ are:

* The six points obtained from $`P`$ by primitive horizontal translations, i.e., the mid-points of the edges of the thick hexagon in Figure 15.
* The two closer vertical translates of $`P`$.
* The points which project to the interior of the thick hexagon and with vertical distance to $`P`$ smaller than 1. There are 22 horizontal planes other than the one containing $`P`$ and with distance to $`P`$ smaller than 1. A simple density argument shows that at most four orbit points in each of the 22 planes lie inside the hexagon. More precisely, the density argument says that exactly four points at each horizontal plane project to the hexagon if one counts points projecting to the interior as 1, those projecting to facets of the hexagon as $`1/2`$ and those projecting to vertices as $`1/3`$.

Summing up, the above gives a bound of $`22\times 4+6+2=96`$ neighbors. Our goal is to decrease the $`22\times 4`$ part by considering vertical planes parallel to the $`XZ`$ coordinate plane. The subgroup $`G_1`$ consisting of elements of $`G`$ which preserve those planes is of type $`p2`$, generated by a translation of length $`l`$ in direction $`X`$, a translation of length 1 in direction $`Z`$ and any order 2 rotation contained in $`G_1`$ (whose axis will be parallel to $`Y`$ and intersect some screw rotation axes of $`G`$).

The orbit $`GP`$ decomposes into an infinite family of orbits of the group $`G_1`$ lying in different $`XZ`$-planes. Ten of them are marked in Figure 15(b) with the letters $`A`$, $`B`$, $`C`$, $`D`$, $`E`$, $`A^{}`$, $`B^{}`$, $`C^{}`$, $`D^{}`$ and $`E^{}`$. $`A`$ is the one containing the base point $`P`$. In each pair $`A`$-$`A^{}`$, $`B`$-$`B^{}`$, $`C`$-$`C^{}`$, $`D`$-$`D^{}`$ and $`E`$-$`E^{}`$ one of the $`G_1`$ orbits is obtained from the other by a screw rotation $`\rho `$ of order 2 in the vertical axis $`\{X=l/4,Y=a/2\}`$. More importantly, when projected to any of the $`XZ`$-planes, $`\rho `$ becomes an element of the normalizer of $`G_1`$ which exchanges the coloring of the rectangular tiling used in Lemma 2.3. Hence, by that Lemma,

Claim 1: In $`A^{}`$ we can have at most 4 neighbors of $`P`$ and in any of the other pairs $`B`$-$`B^{}`$, $`C`$-$`C^{}`$, $`D`$-$`D^{}`$ and $`E`$-$`E^{}`$ one of the two planes can provide at most 7 neighbors and the other one at most 4 neighbors (although a priori we do not know which plane is which).

Let us now show that the bound of 96 obtained above over-counted the points in these ten planes by at least 18. For this we use Figure 16, which essentially coincides with Figure 15(b) except that we have removed the numbers showing the height of different points and included instead the subdivision of the plane into fundamental subdomains of the horizontal group $`G_0`$. The darker fundamental subdomain, which we call $`D_0`$, is the one containing the base point $`P`$.

The lighter shaded polygonal region of Figure 16 consists of the fundamental subdomains $`D`$ with the property that for any choice of $`P`$ in $`D_0`$ the points of $`GP`$ lying over $`D`$ are in the interior of the hexagonal influence region centered at $`P`$. In other words, the fundamental subdomains $`D`$ for which the upper bound of 96 includes two points above $`D`$ for any choice of $`P`$.

This implies that the 96 points of the previous bound include at least 6 points in the planes $`D^{}`$, $`C^{}`$ and $`E`$, at least 8 points in the planes $`B^{}`$, $`A^{}`$, $`A`$, $`B`$, $`C`$ and $`D`$ and at least 5 points in the plane $`E^{}`$. The number for $`A`$ include the special counting of points obtained from $`P`$ by translations of $`G`$. The number for $`E^{}`$ takes into account a fundamental subdomain whose orbit points lie in a facet of the hexagonal prism and which have been counted as 1/2 in the “96 points”. According to Claim 1, we have over-counted at least 5, 3 and 3, respectively, in the pairs of planes $`B`$-$`B^{}`$, $`C`$-$`C^{}`$ and $`D`$-$`D^{}`$. In the pair $`E`$-$`E^{}`$ we have over-counted at least 1, since one of them produces at most 4 neighbors and we have counted more than 4 in each of them. Finally, we have over-counted 4 points in the plane $`A^{}`$ and 2 in the plane $`A`$. ∎

### 4.2. Dirichlet stereohedra with many facets

Our constructions of Dirichlet stereohedra with many facets are based on the following result. The case $`k=8`$ appeared in . The general case has been independently proved by J. Erickson as Lemma 1 in :

###### Lemma 4.2.

Let $`g`$ be the screw rotation of order $`k`$ around the $`Z`$ coordinate axis, with translation of length l, i.e. $`g(x,y,z)=(x\mathrm{cos}(2\pi /k)y\mathrm{sin}(2\pi /k),x\mathrm{sin}(2\pi /k)+y\mathrm{cos}(2\pi /k),z+l)`$. Let $`g`$ be the (infinite cyclic) group generated by $`g`$. Then, any point $`P`$ not on the axis of $`g`$ has as neighbors in $`\text{Vor}_{gP}(P)`$ the $`2k`$ points $`g^iP`$ for $`i\{k,\mathrm{},k\}\{0\}`$.

Proof: For any $`P^3`$ (but not on the $`Z`$-axis) the convex hull of $`gP`$ is an infinite prism over a regular $`k`$-gon, one of the edges of the prism containing the points $`g^{nk}P`$, for $`n`$. In particular, $`g^kP`$ and $`g^k(P)`$ must be neighbors of $`P`$. We will prove that the points $`g^iP`$ for $`i\{k+1,\mathrm{},k1\}\{0\}`$ are also neighbors of $`P`$.

For any $`P^3`$ the orbit $`gP`$ is contained in an helicoidal curve $`H_{r,\alpha ,l}:=\{(r\mathrm{cos}(t\alpha ),r\mathrm{sin}(t\alpha ),\frac{l}{2\pi }t)^3:t\}`$. There is no loss of generality in fixing $`l=2\pi `$ and $`\alpha =0`$, hence using the notation $`H_r`$ for $`H_{r,0,2\pi }`$. We denote $`P_t=(r\mathrm{cos}(t),r\mathrm{sin}(t),t)`$ the point of $`H_r`$ for a certain parameter $`t`$, so that $`g^iP_t=P_{t+2\pi i/k}`$. We will prove that for any two points $`P_t`$ and $`P_t^{}`$ whose angular distance $`|tt^{}|`$ is less than $`2\pi `$, there is a sphere tangent to $`H_r`$ at these two points and not containing any other point of $`H_r`$. This implies the lemma.

To prove our claim, by symmetry considerations we can further assume that $`t^{}=t`$. Then, the two points in the claim are of the form $`P_{t_0}=(r\mathrm{cos}(t_0),r\mathrm{sin}(t_0),t_0)`$ and $`P_{t_0}=(r\mathrm{cos}(t_0),r\mathrm{sin}(t_0),t_0)`$ for a certain $`t_0(0,\pi )`$. The sphere tangent to $`H_r`$ at $`P_{t_0}`$ and $`P_{t_0}`$ will have center at a point $`O=(a,0,0)`$ which satisfies that the vectors

$$OP_{t_0}=(r\mathrm{cos}(t_0)a,r\mathrm{sin}(t_0),t_0)$$

and

$$(dP_t/dt)_{t=t_0}=(r\mathrm{sin}(t_0),r\mathrm{cos}(t_0),1)$$

are orthogonal. The equation

$$(r\mathrm{cos}(t_0)a)r\mathrm{sin}(t_0)r^2\mathrm{cos}(t_0)\mathrm{sin}(t_0)+t_0=0$$

gives the solution

$$a=\frac{t_0}{r\mathrm{sin}(t_0)}$$

We now prove that for any point $`P_t`$ other than $`P_{t_0}`$ or $`P_{t_0}`$ the distance from $`O`$ to $`P_t`$ is strictly bigger than the distance from $`O`$ to $`P_{t_0}`$. It suffices to consider $`t[\pi ,\pi ]`$ because $`d(O,P_{t\pm 2\pi })>d(O,P_t)`$ for any $`t[\pi ,\pi ]`$. Moreover, since $`d(O,P_t)=d(O,P_t)`$ we restrict our attention to $`t[0,\pi ]`$. We define the function

$$f(t):=d(O,P_t)^2d(O,P_{t_0})^2=\frac{2t_0(\mathrm{cos}(t)\mathrm{cos}(t_0))}{\mathrm{sin}(t_0)}+t^2t_{0}^{}{}_{}{}^{2}$$

whose first and second derivatives are

$$f^{}(t)=2t2\frac{t_0}{\mathrm{sin}(t_0)}\mathrm{sin}(t),f^{\prime \prime }(t)=22\frac{t_0}{\mathrm{sin}(t_0)}\mathrm{cos}(t).$$

We have

* $`f(t_0)=f^{}(t_0)=0`$ (as expected).
* $`f^{\prime \prime }(t_0)>0`$. For this, observe that $`f^{\prime \prime }(t_0)>0`$ is equivalent to $`\mathrm{sin}(t_0)t_0\mathrm{cos}(t_0)>0`$, which holds because the function $`g(t):=\mathrm{sin}(t)t\mathrm{cos}(t)`$ is zero at the origin and its derivative $`g^{}(t)=t\mathrm{sin}(t)`$ is strictly positive in $`(0,\pi )`$.
* $`f^{}`$ is injective in $`(0,\pi )`$. Indeed, if $`f^{}(t_1)=f^{}(t_2)`$ then $`\mathrm{sin}(t_1)/t_1=\mathrm{sin}(t_2)/t_2`$ and, in particular, the derivative of the function $`h(t):=\mathrm{sin}(t)/t`$ must have a zero between $`t_1`$ and $`t_2`$. But $`h^{}(t)=(t\mathrm{cos}(t)\mathrm{sin}(t))/t^2=0`$ would imply $`t=\mathrm{tan}(t)`$, which does not happen in the interval $`(0,\pi )`$.

With this we prove that $`f`$ achieves its unique minimum in the interval $`[0,\pi ]`$ at $`t=t_0`$, as follows: Claim (iii) implies that $`f^{\prime \prime }`$ is either always non-negative or always non-positive. By (ii) it is always non-negative. Claims (i) and (ii) imply that $`f`$ has a local minimum at $`t_0`$ which, by the previous observation, is the unique global minimum. ∎

Let $`G`$ be a crystallographic group of type $`P6_122`$. Its two metric parameters (which define $`G`$ modulo conjugation by an isometry) are the lengths $`l`$ and $`a`$ of its minimal translations in directions parallel and perpendicular, respectively, to the order-6 screw-rotation axes. As usual, we assume that the screw rotation axes are vertical, that is to say, parallel to the third coordinate axis. Also, assume that one of the minimal horizontal translations is parallel to the $`X`$-axis and that the $`X`$-axis itself is one of the horizontal order-2 rotation axes in $`G`$. This completely specifies the group $`G`$ (and agrees with Figures 15 and 16).

Let $`g`$ be the screw rotation of order twelve obtained substituting $`k=12`$ in Lemma 4.2. Observe that $`g^2G`$. Let $`\rho `$ be the order-2 rotation $`(x,y,z)(x,y,z)`$ which is in $`G`$ by hypothesis. Suppose now that our base point $`P`$ has coordinates $`(r\mathrm{cos}(\pi /12),r\mathrm{sin}(\pi /12),l/24)`$, so that $`\rho (P)=g^1(P)`$. Under these assumptions we have that the orbits of $`P`$ under the groups $`g`$ and $`\rho ,g^2G`$ coincide. By Lemma 4.2, the Voronoi diagram of this part of $`GP`$ alone produces $`24`$ neighbors of $`P`$. Now, if we fix the parameters $`l`$ and $`r`$ in the above description and make $`a`$ tend to infinity, the neighbors of $`P`$ in the Voronoi diagram of $`\rho ,g^2P`$ will keep being neighbors in $`GP`$. (Observe that $`GP`$ is obtained as the Minkowski sum of $`\rho ,g^2P`$ and a triangular grid of side $`a`$ in a horizontal plane). Moreover, since the regions in the Voronoi diagram of $`\rho ,g^2P`$ are unbounded, new neighbors are guaranteed to appear. Hence, the above construction is guaranteed to produce at least 25 neighbors.

We could try to argue geometrically how many “new” neighbors have to appear in the limit of $`a`$ going to infinity. For example, it is relatively easy to show that this number does not depend on the choice of $`l`$ and $`r`$. However, it seems easier to compute that number experimentally:

###### Example 4.3.

Taking $`l=12`$, $`r=1`$ and $`a=100`$ in the above setting (which gives $`P=(\mathrm{cos}(\pi /12),\mathrm{sin}(\pi /12),1/2)`$) one gets 31 neighbors. The number and identity of the neighbors is (experimentally) stable under increasing the value of $`a`$.

Even more, playing with different possibilities for the parameters we have found that:

###### Example 4.4.

The metric parameters $`l=100`$, $`a=950`$ and the base point $`P=(1,\mathrm{tan}(\pi /12),4)`$ produce a Dirichlet stereohedron with 32 neighbors. This stereohedron is very unstable. For example, changing the last coordinate of $`P`$ to be $`100/24=4.166`$, which would match exactly the above setting with $`r=1/\mathrm{cos}(\pi /12)`$, only 30 neighbors are obtained (and their identity changes drastically). Also, the parameter $`a`$ is not big enough for the number of neighbors to be the same for bigger values of $`a`$.

Figure 17 describes the points of the orbit which produce neighbors in each of the two examples. It shows the same decomposition of the plane into fundamental subdomains which appears in Figure 16. The grey subdomain is the one containing $`P`$. The points of the helicoidal orbit $`\rho ,g^2P`$ are those projecting to the regular hexagon. A plus (resp. a minus) in a subdomain means that the point of $`GP`$ projecting to that subdomain and lying in the upper (resp. lower) half of the band $`Z_P`$ is a neighbor of $`P`$. In the first example all the 24 possible neighbors within the hexagon appear, as predicted. In the second example only 16 of them appear, but this is compensated by more neighbors out of the hexagon.

The computations were made using a Maple program which first generates a sufficiently large number of points $`S`$ of the orbit $`GP`$ to guarantee that all the neighbors of $`P`$ lie in $`S`$ and then checks for each of them whether it is actually a neighbor or not. For the first step, it would be enough for example to use the two points in $`Z_P`$ in each of the subdomains which appear in Figure 16. For the second step, we express being a neighbor of $`P`$ as feasibility of a certain linear program.

The same ideas can be applied to groups having an order-4 screw rotation around a vertical axis and an order-2 rotation in a horizontal axis, with the two axes intersecting one another. One has to use Lemma 4.2 with $`k=8`$ and, hence, can only guarantee to obtain more than 16 neighbors. This is the way we constructed stereohedra with 18 facets for the group $`I\frac{4_1}{g}\frac{2}{m}\frac{2}{d}`$, hence showing that this is exactly the highest possible number of facets of Dirichlet stereohedra for groups with reflections (see \[2, Example 2.9\]).

Specially good is the group $`I4_122`$, whose graphical representation appears in part (a) of Figure 18. It has screw rotations or order-4 in the two versions ‘dextro’ and ‘levo’, and allows a point to be considered as lying in two different ‘helices’.

###### Example 4.5.

The following base point and metric parameters for a tetragonal group $`I4_122`$ produce Dirichlet stereohedra with 29 facets:

Minimal length of horizontal translation = 4

Minimal length of vertical translation = 1

Base point $`P=(1,\frac{1}{2},\frac{1}{16})`$, in the coordinate system of Figure 18 (a)

Part (b) of Figure 18 shows the 29 orbit points producing facets of the stereohedron, with the same conventions of the previous examples. The zero in one of the fundamental subdomains indicates that the corresponding neighbor is at the same height as the base point $`P`$.