Coding Fractals by trees

November 15, 2010

Recently I’ve been editing a set of notes taken by professor Kra during Furstenberg’s course last year. (Well…I should have done this last year >.<) One of the main ideas in the course was to build a correspondence between trees and Fractal sets – and hence enables one to prove statements about dimensions and projections of Fractals by looking at the corresponding trees. I want to sketch some highlights of the basic idea here.

Let Q=Q^{(n)} denote the unit cube in \mathbb{R}^{n}.

Let A\subset\mathbb{R}^{n} and x\in A. For t\in\mathbb{R}, consider the family
t(A-x)\cap Q.

Question:Does the limit exist as t\to\infty? (here we consider the Hausdorff limit on compact subsets of Q)

i.e. we ‘zoom in’ the set around the point x, always crop the set to the cube Q and consider what does the set ‘look like’ when the strength of the magnifying glass approaches infinity.

Example:
If A is smooth (curve of surface), then this limit exists and is a subspace intersected with Q.

Generally one should not expect the above limit to exist for fractal sets, however if we weaken the question and ask for the limit when we take a sequence (n_k)\rightarrow\infty, then it’s not hard to see self-similar sets would have non-trivial limits. Hence in some sense fractal behavior is characterized by having non-trivial limit sets.

Definition: Let A\subset Q^{(n)},
A' is a mini-set of A if for some \lambda\geq 1 and u\in\mathbb{R}^{n}, A' =(\lambda A+u)\cap Q

A'' is a micro-set of A if there is sequence of minisets A'_{n} of A and A'' = \lim_{n\to\infty}A'_{n}

A is homogeneous if all of its microsets are minisets. As we should see below, homogeneous fractals are ‘well-behaved’ in terms of dimensions.

Here comes a version of our familiar definition:

Definition:A set A\subset X has Hausdorff \alpha-measure 0 if for every \varepsilon > 0, there exists a covering of A\subset \bigcup_{n=1}^{\infty}B_{\rho_{n}} with \sum_{n}\rho_{n}^{\alpha}  \alpha.

Thus it makes sense to define:

Definition: The Hausdorff dimension of A is

\dim(A) = \inf\{\alpha>0\colon \text{Hausdorff } \alpha \text{ measure is } 0 \}.

Now comes trees~ For A\subset[0,1] closed, consider expansion in base 3 of numbers in A. In the expansion of each number in A, there will be certain digits which appear. Following this digit, there may be certain digits that can appear. This defines a tree, which is a tree of shrinking triadic intervals that intersects the set A.

Definition: Let \Lambda be a finite set of symbols (which we will refer to as the alphabet and elements of \Lambda are letters of the alphabet).

A word w is any concatenation of finitely many symbols in \Lambda, the number of symbols in w is called the length of w, denoted by \ell(w).

A tree \tau in the alphabet \Lambda is a set of words satisfying
1. If uv\in\tau then u\in\tau.
2. If u\in\tau, then there exists a letter a\in\Lambda such that ua\in\tau.

Notation: if w\in\tau, denote \tau^{w} = \{v\colon wv\in\tau\}.

Definition: A section \Sigma of \tau is a finite set of words for which there exists N such that if s\in\tau and \ell(s) \geq N, then there exists r\in\Sigma and a word w such that s = rw.

Definition: The Hausdorff dimension of a tree is defined by \dim(\tau)=\inf\{ \beta \ | \ \inf_{\Sigma}\{\sum_{r\in\Sigma} e^{-\beta\ell(r)}\} = 0 \} where \Sigma is any section of \tau.

Theorem: The Hausdorff dimension of a tree equals the Hausdorff dimension of set it corresponds to.

The proof is merely going through the definition, hence we won’t present here. It suffice to check the dimension is unchanged if we only consider open ball covers with balls of radius $p^{-n}$ for any given $p \in \N$. Which is indeed true.

Now let’s give a simple example to illustrate how to make use of this correspondence:

It is easy to prove \dim(X \times Y) \geq \dim(X) \times \dim(Y), here we produce an example were the inequality is strict.

Let A \subseteq [0,1] be the set of numbers whose decimal expansion vanishes from the k_{2n} to k_{2n+1}-th digits to the right of 0.

To compute \dim(A), look at levels such that a small number of intervals will cover the set A. The number of intervals of size 10^{k_{2n+1}} is less than 10^{k_{2n}}. Then if \frac{10^{k_{2n}}}{k_{2n+1}} goes to 0, we’ll have that the Hausdorff dimension is 0. So we just
need k_{2n}/k_{2n+1}\to 0.

Let B be the set of numbers whose decimals vanish from k_{2n-1} to k_{2n}-1-th digits. By the same computation, \dim(B) = 0.

What about A\times B? The tree that corresponds to this is a regular tree which every point has 10 branches. So the Hausdorff dimension is 1.

Note: Here the structure of the tree gives you easy information on the set, but it is hard to look directly at the set and see this information.

Many theorems regarding dimension of projections and intersections of fractal sets turns out to be simple to prove after we coded the sets by trees.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: