# Unexpected occurrences of the Sierpinski triangle

The probably most well-known occurrence of the Sierpinski Triangle is as the odd entries of the Pascal triangle

Some month ago however, there was an article about mathematical models of sandpiles along with some images of computer simulations; it struck me to see the same nested triangles as in the Sierpinski triangle (cf e.g. here).

Then I recently wanted to list all pairs of disjoint subsets of some finite set; in order to be able to use bit operations, I iterated over all pairs of subsets encoded as binary numbers and checked whether BIT_AND-ing yielded zero. Much to my surprise, the Sierpinski triangle showed up again, when I visualized the outcome of the bit operation for each pair.



Question:

where else does the Sierpinski triangle, i.e. its fractally nested, regular triangle pattern, appear?

• In automata theory, this paper comes to mind: arxiv.org/pdf/1408.5937v1.pdf Mar 18 '16 at 19:48
• BTW, I strongly suspect that your result is closely related to the binomials-mod-2 visualization, via the Lucas/Kummer theorems: en.wikipedia.org/wiki/Lucas'_theorem Mar 18 '16 at 22:27
• Seemed to me like it's on almost every page of Wolfram's book Mar 19 '16 at 14:22
• @SteveHuntsman right, but after the 3rd page its not unexpected anymore. Mar 19 '16 at 15:39

In Hulk's underwear:

Presumably, because of the relative scale invariance compared to the other patterns? Or possibly they just thought of all the options that were near-'not'-high-contrast circles that Sierpinski Triangles were the coolest.

Note that the size of Mark Ruffalo and the weave of the material and/or pitch of the screen printing involved put a limit on the recursive depth...

It's the Vicon Motion Capture system.

• The mind boggles at any occurrence that would be more unexpected. Gerhard "Totally Did Not Expect That" Paseman, 2016.03.19. Mar 20 '16 at 6:55
• To me, that is the most unlikely place to expect the occurance of a Sierpinski triangle.. Mar 20 '16 at 14:14

The moves leading to the solution of the Towers of Hanoi puzzle form a Sierpiński triangle, as nicely described in this blog:

It is worth pausing a moment to think about this. The Tower of Hanoi is a mental experiment, a “game” devised by a human. It is not a “naturally occurring” phenomena such as a fractal snowflake or a symmetrical fern leaf - it is totally the product of human imagination. Yet the solution to this totally invented game, when graphed, has a strong resemblance to the Sierpiński triangle - which is a fractal. It could be argued that Sierpiński triangle is also the product of the human mind - yet this does not diminish the sense of surprise when the link between the two concepts is established. Why should this link exist? The sense that there is some intriguing connection between two such different things is tantalising.

Some altogether different appearances:

• This reminds me of a relationship between the Towers of Hanoi game and the fundamental group of the Menger curve in arxiv.org/abs/1310.7968 Mar 18 '16 at 20:24
• The tower of Hanoi group is the iterated monodromy group of a rational function with julia set the Sierpinski gasket, which explains this example. Mar 19 '16 at 13:05

Your construction of the Sierpinski triangle is more naturally viewed as a projection of a slice of a three-dimensional analogue. Firstly, recall that infinite binary sequences can be mapped to real numbers in the usual way:

$$\theta : {\mathbb{F}_2}^{\omega} \rightarrow [0, 1]$$

$$(b_1, b_2, b_3, \dots) \mapsto \sum b_i 2^{-i}$$

Then the set:

$$\{ (\theta(x), \theta(y), \theta(z)) : x, y, z \in {\mathbb{F}_2}^{\omega} \textrm{ s.t. } x + y + z = 0 \}$$

of images of triples whose coordinates sum to $0 \mod 2$ is a regular Sierpinski tetrahedron inscribed in the unit cube:

Moreover, if you impose the additional constraint:

$$\theta(x) + \theta(y) = \theta(z)$$

then you obtain one face of this tetrahedron, namely a regular Sierpinski triangle:

Finally, if you project that into the $xy$-plane, you get your original construction of a right-angled Sierpinski triangle as the set of coordinates whose binary expansions are disjoint:

$\dots$ so I claim there is nothing particularly unexpected about the pattern you observed.

• That is a nice explanation of what I didn't expect to see. Mar 19 '16 at 18:32

The classical Laver tables are pretty much versions of the Sierpinski triangle.

Recall that the $n$-th classical Laver table $A_{n}$ is the unique algebra $(\{1,...,2^{n}\},*)$ such that if $x,y,z\in A_{n}$ then

1. $x*1=x+1$ whenever $x<2^{n}$,

2. $2^{n}*1=1$, and

3. $x*(y*z)=(x*y)*(x*z)$.

The classical Laver tables were originally found by Richard Laver in his investigation of extremely large cardinals.

Below is the $6$-th classical Laver table where we put a blue square for each coordinate of the form $(i,i*j)$ (I mean $(i,i*j)$ in the matrix coordinate system) and every other square is left black. I should also mention that due to the periodicity of the classical Laver tables, all the information about the classical Laver tables is contained in its corresponding Sierpinski triangle.

A more full version of the Sierpinski triangle occurs in the final matrix from the generalized Laver tables which I have been researching. Click here for a program that generates the Sierpinski triangle pictures from the final matrix.

Of course, these images are unexpected since the Laver tables provide the only source of computer generated images of objects that arise in current set theory research.

The images were generated by Mathematica and GAP and the second image was originally generated with the help of Jonathan Burns.

• I so far have not been able to prove that the image that comes from the generalized Laver tables is always a subset of the Sierpinski triangle. Feb 10 '17 at 2:41

The Bruno Joyal's answer of When $n\choose k$ divisible by $n$? is an another example of appearance of the Sierpinski Triangle in Pascal triangle.

