Fractal Dimension

From an early age, we that learn lines and curves are one-dimensional, planes and surfaces are two-dimensional, solids such as a cube are three dimensional, and so on. More formally, we say a set is n-dimensional if we need n independent variables to describe a neighborhood of any point. This notion of dimension is called the topological dimension of a set.^5.10The dimension of the union of finitely many sets is the largest dimension of any one of them, so if we ``grow hair'' on a plane, the result is still a two-dimensional set. We should note here that if we take the union of an infinite collection of sets, the dimension can grow. For example, a line, which is one-dimensional, is the union of an infinite number of points, each of which is a zero-dimensional object.

Figure 1: Some one- and two-dimensional sets (the sphere is hollow, not solid).

There can occaisionally be a little confusion about the dimension of an object: sometimes people call a sphere a three-dimensional object, because it can only exist in space, not in the plane. However, a sphere is two-dimensional: any little piece of it looks like a piece of the plane $\R^{2}_{}$, and in such a small piece, you only need two coordinates to describe the location of a point.^5.11

But, what about the fractals we have been considering? For example, what is the dimension of the Koch snowflake? It has topological dimension one, but it is by no means a curve-- the length of the ``curve'' between any two points on it is infinite. No small piece of it is line-like, but neither is it like a piece of the plane or any other $\R^{n}_{}$. In some sense, we could say that it is too big to be thought of as a one-dimensional object, but too thin to be a two-dimensional object. Maybe its dimension should be a number between one and two. In order to make this kind of thinking more precise, let's look at the dimension of familiar objects another way.

Box counting dimension

What is the relationship between an object's length (or area or volume) and its diameter? The answer to this question leads to another way to think about dimension. Let us consider a few examples.

If we try to cover the unit square with little squares of side length $\epsilon$, how many will we need? Obviously, the answer is 1/$\epsilon^{2}_{}$. How about to cover a segment of length 1? Here we need only 1/$\epsilon$ little squares. If we think of the square and segment as sitting in space and try to cover them with little cubes $\epsilon$ on a side, we get the same answer. And if we use the little cubes to cover a 1×1×1 cube, how many will we need? Exactly 1/$\epsilon^{3}_{}$. Note that the exponent here is the same as the dimension of the thing we are trying to cover. This is no coincidence.

Figure 2: Covering a curve, a surface, and a solid cube with cubes of diameter $\epsilon$.

We define the box-counting dimension (or just ``box dimension'') of a set $\Cal{S}$ contained in $\R^{n}_{}$ as follows: For any $\epsilon$ > 0, let N_$\epsilon$($\Cal{S})$ be the minimum number of n-dimensional cubes of side-length $\epsilon$ needed to cover $\Cal{S}$. If there is a number d so that

N_$\epsilon$($$\Cal{S}) \sim 1/\epsilon^d \qquad\text{as}\qquad \epsilon\rightarrow 0,$$

we say that the box-counting dimension of $\Cal{S}$ is d. We will denote this by $\boxdim$$\Cal{S}$ = d.

Note that the box-counting dimension is d if and only if there is some positive constant k so that

$$\lim_{\epsilon\rightarrow 0}^{}$$$${\frac{N_{\epsilon}(\Cal{S})}{1/\epsilon^d}}$$ = k.

Since both sides of the equation above are positive, it will still hold if we take the logarithm of both sides to obtain

$$\lim_{\epsilon\rightarrow 0}^{}$$$$\left(\vphantom{ \ln N_{\epsilon}(\Cal{S}) + d\ln \epsilon }\right.$$ln N_$\epsilon$($$\Cal{S}) + d\ln \epsilon$$$$\left.\vphantom{ \ln N_{\epsilon}(\Cal{S}) + d\ln \epsilon }\right)$$ = ln k.

Solving for d gives

d = $$\lim_{\epsilon\rightarrow 0}^{}$$$${\frac{\ln k - \ln N_{\epsilon}(\Cal{S})}{\ln \epsilon}}$$ = - $$\lim_{\epsilon\rightarrow 0}^{}$$$${\frac{\ln N_{\epsilon}(\Cal{S})}{\ln \epsilon}}$$.

Note that the ln k term drops out, because it is constant while the denominator becomes infinite as $\epsilon$ $\rightarrow$ 0. Also, since 0 < $\epsilon$ < 1, ln$\epsilon$ is negative, so d is positive as we would expect.

We should remark that there are some sets $\Cal{S}$ for which $\boxdim$$\Cal{S}$ cannot be defined because there is no d for which the limit converges.^5.12We will not encounter such examples here, however. Since the box-counting dimension is so often used to calculate the dimensions of fractal sets, it is sometimes referred to as ``fractal dimension''. We prefer the term box dimension, however, because sometimes the term ``fractal dimension'' might refer to box dimension, Hausdorff dimension, or even other measures of dimension such as the information dimension or capacity dimension.

When computing box dimension, several simplifications can be made.

• We need not use boxes if some other shape is more convenient: if we cover our set with disks of diameter $\epsilon$, or even stars or mickey-mouses of diameter $\epsilon$, we will get the same answer.

• Not every possible $\epsilon$ need be considered. It is enough to consider the limit of ln N_{$\epsilon_{i}$}/ln$\epsilon_{i}^{}$ where $\epsilon_{i}^{}$ is a sequence converging to zero. Choosing a convenient sequence often makes the calculations much easier.

Sometimes box counting dimension is referred to as ``similarity dimension'' in the context of self-similar sets. If a set is self-similar, there is an expansion factor r by which one can blow up a small copy to get the whole set. If there are exactly N such small copies that make up the entire set, the box dimension is easily seen to be ln N/ln r.

Computing the box dimension of some examples

