Iterated Function Systems, a Tiny Recipe for a Shape, math that surprises you lesson

Take three rules, each moving every point of the plane halfway toward one corner of a triangle. Apply all three to a square, keep the three small squares they make, and then do the same to the new picture, again and again. Start instead from a triangle or a circle and the first pictures look different, yet after a few rounds they all resemble Sierpinski’s triangle. Why does the starting picture stop mattering, and what exactly are the pictures approaching? This page explains how a handful of shrinking rules decides a whole shape, describes the shape as a set that the rules reproduce, and shows why exactly one such set exists.

Key terms

Iterated function system

Definition An iterated function system is a finite list of maps $f_1, f_2, \ldots, f_k$ , with $k \ge 1$ , each sending points of the plane to points of the plane and each a contraction in the sense of the next card. Some books allow maps that are not contractions, and then the conclusions below can fail. For a set $S$ of points, $f_i(S)$ is the set of all images $f_i(p)$ of points $p$ in $S$ , a copy of $S$ made by the map. The system acts on a whole set by keeping every copy,

\begin{aligned} F(S) &= f_1(S) \cup f_2(S) \\[0.4em] &\quad \cup \cdots \cup f_k(S). \end{aligned}

Starting from a nonempty set $S_0$ that is closed and bounded, it produces the stages $S_1 = F(S_0)$ , $S_2 = F(S_1)$ , and so on. A set is bounded when it fits inside some circle, and closed when it contains every point that points of the set come arbitrarily close to. A filled triangle together with its edges is closed, and the same triangle without its edges is not. The answer to the opening question is that the stages approach one and the same set, called the attractor of the system, whichever nonempty, closed and bounded set $S_0$ is used. The starting set leaves its mark only on the early stages. The chaos game uses the same maps in another way. It follows a single point and applies one randomly chosen map at each step, and when every map has a positive probability and the choices are independent, its points come arbitrarily close to every point of the same attractor, with probability $1$ .

In plain words The recipe says how to make a few smaller copies of a picture and where to put each one. Applying it to the whole picture and repeating gives a sequence of pictures, and they settle down to a shape that depends only on the recipe.

Example The three maps

\begin{aligned} f_1(x, y) &= \bigl(\tfrac{x}{2}, \tfrac{y}{2}\bigr), \\[0.4em] f_2(x, y) &= \bigl(\tfrac{x + 1}{2}, \tfrac{y}{2}\bigr), \\[0.4em] f_3(x, y) &= \bigl(\tfrac{x}{2}, \tfrac{y + 1}{2}\bigr) \end{aligned}

move every point halfway toward the corner $(0, 0)$ , $(1, 0)$ or $(0, 1)$ of a right triangle. Start with the filled unit square $S_0$ , the points with $0 \le x \le 1$ and $0 \le y \le 1$ . The three copies are squares of side $\tfrac12$ in its lower left, lower right and upper left corners, so $S_1$ is the square with its upper right quarter missing. Each later round replaces every square by three squares of half the side in the same arrangement, so $S_n$ consists of $3^n$ squares of side $2^{-n}$ with total area $(3/4)^n$ . Starting instead from the filled triangle with corners $(0, 0)$ , $(1, 0)$ and $(0, 1)$ , the stage $S_n$ consists of $3^n$ triangles with total area $\tfrac12 (3/4)^n$ . The two sequences look different at first, but both close in on the same set, a Sierpinski triangle with its right angle at $(0, 0)$ . It is usually drawn on an equilateral triangle, and the right triangle only keeps the arithmetic simple.

Contraction mapping

Definition Write $\lvert p - q \rvert$ for the distance between points $p$ and $q$ of the plane. A map $f$ from the plane to itself is a contraction mapping, or simply a contraction, if there is a number $r$ with $0 \le r < 1$ such that

\lvert f(p) - f(q) \rvert \le r \, \lvert p - q \rvert

for all points $p$ and $q$ . The smallest such $r$ is the contraction ratio of $f$ . One number $r$ has to work for every pair of points, so a map that shortens every distance, but by factors that come arbitrarily close to $1$ , is not a contraction. A finite list of contractions has a largest ratio, and it is again less than $1$ . Every contraction of the plane has exactly one fixed point, a point $p$ with $f(p) = p$ , and applying $f$ over and over to any starting point brings it closer and closer to that fixed point. This is the Banach fixed point theorem. For a map of the form $(x, y) \mapsto (ax + by + s, \; cx + dy + t)$ with fixed numbers $a$ , $b$ , $c$ , $d$ , $s$ and $t$ , every segment pointing in the same direction is stretched by the same factor. Such a map is a contraction exactly when the largest of these factors, over all directions, is less than $1$ , and that largest factor is its ratio. Checking that each coefficient is small does not settle it.

In plain words A contraction pulls every two points closer together, always by at least the same factor. It may also turn, flip or squash a picture, as long as every distance shrinks by that factor or more.

