Mathematics

FRACTALS AND DIMENSION

TALI KHAIN

Abstract. In this paper, we discuss several key characteristics of fractals,

namely a self-similar structure and a fractional dimension. Interspersed with

the theory, this paper provides plenty of curious examples, including classic examples like the Koch snowflake and the Cantor set.

Contents

1. Introduction 1 2. Measures 1 3. Dimension 4 4. Self-Similarity 5 5. Conclusion 9 Acknowledgments 10 References 10

1. Introduction

As humans, we are accustomed to our three-dimensional world, where a point has a dimension of zero, a line has a dimension of one, a square has a dimension of two, and a cube has a dimension of three. Our understanding of dimension is discrete; we sort all of the objects surrounding us into one of the above categories.

It turns out that we can’t classify quite all objects into an integer-dimension category; those objects which behave in strange ways with regards to dimension are called fractals. Although there is no strict definition for a fractal, most theoretical fractals share similar features. All have an intricate, often iterative, structure: their local geometry is just as detailed as the whole. In addition, this structure is usually self-similar, that is, after enlarging an area of a fractal, we are likely to find a copy of the original.

Fractals are found not only in strictly theoretical contexts, but in nature as well. If we don’t insist on perfect self-similarity, objects such as leaves, coastlines, crystals, and snowflakes all fall into the fractal category.

2. Measures

Before we delve into rigorous mathematics, let’s try to come up with an intuitive definition of dimension. Suppose we have a ball of radius r, Br ⊂ Rd, where d is a positive integer. Let v denote the d-dimensional volume of Br. We will show that the dimension d of Br is related to the volume v and radius r of Br in a rather non-trivial way. Notice that if d = 1, then Br is simply a line segment, so v ∝ r

1

2 TALI KHAIN

(in this case, v is the length of Br). If d = 2, then Br is a circle, so v ∝ r2 (in this case, v is the area of Br). If d = 3, then Br is a sphere, so v ∝ r3. Therefore, we expect that v ∝ rd, or d ∝ log(v)/log(r). Now, notice that our intuitive definition of dimension relies on two concepts, radius (distance) and volume. To rigorously define these notions, we will first need to introduce the concept of measure.

Definition 2.1. Let S ⊂ Rn. A measure µ on S is a function µ : S → R≥0∪{∞} which satisfies the following conditions:

(a) µ(∅) = 0 (b) µ(A) ≤ µ(B) if A ⊂ B (c) µ(

⋃∞ i=1 Ai) ≤

∑∞ i=1 µ(Ai), where {Ai ∈ Rn : i ∈ I} is a countable collection of

sets.

Intuitively, a measure determines the size of a set. Let’s examine a simple exam- ple of a measure, the point mass. Fix some specific element a. If a set M contains a, then µ(M) = 1; if the set M does not contain a, then µ(M) = 0. Let’s check that the point mass is indeed a measure:

(i) µ(∅) = 0, since ∅ contains no points, and in particular, does not contain a. (ii) Suppose A ⊂ B. If a ∈ A, then clearly a ∈ B, so µ(A) = µ(B) = 1. If a /∈ A,

then µ(A) = 0. Since µ(B) = 0 or µ(B) = 1, we have µ(A) ≤ µ(B). (iii) Let Ai be a countable collection of sets, where {Ai ∈ Rn : i ∈ I}. If a ∈⋃∞

i=1 Ai, then µ( ⋃∞ i=1 Ai) = 1. Since a ∈

⋃∞ i=1 Ai, we must have a ∈ Ai for at

least one i ∈ I. Hence ∑∞ i=1 µ(Ai) ≥ 1, so µ(

⋃∞ i=1 Ai) ≤

∑∞ i=1 µ(Ai). Now, if

a /∈ ⋃∞ i=1 Ai, then µ(

⋃∞ i=1 Ai) = 0. In addition, this means that a /∈ Ai for all

i ∈ I. Hence ∑∞ i=1 µ(Ai) = 0, and thus µ(

⋃∞ i=1 Ai) ≤

∑∞ i=1 µ(Ai).

Now, to compute the dimension of fractals, we will have to use the concept of Hausdorff measure. Before we explore this notion, we need to have an understand- ing of distance, as well as how we define covers of sets and the size of these covers.

