Small Triangulations of $4$-Manifolds and the $4$-Manifold Census

We refer to a 4-simplex as a pentachoron (plural: pentachora). The tetrahedral cells of a pentachoron are referred to as facets. We label the vertices of a pentachoron by elements of $\{0,1,2,3,4\}$, and use the convention that facet $i$ refers to the facet opposite to the vertex labelled by $i$. A (generalised, $4$-dimensional) triangulation $𝒯$ is a finite collection of $n$ abstract pentachora, some or all of whose $5n$ facets are affinely identified (“glued”) in pairs. These generalised triangulations are typically far more efficient than simplicial complexes, since we allow two facets of the same pentachoron to become identified.

The boundary of $𝒯$ consists of all the facets that are not identified with any other facets. We allow facets of the same pentachoron to be identified. The gluings defining $𝒯$ also have the effect of merging vertices, edges, triangles, and tetrahedra of the pentachora into equivalence classes, which we refer to as the vertices, edges, triangles, and tetrahedra of $𝒯$.

The link $\mathrm{lk}(v)$ of a vertex $v$ of $𝒯$, is the “frontier” of a small regular neighbourhood of $v$. We treat vertex links as triangulated $3$-dimensional spaces, formed by inserting a small tetrahedron into each corner of each pentachoron, and then joining together the tetrahedra from adjacent pentachora along their triangular faces. This mirrors the traditional concept of a link in a simplicial complex, but is modified to support generalised triangulations.

If $v$ lies in the boundary of $𝒯$, its link is a space with boundary. If the link is homeomorphic to $B^3$, then we refer to $v$ as a boundary vertex. If the link is any other space with boundary then we say $v$ is an invalid vertex. On the other hand, if $v$ does not lie in the boundary of $𝒯$, its link is a closed space. If the link is (PL-)homeomorphic to ${𝕊}^3$, then $v$ is an internal vertex, and if it is any other closed space then it is referred to as an ideal vertex.

We insist that no edge of $𝒯$ is identified with itself in reverse, and that no triangle is identified with itself via a non-identity permutation. This, together with the condition that the link of every vertex is either $B^3$ or ${𝕊}^3$, guarantees that $𝒯$ triangulates a $4$-manifold.

Given a triangulation $𝒯$ of a $4$-manifold, the vector $f(𝒯)=(f_0,f_1,f_2,f_3,f_4)$, where $f_i$ denotes the number of $i$-dimensional faces in $𝒯$, is called its face vector, or $f$-vector for short. Since $𝒯$ triangulates a $4$-manifold, it satisfies the following equations

known as generalised Dehn-Sommerville equations [35]. Here, $\chi (𝒯)$ denotes the Euler characteristic of $𝒯$, a topological invariant. Observe that Equation (1) implies that a triangulation of a closed $4$-manifold must have an even number of pentachora.

To encode a triangulation, we give each pentachoron a label and an ordering of its five vertices. Two triangulations are (combinatorially) isomorphic if they are identical up to relabelling of pentachora and/or reordering of the pentachoron vertices. We can uniquely identify any isomorphism class of triangulations using an efficiently-computable string called an isomorphism signature [11]. Every triangulation has a unique isomorphism signature, and two triangulations have the same signature if and only if they are isomorphic.

An important tool in the study of triangulations is the dual graph (also known as the face pairing graph). Given a triangulation $𝒯$, its dual graph $\mathrm{\Gamma }(𝒯))=(V,E)$ is the multigraph whose nodes are the pentachora in $𝒯$, and for each gluing that identifies two tetrahedral facets of $p_i$ and $p_j$ we add an arc between the corresponding nodes in $V$. By construction, $\mathrm{\Gamma }(𝒯)$ has maximum degree $\le 5$, and is $5$-regular when $𝒯$ triangulates a closed $4$-manifold $\mathrm{\Gamma }(𝒯)$.

The dual graph as defined above does not retain any information about the permutations used in the face identifications, and so $𝒯$ cannot be reconstructed from $\mathrm{\Gamma }(𝒯)$ alone. Nevertheless, some information about the underlying topology of the $4$-manifold can still be extracted from $\mathrm{\Gamma }(𝒯)$. It also proves to be useful as a visual tool when discussing triangulations.

