# Effective Computation of the Heegaard Genus of 3-Manifolds

Benjamin A. Burton1
Finn Thompson2

( 1,2School of Mathematics and Physics, University of Queensland, Brisbane QLD
4072, Australia.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
)

###### Abstract

The Heegaard genus is a fundamental invariant of 3-manifolds. However,
computing the Heegaard genus of a triangulated 3-manifold is NP-hard, and
while algorithms exist, little work has been done in making such an algorithm
efficient and practical for implementation. Current algorithms use almost
normal surfaces, which are an extension of the algorithm-friendly normal
surface theory but which add considerable complexity for both running time and
implementation.

Here we take a different approach: instead of working with almost normal
surfaces, we give a general method of modifying the input triangulation that
allows us to avoid almost normal surfaces entirely. The cost is just four new
tetrahedra, and the benefit is that important surfaces that were once almost
normal can be moved to the simpler setting of normal surfaces in the new
triangulation. We apply this technique to the computation of Heegaard genus,
where we develop algorithms and heuristics that prove successful in practice
when applied to a data set of 3,000 closed hyperbolic 3-manifolds; we
precisely determine the genus for at least 2,705 of these.

##### Keywords

3-manifolds, triangulations, normal surfaces, computational topology, Heegaard
genus

##### Supplementary Material

Software (Source Code): github.com/FinnThompson99/heegaard

##### Acknowledgements

We thank the referees for their helpful comments. The second author was
partially supported by the Australian Research Council (grant DP150104108).

##  1 Introduction

In topology, invariants are used to distinguish between different manifolds.
Powerful invariants are often hard to utilise computationally, and sometimes
only partial information can be calculated for them. One such example is the
fundamental group, which uniquely determines hyperbolic 3-manifolds [17], but
it is non-trivial to determine if two such groups are isomorphic, given their
group presentations [22].

We focus on an invariant known as the Heegaard genus of a 3-manifold, which is
the minimal genus of a surface (a Heegaard surface) that splits a given
manifold into two handlebodies of equal genus. For example, the 3-sphere has
Heegaard genus 0, and all lens spaces have Heegaard genus 1. The Heegaard
genus can be used to calculate the tunnel number of a knot, which is a useful
invariant in knot theory ([8], [16]).

However, computing Heegaard genus is NP-hard [1]. Algorithms of Rubinstein,
Lackenby, Li, and Johannson ([19], [12], [13], [11]) provide theoretical
methods, but primarily argue the existence of an algorithm; these algorithms
are extremely complex to describe and theoretically extremely slow to run.
Furthermore, no implementations currently exist.

These three algorithms all make use of surfaces embedded in triangulations of
3-manifolds. In particular, they use normal and almost normal surfaces, which
are commonly used to certify topological properties of a manifold. Normal
surfaces are described by vectors in $\mathbb{Z}_{\geq 0}^{7n}$ for
triangulations with $n$ tetrahedra, and can be efficiently generated using
high-dimensional polytope vertex enumeration methods. However, almost normal
surfaces are more complicated, requiring vectors in $\mathbb{Z}_{\geq
0}^{35n}$, which can significantly affect the running time of any algorithm
using them, due to an exponential dependence on the dimension of the vector
space.

Our strategy in this paper is to avoid the costs of almost normal surfaces by
modifying the triangulation. Since we are solving topological problems, not
combinatorial problems, we aim to retriangulate our manifolds so that
important almost normal surfaces in the original triangulation (such as a
surface that realises a Heegaard splitting) become normal in the new
triangulation. This then allows us to attack the problem using well-studied
normal surface techniques, such as the highly optimised algorithms in the
software package Regina [6].

Our main tool is a new gadget, which replaces a single tetrahedron and serves
to eliminate the almost normal portion of the surface. Importantly, we show
that this gadget preserves the zero-efficiency of the triangulation, a
property that plays a major role in making normal surface algorithms both
implementable and fast ([4], [10]). We identify a class of exceptional
surfaces with which this gadget cannot be used, but these exceptions are of a
very specific form and are simple to analyse. For computing Heegaard genus, we
show how to work around these exceptions with an alternate method for locating
Heegaard splittings of this form.

Using our techniques, we are able to successfully compute the Heegaard genus
of 2,705 closed, hyperbolic 3-manifolds drawn from the hyperbolic census of
Hodgson and Weeks [9].

##  2 Preliminaries

###  2.1 Triangulations

To study topological objects computationally, we represent $n$-manifolds using
triangulations. These are a pairwise gluing of $n$-dimensional simplicies
along their $(n-1)$-dimensional facets. Specifically, a 3-manifold
triangulation consists of a finite number of tetrahedra that are identified
(or ‘glued’) along pairs of triangular faces. Every compact 3-manifold can be
represented by a triangulation [15].

Let $T$ be some arbitrary triangulation (not necessarily a simplicial
complex), and consider some tetrahedron $\tau$ in $T$. In the triangulation,
edges, triangles (faces) and vertices of $\tau$ are not necessarily distinct.
We use a canonical numbering of the vertices, as in Figure 1.

Figure 1: Canonical numbering of the vertices of a tetrahedron.

Let $\tau^{\Delta}_{ijk}$ denote the triangular face constrained by vertices
$(i,j,k)$ of tetrahedron $\tau$. If a given $\tau^{\Delta}_{ijk}$ is not a
boundary facet, then this triangle is shared between (not necessarily
distinct) tetrahedra $\tau$ and $\bar{\tau}$, and we may write
$\tau^{\Delta}_{ijk}=\bar{\tau}^{\Delta}_{pqr}$.

###  2.2 (Almost) Normal Surfaces

If a surface $S$ is properly embedded in a triangulation $T$, we call it a
normal surface if it meets each tetrahedron $\tau$ of $T$ in a collection of
triangular or quadrilateral normal discs (Figure 2). In each tetrahedron,
triangular discs separate one vertex from the remaining three while
quadrilateral discs separate pairs of vertices. In each tetrahedron, there can
be at most one of any quadrilateral type.

===========

Figure 2: The four triangle pieces, and one of the three quadrilateral pieces.

One such surface is a vertex linking sphere, consisting only of triangle
pieces which together form a sphere (in a closed manifold) that surrounds a
particular vertex in the triangulation.

Normal surfaces are represented by normal coordinates, which are vectors
$\mathbf{v}\in\mathbb{Z}_{\geq 0}^{7|T|}$, notated by
$\mathbf{v}=(v_{1},v_{2},\cdots,v_{7},\cdots,v_{7|T|})$, where $v_{i}$
represent the number of each type in each tetrahedron, and $|T|$ is the number
of tetrahedra in the triangulation $T$.

We call two surfaces locally compatible if they are able to avoid intersection
in any given tetrahedron. That is, in each tetrahedron, together they use at
most one type of quadrilateral piece. Locally compatible surfaces can be added
using the Haken sum. If $U$ and $V$ are normal surfaces with normal
coordinates $\mathbf{U},\mathbf{V}$, then $U+V$ has normal coordinates
$\mathbf{U}+\mathbf{V}$. $U+V$ is formed by a geometric surgery (called
‘regular exchange’), where sections of each surface are cut and glued around
curves in $U\cap V$ (as in Figure 3), such that resulting pieces are normal
discs (as in Figure 4).

Figure 3: Around each intersection $\gamma$, the boundary of a neighbourhood
(green) of $\gamma$ is partitioned between the two sheets (red, blue) in one
of two ways. Figure 4: A regular exchange is performed on two intersecting
pieces in two different ways.

We call a normal surface $S$ fundamental if $S=A+B$ implies
$\mathbf{A}=\mathbf{0}$ or $\mathbf{B}=\mathbf{0}$. By standard Hilbert basis
arguments, any normal surface can be expressed as a sum of fundamental
surfaces (which is possibly not unique).

An almost normal surface is similar to a normal surface, but with the addition
that it must intersect one tetrahedron in a collection of triangles and
quadrilaterals, and exactly one unknotted annulus or octagon piece (see Figure
5). We shall refer to annulus pieces between quadrilaterals or triangles of
the same type as parallel, and all others as non-parallel.

= = = =

Figure 5: Annuli between parallel triangles, non-parallel triangles, a
triangle and a quadrilateral, and parallel quadrilaterals; an octagon piece.

Of these almost normal pieces, there are three octagons, three parallel
quadrilateral annuli, four parallel triangle annuli, six non-parallel triangle
annuli and twelve triangle-quadrilateral annuli. With the four triangle and
three quadrilateral normal pieces, this means that normal coordinates for
almost normal surfaces are vectors in $\mathbb{Z}_{\geq 0}^{35|T|}$.

We call a triangulation of a closed 3-manifold zero-efficient if its only
normal 2-spheres are vertex linking. Indeed, all closed, orientable,
irreducible 3-manifolds (excluding $\mathbb{S}^{3}$, $L(3,1)$ and
$\mathbb{R}P^{2}$) can be modified to a zero-efficient triangulation, with
only one vertex. A celebrated result of Jaco and Rubinstein states that if a
zero-efficient triangulation of a 3-manifold $M$ has an almost normal
2-sphere, then $M=\mathbb{S}^{3}$ [10].

