Ternary Description of the Sierpinski Carpet
The figures below show the first four iterations in the construction of the Sierpinski carpet. The squares in red denote some of the smaller congruent parent squares used in the construction of the next iteration.
We consider the initial square \(C_0\) in the construction of the Sierpinski carpet to be \([0,1]\times[0,1]\) in the \(xy\)-plane. Each point in the unit square can be represented by a pair of base-3 (ternary) expansions of the form
\[\begin{array}{l} x = (0.{x_1}{x_2}{x_3}{x_4} \ldots)_{\small 3} = \displaystyle \sum_{k=1}^\infty\frac{x_k}{3^k} \\ y = (0.{y_1}{y_2}{y_3}{y_4} \ldots)_{\small 3} = \displaystyle \sum_{k=1}^\infty\frac{y_k}{3^k} \\ \end{array}\]
where each digit is either 0,1, or 2. Rational numbers of the form \(k/3^n\) actually have two ternary expansions, one that terminates in repeated 0's, and one that terminates in repeated 2's. For example, 4/9 is represented in ternary either as \(0.1100\overline{0}_{\small 3}\) or as \(0.1022\overline{2}_{\small 3}\) (the overbar over a sequence of digits indicates that the digit pattern keeps repeating infinitely.) All rational numbers between 0 and 1 have a ternary expansion that must eventually repeat [Rational Details].
Claim: The Sierpinski carpet is the set of all pairs \((x,y)\) that have a ternary expansion in which at least one of the corresponding ternary digits of \(x\) and \(y\) in each position is not 1, that is,
\[SC = \left\{ {(x,y) {\text{ in }} [0,1] \times [0,1]:(x_k,y_k) \ne (1,1) {\text{ for all }} k} \right\}\] or equivalently, \[SC = \left\{ {(x,y) {\text{ in }} [0,1] \times [0,1]:x_ky_k \ne 1 {\text{ for all }} k} \right\}\]
Via Carpet
Construction
Each of these nine subsquares corresponds to a pair of ternary digits \( x_1, y_1 \) where \(x_1\) determines which horizontal third the point lies in the square, and \(y_1\) determines which vertical third it lies in. More precisely:
- \(x_1 = 0\) means the point lies in the left third of the unit square,
- \(x_1 = 1\) means the middle third,
- \(x_1 = 2\) means the right third,
and similarly for \(y_k\) with bottom/middle/top. So, for example, all the points in the bottom left subsquare would have a ternary expansion starting with (0.0..., 0.0...). The exception is for points on the boundaries of the subsquares where one of the coordinates is of the form \(k/3\). These have two different ternary expansions. For example, \(x = 1/3\) can be written in base 3 as either \(0.100\overline{0}_{\small 3}\) (with \(x_1=1\)) or \(0.022\overline{2}_{\small 3}\) (with \(x_1=0\)). In the first expansion, the point would be taken to lie in the middle third, and in the second expansion the point would be taken to lie in the left third.
Among these nine subsquares, the one corresponding to the ternary digit-pair \(x_1=1,y_1=1\) is the open middle square. This is the square removed at stage 1 in the construction of \(C_1\). The points that remain in \(C_1\) must therefore have \(x_1\) or \(y_1\), or both, equal to 0 or 2. In either case, the product \(x_1y_1\) would be 0, 2, or 4. This can be expressed as saying that \[C_1 = \left\{ (x,y) \in C_0 : x_1 y_1 \ne 1 \right\}\]
A similar indexing can be done when each of the 8 parent squares in \(C_1\) are further subdivided into 3x3 congruent subsquares as shown in the figure below.
In this figure, the yellow parent subsquare in \(C_1\) on the left corresponds to the ternary index (2,1). That square is now subdivided into 3x3 congruent subsquares as shown on the right. Each of these nine subsquares corresponds to a pair of ternary digits \( x_2, y_2 \) with the same interpretation as above. So, for example, all the points in the bottom right subsquare would now have a ternary expansion starting with (0.22..., 0.10...). Each of the other parent subsquares in \(C_1\) would have a similar indexing when subdivided into 3x3 congruent subsquares. In each case, among these nine subsquares, the one with index corresponding to the ternary digit-pair \(x_2=1,y_2=1\) is the open middle square. These are the squares removed at stage 2 in the construction of \(C_2\), so what is left will satisfy \[C_2 = \left\{ (x,y) \in C_1 : x_2 y_2 \ne 1 \right\}\]
In general, consider a parent square remaining in \(C_{k-1}\), defined by the first \(k-1\) ternary digits of \(x\) and \(y\). When this square is partitioned into 9 subsquares of side length \(1/3^k\), the position of a point \((x,y)\) within this partition is determined by its \(k\)-th ternary digits \(x_k, y_k\). A point \((x,y)\) falls into the open middle square that is removed at step \(k\) in the construction of the Sierpinski carpet if and only if its \(k\)-th digits satisfy \(x_k=1,y_k=1\). Therefore \[C_k = \left\{ (x,y) \in C_{k-1} : x_k y_k \ne 1 \right\}\]
Since this is true for all \(k\) and the Sierpinski carpet is the intersection of all the sets \(C_k\), the point \((x,y)\) is a member of the Sierpinski carpet if and only if there are ternary expansions for \(x\) and \(y\) such that \(x_ky_k \ne 1\) for all values of \(k\). For points with non-unique expansions (e.g., \(4/3 = 0.1100\overline{0}_{\small 3} = 0.1022\overline{2}_{\small 3}\)), you can choose the expansion without a '1' in the critical position.
Notice that which subsquare at iteration $k$ contains a given point is completely determined by the first $k$ digits in the ternary expansion of the coordinates of the point. So if you know that a point is not in the Sierpinski carpet, and you know the ternary expansion of the coordinates, then you can easily determine which subsquare contained that point when it was removed. (See the examples below.)
Via Iterated
Function System
Therefore, the first ternary digit of both \(x\) and \(y\) is 1, and thus \(x_1y_1=1\) for all points \((x,y)\) in the middle square. Therefore \(C_1\) must be the set
\[C_1 = \left\{ {(x,y) {\text{ in }} [0,1] \times [0,1]:{x_1}{y_1} \ne 1 } \right\}\]
Now the IFS for this version of the Sierpinski carpet is
\[ \begin{align} f_1 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} \\ f_2 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} 0 \\ {1/3} \\ \end{array}} \right] \\ f_3 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} 0 \\ {2/3} \\ \end{array}} \right] \\ f_4 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {1/3} \\ 0 \\ \end{array}} \right] \\ f_5 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {1/3} \\ {2/3} \\ \end{array}} \right] \\ f_6 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {2/3} \\ {0} \\ \end{array}} \right] \\ f_7 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {2/3} \\ {1/3} \\ \end{array}} \right] \\ f_8 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {2/3} \\ {2/3} \\ \end{array}} \right] \\ \end{align} \]
Multiplying a ternary number by 1/3 shifts all the digits one place to the right and makes the first digit a 0. Adding 1/3 or 2/3 to such a ternary number after the shift then makes the first digit a 1 or a 2. This means that the action of the eight 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.0{x_1}{x_2}{x_3} \ldots ,0.1{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.2{y_1}{y_2}{y_3} \ldots ) \\ {f_4}(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_5}(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.2{y_1}{y_2}{y_3} \ldots ) \\ {f_6}(0.{x_1}{x_2}{x_3} \ldots ,0.{y_1}{y_2}{y_3} \ldots ) = (0.2{x_1}{x_2}{x_3} \ldots ,0.0{y_1}{y_2}{y_3} \ldots ) \\ {f_7}(0.{x_1}{x_2}{x_3} \ldots ,0.{y_1}{y_2}{y_3} \ldots ) = (0.2{x_1}{x_2}{x_3} \ldots ,0.1{y_1}{y_2}{y_3} \ldots ) \\ {f_8}(0.{x_1}{x_2}{x_3} \ldots ,0.{y_1}{y_2}{y_3} \ldots ) = (0.2{x_1}{x_2}{x_3} \ldots ,0.2{y_1}{y_2}{y_3} \ldots ) \\ \end{array}\]
Notice that for each function, the product \(x_1y_1\) of the ternary digits in the first position of the image point is 0, 2, or 4, and all relationships between the ternary digits of \((x,y)\) in position \(k\) now apply to the digits in position \(k+1\) for the image point. This therefore implies that
\[\begin{array}{l} C_2 =\displaystyle \bigcup_{m=1}^8{f_m}(C_1) = \left\{ {(x,y):{x_1}{y_1} \ne 1 {\text{ and }}{x_2}{y_2} \ne 1} \right\} \\ \end{array}\]
By induction, we can determine that
\[\begin{array}{l} C_{n+1} =\displaystyle \bigcup_{m=1}^8{f_m}(C_n) = \left\{ (x,y):{x_1}{y_1} \ne 1 \text{ and }{x_k}{y_k} \ne 1 \text{ for }k = 2, \ldots ,n + 1 \right\} \end{array}\]
for each value of \(n\). Since the Sierpinski carpet is \(\displaystyle \bigcap_{n=1}^\infty C_n\), the intersection of all these sets, we get the description of \(SC\) given above.
Examples
- Suppose one of the coordinates of a point \((x,y)\) has a ternary expansion consisting of only 0's and 2's. Then that point is in the Sierpinski carpet because there will never be a pair of ternary digits in the same position in the expansion of \(x\) and \(y\) where both digits are 1. For example,
all points of the form \((1/3,y)\) are in the Sierpinski carpet for \(0 \le y \le 1\). In other words, the entire line segment from \((1/3,0)\) to \((1/3,1)\) lies in the carpet. This is because the ternary expansion of \(1/3\) can be written as \(x = 1/3 = 0.0\overline2_{\small 3} = 0.02222\ldots_{\small 3}\,\).
- The point with ternary expansion \((0.\overline{10}_{\small 3},0.\overline{21}_{\small 3})\) is in the Sierpinski carpet. This point is \[ \begin{align} x &= 0.\overline{10} = 0.10101010\ldots_{\small 3} = \sum_{k=1}^\infty \frac{1}{3^{2k-1}} = \frac{\frac{1}{3}}{1-\frac{1}{9}} = \frac{\frac{1}{3}}{\frac{8}{9}} = \frac{3}{8} \\ y &= 0.\overline{21} = 0.21212121\ldots_{\small 3} = \sum_{k=1}^\infty \frac{2}{3^{2k-1}} + \sum_{k=1}^\infty \frac{1}{3^{2k}} = \frac{\frac{2}{3}}{1-\frac{1}{9}} + \frac{\frac{1}{9}}{1-\frac{1}{9}} = \frac{3}{4}+\frac{1}{8} = \frac{7}{8} \end{align} \]
-
The point \((4/9,1/2)\) is not in the Sierpinski carpet because
\[
\begin{array}{rclcl}
\frac{4}{9} &=& 0.11\overline{0} &=& 0.\textcolor{#B30000}{1}1000\ldots \\
\frac{1}{2} &=& 0.\overline{1} &=& 0.\textcolor{#B30000}{1}1111\dots
\end{array}
\]
and therefore this point is removed when the interior of the subsquare \([\frac{1}{3},\frac{1}{3}]\times[\frac{1}{3},\frac{1}{3}]\) is deleted during the first iteration in the construction of the carpet. It doesn't help if the alternative ternary extension \(4/9 = 0.10\overline{2}_{\small 3}\) was used instead since the expansions for \(4/9\) and \(1/2\) would still both have 1 as the initial digit in each expansion.
- The point \((6/17, 38/45)\) is not in the Sierpinski carpet.
\[
\begin{array}{rclcl}
\frac{6}{17} &=& 0.\overline{1001120212211020} &=& 0.1001\,\textcolor{#B30000}{1}\,202122\ldots \\
\frac{38}{45} &=& 0.21\overline{1210} &=& 0.2112\,\textcolor{#B30000}{1}\,012101\dots
\end{array}
\]
This point is removed when the interior of the subsquare \([\frac{85}{243},\frac{86}{243}]\times[\frac{205}{243},\frac{206}{243}]\) is deleted during the 5th iteration in the construction of the carpet.
- The point \((1199/1560, 6/13)\) is not in the Sierpinski carpet. \[ \begin{array}{rclcl} \frac{1199}{1560} &=& 0.2\overline{022020220110} &=& 0.2022020220\,\textcolor{#B30000}{1}\,100220\ldots \\ \frac{6}{13} &=& 0.\overline{110} &=& 0.1101101101\,\textcolor{#B30000}{1}\,011011\dots \end{array} \] This point is removed when the interior of the subsquare \([\frac{136153}{177147},\frac{136154}{177147}]\times[\frac{81760}{177147},\frac{81761}{177147}]\) is deleted during the 11th iteration in the construction of the carpet.
The focus has been primarily on rational numbers in the interval [0,1] because all such rational numbers have a ternary expansion that must eventually repeat. Thus we know exactly what digits are in the ternary expansion of a rational number. It is therefore possible to compare the ternary expansions for two rational numbers to decide whether or not the point with those coordinates are in the Sierpinski carpet. However, an irrational number in the interval [0,1] has a ternary 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 carpet if you find simultaneous 1's in the same position of each ternary expansion, but it is impossible in most cases to determine if a point with an irrational coordinate satisfies the condition to be in the Sierpinski carpet. The exception, as noted above, is if the other coordinate has a ternary expansion consisting only of the digits 0 and 2. In that case it doesn't matter what the ternary expansion of the other coordinate is. For example, the point \((10/13, \pi/4)\) is in the Sierpinski carpet because the ternary expansion for 10/13 is \(0.\overline{202}\) which will never include the digit 1.
Click the "You Try It" button to access a Sierpinski Carpet calculator that can determine if a point in the unit square, with coordinates that are rational or have a repeating ternary expansion, is in the Sierpinski carpet.