We modify our triangulations using Pachner moves (or bistellar flips), which are local moves that change a triangulation but not its underlying PL-type [33]. Informally, an $(i,j)$ Pachner move can be thought of as taking a subcomplex of $i$ pentachora in the boundary comlpex of the $5$-simplex $\partial {\mathrm{\Delta }}^5$, and replacing them with its complement in $\partial {\mathrm{\Delta }}^5$ of $6-i=j$ pentachora. This necessarily means that (a) the $i$ pentachora share a common $(5-i)$-dimensional face – which is removed from the triangulation; and (b) the $j$ pentachora share a common $(i-1)$-face – which is newly inserted into the triangulation. See Figure 1 for an illustration of Pachner moves in dimension four, and see [33] for more details.

The use of Pachner moves has several key benefits: Firstly, two PL manifolds $X$, and $X^{\prime }$ are PL-homeomorphic if and only if there exists a sequence of Pachner moves between $X$ and $X^{\prime }$. This statement is known as Pachner’s theorem and was first proven in [33]. We can therefore certify that two triangulations are PL-homeomorphic by finding a connecting sequence of Pachner moves. Even without a guarantee that this algorithm will terminate, it is effective in practice. Secondly, Pachner moves can be used to reduce the size of a triangulation (without changing the underlying PL-type). Finally, Pachner moves are already implemented and ready-to-use in several software packages. Here, we use Regina [12].

The Pachner graph of a PL manifold $X$, denoted by $𝒫(X)$, is used to describe and track how distinct triangulations of a $4$-manifold can be related via Pachner moves. It is the (infinite) graph with nodes corresponding to isomorphism classes of triangulations of $X$; and two nodes of $𝒫(X)$ are joined by an arc if and only if there is a single Pachner move that takes one triangulation to the other. We refer the reader to [11] for further details.

There are many other local modifications which can be expressed by sequences of Pachner moves. When moving through the Pachner graph, using these additional modifications can be powerful, since they allow the use of “short-cuts” into different areas of the graph. In this article, we make extensive use of two of these additional moves, the $2$-$0$-edge move and the $2$-$0$-triangle move. The $2$-$0$-edge move takes two pentachora, identified along three tetrahedra to form a “pillow” around a common edge, and flattens them to form two tetrahedra. The $2$-$0$-triangle move is similar. Here, two pentachora, are identified along two tetrahedra to form a pillow around a common triangle, and flattens them to form three tetrahedra.

Let $𝒯$ be a $4$-manifold triangulation. For the ring of coefficients $\mathbb{Z}$, the group of $p$-chains, $0\le p\le 4$, denoted $C_p(𝒯,\mathbb{Z})$, of $𝒯$ is the group of formal sums of $p$-dimensional faces with $\mathbb{Z}$ coefficients. The boundary operator is a linear operator ${\partial }_p:C_p(𝒯,\mathbb{Z})\to C_{p-1}(𝒯,\mathbb{Z})$ such that ${\partial }_p\sigma ={\partial }_p\{v_0,\mathrm{\cdots },v_p\}={\sum }_{j=0}^p\{v_0,\mathrm{\cdots },\widehat{v_j},\mathrm{\cdots },v_p\}$, where $\sigma$ is a face of $𝒯$, $\{v_0,\mathrm{\dots },v_p\}$ represents $\sigma$ as a face of a pentachoron of $𝒯$ in local vertices $v_0,\mathrm{\dots },v_p$, and $\widehat{v_j}$ means $v_j$ is deleted from the list. Denote by $Z_p(𝒯,\mathbb{Z})$ and $B_{p-1}(𝒯,\mathbb{Z})$ the kernel and the image of ${\partial }_p$ respectively. Observing ${\partial }_p\circ {\partial }_{p+1}=0$, we define the $p$-th homology group $H_p(𝒯,\mathbb{Z})$ of $𝒯$ by the quotient $H_p(𝒯,\mathbb{Z})=Z_p(𝒯,\mathbb{Z})/B_p(𝒯,\mathbb{Z})$. Each homology group $H_p$ is a finitely generated $\mathbb{Z}$-module, and is a topological invariant of the manifold triangulated by $𝒯$. We write ${\beta }_p=dim(H_p(𝒯,\mathbb{Z}))$ for the dimension of (the free part of) $H_p$. Informally, $H_p(𝒯,\mathbb{Z})$, $0\le p\le 4$, of a triangulation $𝒯$ counts the number of “$p$-dimensional holes” in $𝒯$. For a more thorough introduction to homology theory see [25].

