Tag: fractal

Coding Fractals by trees

ConanLeave a comment

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.

Remarks from the Oxtoby Centennial Conference

Conan1 Comment

A few weeks ago, I received this mysterious e-mail invitation to the ‘Oxtoby Centennial Conference’ in Philadelphia. I had no idea about how did they find me since I don’t seem to know any of the organizers, as someone who loves conference-going, of course I went. (Later I figured out it was due to Mike Hockman, thanks Mike~ ^^ ) The conference was fun! Here I want to sketch a few cool items I picked up in the past two days:

Definition:A Borel measure \mu on [0,1]^n is said to be an Oxtoby-Ulam measure (OU for shorthand) if it satisfies the following conditions:
i) \mu([0,1]^n) = 1
ii) \mu is positive on open sets
iii) \mu is non-atomic
iv) \mu(\partial [0,1]^n) = 0

Oxtoby-Ulam theorem:
Any Oxtoby-Ulam measure is the pull-back of the Lebesgue measure by some homeomorphism \phi: [0,1]^n \rightarrow [0,1]^n.

i.e. For any Borel set A \subseteq [0,1]^n, we have \mu(A) = \lambda(\phi(A)).

It’s surprising that I didn’t know this theorem before, one should note that the three conditions are clearly necessary: A homeo has to send open sets to open sets, points to points and boundary to boundary; we know that Lebesgue measure is positive on open sets, 0 at points and 0 on the boundary of the square, hence any pull-back of it must also has those properties.

Since I came across this at such a late time, my first reaction was: this is like Moser’s theorem in the continuous case! But much cooler! Because measures are a lot worse than differential forms: many weird stuff could happen in the continuous setting but not in the smooth setting.

