Tag: Gromov

On Tao’s talk and the 3-dimensional Hilbert-Smith conjecture

Conan1 Comment

Last Wednesday Terry Tao briefly dropped by our little town and gave a colloquium. Surprisingly this is only the second time I hear him talking (the first one goes back to undergrad years in Toronto, he talked about arithmetic progressions of primes, unfortunately it came before I learned anything [such as those posts] about Szemeredi’s theorem). Thanks to the existence of blogs, feels like I knew him much better than that!

This time he talked about Hilbert’s 5th problem, Gromov’s polynomial growth theorem for discrete groups and their (Breuillard-Green-Tao) recently proved more general analogy of Gromov’s theorem for approximate groups. Since there’s no point for me to write 2nd-handed blog post while people can just read his own posts on this, I’ll just record a few points I personally found interesting (as a complete outsider) and moving on to state the more general Hilbert-Smith conjecture, very recently solved for 3-manifolds by John Pardon (who now graduated from Princeton and became a 1-st year grad student at Stanford, also appeared in this earlier post when he gave solution to Gromov’s knot distortion problem).

Warning: As many of you know I never take notes during talks, hence this is almost purely based on my vague recollection of a talk half a week ago, inaccuracy and mistakes are more than possible.

All topological groups in this post are locally compact.

Let’s get to math~ As we all know, a Lie group is a smooth manifold with a group structure where the multiplication and inversion are smooth self-diffeomorphisms. i.e. the object has:

1. a topological structure
2. a smooth structure
3. a group structure

It’s not too hard to observe that given a Lie group, if we ‘forget’ the smooth structure and just see it as a topological group which is a (topological) manifold, then we can uniquely re-construct the smooth structure from the group structure. From my understanding, this is mainly because given any element in the topological group we can find a unique homomorphism of the group \mathbb{R} into the manifold, sending 0 to identity and 1 to the element. resulting a class of curved through the identity, a.k.a the tangent space. Since the smooth structure is determined by the tangent space of the identity, all we need to know is how to ‘multiply’ two such parametrized curves.

The way to do that is to ‘zig-zag’:

Pick a small \varepsilon, take the image of \varepsilon under the two homomorphisms, alternatingly multiplying them to obtain a sequence of points in the topological group. As \varepsilon \rightarrow 0 the sequence becomes denser and converges to a curve.

The above shows that given a Lie group to start with, the smooth structure is uniquely determined by the topological group structure. Knowing this leads to the natural question:

Hilbert’s fifth problem: Is it true that any topological group which are (topological) manifolds admits a smooth structure compatible with group operations?

Side note: I had a little post-colloquium discussion with our fellow grad student Sam Lewallen, he asked:

Question: Is it possible for the same topological manifold to have two different Lie group structures where the induced smooth structures are different?

Note that neither the above nor Hilbert’s fifth problem shows such thing is impossible, since they both start with the phase ‘given a topological group’. My *guess* is this should be possible (so please let me know if you know the answer!) The first attempt might be trying to generate an exotic \mathbb{R}^4 from Lie group. Since the 3-dimensional Heisenberg group induces the standard (and unique) smooth structure on \mathbb{R}^3, I guess the 4-dimensional Heisenberg group won’t be exotic.

Anyways, so the Hilbert 5th problem was famously solved in the 50s by Montgomery-Zippin and Gleason, using set-theoretical methods (i.e. ultrafilters).

Gromov comes in later on and made the brilliant connection between (infinite) discrete groups and Lie groups. i.e. one see a discrete group as a metric space with word metric, ‘zoom out’ the space and produce a sequence of metric spaces, take the limit (Gromov-Hausdorff limit) and obtain a ‘continuous’ space. (which is ‘almost’ a Lie group in the sense that it’s an inverse limit of Lie groups.)

Hence he was able to adapt the machinery of Montgomery-Zippin to prove things about discrete groups:

Theorem: (Gromov) Any group with polynomial growth is virtually nilpotent.

Side note: I learned about this through the very detailed and well-presented course by Dave Gabai. (I thought I must have blogged about this, turns out I haven’t…)

The beauty of the theorem is (in my opinion) that we are given any discrete group, and all that’s known is how large the balls are (in fact, not even that, we know how large the large balls grow), yet the conclusion is all about the algebraic structure of the group. To learn more about Gromov’s work, see his paper. Although unrelated to the rest of this post, I shall also mention Bruce Kleiner’s paper where he proved Gromov’s theorem without using Hilbert’s 5th problem, instead he used space of harmonic maps on graphs.

Now we finally comes to a point of briefly mentioning the work of Tao et.al.! So they adopted Gromov’s methods of limiting and ‘ultra-filtering’ to apply to stuff that’s not even a whole discrete group: Since Gromov’s technique was to take the limit of a sequence of metric spaces which are zoomed out versions of balls in a group, but the Gromov-Hausdorff limit actually doesn’t care about the fact that those spaces are zoomed out from the same group, they may as well be just a family of subsets of groups with ‘bounded geometry’ of a certain kind.

