## Posts Tagged ‘metric geometry’

### The travelling salesman problem

March 19, 2012

This is one of those items I should have written about long ago: I first heard about it over a lunch chat with professor Guth; then I was in not one, but two different talks on it, both by Peter Jones; and now, finally, after it appeared in this algorithms lecture by Sanjeev Arora I happen to be in, I decided to actually write the post. Anyways, it seem to live everywhere around my world, hence it’s probably a good idea for me to look more into it.

Has everyone experienced those annoy salesman who keeps knocking on you and your neighbors’ doors? One of their wonderful properties is that they won’t stop before they have reached every single household in the area. When you think about it, in fact this is not so straight foreword to do; i.e. one might need to travel a long way to make sure each house is reached.

Problem: Given $N$ points in $\mathbb{R}^2$, what’s the shortest path that goes through each point?

Since this started as an computational complexity problem (although in fact I learned the analysts’s version first), I will mainly focus on the CS version.

Trivial observations:

In total there are about $N!$ paths, hence the naive approach of computing all their lengths and find the minimum takes more than $N! \sim (N/e)^N$ time. (which is a long time)

This can be easily improved by a standard divide and concur:

Let $V \subseteq \mathbb{R}^2$ be our set of points. For each subset $S \subseteq V$, for each $p_1, p_2 \in S$, let $F(S, p_1, p_2) =$ length of shortest path from $p_1$ to $p_2$ going through all points in $S$.

Now the value of this $F$ can be computed recursively:

$\forall |S| = 2$, $F(S, p_1, p_2) = d(p_1, p_2)$;

Otherwise $F(S, p_1, p_2) =$

$\min \{ F(S \backslash \{p_2\}, p_1, q) + d(q, p_2) \ | \ q \in S, q \neq p_1, p_2 \}$

What we need is minimum of $F(V, p_1, p_2)$ where $p_1, p_2 \in V$. There are $2^N$ subsets of $V$, for any subset there are $\leq N$ choices for each of $p_1, p_2$. $F(S, p_1, p_2)$ is a minimum of $N$ numbers, hence $O(N)$ time (as was mentioned in this pervious post for selection algorithm). Summing that up, the running time is $2^N\times N^2\times N \sim O(2^N)$, slightly better than the most naive way.

Can we make it polynomial time? No. It’s well known that this problem is NP-hard, this is explained well in the wikipedia page for the problem.

Well, what can we do now? Thanks to Arora (2003), we can do an approximate version in polynomial time. I will try to point out a few interesting ideas from that paper. The process involved in this reminded me of the earlier post on nonlinear Dvoretzky problem (it’s a little embracing that I didn’t realize Sanjeev Arora was one of the co-authors of the Dvoretzky paper until I checked back on that post today! >.< ) it turns out they have this whole program about ‘softening’ classic problems and produce approximate versions.

Approximate version: Given $N$ points in $\mathbb{R}^2$, $\forall \varepsilon > 0$, find a path $\gamma$ through each point such that length $l(\gamma) < (1+\varepsilon)l(\mbox{Opt})$.

Of course we shall expect the running time $T$ to be a function of $\varepsilon$ and $N$, as $\varepsilon \rightarrow 0$ it shall blow up (to at least exponential in $N$, in fact as we shall see below, it will blow up to infinity).

The above is what I would hope is proved to be polynomial. In reality, what Arora did was one step more relaxed, namely a polynomial time randomized approximate algorithm. i.e. Given $V$ and $\varepsilon$, the algorithm produces a path $\gamma$ such that $E(l(\gamma)-l(\mbox{Opt}) < \varepsilon)$. In particular this means more than half the time the route is within $(1+\varepsilon)$ to the optimum.

Theorem (Arora ’03): $T(N, \varepsilon) \sim O(N^{1/\varepsilon})$ for the randomized approximate algorithm.

Later in that paper he improved the bound to $O(N \varepsilon^{C/\varepsilon}+N\log{N})$, which remains the best know bound to date.

Selected highlights of proof:

One of the great features in the approximating world is that, we don’t care if there are a million points that’s extremely close together — we can simply merge them to one point!

More precisely, since we are allowing a multiplicative error of $\varepsilon$, we also have trivial bound $l(\mbox{Opt}) > \mbox{ diam}(V)$, Hence the length can be increased by at least $\varepsilon \mbox{diam}(V)$ which means if we move each point by a distance no more than $\varepsilon \mbox{diam}(V) / (4N)$ and produce a path $\gamma'$ connecting the new points with $l(\gamma')< (1+\varepsilon/2)l(\mbox{Opt})$, then we can simply get our desired $\gamma$ from $\gamma'$, as shown:

i.e. the problem is “pixelated”: we may bound $V$ in a square box with side length $\mbox{diam}(V)$, divide each side into $8N/\varepsilon$ equal pieces and assume all points are in the center of the gird cell it lies in (for convenience later in the proof we will assume $8N/\varepsilon = 2^k$ is a power of $2$, rescale the structure so that each cell has side length $1$. Now the side length of the box is $8N/\varepsilon = 2^k$):

Now we do this so-called quadtree construction to separate the points (reminds me of Whitney’s original proof of his extension theorem, or the diatic squares proof of open sets being countable) i.e. bound $V$ in a square box and keep dividing squares into four smaller ones until no cell contains more than one point.

In our case, we need to randomize the quad tree: First we bound $V$ in a box that’s 4 times as large as our grid box (i.e. of side length $2^{k+1}$), shift the larger box by a random vector $(-i/2^k,-j/2^k)$ and then apply the quad tree construction to the larger box:

At this point you may wonder (at least I did) why do we need to pass to a larger square and randomize? From what I can see, doing this is to get

Fact: Now when we pick a grid line at random, the probability of it being an $i$th level dividing line is $2^i/2^k = 2^{i-k}$.

Keep this in mind.

Note that each site point is now uniquely defined as an intersection of no more than $k$ nesting squares, hence the total number of squares (in all levels) in this quad tree cannot exceed $N \times k \sim N \times \log{N/\varepsilon}$.

Moving on, the idea for the next step is to perturb any path to a path that cross the sides of the square at some specified finite set of possible “crossing points”. Let $m$ be the unique number such that $2^m \in [(\log N)/\varepsilon, 2 (\log N)/ \varepsilon ]$ (will see this is the best $m$ to choose). Divide sides of each square in our quad tree into $2^m$ equal segments:

Note: When two squares of different sizes meet, since the number of equally squares points is a power of $2$, the portals of the larger square are also portals of the smaller one.

With some simple topology (! finally something within my comfort zone :-P) we may assume the shortest portal-respecting path crosses each portal at most twice:

In each square, we run through all possible crossing portals and evaluate the shortest possible path that passes through all sites inside the square and enters and exists at the specified nodes. There are $(2^{4 \times 2^m})^2 \sim ($side length$)^2 \sim (N/\varepsilon)^2$ possible entering-exiting configurations, each taking polynomial time in $N$ (in fact $\sim N^{O(1/\varepsilon)}$ time) to figure out the minimum.

Once all subsquares has their all paths evaluated, we may move to the one-level larger square and spend another $\log(N/\varepsilon) \times (N/\varepsilon)^2$ operations. In total we have

