Surface Deformations: Visualizing Homotopies

A homotopy is a (smooth) map which continuously deforms a space nicely (without introducing any singularities).

I was part of illiMath2006: an NSF funded Research Experience for Undergraduates (REU) summer program at the University of Illinois at Urbana-Champaign. One of the objectives of the program was to deliver an academia-industry collaborative project centered around a student principal investigator (me). My mentors for the project were George Francis at UIUC, Stuart Levy at the National Center for Supercomputing Applications, and Ulises Cervantes-Pimentel at Wolfram Research.

Our project Sakubo was such a success that Wolfram Research decided to continue the project the following year when I worked there as a summer 2007 intern. We built szgMathematica (= Syzygy + Mathematica) which enables users to use Mathematica’s graphical functions, such as Plot3D or ParametricPlot3D, and view the resulting surfaces in the CUBE.

We even built a function that simulated a rollercoaster where a user could input any closed parametrized curve for the rollercoaster track. The parametrization controlled the speed of the motion. We tried many closed curves from Mathematica’s new (at the time) Knot library and found that crazier knots were not as fun to ride as the standard trefoil. Perhaps there was just too much going on.

The second iteration of the project involved many more people. I worked with George Francis at UIUC, Stuart Levy, Camille Goudeseune at the NCSA, Jim Crowell at ISL, and Ulises Cervantes-Pimentel, Joshua Martell at WRI.

Random_Discrete_Morse

Computing the topological type, or homology, of a given a simplicial complex is straight forward, but not always computationally feasible. The bottleneck is in computing the Smith Normal Form, which is a polynomial time algorithm [Kannan-Bachem], but still too slow on large examples (about cubic).

Discrete Morse theory [Whitehead, Forman] provides a tool set which can be used to find reasonable upper bounds.  A randomized search for small discrete Morse vectors was introduced by Benedetti and Lutz, which we implemented as a client for the topological software package polymake.

I gave a workshop on Random_Discrete_Morse at the Homology: Theoretical and Computational Aspects (HTCA 2015) conference in Genoa, Italy.

While experimenting with Random_Discrete_Morse, we discovered a whole family of contractible, yet non-collapsible simplicial 2-complexes. We call them the sawblade complexes. Read more about the sawblade complexes here.

This project was joint work with Frank Lutz and Michael Joswig, with help from Benjamin Lorenz, Bruno Benedetti, and Karim Adiprasito.

References

Bistellar simplification

In the late 80s Udo Pachner introduced the idea of a bistellar move which can modify the triangulation of an object (simplicial manifold) without changing its fundamental properties (topological type). About a decade later, Frank Lutz implemented bistellar_simplification as a tool to classify objects by their topological type using a simulated annealing strategy. Later, Niko Witte wrote a C++ implementation of Frank’s code for polymake, which considerably sped up the computation. I, then, spent several (loong) months trying to improve Niko’s code so that it can be used to recognize our spheres.

The 2-dimensional version of a bistellar move is well known in the graphics community, though it is usually called by a different name: edge flips. It can be used to find “nice” triangle meshes of some domain, which may, for example, be applied to finite element-type computations.

The idea of the bistellar move is simple. We’ll be using some terminology from here. Let’s start with a simplicial complex \(K\) of dimension \(d\) and a simplex \(\sigma \in K\) of dimension \(0\le i \le d\). (Technically, \(K\) should be a closed combinatorial manifold.)

A bistellar \(i\)-move is \(\Phi_K(\sigma) = K – \text{star}(\sigma,K) + \tau \ast \partial \sigma\), where \(\tau\) is a \((d-i)\)-simplex NOT in \(K\) such that \(\partial \tau = \text{link}(\sigma,K)\). The move is only valid if a \(\tau\) satisfying these properties exists.

The animated gif below shows some bistellar moves in action. You can see why the algorithm is called a bistellar simplification — we can change the triangle mesh to have fewer triangles.

Consider an abstract graph whose nodes are simplicial complexes which are connected by an edge if there exists a single bistellar move to get from one complex to the other. This graph is known as the bistellar flip graph or Pachner graph. The bistellar_simplification algorithm is equivalent to a random walk on this infinite graph which attempts to identify the topological type of the input complex \(K\) by lowering the \(f\)-vector of \(K\).

Tracking the \(f\)-vector is the cheapest way to track our progress of the simplification. In fact, for a 4-dimensional sphere, the number of vertices and edges alone is enough to learn about the entire \(f\)-vector [Klee]. So we can actually track the progress of the simplification on a 2 dimensional graph.

Below is a video tracking the progress of our modified bistellar_simplification on our Akbulut-Kirby 4-sphere AK_I_3. Since following a single dot was difficult to see, I am displaying the \(f\)-vector (or, more precisely, just the vertex and edge count) of 1000 consecutive complexes at a time. For each of those 1000 complexes, I counted the number of 0-,1-,2-,3-,4-dimensional bistellar moves were made (red = 4-move grows the \(f\)-vector, green = 0-move makes \(f\)-vector smaller; green = good). The box on the bottom right displays the vertex and edge count of the complex at the specified round.

Notice that the simulated annealing strategy brings the \(f\)-vector down until it gets stuck for a while, then it grows the \(f\)-vector in an attempt to jiggle the complex out of the local min. The current implementation uses a greedy random strategy, the modifications we made to the strategy only improved the algorithm enough to recognize AK_I_3, AK_II_3, AK_III_3. The other spheres to our knowledge have not been recognized by any heuristic software we know of.