###  2.3 Additional Notation

For a normal or almost normal surface $S$ in a triangulation $T$, let $S_{U}$
represent the part of $S$ restricted to some connected sub-triangulation
$U\subset T$.

For a normal surface $S$ in a triangulation $T$, we use
$\mathbf{S_{\tau}}=(t_{0},t_{1},t_{2},t_{3},q_{01/23},q_{02/13},q_{03/12})$ to
refer to the normal coordinates of $S$ restricted to some tetrahedron $\tau$.

When referring to specific normal or almost normal pieces, we shall use the
following.

  * •

tri_a: the link of the vertex $a$

  * •

quad_ab/cd: the quadrilateral separating vertices $a,b$ from $c,d$

  * •

oct_ab/cd: the octagon separating vertices $a,b$ from $c,d$

  * •

tri_a:tri_b: the annulus connecting tri_a to tri_b, allowing $a=b$.

  * •

tri_e:quad_ab/cd: the annulus connecting tri_e and quad_ab/cd, where
$e\in\\{a,b,c,d\\}$.

###  2.4 Normalisation Moves

We can convert surfaces which are not yet normal into normal surfaces through
a process called normalisation [10]. This is an iterative process using
normalisation moves, used to convert a surface into a normal surface (possibly
making changes to the topology of the surface, but which are harmless).

Two particular examples that are relevant to our work are as follows:

  * •

Compression within a tetrahedron, wherein a tubed region of the surface is cut
and then ‘capped’ off with a disk. This does not change the intersection of
the surface with the boundary of the tetrahedron, but reduces the Euler
characteristic.

  * •

Pulling a piece across the boundary of a tetrahedron, where the surface is
‘pulled’ across an edge, reducing the number of intersections with the
boundary of the tetrahedron. This possibly changes the Euler characteristic.

This second move may be used on octagon pieces in a normal surface, as seen in
Figure 6 where an isotopy of oct_02/13 results in just tri_0 and tri_2.

Figure 6: An octagon is ‘pulled’ towards an edge, creating two triangles.

Normalisation moves may introduce other non-normal pieces, but combinations of
these moves will eventually yield a normal surface.

###  2.5 Implementations of Normal and Almost Normal Surfaces

Regina [6] efficiently implements data structures and algorithms for normal
surfaces. However, they are still inherently exponential methods. Indeed, we
have found an experimental bound on the running time of fundamental normal
surface enumeration for closed hyperbolic 3-manifolds,
$T(n)\in\mathcal{O}(1.934^{n})$ for a triangulation with $n$ tetrahedra. See
[5] for more rigorous experimental results. The number of fundamental normal
surfaces for a triangulation with $n$ tetrahedra is
$C(n)\in\mathcal{O}(\phi^{n})$ where $\phi=\frac{1+\sqrt{5}}{2}$ [3]. On the
same set of closed hyperbolic 3-manifolds, we have experimentally found
$C(n)\in\mathcal{O}(1.503^{n})$. See Appendix A for details. We use these
experimental recordings in place of more theoretical bounds, as theoretical
bounds generally represent the worst-case running times.

Almost normal surfaces have historically been motivated by 3-sphere
recognition [20], which by a result of Thompson only requires use of the
octagon piece [23]. In this special setting, there are techniques to normalise
an almost normal surface with an octagon piece—for instance, Regina features a
simple algorithm to remove octagons from an almost normal surface by modifying
the triangulation using a 3-tetrahedron gadget. This technique is used in the
algorithm for cutting along almost normal surfaces [18].

The more general setting that allows octagon _or_ annulus pieces is
significantly more complex to work with (with normal coordinates in
$\mathbb{Z}^{35|T|}$), and there are no implementations known to the authors.

###  2.6 Heegaard Genus

Any closed, orientable 3-manifold $M$ can be represented as $M=H_{1}\cup
H_{2}$ where $H_{1}$ and $H_{2}$ are handlebodies (solid genus $n$ tori) with
$\partial H_{1}=\partial H_{2}=H_{1}\cap H_{2}$. This decomposition is called
a Heegaard splitting of $M$, and $\partial H_{1}$ is the Heegaard surface. The
Heegaard genus of $M$ is the minimal genus of all Heegaard splittings of $M$.

All 3-manifolds with Heegaard genus 1 are classified as being either
$\mathbb{S}^{1}\times\mathbb{S}^{2}$ or a Lens space. Similarly,
$\mathbb{S}^{3}$ is the only 3-manifold with Heegaard genus 0 [21]. Manifolds
with genus $\geq 2$ are not fully classified, and only some classes of
examples are known. In general, computing the Heegaard genus of a 3-manifold
is an NP-hard problem [1].

We choose to follow the techniques of Rubinstein for determining Heegaard
genus [19]. For a zero-efficient triangulation $T$ of a closed, orientable
$3$-manifold, a Heegaard splitting will be of the form $S=S_{an}+S_{t}$ where
$S_{an}$ is an almost normal surface with negative Euler characteristic, and
$S_{t}$ is a normal surface with zero Euler characteristic [19].

To determine if a triangulation has a genus $g$ Heegaard splitting, we
generate candidate almost normal surfaces and test all combinations for $S$
with Euler characteristic $\chi(S_{an})=2-2g<0$. That is, we cut along each
candidate surface, and test whether the resulting piece/s are two handlebodies
of genus $g$, using an efficient algorithm for handlebody recognition [7]. We
use algebraic properties of a given manifold $M$ to form a lower bound on
genus [14]. In particular, we have
$\mathrm{rank}(H_{1}(M))\leq\mathrm{rank}(\pi_{1}(M))\leq g$ where
$\mathrm{rank}(H_{1}(M))$ and $\mathrm{rank}(\pi_{1}(M))$ are the number of
generators of the first homology group and fundamental group of $M$,
respectively. Hence, we use $\max(2,\,\mathrm{rank}(H_{1}(M)))\leq g$ as a
lower bound.

##  3 A Gadget for Normalising Almost Normal Surfaces

Given an orientable triangulation $T$ and an almost normal surface $S$ in $T$,
we seek a way to modify $T$ into another triangulation $T^{\prime}$ of the
same 3-manifold, so that $S$ can be expressed in $T^{\prime}$ using normal
surfaces only, similar to the octagon gadget (see Section 2.5). As almost
normal pieces only appear within a single tetrahedron, we desire a small
triangulation that we may substitute for a tetrahedron. That is, we desire an
orientable triangulation $G$ that is homeomorphic to the 3-ball ($B^{3}$),
with four vertices and four boundary faces. We shall call such a triangulation
the gadget.

###  3.1 A General Gadget Construction

Suppose that $G$ is a triangulation such that $G\simeq B^{3}$, with four
vertices and four boundary faces, arranged to form the boundary of a
tetrahedron. We define $\partial G^{\Delta}_{ijk}$ to represent the boundary
facet that is constrained by vertices $(i,j,k)$ of the gadget $G$. Then, the
boundary of $G$ is isomorphic to the boundary of a single tetrahedron, and so
we can effectively ‘replace’ a tetrahedron $\tau$ in $T$ with $G$ as follows.

We define $T_{\tau}^{abcd(G)}$ to be the resulting triangulation formed by
removing $\tau$ from $T$, and gluing $G$ in its place according to the
permutation mapping vertices of $\tau$ to $G$ by $(0,1,2,3)\mapsto(a,b,c,d)$.
This operation is simply un-gluing each face of $\tau$ from $T$, then gluing
the corresponding boundary face of $G$ in its place (as indicated in Figure 7)
where

$\tau^{\Delta}_{012}\curvearrowright\partial
G^{\Delta}_{abc},\quad\tau^{\Delta}_{013}\curvearrowright\partial
G^{\Delta}_{abd},\quad\tau^{\Delta}_{023}\curvearrowright\partial
G^{\Delta}_{acd},\quad\tau^{\Delta}_{123}\curvearrowright\partial
G^{\Delta}_{bcd}.$

Figure 7: Some tetrahedron $\tau$ in $T$; $T$ with $\tau$ removed; an abstract
depiction of $G$ in $T^{\prime}=T_{\tau}^{abcd(G)}$.

If any pair of faces of $\tau$ are glued to each other, for example
$\tau^{\Delta}_{012}=\tau^{\Delta}_{312}$, then we glue the boundary faces of
the gadget accordingly, such as $\partial
G^{\Delta}_{abd}\curvearrowright\partial G^{\Delta}_{dab}$.

###  3.2 Gadget Requirements

Here, we discuss motivations behind a choice for the gadget. As discussed, we
assume that $G$ has isomorphic boundary to the boundary of a tetrahedron, and
is itself homeomorphic to $B^{3}$. Now, consider some gluing of the gadget
into a triangulation to form $T^{\prime}=T_{\tau}^{abcd(G)}$. As $\partial
G\cong\partial\tau$ and $G\cong\tau$, $G$ does not modify topological
properties of the triangulation, $T$, in which it is placed. In addition, we
desire the following.

  * •

If $T$ is zero-efficient, then $T^{\prime}=T_{\tau}^{abcd(G)}$ is also zero-
efficient, aside from simple exceptions.

  * •