And this is a recent question about the black line down the center of this image.

The Sierpinski triangle also emerges from a random geometrical process known as the chaos game.

Consider the three vertices of any triangle, start from any one of them, and iterate the following actions: choose one vertex at random; draw a dot at the middle of the segment between your current position and this vertex; move to this dot.

This is what you typically obtain after 10, 100, 1000 and 10000 steps:

and an animation (starting with 1 dot and doubling the number of dots at each step):

You may also have a look at this video of the chaos game and check Wikipedia for more.

• Isn't this already covered in the answer from otakucode, from March 2016? Dec 29 '20 at 22:22
• Oups, sorry, I missed it because it starts with cellular automata, which are not related to the rest of the post, actually. Also, the process is describes is quite different, and does not mention the chaos game. The comment by joeytwiddle is closer, but lacks details, imho. Still, you are right, these processes are somehow variants of the same principle. Dec 29 '20 at 22:37

I've encountered the Sierpinski Triangle or other Sierpinski Gadgets many times when playing around with cellular automata, both 1D and 2D. The most surprising 'place' to me personally, however, has to be a random process which produces the pattern.

The process is simple: Choose 3 random points and plot them. (You can set them up being able to define a right triangle or not, it will only affect how skewed the resulting pattern is) Add the points to a list. Now repeat the following steps: Choose 2 points at random from the list. Find their midpoint. Plot it and add that point to your list.

Repeating those steps will produce a Sierpinski Triangle pattern. The patterns recurrence in so many places, as well as its fractal nature, may lie in the fact that (as can be seen from that process directly) every point in the figure is the midpoint between some other two points also on the figure. That is a very self-referential property, which makes the fractal nature make sense to me. And that it appears in other systems would lead me to suspect that those systems have self-reference built in as well.

I have also run into the pattern long ago when experimenting with visualizing bit manipulation and combining bitwise operations in arbitrary combinations. It comes up quite often there.

• There is a similar algorithm which I first saw used to plot the Sierpinski triangle in 10 lines of BASIC. Having chosen the three corners, and a random point (anywhere you like), repeat the following steps: Choose a corner at random, jump halfway towards it, and then plot a point. After a few iterations you are inside the triangle and will never escape. Mar 21 '16 at 14:01

Apparently it shows up in the recursive construction of polar codes, a type of state-of-the-art capacity achieving coding scheme. http://entropictalks.blogspot.se/2015/03/are-polar-codes-fractal.html

Sierpinski triangles arise as matrices whose characteristic polynomials expectedly and unexpectedly factor nicely as products of linear and quadratic polynomials. For this answer, I have observed these phenomena experimentally, but I do not have a formal proof that these phenomena always hold.

Let $$A=\begin{bmatrix} 0 & a \\ b & c \end{bmatrix}$$.

For $$n\geq 1$$ and for each matrix $$B$$, define the tensor power $$B^{\otimes n}$$ by letting $$B^{\otimes 1}=B$$ and by letting $$B^{\otimes(n+1)}=B^{\otimes n}\otimes B=B\otimes B^{\otimes n}$$. The matrix $$A^{\otimes n}$$ is a depiction of the Sierpinski triangle.

Now, if $$A$$ has eigenvalues $$\lambda,\mu$$, then since the eigenvalues of $$A^{\otimes n}$$ are precisely the elements of the form $$\lambda^{n-i}\mu^{i}$$ for $$0\leq i\leq n$$, it should not surprise any mathematician that the characteristic polynomial $$A^{\otimes n}$$ can be factored completely into linear or quadratic polynomials with coefficients in $$\mathbb{Z}[a,b,c]$$.

Let $$P_{n,k}=(a_{i,j})_{1\leq i\leq n,1\leq j\leq n}$$ be the matrix where $$a_{i,j}=1$$ if $$i-j=k\mod n$$ and $$a_{i,j}=0$$ otherwise. Then I have experimentally verified that characteristic polynomial of the matrix $$A^{\otimes n}\cdot P_{2^{n},k}$$ can also be factored as a product of linear or quadratic polynomials with coefficients in $$\mathbb{Z}[a,b,c]$$ (This is the shifted Sierpinski triangle). Furthermore, if $$N$$ is a $$2^{n}\times 2^{n}$$-matrix where almost all of the entries are zero, then the polynomial $$\text{char}(A^{\otimes n}\cdot P_{2^{n},k}+N)$$ still has a quite decent prime factorization.

For example, if $$n=8,k=7,a=b=c=1$$, then $$A^{\otimes n}\cdot P_{2^{n},k}$$ has characteristic polynomial $$(x-1)^{20}(x+1)^{28}(x^2-18x+1)(x^2-11x-1)^{3}(x^2-7x+1)^{3}(x^2-4x-1)^{3}(x^2-3x+1)^{19}(x^2-x-1)^{33}(x^2+x-1)^{9} (x^2+3x+1)^{12}(x^2+4x-1)^{15}(x^2+7x+1)^{6}.$$

If we replace $$A$$ with an arbitrary $$2\times 2$$ square matrix or even a lower or upper triangular matrix, then the characteristic polynomial of $$A^{\otimes n}\cdot P_{2^{n},k}$$ usually does not have a good factorization.

If $$A_{1},\dots,A_{n}$$ are $$2\times 2$$-matrices where if $$A_{r}=(a_{i,j,r})_{i,j}$$, then $$a_{1,1,r}=0$$, then the characteristic polynomial of $$(A_{1}\otimes A_{2}\otimes\dots\otimes A_{n})\cdot P_{2^{n},k}$$ is usually reducible, but this characteristic polynomial often cannot be factored as a product of linear or quadratic polynomials, but if the underlying field is finite, then this characteristic polynomial factors as a product of linear or quadratic polynomials.