Definition: An K-approximate group S is a (finite) subset of a group G where S\cdot S = \{ s_1 s_2 \ | \ s_1, s_2 \in S \} can be covered by K translates of S. i.e. there exists p_1, \cdots, p_K \in G where S \cdot S \subseteq \cup_{i=1}^k p_i \cdot S.

We shall be particularly interested in sequence of larger and larger sets (in cardinality) that are K-approximate groups with fixed K.

Examples:
Intervals [-N, N] \subseteq \mathbb{Z} are 2-approximate groups.

Balls of arbitrarily large radius in \mathbb{Z}^n are C \times 2^n approximate groups.

Balls of arbitrarily large radius in the 3-dimensional Heisenberg group are C \times 2^4 approximate groups. (For more about metric space properties of the Heisenberg group, see this post)

Just as in Gromov’s theorem, they started with any approximate group (a special case being sequence of balls in a group of polynomial growth), and concluded that they are in fact always essentially balls in Nilpotent groups. More precisely:

Theorem: (Breuillard-Green-Tao) Any K-approximate group S in G is covered by C(K) many translates of subgroup G_0 < G where G_0 has a finite (depending only on K) index nilpotent normal subgroup N.

With this theorem they were able to re-prove (see p71 of their paper) Cheeger-Colding’s result that

Theorem: Any closed n dimensional manifold with diameter 1 and Ricci curvature bounded below by a small negative number depending on n must have virtually nilpotent fundamental group.

Where Gromov’s theorem yields the same conclusion only for non-negative Ricci curvature.

Random thoughts:

1. Can Kleiner’s property T and harmonic maps machinery also be used to prove things about approximate groups?

2. The covering definition as we gave above in fact does not require approximate group S to be finite. Is there a Lie group version of the approximate groups? (i.e. we may take compact subsets of a Lie group where the self-product can be covered by K many translates of the set.) I wonder what conclusions can we expect for a family of non-discrete approximate groups.

As promised, I shall say a few words about the Hilbert-Smith conjecture and drop a note on the recent proof of it’s 3-dimensional case by Pardon.

From the solution of Hilbert’s fifth problem we know that any topological group that is a n-manifold is automatically equipped with a smooth structure compatible with group operations. What if we don’t know it’s a manifold? Well, of course then they don’t have to be a Lie group, for example the p-adic integer group \mathbb{Z}_p is homeomorphic to a Cantor set hence is not a Lie group. Hence it makes more sense to ask:

Hilbert-Smith conjecture: Any topological group acting faithfully on a connected n-manifold is a Lie group.

Recall an action is faithful if the homomorphism \varphi: G \rightarrow homeo(M) is injective.

As mentioned in Tao’s post, in fact \mathbb{Z}_p is the only possible bad case! i.e. it is sufficient to prove

Conjecture: \mathbb{Z}_p cannot act faithfully on a finite dimensional connected manifold.

The exciting new result of Pardon is that by adapting 3-manifold techniques (finding incompressible surfaces and induce homomorphism to mapping class groups) he was able to show:

Theorem: (Pardon ’12) There is no faithful action of \mathbb{Z}_p on any connected 3-manifolds.

And hence induce the Hilbert-Smith conjecture for dimension 3.

Discovering this result a few days ago has been quite exciting, I would hope to find time reading and blogging about that in more detail soon.

Graph of groups in relation to 3-manifolds

Conan5 Comments

(some images might appear soon)

Somehow I decided to wake up at 6:30 a.m. every Thursday to attend Bruce Kleiner‘s 9:30 course in NYU this semester. So far it’s been fun~

I learned about this thing called graph of groups. If you have been reading posts on this blog regarding any geometric group theory stuff (especially those posts related to Kleiner), then warning: this ‘graph’ has nothing to do with the Cayley graph. It’s not much about geometry but a rather ‘category-theoretical’ thing. Well, at this point you may think that you hate those algebra prople and is ready to leave…just don’t do that yet, because I hated them too, and now I finally got a tiny bit of understanding and appreciation on what those abstract non-sense was all about! :-P

So how do we connect cool 3-manifold stuff (incompressible surfaces, loops, embedded discs Heegaard splittings etc.) to groups?

Well, one handy thing is of course the Dehn’s lemma:

Theorem: For 3-manifold M with boundary, if the inclusion map i: \pi_1(\partial(M)) \rightarrow \pi_1(M) is not injective, then there exists a simple non-trivial loop in \partial M bounding an embedded disc in M.

Note: Dehn’s theorem was proved by Papakyriakopoulos, I talked about it in this pervious post, although not exactly stated in this form, we can see that Dehn’s lemma follows easily from the loop theorem.

This means we can say things about the 3-manifold by only looking solely at maps between groups!

That’s cool, but sometimes we find groups and just one map between two groups are not enough, and that’s when graph of groups comes in:

Definition: A graph of groups is a graph with vertice set V, edge set E, to each vertex v we associate a group G_v and to each edge e (say connecting v_1, v_2) we also associate a group G_e, together with a pair of injective homomorphisms f_1: G_e \rightarrow G_{v_1}, f_2: G_e \rightarrow G_{v_2}.

