Larry Riddle, Agnes Scott College

Binary Description of the Sierpinski Gasket

Here we consider a different construction for the Sierpinski gasket. Rather than starting with an equilateral triangle, we start with a right triangle with two sides of length 1. The rest of the construction proceeds as before. Remove the triangle formed by the midpoints of the three sides. In each of the remaining three right triangles, remove the triangle formed by the midpoints of the three sides. Continue indefinitely.

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 gasket lives in the unit square 0 ≤ x ≤ 1, 0 ≤ y ≤ 1.

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} \ldots \\ y = 0.{y_1}{y_2}{y_3}{y_4} \ldots \\ \end{array}$$

(where each digit is either 0 or 1). Dyadic rational numbers of the form k / 2n actually have two binary representations, one that terminates in repeated 0's, and one that terminates in repeated 1's. For example, 3/4 is represented in binary either as 0.110000... or as 0.101111...

The Sierpinski Gasket is the set of all pairs (x, y) such that for each position in the binary representation, at least one of the corresponding binary digits of x and y in that position is 0, that is,

$$SG = \left\{ {(x,y) {\text{ in }} [0,1] \times [0,1]:{x_k}{y_k} = 0 {\text{ for all }} k} \right\}$$

If either x or y is a dyadic rational, then the point will be in SG if either of the binary representations satisfies the condition in the definition of the set.

To see why this works, notice that S(0) consists of all points (x, y) for which x + y ≤ 1. Therefore, if the first binary digit of x is 1, so that x ≥ 1/2, then y must be less than 1/2, i.e. the first digit of y must be 0. The one exception to this is the case when x = 1/2 and y = 1/2. But in this case we can write x = 0.100... in binary and write y = 0.011... in binary. Likewise, if the first binary digit of y is 1, then the first digit of x must be 0. Thus S(0) must be the set

$$S(0) = \left\{ {(x,y) {\text{ in }} [0,1] \times [0,1]:{x_1}{y_1} = 0 } \right\}$$

The IFS for this version of the Sierpinski Gasket is

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

Multiplying a binary number by 0.5 shifts all the digits one place to the right and makes the first digit a 0. Adding 0.5 to such a binary number now converts the first digit to a 1. This means that the action of the three functions in the IFS can be described as follows:

$$\begin{array}{l} {f_1}(0.{x_1}{x_2}{x_3} \ldots ,0.{y_1}{y_2}{y_3} \ldots ) = (0.0{x_1}{x_2}{x_3} \ldots ,0.0{y_1}{y_2}{y_3} \ldots ) \\ {f_2}(0.{x_1}{x_2}{x_3} \ldots ,0.{y_1}{y_2}{y_3} \ldots ) = (0.1{x_1}{x_2}{x_3} \ldots ,0.0{y_1}{y_2}{y_3} \ldots ) \\ {f_3}(0.{x_1}{x_2}{x_3} \ldots ,0.{y_1}{y_2}{y_3} \ldots ) = (0.0{x_1}{x_2}{x_3} \ldots ,0.1{y_1}{y_2}{y_3} \ldots ) \\ \end{array}$$

Notice that for each function, the product of the digits in the first position of the image point is 0, and all relationships between the digits of x and y in position k now apply to the digits in position k+1 for the image point. This therefore implies that

$$\begin{array}{l} S(1) = {f_1}(S(0)) \cup {f_2}(S(0)) \cup {f_3}(S(0)) = \left\{ {(x,y):{x_1}{y_1} = 0{\text{ and }}{x_2}{y_2} = 0} \right\} \\ \end{array}$$

By induction, we can determine that

\begin{align} S(n + 1) &= {f_1}(S(n)) \cup {f_2}(S(n)) \cup {f_3}(S(n)) \\ &= \left\{ {(x,y):{x_1}{y_1} = 0{\text{ and }}{x_k}{y_k} = 0{\text{ for }}k = 2, \ldots ,n + 2} \right\} \\ \end{align}

for each value of n. Since the Sierpinski gasket is the intersection of all these sets, we get the description of SG given above.

There is a second way to see that the set SG described above must be the Sierpinski Gasket. The description of the action of the IFS in terms of the binary representation of the point shows that

$${f_1}(SG) \cup {f_2}(SG) \cup {f_3}(SG) \subseteq SG$$

But suppose (x, y) is a point in SG. Then the digits in the first position of the binary representations of x and y must either be 0 and 0, 1 and 0, or 0 and 1, respectively. In the first case the point (x, y) must be in f1(SG), in the second case the point (x, y) must be in f2(SG), and in the third case the point (x, y) must be in f3(SG). Therefore

$$SG \subseteq {f_1}(SG) \cup {f_2}(SG) \cup {f_3}(SG)$$

and so we can conclude that

$$SG = {f_1}(SG) \cup {f_2}(SG) \cup {f_3}(SG)$$

Since this means that SG is the attractor (invariant set) of this IFS, then SG must be the same as the Sierpinski Gasket.