\documentclass[12pt,letterpaper]{article}
\usepackage{fullpage}
\usepackage{amssymb,amsthm}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{doublespace}
\usepackage[latin1]{inputenc}
\spacing{1.0}
\begin{document}
\title{Colored Symmetry}
\author{Tobin Fricke}
\date{Lunds Universitet, Sweden \\ \& University of California at Berkeley}
\maketitle

Studies of symmetry traditionally concern themselves with isometric transformations leaving some configuration of points unchanged.  In particular it is interesting to study the symmetry groups of infinitely repeating structures, as these infinitely repeating structures may be used to model physical phenomena such as crystals and also artistic tesselations, and we find that in any given dimension there exists only a finite number of these groups.  However, there is often more to symmetry than distance-preserving transformations.  

Consider Escher's drawing (fig \ref{escher}).  The red lizards are clearly related to the white lizards and green lizards, yet they are not identical (they differ in color).  In a strict definition of symmetry, an operation which takes a green lizard and makes it congruent in space to a red lizard is not actually a symmetry operation, as the figures are not the same; they are distinguishable.  Yet, if we consider the differently colored lizards to be equivalent, then we are ignoring structure evident in the drawing.   The solution to this conundrum is to incorporate \emph{color} into our study of symmetry.  While in the case of Escher's drawing, ``color'' really does represent color in the physical sense, we can also use this notion of color as an abstract quantity distinct from position that is manipulated by transformations.

\begin{figure}
\centerline{\includegraphics{escher.eps}}
\caption{\label{escher}Escher, \emph{Lizards; Symmetry Drawing E25}.
India Ink, pencil, watercolor, 1939}
\end{figure}

\section{symmetry}

A \emph{symmetry} of some subset X of euclidean space $R^{n}$ is defined as an isometric (distance preserving) transformation taking the set into a configuration indistinguishable from the original configuration.  For example, we may permute the verticies of a triangle, rotate a sphere through any arbitrary angle, or rotate a cube by a multiple of ninety degrees or invert it through its center; these are all symmetry operations.

A \emph{group} has exactly these properties that we require of symmetry operations and hence is an excellent tool for studying symmetries.  A group is defined as a set $X$ coupled with an operator $*$ that together obey the following properties:

\begin{enumerate}
\begin{spacing}{1.0}
\item{ closure: $ \forall x, y \in G, x * y \in G $}
\item{ associativity: $ \forall x, y, z \in G, (a*b)*c = a*(b*c) $}
\item{ existence of identity: $ \exists e \in G : \forall x \in G, ex = x $ }
\item{ existence of inverses: $ \forall x \in G, \exists x^{-1} \in G  : x * x^{-1} = e $}
\end{spacing}
\end{enumerate}

\subsubsection{group actions}

Every element of the symmetry group \emph{acts} on the set $X$ by transforming it in some way.  We can formalize this phenomenon with the notion of a \emph{group action}.  We require that every element $g \in G$ permute the elements of $X$ in some way that is consistent with the algebraic structure of $G$:

A \emph{group action} of a group $G$ on a set $X$ is a homomorphism $\phi$ from $G$ onto the group of permutations of X (the symmetric group $S_{X}$).

Formally the transformation of an element $x \in X$ to $y \in X$ by an element $g \in G$ due to group action $\phi:G\rightarrow S_X$ should be written $\phi(g)(x)=y$.  However, we will write $g(x)=y$ or even $gx=y$ for convenience. 

By its construction, the symmetry group $G$ has a natural group action on a point set $X$.  In this paper we will construct a second group action to describe how $G$ might operate on other properties of the elements of $X$, generalized in the idea of ``color.''

\subsection{point sets}

The formalism concerning symmetry groups is conveniently built up upon the notion of a \emph{regular system of points}, where each point is equivalent to every other through the use of isometric symmetry operations.  Of this point set we require a number of conditions which should be intuitively agreeable.

We first define a \emph{point set}  as a set whose elements are each points in some metric space such as n-dimensional Euclidean space.  We will be considering mainly points from the plane $R^2$ and from space $R^3$ as these spaces are the most applicable to physical systems.  

Our first condition is of \emph{relative density}, which requires firstly that the set be \emph{discrete} and secondly that it fill space without avoiding any particular region:


definition: a point set is \emph{relatively dense} if:

\begin{enumerate}

\item there is a certain nonzero minimum distance $r>0$ between all pairs of points.  We can form a ball around any point $x$ with radius $r$ and that ball will contain only the point $x$.

\item every open ball containing no points of $X$ must have a radius less than a finite value $R$.
\end{enumerate}

\subsubsection{regularity conditions}

In addition to relative density, we require that a point set be \emph{regular}.  This condition was expressed in a particularly intuitive way by Dirchlet:

a discrete point system is \emph{regular} if from any two points of the system straight lines are drawn to all the other points of the system and these two line systems are directly or mirror congruent.

