Binary Proof for 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. For example, 3/4 is represented in binary either as \(0.110000...{}_{\small 2}\) or as \(0.101111...{}_{\small 2}\).
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\}$$
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.
To see why this works, notice that the initial triangle \(S_0\) consists of all points (\(x\), \(y\)) in the unit square for which \(x + y \le 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\text{...}{}_{\small 2}\) in binary and write \(y = 0.011\text{...}{}_{\small 2}\) 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\}$$
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
$${f_1}(S) \cup {f_2}(S) \cup {f_3}(S) \subseteq S.$$
But suppose (\(x, y)\) is a point in \(S\). Then the digits in the first position of the binary expansions 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)\) will be in \(f_1(S)\), in the second case the point (\(x, y)\) will be in \(f_2(S)\), and in the third case the point (\(x, y)\) will be in \(f_3(S)\). Therefore
$$S \subseteq {f_1}(S) \cup {f_2}(S) \cup {f_3}(S)$$
and so we can conclude that
$$S = {f_1}(S) \cup {f_2}(S) \cup {f_3}(S).$$
Since this means that \(S\) is the unique attractor of this IFS, then \(S\) must be the Sierpinski right triangle.
Arithmetic/
Geometric
View
Why is it that an occurrence of a simultaneous pair of digits (1,1) in the binary expansion of the coordinates of a point will kick that point out of the Sierpinski right triangle? The interior of the middle triangle that is removed during the first iteration of the construction is the set
$$M_1 = \left\{(x,y) \in S_0 : x,y \lt \frac{1}{2} \text{ and } \frac{1}{2} \lt x+y \lt 1 \right\}$$
All the points in $M_1$ have binary expansions of the form $x = 0.0x_2x_3x_4\dots_{\small 2}$ and $y = 0.0y_2y_3y_4\dots_{\small 2}$ since the coordinates are less than 1/2. But the first binary digit of $x+y$ must be a 1 since $x+y \gt 1/2$. This means that there must be a carry when adding the binary digits of $x$ and $y$ so that the expansion of the sum has the form $0.1s_2s_3s_4\dots_{\small 2}$. If all the binary digit pairs are either (0,0), (1,0), or (0,1) , then there will never be a carry during the addition. Thus we will only have $x+y \gt 1/2$ if there is some value $k \ge 2$ where $x_k = y_k = 1$ in both binary expansions. So every point in $M_1$ must have a simultaneous pair of digits (1,1) in their binary expansion.
Let $M_k$ be one of the middle triangles that are removed from $S_{k-1}$ to form $S_k$ during the kth iteration, for $k \ge 1$. The parent triangle in $S_{k-1}$ that contains $M_k$ is of side length $2^{-(k-1)}$ and is affinely similar to $S_0$. This parent triangle can be translated to the origin and then scaled by a factor of $2^{k-1}$ to match the triangle $S_0$. Then the subtriangle $M_k$ will also be translated and scaled by a factor of $2^{k-1}$ to match $M_1$.
Let $(x,y)$ be a point in $M_k$. After the parent triangle containing $M_k$ is translated to the origin, the first $k-1$ binary digits in the translated points will be 0. Scaling by $2^{k-1}$ will then shift all the binary digits to the left by $k-1$ places. Let $(\hat{x},\hat{y})$ be the point obtained from $(x,y)$ after $M_k$ is translated and scaled. See the following diagram.
$ \begin{array}{r@{\;}c@{\;}l@{\;}c@{\;}l} \begin{array}{ll} x = 0.x_1x_2\dots x_kx_{k+1}x_{k+2}x_{k+3}\dots \\ y = 0.y_1y_2\dots y_ky_{k+1}y_{k+2}y_{k+3}\dots \end{array} & \xrightarrow{\text{translate}} & \begin{array}{ll} 0.\underbrace{00\dots0}_{k-1}x_kx_{k+1}x_{k+2}\dots \\ 0.\underbrace{00\dots0}_{k-1}y_ky_{k+1}y_{k+2}\dots \end{array} & \xrightarrow{\text{scale}} & \begin{array}{ll} \hat{x} = 0.x_kx_{k+1}x_{k+2}\dots \\ \hat{y} = 0.y_ky_{k+1}y_{k+2}\dots \end{array} \end{array} $
What this basically means is that $M_k$ can be mapped to $M_1$ by discarding the first $k-1$ binary digits in the coordinates. Now since $(\hat{x},\hat{y})$ will be in $M_1$, we must have $x_k = y_k = 0$ as shown above, and there must be a simultaneous pair of digits (1,1) in the binary expansions of $\hat{x}$ and $\hat{y}$. But these are the same binary digits starting with $x_{k+1},y_{k+1}$ as in the original $x$ and $y$, so the binary expansions of the point $(x,y)$ must also have the digit pair (1,1) somewhere after position $k$. Moreover, the first $k$ digits in the binary expansions can be used to determine exactly which triangle containing $(x,y)$ was removed at the kth iteration [Binary Details].
So all the triangles that are removed during the construction of the Sierpinski right triangle will consist of points whose coordinates will always contain at least one simultaneous (1,1) pair of binary digits. Therefore if a point does not have any simultaneous (1,1) pairs of digits in its binary expansion, it cannot be in any of the removed triangles, and so it must be in the Sierpinski right triangle.