For example, we can choose a countable dense set of smooth Jordan curves in the cube and assign each curve a positive measure (we are free to choose those values as long as they sum to 1. Now we can define a measure supported on the union of curves and satisfies the three conditions. (the measure restricted to each curve is just a multiple of the length) Apply the theorem, we get a homeomorphism that sends each Jordan curve to a Jordan curve with positive n dimensional measure and the n dimensional measure of each curve is equal to our assigned value! (Back in undergrad days, it took me a whole weekend to come up with one positive measured Jordan curve, and this way you get a dense set of them, occupying a full measure set in the cube, for free! Oh, well…>.<)

Question: (posed by Albert Fathi, 1970)
Does the homeomorphism \phi sending \mu to Lebesgue measure depend continuously on \mu?

My first thought was to use smooth volume forms to approximate the measure, for smooth volume forms, Moser’s theorem gives diffeomosphisms depending continuously w.r.t. the form (I think this is true just due to the nature of the construction of the Moser diffeos) the question is how large is the closure of smooth forms in the space of OU-measures. So I raised a little discussion immediately after the talk, as pointed out by Tim Austin, under the weak topology on measures, this should be the whole space, with some extra points where the diffeos converge to something that’s not a homeo. Hence perhaps one can get the homeo depending weakly continuously on \mu.

Lifted surface flows:

Nelson Markley gave a talk about studying flows on surfaces by lifting them to the universal cover. i.e. Let \phi_t be a flow on some orientable surface S, put the standard constant curveture metric on S and lift the flow to \bar{\phi}_t on the universal cover of S.

There is an early result:

Theorem: (Weil) Let \phi_t be a flow on \mathbb{T}^2, \bar{\phi}_t acts on the universal cover \mathbb{R}^2, then for any p \in \mathbb{R}^2, if \displaystyle \lim_{t\rightarrow \infty} ||\bar{\phi}_t(p)|| = \infty then \lim_{t\rightarrow \infty} \frac{\bar{\phi}_t(p)}{||\bar{\phi}_t(p)||} exists.

i.e. for lifted flows, if an orbit escapes to infinity, then it must escape along some direction. (No sprial-ish or wild oscillating behavior) This is due to the nature that the flow is the same on each unit square.

We can find its analogue for surfaces with genus larger than one:

Theorem: Let \phi_t be a flow on S with g \geq 2, \bar{\phi}_t: \mathbb{D} \rightarrow \mathbb{D}, then for any p \in \mathbb{D}, if \displaystyle \lim_{t\rightarrow \infty} ||\bar{\phi}_t(p)|| = \infty then \lim_{t\rightarrow \infty} \bar{\phi}_t(p) is a point on the boundary of \mathbb{D}.

Using those facts, they were able to prove results about the structure of \omega limiting set of such orbits (those that escapes to infinity in the universal cover) using the geometric structure of the cover.

I was curious about what kind of orbits (or just non-self intersecting curves) would ‘escape’, so here’s some very simple observations: On the torus, this essentially means that the curve does not wind around back and forth infinitely often with compatible magnitudes, along both generators. i.e. the curve ‘eventually’ winds mainly in one direction along each generating circle. Very loosely speaking, if a somewhat similar thing is true for higher genus surfaces, i.e. the curve eventually winds around generators in one direction (and non-self intersecting), then it would not be able to have very complicated \omega limiting set.

Measures on Cantor sets

In contrast to the Oxtoby-Ulam theorem, one could ask: Given two measures on the standard middle-third Cantor set, can we always find a self homeomorphism of the Cantor set, pushing one measure to the other?

Given there are so many homeomorphisms on the Cantor set, this sounds easy. But in fact it’s false! –There are countably many clopen subsets of the Cantor set (Note that all clopen subsets are FINITE union of triadic copies of Cantor sets, a countable union would necessarily have a limit point that’s not in the union), a homeo needs to send clopen sets to clopen sets, hence for there to exist a homeo the countably many values the measures take on clopen sets must agree.

So a class of ‘good measures’ on Cantor sets was defined in the talk and proved to be realizable by a pull back the standard Hausdorff measure via a homeo.

I was randomly thinking about this: Given a non-atomic measure \mu on the Cantor set, when can it be realized as the restriction of the Lebesgue measure to an embedding of the Cantor set? After a little bit of thinking, this can always be done. (One can simple start with an interval, break it into two pieces according to the measure \mu of the clopen sets before and after the largest gap, then slightly translate the two pieces so that there is a gap between them; iterate the process)

In any case, it’s been a fun weekend! ^^

Hausdorff dimension of projections

ConanLeave a comment

A few days ago, professor Wilkinson asked me the following question on google talk (while I was in Toronto):

“Say that a set in \mathbb{R}^n is a k-zero set for some integer k<n if for every k-dimensional subspace P, saturating the set X by planes parallel to P yields a set of n-dimensional Lebesgue measure zero. How big can a k-zero set be?”

On the spot my guess was that the Hausdorff dimension of the set is at most n-k. In deed this is the case:

First let’s note that n-dimensional Lebesgue measure of the P-saturated set is 0 iff the n-k dimensional Lebesgue measure of the projection of our set to the n-k subspace orthogonal to P is 0.

Hence the question can be reformulated as: If a set E \subseteq \mathbb{R}^n has all n-k dimensional projection being n-k zero sets, how big can the set be?

Looking this up in the book ‘The Geometry of Fractal Sets’ by Falconer, indeed it’s a theorem:

Theorem: Let E \subseteq \mathbb{R}^n compact, \dim(E) = s (Hausdorff dimension), let G_{n,k} be the Garssmann manifold consisting of all k-dimensional subspaces of \mathbb{R}^n, then
a) If s \leq k, \dim(\mbox{Proj}_\Pi E) = s for almost all \Pi \in G_{n,k}

b) If s > k, \mbox{Proj}_\Pi E has positive k-dimensional Lebesgue measure for almost all \Pi \in G_{n,k}.

In our case, we have some set with all n-k-dimensional projection having measure 0, hence the set definitely does not satisfy b), i.e. it has dimensional at most n-k. Furthermore, a) also gives that if we have a uniform bound on the dimension of almost all projections, this is also a bound on the dimension of our original set.

This is strict as we can easily find sets that’s n-k dimensional and have all such projections measure 0. For example, take an n-k subspace and take a full-dimension measure 0 Cantor set on the subspace, the set will have all projections having measure 0.

Also, since the Hausdorff dimension of any projection can’t exceed the Hausdorff dimension of the original set, a set with one projection having positive n-k measure implies the dimension of the original set is \geq n-k.

Question 2: If one saturate a k-zero set by any smooth foliations with k-dimensional leaves, do we still get a set of Lebesgue measure 0?

