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

Exercise Solutions

Exercise 1

Consider the following generator, $G$.

which acts by removing the middle third of line segments. Repeated application of $G$ results in the following fractal set, referred to as the Cantor set.

Determine an appropriate value of $r$ and use the scaling relation to find the fractal dimension, $D$, of the Cantor set.

Exercise 1 Solution

Letting $r=\frac{1}{3}$ we see that if it takes $N(ϵ)$ measuring sticks of length $ϵ$ (or $ϵ$-tiles if you prefer) to cover the Cantor set, then it will take $N\left(\frac{1}{3}ϵ\right)=2N(ϵ)$ measuring sticks of length $\frac{1}{3}ϵ$ to cover the Cantor set.

Putting this into the scaling relation we get $$\begin{array}{r}N\left(\frac{1}{3}ϵ\right)=2N(ϵ)=N(ϵ){\left(\frac{1}{3}\right)}^{-D}.\end{array}$$ Solving for $D$ yields $D=\frac{\log (2)}{\log (3)}\approx 0.63$. The Cantor set is somewhere between zero-dimensional and one-dimensional.

Exercise 2

Consider the linear function $f(x)=ax+b$. Show that when $0<a<1$, $f(x)$ is a contraction mapping on the domain $[0,1]$. Determine the contraction factor of $f$.

Exercise 2 Solution

To show that $f$ is a contraction mapping, consider $x$ and $y\in [0,1]$. We see that $$\begin{array}{rl}|f(x)-f(y)|& =|ax+b-(ay+b)|\\ & =|ax-ay+b-b|\\ & =|ax-ay|\\ & =a|x-y|\\ & \le a|x-y|.\end{array}$$ Since $0<a<1$, $f$ is a contraction mapping. The contraction factor of $f$ is $a$.

Problem Set Solutions

1. Consider the logistic function $f(x)=rx(1-x)$ where $0<r\le 4$. In the lesson we saw (by looking at a plot of the iterates) that when $r>3$ this function has a two-cycle. Now, let’s show it algebraically. Last week we learned that we can solve for the period two points of $f(x)$ by solving the expression $f^{[2]}(\overline{x})=\overline{x}$, however as $f(x)$ gets more complicated this can leave us with some messy equations to solve. In this question we will work through an easier way to solve for the two-cycle of $f(x)$.

   1. Let $\{p_1,p_2\}$ be the two-cycle of $f(x)$. In order for this to be a two-cycle we must have that $f(p_1)=p_2$ and $f(p_2)=p_1$. Use this fact to write down two expressions relating $p_1$ and $p_2$.

   2. Now subtract the two expressions you found in (a) and use the fact that $p_1\ne p_2$ to simplify the resulting expression. You should end up with an expression which is linear in both $p_1$ and $p_2$.

   3. Finally, substitute this expression back into one of the expressions you found in (a) to solve for either $p_1$ or $p_2$. Use this result to show that $f(x)$ only has a (real-valued) two-cycle when $r>3$.

   Solution:

   1. Using $f(p_1)=p_2$ and $f(p_2)=p_1$ we have the following two expressions $$\begin{array}{rl}r{p}_1(1-p_1)& =p_2\\ r{p}_2(1-p_2)& =p_1\end{array}$$ which relate $p_1$ and $p_2$.

   2. Subtracting the two expressions from (a) gives $$\begin{array}{rl}r{p}_1(1-p_1)-r{p}_2(1-p_2)& =p_2-p_1\\ r(p_1-p_2)-r(p_1^2-p_2^2)& =p_2-p_1\\ r(p_1-p_2)-r(p_1-p_2)(p_1+p_2)& =p_2-p_1.\end{array}$$ Since $p_2\ne p_1$ (by the definition of a two-cycle) we can divide both sides by $p_1-p_2$, resulting in $$\begin{array}{rl}r-r(p_1+p_2)& =-1\\ p_1+p_2& =\frac{1+r}{r}\\ p_1& =\frac{1+r}{r}-p_2.\end{array}$$

   3. Finally, we substitute our result from (b) back into one of our expressions from (a) to solve for $p_1$ or $p_2$. Since $p_1$ and $p_2$ are interchangeable in our initial formulation it doesn’t matter which one we solve for. $$\begin{array}{rl}r{p}_2(1-p_2)& =\frac{1+r}{r}-p_2\\ r{p}_2-r{p}_2^2& =\frac{1+r}{r}-p_2\\ r{p}_2^2-(r+1)p_2+\frac{1+r}{r}& =0.\end{array}$$ Using the quadratic formula we get $$\begin{array}{rl}{p}_2& =\frac{r+1}{2r}\pm \frac{\sqrt{(r+1{)}^2-4r\frac{1+r}{r}}}{2r}\\ & =\frac{r+1}{2r}\pm \frac{\sqrt{(r+1)(r-3)}}{2r}.\end{array}$$ Since $r>0$, this has two distinct (real) solutions when $r>3$. Thus, we have a two-cycle when $r>3$.

