Ultrametrics and the nonlinear Dvoretzky problem

September 19, 2011September 20, 2011 Conan5 Comments

Hi guys~ The school year here at Princeton is finally (gradually) starting. So I’m back to this blog :-P

In this past week before anything has started, Assaf Naor came here and gave a couple rather interesting talks, which I decided to make a note about. For the complete content of the talk please refer to this paper by Naor and Mendel. As usual, I make no attempt on covering what was written on the paper nor what was presented in the talk, just some random pieces and bits which I found interesting.

A long time ago, Grothendieck conjectured what is now known as Dvoretzky’s theorem:

Theorem: For any $D>1$ , for any $k \in \mathbb{N}$ , there exists $N$ depending only on $k, D$ such that any normed vector space of dimension $N$ or larger has a k-dimensional linear subspace that embeds (via a linear transformation) with distorsion at most $D$ into the Hilbert space.

i.e. this says in the case where $D$ is close to $1$ (let’s write $D = 1+\varepsilon$ ) for any given k, *any* norm on a vector space of sufficiently high dimension will have a $k$ dimensional subspace that looks almost Eculidean (meaning unit ball is round up to a multiple $1+\varepsilon$ ).

Well, that’s pretty cool, but linear. As we all know, general metric spaces can be much worse than normed vector spaces. So here comes a nonlinear version of the above, posted by Terrence Tao:

Nonlinear Dvoretzky problem: Given $\kappa>0, D>1$ , does there exist a $\alpha$ so that every metric space of Hausdorff dimension $\geq \alpha$ has a subset $S$ of Hausdorff dimension $\kappa$ that embeds into the Hilbert space with distorsion $D$ ?

Indeed, we should expect this to be a lot more general and much harder than the linear version, since we know literally nothing about the space except for having large Hausdorff dimension and as we know metric spaces can be pretty bizarre. That why we should find the this new result of theirs amazing:

Theorem 1 (Mendel-Naor): There is a constant $C$ such that for any $\lambda \in (0,1)$ , every compact metric space with dimension $\alpha$ has a closed subset $S$ of dimension at least $(1-\lambda) \alpha$ that admits an embedding into Hilbert space with distorsion $C/ \lambda$ .

Note that, in the original linear problem, $N = N(k, D)$ of course blows up to infinity whenever $k \rightarrow \infty$ or $D \rightarrow 1$ . (whenever we need a huge dimensional space with fixed ‘flatness’ or a fixed dimension but ‘super-flat’ subspace). That is, when we are looking for subspaces inside a random space with fixed (large) dimension $N$ , the larger dimension we need, the less flat (more distorsion) we can expect it to be. i.e.

$k \rightarrow N$ necessarily forces $D \rightarrow \infty$ and
$D \rightarrow 1$ forces $k \rightarrow 0$ .

We can see that this nonlinear theorem is great when we need large dimensional subspaces (when $\lambda$ is close to $0$ ), but not so great when we want small distorsion (it does not apply when distorsion is smaller than $C$ , and blows up when it gets close to $C$ ).

In the original statement of the problem this gives not only that a large $\alpha$ exists, but $\alpha(\kappa, D) \leq \frac{D}{D-C} \kappa$ ! In fact, when we are allowing relatively large distorsion (compare to constant $C$ ) this theorem is sharp:

Theorem 2 (Mendel-Naor): There exists constant $C'$ and a family of metric spaces $\{ X_\alpha \ | \ \alpha \in \mathbb{R}^+ \}$ such that for any small $\varepsilon$ , no subset of $X_\alpha$ with dimension $\geq (1-\varepsilon)\alpha$ embeds into Hilbert space with distorsion $\leq C'/\varepsilon$ .

This construction makes use of our all-time favorite: expander graphs! (see pervious post for definitions)

So what if $D$ is small? Turns out, unlike in the linear case when $D<2$ , there is no $\alpha(\kappa, D)$ , in the paper they also produced spaces $X_\alpha$ for each $\alpha$ where the only subset that embeds with distorsion < $2$ are of Hausdorff dimension 0!

In his words, the proof of theorem 1 (i.e. the paper) takes five hours to explain, hence I will not do that. But among many neat things appeared in the proof, instead of embedding into the Hilbert space directly they embedded it into an ultrametric space with distorsion $D$ , and then make use of the fact that any such space sits in the Hilbert space isometrically.

