Classic Iterated Function Systems

Symmetric Fractals

In Symmetry in Chaos: A Search for Pattern in Mathematics, Art and Nature, Michael Field and Martin Golubitsky introduced the idea of a symmetric fractal generated from a single affine transformation combined with elements of a cyclic group $Z_n$ or a dihedral group $D_n$. Their method applies equally well to an iterated function system as it does to a single affine transformation.

The group $Z_n$ consists of the rotational symmetries of a regular n-sided polygon. We can let the n elements of $Z_n$ be represented by counterclockwise rotations about the origin (which corresponds to the center of the polygon) through angles that are integer multiples of 360°/n. The group $D_n$ consists of all $2n$ symmetries of a regular $n$-sided polygon. These are the $n$ rotations in $Z_n$ and the reflections about $n$ lines through the origin and a vertex or midpoint of a side. The following figure shows the symmetry reflections for an equilateral triangle ($D_3$) and a square ($D_4$) which are representative of what happens with regular polygons with odd and even number of vertices, respectively.

An exception is $D_2$ since there is no regular polygon with 2 sides. The group $D_2$ is known as the Klein four-group with the four elements being the identity, a vertical reflection, a horizontal reflection, and a 180° rotation.

Let $H$ be a set of $k$ affine transformations in an iterated function system. Let $G$ be a cyclic symmetry group or dihedral group of n elements. We can form a new set of functions by composing each of the symmetries in $G$ with each of the functions in H to form the set $F = \{f_r : 1 \le r \le m=kn\}$ where each $f_r = g \circ h$ for some $g$ in $G$ and some $h$ in $H$. Since each affine contraction in $H$ consists of rotations, scaling, and translations, each $g \circ h$ is again an affine contraction. Therefore $F$ will be an iterated function system with a unique attractor $B$.

We know that the attractor $B$ satisfies \[B = f_1(B) \cup f_2(B) \cup f_3(B) \cup \cdots \cup f_m(B)\] If $g$ is one of the symmetries in the group $G$, then \[g(B) = g \circ f_1(B) \cup g \circ f_2(B) \cup g \circ f_3(B) \cup \cdots \cup g \circ f_m(B)\] Now \(g \circ f_r = g \circ g_i \circ h_j\) for some \(g_i\) in $G$ and some \(h_j\) in $H$. Since applying $g$ to each of the elements of $G$ will just permute the elements of $G$, the collection \(g \circ f_r\) will consist of the same set of functions as in $F$. This means that the union of sets that make up $g(B)$ is the same union that gives $B$, and therefore $g(B) = B$. Therefore the attractor $B$ shares all the symmetries of the group $G$. See an example with $D_4$.

One of the methods for generating the attractor of an iterated function system on a computer is the random algorithm, also known as the "chaos game." First we choose an initial point \(x_0\) in the attractor. Then we choose a function \(f\) from the IFS at random (with a certain probability), and then we plot \(x_1 = f(x_0)\). This point is guaranteed to lie in the attractor. Next, we choose a function from the IFS again, apply it to \(x_1\), and obtain another point in the attractor, \(x_2\). This process of randomly choosing one of the functions, applying it to the last point plotted, then plotting the new point, is repeated millions of times. The sequence of points plotted this way will fill out the IFS's attractor. In fact, it is not really necessary to start with an initial point that actually lies in the attractor. Any initial point will suffice as long as you wait long enough during the iterative construction before starting to plot the computed points. This allows time for the sequence of transient points to converge towards the attractor set before the plotting begins.

Of course, even the highest resolution computer screen has only finitely many pixels. A single pixel can represent infinitely many points in the attractor. One possible coloring scheme for the random algorithm, therefore, is to color a pixel based on how many points in the random sequence land in that pixel. The next figure shows an image of the symmetric fractal obtained by composing the two elements of $Z_2$ with the two functions in the Heighway dragon IFS, along with the color gradient that shows the colors assigned to pixels depending on the number of times they were drawn during the random algorithm. We colored golden yellow, shading to bright orange, if the pixel count was between 1 and 5. Between a pixel count of 5 and 150 there is a gradient range going from bright orange to a pale orange. Any pixel hit more than 150 times was plotted as if the count had been exactly 150.

Some experimentation is usually needed to find a good color gradient and corresponding pixel counts depending on the size of the final image, the resolution of the computer screen, the number of points to be plotted, and even the probabilities assigned to the functions in the IFS. But an appropriate choice helps to vividly illustrate the symmetry of the attractor.

Image (Click for larger view)	Iterated Function System	Symmetry Group	Detail Links
	Heighway Dragon	$Z_2$	$Z_2$ Heighway
	Golden Dragon	$Z_2$	$Z_2$ Golden
	Koch Curve	$D_2$
	Koch Curve	$Z_4$
	Koch Curve	$D_4$
	Sierpinski Triangle	$Z_3$
	45° Binary Tree	$Z_4$
	45° Binary Tree	$Z_4$
	Single affine map scaling: 0.5 rotation: 180° translation: \(\left(\frac{1}{2},\frac{\sqrt{3}}{2}\right)\)	$Z_5$