Example Each of the three maps above halves every distance exactly, because $f_i(p) - f_i(q) = \tfrac12 (p - q)$ , so its ratio is $\tfrac12$ . The fixed point of $f_3$ is the corner $(0, 1)$ that it pulls toward. The map $(x, y) \mapsto (x/2, \; y/3)$ is a contraction with ratio $\tfrac12$ that shrinks vertical distances more than horizontal ones, so it turns a square into a rectangle that is not a square. A map that shrinks equally in every direction makes copies similar to the original, while a map like this one changes proportions, and the simple dimension formula for similar copies does not in general apply to such systems. Some maps are not contractions. A translation such as $(x, y) \mapsto (x + 1, \; y)$ and a rotation keep every distance, and $(x, y) \mapsto (2x, \; 2y)$ doubles every distance. The map $h$ that sends $(x, y)$ to $(0.7x + 0.7y, \; 0.7x + 0.7y)$ has every coefficient below $1$ , yet it sends $(0, 0)$ and $(1, 1)$ , which are $\sqrt{2}$ apart, to $(0, 0)$ and $(1.4, 1.4)$ , which are $1.4\sqrt{2}$ apart. It stretches that diagonal by the factor $1.4$ , so it is not a contraction.

Invariant set

Definition A set $A$ of points is invariant under the system $f_1, \ldots, f_k$ if

\begin{aligned} A &= f_1(A) \cup f_2(A) \\[0.4em] &\quad \cup \cdots \cup f_k(A). \end{aligned}

The equation says two things. Every copy $f_i(A)$ lies inside $A$ , and every point of $A$ lies in at least one of the copies. The theorem in the next card shows that a system of contractions has exactly one invariant set that is nonempty, closed and bounded, and this set is its attractor. Other invariant sets can exist. The empty set is invariant under every system, and the whole plane is invariant under the three maps above, because each of them sends the plane onto the whole plane. That is why the theorem speaks only of nonempty, closed and bounded sets.

In plain words An invariant set reproduces itself under the recipe. Make the shrunken copies, put each one in its place, and the same set comes back, with nothing missing and nothing extra.

Example On the number line, take $f(x) = x/2$ and $g(x) = x/2 + 1/2$ . The interval $[0, 1]$ is invariant, since $f$ sends it to $[0, \tfrac12]$ and $g$ sends it to $[\tfrac12, 1]$ , and together these make $[0, 1]$ again. The same interval is not invariant under the pair $x/3$ and $x/3 + 2/3$ , because the copies $[0, \tfrac13]$ and $[\tfrac23, 1]$ leave out the middle third. The invariant set of that pair is the Cantor set. For the three maps of the plane above, the Sierpinski triangle $A$ is invariant. The copies $f_1(A)$ , $f_2(A)$ and $f_3(A)$ are its three half-size corner pieces, which together make up all of $A$ and touch only at the single points $(\tfrac12, 0)$ , $(0, \tfrac12)$ and $(\tfrac12, \tfrac12)$ .

Uniqueness of the attractor

Definition The Hausdorff distance $d_H(B, C)$ between two nonempty, closed and bounded sets $B$ and $C$ is the smallest number $d$ such that every point of $B$ lies within distance $d$ of some point of $C$ and every point of $C$ lies within distance $d$ of some point of $B$ . It is $0$ only when $B = C$ . Hutchinson’s theorem, proved by John Hutchinson in 1981, says the following. Let $f_1, \ldots, f_k$ be finitely many contractions of the plane, with $k \ge 1$ , and let $r < 1$ be the largest of their ratios. Then exactly one nonempty, closed and bounded set $A$ satisfies $A = F(A)$ . Moreover, for every nonempty, closed and bounded starting set $S_0$ the stages satisfy

d_H(S_n, A) \le r^n \, d_H(S_0, A),

so they approach $A$ . The same holds on a line, in space and, more generally, in any complete metric space, a space in which every sequence whose terms eventually stay arbitrarily close to one another has a limit in the space. The plane is complete. Each condition does work. A system made of one translation has no nonempty bounded invariant set, and a system made of one rotation about the origin, which keeps distances, leaves every circle centered at the origin invariant, so uniqueness fails. Completeness matters too. On the numbers $x$ with $0 < x \le 1$ , the map $x \mapsto x/2$ is a contraction, but no nonempty set of such numbers is invariant, because an invariant set containing $a$ would also contain $2a$ , $4a$ , $8a$ and so on, which eventually exceed $1$ . The point $0$ that the map pulls toward is missing from that space.

In plain words Suppose two different sets were both reproduced by the recipe, and measure how far apart they are. If every point of one is within $d$ of a point of the other, then every copied point is within $rd$ of the matching copied point, so one round of the recipe multiplies the mismatch by at most $r$ . Both sets come back unchanged, though, so their mismatch would be at most $r$ times itself, and since $r < 1$ only a mismatch of $0$ can do that. The same shrinking pulls any starting picture toward the attractor round after round.

