# 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.