Fedorov's Five Parallelohedra
We will see how some elegant ideas of Conway and Sloane, introduced in the 1990s, lead to Fedorov's determination of the five parallelohedra...
Introduction
The regular convex polyhedra, known as the Platonic solids, were classified by Euclid in the last book of the Elements. As is well known, they are the cube, icosahedron, dodecahedron, tetrahedron, and octahedron.
If we relax the condition that all the faces are congruent to allow two or more types of polygonal faces, we have the Archimedean solids, of which there are 13.
As the names imply, both groups of solids were known in antiquity. In this article, we will look at a result of Fedorov, published in 1885, that determines the five parallelohedra, solids whose translates can be arranged face-to-face to fill space. For instance, the cube is a parallelohedron since translates of the cube can fill space in the way that you might stack book boxes in a storage closet. In fact, the cube is the only Platonic solid that is a parallelohedron.
If we momentarily consider two dimensions, it has been known since antiquity that the only two-dimensional parallelohedra are parallelograms and centrally symmetric hexagons, that is, hexagons whose opposite sides are parallel.
In three dimensions, however, Fedorov found that there are exactly five 3-dimensional parallelohedra:
 |
 |
|
Truncated Octahedron |
Hexarhombic Dodecahedron |
 |
 |
 |
|
Rhombic Dodecahedron |
Hexagonal Prism |
Cuboid |
Of course, the hexagonal prism and the cube are simply the two-dimensional parallelohedra extended into three dimensions.
A portion of the space-filling arrangement of truncated octahedra looks like this:
Fedorov was motivated by a desire to describe the underlying structure of crystals, and his work is highly regarded among crystallographers for the mathematical basis he provided to their discipline. The article by Senechal and Galiulin, cited in the references, gives an interesting description of Fedorov's life and work.
This article explains the origin of the five parallelohedra. Rather than follow Fedorov's line of thought, however, we will see how some elegant ideas of Conway and Sloane, introduced in the 1990s, lead to Fedorov's result.
Parallelohedra and lattices
To explain Fedorov's classification, we will rely on an important result of Delone that, as we will now explain, connects parallelohedra with lattices.
Let's begin with a $n$-dimensional lattice $\Lambda$. Though much of what we see applies in generality, we will focus our attention on 3-dimensional lattices, and we will frequently illustrate important ideas using 2-dimensional lattices.
Given an element $\lambda$ of the lattice, we define its Voronoi cell $V(\lambda)$ to be the set of points whose distance to $\lambda$ is no more than the distance to any other lattice point. Of particular importance is the Voronoi cell $V(0)$, the Voronoi cell of the origin, shown in blue.
Notice that $V(0)$ is a parallelohedron since the other Voronoi cells $V(\lambda)$ are translates of $V(0)$ that fill the plane. Voronoi conjectured in 1908 that every $n$-dimensional parallelohedron is the Voronoi cell of some lattice, perhaps after applying an affine transformation. While this conjecture is still open for dimensions $n\geq 5$, Delone proved it in 1929 for dimensions $n\leq 4$.
Since we are interested here in 3-dimensional parallelohedra, it will therefore suffice to provide a classification of 3-dimensional lattices and their Voronoi cells.
Comments?
Lattices and Voronoi vectors
Given a lattice $\Lambda$, a Voronoi vector is a vector $v$ in the lattice such that the hyperplane that perpendicularly bisects $v$ intersects the Voronoi cell $V(0)$. The lattice shown has six Voronoi vectors.
We say that a Voronoi vector is strict if the hyperplane intersects $V(0)$ in an $(n-1)$-dimensional face of $V(0)$. Notice that all six Voronoi vectors in our example are strict.
By comparison, let's consider another lattice and its Voronoi cells:
Notice that there are now eight Voronoi vectors, but four of them, the ones shaded gray, are not strict. Any two of the Voronoi vectors that are not strict differ by twice a lattice vector.
Given a lattice vector $v$, the set $\overline{v}=v+2\Lambda$ consists of all vectors that differ from $v$ by twice a lattice vector. With these two examples in mind,
it is not difficult to show the following:
A nonzero vector $v$ is a Voronoi vector if and only if $v$ has the minimal length among all vectors in $\overline{v}=v+2\Lambda$.
A Voronoi vector $v$ is strict if and only if $v$ and $-v$ are the only minimal length vectors in $\overline{v}=v+2\Lambda$.
Comments?
Finding an obtuse superbase
To begin our classification of 3-dimensional lattices, it will be helpful to choose a basis $v_1,\ldots, v_n$
and add another vector $v_0$ such that $v_0 + v_1 + \ldots + v_n = 0$ to obtain a superbase.
Any element of $\Lambda$ may be represented in the superbase as $v=\sum_{i=0}^n m_iv_i$, though this representation is not unique. If $v\in 2\Lambda$, then all $m_i$ are even. This fact, along with $v_0+v_1+\ldots+v_n = 0$, implies that the set $\overline{v}=v+2\Lambda$ has exactly one element with $m_0 = 0$ and all other $m_i$ either 0 or 1. This means that there are $2^n$ distinct sets of the form $\overline{v}=v+2\Lambda$ and $2^n-1$ of them do not contain zero. Since each nonzero class $\overline{v}=v+2\Lambda$ contains at least two Voronoi vectors, the lattice $\Lambda$ has at least $2(2^n-1)$ Voronoi vectors.
Given a superbase $v_0,v_1,\ldots, v_n$ for our lattice $\Lambda$, we define $p_{ij}=-v_i\cdot v_j$ when $i\neq j$. We say that the superbase is obtuse if all $p_{ij}=-v_i\cdot v_j \geq 0$, meaning that any two vectors in the superbase form an obtuse angle. Furthermore, the superbase is strictly obtuse if $p_{ij} > 0$ for all $i\neq j$. The quantities $p_{ij}$ are known as the Selling parameters of the superbase.
In our examples, the superbase
|
|
 |
