Colored Symmetry

Tobin Fricke

Lunds Universitet, Sweden & University of California at Berkeley

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 1). 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 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.

1 symmetry

A 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 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:

1. closure: ∀x, y ∈ G, x ∗ y ∈ G

2. associativity: ∀x, y, z ∈ G, (a ∗ b) ∗ c = a ∗ (b ∗ c)

3. existence of identity: ∃e ∈ G : ∀x ∈ G, ex = x Figure 1: Escher, Lizards; Symmetry Drawing E25. India Ink, pencil, watercolor, 1939

4. existence of inverses: ∀x ∈ G, ∃x^{−1} ∈ G : x ∗ x^{−1} = e

1.0.1 group actions

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

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

Formally the transformation of an element x ∈ X to y ∈ X by an element g ∈ G due to group action ϕ : G → S_{X} should be written ϕ(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.”

1.1 point sets

The formalism concerning symmetry groups is conveniently built up upon the notion of a 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 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 relative density, which requires firstly that the set be discrete and secondly that it fill space without avoiding any particular region:

definition: a point set is relatively dense if:

1. 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.

2. every open ball containing no points of X must have a radius less than a finite value R.

1.1.1 regularity conditions

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

a discrete point system is 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 transitively upon the point set X.

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

1.1.2 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 fundamental regions (also known as 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 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.

1.2 symmetry operations

A symmetry operation σ 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 σ.

1.3 point groups

A point group is a group of symmetry operations leaving at least one point unchanged, i.e. there exists a point x such that ∀σ ∈ G, σx = x. These requirements are very general, admitting rotation groups of all orders, and inversions, and, of course, combinations of these operations. The point groups are represented by matricies of determinant ±1.

In two dimensions, a rotation group of order n (that is, consisting of rotations of 2πk/n radians for integers k) is denoted as the cyclic group C_{n}. If we include inversion (improper rotations) then we generate the dihedral group D_{n}, the group of symmetries of a regular n-gon. Similarly, the point groups in three dimensions are the symmetry groups of regular polyhedra, with and without allowing inversion.

1.4 lattice groups

A lattice is a point set exhibiting translational symmetry. In the plane we can represent this translational symmetry by two nonparallel basis vectors α and β, such that for x, y ∈ X there are unique a, b ∈ Z such that y = aα + bβ.

1.5 the crystallographic restriction

Any pattern repeating in space, such as a tesselation of the plane or a crystal in space, exists on such a lattice. Therefore we are very interested in lattice symmetries. In particular this brings about the crystallographic restriction.

If a particular point set exhibits rotational symmetry about a point x and it also exhibits translational symmetry by a vector α then it must also exhibit rotational symmetry about x′ = x+α. It turns out that only rotations of order 1, 2, 3, 4, and 6 are possible in a uniform tiling of space. This is known as the crystallographic restriction.

As we may also utilize the inversion operation, improper rotations should also be included. Thus the possible point-group symmetries on a lattice are C_{1}, C_{2}, C_{3}, C_{4}, C_{6}, D_{1}, D_{2}, D_{3}, D_{4}, D_{6}.

The crystallographic restriction may be proved by contradiction. Suppose a wallpaper group has rotations of order q and let a be the shortest nonzero vector in L, the lattice group. Then let A be a rotation by an angle 2π/q. If q > 6 or if q = 5 then Aa is shorter than A, violating the hypothesis concerning a. The only remaining possibilities are q ∈ {1, 2, 3, 4, 6}.

2 Space groups

The space groups are the result of combining a point group with a lattice group. Two dimensional space groups are called “wallpaper groups” since they represent every possible symmetry system of regular patterns tiling the plane; three dimensional space groups are called the “crystallographic group.” There are seventeen space groups in two dimensions, 230 in three dimensions, and 4901 in four dimensions.

Employing the trick of “homogeneous coordinates” we can represent an affine transformation in n dimensions as an n + 1 dimensional square matrix. In this system point is represented as a column vector consisting of its n coordinates augmented with a dummy coordinate with value 1.

In this way we can represent each basis vector of a translation group as a matrix, as well as a rotation matrix and the inversion matrix. Thus we have the ingredients needed to generate a space group in any dimension. The space groups are exactly those groups generated in this manner. We see immediately as well that any space group will have translation and rotation subgroups. The existence of the subgroup of translations is known as Bieberbach’s theorem.

As a regular point set fills space, the translational subgroup must be infinite. Furthermore, translations are obviously commutative, so this subgroup is Abelian. Senechal notes that the existence of this infinite commutative subgroup may be used to define the space groups.

3 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 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 sodium while others are chlorine. And in geometrical figures, too, a pattern may repeat, shifted, rotated, reflected, and possibly 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 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 permute the colors. Colorings meeting this requirement are called 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.

3.1 cosets

Given any element g ∈ G and subgroup H of G we can form the cosets of G generated by H. We define the right coset generated by H to be gH to be {gh : h ∈ 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 ∈ H are said to be equivalent if ∃h ∈ 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 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 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.

3.2 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 indextwo 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.

3.2.1 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 2(a). The set X consists of these eight sectors.

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 2(c).

Now we select a subgroup to designate as the color-preserving subgroup. Referring to the subgroup structure of D_{4} in figure 2(b), 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 3.

(a) symmetries and equivalent regions of the square (b) Subgroup structure of D_{4} (c) Generic orbit of D_{4} (figure unfinished)

Figure 2: symmetry structure of the square (from [4], p. 64)

(a) Subgroup {e, b_{1}, b_{2}, r^{2}}  (b) Subgroup {e, r, r^{2}, r^{3}}  (c) Subgroup {e, d_{1}, d_{2}, r^{2}}

Figure 3: all dichromatic colorings of the square

3.3 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} ∈ X we will then associate with every element y ∈ X the element of G such that gx_{0} = y, which is possible since G acts transitively. We then wish to find a homomorphism ϕ : G → S_{C} that will associate with every symmetry operation g ∈ 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 ∈ 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 ϕ(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 ϕ. 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: [2] [3] [5] [4] [1]

References

[1] M. A. Armstrong. Groups and Symmetry. Springer-Verlag, (1988).

[2] Peter Engel. Geometric Crystallography: An Axiomatic Introduction to Crystallography. D. Reidel Publishing Company, (1986).

[3] Arthur L. Loeb. Color and Symmetry. Robert E. Krieger Publishing Company, (1971).

[4] Marjorie Senechal. Crystalline Symmetries: An Informal Mathematical Introduction. Adam Hilger, (1990).

[5] I.R. Shafarevich. Basic Notions of Algebra. Springer-Verlag, (1997).