There are many different ways in which we can define distance; in this paper, we will be using the standard Euclidean distance.

Definition 2.2. Let x,y ∈ Rn, where x = (x1,x2, . . . ,xn), and y = (y1,y2, . . . ,yn). Then the Euclidean distance between x and y is defined as

d(x,y) = √

(x1 −y1)2 + (x2 −y2)2 + · · · + (xn −yn)2.

Definition 2.3. Let S ⊂ Rn. The diameter of S is defined to be the largest distance between any two points of S, |S| = sup{d(x,y) : x,y ∈ S}.

Definition 2.4. Let S ⊂ Rn. A δ-cover of S is defined as {Ui ∈ Rn : i ∈ I}, a finite or countable collection of sets, where S ⊂

⋃∞ i=1 Ui and 0 ≤ |Ui| ≤ δ.

Now, let’s begin to define the concept of Hausdorff measure, developed by Felix Hausdorff, a great German mathematician. First, let’s understand the quantity Hsδ (S). Suppose S ⊂ R

n, and s ≥ 0. Given a fixed δ > 0, we define

Hsδ (S) = inf

{ ∞∑ i=1

|Ui|s : {Ui} is a δ-cover of S

} .

FRACTALS AND DIMENSION 3

What exactly do we mean by this? Given a δ > 0, we consider all of the δ-covers of S. Note that these covers may have diameter equal to or less than δ. For a visual of this expression, consider Figure 1. In this diagram, s = 2. The area enclosed by the black outline is our set S. Now, consider the sets Ui and Uj, two components of a δ-cover of S. For each cover, we are summing the square of the diameter of each component of the cover, and then taking the infimum over all covers; this gives us H2δ (S).

Figure 1. Computing the 2-dimensional Hausdorff measure of a set. The area enclosed by the black outline is the set S. The blue sets Ui and Uj are two components of a δ-cover of S, see details in text.

Now, let’s consider what happens to Hsδ (S) as δ → 0. As δ decreases, there are less and less δ-covers of S; hence, as δ → 0, the infimum could increase or not change, but it cannot decrease. That is, as δ → 0, we have a monotonically increasing sequence. Since this sequence is not bounded, we have that limδ→0 H

s δ (S)

exists, but could be infinite.

Definition 2.5. Let S ⊂ Rn. The s-dimensional Hausdorff measure of S is Hs(S) = limδ→0 H

s δ (S).

Let’s briefly convince ourselves that the s-dimensional Hausdorff measure is in- deed a measure:

(i) We need to show that Hs(∅) = 0. Well, the empty set admits all possible δ-covers. In particular, it admits the cover {0}, i.e., ∅ ⊂{0}. For this cover, Hsδ (∅) =

∑∞ i=1 |Ui|

s = ∑ |{0}|s = 0. Clearly, this is the infimum over all

δ-covers, and thus, Hs(∅) = 0. (ii) Suppose A ⊂ B. We need to show that Hs(A) ≤ Hs(B). Well, note that if

some Ui is a cover of B, then Ui must be a cover of A. There are, however, covers of A that are not covers of B. Therefore, for all δ > 0, Hsδ (A) ≤ H

s δ (B),

since the extra covers of A could give a smaller value for ∑∞ i=1 |Ui|

s. Hence Hs(A) ≤ Hs(B).

4 TALI KHAIN

(iii) The proof of this part was adapted from [3]. Suppose {Ai ∈ Rn : i ∈ I} is a countable collection of sets. We need to show that Hs(

⋃∞ i=1 Ai) ≤∑∞

i=1 H s(Ai). Assume that the s-dimensional Hausdorff dimension of each

set is finite, that is Hs(Ai) < ∞ for all i ∈ I. Now, given � > 0, for all i ∈ I, there exists a δ-cover {U(i)j } (that depends on i) of Ai such that∑

j

|U(i)j | s < Hsδ (Ai) +

�

2k .

Now, summing over all i ∈ I, we have∑ i

∑ j

|U(i)j | s <

∞∑ i=1

Hsδ (Ai) + �.

Since {U(i)j } is a cover of Ai for each i ∈ I, the collection ⋃ i∈I{U

(i) j } is a