|
is strictly obtuse. |
is obtuse. |
For a vector $v$ in the lattice, we define $N(v)$ to be the length squared of $v$: $N(v)=|v|^2 = v\cdot v$. Remembering that $v_0 + v_1 + \ldots + v_n = 0$, we find the useful relationship: \[ \begin{eqnarray*} N\left(\sum_{i=0}^n m_iv_i\right) & = & \sum_{ij} m_im_j v_i\cdot v_j \\ & = & \sum_i m_i^2 v_i\cdot v_i + \sum_{i\neq j} m_im_j v_i\cdot v_j \\ & = & \sum_{i\neq j} m_i^2 v_i\cdot (-v_j) - \sum_{i < j} 2m_im_j p_{ij} \\ & = & \sum_{i < j} p_{ij}(m_i^2 -2m_im_j+m_j^2) \\ & = & \sum_{i < j} p_{ij}(m_i-m_j)^2 \end{eqnarray*} \]
If our superbase is obtuse (meaning that all $p_{ij} \geq 0$), then the norm $N(v)$ is minimized in a class $\overline{v}=v+2\Lambda$ when all $m_i$ are either 0 or 1. Therefore, if $S$ denotes a non-empty proper subset of $\{0,1,2,\ldots,n\}$, then $$v_S = \sum_{i\in S} v_i$$ is a Voronoi vector with $$N(v_S) = \sum_{i\in S, j\notin S} p_{ij} \equiv p_{S|\overline{S}}.$$
Moreover, if we assume that the superbase is strictly obtuse (meaning all $p_{ij} > 0$), then the $N(v)$ is minimized only when all $m_i$ are either 0 or 1. Therefore, the vectors $v_S$ are strict if and only if the superbase is strictly obtuse.
For convenience, we will usually write, $v_{\{i,j,\ldots\}}=v_{ij\ldots}$.
Comments?
Vonorms and conorms
It is useful to remember that a base $v_1,\ldots,v_n$ is determined, up to an isometry, by its Gram matrix, the matrix consisting of all inner products. For instance, if we have a basis $v_1,v_2,v_3$, its Gram matrix is: \[ \begin{eqnarray*} \left[ \begin{array}{ccc} v_1\cdot v_1 & v_1\cdot v_2 & v_1\cdot v_3 \\ v_2\cdot v_1 & v_2\cdot v_2 & v_2\cdot v_3 \\ v_3\cdot v_1 & v_3\cdot v_2 & v_3\cdot v_3 \\ \end{array} \right] & = & \left[ \begin{array}{ccc} p_{1|023} & -p_{12} & -p_{13} \\ -p_{21} & p_{2|013} & -p_{23} \\ -p_{31} & -p_{32} & p_{3|012} \end{array} \right] \\ & = & \left[ \begin{array}{ccc} p_{10}+p_{12}+p_{13} & -p_{12} & -p_{13} \\ -p_{21} & p_{20}+p_{21}+p_{23} & -p_{23} \\ -p_{31} & -p_{32} & p_{30}+p_{31}+p_{32} \end{array} \right]. \end{eqnarray*} \]
In other words, if we know the Selling parameters $p_{ij}$, then we know the Gram matrix, from which we can construct a base for the lattice. Therefore, our classification of 3-dimensional lattices will follow from understanding the possible sets of Selling parameters $\{p_{ij}\}$.
In addition, notice that the Selling parameters contain the same information as the $N(V_S)$; for example, \[ \begin{eqnarray*} N(v_{12})& =&(v_1+v_2)\cdot (v_1+v_2) \\ &=& N(v_1) + N(v_2) +2v_1\cdot v_2 \\ &=& N(v_1) + N(v_2) -2p_{12}. \end{eqnarray*} \]
As we will now see, Conway and Sloane describe an exceptionally elegant means of formalizing this fact, which enables us to move easily between the Selling parameters $p_{ij}$ and the norms of the Voronoi vectors $N(v_S)$.
Though much of what follows is true in general, we will tailor our discussion to 3-dimensional lattices since they are our ultimate interest and the statements are somewhat easier to verify.
By $\Lambda/2\Lambda$, we mean the set of all classes $\overline{v}=v+2\Lambda$. This is an $n$-dimensional vector space over the field ${\Bbb Z}_2$. The set of nonzero classes in $\Lambda/2\Lambda$ will be denoted by $P$, the projective plane of order 2. A line in $P$ is a two-dimensional space of $\Lambda/2\Lambda$. As shown below, there are seven points in $P$ and seven lines. Each point lies on three lines and each line contains three points.
To describe the lines of $P$, we will introduce the dual $(\Lambda/2\Lambda)^*$, the set of homomorphisms from $\Lambda/2\Lambda \to {\Bbb Z}_2 = \{\pm 1\}$; that is, $\chi:\Lambda/2\Lambda \to {\Bbb Z}_2$ where $\chi(u+v) = \chi(u)\chi(v)$. These homomorphisms are called characters on the lattice $\Lambda$.
To describe a character, we only need to specify which of the basis vectors $v_0,v_1, v_2$ and $v_3$ are sent to -1. For instance, $\chi_{13}$ is the homomorphism which satisfies $\chi_{13}(v_0) = 1$, $\chi_{13}(v_1) = -1$, $\chi_{13}(v_2) = 1$, and $\chi_{13}(v_3) = -1$. Since $v_0+v_1+v_2+v_3 = 0$, an even number of basis vectors must be sent to -1.
There is a one-to-one correspondence between the nonzero characters $\chi:\Lambda/2\Lambda \to {\Bbb Z}_2$ and the lines in $P$ by associating to $\chi$ the points whose image is 1. We therefore have the following configuration of points and lines in $P$.
We may now consider $P^*$, the dual projective plane, whose points are the non-zero characters $\Lambda/2\Lambda\to{\Bbb Z}_2$. There are seven points in $P^*$ since there are seven lines in $P$. The lines in $P^*$ correspond to the points in $P$; a point $\chi\in P^*$ lies on a line corresponding to the point $v \in P$ if $\chi(v) = 1$.
To each point in $\overline{v}=v+2\Lambda$ in $P$, we may associate its vonorm $\mbox{vo}(\overline{v})$, the square of the length of a shortest vector in $v+2\Lambda$. If we remember that $N(v_S) = p_{S|\overline{S}}$, the vonorm function looks like:
Correspondingly, we associate to each character $\chi$ its conorm $$ \mbox{co}(\chi) = -\frac 14\sum_{\overline{v}\in P} \chi(\overline{v})\mbox{vo}(\overline{v}). $$
For example, we find the pleasing relationship, which holds in general: $$ \begin{eqnarray*} \mbox{co}(\chi_{13})=&-\frac14& \left(\chi_{13}(v_0)\mbox{vo}(v_0) +\chi_{13}(v_1)\mbox{vo}(v_1) +\chi_{13}(v_2)\mbox{vo}(v_2) +\chi_{13}(v_3)\mbox{vo}(v_3) \\ +\chi_{13}(v_{12})\mbox{vo}(v_{12}) +\chi_{13}(v_{13})\mbox{vo}(v_{13}) +\chi_{13}(v_{23})\mbox{vo}(v_{23}) \right)\\ =&-\frac14&\left(p_{01}+p_{02}+p_{03} -p_{10}-p_{12}-p_{13}+p_{20}+p_{21}+p_{23} - p_{30}-p_{31}-p_{32} \\ -p_{10}-p_{13}-p_{20}-p_{23}+p_{10}+p_{12}+p_{30}+p_{32}-p_{20}-p_{21} -p_{30}-p_{31} \right) \\ = & p_{13} \end{eqnarray*} $$
Also, $\mbox{co}(\chi_{0123}) = 0$.
Therefore, the conorm function looks like this:
When we move from $P$ to its dual $P^*$, the vonorms $\mbox{vo}(\overline{v})$ are transformed into the conorms $\mbox{co}(\chi)$. This process may, of course, be reversed; that is, we may move from the dual $P^*$ to the dual $P$. In this case, we find, through a similar computation, that the conorms are transformed back into the vonorms by $$ \mbox{vo}(\overline{v}) = \sum_{\chi(\overline{v}) = -1} \mbox{co}(\chi). $$
This implies a significant fact that we will need momentarily:
The characters $\chi$ where $\mbox{co}(\chi)\neq 0$ cannot all lie on a line in $P^*$.
To see why this is true, suppose that all the characters where $\mbox{co}(\chi)\neq 0$ lie on a line in $P^*$. We have seen that lines in $P^*$ correspond to points $\overline{v}$ in $P$ and that a character $\chi$ lies on the line corresponding to $\overline{v}$ if $\chi(\overline{v}) = 1$. By our assumption, $\chi(\overline{v}) = 1$ for all characters for which $\mbox{co}(\chi)\neq 0$. Therefore, $\mbox{vo}(\overline{v}) = \sum_{\chi(\overline{v}) \neq 1} \mbox{co}(\chi) = 0$. But this is impossible since $\mbox{vo}(\overline{v})$ is the length of a shortest vector in $\overline{v}$, which cannot be zero.
Comments?
Constructing an obtuse superbase
Using the elegant tool provided by the introduction of the projective plane $P$ and its dual $P^*$, we will see that every 3-dimensional lattice $\Lambda$ has an obtuse superbase. Remember that this means $\mbox{co}(\chi_{ij}) = p_{ij}=-v_i\cdot v_j \geq 0$ when $i\neq j$.
Let's suppose that we have a superbase $v_0$, $v_1$, $v_2$, and $v_3$ that is not obtuse. We will describe a change of superbase that, when applied repeatedly, will lead to an obtuse superbase. Conway and Sloane illustrate this idea with an example, which we will follow.
Suppose our base $v_1$, $v_2$, and $v_3$ has the Gram matrix $$ \left[ \begin{array}{ccc} v_1\cdot v_1 & v_1\cdot v_2 & v_1\cdot v_3 \\ v_2\cdot v_1 & v_2\cdot v_2 & v_2\cdot v_3 \\ v_3\cdot v_1 & v_3\cdot v_2 & v_3\cdot v_3 \\ \end{array} \right] = \left[ \begin{array}{ccc} p_{1|023} & -p_{12} & -p_{13} \\ -p_{21} & p_{2|013} & -p_{23} \\ -p_{31} & -p_{32} & p_{3|012} \end{array} \right] = \left[ \begin{array}{ccc} 3 & 1 & 1 \\ 1 & 5 & 2 \\ 1 & 2 & 6 \end{array} \right]. $$
Adding the vector $v_0 = -v_1-v_2-v_3$, we find $$ \left[ \begin{array}{cccc} -p_{0|123} & p_{01} & p_{02} & p_{03} \\ p_{01} & -p_{1|023} & p_{12} & p_{13} \\ p_{02} & p_{21} & -p_{2|013} & p_{23} \\ p_{03} & p_{31} & p_{32} & -p_{3|012} \end{array} \right] = \left[ \begin{array}{ccc} -22 & 5 & 8 & 9 \\ 5 & -3 & -1 & -1 \\ 8 & -1 & -5 & -2 \\ 9 & -1 & -2 & -6 \end{array} \right]. $$
Notice that this is not an obtuse superbase since many of the Selling parameters are negative. We will describe a change of superbase that helps move us towards an obtuse superbase.
Let's put our example into the framework we've developed:
which in our case gives us:
In this example, we will focus on the value $p_{13} = -1$, which we write as $p_{13}=-\epsilon$ to indicate the more general situation. In other words, $\epsilon=1$ in what follows.
Now consider the following change of superbase: $$ v'_0 = v_{01},\quad v'_1 = -v_1,\quad v'_2 = v_{12},\quad v'_3=v_3,, $$
which leads to $$ v'_{12} = v_2,\quad v'_{23}=-v_0,\quad v'_{13}=v_3-v_1. $$
Notice that six of the seven Voronoi vectors in the new superbase are also Voronoi vectors in the old superbase. This means that only one vonorm will change: \[ \begin{eqnarray*} p'_{13|02} & = & v'_{13}\cdot v'_{13} = (v_3-v_1)\cdot(v_3-v_1) \\ & = & (v_3+v_1)\cdot(v_3+v_1) - 4v_1\cdot v_3 \\ & = & p_{13|02}+4p_{13} \\ & = & p_{13|02}-4\epsilon \\ \end{eqnarray*} \]
After applying a projective transformation to $P$, the change in vonorms is
Remember that $$\mbox{co}(\chi) = -\frac 14\sum_{\overline{v}} \chi(\overline{v})\mbox{vo}(\overline{v}) = \frac 14\left(\sum_{\chi(\overline{v})=-1} \mbox{vo}(\overline{v}) -\sum_{\chi(\overline{v})=1} \mbox{vo}(\overline{v}) \right). $$
Since $\chi(\overline{v}) = 1$ if $\overline{v}$ lies on the line corresponding to $\chi$ and $\chi(\overline{v}) = -1$ otherwise, we see that $\mbox{co}(\chi') = \mbox{co}(\chi) + \epsilon$ if $v_{13}$ lies on the line defined by $\chi$ and $\mbox{co}(\chi') = \mbox{co}(\chi) - \epsilon$ if not.
This changes the conorms in $P^*$ as shown, where the red line corresponds to the point $v_{13}$.
We may perform a sequence of similar superbase changes:
With this last step, we have arrived at a superbase where all conorms are non-negative. We have therefore constructed an obtuse superbase.
More generally, given any superbase for a lattice $\Lambda$, there is a sequence of superbase changes, as illustrated above, which produces an obtuse superbase. Since each step reduces one of the vonorms, the vonorms are always bounded by some constant. This implies the sequence of steps eventually stops at an obtuse superbase.
Comments?
Five 3-dimensional lattices
Considering the possibilities for the conorm function allows us to classify 3-dimensional lattices. Remember that $\mbox{co}(\chi_{0123}) = 0$ so there is always one zero conorm. Also, remember that the characters $\chi$ for which $\mbox{co}(\chi)\neq 0$ cannot lie on a line in $P^*$.
This means that the conorm function of an obtuse superbase for a lattice $\Lambda$ will have one of the following forms, perhaps after a projective transformation.
-
One conorm is zero. In this case, we have a strictly obtuse superbase. We will see that the Voronoi cell $V(0)$ is a truncated octahedron.
-
Two conorms are zero, and the Voronoi cell $V(0)$ is a hexarhombic dodecahedron.
-
Three collinear conorms are zero, and the Voronoi cell $V(0)$ is a rhombic dodecahedron.
-
Three non-collinear conorms are zero, and the Voronoi cell $V(0)$ is a hexagonal prism.
-
Four non-collinear conorms are zero, which produces a cuboid.
Let's begin with the first case in which our lattice has a strict obtuse superbase. Each Voronoi vector $v_S$ is therefore strict, which means that the perpendicular bisector of the vector $v_S$ contains a face of $V(0)$.
To exploit this observation, we will introduce a new coordinate system in which a 3-dimensional vector $x$ is described by the coordinate vector $$y = (y_0,y_1,y_2,y_3) = (x\cdot v_0, x\cdot v_1, x\cdot v_2, x\cdot v_3).$$
If, for example, we consider the Voronoi vector $v_0$, we know that the plane defined by $x\cdot v_0 = y_0 = \frac12 v_0\cdot v_0 = \frac12 p_{0|123}$ contains a face of $V(0)$. We will define this face to be $F_{0|123}$ and note that it is contained in the plane where $y_0=\frac12 p_{0|123}$.
More generally, a Voronoi vector $v_S$ defines a plane containing a face $F_{S|\overline{S}}$. We see that
-
$F_{i|jkl}$ is contained in the plane $y_i=\frac12 p_{i|jkl}$,
-
$F_{ij|kl}$ is contained in the plane $y_i+y_j = -y_k-y_l= \frac12p_{ij|kl}$, and
-
$F_{ijk|l}$ is contained in the plane $y_i+y_j+y_k=-y_l=\frac 12 p_{ijk|l}$.
It is fairly straightforward to see that $V(0)$ has 24 vertices $P_{ijkl}$, where $\{i,j,k,l\}$ is any permutation of $\{0,1,2,3\}$, having coordinates \[ \begin{eqnarray*} y_i&=&\frac12(p_{ij}+p_{ik}+p_{il}) \\ y_j&=&\frac12(-p_{ji}+p_{jk}+p_{jl}) \\ y_k&=&\frac12(-p_{ki}-p_{kj}+p_{kl}) \\ y_l&=&\frac12(-p_{li}-p_{lj}-p_{lk}) \\ \end{eqnarray*} \]
The face $F_{i|jkl}$ is hexagonal with vertices $P_{iabc}$ where $\{a,b,c\}$ is a permutation of $\{j,k,l\}$. Similarly, $F_{ij|kl}$ is a rhombic face with vertices $P_{ijkl}$, $P_{jikl}$, $P_{ijlk}$, and $P_{jilk}$. With a little work, we may conclude that $V(0)$ is a truncated octahedron.
Let's go back to our two-dimensional lattices for a moment:
Imagine we have a continous family of lattices that extrapolate between these two lattices so that $p_{12}\to 0$. We would see the two parallel short edges on the Voronoi cells shrink and disappear.
We may do the same thing with our truncated octahedron. Consider the family of lattices in which one conorm is multiplied by a parameter $t$, which decreases from 1 to 0.
One family of parallel edges shrinks and then disappears. The Voronoi cells end with a hexarhombic dodecahedron.
The three other 3-dimensional lattices arise in a similar fashion.
Summary
The use of the projective plane $P$ and its dual, introduced by Conway and Sloane, is a particularly elegant way to organize the relationship between the Selling parameters $p_{ij}$ and the lengths of the Voronoi vectors $v_S$.
In addition to explaining Fedorov's classification of the five three-dimensional parallelohedra, these ideas are also useful in studying lattices in other dimensions. For instance, in a subsequent paper, Conway and Sloane use similar techniques to classify the 52 four-dimensional lattices, a result originally found by Delone and subsequently corrected by Stogrin.
Comments?
References
-
J.H. Conway, N.J.A. Sloane, Low-dimensional lattices. VI. Voronoi reducation of three-dimensional lattices. Proceedings of the Royal Society of London A, 436, 55-68, 1992.
-
E.S. Fedorov, An Introduction to the Theory of Figures. Notices of the Imperial Petersburg Mineralogial Society, 2nd series, vol. 21, 1-279, 1885. (English translation in Symmetry of crystals, ACA Mongraph no. 7, 50-131, 1971.)
-
G.F. Voronoi, Nouvelles applications des paramètres continus à la théorie des formes quadratiques. J. reine angew. Math, 133, 97-178, 1908.
-
B.N. Delone, Sur la partition regulière de l'espace à 4-dimensions. Izv. Akad. Nauk SSSR Otdel. Fiz.-Mat. Nauk, 79-110 and 145-164, 1929.
-
M. Senechal, R.V. Galiulin, An Introduction to the Theory of Figures: the Geometry of E.S. Fedorov, Structural Topology, 10, 5-22, 1984.
David Austin 