Let $X$ be a closed, oriented $4$-manifold. Representatives of classes in $H_2(X;\mathbb{Z})$ generically intersect in a finite number of points (possibly after isotoping them into transverse position). The intersection form $Q_X$ of $X$, is the symmetric, unimodular, bilinear form defined by

where $S_{\alpha }$, and $S_{\beta }$ are $2$-chains representing the classes $\alpha ,\beta \in H_2(X;\mathbb{Z})$. If $X$ is smooth, $S_{\alpha }$, and $S_{\beta }$ can be chosen to be oriented surfaces embedded in $X$ [23, Proposition 1.2.3].

A landmark result of $4$-manifold topology is the following classification result for simply connected (i.e. having trivial fundamental group²²2The fundamental group of a manifold $X$, denoted ${\pi }_1(X)$, describes closed paths in $X$ up to homotopy, with the group operation of path concatenation.) topological $4$-manifolds due to Freedman.

Shortly after Freedman’s result, Donaldson showed the following equally important result.

The results by Freedman and Donaldson (together with Serre’s algebraic classification of indefinite forms) imply the following key result.

In the smooth setting, we primarily work with $4$-manifolds via handle decompositions. Let $X,X^{\prime }$ be two smooth $4$-manifolds. We say $X$ is obtained from $X^{\prime }$ by attaching a ($4$-dimensional) $k$-handle, denoted $X=X^{\prime }{\cup }_{\phi }{h}^k$, if there is an embedding $\phi :S^{k-1}\times D^{4-k}\to \partial X^{\prime }$ such that $X$ is of the form $X=\left[X^{\prime }\bigsqcup D^k\times D^{4-k}\right]/\phi (x)\sim x,$ where $D^k$ denotes the closed $k$-disk ($k\in \{1,2,3,4\}$). There always exists a Morse function $f:X\to ℝ$ inducing a handle decomposition $X={\bigcup }_{i=0}^n{X}_i$ with $\mathrm{\varnothing }=X_{-1}\subset X_0\subset \mathrm{\cdots }\subset X_n=X$ in which $X_i$ is obtained from $X_{i-1}$ by attaching $i$-handles [31]. Since $X$ is closed and connected, it can be assumed that there is a single $0$- and $4$-handle. Hence a closed $4$-manifold $X$ is obtained from $B^4$ by attaching $1$-, $2$-, and $3$-handles and finally capping off with another $B^4$. Given such a handle decomposition, we depict $X$ by drawing the attaching regions of the handles in the boundary of the $0$-handle ($\partial B^4\cong {𝕊}^3\cong {ℝ}^3\cup \{\ast \}$). By a result of Laudenbach and Poenaru [29], $3$- and $4$-handles attach uniquely up to diffeomorphism, and so it suffices to understand how the $1$- and $2$-handles attach. We depict $1$-handles by “dotted” unknots (see Section 5.4 of [23] for details of this notation). $2$-handles are attached via a map of the form $S^1\times D^2\to S^3$. These maps are determined up to isotopy by (i) an embedding $S^1\times \{0\}\to S^3$ (i.e. a knot) and (ii) a choice of normal vector field on the knot. Classes of such vector fields are in bijection with the integers [23]. As such, we draw a $2$-handle as a knot decorated with an integer. A decorated link diagram of this form – dotted unknots and integer decorated links – is called a Kirby diagram and gives a combinatorial encoding of a closed $4$-manifold up to diffeomorphism. Figure 2 is an example of a typical Kirby diagram.