Not surprisingly, the box dimensions of ordinary Euclidean objects such as points, curves, surfaces, and solids coincide with their topological dimensions of 0, 1, 2, and 3-- this is, of course, what we would want to happen, and follows from the discussion at the beginning of §5.1. But what about other, more complicated sets? Let's try a few simple examples for some subsets of the unit interval [0, 1]. In these cases, our $\epsilon$-cubes can be closed intervals of length $\epsilon$.

Consider the set of points $\Cal{A} = \set{0, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \ldots}$. For any n$\ge$ 0, we can cover $\Cal{A}$ with n intervals of length 1/2ⁿ: we need one for the elements between 0 and ${\frac{1}{2^n}}$, and another interval for each of the remaining n - 1 elements of $\Cal{A}$. This means that $\boxdim$$\Cal{A}$ = $\lim_{n\rightarrow\infty}^{}$n/2ⁿ = 0. The box dimension and the topological dimension of $\Cal{A}$ are the same.

Let $\Cal{Q}$ be the set of rational numbers in the interval [0, 1], that is,

$$\Cal{Q}= \set{\frac{p}{q} \st p, q \text{are relatively prime integers with} p \le q}.$$

What is $\boxdim$$\Cal{Q}$? Since the rationals are dense in [0, 1], any interval we choose contains some. This means for every $\epsilon$ > 0, we will need 1/$\epsilon$ intervals to cover $\Cal{Q}$. Thus, N_$\epsilon$($\Cal{Q}) = 1/\epsilon$. Consequently, $\boxdim$$\Cal{Q}$ = $\lim_{\epsilon\rightarrow0}^{}$${\frac{1/\epsilon}{1/\epsilon}}$ = 1.

Recall that any real number x can be represented as a (possibly infinitely long) decimal. For example, 1/4 = .25, 1/11 = .0101$\overline{01}$..., and $\pi$ = 3.14159265.... The decimal expansion is not quite unique-- for example, 1/2 can be written as either .4999999$\overline{9}$... or .5000000$\overline{0}$.... This is the only possible point of confusion, however: any real number x ending in all zeros has another representation ending in all nines.

Let us determine the box-counting dimension of the set

$$\Cal{D}= \set{x\in [0,1] \st x\; \text{has a decimal expansion containing no 4s or 5s}}.$$

First, let's note a few things about $\Cal{D}$:

• It is totally disconnected: that is, between any two points of $\Cal{D}$, there is another point which is not in $\Cal{D}$.
• It is closed: the limit of any convergent sequence of points in $\Cal{D}$ is still in $\Cal{D}$. Note that this is not the case for the set $\Cal{Q}$ above-- a sequence of rational numbers can converge to an irrational.
• It has uncountably many points. Much like the irrational numbers, there are far too many elements of $\Cal{D}$ to enumerate them. Also like the irrational numbers, we can enumerate what is not in $\Cal{D}$.
• We shall see that $\Cal{D}$ is also self-similar: any small piece of it can be scaled up to look like the whole thing just by multiplying by an appropriate power of 10.

So, what is $\boxdim$$\Cal{D}$? Let's construct a sequence of covers of $\Cal{D}$ whose diameter tends to zero, and count the number of pieces we need. Note that while $\Cal{D}$ contains the points^5.13.4 and .6, it does not contain the open interval (.4,.6), so we can cover it by two intervals of length .4, namely [0,.4] and [.6, 1]. This means N_.4 = 2.

At the next finer level, we can see that $\Cal{D}$ can be covered with the intervals

[0,.04],	[.06,.10],	[.10,.14],	[.16,.20],	[.20,.24],	[.26,.30],	[.30,.34],	[.36,.40],
[.60,.64],	[.66,.70],	[.70,.74],	[.76,.80],	[.80,.84],	[.86,.90],	[.90,.94],	[.96, 1]

That is, we need 16 intervals of length .04. This means that N_.04 = 16.

For $\epsilon$ = .004, we will need 8 times as many intervals to cover $\Cal{D}$. This pattern continues: each time we shrink $\epsilon$ by another factor of 10, we need 8 times as many intervals.

This means that

$$\boxdim$$$$\Cal{D}$$ = - $$\lim_{n\rightarrow\infty}^{}$$$${\frac{\ln 8^{n-1}}{\ln \left(4\cdot 10^{-n}\right)}}$$ = - $$\lim_{n\rightarrow\infty}^{}$$$${\frac{(n-1)\ln 8}{\ln 4 - n\ln10}}$$ = $${\frac{\ln 8}{\ln 10}}$$ = $${\frac{3\ln 2}{\ln 10}}$$ $$\approx$$ .903089987

The box-counting dimension of $\Cal{D}$ is not an integer. Note that the topological dimension of $\Cal{D}$ is zero.

Footnotes

... set.^5.10

In fact, there is a much more precise definition of topological dimension, but to give it requires more background material than we are prepared to give here.

... point.^5.11

In fact, this is just a different measure of dimension, called the embedding dimension: a set has embedding dimension n if n is the smallest integer for which it can be embedded into $\R^{n}_{}$ without intersecting itself. Thus, the embedding dimension of a plane is 2, the embedding dimension of a sphere is 3, and the embedding dimension of a klein bottle is 4, even though they all have (topological) dimension two. A famous theorem (the Whitney embedding theorem) says that if a manifold has topological dimension n, its embedding dimension is at most 2n.

... converges.^5.12

Mathematicians often use a more general measure called Hausdorff dimension, which is defined for every such set. One difficulty with the Hausdorff dimension is that it is often very hard to compute. The Hausdorff and box dimensions coincide for compact, self-similar fractals, so we will not concern ourselves with the distinction.

... points^5.13

$\Cal{D}$ contains .4 because it can be written as 0.399$\overline{9}$..., which contains no 4s or 5s.