Grade 11/12 Math Circles
Dynamical Systems and Fractals Part 2

Strange Attractors

Last week we looked at discrete dynamical systems of the form $x_{n+1}=f(x_n)$ where $x_n$ represents the state of some physical system at time point $n$. We saw that such systems can have fixed points (when the state of the system reaches a certain value and stays there indefinitely) and periodic points (when the state of the system oscillates between some finite number of values). Dynamical systems (specifically non-linear dynamical systems) can also exhibit some really interesting aperiodic behaviour where the state of the system is attracted to a set of iterates (an orbit) which appears to be completely random and unpredictable.

One of the most well-known examples of this phenomenon systems is the logistic map - which is used as a model for the population growth and decline of a species. The logistic map is a dynamical system defined as follows: $$\begin{array}{r}{x}_{n+1}=f(x_n)=r{x}_n(1-x_n),\end{array}$$ where $x_n$ is a number between zero and one which represents the ratio of an existing population to the maximum possible population which can be supported by the environment. The constant $r$ represents the growth rate of the population. Typically we consider growth rates $0<r\le 4$ as values outside of this range lead to negative populations (which doesn’t make much physical sense!). For these values of $r$, the system is always attracted to some sort of stable orbit, which we call the attractor of the system and the properties of the attractor depend on the value of $r$.

When $r$ is less than one, the population rapidly dies off to zero (an attractive fixed point), regardless of the initial population. Then, as $r$ is increased we begin to see more interesting behaviour. When $r$ is between $1$ and $3$, the iterates are attracted towards a non-zero fixed point, i.e. the population approaches a stable value. This can be seen on the following figure, a plot of the first one hundred values of $x_n$ for $r=2.5$.

When $r$ is between $3$ and $1+\sqrt{6}$, the iterates are attracted to a stable two-cycle. As seen below (for $r=3.2$), this means that for large values of $n$, the population oscillates between two fixed values.

When $r$ is made even larger, we see that for values of $r$ between approximately $3.44949$ and $3.54409$ a four-cycle emerges, as shown on the following figure.

If we continued to increase $r$, we would see the emergence of an attractive $8$-cycle, $16$-cycle, etc... This is referred to as period-doubling. Eventually, $r$ surpasses a critical value of approximately $3.56995$ and the behaviour changes dramatically. For values of $r$ near this critical value most initial populations lead to orbits which are never periodic and appear random, and unpredictable, like the orbit shown in the next figure.

Although the iterates look like they could be randomly generated, the process is entirely deterministic (if we start with the same $x_0$ we will always get the exact same set of points). This type of behaviour is referred to as chaotic and the entire field of chaos theory is devoted to the study of such systems. In this lesson we will focus on one aspect of chaotic systems, that being the interesting geometric properties of the sets which they are attracted to (called strange attractors). For example, if we plot a large number of iterates $x_n$ on the real number line we can visualize the space occupied by the attractor of the logistic map in its chaotic regime ($r=3.7$). This is shown in the figure below.

At first glance, it seems like the orbit fills in most of the space on the real line. However, if we zoom in on a smaller region of the set, we see that more small gaps emerge. If we continue to zoom in, we would continue to see the emergence of more and more gaps. Although the attractor contains an infinite number of points (since the orbit never repeats itself), these points are all disconnected from each other (even if we zoom in REALLY close).

In multiple dimensions, strange attractors can look very visually striking. An example in two dimensions is the Hénon attractor, shown below.

Strange attractors have some unique mathematical properties, one being that they have fractional dimensions and are thus called fractal sets. Briefly, fractal sets are those which are too irregular to be described by our usual ideas of Euclidean geometry.

Measuring the Size of Fractal Sets

The precise definition of a fractal set is difficult to pinpoint - in fact, Benoît Mandelbrot (the mathematician who proposed the term fractal) is said to have proposed multiple definitions himself. One thing fractal sets do have in common is the idea of possessing detail at all scales like we saw in the previous example. This means that as we zoom in on part of a fractal set more detail continues to emerge. This strange property of fractal sets makes it difficult to measure their sizes. As a motivating example, let’s consider the coastline paradox - which refers to the counterintuitive observation that the coastline of a landmass does not have a well-defined length.

What we have seen is that for irregular curves, the higher the resolution you use to measure their length (i.e. the smaller the measuring sticks) the more detail you measure, leading to increasingly large length estimates. Now, in reality there is a limit to how small we can make our measuring sticks and thus to the level of detail we can measure when it comes to physical object like coastlines. On the other hand, mathematically we can study fractal sets which are infinite in nature. The simplest type of fractal sets which we can study are self-similar. This means that when we zoom in on any portion of the set, it looks similar to the original set. In other words, the set is made up a number of scaled down copies of itself. Let’s take a look at an example of a self-similar fractal.