In our context, we should think of this as gluing together a bunch of spaces and take the fundamental group of those spaces, along with their pairwise intersections, as our vertice and edge groups. Just note that we need to have injections from the edge group to vertice groups. For simplicity one may first restrict oneself to the case where all edge groups are trivial (say spaces glued along contractible spaces).

There is something called the fundamental group of a graph of groups which is essentially the fundamental group of the resulting space after you glued spaces according to the given graph of groups. Note that the injection associated to edges takes into account how gluing of different pairs interact with each other (that is to say, for example, on a homotopy level it knows about triple intersections, etc.)

Let’s look at an application in this paper of Kleiner and Kapovich which I also talked about in an earlier post. Continue from that pervious post, now we know that

Theorem: Any hyperbolic group (plus obvious conditions, namely torsion free and does not split over a finite cyclic group) with 1-dimensional boundary has \partial_\infty G homeomorphic to \mathbb{S}^1, the Sierpinski carpet or the Menger curve.

When \partial_\infty G = \mathbb{S}^1, my wonderful advisor Dave Gabai proved that G would act discrete and cocompactly on \mathbb{H}^2 by isometries. (i.e. it’s almost the fundamental group of some hyperbolic surface except for possible finite order elements which make the action not properly discontinuous.)

Now the next step is of course figuring out when does groups act on \mathbb{H}^3, we have:

Cannon’s conjecture: If hyperbolic group G has boundary \mathbb{S}^2, then G acts discretely and cocompactly on \mathbb{H}^3 by isometries.

This conjecture was also mentioned another pervious post. Turns our we do not know much about groups with \mathbb{S}^2 boundary. However, using graph of groups, they were able to show:

Theorem: If Cannon’s conjecture is true, then those hyperbolic groups with Sierpinski carpet boundary are fundamental groups of hyperbolic 3-manifolds with totally geodesic boundary.

i.e. the idea is to ‘extend’ the group with Sierpinski carpet boundary to a group having sphere boundary. Of course as sets we can embed the carpet into a sphere and start to ‘reflect it along the boundary of the ‘holes’, continue the process and eventually the union of all copies of the carpets is the entire \mathbb{S}^2. The problem is how to ‘reflect’ a group?

First, since the boundary is homeomorphic to the carpet, there are countably many well-defined ‘boundary circles’, the group G acts on the set of boundary circles. They showed this action has only finitely many different orbits. (those orbits of boundary circles will eventually correspond to those totally geodesic boundary components of our resulting 3-manifold). We pick one boundary circle from each orbit and denote their stabilizers H_1, \cdots, H_k each H_i < G.

Define a graph of groups \mathcal{G} with two vertices both labeled G, with k edges, all going from one vertex to the other. Let the edge groups be H_1, \cdots, H_k.

Now we can start to 'unfold' the graph： Let X_G be a 2-complex associated to a set of generators and relations for G and X_i be 2-complexes associated to H_i. The inclusion map induces cellular maps h_i: X_i \rightarrow X_G. Hence we have

\displaystyle h: \sqcup_{i=1}^n X_i \rightarrow X_G

Let X be the mapping cylinder of h. i.e. X has boundary components \sqcup_{i=1}^n X_i and X_G.

Let DX be the complex obtained by gluing together two copies of X along \sqcup_{i=1}^n X_i, take it’s universal cover \widetilde{DX}. Now the fundemental group \hat{G} of DX is, in some sense, the group obtained by doubling G along each H_i. i.e. \hat{G} is the fundamental group of the graph graph of groups \mathcal{G}.

Now by studying the 1-skeleton of the complex \widetilde{DX}, one is able to conclude that \hat{G} is Gromov hyperbolic with \mathbb{S}^2 boundary, as expected.

Hence from groups with Sierpinski carpet boundary we are able to produce groups with sphere boundary. Now if Cannon’s conjecture is true, \hat{G} is fundamental group of some hyperbolic 3-manifold, together with Gabai’s result that H_i are fundamental groups of hyperbolic surfaces, we would have that G is the fundamental group of a hyperbolic 3-manifold with n totally geodesic boundary components.

Well, since now we don’t have Cannon’s conjecture, there is still something we can conclude:

Definition: A n-dimensional Poincare duality group is a group which has group cohomology satisfying n-dimensional Poincare duality.

Those should be thought of as fundamental groups of manifolds in the level of homology. Well, I know nothing about group cohomologies, luckily we have:

Theorem: (Bestvina-Mess)

\Gamma is a n-dimensional Poincare duality group iff it’s torsion free and \partial \Gamma has integral Cech cohomology of \mathbb{S}^{n-1}

Great! In our case \partial \hat{G} IS the sphere! So it’s a 3-dimensional Poincare duality group~ Now we have a splitting of \hat{G} over a bunch of 2-dimensional Poincare duality groups (namely H_i) it follows that (G; H_1, \cdots, H_n) is a Poincare duality pair.

It is not known whether all such pairs can be realized as fundamental groups of 3-manifolds with boundary. If so, then by Thurston’s geometrization we can also obtain what we derived assuming Cannon’s conjecture.

The Carnot-Carathéodory metric

Conan7 Comments

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

Conan5 Comments

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

ConanLeave a comment

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)<n 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.