In this article, I describe the design and colouring of planar symmetric patterns  in particular, twocolour 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 nontrivial 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 uptodate 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 twocolour 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 twocolour 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 nondeterministic (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 onecolour wallpaper patterns. In section 4, we provide a definition of twocolouring 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 twocoloured wallpaper patterns created using dynamics.
Suppose that X is a closed subset of \mathbbR^{2}. 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 S_{T} = SÇE_{T}(2) denote the group of translational symmetries of X.
We shall only be interested in patterns X for which S is a 0dimensional (discrete) subgroup of E(2). We recall the wellknown classification of discrete subgroups S of E(2).
Let F denote a set of n (continuous) planar maps f_{i}:\mathbbR^{2} ®\mathbbR^{2}, 1 £ i £ n. Let S(n) denote the space of all infinite sequences s = (s_{j})_{j ³ 1} of integers such that s_{j} Î {1,¼,n}, j ³ 1. Given x Î \mathbbR^{2}, s Î S(n), we define the sequence (x_{m}^{s})_{m ³ 0} Ì \mathbbR^{2} inductively by

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 (x_{i}^{s}) 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 f_{i} 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 (x_{m}^{s}) is sometimes relatively insensitive to the choice of initial point and sequence s. More precisely, let v(x,s) denote the vlimit set of the iteration (x_{m}^{s}). That is, y Î v(x,s) if there exists an infinite, strictly increasing sequence of integers n_{i} such that
 (2.1) 
A closed set X Ì \mathbbR^{2} is an attractor for the dynamical system defined by F if we can choose an open neighbourhood U of X such that
We are going to represent symmetric designs as attractors of symmetric dynamical systems. We consider both deterministic and nondeterministic 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
Let G Ì E(2) be finite. We consider (continuous) mappings f:\mathbbR^{2} ®\mathbbR^{2} which are Gsymmetric (equivariant). That is, if we apply a symmetry g Î G to x Î \mathbbR^{2} and apply f, the result is the same as if we apply the symmetry g to f(x). In symbols, for all x Î \mathbbR^{2}, g Î G, we have


Parts 1 and 2 of the next result follow easily from the Gsymmetry of f (see []). Suppose that X Ì \mathbbR^{2} is an attractor for the Gsymmetric map f:\mathbbR^{2} ®\mathbbR^{2}. Then
There are restrictions imposed by symmetry on the symmetries of attractors. For example, it is not possible to find a \mathbbD_{6}symmetric planar map f which has an attractor with \mathbbD_{3}symmetry, even though \mathbbD_{3} is a subgroup of \mathbbD_{6}. Further, if f has an attractor with \mathbbD_{6}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 Gsymmetric continuous planar mapping may not have an attractor. Even if we restrict to Gsymmetric 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 Gsymmetric attractors. However, numerical evidence suggests that Gsymmetric 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 Gsymmetric attractors. Unfortunately, numerical investigation also shows that small changes in the planar map can result in a nonfinite attractor changing to a finite attractor.
In Figure 1 we show the result of numerically iterating three maps with \mathbbD_{5}symmetry. The first map is defined by

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 d_{x} denote the Dirac probability measure supported at x. We assume that if X is a Gsymmetric attractor for the Gsymmetric 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 = 0}^{n1} d_{xi} converges (weakly) to a unique Ginvariant 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.
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 plane^{3}. 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 Gsymmetric attractor X. The attractor X supports a natural Ginvariant ergodic measure r such that for almost all x Î \mathbbR^{2} and sequences s Î S(n), [1/n] å_{i = 0}^{n1} d_{xis} 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 \mathbbD_{10}, \mathbbZ_{8} and \mathbbZ_{14}symmetry respectively.
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.
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 twocolor symmetry. Depending on the type of iteration and symmetry chosen, various algorithms are available. For example, if a dihedral group \mathbbD_{n}, n ³ 3, and deterministic iteration are selected, then one possibility is to use the family of \mathbbD_{n}symmetric polynomial maps

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 nondeterministic algorithms tend to need fewer iterations because the associated measures are often relatively uniform.
For onecolor 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 Gsymmetric compact attractor with associated ergodic measure r defined as a weak limit of Dirac measures along trajectories. Since X is Gsymmetric, if follows from the uniqueness of r, that r is Gsymmetric. 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 2colour 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
Let C denote a space of colours (for example, RGB or CMYKspace). 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