The regularity condition may be expressed in the language of group theory by saying that our group action of isometric transformation acts \emph{transitively} upon the point set $X$.

definition: a group action is \emph{transitive} if it has only one orbit; that is, if and only if for all $x, y \in X$, there exists $g \in G$ such that $gx=y$.

\subsubsection{dirchlet domains}

It may seem odd to approach a study of the symmetry of tilings of $n$-dimensional space through a formalism built on these discrete sets of points.  In some cases the use of regular point sets arises naturally.  In crystallography we are likely to consider individual atoms simply as points and in that case the use of point sets is entirely natural.  

In the case of tesselations of the plane the use of point sets feels more abstract, as our drawing is not itself a relatively dense, regular point set.  We can think of the points as ``anchor points'' in the drawing, all equivalent.  Perhaps the most concrete way of connecting the point set to a drawing is to form the \emph{fundamental regions} (also known as \emph{dirchlet domains}) that arise from a given point set.   Given a point set, we can partition space into these fundamental regions which are equivalent under our group of isometric symmetries.   Now we need only define our point set and provide a subdrawing (called a \emph{motif}) to cover one fundamental region, and the entire drawing is defined.

The fundamental regions are most easily defined by identifying each point of the set with a region, and defining the region as containing all space that is closer to this point than to any other point in the set.

\subsection{symmetry operations}

A symmetry operation $\sigma$ on a point set $X$ is a transformation that is both one-to-one and onto; that is to say, the set as a whole is left unchanged by the action of $\sigma$.  

\section{Color}

Until now we've been considering the symmetries of point sets, where the points are indistinguishable outside of context.  The symmetry operators act only on the \emph{positions}.  Yet it is advantageous from the standpoint of applications and interesting from a mathematical perspective to introduce other properties to our points.  In chemical crystals, all points are not actually identical; some might be \emph{sodium} while others are \emph{chlorine}.  And in geometrical figures, too, a pattern may repeat, shifted, rotated, reflected, and possibly \emph{in another color}.  It is from phenomena such as these that we take our inspiration, introducing a new property to the points we consider, a property that we shall call \emph{color}.

When considering the symmetries of point sets considering only the positions of points, we imposed regularity conditions upon the sets.  Our regularity requirement for coloring is that every isometry of the underlying point set should \emph{permute} the colors.    Colorings meeting this requirement are called \emph{perfect} and it is them that interest us.

Perfect colorings may be generated algorithmically through the mechanism of group theory.  For this we will require the machinery of cosets, described in the next section.

\subsection{cosets}

Given any element $g \in G$ and subgroup H of G we can form the cosets of G generated by H.  We define the \emph{right coset generated by H} to be $gH$ to be $\{ gh : h \in H\}$.  There are also left cosets, designated $Hg$ and generated in the analogous fashion, but reversing the order of multiplication.  Given a subgroup H, elements $x,y \in H$ are said to be equivalent  if $\exists  h \in H$ such that $x = yh$.  The equivalence classes resulting from this relation are exactly the left cosets of H.  Thus a subgroup, via its cosets, may be used to partition a group.  

Lagrange's theorem tells us that the number of cosets generated by H is exactly $|G|/|H|$ and this integer is called the \emph{index} of G in H.   

If the left cosets generated by H are the same as the right cosets designated by H, then H is called a \emph{normal subgroup} and there is no ambiguity in refering to just the cosets of H without reference to right or left.