Up-Side-Down-Simplify (USDS): This subroutine is the heart of our algorithm. It is relatively easy to describe, but details are very important. We point out that it is difficult to design a method which is efficient for both triangulations that can trivially be merged with a different class, as well as pathological cases needing millions, if not billions of moves to escape a local area of the Pachner graph (apart from the triangulation presented in Section 5 resisting classification altogether, there are four more $4$-pentachoron triangulations requiring a large number of moves before being classified as standard). Extensive research has been done to find effective strategies to compare PL homeomorphism types for triangulated $4$-manifolds, see Section 1 for a detailed discussion. At least in the case of the census of small $4$-manifold triangulations, the below strategy yields the best results on a consistent basis.

Our heuristic is a slight variation of a standard biased Markov chain-style random walk through the Pachner graph of a triangulation. We bias the sizes of the triangulations visited by the random walk around a fixed target size of $\widehat{n}$ pentachora (in our calculations, we used $8\le \widehat{n}\le 12$). If the current state of the random walk has more than $\widehat{n}$ pentachora, an exponential penalty is imposed on choosing a Pachner move further increasing the size of the state. The same is true for a current state of smaller size than $\widehat{n}$ and moves further reducing its size.

The core idea of our approach lies in the type of moves we choose to increase and decrease the sizes of our triangulations: we use $2$-$4$-Pachner moves to increase the size of a triangulation, but $2$-$0$- edge- and triangle-moves to reduce the size of a triangulation. Moreover, we use standard $3$-$3$-Pachner moves to change triangulations while keeping their $f$-vector constant.

Empirical evidence suggest, that this approach mixes triangulations much faster than by just using standard Pachner moves. This approach has already been used very successfully by the first author [7] in the search of minimal triangulations. The method used there is even simpler in structure than the one presented below.

Our base method has four input parameters that stay fixed for the duration the method is run: (a) A set probability $x\in [0,1]$ to decide whether a $3$-$3$-move or some other move is performed, (b) a target size $\widehat{n}$ for triangulations to be visited in the random walk, (c) a parameter $\alpha \in ℝ$ determining the severity of the penalty for sampling a triangulation of size away from $\widehat{n}$, and (d) a number of steps $s\in \mathbb{Z}$.

Adjust-Vertex-Number: This subroutine takes a triangulated $4$-manifold ${𝒯}_0$ as input, and outputs a PL homeomorphic triangulation with $v$ vertices.

If ${𝒯}_0$ has fewer than $v$ vertices, perform $1$-$5$-moves $v-f_0({𝒯}_0)$ times to obtain a $v$-vertex triangulation. If, on the other hand, the input triangulation has more than $v$ vertices, we randomly perform edge collapses. If not enough edge collapses are available, we run USDS in between until they become available. It is worthwhile noting that the latter case has no guarantee to terminate in general, but does very quickly in practice.

Our implementation is based on establishing PL-homeomorphisms using Pachner’s theorem [33], i.e. by describing sequences of Pachner moves transforming one triangulation into another. Our computations are organised in a Union-Find structure: at any step of our calculations, every triangulation is associated to a class of triangulations for which pairwise PL homeomorphisms have already been established. Each class has a unique representative triangulation. If a sequence of Pachner moves is found turning a triangulation from one class into a triangulation from another class, both classes are merged with the representative of the latter class, and we continue. This way, if the task is to classify $N$ triangulations, we only need to establish $O(N)$, rather than $O(N^2)$ PL homeomorphisms.

We start with a large number of triangulations ${𝒯}_1,\mathrm{\dots },{𝒯}_N$. Here, we assume that all triangulations have the same number of $n$ pentachora, but this is not necessary for the algorithm to work. We furthermore assume that we have already established that all triangulations ${𝒯}_i$, $1\le i\le N$, are homeomorphic. Again, this is not a necessary requirement for the algorithm to work, but we require, however, that all triangulations have already been tested to have the same Euler characteristic $m$.

For $n$-pentachora triangulations of Euler characteristic $m$, it is a consequence of Equations 1, 2, and 3 that their $f$-vector is determined by their number of vertices. We have the following algorithm.

