A Chinese new year greeting~

So this is the first day of the Chinese new year, classes/seminars still haven’t resumed since December 17th, still two weeks to go before anything starts…

Anyways, I’m borrowing this occasion to thank everyone for continuously supporting this blog! We’ve had a great year, check the annual report at the end of the post for details.

As some of you may already know, I have decided that mathematics is not going to be my life-long career. So far it’s not clear in which direction will this blog go, it’s simply too important to abandon. I guess only time would tell. However, expect changes.

Finally, a sketch I doodled up last night~ Happy Chinese new year!

(btw, for those who have seen me in winter, yes I’m waring that Klein bottle hat in the picture!)

The WordPress.com stats helper monkeys prepared a 2011 annual report for this blog.

Here’s an excerpt:

The concert hall at the Sydney Opera House holds 2,700 people. This blog was viewed about 15,000 times in 2011. If it were a concert at Sydney Opera House, it would take about 6 sold-out performances for that many people to see it.

Click here to see the complete report.

Sumsets, in discrete and continuous settings

In the past few years, there are 137 papers with the term ‘sumset’ in its title; and 50 more with ‘sum-set’. Ok the above statement was stolen from a talk I happen to be sitting in, by Noga Alon.

As usual, in the middle of the talk I got carried away by some ‘trivial facts’ he wrote down which are only slightly related to the main content. So I thought about that for during the rest of the talk (and also a little bit afterwards).

This time the curious point pops up when he was motivating why people should be studying chromatic number of random Cayley graphs by its application to sumsets.

Definition: In a vector space , a sumset is a set that can be represented as the Minkowski sum of another set with itself. i.e. where .

It was mentioned that given a large , if we look at sets in , then all sets with large cardinality must be sumsets.

This fact is first published by Ben Green who also raised the natural question:

Question: What’s the lower bound such that all subsets with must be a sumset?

Let’s first see why all sets of large cardinality must be sumsets: Well as we all know (can also be expressed as many other sums) is a sumset. Hence the first non-trivial case is :

The way I think of sumsets is that they are projections of product sets in the angle :

