The Design of 2-Colour Wallpaper Patterns Using Methods Based on Chaotic Dynamics and Symmetry

# The Design of 2-Colour Wallpaper Patterns Using Methods Based on Chaotic Dynamics and Symmetry

### Michael Field

http://nothung.math.uh.edu/~mike/maubeuge

## Abstract

We describe the theoretical basis for the design of symmetric patterns using dynamics, chaos and symmetry. We show examples of some of the one- and two-colour wallpaper patterns that we have created using these ideas.

## 1  Introduction

In this article, I describe the design and colouring of planar symmetric patterns - in particular, two-colour wallpaper patterns - using techniques based on dynamics and chaos. Apart from showing examples, some coloured, of the pictures created using these ideas, my main aim in writing this article was to provide an overview of the theory that underpins the techniques. In a companion article [], I discuss some of the ways in which aesthetics and mathematics become intertwined in attempts to create an art based on symmetry and chaos.

The images shown in this article were all designed and coloured (or `grey scaled') using software that I started to develop about twelve years ago. This software, called prism (an acronym for `PRograms for the Interactive Study of Maps'), allows the interactive design and colouring of planar figures with non-trivial discrete symmetry. Some of the early pictures produced using prism can be found in the 1992 book Symmetry in Chaos  [], written jointly with Marty Golubitsky. (Many of the iterative algorithms used in prism were developed in collaboration with Marty Golubitsky.) We refer to [] for a relatively up-to-date description of prism and the way real (as opposed to virtual) pictures are obtained.

Prism can generate a wide range of symmetric patterns including bounded symmetric patterns in the plane and all of the frieze and wallpaper patterns, including the two-colour wallpaper patterns. In practice, the development of prism has been strongly influenced by my interest in using the program to create artistically satisfying designs. This consideration has particularly influenced the choice of algorithms I use for colouring two-colour designs (see []). It may at first sight seem strange to use relatively sophisticated methods based on symmetry and chaos to construct symmetric designs. Indeed, there are many combinatorial techniques, and computer programs, that can produce symmetric designs (for example, see [,,]). However, the typical image designed using prism exhibits an unusual and striking global coherence as well as a wealth of rich and complex detail. These features result from the image being a visual representation of an attractor of a globally defined dynamical system.

It turns out that prism is a useful tool in teaching both geometry and design []. In recent years, I have used prism as the basis of a course on `Patterns, Designs and Symmetry' that I have given in the Department of Art at the University of Houston (see the URL nothung.math.uh.edu/~patterns/ for some of the designs produced by the Fall 1998 class). In another direction, I have used prism in a seminar on `Symmetry, Patterns and Designs' that I gave in 1999 for the Houston Teachers Institute (see the URL www.uh.edu/hti/).

We now describe the contents of the article by section. In section 2, we describe the mathematical theory underlying the design of images using methods based on symmetry and chaos. After a brief review of planar symmetry, we discuss the concept of an attractor. and give examples of the construction of bounded symmetric attractors using both deterministic and non-deterministic (or `random') dynamical systems. We conclude the section with some comments about the numerical implementation of these ideas and colouring (`coloured measures'). Section 3 is devoted to the topic of one-colour wallpaper patterns. In section 4, we provide a definition of two-colouring that applies to dynamically generated patterns. We also describe two ways in which we can create two colour patterns using dynamics. We conclude by showing some coloured examples of two-coloured wallpaper patterns created using dynamics.

## 2  The Theory of Designer Chaos

In this section, we describe how we can use methods based on symmetry and chaos to construct symmetric designs1. We start with a brief review of some foundational results on planar symmetry groups.

### 2.1  Planar symmetry groups

Let \mathbbR2 denote the Euclidean plane and E(2) denote the Euclidean group of rigid motions of \mathbbR2. We recall that if T Î E(2) is not the identity, then T is either a reflection, or a rotation or a translation or a glide reflection. We denote the subgroup of E(2) consisting of translations by ET(2) and note that ET(2) is naturally identified with \mathbbR2.

Suppose that X is a closed subset of \mathbbR2. A transformation T Î E(2) is a symmetry of X if T(X) = X. We let S = S(X) denote the group of all symmetries of X and remark that S defines a closed subgroup of E(2). Let ST = SÇET(2) denote the group of translational symmetries of X.

We shall only be interested in patterns X for which S is a 0-dimensional (discrete) subgroup of E(2). We recall the well-known classification of discrete subgroups S of E(2).

(B) If S is finite, then there exists n ³ 1 such that S is either isomorphic to \mathbbDn (the dihedral group of order 2n) or \mathbbZn (the cyclic group of order n).
(F) If ST @ \mathbbZ, then S is a frieze group. There are seven isomorphism classes of frieze groups.
(W) ST @ \mathbbZ2, then S is a 2-dimensional periodic or wallpaper group. There are seventeen isomorphism classes of wallpaper groups.
The reader may find proofs of these results, as well as examples of patterns realizing each of the discrete subgroups of E(2), in [,chapters 19,26]. In the sequel, we follow the notation for wallpaper patterns used in [,,] (see also section ).

### 2.2  Attractors

For the present, we restrict attention to attractors of planar dynamical systems. However, all of what we say generalizes easily to dynamical systems defined on more general spaces. Our definitions are formulated so as to cover both deterministic and random (or non-deterministic) dynamical systems. Readers unfamiliar with dynamical systems theory are advised to skim quickly through the following until they come to the paragraphs on numerical implementation.

Let F denote a set of n (continuous) planar maps fi:\mathbbR2 ®\mathbbR2, 1 £ i £ n. Let S(n) denote the space of all infinite sequences s = (sj)j ³ 1 of integers such that sj Î {1,¼,n}, j ³ 1. Given x Î \mathbbR2, s Î S(n), we define the sequence (xms)m ³ 0 Ì \mathbbR2 inductively by

 x0s
 =
 x,
 xms
 =
 fsm(xm-1s),    m > 0.
Often we drop the superscript s if the sequence s is implicit from the context or n = 1. Indeed, if n = 1, the sequence (xm) is the result of repeated iteration of the point x by f: xm = fm(x), m ³ 0. In this case, we regard f as defining a deterministic dynamical system.

If n > 1, the result of the first m iterations generally depends on the sequence s. In this case, it is natural to place a probability measure on S(n)2 and look for properties of (xis) that hold for `most' sequences s. We call F (together with the probability measure on S(n)) a random dynamical system or iterated function system . Roughly speaking, successive iterations are defined by picking maps at `random' from the set F. The theory of iterated function systems when the maps fi are affine linear contractions of the plane may be found in [,]. For the general theory of random dynamical systems, see Arnold [].

For both deterministic and random dynamical systems the asymptotic behavior of the iteration (xms) is sometimes relatively insensitive to the choice of initial point and sequence s. More precisely, let v(x,s) denote the v-limit set of the iteration (xms). That is, y Î v(x,s) if there exists an infinite, strictly increasing sequence of integers ni such that

 lim i®¥ xni = y.
(2.1)

A closed set X Ì \mathbbR2 is an attractor for the dynamical system defined by F if we can choose an open neighbourhood U of X such that

(a) For all x Î U, and sequences s, v(x,s) is a non-empty subset of X.
(b) For (Lebesgue) almost all x Î U and almost all sequences s, v(x,s) = X.
There are many different definitions of attractor in the literature. Our particular definition is chosen for its generality and relevance to our intended applications. Later, when we discuss issues of colouring, we have to strengthen the definition of attractor by requiring that it support a unique ergodic measure naturally defined through the iteration.

### 2.3  Symmetric Attractors

We are going to represent symmetric designs as attractors of symmetric dynamical systems. We consider both deterministic and non-deterministic dynamics. We illustrate the general methods with examples leading to patterns with finite symmetry. We defer to the following section the construction of wallpaper patterns

#### Deterministic dynamics leading to patterns with finite symmetry.

Let G Ì E(2) be finite. We consider (continuous) mappings f:\mathbbR2 ®\mathbbR2 which are G-symmetric (equivariant). That is, if we apply a symmetry g Î G to x Î \mathbbR2 and apply f, the result is the same as if we apply the symmetry g to f(x). In symbols, for all x Î \mathbbR2, g Î G, we have

 f(gx) = g f(x).
Suppose that X is a closed and bounded subset of the plane. Define

 S(G,X) = {g Î G   |  g X = X}.
Obviously, S(G,X) is a subgroup of G. We refer to S(G,X) as the G-symmetry group of X. If G, X are clear from the context, we set S(G,X) = S. For most of our applications, we will have S(G,X) = S(X) - the symmetry group of X.

Parts 1 and 2 of the next result follow easily from the G-symmetry of f (see []). Suppose that X Ì \mathbbR2 is an attractor for the G-symmetric map f:\mathbbR2 ®\mathbbR2. Then

(1) For all g Î G, gX is an attractor with G-symmetry group gS(G,X)g-1.
(2) If g Î G and g Ï S(G,X), then g X ÇX = Æ.
(3) For generic f, S(G,X) = S(X).

There are restrictions imposed by symmetry on the symmetries of attractors. For example, it is not possible to find a \mathbbD6-symmetric planar map f which has an attractor with \mathbbD3-symmetry, even though \mathbbD3 is a subgroup of \mathbbD6. Further, if f has an attractor with \mathbbD6-symmetry, then X must be infinite. We refer to [] for proofs and generalizations of these results (see also [] for the case of invertible maps).

In general, a G-symmetric continuous planar mapping may not have an attractor. Even if we restrict to G-symmetric polynomial mappings - it is possible using classical invariant theory to describe these maps rather precisely - there are only a few, very few, cases where we can explicitly prove the existence of infinite G-symmetric attractors. However, numerical evidence suggests that G-symmetric attractors are quite common. This was first observed in the paper by Chossat & Golubitsky [] who also proposed mechanisms of `symmetry creation' which could lead to G-symmetric attractors. Unfortunately, numerical investigation also shows that small changes in the planar map can result in a non-finite attractor changing to a finite attractor.

Figure
Figure 1: Varying parameters

In Figure 1 we show the result of numerically iterating three maps with \mathbbD5-symmetry. The first map is defined by

 f1(z) = (-2.25 + 0.9|z|2 + 0.041Re(z5))z + 0.1 _z 4 ,     (z Î \mathbb C),
where we have identified the complex plane \mathbb C with \mathbbR2. The remaining maps f2, f3 are obtained by successively incrementing the coefficient of Re(z5) by -0.001. The images shown, from left to right, are the results of iterating each of the maps f1, f2, f3, 50.0001 million times and plotting the fifty million points after the first 1,000 iterations (so as to ignore transients). The initial point x0 was chosen to be (0.1,0.21). For the first and third images, we used a grey scale colouring that depended on the number of times each pixel was hit in the iteration. For the middle image, the attractor is an attracting periodic point of period 5 which lies on an axis of symmetry of \mathbbD5. We represented the points on the periodic orbit as (large) squares to enhance visability of the attractor. Numerical experimentation confirms that the attractors in this sequence are robust to changes of the initial point. However, as follows from lemma 2.3.1, the attractor for f2 can lie on any one of the five axes of symmetry of \mathbbD5 - depending on the choice of x0. Note also that colourings of the attractors corresponding to f1 and f3 are not identical. A consequence of the behaviour shown in Example 2.3.1 is that is it likely to be extremely difficulty to find computable conditions on the coefficients of G-symmetric polynomials that imply the existence of an infinite chaotic G-symmetric attractor. Similar `windows' of attracting periodic orbits are well known in the theory of 1-dimensional mappings.

Rather than attempt further theoretical analysis of symmetric attractors, we shall instead make the working assumption that attractors we find by numerical experimentation are attractors in the sense of Definition 2.2. We need also to assume some facts about the statistical properties of the iteration on and near X. To this end, let dx denote the Dirac probability measure supported at x. We assume that if X is a G-symmetric attractor for the G-symmetric map f, and U is an open neighbourhood of X satisfying the conditions of Definition 2.2, then for almost all x Î U, [1/n] åi = 0n-1 dxi converges (weakly) to a unique G-invariant measure r supported on X. As we explain shortly, we use the existence of r as the theoretical basis for colouring the attractor X. In other words, we regard r as a coloured measure on X where `colour' represents the probability of visiting a pixel (or Borel set) during the iteration.

#### Non-deterministic dynamics.

It is straightforward to construct iterated function systems on the plane which produce symmetric attractors. Let G be a finite subgroup of E(2) of order n. Let f be any affine linear contraction of the plane3. Define F = { g°f   |  g Î G}. It is easy to verify that F consists of affine linear contractions. Define the probability measure p on {1,¼,n} by p(i) = [1/n], 1 £ i £ n, and take the corresponding Bernoulli product measure m on S(n). The iterated function system defined by F, m has a unique G-symmetric attractor X. The attractor X supports a natural G-invariant ergodic measure r such that for almost all x Î \mathbbR2 and sequences s Î S(n), [1/n] åi = 0n-1 dxis converges (weakly) to r. We refer the reader to [,] for details. In Figure  we show three `symmetric fractals' constructed using an iterated function systems generated by a single affine linear contraction. From left to right, the images have \mathbbD10, \mathbbZ8 and \mathbbZ14-symmetry respectively.

Figure
Figure 2: Symmetric Fractals

Following example 2.3.1, we have a used a grey scale colouring that reflects the structure of the natural ergodic measures on the attractors.

### 2.4  Numerical implementation

We divide the numerical investigation of symmetric attractors into two components: experimentation (design) and computation.

#### Experimentation - Design.

The aim of the experimentation or design process is to find aesthetically appealing patterns with specified symmetry. This process is implemented in prism in the following way.

The user initially specifies the symmetry of the pattern (any discrete subgroup of E(2)), and the type of iteration (deterministic or iterated function system). In the case of wallpaper patterns, there is also a choice of one- or two-color symmetry. Depending on the type of iteration and symmetry chosen, various algorithms are available. For example, if a dihedral group \mathbbDn, n ³ 3, and deterministic iteration are selected, then one possibility is to use the family of \mathbbDn-symmetric polynomial maps

 P(z) = (l+ a|z|2 + bRe(zn))z + g _z n-1 ,    (z Î \mathbb C).
In this case the user can vary the (real) coefficients l, a, b, g as part of the experimentation and design process. For further details on this algorithm (and extensions), as well non-deterministic algorithms for bounded patterns, we refer the reader to []. The user can control all aspects of the iteration. For example, the initial point x0, the number of iterations plotted, and the number of iterations that are not plotted during the initial part of the iteration. Further, the effect of incrementing parameters on the iteration can be shown with a sequence of plots on the screen (as in Figure 1).

#### Computation.

Once a design has been selected, a numerical approximation to the (assumed) natural measure on the attractor is computed. This is done by making a choice of resolution (size) and then computing a large number of iterations, recording the number of hits on each pixel. For example, if a resolution of 1000 ×1000 is chosen for an attractor computed using a deterministic algorithm, it might be reasonable to compute 100 million iterates. In practice, the number of iterations needed depends on the specific attractor and also the type of iteration - attractors produced using non-deterministic algorithms tend to need fewer iterations because the associated measures are often relatively uniform.

### 2.5  Colouring

For one-color designs, the attractor is colored on the basis that the colour of a pixel depends only on the number of times the pixel was hit in the iteration.

More formally, suppose that X is a G-symmetric compact attractor with associated ergodic measure r defined as a weak limit of Dirac measures along trajectories. Since X is G-symmetric, if follows from the uniqueness of r, that r is G-symmetric. That is, if A is a measurable subset of X and g Î G, then r(A) = r(g A) for all g Î G.

In order to develop a theory of coloured measures that we can apply - especially to 2-colour quilts - we need to make a further assumption about the measure r. In practice this assumption is harmless and, more importantly, it is consistent with the way we compute approximations to a coloured measure.

Let dl denote Lebesgue measure on the plane.

[cf []] We say the probability measure r is a density on X if there exists a Lebesgue measurable function x:X ®\mathbbR such that

(1) x is G-invariant: x(gx) = x(x), all x Î X, g Î G.
(2) x(x) > 0 for all x Î X.
(3) For all measurable subsets A of X, r(A) = òA x  dl.
We refer to x as a density function on X.

Let C denote a space of colours (for example, RGB- or CMYK-space). A symmetric colouring of the attractor X is given by a map C: X ®C that factors through the density function x.

That is, C is a coloring if there exists c:\mathbbR®C such that

 C(x) = c(x(x)),    (x Î X).

#### Computing densities.

Simple examples, such as the Sierpi\'nski triangle, show that the natural measure r on X is generally not a density. However, it is straightford to show that we can arbitrarily approximate r by an (approximately) G-symmetric density. Furthermore, we can realize the approximation numerically. We briefly sketch the way we do this.

Without loss of generality, assume that X is contained in the unit square S in \mathbbR2. Choose a large positive integer N. Let D denote the partition of S into N2 squares, each of side length 1/N. Let P(S) = {s Î D   |  s ÇX ¹ Æ}. Suppose that (xi) is a sequence of iterates such that the corresponding averages of dirac measures along the trajectory converges to r. For n > 0, s Î D, let i(n) denote the number of times points of the finite trajectory x1,¼, xn enter s. (We ignore the question of iterates lying on the boundary of s and assume that every point of (xi) lies in exactly one square from D.) We define a density function on X by

 xN = lim n®¥ 1n å s Î D i(n) cs,
where cs denotes the characteristic function of the square s. Let rN denote the corresponding measure. Since r is ergodic, it follows easily that the limit defining xN exists for almost all choices of (xi) and depends only on the subdivision D. As we increase N, rN will converge weakly to r. Furthermore, it is easy to see that since r is G-symmetric, the density xN is approximately G-symmetric. All of these statements about approximation can be made quite precise granted our original assumptions about r.

In the sequel, we assume that attractors always have a density. We refer the reader to [,chapter 1], and [,] for more details on colouring. Matters are more complex for two-colour patterns and we discuss this later in section .

## 3  Wallpaper Patterns

We start with a rapid review of some basic facts about lattices, tori and wallpaper patterns. Most of what we say can be found in the text by Armstrong []. We conclude the section with some details and examples on the construction of wallpaper patterns using dynamics.

### 3.1  Geometry of wallpaper patterns

Let O(2) denote the orthogonal group consisting of all rotations about the origin and reflections in lines through the origin of \mathbbR2. In what follows, we identify the group of translations ET(2) with \mathbbR2. Every transformation g Î E(2) can be written uniquely as g = r °t, where t Î \mathbbR2 and r Î O(2). It follows that we have a natural homomorphism p: E(2) ®O(2), defined by p(g) = r.

Let \mathbbZ2 = {(m,n)   |  m,n Î \mathbbZ} denote the integer lattice in \mathbbR2. The quotient group \mathbbR2/\mathbbZ2 is isomorphic to the two-dimensional torus \mathbbT2. Topologically, \mathbbT2 is the product of two circles, or the space obtained by identifying opposite edges of the unit square in \mathbbR2. For future use, we define the hexagonal lattice \mathbbZ2h = {ma + n b   |  m,n Î \mathbbZ}, where a = (1,0), b = ([1/2],[(Ö3)/2]).

Suppose that G is a wallpaper group. Since the translational subgroup of E(2) is naturally identified with \mathbbR2, it follows that the translational subgroup GT of G is naturally identified with a (lattice) subgroup L of \mathbbR2. Necessarily L is isomorphic to \mathbbZ2 and so \mathbbR2/L is also isomorphic to \mathbbT2 - the isomorphism will depend on the choice of isomorphism between L and \mathbbZ2. In the sequel we set \mathbbR2/L = \mathbbT2L to emphasize the dependence of the torus on the lattice. Let J = p(G) denote the point group of G. Since L lies in the kernel of p, it follows that J is a finite subgroup of O(2) and J(L) = L [,Theorem 25.2].

At this point it is customary to divide the lattice subgroups into five classes (oblique, rectangular, centered rectangular (or rhombic), square and hexagonal) and then classify the wallpaper groups according to the point groups that can occur for each lattice class.

We shall proceed a little differently. Since J(L) = L, J acts as a finite group of transformations on \mathbbT2L. It follows that if X is a closed J-invariant subset of \mathbbT2L, then the lift of X to \mathbbR2 will be a doubly periodic pattern with wallpaper symmetry group (at least as big as) G. We use this observation as the basis of our construction of wallpaper patterns using dynamics.

It follows straightforwardly from the J-invariance of the lattice L that rotations in a point group can only be of order 2,3,4 or 6. Further, order 3 or 6 rotations can only occur when the corresponding lattice is hexagonal. Five of the wallpaper patterns (p6m, p6, p3, p31m, p3m1) are only supported on a hexagonal lattice. The remaining twelve patterns can all occur on a square lattice. Amongst these twelve patterns, p4m, p4, p4g are only supported on a square lattice. While the remaining eight patterns all occur on a square lattice, they also occur on other lattices. For example, patterns of type p1, p2 occur on an oblique lattice. Rather than attempt to construct wallpaper patterns for every class of lattices, we shall only work with the integer and hexagonal lattices \mathbbZ2, \mathbbZh2. Once we have constructed a particular pattern on a square lattice that is normally supported on a different lattice class L, we can apply linear transformations to the pattern that map \mathbbZ2 onto a lattice in the class L. For example, if the pattern is of type pmm (normally supported on a rectangular lattice), composition with any non-singular diagonal matrix will lead to a pmm pattern supported on a general rectangular lattice.

### 3.2  Dynamics

#### Deterministic dynamics.

Suppose G is a wallpaper group with associated point group J. For simplicity we suppose that GT = \mathbbZ2. As we indicated above every closed J invariant subset of \mathbbT2 lifts to a wallpaper pattern with wallpaper group (at least) G. In order to construct J-invariant sets using dynamics, we search for J-invariant attractors of continuous (or smooth) J-symmetric mappings f: \mathbbT2 ®\mathbbT2. Every f: \mathbbT2 ®\mathbbT2 lifts to a doubly periodic mapping F:\mathbbR2 ®\mathbbR2. The doubly periodic mappings of \mathbbR2 are given by Fourier series. For deterministic iterations, we work with classes of low order trigonometric polynomials and vary coefficients just as we described above for bounded attractors in the plane. In order to obtain J-invariant attractors, we need to work with J-symmetric trigonometric polynomials on \mathbbT2. The conditions for J-symmetry are straightforward to compute using the dual lattice (see [,Appendix D]).

In order to obtain a sensible symmetry classification of dynamically generated wallpaper patterns, we regard the pattern as being determined by the pair (X,r), where X is a J-invariant attractor and r is a G-invariant measure on X. In particular, we may (and often do) have X = \mathbbT2. If the associated measure r has (say) only the trivial symmetry, then (X,r) will define a wallpaper pattern of type p1 .

#### Non-deterministic dynamics.

We continue to assume G is a wallpaper group with associated point group J. Let f: \mathbbT2 ®\mathbbT2 (possibly not continuous everywhere). Form the iterated function system F = {g °f   |  g Î J}. We find numerically that for most choices of f, the iterated function has a J-symmetric attractor that is independent of the initial point of the iteration. This situation is theoretically well-understood when the elements of F satisfy appropriate Lipschitz conditions (see, for example, [,chapter 9]).

### 3.3  Wallpaper patterns through dynamics

We conclude this section with some examples of wallpaper patterns constructed via dynamics.

Figure
Figure 3: Wallpaper patterns of types pmm and pmg

In Figure 3, we show two quilts generated using an iterated function system. The quilt on the left is of type pmm and the generating function was chosen so as to give an angular effect. As the measures produced by this algorithm are often rather flat, we have given a 3-dimensional effect to the image by using the embossing option of the gimp software package. The image on the right is of type pmg and is a grey scale version of `Blue Columns', a picture that has been exhibited at a number of centers in Spain as part of The Frontier between Art and Science, International Exhibition.

 Figure

Figure 4: Wallpaper patterns of types p6m and pmm

In Figure 4, we show two quilts generated using a deterministic algorithm. The quilt on the left is of type p6m, the one on the right of type pmm. Both patterns are grey scale versions of pictures that were originally designed as possible entries for an additional display during the visit of the The Frontier between Art and Science exhibition to Granada. Eventually, the second image was chosen for the exhibition.

## 4  Two-colour Patterns

We start by reviewing the definition and basic properties of two-colour wallpaper patterns. We then introduce a definition of two-color pattern suitable for the analysis and description of dynamically generated patterns. We conclude by showing some examples of two-coloured patterns

### 4.1  Two-colour wallpaper patterns

The reader may find definitions of two-colour patterns in Grünbaum and Shephard [,chapter 8] and Washburn & Crowe []. Roughly speaking, a 2-colour wallpaper pattern P Ì \mathbbR2 is a wallpaper pattern that uses two colours and is such that

(a) Every symmetry of the (uncoloured) pattern either reverses or preserves colour.
(b) There exist color reversing symmetries.

Woods [] showed that there were exactly 46 2-colour wallpaper patterns. Examples of all 46 of the 2-colour wallpaper patterns may be found in the books by Washburn & Crowe and Grünbaum and Shephard cited above (see also the article by Coxeter []). There are two notations for the 2-colour wallpaper patterns, one due to Belov the other to Coxeter. In what follows we shall assume some familiarity with both notations (see [,§ 3.4.2]).

In Figure  we show a simple example of a two-color pattern of type pg¢ (Belov's notation). In this case, the uncolored pattern has symmetry pg. Translational symmetries preserve colour, while glide reflection symmetries (along either of the glide lines a or b) reverse colour. There are no other symmetries of the pattern. Note that either of the sets Pr, Pb is a wallpaper pattern of type p1. Hence, if we use Coxeter's notion, the pattern is of type pg/p1.

Figure
Figure 5: A 2-colour pattern of type pg¢

Even for two-colour tilings of the plane, there are some subtleties in giving an unambiguous definition. Indeed, if we assume tiles are closed (or open) sets, then either some points of the plane are not covered in the tiling or some (boundary) points are covered at least twice and by tiles of different colours. Since we intend working with dynamically generated sets which may have a very large fractal boundary we need to take some care with definitions.

Figure
Figure 6: A 2-colour pattern of type p4m¢m¢ (p4m/p4)

As a way of motivating our definition, suppose that P is a two-colour wallpaper pattern. Suppose that the colors used in the pattern P are red and blue. Let Pr denote the red points, Pb the blue points. We shall assume that Pr is a closed subset of \mathbbR2. Since there exist colour reversing symmetries of P, Pb is also closed. It follows that the background - the set of points B(P) of \mathbbR2 that do not lie in P - is not empty. Necessarily, the background B(P) is preserved by all the symmetries of P. The pattern shown in Figure 6 satisfies these conditions (The pattern of Figure 5 does not as there is overlap between Pr and Pb along the line b).

If we denote the wallpaper group of the uncolored pattern P by G and the subgroup of color preserving symmetries of P by Gp, then it is easy to see that the quotient group G/Gp @ \mathbbZ2 - the cyclic group of order two.

We abstract this example in the following way. [cf []] A two-colour wallpaper pattern consists of a triple (P,P1,P2) of wallpaper patterns satisfying

(1) P = P1 ÈP2.
(2) If g is an element of the wallpaper symmetry group of P, then either g P1 = P1 or g P1 = P2.
(3) There exists at least one symmetry g of P such that g P1 = P2.

In the sequel we refer to P1,P2 as subpatterns of the two-colour pattern P. Note that in our definition we do not require P1 and P2 to be disjoint. Indeed, we allow P = P1 = P2.

Without further structure, Definition 4.1 adds rather little. Let O(P) = P1 ÇP2 - the overlap. If the overlap is empty or, allowing for boundaries, is of measure zero, we are in the situation described above. If there is an overlap, then we can assign a new colour to O(P). In this way, our two-colour pattern uses four colors corresponding to the sets P1, P2, B(P), and O(P). All symmetries of the pattern P will preserve the colours on B(P), and O(P).

Matters become much more interesting when we add dynamics.

### 4.2  Two-color quilts from dynamics

Suppose that we want to construct two-colour wallpaper patterns of type p/q (Coxeter's notation). Noting Definition 4.1, it suffices to construct a subpattern P1 of type q. Once we know P1, we can apply a colour reversing symmetry to obtain P2 and hence P = P1ÈP2 - a pattern of type p. In what follows, we work on the associated torus. Everything we say lifts immediately to \mathbbR2.

Let J and Js denote the point group associated to p and q respectively. Note that we can and do always regard Js as an index two subgroup of J.

Let P1 be a pattern of type q constructed by dynamics. We can represent P1 by a pair (X1,x1), where X1 Ì \mathbbT2 is a Js-symmetric attractor and x1 is a Js-invariant density (function) on X1. It follows by symmetry that if g Î J \Js, then X2 = g X1 will be a Js-symmetric attractor and x2 = x1 °g is a Js-invariant density on X2. Neither Js nor x2 depends on the particular choice of g Î J \Js.

Set X = X1 ÈX2. Extend xi to X by setting xi equal to zero on the complement of Xi in X, i = 1,2. Define the vector density x: X ®\mathbbR2 by x = (x1,x2). We also define xr = (x2,x1). Symmetry properties of x are given in the following lemma. [[]] Let x Î X, g Î J, then

 x(gx)
 =
 x(x),    (g Î Js)
 =
 xr(x),    (g Ï Js).

[[]] A 2-colouring of (X,x) consists of a map C: X ®C that can be factored

 C = F °x,
where F: \mathbbR2 ®C.

It follows from the definition that the colour assigned to a point x Î X depends only on the densities x1(x), x2(x). Further, it is a consequence of lemma 4.2 that points related by symmetries in Js have the same colour. On the other hand, points symmetrically related by symmetries in J \Js will generally have different colours - unless the map F is symmetric: F(x,y) = F(y,x). In general, symmetries of a dynamically generated two-colour pattern will either preserve colours or symmetrically interchange colours. There is no restriction to two colours. In practice, we typically work from a palette of thousands of colours.

There are many different ways of implementing two-colouring algorithms. We refer the reader to [] for more details and examples. Roughly speaking, our two-colourings depend on symmetry and dynamics in the sense that colours measure the probability of lying in one of the subpatterns as well as the statistics of the iteration on the subpattern. For this reason, colour palettes are typically two-dimensional arrays of colour.

### 4.3  Numerical Algorithms

In the previous sections we have already described all that is required to construct two-colour wallpaper patterns using deterministic algorithms. It turns out that there is an elegant way to construct two-colour wallpaper patterns using non-deterministic algorithms. This method was devised and implemented, in collaboration with Marty Golubitsky, in 1992. An example will suffice to explain the general method. Suppose we want to construct a two-colour wallpaper pattern of type p4m¢m¢. In this case the point group J = \mathbbD4 and Js = \mathbbZ4. Let f be a mapping of the torus and F denote the corresponding iterated function system symmetrized over \mathbbD4. Let Fs be the subset of F defined by symmetrizing over \mathbbZ4. We carry out the usual random iteration but now construct two subsets X1, X2 of the torus according to the following rule. Suppose that we have constructed xm, then xm+1 Î X1 if xm+1 = h xm, where h Î Fs. Otherwise xm+1 Î X2. A particularly nice feature of this scheme is that it allows one to see changes in the structure of the subpatterns Xi without changing the underlying pattern X. The three patterns in Figure  were all obtained by symmetrizing the same generating function over different point groups.

Figure
Figure 7: Two-colour patterns of type p4¢m¢m, p4¢mm¢, and p4m¢m¢.

Reading from left to right, the subpatterns in Figure 7 are of type cmm, pmm and p4. Ignoring colour, all three patterns are of type p4m.

### 4.4  Examples of two-colour designs

We conclude with some examples of two-colour designs that we have created using the ideas described above. All the patterns we show were computed using deterministic algorithms.

In Figure , we show Armies of the Night, a two-colour pattern of type c¢m. The original of this picture is printed on thirty inch square photographic paper and is being exhibited in the Eighth New York Digital Salon.

Figure  is an example of a pattern of type p4g¢m¢.

The images shown in Figures  and were both studies created in connection with the special exhibit in Granada held in association with the The Frontier between Art and Science, International Exhibition. The first image is a pattern of type p6¢mm¢ and colours were deliberately chosen to give a slightly faded appearance to the picture. The final image is a two-colour pattern of type p6¢.

Figure
Figure 8: Armies of the Night: Two-colour pattern of type c¢m

Figure
Figure 9: Two-colour pattern of type p4g¢m¢

Figure
Figure 10: Study for Alhambra: Two-colour pattern of type p6¢mm¢

Figure
Figure 11: Two-colour pattern of type p6¢

Figure

## References

[]
M A Armstrong. Groups and Symmetry, (Undergraduate texts in Mathematics, Springer-Verlag, New York, Berlin, Heidelberg, 1988).
[]
L Arnold. Random Dynamical Systems (Springer Monographs in Mathematics, Springer-Verlag, Berlin-Heidelberg, 1998).
[]
G Bain. Celtic Art: The Methods of Construction (Dover Publications, 1973).
[]
M F Barnsley. Fractals Everywhere (Academic Press, San Diego, 1988).
[]
P Chossat and M Golubitsky, Symmetry increasing bifurcations of chaotic attractors, Physica D 32 (1988), 423-436.
[]
H S M Coxeter. `Colored symmetry', In: M C Escher: Art and Science (eds H S Coxeter et al, Elsevier, Amsterdam and New York), (1986), 15-133.
[]
K Falconner. Fractal Geometry (John Wiley & Sons, Chichester, 1990).
[]
M J Field. `Harmony and Chromatics of Chaos', In: Bridges, Mathematical Connections in Art, Music, and Science, Proc. of the 1999 Bridges Conference, Southwestern College, Kansas.
[]
M J Field, Color Symmetries in Chaotic Quilt Patterns, In: Proc. ISAMA 99, (Eds. N Friedman, J Barrallo), San Sebastian, Spain, 1999.
[]
M J Field, The Art and Science of Symmetric Design, In: Bridges, Mathematical Connections in Art, Music, and Science, Proc. of the 2000 Bridges Conference (Ed Reza Sarhangi, Southwestern College, Kansas, 2000).
[]
M J Field. Designer Chaos, J. Computer Aided Design, to appear.
[]
M J Field, Mathematics through Art - Art through Mathematics, Proc. MOSAIC 2000, to appear.
[]
M J Field. `Dynamics, Chaos and Color Symmetry: The design of two-color quilt patterns', in preparation.
[]
M J Field and M Golubitsky, Symmetry in Chaos, (Oxford University Press, New York and London, 1992).
[]
M J Field, I Melbourne and M Nicol. `Symmetric Attractors for Diffeomorphisms and Flows', Proc. London Math. Soc., (3) 72 (1996), 657-696.
[]
B Grünbaum and G C Shephard. Tilings and Patterns. An Introduction, (W H Freeman and Company, New York, 1989).
[]
S. Jablan. Theory of Symmetry and Ornament , Mathematics Institute, Beograd, 1995.
[]
C S Kaplan. `Computer generated Islamic star patterns', In: Bridges, Mathematical Connections in Art, Music, and Science, Proc. of the 2000 Bridges Conference (Ed Reza Sarhangi, Southwestern College, Kansas, 2000).
[]
I Melbourne, M Dellnitz and M Golubitsky. `The structure of symmetric attractors', Arch. Rat. Mech. Anal. 123 (1993), 75-98.
[]
D Washburn and D Crowe. Symmetries of Culture, (University of Washington Press, Seattle, 1988).
[]
H J Woods. `The Geometrical basis of pattern design. Part 4: Counterchange symmetry in plane patters', Jn. of the Textile Institute, Trans. 27 (1936), 305-320.

### Footnotes:

1We refer the reader to the book Symmetry in Chaos  [] for a more leisurely and elementary introduction to these ideas and to [,] for more recent developments.

2For our applications we typically fix a probability measure on {1,¼,n} and take the corresponding Bernoulli product measure on S(n).

3We might equally well have started with a finite set of affine linear contractions.

File translated from TEX by TTH, version 2.78.
On 21 Oct 2000, 15:26.