$N \times \log{N/\varepsilon} \times (N/\varepsilon)^2 \times N^{O(1/\varepsilon)}$

$\sim N^{O(1/\varepsilon)}$

which is indeed polynomial in $N/\varepsilon$ many operations.

The randomization comes in because the route produced by the above polynomial time algorithm is not always approximately the optimum path; it turns out that sometimes it can be a lot longer.

Expectation of the difference between our random portal respecting minimum path $\mbox{OPT}_p$ and the actual minimum $\mbox{OPT}$ is bounded simply by the fact that minimum path cannot cross the grid lines more that $\mbox{OPT}$ times. At each crossing, the edge it crosses is at level $i$ with probability $2^{i-k}$. to perturb a level $i$ intersection to a portal respecting one requires adding an extra length of no more than $2 \times 2^{k-i}/2^m \sim 2^{k+1-i}/(\log N / \varepsilon)$:

$\displaystyle \mathbb{E}_{a,b}(\mbox{OPT}_p - \mbox{OPT})$

$\leq \mbox{OPT} \times \sum_{i=1}^k 2^{i-k} \times 2^{k+1-i} / (\log N / \varepsilon)$

$= \mbox{OPT} \times 2 \varepsilon / \log N < \varepsilon \mbox{OPT}$

P.S. You may find images for this post being a little different from pervious ones, that’s because I recently got myself a new iPad and all images above are done using iDraw, still getting used to it, so far it’s quite pleasant!

Bonus: I also started to paint on iPad~

–Firestone library, Princeton. (Beautiful spring weather to sit outside and paint from life!)

### Stable isoperimetric inequality

October 10, 2011

Eric Carlen from Rutgers gave a colloquium last week in which he bought up some curious questions and facts regarding the ‘stability’ of standard geometric inequalities such as the isoperimetric and Brunn-Minkowski inequality. To prevent myself from forgetting it, I’m dropping a short note on this matter here. Interestingly I was unable to locate any reference to this nor did I take any notes, hence this post is completely based on my recollection of a lunch five days ago.

–Many thanks to Marco Barchies, serval very high-quality references are located now. It turns out that starting with Fusco-Maggi-Pratelli ’06  which contains a full proof of the sharp bound, there has been a collective progress on shorter/different proofs and variations of the theorem made. See comments below!

As we all know, for sets in $\mathbb{R}^n$, the isoperimetric inequality is sharp only when the set is a round ball. Now what if it’s ‘almost sharp’? Do we always have to have a set that’s ‘close’ to a round sphere? What’s the appropriate sense of ‘closeness’ to use?

One might first attempt to use the Hausdorff distance:

$D(S, B_1(\bar{0})) = \inf_{t \in \mathbb{R}^n}\{D_H(S+t, B_1(\bar{0}))$.

However, we can easily see that, in dimension $3$ or higher, a ball of radius slightly small than $1$ with a long and thin finger sticking out would have volume $1$, surface volume $\varepsilon$ larger than that of the unit ball, but huge Hausdorff distance:

In the plane, however it’s a classical theorem that any region $S$ of area $\pi$ and perimeter $m_1(\partial S) \leq 2\pi +\varepsilon$ as $D(S, B_1(\bar{0})) \leq f(\varepsilon)$ where $f(\varepsilon) \rightarrow 0$ as $\varepsilon \rightarrow 0$ (well, that $f$ is because I forgot the exact bound, but should be linear in $\varepsilon$).

So what distance should we consider in higher dimensions? Turns out the nature thing is the $L^1$ norm:

$D(S, B_1(\bar{0})) = \inf_{t\in \mathbb{R}^n} \mbox{vol}((S+t)\Delta B_1(\bar{0}))$

where $\Delta$ is the symmetric difference.

First we can see that this clearly solves our problem with the thin finger:

To simplify notation, let’s normalize our set $S \subseteq \mathbb{R}^n$ to have volume 1. Let $B_n$ denote the ball with n-dimensional volume 1 in $\mathbb{R}^n$ (note: not the unit ball). $p_n = \mbox{vol}_{n-1}(\partial B_n)$ be the ($n-1$ dimensional) measure of the boundary of $B_n$.

Now we have a relation $D(S, B_n)^2 \leq C_n (\mbox{vol}_{n-1}(\partial S) - p_n)$

As said in the talk (and I can’t find any source to verify), there was a result in the 90’s that $D(S, B_n)^4 \leq C_n (\mbox{vol}_{n-1}(\partial S) - p_n)$ and the square one is fairly recent. The sharp constant $C_n$ is still unknown (not that I care much about the actual constant).

At the first glance I find the square quite curious (I thought it should depend on the dimension maybe like $n/(n-1)$ or something, since we are comparing some n-dimensional volume with (n-1) dimensional volume), let’s see why we should expect square here:

Take the simplest case, if we have a n-dimensional unit cube $C_n$, how does the left and right hand side change when we perturbe it to a rectangle with small eccentricity?

As we can see, $D(R_\varepsilon, C_n)$ is roughly $p_n \varepsilon$. The new boundary consists of two faces with measure $1+\varepsilon$, two faces of measure $1-\varepsilon$ and $2 \times (n-2)$ faces with volume $1-\epsilon^2$. Hence the linear term cancels out and we are left with a change in the order of $\varepsilon^2$! (well, actually to keep the volume 1, we need to have $1-\varepsilon/(1+\varepsilon)$ instead of $1-\varepsilon$, but it would still give $\varepsilon^2$)

It’s not hard to see that ellipses with small eccentricity behaves like rectangles.

Hence the square here is actually sharp. One can check that no matter how many of the $n$ side-length you perturbe, as long as the volume stay the same (up to $O(\varepsilon^2)$) the linear term of the change in boundary measure always cancels out.

There is an analoge of this stability theorem for the Brunn-Minkowski inequality, i.e. Given two sets of volume $V_1, V_2$, if the sum set has volume only a little bit larger than that of two round balls with those volumes, are the sets $L^1$ close to round balls? I believe it’s said this is only known under some restrictions on the sets (such as convex), which is strange to me since non-convex sets would only make the inequality worse (meaning the sum set has larger volume), don’t they?

I just can’t think of what could possibly go wrong for non-convex sets…(Really hope to find some reference on that!)

Anyways, speaking of sum sets, the following question recently caught my imagination (pointed out to me by Percy Wong, thank him~ and I shall quote him ‘this might sound like probability, but it’s really geometry!’):

Given a set $T \subseteq l^2$ (or $\mathbb{R}^n$), we define two quantities:

$G(T)=\mathbb{E}(\sup_{p \in T} \Sigma p_i g_i)$ and

$B(T) = \mathbb{E}(\sup_{p \in T} \Sigma p_i \epsilon_i)$

where $\mathbb{E}$ is the expected value, $\{g_i\}$ are independent random variables with a standard normal distribution (mean 0, variance 1) and $\{\epsilon_i\}$ are independent Bernoulli random variables.

Question: Given any $T$, can we always find $T'$ such that

$T \subseteq T' + B_{l^1}(\bar{0}, c B(T))$ and

$G(T') \leq c B(T)$

To find out more about the question, see Chapter 4 of this book. By the way, I should mention that there is a $5000 prize for this :-P ### 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$? ### A remark on a mini-course by Kleiner in Sullivan’s 70th birthday June 7, 2011 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… ### Stabilization of Heegaard splittings May 9, 2011 In the last lecture of a course on Heegaard splittings, professor Gabai sketched an example due to Hass-Thompson-Thurston of two genus $g$ Heegaard splittings of a $3$-manifold that requires at least $g$ stabilization to make them equivalent. The argument is, in my opinion, very metric-geometric. The connection is so striking (to me) so that I feel necessary to give a brief sketch of it here. (Side note: This has been a wonderful class! Although I constantly ask stupid questions and appear to be confused from time to time. But in fact it has been very interesting! I should have talked more about it on this blog…Oh well~) The following note is mostly based on professor Gabai’s lecture, I looked up some details in the original paper ( Hass-Thompson-Thurston ’09 ). Recall: (well, I understand that I have not talked about Heegaard splittings and stabilizations here before, hence I’ll *try to* give a one minute definition) A Heegaard splitting of a 3-manifold $M$ is a decomposition of the manifold as a union of two handlebodies intersecting at the boundary surface. The genus of the Heegaard splitting is the genus of the boundary surface. All smooth closed 3-manifolds has Heegaard splitting due the mere existence of a triangulation ( by thicken the 1-skeleton of the triangulation one gets a handlebody perhaps of huge genus, it’s easy exercise to see its complement is also a handlebody). However it is of interest to find what’s the minimal genus of a Heegaard splitting of a given manifold. Two Heegaard splittings are said to be equivlent if there is an isotopy of the manifold sending one splitting to the other (with boundary gluing map commuting, of course). A stabilization of a Heegaard splitting $(H_1, H_2, S)$ is a surgery on $S$ that adds genus (i.e. cut out two discs in $S$ and glue in a handle). Stabilization will increase the genus of the splitting by $1$) Let $M$ be any closed hyperbolic $3$-manifold that fibres over the circle. (i.e. $M$ is $F_g \times [0,1]$ with the two ends identified by some diffeomorphism $f: F_g \rightarrow F_g$, $g\geq 2$): Let $M'_k$ be the $k$ fold cover of $M$ along $S^1$ (i.e. glue together$k$copies of $F_g \times I$ all via the map $f$: Let $M_k$ be the manifold obtained by cut open $M'_k$ along$F_g\$ and glue in two handlebodies $H_1, H_2$ at the ends:

Since $M$ is hyperbolic, $M'_k$ is hyperbolic. In fact, for any $\varepsilon > 0$ we can choose a large enough $k$ so that $M_k$ can be equipped with a metric having curvature bounded between $1-\varepsilon$ and $1+\varepsilon$ everywhere.

( I’m obviously no in this, however, intuitively it’s believable because once the hyperbolic part $M'_k$ is super large, one should be able to make the metric in $M'_k$ slightly less hyperbolic to make room for fitting in an almost hyperbolic metric at the ends $H_1, H_2$). For details on this please refer to the original paper. :-P

Now there comes our Heegaard splittings of $M_k$!

Let $k = 2n$, let $H_L$ be the union of handlebody $H_1$ together with the first $n$ copies of $M$, $H_R$ be $H_2$ with the last $n$ copies of $M$. $H_L, H_R$ are genus $g$ handlebodies shearing a common surface $S$ in the ‘middle’ of $M_k$:

Claim: The Heegaard splitting $\mathcal{H}_1 = H_L \cup H_R$ and $\mathcal{H}_2 = H_L \cup H_R$ cannot be made equivalent by less than $g$ stabilizations.

In other words, first of all one can not isotope this splitting upside down. Furthermore, adding handles make it easier to turn the new higher genus splitting upside down, but in this particular case we cannot get away with adding anything less than $g$ many handles.

Okay, not comes the punchline: How would one possible prove such thing? Well, as one might have imagined, why did we want to make this manifold close to hyperbolic? Yes, minimal surfaces!

Let’s see…Suppose we have a common stabilization of genus $2g-1$. That would mean that we can sweep through the manifold by a surface of genus (at most) $2g-1$, with $1$-skeletons at time $0, 1$.

Now comes what professor Gabai calls the ‘harmonic magic': there is a theorem similar to that of Pitts-Rubinstein

Ingredient #1: (roughly thm 6.1 from the paper) For manifolds with curvature close to $-1$ everywhere, for any given genus $g$ Heegaard splitting $\mathcal{H}$, one can isotope the sweep-out so that each surface in the sweep-out having area $< 5 \pi (g-1)$.

I do not know exactly how is this proved. The idea is perhaps try to shrink each surface to a ‘minimal surface’, perhaps creating some singularities harmless in the process.

The ides of the whole arguement is that if we can isotope the Heegaard splittings, we can isotope the whole sweep-out while making the time-$t$ sweep-out harmonic for each $t$. In particular, at each time there is (at least) a surface in the sweep-out family that divides the volume of $M'_n$ in half. Furthermore, the time 1 half-volume-surface is roughly same as the time 0 surface with two sides switched.

We shall see that the surfaces does not have enough genus or volume to do that. (As we can see, there is a family of genus $2g$ surface, all having volume less than some constant independent of $n$ that does this; Also if we have ni restriction on area, then even a genus $g$ surface can be turned.)

Ingredient #2: For any constant $K$, there is $n$ large enough so no surfaces of genus $ and area $ inside the middle fibred manifold with boundary $M'_n$ can divide the volume of $M'_n$ in half.

The prove of this is partially based on our all-time favorite: the isoperimetric inequality:

Each Riemannian metric $\lambda$ on a closed surface has a linear isoperimetric inequality for 1-chains bounding 2-chains, i.e. any homologically trivial 1-chain $c$ bounds a $2$ chain $z$ where

$\mbox{Vol}_2(z) \leq K_\lambda \mbox{Vol}_1(c)$.

Fitting things together:

Suppose there is (as described above) a family of genus $2g-1$ surfaces, each dividing the volume of $M_{2n}$ in half and flips the two sides of the surface as time goes from $0$ to $1$.

By ingredient #1, since the family is by construction surfaces from (different) sweep-outs by ‘minimal surfaces’, we have $\mbox{Vol}_2(S_t) < 5 \pi (2g-2)$ for all $t$.

Now if we take the two component separated by $S_t$ and intersect them with the left-most $n$ copies of $M$ in $M'_{2n}$ (call it $M'_L$), at some $t$, $S_t$ must also divide the volume of $M'_L$ in half.

Since $S_t$ divides both $M'_2n$ and $M'_L$ in half, it must do so also in $M'_R$.

But $S_t$ is of genus $2g-1$! So one of $S_t \cap M'_L$ and $S_t \cap M'_R$ has genus $< g$! (say it's $M'_L$)

Apply ingredient #2, take $K = 5 \pi (2g-2)$, there is $n$ large enough so that $S_t \cap M'_L$, which has area less than $K$ and genus less than $g$, cannot possibly divide $M'_L$ in half.

### A report of my Princeton generals exam

April 26, 2011

Well, some people might be wondering why I haven’t updated my blog since two weeks ago…Here’s the answer: I have been preparing for this generals exam — perhaps the last exam in my life.

For those who don’t know the game rules: The exam consists of 3 professors (proposed by the kid taking the exam, approved by the department), 5 topics (real, complex, algebra + 2 specialized topics chosen by the student). One of the committee member acts as the chair of the exam.

The exam consists of the three committee members sitting in the chair’s office, the student stands in front of the board. The professors ask questions ranging in those 5 topics for however long they want, the kid is in charge of explaining them on the board.

I was tortured for 4.5 hours (I guess it sets a new record?)
I have perhaps missed some questions in my recollection (it’s hard to remember all 4.5 hours of questions).

Conan Wu’s generals

Commitee: David Gabai (Chair), Larry Guth, John Mather

Topics: Metric Geometry, Dynamical Systems

Real analysis:

Mather: Construct a first category but full measure set.

(I gave the intersection of decreasing balls around the rationals)

Guth: $F:S^1 \rightarrow \mathbb{R}$ 1-Lipschitz, what can one say about its Fourier coefficients.

(Decreasing faster than $c*1/n$ via integration by parts)

Mather: Does integration by parts work for Lipschitz functions?

(Lip imply absolutely continuous then Lebesgue’s differentiation theorem)

Mather: If one only has bounded variation, what can we say?

($f(x) \geq f(0) + \int_0^x f'(t) dt$)

Mather: If $f:S^1 \rightarrow \mathbb{R}$ is smooth, what can you say about it’s Fourier coefficients?

(Prove it’s rapidly decreasing)

Mather: Given a smooth $g: S^1 \rightarrow \mathbb{R}$, given a $\alpha \in S^1$, when can you find a $f: S^1 \rightarrow \mathbb{R}$ such that
$g(\theta) = f(\theta+\alpha)-f(\theta)$ ?

(A necessary condition is the integral of $g$ needs to vanish,
I had to expand everything in Fourier coefficients, show that if $\hat{g}(n)$ is rapidly decreasing, compute the Diophantine set $\alpha$ should be in to guarantee $\hat{f}(n)$ being rapidly decreasing.

Gabai: Write down a smooth function from $f:\mathbb{R}^2 \rightarrow \mathbb{R}$ with no critical points.

(I wrote $f(x,y) = x+y$) Draw its level curves (straight lines parallel to $x=-y$)

Gabai: Can you find a such function with the level curves form a different foliation from this one?

(I think he meant that two foliations are different if there is no homeo on $\mathbb{R}^2$ carrying one to the other,
After playing around with it for a while, I came up with an example where the level sets form a Reeb foliation, and that’s not same as the lines!)

We moved on to complex.

Complex analysis:

Guth: Given a holomorphic $f:\mathbb{D} \rightarrow \mathbb{D}$, if $f$ has $50$ $0$s inside the ball $B_{1/3}(\bar{0})$, what can you say about $f(0)$?

(with a bunch of hints/suggestions, I finally got $f(0) \leq (1/2)^{50}$ — construct polynomial vanishing at those roots, quotient and maximal modulus)

Guth: State maximal modulus principal.

Gabai: Define the Mobius group and how does it act on $\mathbb{H}$.

Gabai: What do the Mobius group preserve?

(Poincare metric)

Mather: Write down the Poincare metric, what’s the distance from $\bar{0}$ to $1$? (infinity)

(I don’t remember the exact distance form, so I tried to guess the denominator being $\sqrt{1-|z|}$, but then integrating from $0$ to $1$ does not “barely diverge”. Turns out it should be $(1-|z|^2)^2$.)

Gabai: Suppose I have a finite subgroup with the group of Mobius transformations acting on $\mathbb{D}$, show it has a global fixed point.

(I sketched an argument based on each element having finite order must have a unique fixed point in the interior of $\mathbb{D}$, if two element has different fixed points, then one can construct a sequence of elements where the fixed point tends to the boundary, so the group can’t be finite.)

I think that’s pretty much all for the complex.

Algebra:

Gabai: State Eisenstein’s criteria

(I stated it with rings and prime ideals, which leaded to a small discussion about for which rings it work)

Gabai: State Sylow’s theorem

(It’s strange that after stating Sylow, he didn’t ask me do anything such as classify finite groups of order xx)

Gabai: What’s a Galois extension? State the fundamental theorem of Galois theory.

(Again, no computing Galois group…)

Gabai: Given a finite abelian group, if it has at most $n$ elements of order divisible by $n$, prove it’s cyclic.

(classification of abelian groups, induction, each Sylow is cyclic)

Gabai: Prove multiplicative group of a finite field is cyclic.

(It’s embarrassing that I was actually stuck on this for a little bit before being reminded of using the previous question)

Gabai: What’s $SL_2(\mathbb{Z})$? What are all possible orders of elements of it?

(I said linear automorphisms on the torus. I thought it can only be $1,2,4,\infty$, but turns out there is elements of order $6$. Then I had to draw the torus as a hexagon and so on…)

Gabai: What’s $\pi_3(S^2)$?

($\mathbb{Z}$, via Hopf fibration)

Gabai: For any closed orientable $n$-manifold $M$, why is $H_{n-1}(M)$ torsion free?

(Poincare duality + universal coefficient)

We then moved on to special topics:

Metric Geometry:

Guth: What’s the systolic inequality?

(the term ‘aspherical’ comes up)

Gabai: What’s aspherical? What if the manifold is unbounded?

(I guessed it still works if the manifold is unbounded, Guth ‘seem to’ agree)

Guth: Sketch a proof of the systolic inequality for the n-torus.

(I sketched Gromov’s proof via filling radius)

Guth: Give an isoperimetric inequality for filling loops in the 3-manifold $S^2 \times \mathbb{R}$ where $S^2$ has the round unit sphere metric.

(My guess is for any 2-chain we should have

$\mbox{vol}_1(\partial c) \geq C \mbox{vol}_2(c)$

then I tried to prove that using some kind of random cone and grid-pushing argument, but soon realized the method only prove

$\mbox{vol}_1(\partial c) \geq C \sqrt{\mbox{vol}_2(c)}$.)

Guth: Given two loops of length $L_1, L_2$, the distance between the closest points on two loops is $\geq 1$, what’s the maximum linking number?

(it can be as large as $c L_1 L_2$)

Dynamical Systems:

Mather: Define Anosov diffeomorphisms.

Mather: Prove the definition is independent of the metric.

(Then he asked what properties does Anosov have, I should have said stable/unstable manifolds, and ergodic if it’s more than $C^{1+\varepsilon}$…or anything I’m familiar with, for some reason the first word I pulled out was structurally stable…well then it leaded to and immediate question)

Mather: Prove structural stability of Anosov diffeomorphisms.

(This is quite long, so I proposed to prove Anosov that’s Lipschitz close to the linear one in $\mathbb{R}^n$ is structurally stable. i.e. the Hartman-Grobman Theorem, using Moser’s method, some details still missing)

Mather: Define Anosov flow, what can you say about geodesic flow for negatively curved manifold?

(They are Anosov, I tried to draw a picture to showing the stable and unstable and finished with some help)

Mather: Define rotation number, what can you say if rotation numbers are irrational?

(They are semi-conjugate to a rotation with a map that perhaps collapse some intervals to points.)

Mather: When are they actually conjugate to the irrational rotation?

(I said when $f$ is $C^2$, $C^1$ is not enough. Actually $C^1$ with derivative having bounded variation suffice)

I do not know why, but at this point he wanted me to talk about the fixed point problem of non-separating plane continua (which I once mentioned in his class).

After that they decided to set me free~ So I wandered in the hallway for a few minutes and the three of them came out to shake my hand.

### The Carnot-Carathéodory metric

March 22, 2011

I remember looking at Gromov’s notes “Carnot-Carathéodory spaces seen from within” a long time ago and didn’t get anywhere. Recently I encountered it again through professor Guth. This time, with his effort in explaining, I did get some ideas. This thing is indeed pretty cool~ So I decided to write an elementary introduction about it here. We will construct a such metric in $\mathbb{R}^3$.

In general, if we have a Riemannian manifold, the Riemannian distance between two given points $p, q$ is defined as

$\inf_\Gamma(p,q) \int_0^1||\gamma'(t)||dt$

where $\Gamma$ is the collection of all differentiable curves $\gamma$ connecting the two points.

However, if we have a lower dimensional sub-bundle $E(M)$ of the tangent bundle (depending continuously on the base point). We may attempt to define the metric

$d(p,q) = \inf_{\Gamma'} \int_0^1||\gamma'(t)||dt$

where $\Gamma'$ is the collection of curves connecting $p, q$ with $\gamma'(t) \in E(M)$ for all $t$. (i.e. we are only allowed to go along directions in the sub-bundle.

Now if we attempt to do this in $\mathbb{R}^3$, the first thing we may try is let the sub-bundle be the say, $xy$-plane at all points. It’s easy to realize that now we are ‘stuck’ in the same height: any two points with different $z$ coordinate will have no curve connecting them (hence the distance is infinite). The resulting metric space is real number many discrete copies of $\mathbb{R}^2$. Of course that’s no longer homeomorphic to $\mathbb{R}^3$.

Hence for the metric to be finite, we have to require accessibility of the sub-bundle: Any point is connected to any other point by a curve with derivatives in the $E(M)$.

For the metric to be equivalent to our original Riemannian metric (meaning generate the same topology), we need $E(M)$ to be locally accessible: Any point less than $\delta$ away from the original point $p$ can be connected to $p$ by a curve of length $< \varepsilon$ going along $E(M)$.

At the first glance the existence of a (non-trivial) such metric may not seem obvious. Let’s construct one on $\mathbb{R}^3$ that generates the same topology:

To start, we first identify our $\mathbb{R}^3$ with the $3 \times 3$ real entry Heisenberg group $H^3$ (all $3 \times 3$ upper triangular matrices with “1”s on the diagonal). i.e. we have homeomorphism

$h(x,y,z) \mapsto \left( \begin{array}{ccc} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{array} \right)$

Let $g$ be a left-invariant metric on $H_3$.

In the Lie algebra $T_e(H_3)$ (tangent space of the identity element), the elements $X = \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) , Y = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right)$ and $Z = \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right)$ form a basis.

At each point, we take the two dimensional sub-bundle $E(H_3)$ of the tangent bundle generated by infinitesimal left translations by $X, Y$. Since the metric $g$ is left invariant, we are free to restrict the metric to $E(M)$ i.e. we have $||X_p|| = ||Y_p|| = 1$ for each $p \in M$.

The interesting thing about $H_3$ is that all points are accessible from the origin via curves everywhere tangent to $E(H_3)$. In other words, any points can be obtained by left translating any other point by multiples of elements $X$ and $Y$.

The “unit grid” in $\mathbb{R}^3$ under this sub-Riemannian metric looks something like:

Since we have

$\left( \begin{array}{ccc} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) = \left( \begin{array}{ccc} 1 & x+1 & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{array} \right)$,

the original $x$-direction stay the same, i.e. a bunch of horizontal lines connecting the original $yz$ planes orthogonally.

However, if we look at a translation by $Y$, we have

$\left( \begin{array}{ccc} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right) = \left( \begin{array}{ccc} 1 & x & z+x \\ 0 & 1 & y+1 \\ 0 & 0 & 1 \end{array} \right)$

i.e. a unit length $Y$-vector not only add a $1$ to the $y$-direction but also adds a height $x$ to $z$, hence the grid of unit $Y$ vectors in the above three $yz$ planes look like:

We can now try to see the rough shape of balls by only allowing ourselves to go along the unit grid formed by $X$ and $Y$ lines constructed above. This corresponds to accessing all matrices with integer entry by words in $X$ and $Y$.

The first question to ask is perhaps how to go from $(0,0,0)$ to $(0,0,1)$. –since going along the $z$ axis is disabled. Observe that going through the following loop works:

We conclude that $d_C((0,0,0), (0,0,1)) \leq 4$ in fact up to a constant going along such loop gives the actual distance.

At this point one might feel that going along $z$ axis in the C-C metric is always takes longer than the ordinary distance. Giving it a bit more thought, we will find this is NOT the case: Imagine what happens if we want to go from $(0,0,0)$ to $(0,0,10000)$?

One way to do this is to go along $X$ for 100 steps, then along $Y$ for 100 steps (at this point each step in $Y$ will raise $100$ in $z$-coordinate, then $Y^{-100} X^{-100}$. This gives $d_C((0,0,0), (0,0,10000)) \leq 400$.

To illustrate, let’s first see the loop from $(0,0,0)$ to $(0,0,4)$:

The loop has length $8$. (A lot shorter compare to length $4$ for going $1$ unit in $z$-direction)

i.e. for large $Z$, it’s much more efficient to travel in the C-C metric. $d_C( (0,0,0), (0,0,N^2)) = 4N$

In fact, we can see the ball of radius $N$ is roughly an rectangle with dimension $R \times R \times R^2$ (meaning bounded from both inside and outside with a constant factor). Hence the volume of balls grow like $R^4$.

Balls are very “flat” when they are small and very “long” when they are large.

### Isoperimetric inequality on groups

February 28, 2011

Back in high school, we have all learned and loved the isoperimetric inequality: “If one wants to enclose a region of area $\pi$ on the plane, one needs a rope of length at least $2 \pi$.” or equivalently, given $U \subseteq \mathbb{R}^2$ bounded open, we always have

$\ell(\partial U) \geq 2 \sqrt{\pi} \sqrt{\mbox{Area}(U)}$

Of course this generalizes to $\mathbb{R}^n$:

Theorem: Given any open set $U \subseteq \mathbb{R}^n$, we have

$\mbox{vol}_{n-1}\partial (U) \geq n\cdot \omega_n^{1/n} \mbox{vol}_n(U)^{\frac{n-1}{n}}$

Here $\omega_n$ is the volume of the unit n-ball. Note that the inequality is sharp for balls in $\mathbb{R}^n$.

One nature question to ask should be: for which other kind of spaces do we have such an inequality. i.e. when can we lower bound the volume of the boundary by in terms of the volume of the open set? If such inequality exists, how does the lower bound depend on the volume of the set?

I recently learned to produce such bounds on groups:
Let $G$ be a discrete group, fix a set of generators and let $C_G$ be its Cayley graph, equipped with the word metric $d$.

Let $N(R) = |B_R(e)|$ be the cardinality of the ball of radius $R$ around the identity.

For any set $U \subseteq G$, we define $\partial U = \{g \in G \ | \ d(g, U) = 1 \}$ i.e. points that’s not in $U$ but there is an edge in the Cayley graph connecting it to some point in $U$.

Theorem:For any group with the property that $N(R) \geq c_n R^n$, then for any set $U \subseteq G$ with $|U| \leq \frac{1}{2}|G|$,

$|\partial U| \geq c_n |U|^{\frac{n-1}{n}}$.

i.e. If the volume of balls grow (w.r.t. radius) as fast as what we have in $\mathbb{R}^n$, then we can lower bound the size of boundary any open set in terms of its volume just like what we have in $\mathbb{R}^n$.

Proof: We make use of the fact that right multiplications by elements of the group are isometries on Cayley graph.

Let $R = (\frac{2}{c_n}|U|)^\frac{1}{n}$, so we have $|B_R(e)| \geq 2|U|$.

For each element $g \in B_R(e)$, we look at how many elements of $U$ went outside of $U$ i.e. $| Ug \backslash U|$. (Here the idea being the size of the boundary can be lower bounded in terms of the length of the translation vector and the volume shifted outside the set. Hence we are interested in finding an element that’s not too far away from the identity but shifts a large volume of $U$ outside of $U$.)

The average value of $|Ug \backslash U|$ as $g$ varies in the ball $B_R(e)$ is:

$\displaystyle \frac{1}{|B_R(e)|} \sum_{g\in B_R(e)} |Ug \backslash U|$

The sum part is counting the elements of $U$ that’s translated outside $U$ by $g$ then sum over all $g \in B_R(e)$, this is same as first fixing any $u \in U$, count how many $g$ sends $u$ outside $U$, and sum over all $u \in U$ ( In fact this is just Fubini, where we exchange the order of two summations ). “how mant $g \in B_R(e)$ sends $u$ outside of $U$” is merely $|uB_R(e) \backslash U|$.

Hence the average is

$\displaystyle \frac{1}{|B_R(e)|} \sum_{u\in U}|uB_R(e) \backslash U|$.

But we know $|B_R(e)| \geq 2 \cdot |U|$, hence $|uB_R(e) \backslash U|$ is at least $\frac{1}{2}|B_R(e)|$.

Hence

$\displaystyle \frac{1}{|B_R(e)|} \sum_{u\in U}|uB_R(e) \backslash U|$

$\geq \frac{1}{|B_R(e)|} \cdot |U| \cdot \frac{1}{2} |B_R(e)| = \frac{1}{2} |U|$

Now we can pick some $g \in B_R(e)$ where $|Ug \backslash U| \geq \frac{1}{2}|U|$ (at least as large as average).

Since $g$ has norm at most $R$, we can find a word $g_1 g_2 \cdots g_k = g, \ k \leq R$.

For any $ug \in (Ug \backslash U)$, since $u \in U$ and $ug \notin U$, there must be some $1\leq i\leq k$ s.t. $u(g_1\cdots g_{i-1}) \in U$ and $u(g_1\cdots g_i) \notin U$.

Hence $u g_1 \cdots g_i \in \partial U$, $ug \in \partial U \cdot g_{i+1} \cdots g_k$.

We deduce that $\displaystyle Ug \backslash U \subseteq \partial U \cup \partial U g_k \cup \cdots \cup \partial U g_2 \cdots g_k$ i.e. a union of $k$ copies of $\partial U$.

Hence $R |\partial U| \geq k |\partial U| \geq |Ug \backslash U| \geq \frac{1}{2}|U|$

$|\partial U| \geq \frac{|U|}{2R}$

Since $|B_R(e)| \geq c_n R^n$, we have $R \leq c_n |B_R(e)|^{\frac{1}{n}}$. $R = (\frac{2}{c_n}|U|)^\frac{1}{n} = c_n |U|^\frac{1}{n}$, hence we have

$|\partial U| \geq c_n |U|^\frac{n-1}{n}$

Establishes the claim.

Remark: The same argument carries through as long as we have a lower bound on the volume of balls, not necessarily polynomial. For example, on expander graphs, the volume of balls grow exponentially: $B_R(e) \geq c \cdot e^R$, then trancing through the argument we get bound

$|\partial U| \geq c \cdot \frac{|U|}{\log{|U|}}$

Which is a very strong isoperimetric inequality. However in fact the sharp bound for expanders is $|\partial U| \geq c \cdot |U|$. But to get that one needs to use more information of the expander than merely the volume of balls.

On the same vein, we can also prove a version on Lie groups:

Theorem:Let $G$ be a Lie group, $g$ be a left invariant metric on $G$. If $\mbox{vol}_n(B_R) \geq c_n R^n$ then for any open set $U$ with no more than half of the volume of $G$,

$\mbox{vol}_{n-1}(\partial U) \geq c_n \mbox{vol}_n(U)^\frac{n-1}{n}$.

Note that to satisfy the condition $\mbox{vol}_n(B_R) \geq c_n R^n$, our Lie group must be at least n-dimensional since if not the condition would fail for small balls. $n$ might be strictly larger than the dimension of the manifold depending on how ‘neigatively curved’ the manifold is in large scale.

Sketch of proof: As above, take a ball twice the size of the set $U$ around the identity, say it’s $B_R(e)$. Now we consider all left translates of the set $U$ by element in $B_R(e)$. In average an element shifts at least half of $U$ outside of $U$. Pick element $g$ where $\mbox{vol}(gU \backslash U)$ is above average.

Let $\gamma: [0, ||g||]$ be a unit speed geodesic connecting $e$ to $g$. Consider the union of left translates of $\partial U$ by elements in $\gamma([0, ||g||])$, this must contain all of $gU \backslash U$ since for any $gu \notin U$ the segment $\gamma([0,||g||]) \cdot u$ must cross the boundary of $U$, i.e. there is $c \in [0,||g||]$ where $\gamma(c) u \in \partial U$, hence

$g\cdot u = \gamma(||g||) \cdot u = \gamma(||g||-c)\gamma(c) u \in \gamma(||g||-c) \cdot \partial U$

But since the geodesic has derivative $1$, the n-dimensional volume of the union of those translates is at most $\mbox{vol}_{n-1}(\partial U) \cdot ||g||$.

We have $\mbox{vol}_{n-1}(\partial U) \cdot R \geq \mbox{vol}_n(gU \backslash U) \geq \mbox{vol}_n(U)/2$

Now since we have growth condition

$2\mbox{vol}_n(U) = \mbox{vol}_n(B_R) \geq c_n R^n$

i.e. $R \leq c_n \mbox{vol}_n(U)^\frac{1}{n}$.

Conbine the two inequalities we obtain

$\mbox{vol}_{n-1}(\partial U) \geq c_n \mbox{vol}_n(U)^\frac{n-1}{n}$.

Establishes the theorem.

Remark: In general, this argument produces a lower bound on the size of the boundary in terms of the volume of the set as long as:
1. There is a way to ‘continuously translate’ the set by elements in the space.
2. We have a lower bound on the growth of balls in terms of radius.

The key observation is that the translated set minus the original set is always contained in a ‘flattened cylinder’ of the boundary in direction of the translate, which then has volume controlled by the boundary size and the length of the translating element. Because of this, the constant is almost never strict as the difference (translate subtract original) can never be the whole cylinder (in case of a ball, this difference is a bit more than half of the cylinder).

### On Uryson widths

February 21, 2011

This is a note on parts of Gromov’s paper ‘width and related invariants of Riemannian manifolds’ (1988).

For a compact subset $C$ of $\mathbb{R}^n$, we define the k-codimensional width (or simply k-width) to be the smallest possible number $w$ where there exists a k-dimensional affine subspace $P_k \subseteq \mathbb{R}^n$ s.t. all points of $C$ is no more than $w$ away from $P_k$.

i.e.

$\displaystyle{W}_k(C) = \inf_{P_k \subseteq \mathbb{R}^n} \sup_{p\in C} \mbox{dist}(p, P_k)$
where $\mbox{dist}(p, P_k)$ is the length of the orthogonal segment from $p$ to $P_k$.

It’s easy to see that, for any $C$,

$\mathcal{W}_0(C) \geq \mathcal{W}_1(C) \geq \cdots \geq \mathcal{W}_n(C) = 0$.

At the first glance it may seems that $\mathcal{W}_0(C) = \frac{\mbox{diam}(C)}{2}$. However it is not the case since for example the equilateral triangle of side length $1$ in $\mathbb{R}^2$ has diameter $1$ but 0-width $\frac{1}{\sqrt{3}}$. In fact, by a theorem of Jung, this is indeed the optimum case, i.e. we have:

$\frac{1}{2}\mbox{diam}(C) \leq \mathcal{W}_0(C) \leq \sqrt{\frac{n}{2(n+1)}}\mbox{diam}(C)$

At this point one might wonder (at least I did), if we want to invent a notion that captures the ‘diameter’ after we ‘forget the longest k-dimensions’, a more direct way seem to be taking the smallest possible number $w'$ where there is an orthogonal projection of $C$ onto a $k$ dimensional subspace $P_k$ where any point $p \in P_k$ has pre-image with diameter $\leq w'$.

i.e.

$\displaystyle \widetilde{\mathcal{W}_k}(X) = \inf_{P_k \subseteq \mathbb{R}^n} \sup_{p \in P_k} \mbox{diam}(\pi^{-1}_{P_k}(p))$

Now we easily have $\mbox{diam}(C) = \widetilde{\mathcal{W}_0}(C) \geq \widetilde{\mathcal{W}_1}(C) \geq \cdots \geq \widetilde{\mathcal{W}_n}(C) = 0$.

However, the disadvantage of this notion is, for example, there is no reason for a semicircle arc to have 1-width 0 but a three-quarters circular arc having positive 1-width.

Since we are measuring how far is the set from being linear, taking convex hull should not make the set ‘wider’ $\widetilde{\mathcal{W}_k}$, unlike $\widetilde{\mathcal{W}_k}$ is not invariant under taking convex hulls. Note that for convex sets we do have

$\frac{1}{2}\widetilde{\mathcal{W}_k}(C) \leq \mathcal{W}_k(C) \leq \sqrt{\frac{n-k}{2(n-k+1)}}\widetilde{\mathcal{W}_k}(C)$

$\mathcal{W}_k(C) = 0$ iff $C$ is contained in a $k$-plane.

We now generalize this notion to general metric spaces:

Definition: The Uryson k-width of a compact metric space $M$ is the smallest number $w$ where there exists $k$ dimensional topological space $X$ and a continuous map $\pi: M \rightarrow X$ where any point $x \in X$ has pre-image with diameter $\leq w$.

i.e. $\displaystyle UW_k(M) = \inf \{ \ \sup_{x \in X} \mbox{diam}(\pi^{-1}(x)) \ |$

$\dim{X} = k, \pi:M \rightarrow X \ \mbox{is continuous} \}$

Note: Here dimension is the usual covering dimension for topological spaces: i.e. a topological space $X$ is $n$ dimensional if any finite cover of $X$ has a finite refinement s.t. no point of $X$ is contained in more than $n_1$ sets in the cover and $n$ is the smallest number with this property.

For compact subsets $C$ of $\mathbb{R}^n$ with induced metric, we obviously we have $UW_k(C) \leq \widetilde{\mathcal{W}_k}(C)$ since the pair $(P_k, \pi_{p_k})$ is clearly among the pairs we are minimizing over.

Speaking of topological dimensions, one of the classical results is the following:

Lebesgue’s lemma: Let $M=[0,1]^n$ be the solid n-dimensional cube, then for any topological space $X$ with $\dim(X) and any continuous map $p: M \rightarrow X$, we have image of at least one pair of opposite $(n-1)$-faces intersect.

Since the conclusion is purely topological, this applies equally well to rectangles. i.e. for $M = [0, L_1] \times [0, L_2] \times \cdots \times [0, L_n]$, $L_1 \geq L_2 \geq \cdots \geq L_n$, we have $UW_{n-1}(M) \geq L_n$; furthermore, $UW_k(M) \geq L_{k+1}$ for all $k$.

(If the later statement does not hold, we write $M$ as $M_1 \times M_2$, $M_1$ being the product of the first $(k+1)$ coordinates. Now $UW_k(M) \geq UW_k(M_1) \geq L_{k+1}$).

In light of the earlier post about minimax inequality, we should note that if we restrict $X$ to be a homeomorphic copy of $\mathbb{R}^k$ then the notion is the same as the minimax length of fibres. In particular as proved in the post the minimax length of the unit disc to $\mathbb{R}$ is 2.

Exercise: Check that for the unit $2$-disk, $UW_1(D^2) = \sqrt{3}$, i.e. the optimum is obtained by contracting the disc onto a triod.

Hence it can indeed be strictly smaller than merely taking $\mathbb{R}^k$ as the targeting space, even for simply connected sets. This gives a better measurement of ‘width’ in the sense that, for example, the $\varepsilon$ neighborhood of a tree will have $1-width$ about $2 \varepsilon$.

### Intergal geometry and the minimax inequality in a nutshell

February 7, 2011

The goal for most of the posts in this blog has been to take out some very simple parts of certain papers/subjects and “blow them up” to a point where anybody (myself included) can understand. Ideally the simple parts should give some inspirations and ideas towards the more general subject. This one is on the same vein. This one is based on parts of professor Guth’s minimax paper.

In an earlier post, we talked about the extremal length where one is able to bound the “largest possible minimum length” (i.e. the “maximum minimum length“) of a family of rectifiable curves under conformal transformation. When combined with the uniformization theorem in for surfaces, this becomes a powerful tool for understanding arbitrary Riemannian metrics (and for conformal classes of metrics in higher dimensions).

However, in ‘real life’ we often find what we really want to bound is, instead, the “minimum maximum length” of a family of curves, for example:

Question: Let $\mathbb{D} \subseteq \mathbb{R}^2$ be the unit disc. Given any family $\mathcal{F}$ of arcs with endpoints on $\partial \ \mathbb{D}$ and $\mathcal{F}$ foliates $\mathbb{D}$, then how short can the logest arc in $\mathcal{F}$ possibly be?

In other words, let $\mathbb{F}$ be the collection of all possible such foliations $\mathcal{F}$ as above, what is

$\displaystyle \inf_{\mathcal{F} \in \mathbb{F}} \ \sup_{A \in \mathcal{F}} \ \ell(A)$?

After playing around a little bit with those foliations, we should expect one of the fibres to be at least as long as the diameter ( i.e. no foliation has smaller maximum length leaf than foliating by straight lines ). Hence we should have

$\displaystyle \inf_{\mathcal{F} \in \mathbb{F}} \ \sup_{A \in \mathcal{F}} \ \ell(A) = 2$.

This is indeed easy to prove:

Proof: Consider the map $f: S^1 \rightarrow S^1$ where $S^1 = \partial \ \mathbb{D}$, $f$ switches the end-points of each arc in $\mathcal{F}$. It is easy to check that $f$ is a continuous, orientation reversing homeomorphism of the circle (conjugate to a reflection). Let $p, q$ be its fixed points, $L_1, L_2$ be the two arcs in $S^1$ connecting $p$ to $q$.

Let

$g: z \mapsto -z$

be the antipodal map on $S^1$.

Suppose $p \neq g(q)$ then one of $L_1, L_2$ is longer than $\pi$, say it’s $L_1$.

Then we have

$f \circ g (L_1) \subseteq L_1$.

Hence $f \circ g$ has a fixed point $m$ in $L_1$, i.e. $f(m) = -m$.

There is a fibre $A$ in $\mathcal{F}$ with endpoints $m, -m$, the fibre must have length

$\ell(A) \geq d(-m,m) = 2$.

The remaining case is trivial: if $p = g(q)$ then both $L_1$ and $L_2$ gets mapped into themselves orientation-reversingly, hence fixed points still exists.

Establishes the claim.

Instead of the disc, we may look at circles that sweep out the sphere (hence to avoid the end-point complications):

Theorem: Any one-parameter family of circles that foliates $S^2$ (except two points) must have the largest circle being longer than the equator.

This is merely applying the same argument, i.e. one of the circles needs to contain a pair of antipodal points hence must be longer than the equator.

In order for easier generalization to higher dimensions, with slight modifications, this can be formulated as:

Theorem: For any $f: T^2 \rightarrow S^2$ having non-zero degree, there is $\theta \in S^1$ where $\ell(f(S^1 \times \{ \theta \})$ is larger than the equator.

Hence in higher dimensions we can try to prove the same statement for largest image of a lever $k$-sphere under $f: S^k \times S^{n-k} \rightarrow S^n$. However before we do that I would like to highlight some intergal geometry machineries that are new to me but seemingly constantly used in proving those kinds of estimates. We shall get some idea of the method by showing:

Theorem: Let $\mathbb{R}P^n$ be equipped with the round metric. $p^k \subseteq \mathbb{R}P^n$ be a ‘flat’ $k$-dimensional plane. Then any $k$-chain $z^k \subseteq \mathbb{R}P^n$ in the same $k$ dimensional homology class as $p^k$ must have volume at least as large as $p^k$.

Proof: Let $Gr(\mathbb{R}P^n, n-k)$ be the set of all $(n-k)$-planes in $\mathbb{R}P^n$ (i.e. the Grassmannian).

There is a standard way to associate a measure $\mu$ on $Gr(\mathbb{R}P^n, n-k)$:

Let $\lambda$ be the Haar measure on $SO(n+1)$, fix some $Q \in Gr(\mathbb{R}P^n, n-k)$.

Since $SO(n+1)$ acts on $\mathbb{R}P^n$, for open set $S \subseteq Gr(\mathbb{R}P^n, n-k)$, we set

$\mu(S) = \lambda( \{ T \in SO(n+1) \ | \ T(Q) \in S \})$.

–The measure of a collection of planes is the measure of linear transformations that takes the given plane to an element of the set.

Now we are able to integrate over all $(n-k)$-planes!

For almost all $Q \in Gr(\mathbb{R}P^n, n-k)$, since $P$ is $k$-plane, we have $| Q \cap P | = 1$. ( not $1$ only when they are ‘parallel’ )

Since $[z] = [p]$ in $H_k(\mathbb{R}P^n, \mathbb{Z}_2)$, for almost all $Q$, $z$ intersects $Q$ at least as much as $P$ does. We conclude that for almost all $Q, \ | z \cap Q | \geq 1$.

Fact: There exists constant $C$ such that for any $k$-chain $\Sigma^k \in \mathbb{R}P^N$,

$\mbox{Vol}_k(\Sigma^k) = \mathbb{E}(|\Sigma \cap Q |)$.

The fact is obtained by diving the chain into fine cubes, observe that both volume and expectation are additive and translation invariant. Therefore we only need to show this for infinitesimal cubes (or balls) near $0$. We won’t work out the details here.

Hence in our case, since for almost all $Q$ we have $| z \cap Q | \geq 1$, the expectation $\mathbb{E}(|z \cap Q |) \geq 1$.

We therefore deduce

$\mbox{Vol}_k(z) = \mathbb{E}(|z \cap Q |) \geq 1$.

Establishes the theorem.

Remark: I found this intergal geometry method used here being very handy: in the old days I always try to give lower bounds on volume of stuff by intersecting it with planes and then pretend the ‘stuff’ were orthogonal to the plane, which is the worst case in terms of having small volume. An example of such bound can be found in the knot distorsion post where in order to lower bound the length we look at its intersection number with a family of parallel planes and then integrate the intersection.

This is like looking from one particular direction and record how many times did a curve go through each height, of course one would never get the exact length if we know the curve already. What if we are allowed to look from all directions?

I always wondered if we know the intersection number with not only a set of parallel planes but planes in all directions, then are there anything we can do to better bound the volume? Here I found the perfect answer to my question: by integrating over the Grassmannian, we are able to get the exact volume from how much it intersect each plane!

We get some systolic estimates as direct corollaries of the above theorem, for example:

Corollary: $\mbox{Sys}_1(\mathbb{R}P^2) = \sqrt{\pi/2}$ where $\mathbb{R}P^2$ carries the round metric with total volume $1$.

Back to our minimax problems, we state the higher dimensional version:

Wish: For any $C^1$ map $f: S^k \times S^{n-k} \rightarrow S^n$ where $S^n$ carries the standard round metric, there exists some $\theta \in S^{n-k}$ with

$\mbox{Vol}_k(f(S^k\times \{\theta\})) \geq \mbox{Vol}_k(E^k)$

where $E^k \subseteq S^n$ is the $k$-dimensional equator.

But what we have is that there is a (small) positive constant $c(n,k)$ s.t. $\mbox{deg}(f) \neq 0$ implies

$\displaystyle \sup_{\theta \in S^{n-k}} \mbox{Vol}_k(f(S^k \times \{\theta\})) \geq c(n,k) \mbox{Vol}_k(E^k)$

(shown by an inductive application of the isomperimetric inequality on $S^N$, which is obtained from applying intergal geometry methods)