A Glimpse into Infinity!
In my class, “Nature Inspired Design in Computing,” we recently delved into the intriguing world of fractals. I put together this blog post to share some insights from exploring fractals. We’ll start by unraveling the foundational definitions and intuitions, then progress to the mathematics of fractals, highlighting how our standard understanding of spatial dimensions might not quite grasp their unique nature. By the end, we’ll introduce the formal concept of the box counting dimension—often referred to as the Minkowski-Bouligand dimension—illustrating that fractals interestingly possess fractional dimensions!
What really are fractals? Fractals are intricate patterns that repeat themselves, no matter how much you zoom in. The etymology of the term “fractal” (from Latin fractus) is due to this self similar nature, meaning that if you zoom in on a portion of the fractal, you will see a shape that looks similar to the larger scale. This property gives the appearance of being “broken” into smaller parts that look like the whole. Unlike simple shapes like circles or squares, fractals sit somewhere in-between dimensions, making them both fascinating and a bit mysterious. You can spot these patterns everywhere – from the way trees branch out to the designs on seashells.
Fractals, while seemingly a modern concept, have roots that stretch back far earlier than one might think.
Ancient Beginnings: While the formal study of fractals is relatively recent, many ancient cultures incorporated fractal-like patterns into their art and architecture. The recursive patterns in African art, the infinite loops in Celtic knots, and the intricate designs in Indian mandalas all hint at an innate human appreciation for self-similar patterns.
The 19th Century and Early Pioneers: Mathematicians like Karl Weierstrass, Georg Cantor, and Helge von Koch began exploring functions and sets which didn’t have the properties of classical Euclidean geometry. Koch’s famous ‘snowflake curve’, for instance, was a continuous curve with no tangents – a radical idea for its time.
Benoit B. Mandelbrot – The Father of Fractals: The 20th century saw the birth of fractals as a formal field of study, largely thanks to Benoit B. Mandelbrot. In 1975, he coined the term ‘fractal’ to describe shapes that appear similar at any level of magnification. His work was inspired by earlier mathematicians but also by his study of real-world phenomena, like the irregularity of coastlines. Mandelbrot’s book, “The Fractal Geometry of Nature,” published in 1982, revolutionized how we understand many natural phenomena and patterns.
Fractals in the Digital Age: With the advent of computers, visualizing and generating fractals became much easier. They soon permeated various fields, from computer graphics in movies to the design of antennas and even in financial models. Computers allowed for deep dives into fractal sets, like the famous Mandelbrot set, revealing their endless intricacies.
Today, fractals continue to inspire scientists, artists, and thinkers alike. They bridge the gap between abstract mathematics and the tangible patterns we see in the world around us, standing as a testament to the beauty and complexity inherent in nature and mathematics.
Till now, we took fractals as some shape that is somehow differnt from regular shapes like circles, squares, etc. So, if we are provided a shape, how do we see if it is fractal or not? Can we formalize what a fractal really is? It seems not.
Attempts to Formally Define Fractals and Their Shortcomings
I shamelessly take the below section from the Wikipedia to drive home the characteristics of a fractal,
One point agreed on is that fractal patterns are characterized by fractal dimensions, but whereas these numbers quantify complexity (i.e., changing detail with changing scale), they neither uniquely describe nor specify details of how to construct particular fractal patterns. In 1975 when Mandelbrot coined the word “fractal”, he did so to denote an object whose Hausdorff–Besicovitch dimension is greater than its topological dimension. However, this requirement is not met by space-filling curves such as the Hilbert curve.
Because of the trouble involved in finding one definition for fractals, some argue that fractals should not be strictly defined at all. According to Falconer, fractals should be only generally characterized by a gestalt of the following features;
- Self-similarity, which may include:
- Exact self-similarity: identical at all scales, such as the Koch snowflake
- Quasi self-similarity: approximates the same pattern at different scales; may contain small copies of the entire fractal in distorted and degenerate forms; e.g., the Mandelbrot set’s satellites are approximations of the entire set, but not exact copies.
- Statistical self-similarity: repeats a pattern stochastically so numerical or statistical measures are preserved across scales; e.g., randomly generated fractals like the well-known example of the coastline of Britain for which one would not expect to find a segment scaled and repeated as neatly as the repeated unit that defines fractals like the Koch snowflake.
- Qualitative self-similarity: as in a time series.
Multifractal scaling: characterized by more than one fractal dimension or scaling rule Fine or detailed structure at arbitrarily small scales. A consequence of this structure is fractals may have emergent properties (related to the next criterion in this list).
- Irregularity locally and globally that cannot easily be described in the language of traditional Euclidean geometry other than as the limit of a recursively defined sequence of stages. For images of fractal patterns, this has been expressed by phrases such as “smoothly piling up surfaces” and “swirls upon swirls”;see Common techniques for generating fractals. As a group, these criteria form guidelines for excluding certain cases, such as those that may be self-similar without having other typically fractal features. A straight line, for instance, is self-similar but not fractal because it lacks detail, and is easily described in Euclidean language without a need for recursion.
Even for mathematicians, who are very particular about formally defining concepts, fractals pose a significant challenge. I dont personally have any preferences for a particular definition of a fractal. We don’t have to do that for the purposes of this post.
As we’ve seen, the journey of fractals has been a rich tapestry of evolving definitions, each trying to encapsulate their mesmerizing complexity. Historically, scientists grappled with the challenge of defining these enigmatic figures, from their self-similarity to their resistance to traditional geometric classification. But why did these definitions matter? Why was it so crucial to understand what exactly a fractal is? The answer lies in the very nature of fractals themselves. By understanding their foundational properties, we can better appreciate their quirks, challenges, and the mysteries they present. And what better way to delve into this understanding than by exploring a practical example?
We will consider the Sierpinski triangle to tease out the properties of fractals. By the end of this section, we should be sufficiently convinced that conventional integer dimensional spaces are inadequate to understand them.
What we’re left with is a pattern that, no matter how closely you look at it, keeps revealing smaller triangles. self similarity! The Sierpinski triangle may look complicated, but its construction is based on a straightforward and repetitive process. It’s a perfect example of how simple rules can lead to complex and beautiful patterns.
The code for generating this triangle in javascript is in the source code of this webpage. Right-click -> view source -> Search for a function called tripinski.
To understand why introducing a fractional dimension was even necessary for fractals, lets see how much our conventional notions of integer-dimensional spaces work with the Sierpinski triangle. What we mean by “conventional” is that our notion that lines are 1D objects, areas like triangle and rectangle are 2D objects, volumes like sphere and cube are 3D objects and so on. We will use this temporary notion of dimension for now, and formalize it later.
Computing the perimeter of an infinite object like the Sierpinski triangle is challenging. We can approach this problem is by first figuring our how the perimeter changes when you repeat the process of generating a fractal. Once that is done, we can reason about how the perimeter behaves when approaching infinity.
We begin with a full equilateral triangle with area shaded in black. Assume each side has a length of $d$. The perimeter of this triangle is $3d$. Now, we can start our Sierpinski procedure. Let’s create a new variable $P_0 = 3d$ to hold the perimeter at each iteration.
Iteration 1
Connect the midpoints of the big triangle and remove the resulting middle triangle. The figure we get looks like this
Now the perimeter gets added because it has to account for the hole in the middle,
\[P_1 = 3d + 3 \frac{d}{2}\]The additional term adds the sides of the new triangle in the middle. This is good, it seems we are starting to find some pattern which is the side length always reduces to half.
Iteration 2
Connect the midpoints of all the possible sides and remove triangles again. The figure we get looks like this
The perimeter now has to account for the new holes we created.
\[P_2 = 3d + (3 \frac{d}{2^1}) + 3 (3 \frac{d}{2^2})\]Now, we are starting to see some pattern. It seems at each iteration, the number of triangles grow 3 times and the sidelength of the triangles halves. Let us do one of iteration and see if the pattern holds.
Iteration 3
Connect the midpoints of all the possible sides and remove triangles again. The figure we get looks like this
The perimeter is
\[P_4 = 3d + (3 \frac{d}{2^1}) + 3 (3 \frac{d}{2^2}) + 3^2 (3 \frac{d}{2^3})\] \[P_4 = 3d + 3^1 \frac{d}{2^1} + 3^2 \frac{d}{2^2} + 3^3 \frac{d}{2^3}\]Iteration n
Now, it is fairly easy to see the pattern. At each iteration, a new term gets added to the area, which is some power of $\frac{3}{2}$ times the sidelength. We can generalize this, and write a form for the perimeter at the $n^{\text{th}}$ iteration.
\[P_n = 3d + \sum_{i=1}^n \left( \frac{3}{2} \right)^i d \,\,, n>0\]The second term is a geometric series can be summed over (Check the linked Wikipedia page if a refresher is needed). We can now apply for the formula for the geometric series sum to reduce our perimeter.
\[P_n = 2d - d \left(\frac{1-\left(\frac{3}{2}\right)^{n+1}}{\frac{1}{2}}\right)\]What happens to the perimeter when we approach infinity?
\[\lim_{n \to \infty} P_n = P_{\infty} = \infty\]So perimeter reaches infinity. It makes sense because we are keeping on adding new triangles and hence new lines contributing to the perimeter.
In case, why $P_{\infty}$ is $\infty$ is not clear, we can take a step back. We had $2d-$something and the something is a very high negative number since we have $1-(\frac{3}{2})^{n+1}$ in the numerator and $\frac{3}{2} > 1$ which means it is going to infinity as we power the term.
Now, lets see what happens to the area. First, lets recap that the area of an equilateral triangle and the entire black triangle is $\frac{\sqrt{3}}{4} d^2$ where $d$ is the side-length. We will call this $A_0$ so that we dont have to keep track of the annoying $\frac{3}{4}$ terms.
Iteration 1
In iteration 1, we are dividing the big triangle into $3$ small identical triangles. Therefore, the area has to be $A_0/4$ for each of the triangles. Then, we remove one of the triangles. The resultant area is
\[A_1 = A_0 - \frac{A_0}{4}\]Iteration 2
In iteration 2, we repeat the same process of division for the 3 triangles obtained from the first iteration. Each small triangle will have the area $(A_0/4) \times 1/4 = A_0/4^2$. and we are removing $3$ of these small areas in this iteration.
\[A_2 = A_0 - \frac{A_0}{4} - 3 \frac{A_0}{4^2}\]Iteration 3
In iteration 3, we repeat the same process of division for the 9 triangles obtained from the second iteration. Each small triangle will have the area $(A_0/4^2) \times 1/4 = A_0/4^3$, and we are removing $3^2$ of these small areas in this iteration.
\[A_2 = A_0 - \frac{A_0}{4} - 3 \frac{A_0}{4^2} - 3^2 \frac{A_0}{4^3}\]Iteration n
Now, we are in a good place to generalize to $n$ iterations. At each step of the iteration, I am adding a term that is $(3/4)$ times the previous factor. I am doing a bit of algebra (multiply and divide each term by 3) to write the summation in a neat form.
\[A_n = A_0 - \sum_{i=1}^n \left( \frac{3}{4} \right)^i \frac{A_0}{3} \,\,\,, n>0\]This is also a geometric series like before. Lets use the summation formula and reduce the summation in the term.
\[A_n = \frac{4}{3} A_0 - \left( \frac{1 - \left(\frac{3}{4}\right)^{n+1}}{\frac{1}{4}} \frac{A_0}{3}\right)\]Now, we can figure out what happens when $n$ approaches infinity by applying limits.
\[\lim_{n \to \infty} A_n = A_\infty = \frac{4}{3} A_0 - \frac{4}{3} A_0 = 0\]The trick to get this is to see that $(\frac{3}{4})^n$ becomes smaller as the $n$ increases (as $\frac{3}{4} < 1$) with it converging to $0$ when approaching infinity.
Now that we have the perimeter and area computed, we can compare the two. Recap:
\[P_\infty = \infty \text{ and } A_\infty = 0\]Let’s imagine now iterating through the triangle generation procedure. We take smaller and smaller triangles away from the larger triangle. So, in a way, the “edge” or perimeter of our triangle keeps growing. Now, if we were to paint the inside of this triangle at each iteration, you’d find that there’s less and less space to paint each time. That’s because the area inside the triangle keeps getting smaller.
It’s enough to make you scratch your head: a shape with an edge that keeps growing but an inside that’s disappearing!
This weirdness is why mathematicians started to think that maybe the usual way we talk about dimensions doesn’t quite work for something like the Sierpinski triangle. I mean, how can we have something that’s bigger on the outside but smaller on the inside?
So, this trippy triangle tells us we might need some new math tools to understand these kinds of shapes better.
Okay, at this point, we know that we need a new notion of dimension, but what exactly is dimension? We will take a look at this question in two ways. First, we will build some intuition about what is actually meant when we say the dimensions of an object. Next, we will introduce the box-counting dimension formally. Feel free to skip the first section, if it seems too basic :)
When do we say an object is 1D, 2D, or 3D? Let’s first take a step back and begin with a simple notion of dimension.
DEFINITION (TEMPORARY #1): Dimension of an object is defined as the minimum number of dimensions in the coordinate space required to describe all the points in the object
We know a line is 1D. So, according to our notion of dimension, it must mean that we can represent the line in a 1D space. Now, let’s take a circle of radius 1 without any area, and only the circumference. According to our definition, we need a 2D plane to draw it. But, here is the problem - although we use a 2D plane to represent the circle, you dont really need 2 numbers to describe all of it’s points. That is, you can take any $x$ and solve the equation $y = \sqrt{1-x^2}$ to get y. So, somehow your $x$ uniquely specified all your points in the circle, which must mean that the circle we have is actually a 1D object even through we draw it in 2D coordinate space. Another way to look at this is that you can construct a coordinate system which is not a plane like in the typical coordinate system but is curved along the circumference of the circle such that the circle becomes a 1D object. The point I want to make is the difference between the space in which an object is embedded and the intrinsic dimensionality of the object itself. From the curved vs planar spaces we used for the circle argument, it is clear that we need a new definition for dimensions, one which is independent of the space used to represent the object. Let’s consider the following definition:
DEFINITION (TEMPORARY #2): Dimension of an object is defined as the minimum number of independent parameters required to specify all the points of the object.
This seems to be a nice enough definition for a dimension. We can see now that the minimum number of independent parameters we required for the circle case is actually $1$ (the $x$ value) and the $y = \sqrt{1-x^2}$ is actually dependent on $x$. Another easier way to express the points in the circle is using the angle it makes with one of the coordinate axis ($\theta$). For a hollow circle, all the points are described by this angle and a fixed radius $r$. We can now consider what happens when the circle object of radius 1 encloses an area within its circumference. Now, we need two independent parameters $r$ and $\theta$. The radius parameter $r$ can vary from $0$ to $1$ and the $\theta$ parameter can vary from $0$ to $2 \pi$. Seems like we are on the right track. Now what if I give an arbitrary shape like our Sierpinski fractal? How do we find this minimum number of parameters required to describe it?
Let’s see how a simple use of a scale and measuring with it, can get us this number. Suppose we have a scale - a 3D cube with $1 \mu$ side-length using which we can count how many of the scale make up our object which we call measure. We now use this scale and count how many points (in the units of $\mu$) are there in the hollow circle. For a circle of $1 \mu$ radius, the circumference we get will be $c = 2 \pi \mu$. Now, the choice of $\mu$ we made here is arbitrary, we can argue that we don’t like a $\mu$ unit scale anymore, and we want to start using a $\frac{\mu}{2}$ unit scale. How does the circumference we measured change with the new unit? The new circumference is $2 c$ - it doubled!
How about a circle which has points within it? In this case, we need to measure the area of the circle to cover all the points. Similar to the above, for $1 \mu$ scale, we get an area of $a = \pi \mu^2$. Now if the scale is $\frac{\mu}{2}$, the area is $4a$. Compared to the hollow circle, our measure of the object has doubled for a filled circle.
Let’s take one more step and see if we can establish some trends in the behavior of these measurements we are making. Consider a filled sphere, we need to measure the volume to cover all the points. The volume for the case of a scale of $\mu$ units is $v = \frac{4}{3} \pi \mu^3$ and for the $\frac{\mu}{2}$ scale, the volume becomes $2^3 v$. To summarize, this is how the measures changed when the scale is changed from $\mu$ to $\frac{\mu}{2}$
\[1D \text{(circumference)}: 2^{\textcolor{red}{1}} c \text{ and } 2D \text{(area)}: 2^{\textcolor{red}{2}} a \text{ and } 3D \text{(volume)}: 2^{\textcolor{red}{3}} v\]This seems very interesting - somehow the dimensionality of the object is encoded in the exponent of the amount by which the scale is changed (that is as the power of $2$). We can obtain this from the measurement just by applying $\log_2$. Whew! that was a long detour, but we are now in a good position to formalize and find the box counting dimension.
DEFINITION (Box-Counting Dimension): Suppose we have a set $S$ defined with a way to measure using some notion of a cube of side $\epsilon>0$ in the set. Let $N_\epsilon$ be the number of $n$-dimensional cubes of side-length $\epsilon$ needed to cover $S$. If there is a number $d$ such that
\[d = - \lim_{\epsilon \to 0} \frac{\ln N_\epsilon (S)}{\ln \epsilon}\]The number $d$ is the box counting dimension of the set $S$
Intuitively, the box-counting dimension gives us a way to quantify how much “space” an object takes up when we look at it at different scales. The scales here are formalized by taking different sizes ($\epsilon$) for our counting boxes. The dimension is the exponent we found in the previous section (What is dimension?) that was encoding the dimension of the object.
Now that we have a very nice definition for dimension, lets apply it to our Sierpinski triangle and see what its dimensions are - hopefully that will shed some light into the counter-intuitiveness of the area, and perimeter calculation. Since Sierpinski triangle is an infinite figure, it is not trivial to just place boxes like in the circle example. Instead, we are going to use the same procedure for computing the area and perimeter - that is figure out the number of boxes at each step in the iteration and figure out what happens when the iteration nears infinity.
Iteration 1
We have $3$ boxes here each with sidelength $\frac{d}{2}$. So $N_{\frac{d}{2}} = 3$
Iteration 2
We have $9$ boxes here each with sidelengh $\frac{d}{2^2}$. So $N_{\frac{d}{2^2}} = 3^2$
Iteration 3
We have $27$ boxes here each with sidelength $\frac{d}{2^3}$. So $N_{\frac{d}{2^3}} = 3^3$
Iteration i
We have some patttern here and let’s generalize the pattern to arbitrary iteration $n$. We get $N_{\frac{d}{2^i}} = 3^{i}$
Computing Box-Counting dimension
We can now use the formulae we have for the box counting dimension.
\[d = - \lim_{\epsilon \to 0} \frac{\ln N_\epsilon (S)}{\ln \epsilon}\]The trick is to use this formulae is to change $\epsilon$ to the iteration $i$. Since $i \to \infty$, the sidelength $\epsilon \to 0$, we can now write the dimension as
\[d = - \lim_{i \to \infty} \frac{\ln \left( N_{\frac{d}{2^i}} \right) }{\ln \left( \frac{d}{2^i} \right) }\]Substituting our $N$ we get,
\[d = - \lim_{i \to \infty} \frac{\ln \left( 3^i \right) }{\ln \left( \frac{d}{2^i} \right) }\] \[d = - \lim_{i \to \infty} \frac{i \ln \left( 3 \right) }{\ln \left( d \right) - i \ln \left( 2 \right) }\]We cannot set $i$ to infinity directly here. So, we divide the numerator and denominator by $i$.
\[d = - \lim_{i \to \infty} \frac{\ln \left( 3 \right) }{\frac{\ln \left( d \right)}{i} - \ln \left( 2 \right) }\]Earlier, when we examined the Sierpinski triangle, two aspects stood out: its ever-expanding perimeter and its diminishing area with each iteration. At first glance, this appears paradoxical. How can a shape continue to grow outward indefinitely while the space it occupies shrinks? This is where the fractional dimension, as revealed by the box counting method, provides clarity.
The Sierpinski triangle’s fractional dimension bridges the gap between the unusual behavior of its perimeter and area. When you consider its boundary, it seems to be constantly stretching out, giving the illusion of infinity. Yet, simultaneously, the shape is riddled with holes, which accounts for the decreasing area. This ‘in-between’ nature of the Sierpinski triangle’s dimension reflects precisely this interplay. It’s as if the triangle is trying to exist in a space between a line and a plane. The perimeter’s endless growth hints towards a dimension greater than 1, while the vanishing area alludes to it being less than a solid 2D figure.
Thus, the fractional box counting dimension not only captures the inherent intricacy of the Sierpinski triangle but also elegantly reconciles the peculiarities observed in its area and perimeter. This provides a comprehensive picture of the triangle’s nature, emphasizing the unique space it occupies in the geometric universe.
We took a dive into the world of fractals and revealed patterns that challenge traditional geometry. By journeying from basic definitions to complex computations, we unveiled the mystery of the fractional dimension using the Sierpinski triangle as our guide.
A simple iterative process can create the Sierpinski triangle. Starting with an equilateral triangle and repeatedly removing smaller triangles, we’re left with a pattern that both mesmerizes and puzzles. As the iterations progress, the Sierpinski triangle displays a curious phenomenon: its perimeter seems to grow endlessly, while its area shrinks. This counterintuitive behavior requires a deeper exploration.
To understand the Sierpinski triangle’s enigmatic behavior, we introduced the ‘box counting’ method. This approach revealed that the Sierpinski triangle’s dimension isn’t whole but fractional, providing a fresh lens to understand the triangle’s intricate balance between emptiness and substance.
The Sierpinski triangle, with its fractional dimension, stands as a testament to the beauty and complexity of fractals. Its unique behavior, bridging the gap between traditional dimensions, offers insights into the rich tapestry of geometry and emphasizes the vastness of the mathematical universe.