Definition: An ultrametric on space $X$ is a metric with the additional property that for any three points $x, y, z \in X$ , we have the so-called strong triangle inequality, i.e.

$d(x, y) \leq \max \{ d(x, z), d(y,z) \}$

If one pause and think a bit, this is a quite weird condition: for example, all triangles in an ultrametric space are isosceles with the two same length edge both longer than the third edge; every point is the center of the ball, etc.

Exercise: Come up with an example of an ultrametric that’s not the discrete metric, on an infinite space.

Not so easy, hum? My guess: the first one you came up with is the space of all words in 2-element alphabet $\Sigma_2$ , with the dictionary metric (two points are distance $2^{-n}$ apart where $n$ is the first digit they differ), right?

In fact in some sense all ultrametrics look like that. (i.e. they are represented by an infinite tree with weights assigned to vertices, in the above case a 2-regular tree with equal weights on same level) Topologically our $\Sigma_2$ is a Cantor set and sits isometrically in $l_2$ . It’s not hard to see in fact all such space embeds isometrically in $l_2$ .

I just want to say that this operation of first construct an ultrametric space according to our given metric space, embed, and then embed the ultrametric metric space into the Hilbert space somehow reminds me of when we want to construct a measure satisfying a certain property, we first construct it on a Cantor set, then divide up the space and use the values on parts of the Cantor set for parts of the space…On this vein the whole problem gets translated to producing a tree that gives the ultrametric and work with the tree (by no means simple, though).

Finally, let’s see a cute statement which can be proved by applying this result:

Urbanski’s conjecture: Any compact metric space of Hausdorff dimension > $n$ can be mapped surjectively [thanks to Tushar Das for pointing out the typo] onto the unit ball $B_1^n$ by a Lipschitz map.

(note strictly larger is important for our theorem to apply…since we need to subtract an $\varepsilon$ ) and hence another cute statement that’s still not known:

Question: Does any compact metric space with positive Hausdorff $n$ -dimensional measure maps Lipschitzly onto $B_1^n$ ?

A remark on a mini-course by Kleiner in Sullivan’s 70th birthday

June 7, 2011June 7, 2011 Conan2 Comments

I spent the last week on Long Island for Dennis Sullivan’s birthday conference. The conference is hosted in the brand new Simons center where great food is served everyday in the cafe (I think life-wise it’s a wonderful choice for doing a post-doc).

Anyways, aside from getting to know this super-cool person named Dennis, the talks there were interesting~ There are many things I found so exciting and can’t help to not say a few words about, however due to my laziness, I can only select one item to give a little stupid remark on:

So Bruce Kleiner gave a 3-lecture mini-course on boundaries of Gromov hyperbolic spaces (see this related post on a piece of his pervious work in the subject)

Cannon’s conjecture: Any Gromov hyperbolic group with $\partial_\infty G \approx \mathbb{S}^2$ acts discretely and cocompactly by isometries on $\mathbb{H}^3$ .

As we all know, in the theory of Gromov hyperbolic spaces, we have the basic theorem that says if a groups acts on a space discretely and cocompactly by isometries, then the group (equipped with any word metric on its Cayley graph) is quasi-isometric to the space it acts on.

Since I borrowed professor Sullivan as an excuse for writing this post, let’s also state a partial converse of this theorem (which is more in the line of Cannon’s conjecture):

Theorem: (Sullivan, Gromov, Cannon-Swenson)
For $G$ finitely generated, if $G$ is quasi-isometric to $\mathbb{H}^n$ for some $n \geq 3$ , then $G$ acts on $\mathbb{H}^n$ discretely cocompactly by isometries.

This essentially says that due to the strong symmetries and hyperbolicity of $\mathbb{H}^n$ , in this case quasi-isometry is enough to guarantee an action. (Such thing is of course not true in general, for example any finite group is quasi-isometric to any compact metric space, there’s no way such action exists.) In some sense being quasi-isometric is a much stronger condition once the spaces has large growth at infinity.