cover of ⋃ i∈I Ai, so we have

Hsδ

(⋃ i∈I

Ai

) ≤ ∑ i

∑ j

|U(i)j | s <

∞∑ i=1

Hsδ (Ai) + �.

If we let � → 0,

Hsδ

(⋃ i∈I

Ai

) ≤ ∞∑ i=1

Hsδ (Ai)

for any δ > 0. Letting δ → 0, we then have

Hs

(⋃ i∈I

Ai

) ≤ ∞∑ i=1

Hs(Ai).

Hence the s-dimensional Hausdorff measure is indeed a measure.

3. Dimension

Now, note that if δ < 1, then for any set S ⊂ Rn, as s increases, Hsδ (S) is non-increasing; hence Hs(S) is likewise non-increasing. Let t > s, and suppose {Ui} is a δ-cover of S. Then

∞∑ i=1

|Ui|t ≤ ∞∑ i=1

|Ui|t−s|Ui|s ≤ δt−s ∑ |Ui|s

Taking the infimum of both sides, we get Htδ(S) ≤ δ t−sHsδ (S). Now, let δ → 0.

If Hs(S) < ∞, then Ht(S) = 0. Likewise, if Ht(S) > 0, then we must have limδ→0 H

s δ (S) = ∞. That is, there is no more than one value of s such that

0 < Hs(S) < ∞. Visually, this means that on a graph of Hs(S) vs. s, there is a value of s at which Hs(S) jumps from ∞ to 0 (see Figure 2). It is this value of s which we define as the Hausdorff dimension of S.

Definition 3.1. Let S ⊂ Rn. The Hausdorff dimension of S, or dimHS, is

dimHS = inf{s ≥ 0 : Hs(S) = 0} = sup{s : Hs(S) = ∞}.

FRACTALS AND DIMENSION 5

Figure 2. Graph of Hs(S) vs. s for a set S. As we can see, there is a jump from ∞ to 0, and the Hausdorff dimension of S is the value of s at which this jump occurs.

To intuitively understand the Hausdorff dimension, let’s test this definition on an object we are familiar with, such as the line segment [0, 1]. First, suppose δ = 0.1. Then, given a δ-cover of our line segment, all the components of the cover have diameter less than or equal to 0.1, that is |Ui| ≤ 0.1 for all i. Of course, there are many ways we could cover this line segment with these Ui. However, note that we can cover [0, 1] with exactly ten of these components if they are arranged appropriately, for instance, if each |Ui| = 0.1, and the sets do not overlap. Now, analogously, suppose we have a δ-cover, with the diameter of each component

|Ui| = δ. We then have that ∑∞ i=1 |Ui|

s = ∑1/δ i=1 δ

s = 1 δ δs = δs−1. Now, when

s > 1, if we let δ → 0, we have δs−1 → 0. When s < 1, if we let δ → 0, we have δs−1 → ∞. That is, if s < 1, Hs([0, 1]) = ∞, and if s > 1, Hs([0, 1]) = 0. Since the jump between 0 and ∞ occurs at s = 1, the Hausdorff dimension of the line segment [0, 1] is 1, as expected.

4. Self-Similarity

Now we will explore a particularly nice class of fractals. Self-similar fractals are those which are composed of scaled copies of themselves; that is, to construct the next iteration of the fractal, we perform simple translations or rotations on smaller versions of the shapes of the previous iteration. In the following definitions, we will rigorously define these maps, called contractions.

6 TALI KHAIN

Definition 4.1. Let D ⊂ Rn be a closed subset. A map S : D → D is called a contraction if there exists a number c, where 0 < c < 1, such that |S(x)−S(y)| ≤ c|x − y| for all x,y ∈ D. We call S a contracting similarity if equality holds, that is, if |S(x) −S(y)| = c|x−y|, and we call c the ratio of similarity.

Definition 4.2. A finite collection of contractions {S1,S2, . . . ,Sk}, where k ≥ 2, is called an iterated function system.

Definition 4.3. A non-empty compact set A ⊂ D is called an attractor if A =⋃k i=1 Si(A), where {S1,S2, . . . ,Sk} is an iterated function system.

