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.
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).
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
|
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
| (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
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
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
|
|
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
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.
In Figure 1 we show the result of numerically iterating three maps with \mathbbD5-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 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.
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.
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 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
|
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.
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
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
|
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
|
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 .
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.
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 .
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 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 |
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 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
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.
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.
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
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.
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
|
[[]] A 2-colouring 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 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.
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.
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 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¢.
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.