Classic Iterated Function Systems

Larry Riddle, Agnes Scott College

Binary Description of the Sierpinski Right Triangle

Here we consider a different construction for the Sierpinski gasket. Rather than starting with an equilateral triangle, we start with a right triangle (brown) with two sides of length 1. The rest of the construction proceeds as before. Remove the interior of the triangle (red) formed by the midpoints of the three sides. In each of the remaining three right triangles, remove the interior of the triangle formed by the midpoints of the three sides. Continue indefinitely. Below are the first three iterations. The limit is sometimes referred to as the Sierpinski right triangle.

First 3 iterations of the Sierpinski right triangle

We position the triangle in the first quadrant so that the two sides of unit length lie along the x-axis and y-axis. This means the Sierpinski right triangle lives in the unit square \(0 \le x \le 1,\,\) \(0 \le y \le 1.\) Then the IFS for this version of the Sierpinski right triangle can be written as follows:

$$\begin{array}{l} {f_1}({\bf{x}}) = \left[ {\begin{array}{cc} {0.5} & 0 \\ 0 & {0.5} \\ \end{array}} \right]{\bf{x}} \\ {f_2}({\bf{x}}) = \left[ {\begin{array}{cc} {0.5} & 0 \\ 0 & {0.5} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{c} {0.5} \\ 0 \\ \end{array}} \right] \\ {f_3}({\bf{x}}) = \left[ {\begin{array}{cc} {0.5} & 0 \\ 0 & {0.5} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{c} 0 \\ {0.5} \\ \end{array}} \right] \\ \end{array}$$

The Sierpinski right triangle is the unique attractor (invariant set) for this iterated function system.

Each point in the unit square can be represented by a pair of binary numbers of the form

\[\begin{array}{l} x =(0.{x_1}{x_2}{x_3}{x_4}\text{...}){}_{\small 2} = \displaystyle \sum_{k=1}^\infty\frac{x_k}{2^k} \\ y = (0.{y_1}{y_2}{y_3}{y_4}\text{...}){}_{\small 2} =\displaystyle \sum_{k=1}^\infty\frac{y_k}{2^k} \\ \end{array}\]

(where each digit is either 0 or 1). Dyadic rational numbers of the form \(k/2^n\) actually have two binary expansions, one that terminates in repeated 0's, and one that terminates in repeated 1's [ Dyadic Details]. For example, 3/4 is represented in binary either as \(0.110000...{}_{\small 2}\) or as \(0.101111...{}_{\small 2}\).

Proof

Claim. The Sierpinski right triangle is the set of all pairs (\(x\), \(y\)) such that for each position in the binary expansion, at least one of the corresponding binary digits of \(x\) and \(y\) in that position is 0, that is, $$S = \left\{ {(x,y) {\text{ in }} [0,1] \times [0,1]:{x_k}{y_k} = 0 {\text{ for all }} k} \right\}$$

Another way to say this is that there will never be a simultaneous (1,1) pair in these binary expansions. If either \(x\) or \(y\) is a dyadic rational, then the point will be in \(S\) if either of the binary expansions satisfies the condition in the definition of the set.

Examples

  1. The point with binary expansion \((0.001_{\small 2},0.\overline{110}_{\small 2})\) is in the Sierpinski right triangle. This point is \[ \begin{align} x &= 0.001_{\small 2} = 0.001000000\ldots_{\small 2} = \frac{1}{2^3} = \frac{1}{8} \\ y &= 0.\overline{110}_{\small 2} = 0.110110110\ldots_{\small 2} = \sum_{k=1}^\infty \frac{1}{2^{3k-2}} + \sum_{k=1}^\infty \frac{1}{2^{3k-1}} = \frac{\frac{1}{2}}{1-\frac{1}{8}} + \frac{\frac{1}{4}}{1-\frac{1}{8}} = \frac{4}{7}+\frac{2}{7} = \frac{6}{7} \end{align} \] There will never be a simultaneous (1,1) pair in these binary expansions.
    [Show plotted point in $S_5$]
     
  2. The point \((2/5,5/64)\) is not in the Sierpinski right triangle because \[ \begin{array}{r@{\;}c@{\;}l@{\;}c@{\;}l} \frac{2}{5} &=& 0.\overline{0110} &=& 0.0110\,\textcolor{blue}{\textbf{0}}\,\textcolor{red}{1}\,100110\ldots \\ \frac{5}{64} &=& 0.000101 &=& 0.0001\,\textcolor{blue}{\textbf{0}}\,\textcolor{red}{1}\,000000\dots \end{array} \] which has the first simultaneous (1,1) pair of binary digits at position 6 and the closest pair (0,0) in position 5. The conclusion does not change if the alternative binary extension \(5/64 = 0.000100\overline{1}_{\small 2}\) is used instead since the expansions for \(2/5\) and \(5/64\) would still have a simultaneous (1,1) in position 7. The point lies in the triangle with vertices $(\frac{12}{32},\frac{3}{32}),(\frac{13}{32},\frac{3}{32}),(\frac{13}{32},\frac{2}{32})$ that was removed during the 5th iteration in the construction of the Sierpinski right triangle.
    [Show plotted point]
     
  3. The point \((5/127, 37/63)\) is not in the Sierpinski right triangle. \[ \begin{array}{r@{\;}c@{\;}l@{\;}c@{\;}l} \frac{5}{127} &=& 0.\overline{0000101} &=& 0.00\,\textcolor{blue}{\textbf{0}}\,010\,\textcolor{red}{1}\,000010\ldots \\ \frac{37}{63} &=& 0.\overline{100101} &=& 0.10\,\textcolor{blue}{\textbf{0}}\,101\,\textcolor{red}{1}\,001011\dots \end{array} \] Here the first simultaneous (1,1) pair of binary digits is at position 7 and the closest pair (0,0) is in position 3. Since neither coordinate is a dyadic rational, there are no alternative extensions for either coordinate. The point lies in the triangle with vertices $(0,\frac{5}{8}),(\frac{1}{8},\frac{5}{8}),(\frac{1}{8},\frac{4}{8})$ that was removed during the 3rd iteration in the construction of the Sierpinski right triangle.
    [Show plotted point]
You Try It

Click the "You Try It" button to access a Sierpinski Right Triangle calculator that can determine if a point in the unit square, with coordinates that are rational or which have a repeating binary expansion, is in the Sierpinski right triangle.

The focus has been primarily on rational numbers in the interval [0,1] because all such rational numbers have a binary expansion that must eventually repeat. Thus we know exactly what digits are in the binary expansion of a rational number. It is therefore possible to compare the binary expansions for two rational numbers to decide whether or not the point with those coordinates are in the Sierpinski right triangle. However, an irrational number in the interval [0,1] has a binary expansion that is infinite, non-terminating, and non-repeating. It may be possible to decide that a point with one or two irrational coordinates is not in the triangle if you find simultaneous 1's in the same position of each binary expansion, but it is impossible except in special cases to determine if a point with an irrational coordinate satisfies the condition to be in the Sierpinski right triangle. The exception is that the all the line segments of the right triangles constructed during each iteration are in the Sierpinski right triangle, so any point on such a line segment that has an irrational coordinate will be in the triangle. For example, every point \((x,1/2)\) with \(0 \lt x \lt 1/2\) is in the triangle because the first binary digit of \(x\) will be 0 while \(1/2 = 0.10000\dots_{\small 2}\), so there will be no simultaneous (1,1) pairs. Thus the point $(\pi/8,1/2)$ is in the Sierpinski right triangle [Show plotted point].