There must be a well-defined choice of normal surfaces in $G$ that each
correspond to one of the four triangular or three quadrilateral pieces of a
normal surface in $\tau$. Similarly, there must be a well-defined choice of an
octagon piece, and some annulus pieces (discussed in Lemma 3.6), such that
local compatibility of these surfaces matches the local compatibility of
(almost) normal pieces. For example, we require that the triangle pieces in
$G$ are compatible with all other pieces.

This means that if $S$ is a normal surface in $T$, then there must exist some
normal surface $S^{\prime}$ in $T^{\prime}$ with identical normal coordinates
$\mathbf{S_{T\setminus\tau}}=\mathbf{S^{\prime}_{T^{\prime}\setminus G}}$
outside of $\tau$/$G$, where additionally $S$ is isotopic to $S^{\prime}$.
Similarly, the normal surfaces of $G$ chosen to represent (almost) normal
pieces should be sufficient to construct any almost normal surface of $T$,
aside from some manageable exceptions. That is, if a surface $S$ has an almost
normal piece in $\tau$, then for some (possibly distinct) tetrahedron
$\tau^{\prime}$ and some permutation $(a,b,c,d)$, there must exist a normal
surface $S^{\prime}$ in $T_{\tau^{\prime}}^{abcd(G)}$ where $S$ is isotopic to
$S^{\prime}$.

###  3.3 Choice of the Gadget

The requirements that the boundary of $G$ must be isomorphic to the boundary
of a tetrahedron, and that $G$ is homeomorphic to $B^{3}$, are both targeted
using Regina’s tricensus command, which generates a list of triangulations
satisfying given conditions.

To ensure that the chosen triangulation would have surfaces equivalent to
annulus or octagon pieces, a search of the fundamental normal surfaces was
conducted. Examining the boundary components of each surface for each
triangulation yielded a candidate for our gadget $G$.

We now denote the 5-tetrahedron triangulation with isomorphism signature (a
compact code used to uniquely generate triangulations in Regina)
‘fHLMabddeaaaa’ by $G$, or the gadget.

In version 7.x of Regina, the command Triangulation3(‘fHLMabddeaaaa’) can be
used to reconstruct our gadget. Table 1 provides the gluing instructions for
pairs of faces of the five tetrahedra. Here, ‘Face $abc$’ refers to the
triangular face that meets vertices $(a,b,c)$, and $k(abc)$ represents face
$abc$ of tetrahedron $k$.

Tetrahedron | Face 012 | Face 013 | Face 023 | Face 123
---|---|---|---|---
0 | 2 (012) | 1 (013) |  | 1 (123)
1 | 3 (012) | 0 (013) | 3 (023) | 0 (123)
2 | 0 (012) | 4 (013) | 4 (023) | 3 (123)
3 | 1 (012) |  | 1 (023) | 2 (123)
4 |  | 2 (013) | 2 (023) |
Table 1: Construction of the gadget.

Alternatively, Figure 8 provides a geometric description of the construction
of the gadget.

Figure 8: Geometric construction of $G$; an additional tetrahedron is glued in
each step.

The fundamental normal surfaces of $G$ are detailed below, along with their
index when generated by Regina. See Table 3 of Appendix B for details of their
normal coordinates. Boundary types are determined by observing the polygonal
boundary of each surface in the gadget, and determining its shape (e.g
triangular boundaries have three sides).