We answer the question in the affective.

Given foliation \mathcal{F} of \mathbb{R}^n and k-zero set E. For any point p \in E, there exists a small neighborhood in which the foliation is diffeomorphic to the subspace foliation of the Euclidean space. i.e. there exists f from a neighborhood U of p to (-\epsilon, \epsilon)^n where the leaves of \mathcal{F} are sent to \{\bar{q}\} \times (-\epsilon, \epsilon)^k, \bar{q} \in (-\epsilon, \epsilon)^{n-k}.

By restricting f to a small neighborhood (for example, by taking \epsilon to be half of the origional \epsilon), we may assume that f is bi-Lipschitz. Hence the measure of the \mathcal{F}-saturated set inside U of U \cap E is the same as f(U \cap E) saturated by parallel k-subspaces inside (-\epsilon, \epsilon)^n. Dimension of f(E) is the same as dimension of E which is \leq n-k, if the inequality is strict, then all projections of f(E) onto n-k dimensional subspaces has measure 0 i.e. the saturated set by k-planes has n dimensional measure 0.

…to be continued

Kaufman’s construction

ConanLeave a comment

This is a note on R. Kaufman’s paper An exceptional set for Hausdorff dimension

We construct a set D \subseteq \mathbb{R}^2 with \dim(D) = d < 1 and E \subseteq [0, \pi) with \dim(E) > 0 s.t. for all directions \theta \in E, \dim(\pi_\theta(D)) < d-\epsilon (the projection of D in direction \theta is less than d-\epsilon)

\forall \alpha >1, let (n_j)_{j=1}^\infty be an rapidly increasing sequence of integers.

Define D_j = \{ (a, b)/n_j + \xi \ | \ a, b \in \mathbb{Z}, \ ||(a, b)|| \leq n_j; \ | \xi | \leq n_j^{- \alpha} \}

i.e. D_j = \bigcup \{ B((a,b)/n_j, 1/n_j^\alpha) \ | \ (a, b) \in \mathbb{Z}^2 \cap B( \overline{0}, n_j) \}

Let D = \bigcap_{j=1}^\infty D_j

\because \alpha > 1, \ (n_j) rapidly increasing, \dim(D) = 2 / \alpha

Let c \in (0, 1) be fixed, define E' = \{ t \in \mathbb{R} \ | \ \exists positive integer sequence (m_{j_i})_{i=1}^\infty s.t. m_{j_i} < C_1 n_{j_i}^c, \ || m_{j_i} t || < C_2 m_{j_i} / n_{j_i}^\alpha \}

\forall t \in E', \ \forall i \in \mathbb{N}, \ \forall p = (a, b)/n_{j_i} + \xi \in D_{j_i}, we have:

| \langle p, (1, t) \rangle - a/n_{j_i} - bt/n_{j_i} | \leq (1+|t|)/n_{j_i}^\alpha

Let b = q m_{j_i} + r where 0 \leq r < m_{j_i}, |q m_{j_i}| < C n_{j_i}

\exists z_{j_i} \in \mathbb{Z}, \ | z_{j_i} | < C | n_{j_i} |, \ | \theta |<1

bt = qm_{j_i}t +rt = X + rt + q \theta ||m_{j_i}t||

A question by Furstenberg

ConanLeave a comment

Yesterday I was talking about some properties of different dimensions with Furstenburg. Somehow I mentioned Kekaya, and he told me about the following question he has been longing to solve (which is amazingly many similarities to Kekaya):

For set S \in \mathbb{R}^2, if \exists \delta>0 s.t. for all direction \theta, \exists line l with direction \theta s.t. \dim (l \cap S) > \delta . Does it follow that \dim(A) \geq 1 ?

Note that a stronger conjecture would be \dim(A) is at least 1+\delta which when taking \delta = 1 would give a generalization of the 2-dimensional Kekaya. (i.e. instead of having to have a line segment, we only require a 1-dimension set in each direction)

Reviewing the proofs of the 2-dimsional Kekaya, I found they all rely on the fact that the line segment is connected…Hence it might be interesting to even find an answer to the following question:

If A \subseteq \mathbb{R}^2 contains a measure 1 set in every direction, does it follow that \dim(A)=2?