Example For the three maps above, $r = \tfrac12$ . Let $Q$ be the filled unit square and $T$ the filled triangle inside it with corners $(0, 0)$ , $(1, 0)$ and $(0, 1)$ . Every point of $T$ lies in $Q$ , and the point of $Q$ farthest from $T$ is the corner $(1, 1)$ , at distance $\sqrt{2}/2$ from the nearest point $(\tfrac12, \tfrac12)$ of $T$ . So $d_H(Q, T) = \sqrt{2}/2$ , and after $n$ rounds the stage made from $Q$ and the stage made from $T$ are within Hausdorff distance

\frac{\sqrt{2}}{2} \cdot 2^{-n}

of each other, which after ten rounds is less than $0.0007$ . The same bound holds between the stage made from $Q$ and the Sierpinski triangle itself, since the triangle lies in $Q$ and the corner $(1, 1)$ is again the point of $Q$ farthest from it.

Check yourself

Start the three maps $f_1$ , $f_2$ , $f_3$ from the single point $(0, 0)$ . Find the stages $S_1$ and $S_2$ , and count the points of $S_n$ .

Show the answer

A single point is nonempty, closed and bounded, so it is an allowed starting set. The maps send $(0, 0)$ to $(0, 0)$ , $(\tfrac12, 0)$ and $(0, \tfrac12)$ , and these three points make up $S_1$ . Applying the three maps to each of them gives the nine points of $S_2$ ,

\begin{gathered} (0, 0), \ (\tfrac14, 0), \ (\tfrac12, 0), \\[0.4em] (\tfrac34, 0), \ (0, \tfrac14), \ (0, \tfrac12), \\[0.4em] (0, \tfrac34), \ (\tfrac12, \tfrac14), \ (\tfrac14, \tfrac12). \end{gathered}

Write the coordinates in binary. Each map shifts the digits of both coordinates one place to the right of the binary point and writes a new first digit, which is $1$ in $x$ and $0$ in $y$ for $f_2$ , $0$ in $x$ and $1$ in $y$ for $f_3$ , and $0$ in both for $f_1$ . So $S_n$ consists of the points $(a/2^n, \; b/2^n)$ where $a$ and $b$ are whole numbers from $0$ to $2^n - 1$ whose binary forms never have the digit $1$ in the same place. Each of the $n$ digit places has three possibilities, so $S_n$ has $3^n$ points, all different. Every one of them lies in the Sierpinski triangle, because $(0, 0)$ does and the triangle is invariant, and by the theorem these finite sets approach the whole triangle. The same pairs $(a, b)$ are exactly those for which the binomial coefficient $\binom{a + b}{a}$ is odd, which is why Pascal’s triangle modulo 2 shows the same pattern.

On the number line keep $f(x) = x/2$ , but replace $g$ by the translation $h(x) = x + 1$ . Start from the set containing only $0$ . What happens to the stages, and does this system have an attractor?

Show the answer

The stages are $S_1 = \{0, 1\}$ , then $S_2 = \{0, \tfrac12, 1, 2\}$ and

S_3 = \{0, \tfrac14, \tfrac12, 1, \tfrac32, 2, 3\}.

Applying $h$ again and again to $0$ shows that $S_n$ contains the number $n$ , so the stages run off without bound. No nonempty, closed and bounded set $A$ can be invariant. Such a set would have a largest number $M$ , and then $h(M) = M + 1$ would lie in $h(A)$ , which is part of $A$ , although it is larger than $M$ . The theorem does not apply because $h$ keeps every distance, so it is not a contraction. Invariant sets still exist. The set of all numbers $x \ge 0$ is one, since $f$ sends it onto itself and $h$ sends it to the numbers $x \ge 1$ , but it is not bounded.

Use four maps instead of three, each moving every point halfway toward one corner of the unit square, the corners $(0, 0)$ , $(1, 0)$ , $(0, 1)$ and $(1, 1)$ . What is the attractor, and what do the stages starting from $(0, 0)$ look like?

Show the answer

The four copies of the filled unit square $Q$ are the four squares of side $\tfrac12$ that together make up $Q$ , so $Q = F(Q)$ . The square is nonempty, closed and bounded, so by the uniqueness of the attractor it is the attractor, and this recipe makes no fractal at all. Starting from $(0, 0)$ , the stage $S_n$ is the grid of $4^n$ points $(a/2^n, \; b/2^n)$ with $0 \le a \le 2^n - 1$ and $0 \le b \le 2^n - 1$ , since now every pair of binary digits is allowed. The point of $Q$ farthest from this grid is the corner $(1, 1)$ , at distance $\sqrt{2} \cdot 2^{-n}$ from the grid point $(1 - 2^{-n}, \; 1 - 2^{-n})$ . That is exactly the bound $r^n \, d_H(S_0, Q) = 2^{-n} \sqrt{2}$ from the theorem, because $(1, 1)$ is $\sqrt{2}$ away from $(0, 0)$ . Dropping the map toward $(1, 1)$ removes every grid point whose $a$ and $b$ share a binary digit $1$ , and the points that remain approach the Sierpinski triangle.

Iterated Function Systems, a Tiny Recipe for a Shape

Key terms

Iterated function system

Contraction mapping

Invariant set

Uniqueness of the attractor

Check yourself

How this lesson connects

Builds on

Used later in