Skip to content

Computational Topology

February 12, 2012


Unravelling the structure of mappings

Camille Jordan was a mathematician who has his name attached to many important concepts: the Jordan curve theorem, the Jordan normal form in matrix theory, Jordan content or measure, and the Jordan-Hölder theorem in group theory. Even cooler, he has an asteroid named after him: 25593 Camillejordan. One might ask, how did he do this? How did he get so many things named after him?

Today Ken and I wish to comment on a pretty paper on the computation of homotopy classes, which just appeared in this year’s SODA conference. More than pretty it was awarded the best paper award for 2012.

We continue the reporting on some of the SODA papers, for those who did not attend the conference in Tokyo. This is part of GLL’s service to the community, saving your travel dollars. Of course, it is much better to be at the conference than to read about papers here. As always we say to read the original paper to really understand the details, but we hope these summaries and pointers are helpful.

One measure of the importance of a mathematical concept is its ratio of

\displaystyle  \frac{\text{complex behavior}}{\text{definitional complexity}}.

The higher this value, the better the notion. We really desire easily-defined concepts that have way more complex behavior than their definitions. If the definition takes pages and the behavior is simple, we are not excited. If the definition is simple, and the behavior is extremely subtle and mysterious, all the better. Note how this corresponds to the discussion of salience and depth at the end of the previous post.

Long and Winding Roads

The notion of homotopy, invented initially by Jordan in terms of closed paths and developed by many others, is one of those notions from topology that sound pretty simple. Yet its behavior is still a major mystery for even simple objects like spheres. Well perhaps spheres are not that simple—the Poincaré Conjecture is a perfect example of their subtle behavior—but still the fact that we cannot understand completely the homotopy classes for spheres is pretty upsetting.

From our friends at Wikipedia is a picture that mimics part of the Hopf fibration, which is a map from the 3-sphere to the 2-sphere such that the inverse image of every point on the latter is a circle on the former:

When I applied to graduate schools I was interested in two areas: topology and computer science—do not ask why these two. Luckily for me, while I was accepted at several mathematics departments that were strong in topology, I took the easy way out and went to CMU to study computer science. I found out later that I am able to prove theorems about high-dimensional geometric problems, yet my intuition about geometry is near zero, so avoiding topology was probably a good move. The Hopf fibration picture, above, is a complete mystery to me.

The homotopy groups are based on an operation of composing closed paths, which is extended to higher-dimensional notions of composition. The following table should give some idea of the complex behavior of these groups:

If you see the whole pattern let us know. Notice that part of one row has a weird jump from 2 to 30 then back down:

\displaystyle  \mathbb{Z}_{2},\mathbb{Z}_{2},\mathbb{Z}_{2},\mathbb{Z}_{30},\mathbb{Z}_{2}.

A One-Minute Introduction To Homotopy

The usual joke definition of a topologist is someone who cannot tell the difference between a coffee cup and a donut. The point is that they both are the same as topological spaces. One of the great strengths of topology is this tremendous smearing of things that we would usually think of as quite different; this smearing allows great insights to be made.

Topologists are also interested in smearing the differences between maps, usually continuous maps, between two spaces. Suppose {f} and {g} are mappings from the space {X} to the space {Y}. They are considered equivalent if they are homotopic, i.e., if one can be continuously deformed into the other one. This leads to the study of {[X,Y]} which is the collection of all classes of maps from {X} to {Y} grouped by this notion of homotopy.

The great insight is that the cardinality of the number of maps from {X} to {Y} is usually uncountable, indeed highly uncountable—it often has cardinality well above that of the reals. But the number of homotopy classes can be vastly smaller: they are finite in the cases that are studied here. Clearly reducing highly-uncountable sets to finite sets is a huge insight that should and does yield wonderful results. I wish we would have some way to reduce the number of objects that arise in computer science theory in the same way.

Let’s just consider the case where {X} is the circle {S^1}, viewed as going from the base point {0} to {1} which is the same point, and {Y} similarly has a fixed base point {y_0} so maps {f} always have {f(0) = y_0 = f(1)}. We can make a group, called the fundamental group, out of these path-like maps. The identity of the group is the constant map {f_0(x) = y_0} for all {x}. The product {h = f * g} and inverses {f^{-1}} are then defined this way:

\displaystyle  \begin{array}{rcl}  h(x) &=& f(2x) \quad\text{if } x \leq 1/2\\ h(x) &=& g(2x-1) \text{ if } x \geq 1/2\\ f^{-1}(x) &=& f(1-x). \end{array}

The definition of {h} “glues together” nicely because {h(1/2) = f(1) = y_0 = g(0)}. Intuitively {f*g} means the path that first follows {f} at “twice the speed” and then similarly follows {g}. Inversion means following the path in reverse.

Why does {f*f^{-1}} yield the identity? Here is where the fact that all this is modulo homotopy equivalence comes in. Picture the path as a string, and for argument’s sake, let’s say that {f} was winding the string around and through a donut so you could dunk it fully in your coffee without burning your fingers. Composing with {f^{-1}} means that instead of stopping the string once around you doubled it backwards around the donut. The string then doesn’t wind around, but rather comes loose and can be pulled back all the way to a point, which is equivalence to the identity map. Provided every pair of points in {Y} are connected by a path, the choice of {y_0} doesn’t matter, so we simply have the fundamental group {\pi_1(Y)}.

To define the higher homotopy groups, we use maps defined on {S^n}, and glue maps at higher-dimensional faces than points. What’s neat is that for {n \geq 2}, the group turns out to be abelian—see here for a proof.

The SODA Paper

Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek and Uli Wagner
prove in their great paper that it is possible to compute homotopy groups. Here possible means that it is computable, but they reserve the right to give—in a future paper—efficient algorithms for these computations. Here they “only” show how to compute the groups.

Theorem: Let {d \ge 2}. Assuming that {Y=S^{d}} and that {\dim X \le 2d-2}, then the set {[X,Y]} is computable: It is a finite Abelian group and the algorithm computes the structure of the group as products of cyclic groups. Morever, the algorithm attaches a unique group element to any map {f:X \rightarrow Y}. Thus it is possible to tell if two maps are homotopic.

They point out that their proof is an amalgamation of known methods and ideas, but still putting all this together seems to be a terrific contribution. The details are something that you really need to look at the paper to see.

Open Problems

There are many open questions. Can their special case be done in polynomial time? Can it be extended to a larger class of spaces, and when does the problem become hard?

About these ads
2 Comments leave one →
  1. Uli permalink
    February 13, 2012 7:51 am

    Regarding your wish for “some way to reduce the number of objects that arise in computer science theory in the same way [as in algebraic topology]“, let med point at the directed-topology research program which Eric Goubault initiated some 15 years ago. I would say the proof that this is useful is still out; but it’s certainly a nice try to use inspiration from algebraic topology in concurrency theory. See http://en.wikipedia.org/wiki/Directed_algebraic_topology

Trackbacks

  1. Why Is 290 Special? | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,873 other followers