Fractals

Fractals are geometric objects with a fractional dimension; there are several definitions of dimension that can include this possibility. Usually (but not always) fractals have some sort of self-similar structure, or an approximately self-similar structure.

Box-counting dimension

One of the simplest dimension definitions is the box-counting dimension. Given a bounded set $S$ in $n$ -dimensional space $\mathbb{R}^n$ , let $N(\epsilon)$ be the minimal number of boxes with side length $\epsilon$ needed to cover the set. Then the box-counting dimension is

$$ D_B(S) = \lim_{\epsilon \rightarrow 0} \frac{\log(N(\epsilon))}{\log(1/\epsilon)} $$.

For example, if we have a smooth simple closed curve in the plane, such as a circle, for small enough $\epsilon$ the number of squares needed will be about the arclength of the curve divided by $\epsilon$ , so $N(\epsilon) \approx C/\epsilon$ for some constant $C$ . As $\epsilon$ goes to zero, the numerator will approach the denominator, and the box-counting dimension will be $1$ .

Similarity dimension

It can be difficult to calculate the fractal dimension of a set. If the set is self-similar (or at least asymptotically self-similar), then there is a simple recipe for calculating the dimension. If a set $S$ is similar to $M$ copies of itself rescaled by a factor of $1/r$ , then the similarity dimension is

$D_s(S) = \frac{\log(M)}{\log(r)}.$

We will use this to calculate the dimension of several classic fractals below.

Hausdorff dimension

In contrast to the similarity dimension, a much more general definition of fractal dimension is the Hausdorff dimension $D_H$ , developed by Felix Hausdorff in a very influential 1919 paper ("Dimension and outer measure"). To define it we need some auxiliary concepts.

We define the diameter of a set $U$ in a metric space $X$ (with metric $\rho$ ) to be

$diam(U) = \sup_{x,y \in U} \rho(x,y)$

where $\sup$ is the supremum, or least upper bound.

Next we need the Hausdorff outer measure for dimension $d$ at a scale $\epsilon$ of a set $S \subset X$ . First we use

$H^d_{\epsilon}(S) = \inf \{ \sum_{i}^{\infty} (diam(U))^d \ \ | \ \ S \subset \cup_{i=1}^{\infty} U_i, diam(U) < \epsilon \}$

to obtain the outer measure as the limit

$H^d(S) = \lim_{\epsilon \rightarrow 0} H^d_{\epsilon}(S)$

where the infimum, or greatest lower bound, in $H^d_{\epsilon}(S)$ is taken over all covers of $S$ by sets $U$ that have diameter less than $\epsilon$ . Because the structures of the sets $U_i$ are arbitrary (apart from the diameter bound), this can be a very difficult definition to use in practice.

Now we can define the Hausdorff dimension as

$D_H(S) = \inf \{ d \ge 0 \ \ | \ \ H^d(S) = 0 \}.$

Correlation dimension

A more empirical type of fractal dimension is the correlation dimension, developed by physicists Grassberger and Procacci in 1983. We assume that we have samples (or an orbit) $x_0, x_1, \ldots$ from a set $S$ . Then for a given scale $r$ we define a correlation function

$C_r(S) = \lim_{N \rightarrow \infty} \frac{ \# \{ (y,z) \ \ | y,z \in S, |y-z| < r \} }{ \# \{ (y,z) \ \ | y,z \in S \} }$

i.e. the limit of the fraction of pairs of points that are within a given distance from each other. Then the correlation dimension is

$d_C(S) = \lim_{r \rightarrow 0} \frac{\log C_r(S)} { \log r}.$

Some Famous Fractals

Smith-Volterra-Cantor set

Often just called the Cantor set, this is probably the most important and ubiquitous fractal found in dynamical systems.

The Cantor set is defined as the intersection of the sequence of sets formed by deleting the middle of each previous stage's intervals. If the middle third is deleted, then the set is similar to two copies of itself scaled by a factor of $3$ , so the similarity dimension is $\frac{\log 2}{\log 3} \approx 0.63$ . If instead at each state the intervals are replaced by two smaller copies of size $1/a$ , with $a \in (2,\infty)$ , then the similarity dimension is $\frac{\log 2}{\log a} \in (0,1)$ .

Weierstrass function

As we mentioned in the introduction, perhaps the earliest mathematical example of a fractal is a function constructed by Karl Weierstrass that is continuous but nowhere differentiable:

$\sum_{n=0}^{\infty} a^n \cos(b^n \pi x) , \ \ \ \ ab > 1 + 3 \pi/2$

Zooming in on the Weierstrass function (a=0.1, b=31)

With certain choices of $a$ and $b$ , this can be used as a sonic waveform to make a sound with the peculiar property that if a recording of it is sped up, the perceived pitch will go down (pointed out by the acoustic engineer and author Manfred Schroeder in his very interesting book "Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise").

Sierpinski triangle

The Sierpinski triangle was described by Sierpinski in 1915, although the geometric idea has appeared in art (e.g. Roman tilings) for at least 1000 years.

An interesting way to stochasticly construct a Sierpinski triangle is to pick three primary points in the plane, and any starting point $z_0$ . Then at each step choose one of the three primary points at random, and the next point is the midpoint of that primary point and the previous iterate. This is shown below (you can move the primary points).

This procedure is an example of an iterated function system, or IFS. These can be efficient methods for constructing some fractals, for example for drawing plant leaves in computer graphics.

Since the Sierpinski triangle is similar to 3 copies of itself scaled by a factor of 2, the similarity dimension is $\frac{\log{3}}{\log2} \approx 1.6$ .

Koch snowflake

In 1904, the Swedish mathematician Helge von Koch described a fractal with a simple geometric construction, usually called the Koch snowflake.

The similarity dimension of the Kock snowflake is $\frac{4}{3} \approx 1.3$ .

Hilbert curve

This important example was described by David Hilbert in 1891. It is constructed as a limit of continuous curves, as shown in the animation below for a few iterations:

The limit curve gives a continuous function from a one-dimensional line segment to a two-dimensional square. Because of this surprising property, it has some practical applications in image processing, databases, and other areas.

Lindenmayer systems (L-system)

The biologist Aristid Lindenmayer invented a variant of formal grammars and cellular automata called L-systems in his honor. Although Lindenmayer invented these systems to study the growth of plants and algae, they are also very useful in describing many self-similar fractals, including some of the earliest and important examples (e.g. the Hilbert curve).

Exercises

Compute the box-counting dimension of the sets (a) $A = \{0\} \cup \{1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \ldots \}$ and (b) $B = \{0\} \cup \{1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \ldots \}$ .