2. Consider a circle $C$ which has radius $1$. Now consider inscribing $C$ with a regular polygon $P_n$ which has $2^n$ equal sides, as shown in the figure below.

   

   The idea is that we can consider the length ($L_n$) of the perimeter of $P_n$ as an approximation for the circumference ($L=2\pi$) of the circle $C$.

   1. Write down an expression for $L_n$ (the length of the perimeter of $P_n$).

   2. CHALLENGE (You will need to be familiar with limits in order to solve this next part.) Show that $\underset{n\to \mathrm{\infty }}{lim}{L}_n=L=2\pi$.

      Hint: You may work with angles in either degrees or radians (if you are familiar with radians). You will need to use the fact that $\underset{x\to 0}{lim}\frac{\sin (x)}{x}=1$ (when $x$ is in radians) or that $\underset{x\to 0}{lim}\frac{\sin (x)}{x}=\frac{\pi }{180}$ (when $x$ is in degrees).

   Solution: Working with angles in degrees (solution using radians is very similar):

   1. To start, we need the length of each side of $P_n$, which is given by $$\begin{array}{r}2\cdot \sin \left(\frac{{\theta }_n}{2}\right)=2\cdot \sin \left(\frac{360\mathrm{°}}{2^{n+1}}\right)\end{array}$$ as seen on the following figure.

      

      Since $P_n$ has $2^n$ sides, the length of its perimeter is given by $$\begin{array}{rl}{L}_n& =2^n\cdot 2\cdot \sin \left(\frac{360\mathrm{°}}{2^{n+1}}\right)\\ & =2^{n+1}\cdot \sin \left(\frac{360\mathrm{°}}{2^{n+1}}\right).\end{array}$$

   2. 
      

      $$\begin{array}{rl}L=\underset{n\to \mathrm{\infty }}{lim}{L}_n& =\underset{n\to \mathrm{\infty }}{lim}{2}^{n+1}\cdot \sin \left(\frac{360\mathrm{°}}{2^{n+1}}\right)\\ & =\underset{n\to \mathrm{\infty }}{lim}\frac{\sin \left(\frac{360\mathrm{°}}{2^{n+1}}\right)}{\frac{1}{2^{n+1}}}\end{array}$$ Now, let $x_n=\frac{360\mathrm{°}}{2^{n+1}}$. As $n\to \mathrm{\infty }$, $x_n\to 0$. $$\begin{array}{rl}\underset{n\to \mathrm{\infty }}{lim}{L}_n& =\underset{x_n\to 0}{lim}\frac{\sin (x_n)}{\frac{x_n}{360\mathrm{°}}}\\ & =360\mathrm{°}\underset{x_n\to 0}{lim}\frac{\sin (x_n)}{x_n}\\ & =360\mathrm{°}\cdot \frac{\pi }{180\mathrm{°}}\\ & =2\pi \end{array}$$ which gives the desired result.

3. Consider the generator $G$ sketched below:

   

   where $0<r_1<1$, $0<r_2<1$ and $1<r_1+r_2<2$.

   1. Starting with the set $J_0=[0,1]$, sketch $J_1=G(J_0)$ and $J_2=G(J_1)$.

   2. What is the length of $J_1$ ($L_1$)? Of $J_2$ ($L_2$)? In general, can you find an expression for the length of $J_n=G^n(J_0)$?

   3. What do you expect to happen to the length of $J_n$ as $n$ gets infinitely large (i.e. as the set $J_n$ approaches the attractor)?

   Solution:

   1. $J_1$ and $J_2$ are as follows

      

   2. The length of $J_1$ is $L_1=r_1+r_2$.

      The length of $J_2$ is $L_2=r_1^2+2r_1{r}_2+r^2=(r_1+r_2{)}^2$.

      In general, $G$ scales the length of each line segment by a factor of $r_1+r_2$ so we can write $L_n=(r_1+r_2{)}^n$.

   3. Since $r_1+r_2>1$, $\underset{n\to \mathrm{\infty }}{lim}{L}_n=\underset{n\to \mathrm{\infty }}{lim}(r_1+r_2{)}^n=\mathrm{\infty }$. In other words, as $n$ gets infinitely large, the length of $J_n$ will approach infinity (meaning that the attractor has infinite length).

