## Ultrametrics and the nonlinear Dvoretzky problem

September 19, 2011

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

### 5 Responses to “Ultrametrics and the nonlinear Dvoretzky problem”

1. tushar Says:

Nice post Conan :-) I’m still wondering how the Naor-Mendel results imply Urbanski’s conjecture… any ideas?

2. tushar Says:

In this vein, and hopefully to provide some perspective, recall the original conjecture made by Miklós Laczkovich:

Given a set E ⊂ R^n of positive Lebesgue measure, is there a Lipschitz function f : R^n → R^n that maps E onto a ball?

This has been open for many years now! I first heard about it in 2007 (from the horse’s mouth) at a birthday celebration for David Preiss in Warwick – fun times :-)

Note the solution of Laczkovich in 2 dimensions via the theorem of Uy (this is an observation due to Peter Jones):

For every compact set E ⊂ R^2 of positive Lebesgue measure there is a non-constant complex-valued Lipschitz function that is holomorphic everywhere outside E (including infinity).

N.X. Uy
Removable sets of analytic functions satisfying a Lipschitz condition.
Ark. Mat., 17 (1979), 19–27.

However, Laczkovich’s conjecture remains open in dimensions 3 and greater…

http://www.dm.unipi.it/~alberti/files/ricerca/2010-12/acp-icm2010-rdc.pdf

Giovanni Alberti, Marianna Cs\”ornyei, David Preiss
Differentiability of Lipschitz functions, structure of null sets, and other problems.
Proceedings of the International Congress of Mathematicians Hyderabad, India, 2010.

…where I’ve liberally stolen from!

• 777 Says:

Cool! In fact that ICM talk you mentioned was one of my favorite in the whole conference! (I even made a comment on that in my ICM remark post here)

It great that you told me this! because last night I was trying to prove that Urbanski thing by starting with ’embed into the Hilbert space, then project to the first N coordinates, since it has dimension >n so the projection would still have dimension >n, hence has infinite n-dimensional measure’

Well, this clearly isn’t how it should be applied since otherwise I’ll be proving this open problem you mentioned >.< (I imagine infinite n-dimensional measure doesn't help much more than positive measure…)

I'll look into that some more~

Thanks again!

3. tushar Says:

here it is:

http://arxiv.org/abs/1203.0686

Tamás Keleti, András Máthé, Ondřej Zindulka
Hausdorff dimension of metric spaces and Lipschitz maps onto cubes,

note that this uses Theorem 1 above.

http://arxiv.org/abs/1106.0879

Manor Mendel, Assaf Naor
Ultrametric subsets with large Hausdorff dimension

this is also linked above via assaf’s webpage. a nice sketch of the K-M-Z argument has recently been added in section 1.3.1

4. The travelling salesman problem « Area 777 Says:

[…] Ultrametrics and the nonlinear Dvoretzky problem […]