Our implementation of the algorithm described in this section is available at https://github.com/raburke/Dim4Census.

Our guiding principle for the implementation is to minimise human intervention. We point out that we can modify arbitrarily many triangulations in parallel until they can be merged with an existing component of the Union-Find structure. This parallelises the bottleneck of the computation for large censuses of largely easy-to-handle triangulations. When dealing with pathologically difficult combinatorial structures, running different random walks on the same triangulation may lead to similar speed-ups. However, for the $6$-pentachoron census with its $\approx 400,000$ triangulations, parallelisation is not crucial and we hence defer its implementation to future work.

For some indications of running times, we ran our algorithm on a laptop with an 11th Gen Intel i7 processor and 32GB of RAM, with input the $\mathrm{405\hspace{0.17em}188}$ $6$-pentachoron triangulations homeomorphic to $S^4$. We obtained the following timings for first running Adjust-Vertex-Number (referred to as Step 1), then running USDS until only 10 connected components are left over (Step 2), and then the times to merge any additional component until we reduce to 6 connected components, which is when we stopped our calculations.

Achieving 5 connected components usually does not take much longer (with $\mathrm{1\hspace{0.17em}611}$ and $\mathrm{18\hspace{0.17em}929}$ additional seconds in two of the six runs summarised above). Achieving four connected components takes around a week, as we were able to observe on multiple occasions. The algorithm never achieved 3 connected components. Running the complete algorithm in parallel on $100+$ cores may produce additional results. Alternatively, exhaustive enumeration on a larger machine with more memory may lead to additional merges of connected components.

PL classification of other topological types was achieved through a combination of exhaustive enumeration and our main algorithm. Relevant timings are summarised below.

As discussed in Section 4, our PL classification algorithm determines whether two given triangulations are PL homeomorphic. What is missing from this algorithm is a reference triangulation for which its PL homeomorphism type is known.

For this we use the software tool Katie [6, 7], developed by the first author. Katie is based on an algorithm due to Casali and Cristofori [18]. It takes as input a Kirby diagram and produces a triangulation of the associated PL $4$-manifold. For each of the topological types in Tables 1, 2, and 3, we start with the Kirby diagram representing its canonical PL-type, and compare the resulting triangulation to the triangulations in the census.

For all but three topological types, all triangulations homeomorphic to a given $4$-manifold, are pairwise PL-homeomorphic. The three exceptions are ${𝕊}^4$, $ℂP^2$, and the $\mathbb{Q}$-homology sphere $Q{S}^4(2)$, cf. Table 3 for which we find $4$, $3$, and $2$ components respectively.

As already documented in Section 4.3, our algorithm reliably takes all $\mathrm{405\hspace{0.17em}188}$ triangulations homeomorphic to ${𝕊}^4$ from the $6$-pentachoron census and classifies them into around $5$ PL classes within a day of computation time. Some of the remaining classes have remarkable combinatorial properties, which are discussed in more detail in Section 5. These remaining classes are certified to be impossible to connect to other classes using an exhaustive enumeration and traversal of the Pachner graph with an excess height of $6$ (that is, only triangulations with number of pentachora up to $6+6=12$ are considered).

In some contrast to the triangulations homeomorphic to ${𝕊}^4$, we can connect all but four of the $\mathrm{29\hspace{0.17em}124}$ triangulations homeomorphic to $S^3\times S^1$ using exhaustive simplification and traversal of the Pachner graph, with an excess height of at most four. The remaining four can be confirmed to be standard $S^3\times S^1$s by (i) retriangulating to show they were all PL-homeomorphic to each other, and then (ii) traversing the Pachner graph with an excess height of at most $6$. Alternatively, using our algorithm, all $\mathrm{29\hspace{0.17em}124}$ triangulations homeomorphic to $S^3\times S^1$ can be connected within an hour of computation time, see Section 4.3.

This difference in behaviour is noteworthy since ${𝕊}^4$ and $S^3\times S^1$ are the only two $4$-manifolds which can be triangulated using only $2$ pentachora.