4. Consider the following two function iterated function system (IFS) on $[0,1]$, $$\begin{array}{r}{f}_1(x)=\frac{1}{5}x,f_2(x)=\frac{1}{5}x+\frac{4}{5}.\end{array}$$

   1. Let $I_0=[0,1]$ and $I_1=F(I_0)$ where $F$ is the parallel IFS operator composed of the two functions $f_1$ and $f_2$. Sketch $I_1$ on the real number line.

   2. Let $I_2=F(I_1)$. Sketch $I_2$ on the real number line.

   3. Let $I$ denote the limiting set (or attractor) of this IFS. Use the scaling relation to determine the fractal dimension $D$ of $I$.

      Hint: $D$ will be a ratio of two logarithms.

   Solution:

   1. $I_1$ is as follows

      

   2. $I_2$ is as follows

      

   3. Letting $r=\frac{1}{5}$ we see that $N(rϵ)=2N(ϵ)$ (one measuring stick of length one, two of length $\frac{1}{5}$, four of length $\frac{1}{25}$, etc...). Putting this into the scaling relation we get $$\begin{array}{r}N\left(\frac{1}{5}ϵ\right)=2N(ϵ)=N(ϵ){\left(\frac{1}{5}\right)}^{-D}\end{array}$$ which implies $$\begin{array}{rl}2N(ϵ)& =N(ϵ){\left(\frac{1}{5}\right)}^D\\ 2& =5^D\\ D& =\frac{\log (2)}{\log (5)}\approx 0.43.\end{array}$$

5. Show that the function $f(x)=x^2$ is a contraction mapping on the domain $[0,\frac{1}{4}]$. Determine the contraction factor of $f$.

   Solution: Let $x,y\in [0,\frac{1}{4}]$. Then $$\begin{array}{rl}|f(x)-f(y)|& =|x^2-y^2|\\ & =|x+y||x-y|\\ & \le \frac{1}{2}|x-y|.\end{array}$$ Therefore $f$ is a contraction mapping with contraction factor $\frac{1}{2}$ on the domain $[0,\frac{1}{4}]$.

6. Consider the image of the Sierpinski carpet, $S$, shown below. The Sierpinski carpet is a self-similar fractal which means that is a union of contracted copies of itself.

   

   1. Show (by circling them on the figure) that $S$ is made up of eight contracted copies of itself. What is the contraction factor of these copies?

   2. Determine the similarity dimension of $S$.

   Solution:

   1. We see that there are eight contracted copies of $S$, as shown on the following figure. We can also see from the figure that each copy of $S$ is scaled down by $\frac{1}{3}$, or has a contraction factor of $\frac{1}{3}$.

      

   2. Since $S$ is made up of eight copies of itself, each scaled by a factor of $\frac{1}{3}$, the similarity dimension of $S$ is $$\begin{array}{r}D=\frac{\log (8)}{\log (3)}\approx 1.89.\end{array}$$

7. Consider the image of the modified Sierpinski triangle, $S$, shown below.

   

   1. Show (by circling them on the figure) that $S$ is made up of three contracted copies of itself.

   2. Imagine starting with a right triangle, $S_0$, which has vertices at $(0,0)$, $(1,0)$, and $(0,1)$. Describe (in terms of contraction factors, translations, rotations, etc...) the three map IFS which you could use to construct $S$ from $S_0$.

   3. Determine the similarity dimension of $S$.

   4. CHALLENGE Describe a fourth map which could be added to the IFS you found in (b) so that the attractor of the IFS is a solid triangular region.

   Solution:

   1. We can see from the figure below that $S$ is made up of three contracted copies of itself.

      

   2. We can see from the figure that $S$ is made up of three scaled copies of itself, each contracted by a factor of $\frac{1}{2}$.

      The first map simply scales $S_0$ by $\frac{1}{2}$, resulting in the triangle in the bottom left corner. The second map scales $S_0$ by $\frac{1}{2}$ and translates it to the right by $\frac{1}{2}$, resulting in the triangle in the bottom right corner. Finally, the third map scales $S_0$ by $\frac{1}{2}$ and translates it upwards by $\frac{1}{2}$ to form the triangle in the top corner.

   3. The similarity dimension of $S$ is given by $$\begin{array}{r}D=\frac{\log (3)}{\log (2)}\approx 1.56.\end{array}$$

   4. If we want the attractor of the IFS to be a solid triangular region, we need to add a fourth map which will fill up the triangular gap in the middle. We can do this by defining a map which scales $S_0$ by $\frac{1}{2}$, rotates it by $180\mathrm{°}$ and translates it by $\frac{1}{2}$ up and to the right.