Hence our goal is to make up a set such that the projection, after mod , is everything except for the point . Well, this isn’t too hard, first note the image of the ‘interval’ after mod is exactly the set we wanted. Now we just need to make project to the interval! will do. (Here by we meant that it’s the integer when is even and when it’s odd.

Note that since , is actually a square in and only “warped” in mod after we project it to .

So we just showed all sets with one missing element is a sumset~ Now let’s move to sets of size …(Don’t worry, I’m not going on to 3 and the length of this post will be finite :-P)

In contrast to the above argument which actually works in the continuous setting and shows the Lie group missing any interval is a sumset, this time we actually need to use the fact that our space is discrete and finite.

Note first that the property of being a sumset is invariant under scaling and translating by an integer. Indeed,

and of course .

Now no matter which two points we delete, i.e. , we may let . We have , which is the projection of the square .

Hence is a sumset.

After playing around with the torus for a little bit, I believe in the continue case we can still write deleting two (small) intervals as a sumset where is a union of no more than 4 intervals. There are quite a few cases involved concerning the spacing between small intervals, hence I’ll just draw an example:

(By the way, this is about as far as I got daydreaming during the lecture, the rest came from the sources I looked up afterwards.)

Unfortunately since the scaling and translating gived only two degrees of freedom, the above argument fails when considering sets missing three points. (Playing with torus as I first tried, however, might still work)

Back to our question, so now we know at least the natural thing to study is of course how does it grow with . Recall that we denoted , hence the problem is equivalent to giving asymptotic lower bounds for .

So this is quite curious, what do you think? Is just a counstant? (such as , or ?) Or is it always more than a fixed proportion of ? (say any set containing 99% of the elements must be a sumset?) Or something in-between?

As one might have expected, is more than a constant,

Theorem: (Green) .

It’s also not as large as a fixed percentage:

Theorem: (Gowers-Green)

So it’s something ‘in-between’. Interesting…So what is this number? This is an open question in general, by applying methods of Cayley graphs and their spectrums, the speaker (of the talk) was able to improve the above bounds (in this other paper):

Theorem: (Alon)

However one should expect that

Conjecture: (Green) .

Having knowing absolutely nothing about the subject (or combinatorics in general), my first reaction about this is that perhaps, if we look at where is roughly , let be the set missing equally spaced points, now if we want to write as a sumset that’s like finding a product that misses all diagonal circles and have at least points in each thin strip to ‘block’ every diagonal circle in the strip.

I think this set looks (by the same philosophy as when we play around with the two intervals on the tori case) fairly hard to express as a sum. i.e. when we are exactly in , we can probably ‘just’ do it by choosing one representative from each mod class and place them in the strips. But looks as if the ‘resolution’ is any lower, (i.e. is a little smaller and we still have about equally spaced holes), we would not have enough freedom to place the points.

Anyways, that last remark might be completely nonsense~ The conjecture is interesting, tho.

The Schwartz lantern

It’s thanksgiving, let’s have some fun in lantern-making!

This thing called Schwartz lantern initially came up in a talk some years ago, I vaguely remembered it as ‘a cool example where the refining triangle approximation of a smooth surface fail to converge in area’. Anyways, it came up again recently as I was talking to some German postdoc working in ‘discrete differential geometry’. As the example was mentioned, he took a napkin and started folding…and I just realized this lantern can actually be made with a piece of flat paper!

Given a compact, smooth surface (possibly with boundary) embedded in , we can approximate it by a PL surface with all vertices on the surface and having only triangular faces. (just like what’s done in many computer graphic softwares nowadays).

Question: When the vertices of the faces gets denser and denser and the diameter of triangles converge to , does the area of the PL surface converge to the area of the surface?

Ok, to explain why I found this being a quite curious little question, let’s prove a couple of trivial observations:

Trivial fact #1: The sequence of PL surfaces as described above does Hausdorff converge to the smooth surface.

Proof:Since our surface is smooth, as the diameter of the triangles converge to , the length of the geodesic between two vertices is roughly the length of the edge in the 1-skeleton of the PL surface. In particular, less than twice its length.

Now by compactness we have a positive injectivity radius, implying that for small enough length , the diameter (on the surface) of region enclosed by any loop of length most is controlled by (say it’s which converge to as ). Now the diameter of the region is of course even smaller than its surface diameter.

In conclusion, when all triangles have small diameter (hence all its sides have length at most ), the geodesic triangle on the surface has parameter less than . So diameter of the geodesic triangle is no more than . Hence the surface is contained in the -neighbourhood of the vertex set.

Obviously the PL surface is also contained in this neighbourhood. Hence the Hausdorff distance is at most , which converges to .

Trivial fact #2: For curves in (in fact, or ), the length converges.

Proof: Well…what can I say…see any undergrad calculus book? (well, all we need is that smooth curves are rectifiable. Of course they are…

So from the above observations, does it kinda smell like the area would converge? (If you know the answer, you should pretend you don’t and nod at this point :-P) Well, the fact is they don’t have to converge! (otherwise why are we making counter-examples here?) Furthermore, this is first discovered by a super-cool dude – Schwartz! He even wrote a paper about it back in 1880.

How can this be possible? You might have already observed that with some simple curvature bounding, we can push the argument for trivial fact #1 to show that area of the curved surface is controlled above by the straight surface, The point being (perhaps to one’s surprise) that the ‘straight surface’ can be a lot LARGER than the curved one!

So the example is a sequence of ‘lanterns’ converging to a standard cylinder (say of height and circumference both equal to ), i.e. PL surfaces with triangular faces, vertices on the cylinder, with smaller and smaller ‘grids’, and the sum of areas of the triangle blows up to infinity.

As shown above, if we have put points on the cylinder, points along the circumference and in the vertical direction (picture is not to scale); connected to form triangles in the above way.

Now all triangles are isosceles and identical. Doing some middle-school geometry shows that they have base length and height (this calculates the distance between the midpoint of the base to the cylinder surface).

Having triangles means the area of the PL surface is at least when large, . Hence the blows up to infinity.

Is this pretty cool? This lantern also have an interesting feature that, if we define ‘curvature’ on vertices to be the sum of angles attached to that vertex, (and of course the curvature on the edge between two flat faces shall be ), then all lanterns have curvature everywhere, just as in the smooth cylinder! i.e. it can be made by folding a single piece of flat paper.

Let’s note that although the triangles are getting uniformly smaller, they do become ‘thinner and thinner’ in the example. In fact this is the only way it can go wrong, i.e. it can be shown that if we further require the triangles to have bounded eccentricity then the area does converge.

Add-on: I actually made the lantern! They are interesting to fold, aesthetically pleasing and even functional! (you’ll see light flaring out in an interesting way)

Trying it out while one thinks about problems is highly amusing and recommended~

All one needs to do is:

Tips on folding:

1. Be sure to make all diagonal lines positive fold and horizontal lines negative.

2. Make the diagonals cross an even number of horizontals or else after you finish all diagonals, you’ll end up with left and right-facing diagonals not crossing on the horizontal (i.e. you’ll need to double the number of horizontals to make it work again)

3. After finishing all lines, it might be hard at first to make the whole thing ‘fold up’. The trick being to make sure all ‘crosses’ are ‘poped-out’ on the whole surface. The final folding process does not work locally!

4. Although theoretically you can take an arbitrarily long strip of paper with unit width to make unit-sized lantern, but in order to not make a million folds and have super-sharp angles between the diagonal and horizontal; I recommend not being too aggressive on the length :-P (square-ish papers are good enough)

Have fun!~

A not-very-good picture of my lantern (larking light bulb…>.<)

Haken manifolds and virtual Haken conjecture

Hi people~ My weekends have been unfortunately filled up with grading undergrad assignments for the last couple of weeks >.< I'll try to catch up on blogging by finding some other time slot during the week.

As a grand-student of Thurston's I feel obligated to end my ignorance regarding Haken manifolds. I guess it's a good idea to start by writing my usual kids-friendly exposition here.

In the rest of the post, is a compact (so perhaps with boundary), orientable, irreducible (meaning each embedded 2-sphere bounds a ball) 3-manifold.

Definition: A properly embedded oriented surface is incompressible if is not the 2-sphere and any simple closed curve on which bounds an embedded disc in also bounds one in .

Figure 1

In other words, together with Dehn’s lemma this says the map induced by the inclusion map is injective.

Note that the surface could have boundary, for example:

Figure 2

Definition: is Haken if it contains an incompressible surface.

Okay, at this point you should be asking, what’s good about Haken manifolds? The beauty about it is that, roughly speaking, once you find one incompressible surface in the manifold, you can just keep finding them until the manifold is completely chopped up into balls by incompressible surfaces.

Theorem: (Haken) Any Haken 3-manifold contains a hierarchy where

1. is an incompressible surface in
2. where is an incompressible surface for the closure of some connected component of $latex
3. is a union of 3-balls

Sketch of proof: This is much simpler than it might appear to be. The point is (at least in my opinion), except for trivial cases as long as a manifold has boundary it must be Haken.

Lemma: If has a component that’s not then is Haken.

The proof of the lemma is merely that any such will have infinite hence by the sphere theorem it will contain an embedded surface with non-trivial homology, if such surface is compressible then we just cut along the boundary of the compressing disc and glue two copies of it. This does not change the homology. Hence at the end we will arrive at a non-trivial incompressible surface.

Figure 3

Now back to proving of the theorem, so we start by setting to be an incompressible surface given by being Haken.

Now since is irreducible, we cut along , i.e. take the closure of each component (may have either one or two components) of . Those will have a non-spherical boundary component, hence by lemma containing homologically non-trivial incompressible surface.

This process continuous as long as some pieces has non-spherical boundary components. But since is irreducible, any sphere bounds a 3-ball in , hence all components with sphere boundary are 3-balls. (In particular, the case where a component have multiple sphere boundary components cannot occur since the first boundary component bounds a 3-ball hence it can’t have any non-trivial incompressible surfaces on both sides.)

Now the only remaining piece is to show that this process terminates. We apply a standard ‘normal surface argument’ for this. Essentially if we fix a triangulation of ,

A normal surface in is one that intersects each 3-simplex in a disjoint union of following two shapes:

Figure 4

There can’t be infinitely many non-parallel disjoint normal surfaces in (in fact there can be no more than 6 times the number of 3-simplexes since each complementry component need to contain at least one non-I-bundle part from one 3-simplex).

Figure 5

However, if the above process do not terminate, we would obtain a sequence of non-parallel non-spherical boundary components:

Figure 6

They represent different homology classes hence can be represented by disjoint normal which results in a contradiction.

In general, this gives a way to prove theorems about Haken manifolds by using inductionL i.e. one may hope to just show the property trivially holds for 3-balls and is invariant under gluing two pieced along an incompressible surface. Note that the gluing surface being incompressible is in fact quite strong hence making the induction step possible in many cases.

For example, by applying an incredible amount of brilliant techniques, Thurston was able to prove his revolutionary result:

Hyperbolization theorem for Haken manifolds: Any Haken manifold with tori boundary components that does not contain incompressible tori admits a complete hyperbolic structure of finite volume in its interior.

In other words, this is saying that given a Haken manifold, we cut along any incompressible tori, the resulting manifold with tori boundary must have a complete hyperbolic structure with cusps near each boundary component,

This is the best we could hope for since manifolds with incompressible tori would have their fundamental group split over which of course imply they can’t be hyperbolic.

Now the more manifolds being Haken means the better this theorem is. Many evidences show that in fact a lot of manifolds are indeed Haken, in perticular we have:

Virtual Haken Conjecture: is finitely covered by a Haken manifold as long as is infinite.

We can see that together with Thurston’s hyperbolization theorem, this would give full solution to the geometrization conjecture for general 3-manifolds.

However, although now Perelman has proved the geometrization conjecture, the virtual Haken conjecture remains open. But in light of Perelman’s result now we are able to try to ‘back-solve’ the puzzle and only prove the virtual Haken conjecture for hyperbolic manifolds.

(to be continued)

Longest shortest geodesic on a 2-sphere

This is a little note about constructing a Riemannian 2-sphere which has longer shortest geodesic than the round 2-sphere of same area.

—–  Background Story  —–

So there has been this thing called ‘mathematical conversations’ at the IAS, which involves someone present a topic that’s elementary enough to be accessible to mathematicians in all fields and yet can be expanded in different directions and lead into interesting interdisciplinary discussions.

Nancy Hingston gave one of those conversations about simple geodesics on the two-sphere one night and I was (thanks to Maria Trnkova who dragged me in) able to attend.

So she talked about some fascinating history of proving the existence of closed geodesics and later simple closed geodesics on generic Riemannian two-spheres.

Something about this talk obviously touched my ‘systolic nerve’, so when the discussion session came up I asked whether we have bounds on ‘length of longest possible shortest closed geodesic on a sphere with unit area’. The question seem to have generated some interest in the audience and resulted in a back-and-forth discussion (some of which I had no clue what they were talking about). So the conclusion was at least nobody knows such a result on top of their head and perhaps optimum is obtained by the round sphere.

—–  End of Story —-

A couple of post-docs caught me afterwards (Unfortunately I didn’t get their names down, if you happen to know who they are, tell me~) and suggested that suspending a smooth triangular region and smoothen the corners might have longer shortest geodesic than the round sphere:

The evidence being the fact that on the plane a rounded corner triangular contour has larger ‘width’ than the disc of same area. (note such thing can be made to have same width in all directions)

Well that’s pretty nice, so I went home and did a little high-school computations. The difficulty about the pillow is that the shortest geodesic isn’t necessarily the one that goes through the ‘tip’ and ‘mid-point of the base’, something else might be shorter. I have no idea how to argue that.

A suspicious short geodesic:

So I ended up going with something much simpler, namely gluing together two identical copies of the flat equilateral triangles. This can be made to a Riemannian metric by smoothing the edge and corners a little bit:

Okay, now the situation is super simple~ I want to prove that this ‘sphere’ (let’s call it from now on) has shortest geodesic longer than the round sphere ()!

Of course we suppose both and has area 1.

Claim: The shortest geodesic on has length (which is length of the one through the tip and mid-point of the opposite edge.)

Proof: The shortest closed geodesic passing through the corner is the one described above, since any other such geodesics must contain two symmetric segments from the corner to the bottom edge on the two triangles, those two segments alone is longer than the one orthogonal to the edge.

That middle one has length where

i.e.

The good thing about working with flat triangles is that now I know what the closed geodesics are~

First we observe any closed geodesic not passing through the corner is a periodical billiard path in the triangular table with even period.

So let’s ‘unfold’ the triangles on the plane. Such periodic orbits correspond to connecting two corresponding points on a pair of identified parallel edges and the segment between them intersecting an even number of tiles.

W.L.O.G we assume the first point in on edge . Since we are interested in orbits having shortest length, let’s take neighborhood of radius around our edge : (all edges with arrows are identified copies of )

There are only 6 parallel copies of in the neighborhood:

Note that no matter what point on we start with, the distance from to another copy of it on any of the six edges is EQUAL to . (easy to see since one can slide the segments to begin and end on vertices.)

Hence we conclude there are no shorter periodic billiard paths, i.e. the shortest closed geodesic on has length .

Note it’s curious that there are a huge amount of closed geodesics of that particular length, most of them are not even simple! However it seems that after we smoothen to a Riemannian metric, the non-simple ones all become a little longer than that simple one through the corner. I wonder if it’s possible that on a Riemannian sphere the shortest closed geodesic is a non-simple one.

Anyways, now let’s return to ~ So the surface area is hence the radius is

Any closed geodesics is a multiple of a great circle, hence the shortest geodesic has length , which is just slightly shorter than .

Now the natural question arises: if the round sphere is not optimum, then what is the optimum?

At this point I looked into the literature a little bit, turns out this problem is quite well-studied and there is a conjecture by Christopher Croke that the optimum is exactly . (Of course this optimum is achieved by our singular triangle metric hence after smoothing it would be .

There is even some recent progress made by Alex Nabutovsky and Regina Rotman from (our!) University of Toronto! See this and this. In particular, one of the things they proved was that the shortest geodesic on a unit area sphere cannot be longer than , which I believe is the best known bound to date. (i.e. there is still some room to .)

Random remark: The essential difference between this and the systolic questions is that the sphere is simply connected. So the usual starting point, namely ‘lift to universal cover’ for attacking systolic questions does not work. There is also the essential difference where, for example, the question I addressed above regarding whether the shortest geodesic is simple would not exist in systolic situation since we can always split the curve into two pieces and tighten them up, at least one would still be homotopically non-trivial. In conclusion since this question sees no topology but only the geometry of the metric, I find it interesting in its own way.

Graph of groups in relation to 3-manifolds

(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 with boundary, if the inclusion map is not injective, then there exists a simple non-trivial loop in bounding an embedded disc in .

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 , edge set , to each vertex we associate a group and to each edge (say connecting ) we also associate a group , together with a pair of injective homomorphisms , .

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 homeomorphic to , the Sierpinski carpet or the Menger curve.

When , my wonderful advisor Dave Gabai proved that would act discrete and cocompactly on 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 , we have:

Cannon’s conjecture: If hyperbolic group has boundary , then acts discretely and cocompactly on by isometries.

This conjecture was also mentioned another pervious post. Turns our we do not know much about groups with 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 . 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 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 each .

Define a graph of groups with two vertices both labeled , with edges, all going from one vertex to the other. Let the edge groups be .

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

Let be the mapping cylinder of . i.e. has boundary components and .

Let be the complex obtained by gluing together two copies of along , take it’s universal cover . Now the fundemental group of is, in some sense, the group obtained by doubling along each . i.e. is the fundamental group of the graph .

Now by studying the 1-skeleton of the complex , one is able to conclude that is Gromov hyperbolic with 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, is fundamental group of some hyperbolic 3-manifold, together with Gabai’s result that are fundamental groups of hyperbolic surfaces, we would have that is the fundamental group of a hyperbolic 3-manifold with 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)

is a n-dimensional Poincare duality group iff it’s torsion free and \partial \Gamma$ has integral Cech cohomology of

Great! In our case IS the sphere! So it’s a 3-dimensional Poincare duality group~ Now we have a splitting of over a bunch of 2-dimensional Poincare duality groups (namely ) it follows that 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.

A Bosuk-Ulam-kind theorem for simplexes

This little note came out of a lunch discussion with NYU grad student Alfredo Hubard earlier this week. I think the problem-solving process was quite amusing hence worth shearing.

Back in kindergarten, we all learned this theorem called ‘at any given time, there are two opposite places on Earth having exactly the same temperature and air pressure’. Yes that’s the Bosuk-Ulam theorem. I remember at some point I came across a much less famous theorem in some kind of discrete/combinatorial geometry, saying:

Theorem: Any map from a n-dimensional simplex to must have a pair of intersecting opposite faces.

Note: each k-dimensional face of the n-dimensional simplex has a unique, well-defined dimensional opposite face, as shown:

Some examples of maps from the 3-simplex to :

i.e. in general they can be quite a mess. I think it can be proved by Thurston’s simplex straightening argument. (haven’t checked carefully)

To me this is like Bosuk-Ulam except for instead of considering a large amount of antipodal pairs, we consider only finitely many such pairs. Hence a discrete analoge.

However, one should note that although they are of the same nature, neither follows from the other.

So somehow this theorem came up during the lunch and Alfredo mentioned to me that professor Guth wondered whether the theorem can be proved for mappings from the simplex to lower dimensional simplicial complexes (instead of ). i.e.

Question: Given where denote the -dimensional simplex and is a -dimensional simplicical complex. Then must there be a pair of opposite faces with intersecting image?

So we started to throw out random ideas.

First of all, although only boundary faces of the simplex has non-empty opposite faces (hence can possibly be intersecting pair), it is important that is defined on the solid simplex. (i.e. if one just map the boundary, then we may let be topologically a sphere and make the map a homeomorphism!) So the moral is, we kind of need to ‘claps’ the simplex to a simply connected lower dimensional thing first, then map it to our , hence having non-trivial topology won’t be of much help. Looks almost like the case, doesn’t it?

Perhaps the image on can be complicated and has non-trivial topology, but this is merely ‘wrapping’ a contractible, -dimensional thing around. But wrapping around can only cause more overlapping hence making the faces intersecting more, not less.

The above line of thoughts give an immediate proof in the case when is a surface and : Lift the map to the universal cover and apply the theorem for . (It’s a little more tricky when the surface is but you can work it out~ the map restricted to must be of even degree) Note this won’t generalize to higher dimensions (even for manifolds) since universal covers are no longer that similar to .

So what’s the main difference between complexes and manifolds? well, one can have more than two dimensional faces attached to the same dimensional face. I decided to first think of whether Bosuk-Ulam is still true if we further assume that the map extends to the solid ball (as seen above, it is true in the surface case).

After trying to generalize that ‘lifting’ proof for a while, we realized the Bosuk-Ulam does not work for simplicial complexes in all dimensions! For very simple reason, i.e. if we map the to by projecting down, the pre-image of the center point is the only pair of antipodal points that’s mapped together. Hence if instead of we have three -simplicies attached along a single -simplex (think of it as a piece of with a vertical simplex attached in the middle):

Now we can still project to that piece of , with the image of antipodal point lying on the middle simplex, all we need to do is to separate this pair while not creating new pairs! But this is easy, just ‘drug’ the upper sheet into the third -simplex a little bit:

(the region outside of the red neibourhood is unchanged) It’s easy to see that no new antipodal pair is moved together.

So now we turned back to the simplex and realized it’s even easier to argue: project in orthogonal direction to a -face, originally the only intersecting pair of opposite faces was the vertex and that -face. Now if we lift the vertex int the third sheet, nothing can intersect~

OK~ perhaps not a useful answer but problem solved!

So far I do not know the answer to the following:

Questions:

1. Is this intersecting faces theorem true for mapping -simplexes to -dimensional manifolds?

2. Is the Bosuk-Ulam true if we consider maps from spheres to -dimensional manifolds which extends to the ball?

The later might be well-known. But so far I can only find a theorem by Conner and Floyd, stating that any map from to a lower dimensional manifold must have a pair of antipodal points mapped together.

Stable isoperimetric inequality

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 , 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:

.

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

In the plane, however it’s a classical theorem that any region of area and perimeter as where as (well, that is because I forgot the exact bound, but should be linear in ).

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

where 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 to have volume 1. Let denote the ball with n-dimensional volume 1 in (note: not the unit ball). be the ( dimensional) measure of the boundary of .

Now we have a relation

As said in the talk (and I can’t find any source to verify), there was a result in the 90′s that and the square one is fairly recent. The sharp constant 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 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 , how does the left and right hand side change when we perturbe it to a rectangle with small eccentricity?

As we can see, is roughly . The new boundary consists of two faces with measure , two faces of measure and faces with volume . Hence the linear term cancels out and we are left with a change in the order of ! (well, actually to keep the volume 1, we need to have instead of , but it would still give )

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 side-length you perturbe, as long as the volume stay the same (up to ) 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 , if the sum set has volume only a little bit larger than that of two round balls with those volumes, are the sets 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 (or ), we define two quantities:

and

where is the expected value, are independent random variables with a standard normal distribution (mean 0, variance 1) and are independent Bernoulli random variables.

Question: Given any , can we always find such that

and

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

Kissing numbers of sphere packings

Enough of the ‘trying to understand recent big theorems’ on this blog, let’s do something light and fun this week!

As I was browsing the ArXiv one day, one thing led to anther and I eventually arrived in a very short and cute paper of Greg Kuperberg and Oded Schramm.

So, we have sphere packings, which is simply a bunch of spheres (say in ) with disjoint interiors, some of them might be tangent to others, in which case we say the two sphere ‘kiss‘, like this: (points of tangency are marked with a red cross)

We can associate a graph to a sphere packing with vertices representing spheres and join two vertices with an edge if two sphere kisses:

Question: What kind of graph can appear this way?

Now if we go back to two-dimensions, it’s a classical theorem that any planar graph can appear as the nerve of a circle packing. (In fact, as mentioned at the end of this earlier post, something much stronger is true. i.e. it’s a theorem of Schramm that one can ‘kiss’ pretty much any given set of planar objects with a given nerve.)

In light of this, it’s nature to wonder whether every graph can be realized as a nerve of some sphere packing (since all graph embeds in some oriented surface which then embeds in ). Turns out, no.

However I would imagine it’s not easy to show things such as a given graph cannot be realized. In the paper they came up with what’s perhaps the first restriction that shows not all graphs can be realized in such packing, namely:

The average kissing number is, as one might expect, in average how many kisses does each sphere get, i.e.

2 * number of tangency points / number of balls

If one thinks about it, how might one attempt to construct a packing with super large average kissing number? Well, perhaps we start with a single sphere, put a huge amount of small spheres around it (because one cannot fit many large spheres), then this middle one does get a lot of kisses, but what about the smaller ones? If they are equal sized then all the small spheres only gets roughly 7 kisses…now we need to put even smaller spheres around each of those…If we stop at any stage, there would be more smallers spheres that’s not taken care of than the larger ones with lots of kisses, so it’s not clear at all if the average can blow up.

As usual, things are much simpler in two dimensions: Since the Euler characteristic of any planar graph is 2 (), and (any face needs at least 3 edges around them, precisely two faces share an edge) we have

, hence <

On the other hand, for our all-time favorite hexagonal packing of congruent circles, if we take more and more layers, the number of balls with six kisses grow like , the number of balls on the boundary (hence with less than six kisses) is like . Hence by adding enough layers we can make the average as close to 6 as we want~

Hexagonals are the best, as expected~

Now comes what’s in the paper: they showed that for any sphere packing, the average kissing number is less than . Hence any graph with average degree larger than 15 cannot be realized. They also provided an example of sphere packings with average kissing number larger than 12.

For simplicity I’ll only reproduce the ‘warm-up case’ in the paper which proves the kissing number is no more than 24. (well, since our goal here is only to say that not all graphs can be realized.) I find this observation (due to Schramm) is very simple, cute, and works in any dimensions.

Let’s first define some numbers:

the maximum number of congruent sphere kissing one sphere (i.e. how many unit spheres we can place around a unit sphere) can be easily computed, for example and , etc.

Let average kissing number of sphere packings in dimension . As we have seen and we are interested in giving upper bounds to .

Theorem: .

Given a sphere packing , let be the set of kissing pairs and be the set of spheres.

Define map where maps each pair to the sphere in the pair with smaller radius (if the two spheres has the same radius, then just randomly choose one).

Since each sphere can only be surrounded by spheres of its size (of course larger than its size would give us fewer), we conclude that is at most to . Therefore, we have

, i.e.

How simple!

Now going from 24 to requires some estimates relying on us being in 3-dimensions. Essentially, given any sphere in the packing, if we enlarge it by a ratio w.r.t its center, then this ‘shell’ intersect some other spheres in disjoint circles. Those circles of course cuts out a fraction of the area that’s < 1 on the shell. Summing this fraction over all shells results a number that’s less than .

Now if we look at each pair of balls, say take pair (V_1, V_2), it turns out that if they kiss, the fraction of shell around that’s cut out by plus the fraction of shell around cut out by is a constant depending only on .

Hence we get a relation . Choose an optimum gives which is a bit less than 15.

So we know but larger than 12, the problem of finding the exact value of remains open, so is the problem of giving other restrictions on the graph for being the nerve of a sphere packing.

Ultrametrics and the nonlinear Dvoretzky problem

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 , for any , there exists depending only on such that any normed vector space of dimension or larger has a k-dimensional linear subspace that embeds (via a linear transformation) with distorsion at most into the Hilbert space.

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

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 , does there exist a so that every metric space of Hausdorff dimension has a subset of Hausdorff dimension that embeds into the Hilbert space with distorsion ?

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 such that for any , every compact metric space with dimension has a closed subset of dimension at least that admits an embedding into Hilbert space with distorsion .

Note that, in the original linear problem, of course blows up to infinity whenever or . (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 , the larger dimension we need, the less flat (more distorsion) we can expect it to be. i.e.

necessarily forces and
forces .

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

In the original statement of the problem this gives not only that a large exists, but ! In fact, when we are allowing relatively large distorsion (compare to constant ) this theorem is sharp:

Theorem 2 (Mendel-Naor): There exists constant and a family of metric spaces such that for any small , no subset of with dimension embeds into Hilbert space with distorsion .

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

So what if is small? Turns out, unlike in the linear case when , there is no , in the paper they also produced spaces for each where the only subset that embeds with distorsion < 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 , and then make use of the fact that any such space sits in the Hilbert space isometrically.

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

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 , with the dictionary metric (two points are distance apart where 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 is a Cantor set and sits isometrically in . It’s not hard to see in fact all such space embeds isometrically in .

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 > can be mapped surjectively [thanks to Tushar Das for pointing out the typo] onto the unit ball by a Lipschitz map.

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

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