Without loss of generality, assume that X is contained in the unit square S in \mathbbR^{2}. Choose a large positive integer N. Let D denote the partition of S into N^{2} squares, each of side length 1/N. Let P(S) = {s Î D  s ÇX ¹ Æ}. Suppose that (x_{i}) 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 x_{1},¼, x_{n} enter s. (We ignore the question of iterates lying on the boundary of s and assume that every point of (x_{i}) lies in exactly one square from D.) We define a density function on X by

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 twocolour patterns and we discuss this later in section .
Let O(2) denote the orthogonal group consisting of all rotations about the origin and reflections in lines through the origin of \mathbbR^{2}. In what follows, we identify the group of translations E_{T}(2) with \mathbbR^{2}. Every transformation g Î E(2) can be written uniquely as g = r °t, where t Î \mathbbR^{2} and r Î O(2). It follows that we have a natural homomorphism p: E(2) ®O(2), defined by p(g) = r.
Let \mathbbZ^{2} = {(m,n)  m,n Î \mathbbZ} denote the integer lattice in \mathbbR^{2}. The quotient group \mathbbR^{2}/\mathbbZ^{2} is isomorphic to the twodimensional torus \mathbbT^{2}. Topologically, \mathbbT^{2} is the product of two circles, or the space obtained by identifying opposite edges of the unit square in \mathbbR^{2}. For future use, we define the hexagonal lattice \mathbbZ^{2}_{h} = {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 \mathbbR^{2}, it follows that the translational subgroup G_{T} of G is naturally identified with a (lattice) subgroup L of \mathbbR^{2}. Necessarily L is isomorphic to \mathbbZ^{2} and so \mathbbR^{2}/L is also isomorphic to \mathbbT^{2}  the isomorphism will depend on the choice of isomorphism between L and \mathbbZ^{2}. In the sequel we set \mathbbR^{2}/L = \mathbbT^{2}_{L} 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 \mathbbT^{2}_{L}. It follows that if X is a closed Jinvariant subset of \mathbbT^{2}_{L}, then the lift of X to \mathbbR^{2} 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 Jinvariance 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 \mathbbZ^{2}, \mathbbZ_{h}^{2}. 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 \mathbbZ^{2} 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 nonsingular diagonal matrix will lead to a pmm pattern supported on a general rectangular lattice.
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 Jinvariant attractor and r is a Ginvariant measure on X. In particular, we may (and often do) have X = \mathbbT^{2}. If the associated measure r has (say) only the trivial symmetry, then (X,r) will define a wallpaper pattern of type p1 .
We conclude this section with some examples of wallpaper patterns constructed via dynamics.
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 3dimensional 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 
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.
The reader may find definitions of twocolour patterns in Grünbaum and Shephard [,chapter 8] and Washburn & Crowe []. Roughly speaking, a 2colour wallpaper pattern P Ì \mathbbR^{2} is a wallpaper pattern that uses two colours and is such that
Woods [] showed that there were exactly 46 2colour wallpaper patterns. Examples of all 46 of the 2colour 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 2colour 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 twocolor 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 P_{r}, P_{b} is a wallpaper pattern of type p1. Hence, if we use Coxeter's notion, the pattern is of type pg/p1.
Even for twocolour 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.
As a way of motivating our definition, suppose that P is a twocolour wallpaper pattern. Suppose that the colors used in the pattern P are red and blue. Let P_{r} denote the red points, P_{b} the blue points. We shall assume that P_{r} is a closed subset of \mathbbR^{2}. Since there exist colour reversing symmetries of P, P_{b} is also closed. It follows that the background  the set of points B(P) of \mathbbR^{2} 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 P_{r} and P_{b} 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 G_{p}, then it is easy to see that the quotient group G/G_{p} @ \mathbbZ_{2}  the cyclic group of order two.
We abstract this example in the following way. [cf []] A twocolour wallpaper pattern consists of a triple (P,P_{1},P_{2}) of wallpaper patterns satisfying
In the sequel we refer to P_{1},P_{2} as subpatterns of the twocolour pattern P. Note that in our definition we do not require P_{1} and P_{2} to be disjoint. Indeed, we allow P = P_{1} = P_{2}.
Without further structure, Definition 4.1 adds rather little. Let O(P) = P_{1} ÇP_{2}  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 twocolour pattern uses four colors corresponding to the sets P_{1}, P_{2}, 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.
Suppose that we want to construct twocolour wallpaper patterns of type p/q (Coxeter's notation). Noting Definition 4.1, it suffices to construct a subpattern P_{1} of type q. Once we know P_{1}, we can apply a colour reversing symmetry to obtain P_{2} and hence P = P_{1}ÈP_{2}  a pattern of type p. In what follows, we work on the associated torus. Everything we say lifts immediately to \mathbbR^{2}.
Let J and J_{s} denote the point group associated to p and q respectively. Note that we can and do always regard J_{s} as an index two subgroup of J.
Let P_{1} be a pattern of type q constructed by dynamics. We can represent P_{1} by a pair (X_{1},x_{1}), where X_{1} Ì \mathbbT^{2} is a J_{s}symmetric attractor and x_{1} is a J_{s}invariant density (function) on X_{1}. It follows by symmetry that if g Î J \J_{s}, then X_{2} = g X_{1} will be a J_{s}symmetric attractor and x_{2} = x_{1} °g is a J_{s}invariant density on X_{2}. Neither J_{s} nor x_{2} depends on the particular choice of g Î J \J_{s}.
Set X = X_{1} ÈX_{2}. Extend x_{i} to X by setting x_{i} equal to zero on the complement of X_{i} in X, i = 1,2. Define the vector density x: X ®\mathbbR^{2} by x = (x_{1},x_{2}). We also define x^{r} = (x_{2},x_{1}). Symmetry properties of x are given in the following lemma. [[]] Let x Î X, g Î J, then

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

It follows from the definition that the colour assigned to a point x Î X depends only on the densities x_{1}(x), x_{2}(x). Further, it is a consequence of lemma 4.2 that points related by symmetries in J_{s} have the same colour. On the other hand, points symmetrically related by symmetries in J \J_{s} will generally have different colours  unless the map F is symmetric: F(x,y) = F(y,x). In general, symmetries of a dynamically generated twocolour 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 twocolouring algorithms. We refer the reader to [] for more details and examples. Roughly speaking, our twocolourings 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 twodimensional arrays of colour.
In the previous sections we have already described all that is required to construct twocolour wallpaper patterns using deterministic algorithms. It turns out that there is an elegant way to construct twocolour wallpaper patterns using nondeterministic 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 twocolour wallpaper pattern of type p4m¢m¢. In this case the point group J = \mathbbD_{4} and J_{s} = \mathbbZ_{4}. Let f be a mapping of the torus and F denote the corresponding iterated function system symmetrized over \mathbbD_{4}. Let F_{s} be the subset of F defined by symmetrizing over \mathbbZ_{4}. We carry out the usual random iteration but now construct two subsets X_{1}, X_{2} of the torus according to the following rule. Suppose that we have constructed x_{m}, then x_{m+1} Î X_{1} if x_{m+1} = h x_{m}, where h Î F_{s}. Otherwise x_{m+1} Î X_{2}. A particularly nice feature of this scheme is that it allows one to see changes in the structure of the subpatterns X_{i} without changing the underlying pattern X. The three patterns in Figure were all obtained by symmetrizing the same generating function over different point groups.
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.
We conclude with some examples of twocolour 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 twocolour 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 twocolour pattern of type p6¢.
^{1}We 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.
^{2}For our applications we typically fix a probability measure on {1,¼,n} and take the corresponding Bernoulli product measure on S(n).
^{3}We might
equally well have started with a finite set of affine linear contractions.