# bdry | Euler char. | Shape | Boundary types | Index
---|---|---|---|---
1 | -1 | One-punctured torus | Quad | 0, 3
1 | Octagon | Oct | 17, 18
Triangle | Tri | 7, 8, 10, 13
Quadrilateral | Quad | 2, 5, 6, 11, 12
2 | 0 | Annulus (non-parallel triangles) | Two tri | 1, 4, 16, 19
Annulus (quadrilateral, triangle) | Quad, tri | 9, 27
Annulus | Oct, tri | 15, 26
3 | -1 | Three-punctured sphere | Three tri | 14, 25
Three-punctured sphere | Quad, two tri | 23, 24, 28
Three-punctured sphere | Oct, two tri | 22
-3 | Three-punctured torus | Quad, two tri | 20
4 | -2 | Four-punctured sphere | Four tri | 21
Table 2: Fundamental normal surfaces of $G$, detailed by number of boundaries
(# bdry), Euler characteristic, topological description, boundary types and
their index.

We refer to the surface with index i by sf_i. Note that rows where multiple
indexes are listed simply represent instances of different orientations of the
same surface.

Next, we explore the surfaces in $G$ that correspond to normal and almost
normal pieces in a single tetrahedron $\tau$.

##### Triangles

The four triangular disc surfaces (sf_7, sf_8, sf_10, sf_13) are vertex links
in $G$, and are hence composed of triangle pieces only. These are isotopic to
the four triangular pieces we consider for a normal surface. Due to this, we
introduce the following more insightful names,

$G_{t_{0}}=\texttt{sf\\_13},\quad G_{t_{1}}=\texttt{sf\\_10},\quad
G_{t_{2}}=\texttt{sf\\_8},\quad G_{t_{3}}=\texttt{sf\\_7}.$

##### Quadrilaterals

The three quadrilateral pieces in $\tau$ are each isotopic to at least one of
the quadrilateral surfaces in the gadget (sf_2, sf_5, sf_6, sf_11, sf_12).

Surfaces sf_2 and sf_12 both represent quad_03/12. However, surface sf_12 is
not locally compatible with the annulus tri_3:quad_03/12 (that is, sf_9) –
this is undesired, so we choose surface sf_2 to represent this quadrilateral.

Similarly, surfaces sf_5 and sf_11 both represent quad_02/13. Without loss of
generality, we arbitrarily choose surface sf_5 to represent this
quadrilateral. So, we introduce the following names,

$G_{q_{01/23}}=\texttt{sf\\_6},\quad G_{q_{02/13}}=\texttt{sf\\_2},\quad
G_{q_{03/12}}=\texttt{sf\\_5}.$

######  Corollary 3.1.

With this construction, for a normal surface $S$ in a triangulation $T$, we
can choose a normal surface $S^{\prime}$ in $T^{\prime}=T_{\tau}^{abcd(G)}$
where in $G\subset T^{\prime}$, $S^{\prime}_{G}$ has normal coordinates

$\mathbf{S^{\prime}_{G}}=t_{0}\mathbf{G_{t_{a}}}+t_{1}\mathbf{G_{t_{b}}}+t_{2}\mathbf{G_{t_{c}}}+t_{3}\mathbf{G_{t_{d}}}+q_{01/23}\mathbf{G_{q_{ab/cd}}}+q_{02/13}\mathbf{G_{q_{ac/bd}}}+q_{03/12}\mathbf{G_{q_{ad/bc}}},$

where
$\mathbf{S_{\tau}}=(t_{0},t_{1},t_{2},t_{3},q_{01/23},q_{02/13},q_{03/12})$
are the normal coordinates of $S$ in $\tau$. Hence, $S$ is isotopic to
$S^{\prime}$.

##### Annuli and Octagons

Among the normal surfaces in the gadget, we also have candidates for almost
normal pieces. Namely, sf_17 and sf_18 are both discs with octagonal boundary,
and we declare that

$G_{O_{02/13}}=\texttt{sf\\_18},\quad G_{O_{03/12}}=\texttt{sf\\_17}.$

Finally, with the presence of four different annulus pieces between non-
parallel triangles, and two of triangle-quadrilateral type, we choose

$G_{t_{0}}^{t_{2}}=\texttt{sf\\_19},\,\,\,G_{t_{0}}^{t_{3}}=\texttt{sf\\_16},\,\,\,G_{t_{1}}^{t_{2}}=\texttt{sf\\_1},\,\,\,G_{t_{1}}^{t_{3}}=\texttt{sf\\_4},\,\,\,G_{t_{0}}^{q_{03/12}}=\texttt{sf\\_27},\,\,\,G_{t_{3}}^{q_{03/12}}=\texttt{sf\\_9}.$

Note that parallel annuli are missing from $G$, this will be discussed later.

###  3.4 Verifying Requirements

With the normal and almost normal pieces of the gadget identified, we now show
that our choice of $G$ satisfies the properties discussed in Section 3.2.

######  Observation 3.2.

The sum of any two fundamental normal surfaces in $G$ can be expressed as the
sum of pairwise disjoint fundamental surfaces. This can be verified in Regina.

Note that this is not true for all triangulations, as in general the connected
components of a normal surface $A+B$ may include non-fundamental surfaces.

######  Lemma 3.3.

Any normal surface in the gadget can be expressed as a sum of pairwise
disjoint fundamental normal surfaces.

The approach we take is to express any normal surface as the sum of connected
fundamental surfaces, by repeatedly using Observation 3.2 on pairs of
intersecting surfaces, allowing us to rewrite this surface in a way that has
fewer intersections between its summands.

###### Proof.

Let $U=\sum_{i=1}^{k}U_{i}$ be a normal surface in the gadget, where each
$U_{i}$ is a fundamental normal surface (not necessarily distinct) and
consider the set $\Omega=\\{U_{i}:i=1,\cdots,k\\}$. Let $I$ represent the
total number of intersection curves between these surfaces, noting that
surfaces intersect transversely. In particular, we may ‘push’ components of
$U$ so that no two intersection curves meet within $G$.

Now, take two surfaces $A,B\in\Omega$ that are not disjoint. By Observation
3.2, in the Haken sum of $A$ and $B$, we find $A+B=\sum S_{i}$ where $S_{i}$
are pairwise disjoint fundamental normal surfaces. Consider some curve
$\gamma$ in $A\cap B$. Within a small open regular neighbourhood of $\gamma$,
$N(\gamma)$, a regular exchange is performed as in Figure 3, such that all
intersections resolve to normal discs, as in Figure 4. This decreases the
number of intersections $I$ by $1$ for each $\gamma$.

We have verified that resolving the intersections of $A+B$ does not increase
$I$. Now, we must check that any intersections with any additional surfaces
are not created.

Take some surface $C\in\Omega$ that intersects $A$ and/or $B$. Each curve in
$A\cap C$ or $B\cap C$ is outside of the regions $\bigcup_{\gamma_{i}\in A\cap
B}N(\gamma_{i})$, so evaluating $A+B$ does not create any new intersections
between $C$ and any component $S_{i}$. In fact, the sets of intersection
curves $(A\cap C)\cup(B\cap C)=\bigcup_{S_{i}\in A+B}(S_{i}\cap C)$ are equal.
So, $I$ is strictly decreasing.

We may continue this process again for some new pair of intersecting,
fundamental surfaces, until $I=0$ and we have a collection of disjoint,
fundamental surfaces. ∎

######  Theorem 3.4.

Let $T$ be a zero-efficient triangulation of a 3-manifold which is not
$\mathbb{S}^{3}$, $\mathbb{R}P^{3}$ or $L(3,1)$. Remove some tetrahedron
$\tau$ from $T$ and replace it with $G$ according to some permutation
$(a,b,c,d)$. Then the resulting triangulation $T^{\prime}:=T_{\tau}^{abcd(G)}$
is also zero-efficient.

###### Proof.

According to Proposition 5.1 of [10], because $T$ is zero-efficient and not
$\mathbb{S}^{3}$, $\mathbb{R}P^{3}$ or $L(3,1)$, it is a one-vertex
triangulation. As $\tau$ and $G$ have the same number of vertices,
$T^{\prime}$ is a one-vertex triangulation.

So, we suppose that $T$ is zero-efficient, but $T^{\prime}$ is not. That is,
suppose that $T^{\prime}$ has some non-vertex-linking normal 2-sphere $S$. By
Lemma 3.3, the connected components of $S_{G}$ are all fundamental normal
surfaces as described in Table 2 – excluding sf_0, sf_3, sf_20, which have
genus $1$. Now, consider embedding $S$ into $T$ to form the surface
$S^{\prime}$, so that in tetrahedron $\tau$ we have that $S^{\prime}_{\tau}$
is isotopic to $S_{G}$. This is not necessarily a normal surface, so we
attempt to normalise it. As $S^{\prime}$ is a sphere, any tubed piece within
$\tau$ may be cut and ‘capped’ (see Section 2.4), cutting $S^{\prime}$ into
two spheres. In particular, we find an inner-most tube in $S^{\prime}_{\tau}$,
and cut and cap it as in Figure 9.

Figure 9: Cutting and then capping an inner-most tube

As we repeat this process, we form $\bar{S^{\prime}}$, a collection of
spheres, with $\partial\bar{S^{\prime}}_{\tau}=\partial S_{G}$. The components
of $\bar{S^{\prime}}_{\tau}$ are triangles, plus possibly either octagons or
quadrilaterals (but not both as they are not locally compatible).

If $\bar{S^{\prime}}$ has one or more octagon piece, then we normalise all but
one octagon by pushing them towards adjacent tetrahedra (see Figure 6 in
Section 2.4). Now, since exactly one octagon remains, $\bar{S^{\prime}}$ has a
component that is an almost normal sphere in $T$. From Proposition 5.12 of
[10], this means $T$ must be $\mathbb{S}^{3}$ – but this contradicts our
assumptions about $T$.

Now, if $\bar{S^{\prime}}$ has quadrilaterals but no octagons, then it has a
component that is a normal 2-sphere in $T$ which is not vertex linking. This
contradicts $T$ being zero-efficient.

Finally, consider the case where $\bar{S^{\prime}}$ has only triangular
pieces. As we assumed that $S$ is not vertex linking, then $S_{G}$ must have
had at least one copy of an annulus between triangles. But, as $T^{\prime}$ is
a one-vertex triangulation, this means that $S$ had genus $>1$, as each tube
essentially adds a handle to a vertex linking sphere formed from the remaining
triangles. But, then $S$ is not a sphere, so we again find a contradiction.

In each case, we have reached a contradiction to the assumption that
$T^{\prime}$ is not zero-efficient. Hence, we can conclude that the gadget
preserves zero-efficiency.

∎

Now, we address the parallel annulus types that are not captured by the
gadget, and show why this exceptional case is harmless for algorithms such as
computing Heegaard genus.

######  Observation 3.5.

Suppose $S$ is an almost normal surface in some closed triangulation $T$. If
the almost normal piece in $S$ is an annulus in tetrahedron $\tau$, then on
any face of $\tau$ that intersects the annulus twice, the annulus may be
isotoped (‘pushed across’) to the adjacent tetrahedron.

For example, consider such a case in Figure 10.

Figure 10: An annulus piece between a triangle and quadrilateral is pushed
into a neighbouring tetrahedron, as an annulus between two non-parallel
triangles.

The normal discs in the adjacent tetrahedron need not be the same type, as in
Figure 10.

Whether pairs of boundary curves constrained to the shared face are parallel
determines what annulus piece may appear in this adjacent tetrahedron. Which
face the tube is pushed towards determines which annulus may appear in the
adjacent tetrahedron.

######  Lemma 3.6.

Let $S$ be a connected, almost normal surface in a closed, orientable
triangulation $T$ (which is not the 3-sphere). Suppose it has an annulus piece
of parallel triangle or quadrilateral type in some tetrahedron $\tau$. Then,
one of the following holds:

  1. 1.

$S$ is isotopic to an almost normal surface $S^{\prime}$ with a non-parallel
boundary type annulus in some (possibly different) tetrahedron
$\tau^{\prime}$;

  2. 2.

$S$ does not represent a minimal Heegaard splitting;

  3. 3.

$S$ is the orientable double cover of some non-orientable surface $U_{no}$
with a tube connecting the two sheets that cover some local region of
$U_{no}$.

###### Proof.

Suppose we have a surface $S$ with an annulus of either parallel-triangle or
parallel-quadrilateral type. We attempt to push the tube from tetrahedron to
tetrahedron until reaching a non-parallel annulus type. If successful, this
proves Case 1.

If a non-parallel piece cannot be found, then our surface must either be two
parallel copies of an orientable surface $U_{o}$, or the orientable double
cover of a non-orientable surface $U_{no}$, in both cases with a tube
connecting its two sheets. The non-orientable case is simply Case 3, which
will be discussed after the proof.

Suppose that $S$ realises a Heegaard splitting of genus $g$ and therefore $S$
has Euler characteristic $\chi(S)=2-2g$.

If $S=U_{o}\\#U_{o}$ where $U_{o}$ is orientable and separating, then $U_{o}$
has Euler characteristic $\chi(U_{o})=2-g$ and $U_{o}$ splits the
triangulation into 3-manifolds $X$ and $Y$ where $\partial X=\partial
Y=U_{o}$. Refer to Figure 11. Now, consider the 3-manifold $Z$ bounded by
$S=U_{o}\\#U_{o}$, wedged between the two copies of $U_{o}$. As
$\chi(U_{o}\\#U_{o})=\chi(S)=2-2g$ for the Heegaard splitting $S$, $Z$ has
genus $g$. To the other side of $S$ is the 3-manifold $X\asymp Y$, which is
$X$ connected to $Y$ by a solid tube. As $S$ is a Heegaard splitting, $X\asymp
Y$ must also be a handlebody of genus $g$. But, then $X$ and $Y$ are both
handlebodies of genus $\frac{g}{2}$ (because they are both bounded
individually by the genus $g$ surface $U_{o}$), so $U_{o}$ is a Heegaard
splitting of genus $\frac{g}{2}$. Hence, $S$ is not a minimal Heegaard
splitting (unless $g=0$, but $T$ is not the 3-sphere).

Figure 11: An orientable surface $U_{o}$ divides the 3-manifold into $X$ and
$Y$. Two copies of $U_{o}$, tubed together, form $S=U_{o}\\#U_{o}$ which
divide the 3-manifold into $Z$ and $X\asymp Y$.

Finally, if $S=U_{o}\\#U_{o}$ but $U_{o}$ is non-separating, then cutting $T$
along $S$ yields a 3-manifold $X$ with a properly embedded disc (slicing
through the tube) that separates $\partial X$ but not $X$. Therefore $X$ is
not a handlebody and $S$ is not a Heegaard splitting, giving us Case 2.

∎

Consider Case 3 of the previous lemma. We abuse notation and let
$S=U_{no}\asymp U_{no}$ represent the orientable double cover of $U_{no}$ with
a tube connecting its two sheets. Cutting the triangulation $T$ along $U_{no}$
yields the 3-manifold $X$ with $\partial X=S$. Since $S$ cuts $T$ into two
handlebodies of genus $g$, it follows that $X$ is just one of these
handlebodies with one of its handles cut. That is, $X$ is a handlebody with
genus $g-1$. Such a case can be detected by searching for surfaces with Euler
characteristic $\chi(U_{no})=\frac{1}{2}\chi(S)+1$ which cut the triangulation
into one genus $g-1$ handlebody.

######  Corollary 3.7.

For an almost normal surface $S$ that realises a minimal Heegaard splitting of
a triangulation $T$, one of the following holds:

  1. 1.

There exists a gluing of the gadget into $T$ to form
$T^{\prime}=T_{\tau}^{abcd(G)}$ for some permutation $(a,b,c,d)$ and some
tetrahedron $\tau$, and there exists a normal surface $S^{\prime}$ in
$T^{\prime}$ that is isotopic to $S$;

  2. 2.

$S$ is of the type of Case 3 in Lemma 3.6.

###### Proof.

Suppose that $S$ is an almost normal surface in a triangulation $T$, with its
almost normal piece in tetrahedron $\tau$.

There are twelve rotational symmetries of a tetrahedron (twelve even
permutations of its vertices), and hence twelve possible triangulations that
may be formed for each tetrahedron.

We may transform the coordinates of the normal pieces as in Corollary 3.1.

If the almost normal piece of $S$ is an annulus between parallel triangles or
quadrilaterals, then we attempt to push this tube across the tetrahedra until
reaching a non-parallel annulus piece, and apply the gadget accordingly. If
this is unsuccessful, then $S$ must be the orientable double cover of some
non-orientable normal surface $U_{no}$ with a tube connecting its two sheets,
as in Case 3 of Lemma 3.6. Then, to determine if $S$ is a genus $g$ Heegaard
splitting, simply cut along $U_{no}$ and check, via the algorithm for
handlebody recognition [7], whether the resulting manifold is a genus $g-1$
handlebody.

Now, if the almost normal piece of $S$ is an octagon or a non-parallel annulus
piece, then we seek to construct a surface in $T_{\tau}^{abcd(G)}$ for some
permutation of the vertices of $\tau$ into $G$, $(0,1,2,3)\mapsto(a,b,c,d)$.

As the gadget has two distinct triangle-quadrilateral annulus pieces of a
total possible twelve, each permutation of the gadget can represent two
distinct annuli of this type. Hence, we only need to try six possible
permutations. We choose the following,

$(0,1,2,3),\quad(0,3,1,2),\quad(1,0,3,2),\quad(1,2,0,3),\quad(2,0,1,3),\quad(3,1,0,2).$

This choice of permutation allows us to ‘rotate’ the required octagon or
annulus piece of $G$ into the same position as the one in $\tau$. Refer to
Appendix C for the specific choices of individual almost normal pieces.

∎

###  3.5 Implementations

In practice, as there is no current implementation of annulus pieces in
Regina, we cannot directly normalise an almost normal surface using the
gadget. Instead, we need to consider all normal surfaces from all possible
triangulations resulting from gluing the gadget into any tetrahedron.

With the gadget, Heegaard splittings can now always be represented by normal
surfaces. However, these surfaces are not necessarily fundamental. Therefore
we use the gadget to generate a set of candidate surfaces for each potential
value of genus; this set will be finite, due to Euler characteristic being
additive under Haken sum. We discuss this process further in Section 4.

####  3.5.1 Method 1: Generating All Surfaces

For each tetrahedron $\tau$ in a triangulation $T$, form $T_{\tau}^{abcd(G)}$
for the six distinct permutations (see the proof of Corollary 3.7), and then
generate all fundamental normal surfaces in it. For a triangulation with $n$
tetrahedra, this means $6n$ sets of normal surfaces must be enumerated. This
represents almost normal surfaces that may be embedded in $T$, as well as many
others (which use surfaces of the gadget that are not tubes, octagons,
triangles or quadrilaterals).

Denote the running time for generating normal surfaces for a triangulation
with $n$ tetrahedra by $T(n)$, and let $C(n)$ represent the number of normal
surfaces for such a triangulation. From Section 2.5,
$T(n)\in\mathcal{O}(1.934^{n})$ and $C(n)\in\mathcal{O}(1.503^{n})$. Suppose
that the running time of the algorithm to check if a surface is a Heegaard
splitting has running time $f(n)$. Then, to generate and test each surface in
the $6n$ triangulations, we find a running time on the order of
$M_{1}(n)=6n(T(n+4)+C(n+4)f(n))=6n(1.934^{n+4}+1.503^{n+4}f(n))$.

####  3.5.2 Method 2: Constructing Each Annulus

Alternatively, we have developed a method to form the necessary set of almost
normal surfaces using an existing set of fundamental normal surfaces for the
base triangulation.

Let $\Omega$ be the set of fundamental normal surfaces for a triangulation
$T$. For each surface $S\in\Omega$, we form a set of almost normal surfaces
with an annulus piece between triangles and/or quadrilaterals in $S$ as
follows. For each tetrahedron $\tau$, if $S_{\tau}$ has at least two triangles
on different vertices, then we consider the surface with an annulus between
two of these triangles. Similarly, if $S_{\tau}$ has at least one triangle and
at least one quadrilateral, we consider the surface with an annulus between
these. In either case, we determine which annulus type from the gadget is
necessary, and under which permutation, and construct the new surface within
$T^{\prime}=T_{\tau}^{abcd(G)}$. As we begin with a set of normal surfaces
(that is, they are not already ‘tubed’), when we form the equivalent surface
in $T^{\prime}$, we must add the coordinates for the annulus piece to the
coordinates for each triangle or quadrilateral excluding those corresponding
to the boundaries of the annulus.

For example, in Figure 12, $S_{\tau}$ has coordinates $(1,0,0,2,0,0,1)$ and
supports several annulus types, such as one connecting a triangle to its
quadrilateral. Using the identity permutation, we find that
$G_{t_{3}}^{q_{03/12}}$ gives us the annulus between tri_3:quad_03/12. Then,
the remaining triangle pieces are represented using $G_{t_{0}}$ and
$G_{t_{3}}$.

Figure 12: A surface with coordinates $(1,0,0,2,0,0,1)$ in a tetrahedron, and
its ‘tubing’.

A complete guide to our choice of permutations and coordinates is given in
Appendix C.

Now, using the same results from Section 2.5, the running time for this method
is on the order of $M_{2}(n)=T(n)+C(n)*6n*f(n)=1.934^{n}+6n\times
1.503^{n}f(n)$, as there are at most six annulus types that could exist in any
given tetrahedron.

##### Performance Comparison

In our discussion of the two methods, we found
$M_{1}(n)\in\mathcal{O}(6n(1.934^{n+4}+1.503^{n+4}f(n)))$ and
$M_{2}(n)\in\mathcal{O}(1.934^{n}+6n\times 1.503^{n}f(n))$, where $f(n)$ is
the time to test if a given surface is a Heegaard splitting. Asymptotically
$M_{2}(n)\sim 6n\times 1.934^{4}\times M_{1}(n)$, and so we expect method 2 to
be significantly faster than method 1.

##### Generating All Surfaces with Method 2

In Method 2 (Section 3.5.2), we described how a non-parallel annulus of an
almost normal surface can be converted into a normal surface using the gadget.
Here, we justify that this method produces all the candidate almost normal
surfaces that may represent a minimal Heegaard splitting. First, suppose that
almost normal surfaces with octagon pieces have been considered already (i.e.
have been tested as Heegaard splittings). Now, any almost normal surface with
an annulus piece has such an annulus ‘tubing’ together two triangles and/or
quadrilaterals.

Suppose $S$ is an orientable fundamental almost normal surface with Euler
characteristic $\chi(S)<0$, with a non-parallel annulus in some tetrahedron
$\tau$. Let $\bar{S}$ be the surface generated by cutting and capping the
annulus. Of course, $\chi(\bar{S})=\chi(S)+2$ and $\bar{S}$ is a normal
surface, but is not necessarily fundamental, so $\bar{S}=\sum_{i}A_{i}$ for
some fundamental normal surfaces $A_{i}$. The annulus of $S$ either connects
two components in $\tau$ of a particular $A_{i}$, or connects two components
between $A_{j}$ and $A_{k}$ for $j\neq k$. We can generate all tubings of
$A_{i}$ to itself by constructing tubes as in Section 3.5.2. Similarly, we can
generate tubings of $A_{j}+A_{k}$.

Now, if $S$ has a parallel annulus piece, then either it is of the type of
Case 3 in Lemma 3.6, or $S$ will not represent a minimal Heegaard splitting,
or it is isotopic to some $S^{\prime}$ with a non-parallel annulus.

In practice, this results in the following method for detecting a splitting of
genus $g$.

  1. 1.

Generate the set $\Omega_{AN}$ of all fundamental almost normal surfaces of a
triangulation $T$ in Regina, test if those with genus $g$ are Heegaard
splittings. If not, generate the set of fundamental normal surfaces,
$\Omega_{N}$.

  2. 2.

For each tetrahedron, for each orientable surface of genus $g-1$ in
$\Omega_{N}$, form all tubings.

  3. 3.

For each tetrahedron, for each set of locally compatible surfaces in
$\Omega_{N}$ whose Euler characteristics sum to $2-2(g-1)$, form all tubings.

  4. 4.

Test all tubed surfaces as Heegaard splittings.

Note that constructing a tube increases the Euler characteristic of a surface
by 2, which is equivalent to increasing the genus of a connected surface by 1.

##  4 Computing Heegaard Genus

As discussed in Section 2.6, a result of Rubinstein declares that Heegaard
splittings are given by $S=S_{an}+S_{t}$ where $S_{an}$ is almost normal,
$S_{t}$ is normal, $\chi(S_{an})<0$ and $\chi(S_{t})=0$ [19]. So, to determine
if a triangulation has a genus $g$ Heegaard splitting, all such surfaces where
$\chi(S_{an})=2-2g$ must be tested as splittings. Furthermore, we know that
every summand of $S_{an}$ must have negative Euler characteristic, and every
summand of $S_{t}$ has zero Euler characteristic. Hence, there are finitely
many cases to consider of $S_{an}$ as their Euler characteristic must
represent an integer partition of $2-2g$. We can generate these using normal
and almost normal surfaces in Regina with octagon pieces, or by constructing
tubed surfaces as in Section 3.5.2.

For the torus piece $S_{t}$, as Euler characteristic is additive under Haken
sum, this could theoretically require an unbounded number of different sums of
tori. However, from Lemma 5.1 of [2], we know that if $S$ is a normal surface
and $A$ is an edge-linking torus, then $S+A$ is either disconnected or is
isotopic to $S$, so need not be considered in summands of $S_{t}$. Tentatively
and naively, we therefore consider splittings as $S=S_{an}$ only. If there are
non-edge-linking tori present, this means we may not see our splitting, and so
in such settings we can only form an upper bound on the genus. Experimentally,
edge-linking tori do form the majority of tori in the cases we have tested,
and in those cases that remain, we can attempt to form a lower bound using
algebraic techniques as in Section 2.6.

We have tested this approach on all orientable triangulations in the closed
hyperbolic census of Hodgson and Weeks (in [9]) – all of which are zero-
efficient. We first search for a genus 2 splitting, and if one does not exist,
search for a genus 3 splitting (then 4, etc). Of the 3,000 triangulations in
this census, 44 had $\mathrm{rank}(H_{1}(M))=3$, and genus 3 splittings were
found. Then, 2,661 had $\mathrm{rank}(H_{1}(M))\leq 2$, and genus 2 splittings
were found. For each of the remaining 295, an exhaustive search of genus 2
surfaces (without tori) found no splittings, but genus 3 splittings were
found. In these 295 cases, we cannot guarantee they have genus 3, but merely
provide an informed upper bound.

## References

  * [1] David Bachman, Ryan Derby-Talbot, and Eric Sedgwick.  Computing Heegaard genus is NP-hard.  In A journey through discrete mathematics, pages 59–87. Springer, Cham, 2017.
  * [2] Birch Bryant, William Jaco, and J. Hyam Rubinstein.  Efficient triangulations and boundary slopes.  Topology Appl., 297:Paper No. 107689, 18, 2021.  doi:10.1016/j.topol.2021.107689.
  * [3] Benjamin A. Burton.  The complexity of the normal surface solution space.  In Computational geometry (SCG’10), pages 201–209. ACM, New York, 2010.  doi:10.1145/1810959.1810995.
  * [4] Benjamin A. Burton.  A new approach to crushing 3-manifold triangulations.  In Computational geometry (SoCG’13), pages 415–423. ACM, New York, 2013.  doi:10.1145/2462356.2462409.
  * [5] Benjamin A. Burton.  Enumerating fundamental normal surfaces: Algorithms, experiments and invariants.  In ALENEX 2014: Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, pages 112–124. SIAM, 2014.
  * [6] Benjamin A. Burton, Ryan Budney, William Pettersson, et al.  Regina: Software for low-dimensional topology.  http://regina-normal.github.io/, 1999–2023.
  * [7] Benjamin A. Burton and Alexander He.  Finding large counterexamples by selectively exploring the Pachner graph.  In 39th International Symposium on Computational Geometry, volume 258 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 21, 16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2023.  doi:10.4230/lipics.socg.2023.21.
  * [8] Bradd Clark.  The Heegaard genus of manifolds obtained by surgery on links and knots.  Internat. J. Math. Math. Sci., 3(3):583–589, 1980.  doi:10.1155/S0161171280000440.
  * [9] Craig D. Hodgson and Jeffrey R. Weeks.  Symmetries, isometries and length spectra of closed hyperbolic three-manifolds.  Experiment. Math., 3(4):261–274, 1994.  URL: http://projecteuclid.org/euclid.em/1048515809.
  * [10] William Jaco and J. Hyam Rubinstein.  $0$-efficient triangulations of 3-manifolds.  J. Differential Geom., 65(1):61–168, 2003.  URL: http://projecteuclid.org/euclid.jdg/1090503053.
  * [11] Klaus Johannson.  Heegaard surfaces in Haken $3$-manifolds.  Bull. Amer. Math. Soc. (N.S.), 23(1):91–98, 1990.  doi:10.1090/S0273-0979-1990-15910-5.
  * [12] Marc Lackenby.  An algorithm to determine the Heegaard genus of simple 3-manifolds with nonempty boundary.  Algebr. Geom. Topol., 8(2):911–934, 2008.  doi:10.2140/agt.2008.8.911.
  * [13] Tao Li.  An algorithm to determine the Heegaard genus of a 3-manifold.  Geom. Topol., 15(2):1029–1106, 2011.  doi:10.2140/gt.2011.15.1029.
  * [14] Tao Li.  Rank and genus of 3-manifolds.  J. Amer. Math. Soc., 26(3):777–829, 2013.  doi:10.1090/S0894-0347-2013-00767-5.
  * [15] Edwin E. Moise.  Affine structures in $3$-manifolds. V. The triangulation theorem and Hauptvermutung.  Ann. of Math. (2), 56:96–114, 1952.  doi:10.2307/1969769.
  * [16] Kanji Morimoto.  On Heegaard splittings of knot exteriors with tunnel number degenerations.  Topology Appl., 196:719–728, 2015.  doi:10.1016/j.topol.2015.05.042.
  * [17] G. D. Mostow.  Quasi-conformal mappings in $n$-space and the rigidity of hyperbolic space forms.  Inst. Hautes Études Sci. Publ. Math., (34):53–104, 1968.  URL: http://www.numdam.org/item?id=PMIHES_1968__34__53_0.
  * [18] William Pettersson and Benjamin A. Burton.  ”Normalise” AlmostNormal surfaces, 2017.  URL: https://github.com/regina-normal/regina/issues/33.
  * [19] J. H. Rubinstein.  Polyhedral minimal surfaces, Heegaard splittings and decision problems for $3$-dimensional manifolds.  In Geometric topology (Athens, GA, 1993), volume 2 of AMS/IP Stud. Adv. Math., pages 1–20. Amer. Math. Soc., Providence, RI, 1997\.  doi:10.1090/amsip/002.1/01.
  * [20] Joachim H. Rubinstein.  An algorithm to recognize the $3$-sphere.  In Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994), pages 601–611. Birkhäuser, Basel, 1995.
  * [21] Nikolai Saveliev.  Lectures on the topology of 3-manifolds.  De Gruyter Textbook. Walter de Gruyter & Co., Berlin, revised edition, 2012.  An introduction to the Casson invariant.
  * [22] Z. Sela.  The isomorphism problem for hyperbolic groups. I.  Ann. of Math. (2), 141(2):217–283, 1995.  doi:10.2307/2118520.
  * [23] Abigail Thompson.  Thin position and the recognition problem for $S^{3}$.  Math. Res. Lett., 1(5):613–630, 1994.  doi:10.4310/MRL.1994.v1.n5.a9.
  * [24] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors.  SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.  Nature Methods, 17:261–272, 2020.  doi:10.1038/s41592-019-0686-2.

##  Appendix A Running Time Computations

Of the first 3000 triangulations in the Hodgson-Weeks Closed Hyperbolic Census
in Regina, fundamental normal surfaces were generated for the 2974
triangulations with at most 23 tetrahedra. The number of surfaces and
enumeration time were recorded. These tests were run on an 8-core CPU with
16GB RAM.

Using curve_fit in SciPy [24], we fit linear models to $(n,\log_{10}(T))$ and
$(n,\log_{10}(S)$ where $n$ is the number of tetrahedra, $T$ is the running
time and $S$ is the number of normal surfaces. We found
$\log_{10}(T)=0.2866n-4.2309$ with $R^{2}=0.8363$ for the enumeration time,
and $\log_{10}(S)=0.1771n-0.3887$ with $R^{2}=0.8384$ for the number of
surfaces. Equivalently, $T\approx 5.9\times 10^{-5}1.934^{n}$ and $S\approx
0.41\times 1.503^{n}$. By this, we may estimate that
$T(n)\in\mathcal{O}(1.934^{n})$ and $C(n)\in\mathcal{O}(1.503^{n})$.

Figure 13: Data plotted with the exponential model for the enumeration time
(left) and number of surfaces (right).

##  Appendix B Fundamental Normal Surfaces of the Gadget

The coordinates of the surfaces introduced in Table 2 are detailed below. The
coordinates and order of the surfaces are as produced in version 7.3 of
Regina, for the triangulation with isomorphism signature ‘fHLMabddeaaaa’. To
replicate these surfaces in Regina, use the command
NormalSurfaces(Triangulation3(‘fHLMabddeaaaa’), NS_STANDARD, NS_FUNDAMENTAL).

Surface | Coordinates
---|---
sf_0 | $(0,0,0,0,0,0,1,\,\,\,0,0,0,0,0,0,1,\,\,\,0,0,0,0,0,0,1,\,\,\,0,0,0,0,0,0,1,\,\,\,0,0,0,0,0,0,1)$
sf_1 | $(0,0,0,0,0,0,1,\,\,\,0,0,0,0,0,0,1,\,\,\,0,0,0,0,0,0,1,\,\,\,0,0,0,0,0,0,1,\,\,\,0,1,1,0,0,0,0)$
sf_2 | $(0,0,0,0,0,0,1,\,\,\,0,0,0,0,0,0,1,\,\,\,1,0,0,1,0,0,0,\,\,\,0,0,0,0,0,0,1,\,\,\,1,0,0,1,0,0,0)$
sf_3 | $(0,0,0,0,0,1,0,\,\,\,0,0,0,0,0,1,0,\,\,\,0,0,0,0,0,1,0,\,\,\,0,0,0,0,0,1,0,\,\,\,0,0,0,0,0,1,0)$
sf_4 | $(0,0,0,0,0,1,0,\,\,\,0,0,0,0,0,1,0,\,\,\,0,1,0,1,0,0,0,\,\,\,0,1,0,1,0,0,0,\,\,\,0,1,0,1,0,0,0)$
sf_5 | $(0,0,0,0,0,1,0,\,\,\,1,0,1,0,0,0,0,\,\,\,0,0,0,0,0,1,0,\,\,\,1,0,1,0,0,0,0,\,\,\,0,0,0,0,0,1,0)$
sf_6 | $(0,0,0,0,1,0,0,\,\,\,0,0,0,0,1,0,0,\,\,\,0,0,0,0,1,0,0,\,\,\,0,0,0,0,1,0,0,\,\,\,0,0,0,0,1,0,0)$
sf_7 | $(0,0,0,1,0,0,0,\,\,\,0,0,0,1,0,0,0,\,\,\,0,0,0,1,0,0,0,\,\,\,0,0,0,1,0,0,0,\,\,\,0,0,0,1,0,0,0)$
sf_8 | $(0,0,1,0,0,0,0,\,\,\,0,0,1,0,0,0,0,\,\,\,0,0,1,0,0,0,0,\,\,\,0,0,1,0,0,0,0,\,\,\,0,0,1,0,0,0,0)$
sf_9 | $(0,0,1,0,0,1,0,\,\,\,0,0,1,0,0,1,0,\,\,\,0,1,1,1,0,0,0,\,\,\,0,1,1,1,0,0,0,\,\,\,0,0,0,1,0,0,1)$
sf_10 | $(0,1,0,0,0,0,0,\,\,\,0,1,0,0,0,0,0,\,\,\,0,1,0,0,0,0,0,\,\,\,0,1,0,0,0,0,0,\,\,\,0,1,0,0,0,0,0)$
sf_11 | $(0,1,0,1,0,0,0,\,\,\,0,1,0,1,0,0,0,\,\,\,0,0,0,0,0,1,0,\,\,\,0,0,0,0,0,1,0,\,\,\,0,0,0,0,0,1,0)$
sf_12 | $(0,1,1,0,0,0,0,\,\,\,0,1,1,0,0,0,0,\,\,\,0,1,1,0,0,0,0,\,\,\,0,1,1,0,0,0,0,\,\,\,0,0,0,0,0,0,1)$
sf_13 | $(1,0,0,0,0,0,0,\,\,\,1,0,0,0,0,0,0,\,\,\,1,0,0,0,0,0,0,\,\,\,1,0,0,0,0,0,0,\,\,\,1,0,0,0,0,0,0)$
sf_14 | $(1,0,0,0,0,1,0,\,\,\,1,0,0,0,0,1,0,\,\,\,0,1,0,0,0,0,1,\,\,\,1,1,0,1,0,0,0,\,\,\,0,1,0,0,0,0,1)$
sf_15 | $(1,0,0,0,0,1,0,\,\,\,1,0,0,0,0,1,0,\,\,\,0,1,0,0,0,0,1,\,\,\,1,1,0,1,0,0,0,\,\,\,0,2,1,0,0,0,0)$
sf_16 | $(1,0,0,1,0,0,0,\,\,\,1,0,0,1,0,0,0,\,\,\,0,0,0,0,0,0,1,\,\,\,1,0,0,1,0,0,0,\,\,\,0,0,0,0,0,0,1)$
sf_17 | $(1,0,0,1,0,0,0,\,\,\,1,0,0,1,0,0,0,\,\,\,0,0,0,0,0,0,1,\,\,\,1,0,0,1,0,0,0,\,\,\,0,1,1,0,0,0,0)$
sf_18 | $(1,0,1,0,0,0,0,\,\,\,0,0,0,0,0,1,0,\,\,\,1,0,0,1,1,0,0,\,\,\,0,1,0,1,0,0,0,\,\,\,1,0,0,1,1,0,0)$
sf_19 | $(1,0,1,0,0,0,0,\,\,\,0,0,0,0,0,1,0,\,\,\,1,0,1,0,0,0,0,\,\,\,0,0,0,0,0,1,0,\,\,\,1,0,1,0,0,0,0)$
sf_20 | $(1,0,1,0,0,1,0,\,\,\,0,0,0,0,0,2,0,\,\,\,0,1,1,0,0,0,1,\,\,\,0,1,0,1,0,1,0,\,\,\,0,0,0,0,0,0,2)$
sf_21 | $(1,0,1,0,0,1,0,\,\,\,0,0,0,0,0,2,0,\,\,\,0,1,1,0,0,0,1,\,\,\,0,1,0,1,0,1,0,\,\,\,0,1,1,0,0,0,1)$
sf_22 | $(1,0,1,0,0,1,0,\,\,\,0,0,0,0,0,2,0,\,\,\,0,1,1,0,0,0,1,\,\,\,0,1,0,1,0,1,0,\,\,\,0,2,2,0,0,0,0)$
sf_23 | $(1,0,1,0,0,1,0,\,\,\,0,0,0,0,0,2,0,\,\,\,1,1,1,1,0,0,0,\,\,\,0,1,0,1,0,1,0,\,\,\,1,0,0,1,0,0,1)$
sf_24 | $(1,0,1,0,0,1,0,\,\,\,1,0,1,0,0,1,0,\,\,\,0,1,1,0,0,0,1,\,\,\,1,1,1,1,0,0,0,\,\,\,0,0,0,0,0,0,2)$
sf_25 | $(1,0,1,1,0,0,0,\,\,\,0,0,0,1,0,1,0,\,\,\,0,0,1,0,0,0,1,\,\,\,0,0,0,1,0,1,0,\,\,\,0,0,1,0,0,0,1)$
sf_26 | $(1,0,1,1,0,0,0,\,\,\,0,0,0,1,0,1,0,\,\,\,0,0,1,0,0,0,1,\,\,\,0,0,0,1,0,1,0,\,\,\,0,1,2,0,0,0,0)$
sf_27 | $(1,1,1,0,0,0,0,\,\,\,0,1,0,0,0,1,0,\,\,\,1,1,1,0,0,0,0,\,\,\,0,1,0,0,0,1,0,\,\,\,1,0,0,0,0,0,1)$
sf_28 | $(1,1,1,1,0,0,0,\,\,\,0,1,0,1,0,1,0,\,\,\,0,1,1,0,0,0,1,\,\,\,0,1,0,1,0,1,0,\,\,\,0,0,0,0,0,0,2)$
Table 3: The coordinates of the fundamental normal surfaces of the gadget.

##  Appendix C Constructing Normal Surfaces in the Gadget

Given a normal surface $S$ in a triangulation $T$, we describe how to build a
surface $S^{\prime}$ in $T^{\prime}=T_{\tau}^{abcd(G)}$ where outside of a
tetrahedron $\tau$,
$\mathbf{S_{T\setminus\tau}}=\mathbf{S^{\prime}_{T^{\prime}\setminus G}}$, and
where $S^{\prime}_{G}$ is isotopic to $S_{\tau}$ with a tube connecting two
non-parallel pieces. In practice, normal surfaces of $T$ are generated, and
then all valid tubes are constructed (i.e. non-zero components and local
compatibility are satisfied). Table 4 lists the required permutations and the
new coordinates for $S^{\prime}_{G}$ in each case.

Tube in $\tau$ | Tube in $G$ | Perm. | New coordinates
---|---|---|---
tri_0:tri_1 | $G_{t_{0}}^{t_{2}}$ | $(2,0,1,3)$ | $\begin{aligned} &(t_{1}-1)\mathbf{G_{t_{0}}}+t_{2}\mathbf{G_{t_{1}}}+(t_{0}-1)\mathbf{G_{t_{2}}}+t_{3}\mathbf{G_{t_{3}}}\\\ &+q_{01/23}\mathbf{G_{q_{02/13}}}+\mathbf{G_{t_{0}}^{t_{2}}}\end{aligned}$
tri_0:tri_2 | $G_{t_{0}}^{t_{2}}$ | $(0,1,2,3)$ | $\begin{aligned} &(t_{0}-1)\mathbf{G_{t_{0}}}+t_{1}\mathbf{G_{t_{1}}}+(t_{2}-1)\mathbf{G_{t_{2}}}+t_{3}\mathbf{G_{t_{3}}}\\\ &+q_{02/13}\mathbf{G_{q_{02/13}}}+\mathbf{G_{t_{0}}^{t_{2}}}\end{aligned}$
tri_0:tri_3 | $G_{t_{0}}^{t_{3}}$ | $(0,1,2,3)$ | $\begin{aligned} &(t_{0}-1)\mathbf{G_{t_{0}}}+t_{1}\mathbf{G_{t_{1}}}+t_{2}\mathbf{G_{t_{2}}}+(t_{3}-1)\mathbf{G_{t_{3}}}\\\ &+q_{03/12}\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{0}}^{t_{3}}}\end{aligned}$
tri_1:tri_2 | $G_{t_{1}}^{t_{2}}$ | $(0,1,2,3)$ | $\begin{aligned} &t_{0}\mathbf{G_{t_{0}}}+(t_{1}-1)\mathbf{G_{t_{1}}}+(t_{2}-1)\mathbf{G_{t_{2}}}+t_{3}\mathbf{G_{t_{3}}}\\\ &+q_{03/12}\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{1}}^{t_{2}}}\end{aligned}$
tri_1:tri_3 | $G_{t_{1}}^{t_{3}}$ | $(0,1,2,3)$ | $\begin{aligned} &t_{0}\mathbf{G_{t_{0}}}+(t_{1}-1)\mathbf{G_{t_{1}}}+t_{2}\mathbf{G_{t_{2}}}+(t_{3}-1)\mathbf{G_{t_{3}}}\\\ &+q_{02/13}\mathbf{G_{q_{02/13}}}+\mathbf{G_{t_{1}}^{t_{3}}}\end{aligned}$
tri_2:tri_3 | $G_{t_{1}}^{t_{3}}$ | $(2,0,1,3)$ | $\begin{aligned} &t_{1}\mathbf{G_{t_{0}}}+(t_{2}-1)\mathbf{G_{t_{1}}}+t_{0}\mathbf{G_{t_{2}}}+(t_{3}-1)\mathbf{G_{t_{3}}}\\\ &+q_{01/23}\mathbf{G_{q_{02/13}}}+\mathbf{G_{t_{1}}^{t_{3}}}\end{aligned}$
tri_0:quad_01/23 | $G_{t_{0}}^{q_{03/12}}$ | $(0,3,1,2)$ | $\begin{aligned} &(t_{0}-1)\mathbf{G_{t_{0}}}+t_{2}\mathbf{G_{t_{1}}}+t_{3}\mathbf{G_{t_{2}}}+t_{1}\mathbf{G_{t_{3}}}\\\ &+(q_{01/23}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{0}}^{q_{03/12}}}\end{aligned}$
tri_0:quad_02/13 | $G_{t_{3}}^{q_{03/12}}$ | $(3,1,0,2)$ | $\begin{aligned} &t_{2}\mathbf{G_{t_{0}}}+t_{1}\mathbf{G_{t_{1}}}+t_{3}\mathbf{G_{t_{2}}}+(t_{0}-1)\mathbf{G_{t_{3}}}\\\ &+(q_{02/13}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{3}}^{q_{03/12}}}\end{aligned}$
tri_0:quad_03/12 | $G_{t_{0}}^{q_{03/12}}$ | $(0,1,2,3)$ | $\begin{aligned} &(t_{0}-1)\mathbf{G_{t_{0}}}+t_{1}\mathbf{G_{t_{1}}}+t_{2}\mathbf{G_{t_{2}}}+t_{3}\mathbf{G_{t_{3}}}\\\ &+(q_{03/12}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{0}}^{q_{03/12}}}\end{aligned}$
tri_1:quad_01/23 | $G_{t_{3}}^{q_{03/12}}$ | $(0,3,1,2)$ | $\begin{aligned} &t_{0}\mathbf{G_{t_{0}}}+t_{2}\mathbf{G_{t_{1}}}+t_{3}\mathbf{G_{t_{2}}}+(t_{1}-1)\mathbf{G_{t_{3}}}\\\ &+(q_{01/23}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{3}}^{q_{03/12}}}\end{aligned}$
tri_1:quad_02/13 | $G_{t_{0}}^{q_{03/12}}$ | $(2,0,1,3)$ | $\begin{aligned} &(t_{1}-1)\mathbf{G_{t_{0}}}+t_{2}\mathbf{G_{t_{1}}}+t_{0}\mathbf{G_{t_{2}}}+t_{3}\mathbf{G_{t_{3}}}\\\ &+(q_{02/13}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{0}}^{q_{03/12}}}\end{aligned}$
tri_1:quad_03/12 | $G_{t_{0}}^{q_{03/12}}$ | $(1,0,3,2)$ | $\begin{aligned} &(t_{1}-1)\mathbf{G_{t_{0}}}+t_{0}\mathbf{G_{t_{1}}}+t_{3}\mathbf{G_{t_{2}}}+t_{2}\mathbf{G_{t_{3}}}\\\ &+(q_{03/12}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{0}}^{q_{03/12}}}\end{aligned}$
tri_2:quad_01/23 | $G_{t_{0}}^{q_{03/12}}$ | $(1,2,0,3)$ | $\begin{aligned} &(t_{2}-1)\mathbf{G_{t_{0}}}+t_{0}\mathbf{G_{t_{1}}}+t_{1}\mathbf{G_{t_{2}}}+t_{3}\mathbf{G_{t_{3}}}\\\ &+(q_{01/23}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{0}}^{q_{03/12}}}\end{aligned}$
tri_2:quad_02/13 | $G_{t_{0}}^{q_{03/12}}$ | $(3,1,0,2)$ | $\begin{aligned} &(t_{2}-1)\mathbf{G_{t_{0}}}+t_{1}\mathbf{G_{t_{1}}}+t_{3}\mathbf{G_{t_{2}}}+t_{0}\mathbf{G_{t_{3}}}\\\ &+(q_{02/13}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{0}}^{q_{03/12}}}\end{aligned}$
tri_2:quad_03/12 | $G_{t_{3}}^{q_{03/12}}$ | $(1,0,3,2)$ | $\begin{aligned} &t_{1}\mathbf{G_{t_{0}}}+t_{0}\mathbf{G_{t_{1}}}+t_{3}\mathbf{G_{t_{2}}}+(t_{2}-1)\mathbf{G_{t_{3}}}\\\ &+(q_{03/12}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{3}}^{q_{03/12}}}\end{aligned}$
tri_3:quad_01/23 | $G_{t_{3}}^{q_{03/12}}$ | $(1,2,0,3)$ | $\begin{aligned} &t_{2}\mathbf{G_{t_{0}}}+t_{0}\mathbf{G_{t_{1}}}+t_{1}\mathbf{G_{t_{2}}}+(t_{3}-1)\mathbf{G_{t_{3}}}\\\ &+(q_{01/23}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{3}}^{q_{03/12}}}\end{aligned}$
tri_3:quad_02/13 | $G_{t_{3}}^{q_{03/12}}$ | $(2,0,1,3)$ | $\begin{aligned} &t_{1}\mathbf{G_{t_{0}}}+t_{2}\mathbf{G_{t_{1}}}+t_{0}\mathbf{G_{t_{2}}}+(t_{3}-1)\mathbf{G_{t_{3}}}\\\ &+(q_{02/13}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{3}}^{q_{03/12}}}\end{aligned}$
tri_3:quad_03/12 | $G_{t_{3}}^{q_{03/12}}$ | $(0,1,2,3)$ | $\begin{aligned} &t_{0}\mathbf{G_{t_{0}}}+t_{1}\mathbf{G_{t_{1}}}+t_{2}\mathbf{G_{t_{2}}}+(t_{3}-1)\mathbf{G_{t_{3}}}\\\ &+(q_{03/12}-1)\mathbf{G_{q_{03/12}}}+\mathbf{G_{t_{3}}^{q_{03/12}}}\end{aligned}$
Table 4: For each annulus in a tetrahedron $\tau$, this declares which surface
in $G$ of the same annulus type shall be used, under which permutation, and
the transformed surface coordinates.