We have also tried to implement a Markov chain Monte Carlo (Metropolis) method to improve the algorithm. We have tried several different parameters for the energy. Our tests so far indicate that an MCMC strategy results in a significant slow down of the algorithm. We are now looking into testing other deep learning techniques.

Triangulations of the Akbulut-Kirby Spheres

Our triangulations of the Akbulut-Kirby Spheres

Manifold recognition is known to be unsolvable for dimensions \(d \ge 4\) [Markov]. The related sphere recognition problem is known to be undecidable for dimensions \(d > 4\). However, 3-sphere recognition is decidable [Rubinstein, Thompson], but was found to be NP [Schleimer] and co-NP [Hass-Kuperberg]. The decidability of the 4-sphere recognition problem is still unknown.

Fortunately, there are several heuristic methods which can effectively and quickly recognize spheres to be spheres for all triangulations (or, more accurately, simplicial complexes) that we know of. Except, that is, for the family of examples which we constructed: our triangulations of the Akbulut-Kirby spheres.

The Akbulut-Kirby spheres were originally introduced as candidate exotic spheres [Akbulut-Kirby]. Selman Akbulut and Rob Kirby described a smooth manifold which is homeomorphic to a 4-dimensional sphere, but could not find a diffeomorphism to the sphere. If they could prove that there are no diffeomorphisms to the sphere, then they would have found a counterexample to the smooth Poincare conjecture in dimension 4. It took over 2 decades, but Akbulut himself found that diffeomorphism [Akbulut]. And the smooth Poincare conjecture in dimension 4 is still an open problem today.

Akbulut and Kirby simplified the description enough that one can follow the general idea without being an expert in differential topology and Kirby calculus.

Start with a 4-dimensional ball to which we attach two handles (like the handle on a coffee mug). Formally these handles are called one-handles. So we have now attached two one-handles. We then label each handle so we can keep track of which is which. Let us call the purple one \(x\) and the green one \(y\). Notice the image is a 3-dimensional depiction of our 4-manifold.We then want to glue two 4-balls onto this manifold to close up the two holes that we introduced when we attached the two one-handles in the beginning. But we will glue them on in a non-trivial way. We will follow along the two paths (red and blue) shown above. If you start from the blue dot and walk along, you’ll find the blue path goes along the \(x\)-handle, then \(y\), then \(x\), then the \(y\)-handle backwards, then \(x\) backwards, then \(y\) backwards, and return to the blue dot. We describe this blue path as \(xyxy^{-1}x^{-1}y^{-1}\) and the red one is \(x^5y^{-4}\).

We started with a 4-ball, introduced two holes, then closed off those holes. So we’re back to having just a ball. Make a copy of that ball. Then match up the boundaries of the two balls. And voila: we get a 4-dimensional sphere.

This sphere we constructed is described by the finitely presented group \(G = \langle x,y \mid xyx=yxy. x^5 = y^4 \rangle\), which you can read all about in the beginning of Kirby’s Topology of 4-manifolds.

That’s essentially the entire construction.

We developed a few simplicial versions of this procedure. It was a bit involved (enough for me to get a PhD), but we produced some nice pictures. Here’s a taste. For more details, check out the dissertation or the preprint.

We know that the manifolds we constructed are proper 4-spheres by Akbulut’s proof and the fact that in dimension 4, PL=DIFF. Yet, none of the sphere recognition heuristic software we know of have been able to correctly recognize them to be spheres. To our knowledge, these are the only such examples.

For a more graphical summary of this project, check out this poster that was presented at the MSRI Modern Math Workshop at SACNAS 2015.

References

LaTeX hack: Adding a custom .cls to your search path

After a few hours of frustrated head bashing against my desk, I’ve finally figured out a way to add a directory containing a custom class file to my TeX search path. So before I forget the vital — yet simple — two steps, I will record them here. (Yep, that’s 4 whole hours for 2 lines of code.)

First let me give credit where credit is due. This page helped me immensely. Thank you, you wonderful LaTeX hackers.

Let’s assume you’ve created an amazingly useful class file that is useful to no one else but you. (This would also apply for a custom style file (.sty) as well.) And say you want to use that class for more than one LaTeX project. It would be easy to just have the .cls file in the same folder as your LaTeX project. But you want to have just the one .cls for multiple LaTeX projects.

For this example, I’m going to call that file syllabus.cls. Let’s put that into its own unusually named folder
~/some/path/syllabus/syllabus.cls

Before we move ahead to the two lines of code, you’ll need to learn a bit about your LaTeX installation. This is the head-bashing part.

(In case you’re curious: I’m on a Mac OSX (Yosemite) with TeX-Live 2015. Also, I use TeX-lipse (with Skim) for my editor.)

Open your Terminal and type

kpsewhich --var-value TEXMFLOCAL

For me, this returns
/usr/local/texlive/texmf-local

From the many posts I read on tex.stackexchange, I expected that it would be enough to place my syllabus folder right here. But it turns out life is not so kind.

One needs to dig a bit deeper to:
/usr/local/texlive/texmf-local/tex/latex/local

I don’t know if this is true for everybody, but that was the case for me.

And now, the moment you’ve all been waiting for:


sudo mv ~/some/path/syllabus/ /usr/local/texlive/texmf-local/tex/latex/local
sudo texhash

And that’s all. Now back to writing up some syllabi.