Let’s now imagine that we want to measure the size of the von Koch curve. Since it is a curve, our first instinct would be to measure it’s length. Using the same approach we used for the coastline, we can approximate the length of the von Koch curve using finite measuring sticks. If we use measuring sticks of length ${ϵ}_n$, then our length estimate is given by $L_n=N({ϵ}_n){ϵ}_n$ where $N({ϵ}_n)$ is the number of measuring sticks of length ${ϵ}_n$ which are required.

Let us assume that the length of the line we started out with in the construction of the von Koch curve is one (i.e. $\ell =1$ in Example 2). Then if we use measuring sticks of length $\frac{1}{3}$ we will clearly need $4$ measuring sticks to cover the set. Setting ${ϵ}_1=\frac{1}{3}$ we have $L_1=4\cdot \frac{1}{3}$. If we shrink the rod further, letting ${ϵ}_2=\frac{1}{3^2}=\frac{1}{9}$ then we will require $4^2=16$ measuring sticks to cover the set, resulting in $L_2=16\cdot \frac{1}{9}$. A pattern is clearly emerging. If we let ${ϵ}_n=\frac{1}{3^n}$, then $$\begin{array}{r}{L}_n=4^n\cdot \frac{1}{3^n}={\left(\frac{4}{3}\right)}^n.\end{array}$$ Since $\frac{4}{3}>1$ if we let $n$ go to infinity (i.e. make the measuring rods really tiny), the length estimates will get larger and larger, never settling on a finite value. Just like the coastline example, the von Koch curve does not have a finite length!

So how can we measure the size of the von Koch curve? We could try measuring its area instead. We can estimate the area of an object in a similar way to length, but instead of measuring sticks we cover the set with $ϵ$-tiles, squares of side length $ϵ$, and let $A_n=N({ϵ}_n){ϵ}_n^2$. As we let $ϵ$ get very small, we require approximately the same number of $ϵ$-tiles to cover the set as we needed measuring sticks of length $ϵ$. Thus for large $n$ we have $$\begin{array}{r}{A}_n\approx 4^n{\left(\frac{1}{3^n}\right)}^2={\left(\frac{4}{9}\right)}^n.\end{array}$$ Since $\frac{4}{9}<1$, if we let $n$ go to infinity, our estimates of the area will get smaller and smaller, approaching zero.

In order to measure the size of the von Koch curve, it turns out we need some other type of measurement instead, a D-dimensional measurement, if you will. Consider the estimate $$\begin{array}{r}{L}^D(S)\approx N(ϵ){ϵ}^D\end{array}$$ where $ϵ$ is the number of $ϵ$-tiles required to cover the set. We can also write this as $$\begin{array}{r}{L}^D(S)=\underset{ϵ\to 0}{lim}N(ϵ){ϵ}^D.\end{array}$$ This definition is actually consistent with our usual ideas of measurement. If we let $D=1$ then we recover our definition of length (how we measure one-dimensional objects) and if $D=2$, we recover the definition of area (how we measure two-dimensional objects). We know that for the von Koch curve when $D=1$ we get an infinite measurement (length), and yet when $D=2$ we get a measurement (area) of zero, neither of which is particularly meaningful. Perhaps there is some fractional measure of $D$ (between one and two) which yields a finite measurement.

Let’s once again consider covering the von Koch curve with tiles of side length ${ϵ}_n=\frac{1}{3^n}$. Now the $D$-dimensional estimate of its size is $$\begin{array}{r}{L}^D({ϵ}_n)=N({ϵ}_n){ϵ}_n^D=4^n{\left(\frac{1}{3^n}\right)}^D={\left(\frac{4}{3^D}\right)}^n.\end{array}$$ As we consider letting $n$ go infinity, we see that if $\frac{4}{3^D}<1$, the result will be zero and if $\frac{4}{3^D}>1$, the result will be infinite. The only way we will have a finite measurement is if $\frac{4}{3^D}=1$. Solving for $D$ we have $$\begin{array}{rl}\frac{4}{3^D}& =1\\ 4& =3^D\\ \log (4)& =D\log (3)\\ D& =\frac{\log (4)}{\log (3)}\\ & \approx 1.26\end{array}$$ which is a number between one and two, as expected. This fractional number $D\approx 1.26$ is called the fractal dimension of the von Koch curve. For self-similar fractals like the von Koch curve we can compute this number exactly - in the real world we use numerical methods to estimate this number.