Many of the triangulations resisting classification contain a particular $2$-pentachoron subcomplex which we discuss briefly in this section. The complex in question, denoted $C$, has isomorphism signature cHIbbb0bRbpb, $f$-vector $(1,1,5,6,2)$, and has boundary a $2$-tetrahedron solid torus. Considered in isolation, $C$ is not a triangulation of a manifold (its vertex link is a pinched genus-$4$ handlebody, and the link of its edge is a thrice-punctured sphere). However, $C$ can be uniquely closed into an ideal triangulation of a $4$-manifold: the unique³³3Verifiable via a very short exhaustive search of the ideal $2$-pentachoron census. $2$-pentachoron triangulation of a Cappell–Shaneson $2$-knot complement [5]. This is a triangulation of the complement of a “knotted” $2$-sphere in the $4$-sphere, $S^4-\nu S^2$.

The “cut-open” Cappell–Shaneson complex $C$ embeds in a topological $4$-ball $B_C^4$, where $B_C^4$ is obtained from the unique $4$-pentachoron $4$-sphere still resisting classification (eAMPcaabcddd+aoa+aAa8aQara) by ungluing a single facet identification. We denote this $4$-sphere by $S_C^4$. The isomorphism signature of $B_C^4$ is eGzMkabcdddcaGa8aAa0awa. Its fundamental group presentation, as simplified by Regina [12] or GAP’s SimplifiedFpGroup [24], is $⟨a,b\mid a^3{b}^3{a}^{-2}{b}^{-2},a^{-3}{b}^{-1}{a}^5{b}^2⟩$; moreover, GAP certifies that this is a presentation of the trivial group. It seems natural to assume that $S_C^4$ relates – in some way – to the Cappell–Shaneson spheres, formerly conjectured to be exotic [17], and shown to be standard in [1, 22].

It is worthwhile to note that, when $B_C^4$ is attached to a larger triangulation, the $B_C^4$ subcomplex remains intact through very large flip sequences. In this sense, $C$, or $B_C^4$, is a potential combinatorial obstruction to simplify triangulations it appears within (similar to the Dunce hat being a combinatorial obstruction to collapsing a contractible space). Additionally, the presentation of the fundamental group of $B_C^4$ is also challenging to simplify, but possible using the simplification heuristic for finitely presented groups implemented in GAP [24].

We have the following results and conjectures concerning $B_C^4$ and $S_C^4$.

We conjecture that $B_C^4$ supports the standard PL structure because of its small size. Another reason is its relation to a Cappell-Shaneson sphere that is known to be standard [1, 22], see above.

Generating a census (of any type) with $n$ simplicies consists of two stages: First, enumerate all possible dual graphs with $n$ nodes; then, for each graph, test all possible $5n/2$ facet gluings and retain those that yield valid triangulations. For 2, 4, and 6 pentachora there are $3$, $26$, and $638$ such graphs, leading to $8$, $784$, and $\mathrm{440\hspace{0.17em}495}$ valid 4-manifold triangulations, respectively.

We can deduce from this that only a very small fraction of possible gluings give rise to a triangulation of a 4-manifold, implying that various optimisations are possible (and needed) to build the census even only up to $6$ pentachora (cf. [9, 10, 13] for an overview of such optimisations in the $3$-dimensional setting). In the case of 8 pentachora however, existing optimisations are no longer sufficient. Consequently, entirely new algorithms are in development to complete this next step of the $4$-dimensional census. A completed $8$-pentachoron census will come with new challenges for classifying their PL-types. Undoubtedly, more interesting pathological triangulations will emerge and in greater numbers. This is work in progress.

The Cappell – Shaneson subcomplex $C$, discussed at the beginning of this section is only one of many such topological objects that can be described using only a small number of pentachora. In theory, each of them can lead to difficult triangulations of $4$-balls and $4$-spheres, related to $B_C^4$ and $S_C^4$. Such examples are very useful for constructions in low-dimensional topology, or to benchmark future iterations of search methods. Given such a collection of examples, the major challenge is to either rigorously quantify how difficult they are to simplify, or to relate them to former or present potential counterexamples to S4PC.