Hence, self-similar fractals are attractors; that is, they are completely described by some collection of contracting similarities. The theorem below will allow us to calculate the Hausdorff dimension of self-similar fractals by utilizing the ratios of the similarities which define them. This calculation method is much more simple and intuitive than direct calculation of the dimension.

Theorem 4.4. Let F be a fractal such that

(4.5) F =

m⋃ i=1

Si(F),

where S1, . . . ,Sm are similarities with ratios c1, . . . ,cm. Then, dimHF = s, where s is given by

(4.6)

m∑ i=1

csi = 1.

In addition, HS(F) is a finite positive number.

Proof. To prove this theorem, we will bound Hs(F) from above and from below, and thus show that Hs(F) is a finite positive number. Hence, since it is this partic- ular value of s which makes Hs(F) finite, we will have dimHF = s. The first half of the proof (the upper bound), provided below, shows that Hs(F) is finite; for the proof that Hs(F) is positive (the lower bound), see Falconer’s Fractal Geometry [1].

Suppose we have ∑m i=1 c

s i = 1. Now, consider all compositions of the similarities

S1, . . . ,Sm of length k, where k ≥ 1. (Note that we can repeat similarities; for instance, a composition of length k = 3 could be S1 ◦ S1 ◦ S2). Let Ik be an indexing set for all such compositions of k. Then, by applying (4.5) k times, we have

F =

m⋃ i=1

Si

( m⋃ i=1

Si

( m⋃ i=1

Si (. . . )

)) ︸ ︷︷ ︸

k−times

= ⋃ Ik

Si1 ◦ · · · ◦Sik (F)

That is, F is equal to the union of the images of all possible compositions of length k of the similarities over F.

Note that the above equality holds for all k ∈ N, and for all k, this union of images is a cover of F. Now, since the mapping Si1 ◦ ·· · ◦Sik is a similarity itself,

FRACTALS AND DIMENSION 7

with ratio ci1 · · ·cik , we have∑ Ik

|Si1 ◦·· ·◦Sik (F)| s = |F|s

∑ Ik

(ci1 · · ·cik ) s = |F |s

(∑ i1

csi1

) · · ·

(∑ ik

csik

) = |F|s

where the last equality is by (4.6). Note that

|Si1 ◦ · · · ◦Sik (F)| = ci1 · · ·cik|F| ≤ (max{c1, . . . ,cm}) k|F|.

Now, using the expression above, since our choice of k is unbounded, for any δ > 0, we can find a k such that |Si1 ◦· · ·◦Sik (F)| ≤ δ. Therefore, these images are not just covers of F , but are δ-covers of F. However, there are many more possible covers of F. Thus we have an inequality in Hsδ (F) ≤ |F|

s, and hence Hs(F) ≤ |F |s. Since |F| is finite, we have that Hs(F) is finite. Thus, we have shown that Hs(F) is bounded above.

�

Let’s take a look at a few examples.

Example 4.7. Here is the middle third Cantor set.

Figure 3. Cantor Set.

To construct this fractal, we start out with the line segment [0, 1]. Then, we remove the middle third of the segment, but leave the endpoints, to get the segments [0, 1

3 ] and [ 2

3 , 1]. In the next iteration, we again remove the middle third of each

segment, and continue this process to infinity. Now, as we can see from Figure 3, the Cantor set is self-similar, as it is composed of scaled copies of itself. So, to calculate the Hausdorff dimension of the Cantor set C, we can utilize Theorem 4.4. To do this, we first need to express C as a union of the images of some similarities. Which similarities? Well, let’s look at Figure 3 again. How do we get the second iteration of the Cantor set from the first? We shrink the line segment [0, 1] by a factor of 3, and then send one copy of the scaled segment to [0, 1

3 ] and

send a second copy to [ 2 3 , 1]. From this, we can see that exactly two similarities

describe this transformation. The first similarity is S1(x) = 1 3 x, and the second is

S2(x) = 1 3 x + 2

3 . Then, we have C =

⋃2 i=1 Si(C) = S1(C) ∪S2(C). Note that the

ratios corresponding to both of these similarities are c1 = c2 = 1 3 , since this is by

