Content-Type: multipart/mixed; boundary="-------------0207250523865"
This is a multi-part message in MIME format.
---------------0207250523865
Content-Type: text/plain; name="02-323.comments"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="02-323.comments"
Slightly updated and corrected version of a paper published in
J. Phys. A: Math. Gen. 30 (1997) 2687-2698.
---------------0207250523865
Content-Type: text/plain; name="02-323.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="02-323.keywords"
similarity submodules, Dirichlet series
---------------0207250523865
Content-Type: application/x-tex; name="colour2.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="colour2.tex"
\documentclass[12pt,a4paper]{article}
\usepackage{amssymb}
\renewcommand{\baselinestretch}{1.13}
\newcommand{\bm}[1]{\mbox{\boldmath $#1$}}
\newcommand{\bms}[1]{\mbox{\footnotesize \boldmath $#1$}}
\newcommand{\zr}[1]{\mbox{\hspace*{#1em}}}
\newcommand{\Id}{\mbox{1\zr{-0.62}{\small 1}}}
\newcommand{\EE}{\mathbb E}
\newcommand{\NN}{\mathbb N}
\newcommand{\RR}{\mathbb R}
\newcommand{\CC}{\mathbb C}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\II}{\mathbb I}
\newcommand{\TT}{\mathbb T}
\newcommand{\QQ}{\mathbb Q}
\newcommand{\aaa}{\mathfrak a}
\newcommand{\N}{\mbox{N}}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\textwidth 15.3cm
\topmargin -1cm
\evensidemargin 0.5cm
\oddsidemargin 0.5cm
\input{epsf}
\begin{document}
\bibliographystyle{unsrt}
\parindent0pt
\begin{center}
{\large \bf Combinatorial aspects of colour symmetries}
\end{center}
\vspace{3mm}
\begin{center} {\sc Michael Baake}
\vspace{5mm}
Institut f\"ur Theoretische Physik, Universit\"at T\"ubingen, \\
Auf der Morgenstelle 14, D-72076 T\"ubingen, Germany\footnote{Address
since March 2001: Institut f\"ur Mathematik, Universit\"at Greifswald,
Jahnstr. 15a, 17487 Greifswald, Germany; Email: {\sf mbaake@uni-greifswald.de}}
\end{center}
\vspace{3mm}
\vspace{5mm}
\begin{abstract}
The problem of colour symmetries of crystals and quasicrystals is
investigated from its combinatorial point of view. For various lattices
and modules in two and three dimensions, the number of colourings
compatible with point and translation symmetry is given in terms of
Dirichlet series generating functions.
\end{abstract}
\parindent15pt
\vspace{15mm}
\subsection*{Introduction}
The concept of colour symmetry is a useful tool to investigate the
structure of discrete point sets (or related patterns) with additional
(scalar) degrees of freedom on top of each point, called colours.
To make this a bit more precise, let us consider a discrete point set
$\cal P$ in Euclidean space $\EE^n$. Let us
assume that each point shows one of finitely many colours.
Finally, define the local isomorphism class LI($\cal P$) as the class
of coloured point sets that are patch-equivalent with $\cal P$, i.e.\
the class of point sets $\cal P'$ with the property that arbitrarily large
patches of $\cal P'$ occur in $\cal P$ and vice versa.
Now, a Euclidean motion combined with a (global) permutation of colours
is called a (generalized) colour symmetry of LI($\cal P$) iff it maps
LI($\cal P$) into itself. The classification of these symmetries is a rather
difficult task, and has been studied extensively in two and three dimensions,
see \cite{Harker,Schwarz,Schwarz2} and references therein.
While being incomplete even in this crystallographic case,
things are much worse with non-crystallographic symmetries which are
of considerable interest in the theory of quasicrystals.
There are attempts
to find the colour symmetries with a small number of colours explicitly
\cite{Lueck}, and an approach via the Fourier transform can be used
algorithmically to calculate all possibilities up to a given number of
colours \cite{Ron}, but neither of these can give full answers.
There is another approach to colourings, based on the algebraic
structure of crystals and quasicrystals \cite{MP}, which can be used
to count the different possibilities to colour such structures in a way
that is compatible with its natural symmetry.
To expand on that, we will now consider the slightly more special case of
colour point symmetries where one colour occupies an object of the
same kind as the original, uncoloured one (e.g.\ it occupies a square
sublattice of the square lattice etc.) and all the other colours are translates
(i.e.\ they code the cosets or residue classes). Admittedly, this is only a subclass
of the colouring problem (compare with the discussion in \cite{Harker}),
but we will restrict our attention even further
to irreducible symmetries, such as $n$-fold symmetry in the plane ($n\geq 3$)
or cubic and icosahedral symmetry in 3-space. Nevertheless, this problem
should be of some interest because it can be solved
completely in 2D and to a large extent in 3D.
In the latter case, one has to extend the setup to the situation that one
colour occupies a sublattice (or submodule) with the same point symmetry
(which actually only means that the point symmetry groups under consideration
are conjugates of one another in $O(3)$). This is necessary because the
black-and-white colouring of $\ZZ^3$ (i.e.\ the 3D checkerboard lattice)
results in a face-centred Bravais type, but, obviously, should not be
excluded.
In this article, we start with the analysis of possibilities to achieve such
a colouring (which is a combinatorial problem) and postpone the determination
of the corresponding colour groups (which is a group theoretic problem),
together with some more general results, compare \cite{BM}, to a forthcoming
publication. The first part deals with the plane, where we explain the
setting with the familiar case of the square lattice and later present
other cases of interest. As we focus on applicability to quasicrystals,
we will actually have to talk about the colouring of modules rather than
of lattices in general.
The second part derives similar results for cubic lattices as well
as icosahedral modules, with additional material being presented
in the Appendix. In both cases, we also discuss in some
detail the relation between the three different Bravais classes that
can sit inside each other and give rise to colourings compatible with
cubic resp.\ icosahedral symmetry.
\subsection*{A warm-up exercise: the square lattice $\ZZ^2$}
Let us illustrate the problem and its solutions with a simple 2D example.
The only lattice in the Euclidean plane that shows fourfold symmetry
(described by the cyclic group $C_4$) is the square lattice resp.\ its
Bravais class, i.e.\ up to scaling and Euclidean motions, only
\be
\ZZ^2 \; = \; \{ (m,n) \mid m,n \in \ZZ \}
\ee
has $C_4$-symmetry. Due to invariance under reflection in the $x$-axis, the
full symmetry group is actually $D_4$, the dihedral group of order 8.
We now want to colour the lattice sites with finitely many pairwise different
colours in such
a way that the coloured version is still crystallographic (i.e.\ its periods
span the plane over the reals), one of the colours occupies a sublattice
which is still invariant under fourfold rotation (and hence of square
lattice type), while the other colours label the cosets.
To classify all possibilities, we thus have to know how many square sublattices
of $\ZZ^2$ of a given index $m$ exist (the cosets are unique).
Let us call this number $a_4^{}(m)$.
Clearly, $\ZZ^2$ contains many more sublattices than those we are
presently interested in: there are e.g.\ three sublattices of index 2,
only one of which is square while the other two have rectangular symmetry
only. Consequently, our numbers $a_4^{}(m)$ are smaller than the number
$f^{(2)}(m)$ of {\em all} sublattices of index $m$, given by \cite{Baake}
\be
f^{(2)}(m) \; = \; \sum_{d \mid m} d
\ee
where $d | m$ means $d$ divides $m$. Its Dirichlet series generating
function is ${\zeta(s) \zeta(s-1)}$ where $\zeta(s)$ is Riemann's
$\zeta$-function, see \cite{Hardy} or the Appendix.
This type of generating function is more appropriate
than the usual power series because $f^{(2)}(m)$ is a multiplicative
function, i.e.\ $f^{(2)}(1)=1$ and $f^{(2)}(mn)=f^{(2)}(m)f^{(2)}(n)$
whenever $m,n$ are coprime. This type of structure will also show up
in all other cases discussed in this article.
How can we select, from the sublattices of index $m$, those that are
square lattices? An efficient way, which also generalizes to other
planar symmetries, is through the observation that $\ZZ^2$ can be
seen as a ring of algebraic integers. In this case, we have
\be
\ZZ^2 \; = \; \ZZ[i] \; = \; \{ m + n i \mid m,n \in \ZZ \}
\ee
which are the so-called Gaussian integers \cite{Hardy}, the algebraic integers
in the quadratic field $\QQ(i)=\{p+qi \mid p,q \in \QQ \}$ (a field
extension of the rationals $\QQ$ of degree 2).
Sublattices now correspond to subgroups of finite index, and those
invariant under
fourfold rotation (i.e.\ under multiplication by $i$) correspond
to {\em ideals}. They are the subgroups $\aaa \subset \ZZ[i]$ with
$\gamma \aaa \subset \aaa$ for all $\gamma \in \ZZ[i]$, for background
material on the concepts and results used we refer to \cite{Lidl,Hardy,Wash}.
Consequently, counting all square sublattices of $\ZZ^2$ of index
$m$ is the same as counting all ideals of the ring $\ZZ[i]$ of finite index
$m$, where $m = \mbox{norm}(\aaa)$ is the (number theoretic) norm
of $\aaa$ (which equals the number of residue classes of $\aaa$
in $\ZZ[i]$). As the ring $\ZZ[i]$ is a principal ideal domain and commutative,
each ideal $\aaa$ is two-sided and generated by an element $\alpha \in
\ZZ[i]$, i.e.\
\be
\aaa \; = \; \alpha \ZZ[i]
\ee
for some $\alpha = k + \ell i$. But then, the norm of $\aaa$ simply reads
\be
\mbox{norm}(\aaa) \; = \; |\alpha|^2 \; = \; k^2 + \ell^2
\ee
which is the area of the fundamental domain of the
sublattice defined by $\alpha$.
The number of these ideals of index $m$ is our number $a_4^{}(m)$,
and it is a multiplicative function which is a consequence of
unique prime factorization (up to units) \cite{Hardy} in the ring $\ZZ[i]$.
Its generating function (of Dirichlet series type) is the Dedekind
$\zeta$-function of the field $K=\QQ(i)$
\be
\zeta_K^{}(s) \; = \; \sum_{\aaa}
\frac{1}{\mbox{norm}(\aaa)^s}
\; = \; \sum_{m=1}^{\infty}
\frac{a_4^{}(m)}{m^s}
\ee
where the first sum runs over all ideals $\aaa \neq \{0\}$. It reads explicitly
\begin{eqnarray}
\zeta^{}_{K}(s) & = &
\sum_{m=1}^{\infty} \frac{a_{4}^{}(m)}{m^s} \; = \;
\frac{1}{1-2^{-s}} \cdot
\prod_{p \equiv 1 \; (4)}
\frac{1}{(1-p^{-s})^2} \cdot
\prod_{p \equiv 3 \; (4)} \frac{1}{1-p^{-2s}} \\
& = & \mbox{\small $
1+{1\over2^s}+{1\over4^s}+{2\over5^s}+{1\over8^s}+{1\over9^s}+
{2\over10^s}+{2\over13^s}+{1\over16^s}+{2\over17^s}+{1\over18^s}+
{2\over20^s}+{3\over25^s} +{2\over26^s}+ \cdots $} \nonumber
\end{eqnarray}
One can easily derive an explicit expression for the coefficients.
The result is $a_4^{}(1)=1$, $a_4^{}(2^r)=1$, $a_4^{}(mn)=a_4^{}(m)a_4^{}(n)$
for $m,n$ coprime (multiplicativity of $a_4^{}(m)$), $a_4^{}(p^r)=r+1$ for
$p\equiv 1\; (4)$, and, finally, $a_4^{}(p^{2r})=1$ and $a_4^{}(p^{2r-1})=0$
for $p\equiv 3\; (4)$.
A Dirichlet series generating function allows for the determination of
the asymptotic behaviour of the coefficients through the residue of the
$\zeta$-function at its right-most pole in the complex $s$-plane ($s=1$
in this case). The result is that the {\em average} value of $a_4^{}(m)$
is constant, namely $\pi/4$. In other words, the number of possibilities
to colour the square lattice with less than $N$ colours (and with our general
restrictions discussed above) is asymptotically $\pi N/4$.
\subsection*{More generality: other planar cases}
Having desribed the square lattice in detail, we shall now generalize
our approach to other $\ZZ$-modules of the plane, namely those with
$n$-fold rotational symmetry, $n>2$. Though many things are similar here,
the number theoretic background is a lot more involved, see \cite{Wash}.
Let us nevertheless consider the $\ZZ$-span of a regular $n$-star,
\be \label{module}
{\cal M}_n \; := \; \ZZ\cdot 1 + \ZZ\cdot\xi + \ldots + \ZZ\cdot\xi^{n-1} \, ,
\ee
where $\xi=\exp(2\pi i/n)$. This is called the standard $n$-fold symmetric
module of the plane \cite{Mermin}. It is a $\ZZ$-module of rank $\phi(n)$,
where $\phi$ denotes Euler's totient function \cite{Hardy}, and it is
discrete (i.e.\ a lattice) only for $n=3,4,6$. Note that ${\cal M}_3 = {\cal M}_6$,
and, in general, ${\cal M}_n = {\cal M}_N$ where $N$ is defined as
$n$ resp.\ $2n$ for $n$ even resp.\ odd. So, the module ${\cal M}_n$ has
$N$-fold rotational symmetry.
The cases with $n=5$ and $n\geq 7$ correspond to 2D quasicrystals or
other nonperiodic Delone sets, where they show up as the
so-called limit translation
modules \cite{BS} of the discrete structures. Consequently, as discussed
in detail in \cite{PBR}, these modules are the universal objects, and the
colouring problem has to be solved for them. The results then apply
to each translation class of points of the corresponding Delone set
separately.
Now, how does the definition (\ref{module}) help?
The first observation is that ${\cal M}_n = \ZZ[\xi]$ is the ring of
cyclotomic integers in the cyclotomic field $\QQ(\xi)$ (see \cite{Wash}
for details), and the second is that the subgroups we need (i.e.\
those with $N$-fold symmetry) are again {\em ideals} of $\ZZ[\xi]$.
So, it is helpful to know the Dedekind $\zeta$-function of $\QQ(\xi)$
which is the Dirichlet series generating function of the numbers of
ideals of a given index.
In what follows, we will list some examples, including all those related
to 2D quasicrystals found so far. They share another special property
with other cases of small $n$, namely the uniqueness of the ideal
class. This means that, for fixed $n$, all ideals are equal up to a
similarity transformation, or, in other words, there is only one
Bravais-type of $n$-fold symmetric modules of the plane \cite{Mermin}
of rank $\phi(n)$. This is true of
precisely 29 planar modules, namely those with \newline
\centerline{$n = 3,4,5,7,8,9,11,12,13,15,16,17,19,20,21,$}
\centerline{$24,25,27,28,32,33,35,36,40,44,45,48,60,84$}
(where $n\not\equiv 2$ mod 4 to avoid double counting),
see theorem 11.1 of \cite{Wash}.
The necessary material for the actual calculation of the $\zeta$-functions
can be found in section III of \cite{PBR} and will not be
repeated here. In what follows, we just summarize the results for
several important 2D lattices and modules.
\subsubsection*{The triangular lattice}
The triangular lattice (with sixfold symmetry) is a scaled down
version of the root lattice $A_2$ and coincides with the ring of Eisenstein
integers \cite{Hardy}. They are the algebraic integers in the
quadratic field $K=\QQ(\sqrt{-3}\,)$.
The corresponding $\zeta$-function reads
\begin{eqnarray}
\zeta^{}_{K}(s) & = &
\sum_{m=1}^{\infty} \frac{a_{6}^{}(m)}{m^s} \; = \;
\frac{1}{1-3^{-s}} \cdot
\prod_{p \equiv 1 \; (3)}
\frac{1}{(1-p^{-s})^2} \cdot
\prod_{p \equiv 2 \; (3)} \frac{1}{1-p^{-2s}} \\
& = & \mbox{\small $
1+{1\over3^s}+{1\over4^s}+{2\over7^s}+{1\over9^s}+{1\over12^s}+
{2\over13^s}+{1\over16^s}+{2\over19^s}+{2\over21^s}+{1\over25^s}+
{1\over27^s}+{2\over28^s} + \cdots $} \nonumber
\end{eqnarray}
The explicit expressions for the coefficients are $a_6^{}(1)=1$,
$a_6^{}(3^r)=1$, $a_6^{}(mn)= a_6^{}(m) a_6^{}(n)$ for $m,n$
coprime, $a_6^{}(p^r)=r+1$ for $p\equiv 1\; (3)$, and finally,
for $p\equiv 2\; (3)$, one has $a_6^{}(p^{2r})=1$ and
$a_6^{}(p^{2r-1})=0$. The average value of $a_6^{}(m)$ is
asymptotically $\pi/3\sqrt{3}$.
\subsubsection*{Fivefold symmetry}
The fivefold module in the plane, ${\cal M}_5$, is the ring
of algebraic integers in the field $K=\QQ(\xi)$, with $\xi = e^{2 \pi i/5}$.
Its $\zeta$-function reads
\begin{eqnarray}
\zeta^{}_{K}(s) & = &
\sum_{m=1}^{\infty} \frac{a_{10}^{}(m)}{m^s} \; = \; \\
& = & \frac{1}{1-5^{-s}} \cdot
\prod_{p \equiv 1 \; (5)}
\frac{1}{(1-p^{-s})^4} \cdot
\prod_{p \equiv -1 \; (5)}
\frac{1}{(1-p^{-2s})^2} \cdot
\prod_{p \equiv \pm 2 \; (5)} \frac{1}{1-p^{-4s}} \nonumber \\
& = & \mbox{\small $
1+{1\over5^s}+{4\over11^s}+{1\over16^s}+{1\over25^s} +
{4\over31^s}+{4\over41^s}+{4\over55^s}+{4\over61^s}+
{4\over71^s}+{1\over80^s}+{1\over81^s}+{4\over101^s} +
\cdots $} \nonumber
\end{eqnarray}
As before, the coefficients $a_{10}^{}(m)$ can be given explicitly. Due to
their multiplicativity, it is sufficient to know them for prime powers.
The result is $a_{10}^{}(1)=1$; $a_{10}^{}(5^r) = 1$;
$a_{10}^{}(p^r) = (r+1)(r+2)(r+3)/6$
for $p \equiv 1 \; (5)$; $a_{10}^{}(p^{2r+1}) = 0$ and
$a_{10}^{}(p^{2r}) = r+1$ for $p \equiv 4 \; (5)$; finally,
$a_{10}^{}(p^{4r}) = 1$ and $a_{10}^{}(p^{4r-\ell})=0$ (with $\ell=1,2,3$)
for $p \equiv \pm 2 \; (5)$.
The average value of $a_{10}^{}(m)$ is asymptotically
$4 \pi^2 \log(\tau)/25 \sqrt{5} \simeq 0.339837$.
\subsubsection*{Sevenfold symmetry}
Before we complete the examples related to quadratic irrationalities,
let us give at least one example of a more complicated structure,
namely that of sevenfold (and hence also fourteenfold) symmetry.
Here, $K=\QQ(e^{2\pi i/7})$, and the $\zeta$-function reads:
{\hfuzz 2pt
\begin{eqnarray}
\zeta^{}_{K}(s) & = &
\sum_{m=1}^{\infty} \frac{a_{14}^{}(m)}{m^s} \nonumber \\
& = & \frac{1}{1-7^{-s}} \cdot
\prod_{p \equiv 1 \; (7)} \frac{1}{(1-p^{-s})^6} \cdot
\prod_{p \equiv 3 \; \mbox{\footnotesize or } 5 \; (7)}
\frac{1}{1-p^{-6s}} \cdot \\
& & \prod_{p \equiv 2 \; \mbox{\footnotesize or } 4 \; (7)}
\frac{1}{(1-p^{-3s})^2} \cdot
\prod_{p \equiv 6 \; (7)} \frac{1}{(1-p^{-2s})^3} \cdot
\nonumber \\
& = & \mbox{\small $
1+{1\over7^s}+{2\over8^s}+{6\over29^s}+{6\over43^s}+
{1\over49^s}+{2\over56^s}+{3\over64^s}+{6\over71^s}+{6\over113^s}+
{6\over127^s}+{3\over169^s}+{6\over197^s}+ \cdots $} \nonumber
\end{eqnarray} }
Since it is clear how to derive explicit formulas for the coefficients by
suitable manipulations with geometric series, we suppress such details
from now on. Also, the asymptotic behaviour can be calculated along the
lines mentioned above, see \cite{PBR} for details.
\subsubsection*{Eightfold symmetry}
Here, we obtain, with $K=\QQ(e^{2\pi i/8})$:
\begin{eqnarray}
\lefteqn{ \zeta^{}_{K}(s) \; = \;
\sum_{m=1}^{\infty} \frac{a_{8}^{}(m)}{m^s} }\\
& = & \frac{1}{1-2^{-s}} \cdot
\prod_{p \equiv 1 \; (8)}
\frac{1}{(1-p^{-s})^4} \cdot
\prod_{p \equiv -1 \; (8)}
\frac{1}{(1-p^{-2s})^2} \cdot
\prod_{p \equiv \pm 3 \; (8)}
\frac{1}{(1-p^{-2s})^2} \nonumber \\
& = & \mbox{\small $
1+{1\over2^s}+{1\over4^s}+{1\over8^s}+{2\over9^s}+{1\over16^s}+
{4\over17^s}+{2\over18^s}+{2\over25^s}+{1\over32^s}+{4\over34^s}+
{2\over36^s}+{4\over41^s}+{2\over49^s} + \cdots $} \nonumber
\end{eqnarray}
\subsubsection*{Twelvefold symmetry}
The cyclotomic field is now $K=\QQ(e^{2\pi i/12})$, and the $\zeta$-function
reads
\begin{eqnarray}
\lefteqn{ \zeta^{}_{K}(s) \; = \;
\sum_{m=1}^{\infty} \frac{a_{12}^{}(m)}{m^s} }\\
& = & \frac{1}{1-4^{-s}} \cdot \frac{1}{1-9^{-s}}
\prod_{p \equiv 1 \; (12)}
\frac{1}{(1-p^{-s})^4} \cdot
\prod_{p \equiv -1 \; (12)}
\frac{1}{(1-p^{-2s})^2} \cdot
\prod_{p \equiv \pm 5 \; (12)}
\frac{1}{(1-p^{-2s})^2} \nonumber \\
& = & \mbox{\small $
1+{1\over4^s}+{1\over9^s}+{4\over13^s}+{1\over16^s}+{2\over25^s}+
{1\over36^s}+{4\over37^s}+{2\over49^s}+{4\over52^s}+{4\over61^s}+
{1\over64^s}+{4\over73^s}+{1\over81^s} + \cdots $} \nonumber
\end{eqnarray}
At this point, we close the section on 2D examples. More can be worked
out explicitly with the material of section III of \cite{PBR} and
the general theory as explained in sections 1-4 and 11 of \cite{Wash}.
In Table~\ref{counts}, the numbers $a_N^{}(m)$ up to $m=30$ are
summarized for various $N$.
\begin{center}
\begin{table}
$$\begin{array}{|r|rrrrrr|}
\hline
m & a_4^{}(m) & a_6^{}(m) & a_{8}^{}(m) &
a_{10}^{}(m) & a_{12}^{}(m) & a_{14}(m) \\
\hline
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
2 & 1 & 0 & 1 & 0 & 0 & 0 \\
3 & 0 & 1 & 0 & 0 & 0 & 0 \\
4 & 1 & 1 & 1 & 0 & 1 & 0 \\
5 & 2 & 0 & 0 & 1 & 0 & 0 \\
6 & 0 & 0 & 0 & 0 & 0 & 0 \\
7 & 0 & 2 & 0 & 0 & 0 & 1 \\
8 & 1 & 0 & 1 & 0 & 0 & 2 \\
9 & 1 & 1 & 2 & 0 & 1 & 0 \\
10 & 2 & 0 & 0 & 0 & 0 & 0 \\
11 & 0 & 0 & 0 & 4 & 0 & 0 \\
12 & 0 & 1 & 0 & 0 & 0 & 0 \\
13 & 2 & 2 & 0 & 0 & 4 & 0 \\
14 & 0 & 0 & 0 & 0 & 0 & 0 \\
15 & 0 & 0 & 0 & 0 & 0 & 0 \\
16 & 1 & 1 & 1 & 1 & 1 & 0 \\
17 & 2 & 0 & 4 & 0 & 0 & 0 \\
18 & 1 & 0 & 2 & 0 & 0 & 0 \\
19 & 0 & 2 & 0 & 0 & 0 & 0 \\
20 & 2 & 0 & 0 & 0 & 0 & 0 \\
21 & 0 & 2 & 0 & 0 & 0 & 0 \\
22 & 0 & 0 & 0 & 0 & 0 & 0 \\
23 & 0 & 0 & 0 & 0 & 0 & 0 \\
24 & 0 & 0 & 0 & 0 & 0 & 0 \\
25 & 3 & 1 & 2 & 1 & 2 & 0 \\
26 & 2 & 0 & 0 & 0 & 0 & 0 \\
27 & 0 & 1 & 0 & 0 & 0 & 0 \\
28 & 0 & 2 & 0 & 0 & 0 & 0 \\
29 & 2 & 0 & 0 & 0 & 0 & 6 \\
30 & 0 & 0 & 0 & 0 & 0 & 0 \\
\hline
\end{array}$$
\caption{Number of colourings for various planar symmetries}
\label{counts}
\end{table}
\end{center}
\subsection*{3D: The cubic Bravais classes}
Let us consider the so-called primitive cubic lattice, represented by $\ZZ^3$.
This is also called $P$-type for short.
It is only one of three possible Bravais classes with cubic symmetry $O_h$,
the other two being the face-centred cubic ($f\!cc$ or $F$-type)
and the body-centred cubic ($bcc$ or $B$-type) ones.
This shows one immediate complication: sublattices with cubic
symmetry may be of different Bravais type! In fact, inside $\ZZ^3$ there is
one $F$-type sublattice of index 2
($\Gamma_F = \{(m_1,m_2,m_3) \mid m_1+m_2+m_3 \mbox{ even}\}$)
and one $B$-type sublattice of index 4
($\Gamma_B = \{(m_1,m_2,m_3) \mid m_1 \equiv m_2 \equiv m_3 \; (2)\}$).
Consequently, it is natural to attack our problem in two steps, first
focusing on a single Bravais class and later extending to all of them.
Again, the focus is on those cases where one colour occupies a sublattice
(compare \cite{Harker} for the more general situation). Let us thus
first ask for sublattices of $P$-type, i.e.\ we ask for rotations $R$,
followed by a homothety $\alpha > 0$, such that
\be
\alpha R \ZZ^3 \; \subset \; \ZZ^3 \, .
\ee
Note that we need neither consider reflections, as they can always be written
as $-R$ and inversion is a lattice symmetry, nor negative $\alpha$, for the same
reason. Also, $\alpha=0$ would not give us a 3D lattice.
If we now use the standard basis $\bm{e}_1,\bm{e}_2,\bm{e}_3$ and write
$\ZZ^3 = \ZZ\bm{e}_1 \oplus \ZZ\bm{e}_2 \oplus \ZZ\bm{e}_3$, we are actually
asking for all $R\in SO(3)$ and $\alpha >0$ such that $\alpha R$ has integer
entries only.
Now, if $\alpha R$ is integral, so is its transpose, and
$\alpha R (\alpha R)^t = \alpha^2 \,\Id\,$ implies $\alpha^2 \in \NN$.
On the other hand, $\det(\alpha R)=\alpha^3$ is also in integer.
Therefore, $\alpha = \alpha^3/\alpha^2$ must be rational. But, as its square
is an integer, $\alpha$ itself must be an integer, and then the rotation
matrix $R$ can only have rational entries, i.e.\ $R \in SO(3,\QQ)$.
Then, $\alpha$ must actually be an integer multiple of the denominator
of $R$ (being the smallest integer $m$ such that $m R$ is integral),
see \cite{BM} for a more detailed discussion.
Let us pause to remark that the same type of argument can be used
for $\ZZ^n$ with arbitrary $n$. If $n$ is {\em odd}, one finds that $\alpha R$
maps to a $P$-type sublattice if and only if $R\in SO(n,\QQ)$ and
$\alpha$ is an integer multiple of the denominator of $R$. If, however,
$n$ is {\em even}, we can also get solutions where $\alpha$ is a quadratic
irrationality (and only $R^2 \in SO(n,\QQ)$), as happened above in the case of
the square lattice.
Our combinatorial problem in 3D can now be solved it we know the
number of $SO(3,\QQ)$-matrices with a given denominator.
This number is known
from the solution of a different, but closely related problem, namely
that of the coincidence rotations of the cubic lattice, compare
\cite{BP} and references therein. The corresponding Dirichlet series generating
function $\Phi_{cub}(s)$ is repeated in the Appendix for convenience.
Let us now derive the generating function for the number of cubic
sublattices of $\ZZ^3$. There are three different sources for them.
First, for each $R\in SO(3,\QQ)$, we have one solution of the form
$\Gamma = \mbox{den}(R) \cdot R \ZZ^3$ (with $\mbox{den}(R)^3$
different colours, namely one for $\Gamma$ and each of its cosets).
This same solution is obtained by altogether 24 pairwise different
$SO(3,\QQ)$-matrices, because $SO(3,\ZZ)$ (the rotation symmetry
group of $\ZZ^3$) contains 24 elements. The generating function for
these cases is obviously $\Phi_{cub}(3s)$.
Next, for each such $\Gamma$, we also have the sublattice $m\Gamma$
for each $m\in\NN$, and none of those, except $\Gamma$ itself, has been
counted yet. Since the number of colours for $m\Gamma$ is $m^3$ times
as large as that for $\Gamma$, our generating function gets multiplied by
$\zeta(3s)$ to account for these possibilities. This exhausts the $P$-type
sublattices of $\ZZ^3$ wherefore
\begin{eqnarray}
F(s) & = &\zeta(3s)\Phi_{cub}(3s) \\
& = & \mbox{\small $
1 + {1\over8^s} + {5\over27^s} + {1\over64^s} +
{7\over125^s} + {5\over216^s} + {9\over343^s} +
{1\over512^s} + {17\over729^s} + {7\over1000^s} +
{13\over1331^s} + \cdots $} \nonumber
\end{eqnarray}
is the proper generating function for them.
Finally, one can also find, as explained earlier, an $F$-type and a $B$-type
sublattice in each of the $P$-type cubic ones, which results in an
overall factor $1 + 2^{-s} + 4^{-s}$. Altogether this gives the
generating function
\begin{eqnarray} \label{cubgenfun}
F_{cub}(s) & = & (1 + 2^{-s} + 4^{-s})
\cdot \zeta(3s) \cdot \Phi_{cub}(3s) \\
& = & \mbox{\small $
1+{1\over2^s}+{1\over4^s}+{1\over8^s}+{1\over16^s}+{5\over27^s}+
{1\over32^s}+{5\over54^s}+{1\over64^s}+{5\over108^s}+{7\over125^s}+
{1\over128^s} + \cdots $} \nonumber
\end{eqnarray}
The Bravais type can be determined as follows. If $m$ is a possible number
of colours (i.e.\ the denominator of a fraction with non-zero numerator),
and if $s$ is the largest integer such that $2^s | m$, then the colouring
is based on $P$-, $F$- or $B$-type if $s$ is congruent (mod 3) to
0, 1 or 2, respectively. The answer for the other cubic lattices is
similar, with the roles of $P$, $F$ and $B$ and the prefactor in
(\ref{cubgenfun}) appropriately changed (note that $\Gamma^{}_B$ as
defined above is not a sublattice of $\Gamma^{}_F$).
\subsection*{3D: The icosahedral modules of rank 6}
It is well known that there are three different icosahedral modules
in 3-space, which can be obtained as projections of the three types
of hypercubic lattices in 6-space. They are thus called $B$-, $P$-
and $F$-type for body-centred, primitive and face-centred, respectively.
It is convenient to describe them in an orthogonal basis
$\bm{e}_1^{}, \bm{e}_2^{}, \bm{e}_3^{}$ of twofold
axes of the icosahedron. With $\alpha_i \in \ZZ[\tau]$,
$\tau = (1 + \sqrt{5})/2$ the golden ratio,
the $B$- and $F$-type modules then read
\begin{eqnarray*} \label{ico1}
{\cal M}_B & = & \{ \mbox{$\sum_{i=1}^{3}$} \alpha_i \bm{e}_i \mid
\tau^2\alpha_1^{} + \tau\alpha_2^{} + \alpha_3^{} \equiv 0 \; (2) \} \, , \\
{\cal M}_F & = & \{ \, \bm{x} \in {\cal M}_B \mid
\alpha_1^{} + \alpha_2^{} + \alpha_3^{} \equiv 0 \; (2) \} \, .
\end{eqnarray*}
Clearly, ${\cal M}_F$ is a submodule of ${\cal M}_B$ of index 4, and
both are $\ZZ$-modules of rank 6, but also $\ZZ[\tau]$-modules of
rank 3. In particular, they are both invariant under multiplication by $\tau$.
In between these two modules, there is also a $P$-type module, or
in fact there are three different ones of this type (all three on
different scales), namely
\begin{eqnarray} \label{ico2}
{\cal M}_P^{(1)} & = & \{ \, \bm{x} \in {\cal M}_B \mid
\alpha_1^{} + \alpha_2^{} + \alpha_3^{}
\equiv 0 \mbox{ or } 1 \; (2) \} \, , \nonumber \\
{\cal M}_P^{(2)} & = & \{ \, \bm{x} \in {\cal M}_B \mid
\alpha_1^{} + \alpha_2^{} + \alpha_3^{}
\equiv 0 \mbox{ or } \tau \; (2) \} \, , \\
{\cal M}_P^{(3)} & = & \{ \, \bm{x} \in {\cal M}_B \mid
\alpha_1^{} + \alpha_2^{} + \alpha_3^{}
\equiv 0 \mbox{ or } \tau^2 \; (2) \} \, . \nonumber
\end{eqnarray}
They are again $\ZZ$-modules of rank 6, but not $\ZZ[\tau]$-modules
because they are not invariant under multiplication by $\tau$. In fact,
as $\tau {\cal M}_P^{(1)} = {\cal M}_P^{(2)}$ etc., they form a 3-cycle
under multiplication by $\tau$. Nevertheless, together with
$\ZZ[\tau]^3 = \ZZ[\tau]\bm{e}_1^{} + \ZZ[\tau]\bm{e}_2^{} +
\ZZ[\tau]\bm{e}_3^{}$, we have the inclusion
\be \label{inclu}
2 \ZZ[\tau]^3 \stackrel{4}{\subset} {\cal M}_F^{}
\stackrel{2}{\subset} {\cal M}_P^{(i)} \stackrel{2}{\subset}
{\cal M}_B^{} \stackrel{4}{\subset} \ZZ[\tau]^3
\ee
for $i=1,2,3$, where the integer on top of the inclusion symbol denotes
the corresponding index, e.g.\ ${\cal M}_B$ is a submodule of $\ZZ[\tau]^3$
of index 4 which means that $\ZZ[\tau]^3$ is a disjoint union of ${\cal M}_B$
and three cosets of it.
Let us now consider the colouring problem for the module ${\cal M}_B$
and let us assume that we know all submodules $\Lambda$ of the same
Bravais type which are maximal in the sense that
$\alpha\Lambda \subset {\cal M}_B$ implies $\alpha \in \ZZ[\tau]$.
But then, as $\Lambda$ itself must be a $\ZZ[\tau]$-module, each
$\alpha\in\ZZ[\tau]$ is possible, and the corresponding group-subgroup
index is
\be \label{index1}
[ \Lambda : \alpha\Lambda] \; = \; |\N(\alpha)^3|
\ee
where $\N(\gamma)$ denotes the (number theoretic) norm in the
quadratic field $\QQ(\tau)$. For $\gamma=p+q\tau$ it reads
\be \label{norm}
\N(\gamma) \, := \, \gamma\gamma' \, = \, p^2 + p q - q^2
\ee
where $\gamma'=p+q\tau'$ is the algebraic conjugate of $\gamma$
defined through $\tau' = -1/\tau = 1 - \tau$.
In particular, Eq.~(\ref{index1}) says that
$\alpha\Lambda$ requires $|\N(\alpha)^3|$ times as many colours as
$\Lambda$. The number of {\em different} solutions obtained this way
is in one-to-one correspondence with the ideals of $\ZZ[\tau]$,
which are counted by the $\zeta$-function $\zeta^{}_{\QQ(\tau)}(s)$,
see the Appendix. So, this contributes a factor $\zeta^{}_{\QQ(\tau)}(3s)$
to the generating function of the colouring problem.
Now, we have to determine the maximal submodules $\Lambda$ of
$B$-type. Before we do that, let us briefly look at the related
colouring problem for the (modulated cubic) module
$\ZZ[\tau]^3 = \ZZ^3 \oplus \tau \ZZ^3$. Consider a rotation
$R$ and a stretching factor $\alpha$ such that
\be
\alpha R \ZZ[\tau]^3 \, \subset \, \ZZ[\tau]^3 \, .
\ee
Then, by an analogous argument to that
of the cubic case, we may conclude that both $\alpha^2$
and $\alpha^3$ are in $\ZZ[\tau]$, and hence $\alpha\in\QQ(\tau)$.
But, from (\ref{norm}), $\N(\alpha)\in\QQ$ and $\N(\alpha^2)=
\N(\alpha)^2\in\ZZ$, hence $\N(\alpha)\in\ZZ$ which implies
$\alpha\in\ZZ[\tau]$. Consequently, $R\in SO(3,\QQ(\tau))$,
and we then conclude, very much as in the case of the cubic lattice
$\ZZ^3$, that the only (linear) similarity transformations
that map $\ZZ[\tau]^3$ into itself are $\ZZ[\tau]$-multiples
of $\mbox{den}(R) R$, where $\mbox{den}(R)$ is the greatest common divisor
of all $\beta \in \ZZ[\tau]$ with $\beta R$ integral.
Note that $SO(3,\QQ(\tau))$ is the group
of coincidence rotations of $\ZZ[\tau]^3$ (and simultaneously of
the icosahedral module ${\cal M}_B$), see \cite{BP,Baake} for details.
{}From here, one can calculate the generating function of the different
colourings \cite{BM}, using explicit results from \cite{Baake}.
Instead of going into details there, let us now consider the icosahedral
module ${\cal M}_B$, and a similarity transformation $\alpha R$ such that
\be
\alpha R {\cal M}_B \, \subset \, {\cal M}_B\, .
\ee
From (\ref{inclu}) it follows that then also $\alpha R {\cal M}_B
\subset \ZZ[\tau]^3$ and hence
$\alpha R (2 \ZZ[\tau]^3) \subset \ZZ[\tau]^3$, which
means that $2 \alpha R$ must have $\ZZ[\tau]$ entries only.
This is a necessary (but not sufficient) condition, while
$\alpha R$ integral is certainly sufficient, but not necessary.
In any case, we can conclude that $2 \alpha \in \ZZ[\tau]$ and
$R\in SO(3,\QQ(\tau))$ is a rational matrix.
For each $R\in SO(3,\QQ(\tau))$ we thus obtain one maximal
${\cal M}_B$-submodule $\Lambda$, and precisely 60 different $R$'s
will result in the
same $\Lambda$ as there are 60 rotation symmetries of the icosahedron
that map $\Lambda$ onto itself. To get $\Lambda$, we have to multiply
$R$ by a suitable number, and, in contrast to the cubic case above,
this number is not always the denominator of $R$, but sometimes a divisor
of it (then coinciding with $\mbox{den}(R)/2$ up to units in $\ZZ[\tau]$).
In any case, it can be chosen as a totally positive number in $\ZZ[\tau]$
whose norm is the so-called
{\em coincidence index} $\Sigma(R)$, defined through \cite{BP,Baake}
\be
\Sigma(R) \; := \; [{\cal M}_B : ({\cal M}_B \cap R{\cal M}_B)] \, .
\ee
The corresponding similarity transformation maps ${\cal M}_B$ to
a maximal submodule $\Lambda$ which then requires $\Sigma(R)^3$
different colours. So, with $\Phi_{ico}(s)$ being the generating function
for the icosahedral coincidence problem, see \cite{BP,Baake} and the
Appendix, the contribution to the colouring problem is given by
the factor $\Phi_{ico}(3s)$, in complete analogy to the cubic case.
The same kind of reasoning also applies to the module ${\cal M}_F$.
Therefore,
\begin{eqnarray}
F(s) & = & \zeta^{}_{\QQ(\tau)}(3s) \Phi_{ico}(3s) \\
& = & \mbox{\small $
1 + {6\over64^s} + {7\over125^s} + {11\over729^s} +
{26\over1331^s} + {26\over4096^s} + {42\over6859^s} +
{42\over8000^s} + {37\over15625^s} +
{62\over24389^s} + \cdots $} \nonumber
\end{eqnarray}
is, at the same time, the generating function for the $B$-type
submodules of ${\cal M}_B$ and for the $F$-type submodules
of ${\cal M}_F$. In order to include the $P$-type modules in a
natural way, we observe that the triple
$({\cal M}_P^{(1)},{\cal M}_P^{(2)},{\cal M}_P^{(3)})$
considered as a set is mapped onto itself under multiplication
with {\em any\/} $\ZZ[\tau]$-number, while each member of the
set has its own coincidence site submodules (with the same index
formula as for the $B$- and $F$-type modules). Furthermore,
two such triples (which are 3-cycles under multiplication by $\tau$)
are either equal or disjoint. So, it is easiest to count triples rather
than single modules because $F(s)$ is then also the generating
function for this case, and a separate counting just requires multiplication
of the corresponding numerator by 3.
If we want to know the number of icosahedral submodules of
either type, we obtain three different solutions, depending on
the module we start from:
\begin{eqnarray} \label{icogenfun}
F_{ico}^{(B)}(s) & = & (1 + 2^{-s} + 4^{-s})
\cdot \zeta_{\QQ(\tau)}^{}(3s)
\cdot \Phi_{ico}(3s) \nonumber \\
F_{ico}^{(P)}(s) & = & (1 + 2^{-s} + 32^{-s})
\cdot \zeta_{\QQ(\tau)}^{}(3s)
\cdot \Phi_{ico}(3s) \\
F_{ico}^{(F)}(s) & = & (1 + 16^{-s} + 32^{-s})
\cdot \zeta_{\QQ(\tau)}^{}(3s)
\cdot \Phi_{ico}(3s) \nonumber
\end{eqnarray}
This is slightly more complicated than the cubic case as
a consequence of Eq.~(\ref{inclu}). In particular, both $B$- and
$P$-type allow for a 2-colouring (then being of $P$- and $F$-type,
respectively) while 16 is the smallest number of colours for
the $F$-type module.
\subsection*{Concluding Remarks}
In this article, a subclass of the colouring problem of lattices
and modules with irreducible symmetries was considered.
The combinatorial part was explicitly solved by means of
Dirichlet series generating functions for various planar modules
with $n$-fold symmetry as well as for cubic lattices and
icosahedral modules in 3-space. A similar analysis is
possible in 4D, as well as for certain series of lattices in
higher dimension.
Clearly, one is not only interested in the number of colouring
possibilities but in the actual colour symmetry groups. In the
planar case, a more complete answer is possible through the
unique factorization property in rings of cyclotomic integers,
which will be reported separately. In 3-space, due
to non-commutativity of the ring of integer quaternions resp.\
the ring of icosian numbers, things are more complicated and
will require a more detailed analysis.
Concerning the generality of our findings, it is clear that there are
relevant cases of colourings already with 4-fold symmetry that
do {\em not\/} belong to the restricted class investigated here,
compare \cite{Schwarz2}. They
can be found systematically by the method of \cite{Ron} which
also allows for an algorithmic version that can be used on a
computer. Whether the generating function approach allows for
a generalization to cover this, e.g.\ along the lines of
\cite{Harker,Schwarz2,Rutherford}, is presently under investigation.
\subsection*{Acknowledgements}
It is my pleasure to thank R.\ Lifshitz and R.\ L\"uck for valuable
discussions and for communication of results prior to publication.
Also, I am grateful to J.\ Hermisson for critically reading the
manuscript and to R.\ V.\ Moody for his help and hospitality
during a stay at the Department of Mathematics of the University of
Alberta, Edmonton, where this manuscript was completed.
\subsection*{Appendix}
It is the purpose of this Appendix to provide some details on the
generating functions and the $\zeta$-functions used above.
The simplest case is Riemann's $\zeta$-function itself,
\begin{equation}
\zeta(s) \; = \; \sum_{m=1}^{\infty} \frac{1}{m^s}
\; = \; \prod_{p} \frac{1}{1-p^{-s}} \, ,
\end{equation}
which allows a representation as an Euler product because all
numerators of the sum are 1 and thus define a multiplicative
function.
Similarly, the $\zeta$-function of $\QQ(\tau)$ (which counts the
ideals in $\ZZ[\tau]$) is the Dirichlet series of a multiplicative
function and reads
\begin{eqnarray} \label{tauzeta}
\lefteqn{ \zeta_{\QQ(\tau)}^{}(s) \; = \;
\frac{1}{1-5^{-s}} \cdot
\prod_{p \equiv \pm 1 \; (5)}
\frac{1}{(1-p^{-s})^2} \cdot
\prod_{p \equiv \pm 2 \; (5)}
\frac{1}{1-p^{-2s}} } \\
& & \mbox{\small $
= \, 1+{1\over4^s}+{1\over5^s}+{1\over9^s}+{2\over11^s}+{1\over16^s}+
{2\over19^s}+{1\over20^s}+{1\over25^s}+{2\over29^s}+{2\over31^s}+
{1\over36^s}+{2\over41^s}+{2\over44^s}
+ \cdots $} \nonumber
\end{eqnarray}
The various other $\zeta$-functions that appear in the text are
described in detail in \cite{PBR} and need not be repeated here.
Finally, let us give the generating functions of the coincidence
problem, for details on how to calculate them we refer to \cite{Baake}.
\begin{eqnarray} \label{cubcsl}
\lefteqn{\Phi_{cub}(s) \; = \; \prod_{p \neq 2}
\frac{1+p_{}^{-s}}{1-p_{}^{1-s}} \; = \;
\frac{1-2^{1-s}}{1+2^{-s}} \cdot
\frac{\zeta(s) \zeta(s-1)}{\zeta(2s)} } \\
& & \mbox{\small $
= \, 1+{4\over3^s}+{6\over5^s}+{8\over7^s}+{12\over9^s}+{12\over11^s}+
{14\over13^s}+{24\over15^s}+{18\over17^s}+{20\over19^s}+
{32\over21^s}+{24\over23^s}+{30\over25^s}+{36\over27^s}+
\cdots $} \nonumber
\end{eqnarray}
\begin{eqnarray}
\lefteqn{\Phi_{ico}(s)
\; = \; \frac{1+5_{}^{-s}}{1-5_{}^{1-s}}
\prod_{p \equiv \pm 2 \; (5)}
\frac{1+p_{}^{-2s}}{1-p_{}^{2(1-s)}}
\prod_{p \equiv \pm 1 \; (5)}
\left( \frac{1+p_{}^{-s}}{1-p_{}^{1-s}} \right)^2 } \\
& & \mbox{\small $
=1+{5\over4^s}+{6\over5^s}+{10\over9^s}+{24\over11^s}+{20\over16^s}
+{40\over19^s}+{30\over20^s}+{30\over25^s}+{60\over29^s}
+{64\over31^s}+{50\over36^s}+ {84\over41^s}+{120\over44^s}
+\cdots $} \nonumber
% {60\over45^s}+{50\over49^s}
\end{eqnarray}
The latter function can be expressed in terms of the $\zeta$-function
of Eq.~(\ref{tauzeta})
\begin{equation}
\Phi_{ico}(s) \; = \;
\frac{\zeta_{\QQ(\tau)}^{}(s)\zeta_{\QQ(\tau)}^{}(s-1)}
{\zeta_{\QQ(\tau)}^{}(2s)}
\end{equation}
which shows again the close analogy between the cubic and
the icosahedral case.
\vspace{5mm}
\begin{thebibliography}{99}
\small
\bibitem{Baake}
M.~Baake,
``Solution of the coincidence problem in dimensions $d\leq 4$'',
in: {\em The Mathematics of Long-Range Aperiodic Order},
ed.\ R.\ V.\ Moody, Kluwer, Dordrecht (1997), pp.\ 9--44.
\bibitem{BM}
M.~Baake and R.~V.~Moody,
``Similarity sublattices and semigroups'', in:
Quasicrystals and Discrete Geometry, ed.\ J.\ Patera,
AMS, Providence, RI (1998), pp.\ 1--13.
\bibitem{BP}
M.~Baake and P.~A.~B.~Pleasants,
``Algebraic solution of the coincidence problem in two and
three dimensions'', {\em Z.\ Naturf.} {\bf 50a} (1995) 711--17.
\bibitem{BS}
M.~Baake and M.~Schlottmann,
``Geometric aspects of tilings and equivalence con\-cepts'',
in: {\em Proceedings of the 5th International Conference on Quasicrystals},
eds.\ C.\ Janot and R.\ Mosseri, World Scientific, Singapore (1995),
pp.~15--21.
\bibitem{Hardy}
G.~H.~Hardy and E.~M.~Wright, {\em An Introduction to the Theory of Numbers},
5th ed., Clarendon Press, Oxford (1979).
\bibitem{Harker}
D.~Harker, ``Colored lattices'', {\em Proc.\ Natl.\ Acad.\ Sci.\ USA}
{\bf 75} (1978) 5264--7; ``Effect of rotational symmetry on colored
lattices'', {\em Proc.\ Natl.\ Acad.\ Sci.\ USA} {\bf 75} (1978) 5751--4.
\bibitem{Lidl}
R.~Lidl and G.~Pilz,
{\em Applied Abstract Algebra}, Springer, New York (1984).
\bibitem{Ron}
R.~Lifshitz, ``Theory of color symmetry for periodic and quasiperiodic
crystals'', {\em Rev.\ Mod.\ Phys.} {\bf 69} (1997) 1181--1218.
\bibitem{Lueck}
R.~L\"uck, private communication.
\bibitem{Martin}
M.~Schlottmann, {\em Geometrische Eigenschaften quasiperiodischer Strukturen},
Dissertation, Univ.\ T\"ubingen, 1993.
\bibitem{Mermin}
N.~D.~Mermin, D.~S.~Rokhsar and D.~C.~Wright,
``Beware of 46-fold symmetry: The classification of two-dimensional
quasicrystallographic lattices'',
{\em Phys.\ Rev.\ Lett.} {\bf 58} (1987) 2099--101.
\bibitem{MP}
R.~V.~Moody and J.~Patera,
``Colourings of quasicrystals'',
{\em Can.\ J.\ Phys.} {\bf 72} (1994) 442--52.
\bibitem{Peter1}
P.~A.~B.~Pleasants, ``Quasicrystals with arbitrary symmetry group'', in:
{\em Proceedings of the 5th International Conference on Quasicrystals},
eds.\ C.\ Janot and R.\ Mosseri, World Scientific, Singapore (1995),
pp.~22--30.
\bibitem{PBR}
P.~A.~B.~Pleasants, M.~Baake and J.~Roth,
``Planar coincidences for $N$-fold symmetry'',
{\em J.\ Math.\ Phys.} {\bf 37} (1996) 1029--58.
\bibitem{Rutherford}
J.~S.~Rutherford,
``The enumeration and symmetry-significant properties of derivative
lattices'', {\em Acta cryst.} {\bf A48} (1992) 500--8;
``The enumeration and symmetry-significant properties of derivative
lattices. II. Classification by colour lattice group'',
{\em Acta cryst.} {\bf A49} (1993) 293--300;
``The enumeration and symmetry-significant properties of derivative
lattices. III. Periodic colourings of a lattice'',
{\em Acta cryst.} {\bf A51} (1995) 672--9.
\bibitem{Schwarz}
R.~L.~E.~Schwarzenberger,
{\em $N$-dimensional Crystallography},
Pitman, San Francisco (1980).
\bibitem{Schwarz2}
R.~L.~E.~Schwarzenberger,
``Colour symmetry'',
{\em Bull.\ London Math.\ Soc.} {\bf 16} (1984) 209--40.
\bibitem{Wash}
L.~C.~Washington,
{\em Introduction to Cyclotomic Fields}, 2nd ed.,
Springer, New York (1997).
% \bibitem{Wilf}
% H.~S.~Wilf, {\em Generatingfunctionology}, 2nd ed.,
% Academic Press, Boston (1994).
\end{thebibliography}
\end{document}
---------------0207250523865--