Coding Fractals by trees

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$ .