The result above can be written in another way, in terms of the scaling relationship between the number of $ϵ$-tiles (or measuring sticks) needed to cover the set and the number of $rϵ$-tiles (or measuring sticks) needed to cover the set (where $r$ is a scale factor which adjusts the size of the tiles/measuring sticks).

Going back to the von Koch curve briefly, it makes sense to let $r=\frac{1}{3}$. Then we see that if $N(ϵ)$ is the number of measuring sticks of length $ϵ$ required to cover the von Koch curve, then $N(rϵ)=N\left(\frac{1}{3}ϵ\right)=4N(ϵ)$. Putting this into the scaling relation we get $$\begin{array}{r}N\left(\frac{1}{3}ϵ\right)=4N(ϵ)=N(ϵ){\left(\frac{1}{3}\right)}^{-D}.\end{array}$$ Dividing both sides by $N(ϵ)$ and rearranging gives $$\begin{array}{r}{3}^D=4\to D=\frac{\log (4)}{\log (3)}\end{array}$$ which is in agreement with the dimension we found previously. Okay, now it’s your turn!

Iterated Function Systems

As we saw in the previous section, self-similar fractal sets can be constructed by a recursive procedure starting with a generator which we have thus far defined graphically. We can make this construction more precise mathematically using functions. Let’s take another look at the Cantor set from the previous exercise.

Example 3

Consider the following two functions which map the interval $I=[0,1]$ onto itself, $f_1(x)=\frac{1}{3}x$ and $f_2(x)=\frac{1}{3}x+\frac{2}{3}$. We will now examine the repeated action of $f_1$ and $f_2$ on the interval $I=[0,1]$. Instead of looking at where each function sends a single point $x\in [0,1]$, we will consider the action of each function sends sets of points in $I=[0,1]$.

For instance, we see that $f_1$ maps the point $x=0$ to $x=0$ and $x=1$ to $x=\frac{1}{3}$, and all other $x\in [0,1]$ somewhere inside this interval. We can write this as $f_1([0,1])=[0,\frac{1}{3}]$. In other words, $f_1$ shrinks the interval $[0,1]$ to $[0,\frac{1}{3}]$. Similarly, we find that $f_2([0,1])=[\frac{2}{3},1]$.

Now, instead of considering the action of $f_1$ and $f_2$ separately, let’s consider them acting in unison as a parallel operator, which we will call $F$. We define the action of $F$ on any subset $S$ of $[0,1]$ as follows, $$\begin{array}{r}F(S)=f_1(S)\bigcup f_2(S)\end{array}$$ where $\bigcup$ denotes taking the union of two sets, i.e. joining them together. To illustrate:

Image	Notation
	$I_0=[0,1]$
	${\displaystyle I_1=f_1([0,1])\bigcup f_2([0,1])=[0,1/3]\bigcup [2/3,1]}$
	${\displaystyle I_2=f_1([I_1])\bigcup f_2([I_1])}$
$⋮$	$⋮$
	${\displaystyle I_n}$

The parallel operator $F$ performs the same middle thirds dissection procedure used to produce the Cantor set. As a result, if we let $n$ go to infinity, the limiting set will be the Cantor set.

What we just saw is an example of an iterated function system. Before we can properly define an iterated function system, we first need the definition of a contraction mapping.

What this definition means is that a contraction mapping $f$ maps any two distinct points $x$ and $y$ in its domain closer to each other.

Linear functions, like $f_1$ and $f_2$ above (also called affine transformations) represent familiar geometrical transformations including scaling, reflection, translation, and rotation (in two dimensions). In our construction of self-similar fractal sets we will only consider affine transformations.

Now that we are familiar with the idea of contraction mappings we can define an iterated function system (IFS) properly.

The parallel operation of the functions $f_1$ and $f_2$ defined at the beginning of this section is an IFS which when iterated indefinitely generates the Cantor set.

Practically, this means that given a set of contraction maps, we can quickly construct the attractor set $A$, allowing us to generate images of many interesting fractal sets. We have defined iterated function systems in one dimension, however we can also generalize the definition to multiple dimensions to generate more interesting pictures which lie in two and three-dimensional space. We won’t formally define this, but we will look at an example of what this looks like graphically.

We could use the scaling relation to determine the dimension of the Sierpinski triangle, but it will be a little bit more difficult to work out a covering of the Sierpinski triangle with measuring sticks or tiles. Instead, we can compute something called the similarity dimension, which for a self-similar fractal set gives us the same dimensions we would get from the scaling relation.

Using the above definition, the dimension of the Sierpinski triangle is $$\begin{array}{r}D={\displaystyle \frac{\log (3)}{\log (2)}}\approx 1.56.\end{array}$$ This is between one and two, as we might have expected.