The cosets of a normal subgroup themselves form a group owing to the property that, for a normal subgroup $H$, the left and right cosets may be identified: $gH = Hg$.  The `multiplication' operation in a coset group is the natural one.  The product of two cosets is the coset containing the product of an element from each of the two cosets, and closure is shown simply: $(gH)(g'H) = g(Hg')H = g(g'H)H = (gg')H$.

\subsection{dichromatic colorings}

For simplicity we may first informally consider a dichromatic coloring.   It is clear that some symmetry operations will preserve colors; at least the identity transformation must do so.  Every symmetry operation in $G$ must either reverse the color of every element in $X$, or leave the color of every element unchanged.  Thus there must be a subgroup of $G$ which contains only color-preserving operations.

Since $G$ acts transitively on $X$, every element of $X$ is reachable by any other through the action of an element of $G$.  Therefore we need only choose one element of $X$ to be colored ``black'' and through the use of the color-preserving subgroup we can locate every other black element.  The remaining elements will be colored white.

In designing a dichromatic coloring of a figure we may arbitrarily choose any index-two subgroup to be the color-preserving subgroup.  In this way we can find all possible dichromatic colorings of a figure described by a given symmetry group.  

We will discuss dichromatic colorings slightly more formally with the aid of an example, and then we will move on to a discussion of colorings with an arbitrary number of colors.

\subsubsection{example:  dichromatic coloring of the square}

Our coloring procedure requires only a transitive symmetry group and does not exploit the regularity and density conditions we imposed on the point set.  Therefore we may also use this procedure to color finite figures.   To illustrate the process we will find all colorings of the symmetry group of the square.

The square, being a regular 4-sided polygon, has as its symmetry group the dihedral group $D_4$.  In general the symmetry group of a regular $n$-sided polygon (an ``$n$-gon'') is the dihedral group $D_n$, and the ``equivalent regions'' of that polygon are found by dividing the polygon into sectors, where every vertex and the midpoint of every edge lie on a sector boundary. 

If we designate the identity transformation as $e$, a quarter-turn rotation by $r$, mirroring along the two diagonals as $d_1, d_2$, and mirroring along horizontal and vertical bisectors as $b_1, b_2$, then we have $D_{4}=\{e, r, r^2, r^3, d_1, d_2, b_1, b_2\}$.  These operations and the resulting eight equivalent sectors of the square are illustrated in figure \ref{square_symmetries}.  The set $X$ consists of these eight sectors.

\begin{figure}
 \centering
 \subfigure[symmetries and equivalent regions of the square]{
   \label{square_symmetries} 
   \includegraphics{square_symmetries.eps}}
 \subfigure[Subgroup structure of $D_4$]{
   \label{d4grouptree}
   \includegraphics{d4grouptree.eps}} 
 \subfigure[Generic orbit of $D_4$ (\emph{figure unfinished})]{
   \label{square_sectors_labelled}
   \includegraphics{d4genericorbit.eps}}
 \caption{symmetry structure of the square (from ~\cite{Senechal}, p. 64)}
\end{figure}

First we find a generic orbit of $G$ by choosing an arbitrary sector $x_0$ and then computing $ex_0$, $rx_0$, $r^{2}x_0$, etc for every operator in $G$, each time labeling the resulting sector $y$ with the group element $g$ such that $y=gx_0$.  The labeling resulting from one choice of $x_0$ is shown in figure \ref{square_sectors_labelled}.

Now we select a subgroup to designate as the color-preserving subgroup.  Referring to the subgroup structure of $D_4$ in figure \ref{d4grouptree}, we find three subgroups of index two (i.e. of size $|G|/2 = 8/2 = 4$), each leading to a unique coloring, illustrated in figure \ref{square_colorings}.

\begin{figure}
 \centering
 \subfigure[Subgroup $\{e, b_1, b_2, r^2\}$]{
  \includegraphics{squarecoloring1.eps}}
 \subfigure[Subgroup $\{e, r, r^2, r^3\}$]{
  \includegraphics{squarecoloring2.eps}}
 \subfigure[Subgroup $\{e, d_1, d_2, r^2\}$]{
  \includegraphics{squarecoloring3.eps}}
 \caption{all dichromatic colorings of the square}
 \label{square_colorings}
\end{figure}

\subsection{general colorings}

The procedure for dichromatic colorings immediately suggests a scheme for generating a perfect coloring with an arbitrary number $k$ of colors, provided the symmetry group $G$ has a subgroup of index $k$.  We formalize the notion of a coloring by expressing it as a group action from $G$ onto a set of colors $C$.  We select a color-preserving subgroup use it to partition $X$ into colors.

A coloring of a figure can be established by finding a group action of the figure's symmetry group G onto the set of colors $C = \{c_0, c_1, ..., c_k\}$.   Fixing an element $x_0 \in X$ we will then associate with every element $y \in X$ the element of $G$ such that $gx_0=y$, which is possible since $G$ acts transitively.  We then wish to find a homomorphism $\phi: G \rightarrow S_{C}$ that will associate with every symmetry operation $g \in G$ a permutation of the set of colors $C$. 

We begin by setting the color of $x_0$ to $c_0$.  The stabilizer group $G_{x}=\{g : gx=x\}$ is a subgroup of $G$ which leaves every $x\in X$ unchanged; it is the subgroup of color-preserving operations.  Thus every element $G_{c_0}x_0$ also has color $c_0$.   By finding an as yet uncolored element $x'=g'x_0$ then we can find the color of $x'$ knowing the color permutation $\phi(g')$ and the color of $x_0$.   By repeating this process, every point in $X$ can be colored.

What we have done is to partition $G$ into the cosets of a stabilizer group of the group action $\phi$.   We see also that the number of colors $k$ is equal to the number of cosets of H in G, which in turn is equal to $|G|/|H|$.

We can choose our group action implicitly by selecting its stabilizer groups from the subgroups of $G$, just as we generated dichromatic colorings by choosing a subgroup to act as a color-preserving subgroup.  By the equation $k=|G|/|H|$ we see that if we wish to have $k$ colors, we need to choose a subgroup $H$ of index $k$ in $G$.

References:
~\cite{Engel}
~\cite{Loeb1}
~\cite{Shafarevich}
~\cite{Senechal}
~\cite{Armstrong}

\bibliographystyle{plain}
\bibliography{symmetry}

\end{document}