In light of the above two theorems we know that Cannon’s conjecture is equivalent to saying that any hyperbolic group with boundary $\mathbb{S}^2$ is quasi-isometric to $\mathbb{H}^3$ .

At first glance this seems striking since knowing only the topology of the boundary and the fact that it’s hyperbolic, we need to conclude what the whole group looks like geometrically. However, the pervious post on one dimensional boundaries perhaps gives us some hint on the boundary can’t be anything we want. In fact it’s rather rigid due to the large symmetries of our hyperbolic group structure.

Having Cannon’s conjecture as a Holy Grail, they developed tools that give raise to some very elegant and inspring proofs of the conjecture in various special cases. For example:

Definition: A metric space $M$ , is said to be Alfors $\alpha$ -regular where $\alpha$ is its Hausdorff dimension, if there exists constant $C$ s.t. for any ball $B(p, R)$ with $R \leq \mbox{Diam}(M)$ , we have:

$C^{-1}R^\alpha \leq \mu(B(p,R)) \leq C R^\alpha$

This is saying it’s of Hausdorff dimension $\alpha$ in a very strong sense. (i.e. the Hausdorff $\alpha$ measure behaves exactly like the regular Eculidean measure everywhere and in all scales).

For two disjoint continua $C_1, C_2$ in $M$ , let $\Gamma(C_1, C_2)$ denote the set of rectifiable curves connecting $C_1$ to $C_2$ . For any density function $\rho: M \rightarrow \mathbb{R}^+$ , we define the $\rho$ -distance between $C_1, C_2$ to be $\displaystyle \mbox{dist}_\rho(C_1, C_2) = \inf_{\gamma \in \Gamma(C_1, C_2)} \int_\gamma \rho$ .

Definition: The $\alpha$ -modulus between $C_1, C_2$ is

$\mbox{Mod}_\alpha(C_1, C_2) = \inf \{ \int_M \rho^\alpha \ | \ \mbox{dist}_\rho(C_1, C_2) \geq 1 \}$ ,

OK…I know this is a lot of seemingly random definitions to digest, let’s pause a little bit: Given two continua in our favorite $\mathbb{R}^n$ , new we are of course Hausdorff dimension $n$ , what’s the $n$ -modulus between them?

This is equivalent to asking for a density function for scaling the metric so that the total n-dimensional volume of $\mathbb{R}^n$ is as small as possible but yet the length of any curve connecting $C_1, \ C_2$ is larger than $1$ .

So intuitively we want to put large density between the sets whenever they are close together. Since we are integrating the $n$ -th power for volume (suppose $n>1$ , since our set is path connected it’s dimension is at least 1), we would want the density as ‘spread out’ as possible while keeping the arc-length property. Hence one observation is this modulus depends on the pair of closest points and the diameter of the sets.

The relative distance between $C_1, C_2$ is $\displaystyle \Delta (C_1, C_2) = \frac{\inf \{ d(p_1, p_2) \ | \ p_1 \in C_1, \ p_2 \in C_2 \} }{ \min \{ \mbox{Diam}(C_1), \mbox{Diam}(C_2) \} }$

We say $M$ is $\alpha$ -Loewner if the $\alpha$ modulus between any two continua is controlled above and below by their relative distance, i.e. there exists increasing functions $\phi, \psi: [0, \infty) \rightarrow [0, \infty)$ s.t. for all $C_1, C_2$ ,

$\phi(\Delta(C_1, C_2)) \leq \mbox{Mod}_\alpha(C_1, C_2) \leq \psi(\Delta(C_1, C_2))$

Those spaces are, in some sense, regular with respect to it’s metric and measure.

Theorem: If $\partial_\infty G$ is Alfors 2-regular and 2-Loewner, homeomorphic to $\mathbb{S}^2$ , then $G$ acts discrete cocompactly on $\mathbb{H}^3$ by isometries.

Most of the material appeared in the talk can be found in their paper.

There are many other talks I found very interesting, especially that of Kenneth Bromberg, Mario Bonk and Peter Jones. Unfortunately I had to miss Curt McMullen, Yair Minski and Shishikura…

Coding Fractals by trees

November 15, 2010November 19, 2010 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.

Hausdorff dimension of projections

March 30, 2010March 31, 2010 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

October 23, 2009March 3, 2010 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 \}$