how much we scale an iteration to get the next iteration. Now we apply Theorem 4.4. We need to solve for the value of s which satisfies the equality

∑2 i=1 c

s i = 1.

Well, since c1 = c2 = 1 3 , we have 1

3

s + 1

3

s = 1, so 2( 1

3 )s = 1. Then 1

3

s = 1

2 , so

s = log(2)

log(3) ≈ 0.6309.

8 TALI KHAIN

Example 4.8. Now, let’s look at the Sierpinski triangle (Figure 4).

Like the Cantor set, the Sierpinski triangle is also a self-similar fractal. So, to calculate its dimension, we can apply Theorem 4.4. To do this, we need to figure out which similarities describe the Sierpinski triangle. First, let’s understand how this fractal is constructed. We start out with an equilateral triangle. Then, we divide the triangle into four smaller equilateral triangles by placing vertices at the midpoints of each edge. To get the second iteration of the fractal, we remove the central upside down triangle. Then we repeat the process: divide each triangle into four, and remove the central one. Now, let’s express this procedure using similarities. To get from the first iteration to the second iteration, we shrink the original triangle by a factor of 2, make three copies, and move each copy so that it is aligned with one of the vertices of the original triangle. In this case, we have three similarities, S1,S2, and S3, where the ratios c1 = c2 = c3 =

1 2 . So, by Theorem 4.4,

we have 1 2

s + 1

2

s + 1

2

s = 1. Hence s =

log(3)

log(2) ≈ 1.585.

Figure 4. Sierpinski Triangle.

The same result can be achieved using a different set of similarities, for instance with ratios c1 = c2 =

1 2

(these similarities shrink the original triangle by a factor of 2 and make two copies, thus going from the first iteration to the second), and c3 = c4 = c5 =

1 4

(these similarities shrink the original triangle by a factor of 4 and make three copies, thus creating three triangles and going from the first iteration to the third). Then, to find s, we need to solve the following equation: 1

2

s + 1

2

s +

1 4

s + 1

4

s + 1

4

s = 1, which results in the same s-value as above, s =

log(3)

log(2) ≈ 1.585.

FRACTALS AND DIMENSION 9

Example 4.9. Now, let’s look at an example of a fractal which is described by similarities with different ratios.

Here is the modified Koch curve (Figure 5). To construct it, we start out with the unit interval. Then, in place of the middle third, we construct a part of a rectangle, with the horizontal side of length 1

3 and with the vertical sides of length

1 4 . In the next iteration, we repeat the same process on each side, that is, five times.

Figure 5. Modified Koch Curve.

Which similarities describe the modified Koch curve? Well, let’s see: to get from the first iteration to the second, we shrink the unit interval by a factor of 3, and send three copies of this segment to the horizontal lengths in the second iteration, and we shrink the unit interval by a factor 4, and send two copies of this segment to the vertical lengths in the second iteration. That is, we have five similarities, with ratios c1 = c2 = c3 =

1 3

and c4 = c5 = 1 4 . By applying Theorem 4.4, we have

3( 1 3 )s + 2( 1

4 )s = 1, which results in s ≈ 1.34.

5. Conclusion

In this work, we explored fractals, highly unusual objects with fractional dimen- sion. We introduced the concepts of Hausdorff measure and Hausdorff dimension in order to discuss the non-integer dimension of fractals. We then utilized the self- similarity of fractals to develop a simple method of calculating their dimension, and applied this procedure to compute the dimension of the Cantor Set, Sierpinski Triangle, and modified Koch Curve.

10 TALI KHAIN

Acknowledgments. It is a pleasure to thank my mentors, Zev Chonoles and Catherine Ray, for their help and guidance. I would also like to thank Professor Babai, for wonderful and inspiring lectures, and Professor May, for organizing this fantastic program!

References

[1] Falconer, K. J. Fractal Geometry: Mathematical Foundations and Applications. 2nd ed. Chich-

ester: Wiley, 1990. Print. [2] Benoit Mandelbrot: How Long Is the Coast of Britain? Statistical Self-Similarity and Frac-

tional Dimension. Science, New Series, Vol. 156, No. 3775. (May 5, 1967), pp. 636-638.

[3] ”Hausdorff Dimension”. Mathematical Database. Web.