Triangularized: Sierpinski’s Gasket and Pascal’s Triangle

Michael Emmerich, September 28th. 2024

Introduction

The Sierpinski Gasket is a fractal pattern named after the Polish mathematician Wacław Sierpiński (1882–1969). Sierpiński was a prominent figure in set theory, number theory, and topology, and he introduced several well-known fractals, including the Sierpinski Gasket (also known as the Sierpinski Triangle) in 1915. This pattern exhibits self-similarity, meaning that it looks the same at different scales, a hallmark property of fractals.

The Sierpinski Gasket can be generated through various methods, one of which is the use of a cellular automaton, a simple computational model where cells evolve based on predefined rules. In this essay, we will explain how the Sierpinski Gasket can emerge from a binary cellular automaton using the exclusive OR (XOR) operation. Additionally, we will discuss the connection between the Sierpinski Gasket and the odd numbers in Pascal’s Triangle.

Cellular Automaton Rule

The cellular automaton used to generate the Sierpinski Gasket operates on a two-dimensional grid of cells, where each cell can be in one of two states: ${0}$ or ${1}$ . The automaton starts with an initial condition of a single active cell (value ${1}$ ) in the middle of the top row.

Update Rule

The state of each cell in subsequent rows is determined by the XOR operation applied to the two cells diagonally above it. This rule can be written as:

$\displaystyle \text{Cell}(x, y) = \text{Cell}(x-1, y-1) \oplus \text{Cell}(x+1, y-1)$

where ${ \oplus }$ denotes the XOR operation. The XOR operator is defined as follows:

$\displaystyle A \oplus B = \begin{cases} 1, & \text{if } A \neq B \\ 0, & \text{if } A = B \end{cases}$

This simple rule gives rise to the triangular, fractal structure known as the Sierpinski Gasket. By iterating the process row by row, the structure grows, and the self-similar fractal pattern becomes visible.

Connection to Pascal’s Triangle

The Sierpinski Gasket can also be constructed by examining the odd numbers in Pascal’s Triangle. Pascal’s Triangle is constructed by summing pairs of numbers from the row above. However, when we take each entry modulo 2, a fascinating connection to the Sierpinski Gasket emerges.

Odd Numbers in Pascal’s Triangle

In Pascal’s Triangle, each entry at position ${ (n, k) }$ is the binomial coefficient ${ \binom{n}{k} }$ , which counts the number of ways to choose k elements from a set of n elements. When we reduce the entries modulo 2, we are only interested in whether the number is odd or even:

$\displaystyle \text{Pascal}(n, k) \mod 2 = \begin{cases} 1, & \text{if } \binom{n}{k} \text{ is odd} \\ 0, & \text{if } \binom{n}{k} \text{ is even} \end{cases}$

The odd numbers in Pascal’s Triangle form a pattern identical to the Sierpinski Gasket. This is because the XOR operation in the cellular automaton mirrors the same process of adding and reducing modulo 2. Each cell in the automaton corresponds to whether a number in Pascal’s Triangle is odd (1) or even (0).

XOR and Pascal’s Triangle

To understand why this connection exists, consider how entries in Pascal’s Triangle are computed:

$\displaystyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

When taking these values modulo 2, this addition behaves like an XOR operation:

$\displaystyle \text{Pascal}(n, k) \mod 2 = \left(\text{Pascal}(n-1, k-1) \mod 2\right) \oplus \left(\text{Pascal}(n-1, k) \mod 2\right)$

Thus, the rule for generating the Sierpinski Gasket using XOR in the cellular automaton is equivalent to determining whether each entry in Pascal’s Triangle is odd or even. This is why the cellular automaton and Pascal’s Triangle modulo 2 both produce the same fractal pattern.

Sierpinski and His Contributions

Wacław Sierpinski was one of the leading mathematicians of his time and made significant contributions to various fields in mathematics, including the study of fractals, set theory, and number theory. His work on fractals, including the Sierpinski Gasket and the Sierpinski Carpet, has inspired extensive research in modern mathematics and computer science, particularly in the areas of recursion, self-similarity, and chaos theory.

Summary

The Sierpinski Gasket is a beautiful example of how simple mathematical rules can give rise to complex, self-similar patterns. By understanding the underlying mechanisms—such as the XOR operation and modulo 2 arithmetic in the Pascal triangle —we can appreciate the deep connections between different areas of mathematics.

We’ve visualized the Sierpinski Gasket using a simple interactive app (Link at the end of the essay), where the canvas is sized at 513 pixels. Interestingly, the black interior triangle closes at pixel 512—a power of 2—revealing the fractal’s connection to binary structures. But this is just the beginning. There’s so much more mathematical beauty and regularity hidden within the Sierpinski Gasket. Below we added an example bz K. Decker (2016) where even a relationship between the unknown distribution laws of the prime numbers and the Sierpinski triangle is made. Ultimatively, however, it turns out that this connection can be best understood by an XOR pattern that emerges in a sufficiently fast decreasing sequence (columns), and hence might not directly shed much light on the distribution of the primes.

We invite you to explore its fascinating properties by diving into the interactive Python code provided. Experiment with different grid sizes, patterns, and rules, and uncover deeper insights into the symmetry, scaling, and recursive structure that define this timeless fractal.

https://trinket.io/pygame/f570ff844ccb

KDecker (https://math.stackexchange.com/users/70463/kdecker), Has anyone found a “pattern” in prime numbers?, URL (version: 2016-09-06): https://math.stackexchange.com/q/371434 link

W. Sierpiński, “Sur une courbe dont tout point est un point de ramification,” C.R. Acad. Sci. Paris, 160 (1915), 302–305.

Triangularized: Sierpinski’s Gasket and Pascal’s Triangle

Share this:

Leave a comment Cancel reply