Learning 3-Manifold Triangulations:
Pachner Graph Network Analysis
& Machine Learning IsoSigs
Francesco Costantino1, Yang-Hui He2,3,4,5, Elli Heyes3,2, Edward Hirst6

1 | Institut de Mathématiques de Toulouse, 118 route de Narbonne, F-31062 Toulouse, France
---|---
2 | London Institute for Mathematical Sciences, Royal Institution, London W1S 4BS, UK
3 | Department of Mathematics, City, University of London, EC1V 0HB, UK
4 | Merton College, University of Oxford, OX14JD, UK
5 | School of Physics, NanKai University, Tianjin, 300071, P.R. China
6 | Centre for Theoretical Physics, Queen Mary University of London, E1 4NS, UK

<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Report Number: QMUL-PH-23-16

###### Abstract

Real 3-manifold triangulations can be uniquely represented by isomorphism
signatures. Databases of these isomorphism signatures are generated for a
variety of 3-manifolds and knot complements, using SnapPy and Regina, then
these language-like inputs are used to train various machine learning
architectures to differentiate the manifolds, as well as their Dehn surgeries,
via their triangulations. Gradient saliency analysis then extracts key parts
of this language-like encoding scheme from the trained models. The isomorphism
signature databases are taken from the 3-manifolds’ Pachner graphs, which are
also generated in bulk for some selected manifolds of focus and for the subset
of the SnapPy orientable cusped census with $<8$ initial tetrahedra. These
Pachner graphs are further analysed through the lens of network science to
identify new structure in the triangulation representation; in particular for
the hyperbolic case, a relation between the length of the shortest geodesic
(systole) and the size of the Pachner graph’s ball is observed.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Triangulation IsoSigs
    2. 2.2 Algorithms for $3$-manifolds
  3. 3 Data Generation & Analysis
    1. 3.1 Pachner Graph Network Analysis
      1. 3.1.1 Orientable Cusped Census
  4. 4 Machine Learning IsoSigs
    1. 4.1 Differentiating Manifolds
      1. 4.1.1 Neural Networks
      2. 4.1.2 Transformers
    2. 4.2 Differentiating Knots
      1. 4.2.1 Supplementing with Dehn Surgery
  5. 5 Conclusions and Outlook
  6. Acknowledgments
  7. A IsoSig Encoding
  8. B Pachner Graphs

##  1 Introduction

Low-dimensional topology, as the study of manifolds of dimension $2,3$, and
$4$, has yielded countless invaluable results and insights. Initially it was
driven by the quest of the Poincaré conjecture (stating that a $3$-manifold
homotopy equivalent to the $3$-sphere is homeomorphic to it) and W. Thurston’s
geometrisation conjecture [1] which were finally proven by G. Perelman through
Ricci flow regularisation techniques [2, 3]. But during the eighties the
discovery of the first relevant examples of topological quantum field theories
by Witten [4] established the field as a central testing ground for most
physical theories. Therefore, beyond their intrinsic interest within
mathematics, this field has long had large influence within physics [5], and
more recently, its influence has been cemented in the development of the
younger field of computer science [6], where in particular concepts such as
triangulation and meshing are essential for rendering and visualisation.

As computational power has exponentially developed in recent decades, so too
has the potential for implementation of resource-expensive computational
methods. Many problems completely intractable before have now become rather
accessible, largely through methods of ‘big data’ and ‘big compute’. However
mathematical research presents a unique challenge, where datasets can often be
generated infinitely and sampled cheaply, exhaustive computation becomes
infeasible, demanding statistical practises. It is here, from a presently
prominent subfield of computational science that a wealth of new techniques
have been made available for approaching mathematical research; that field
being: machine learning (ML).

Machine learning covers a broad range of techniques for computational
statistics, and the subfield itself can be split into three core subsubfields,
which each have already seen compelling successes in mathematics and
mathematical physics. These are: supervised learning [7, 8, 9, 10, 11, 12, 13,
14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25], unsupervised learning [26,
27, 28], and reinforcement learning [29, 30, 31, 32, 33, 34]. This work
focuses on techniques from the first of these subsubfields, in particular
using supervised learning methods to classify and study $3$-manifolds.

The direct application of machine learning methods within low-dimensional
topology is increasingly widespread. Initiated in [35], where neural networks
(NNs) were first used to predict knot invariants, after the surprisingly
accurate prediction of the hyperbolic volume of a knot complement from its
Jones polynomial [36], the study carried on in [37] where it was shown that
NNs could effectively distinguish high complexity knot presentations of the
trivial knot from non-trivial ones. In [38, 39], notable knot invariants (the
Jones polynomial, Rasmussen’s $s$-invariant, and Khovanov homology) where
mutually predicted by NNs with high accuracies, indicating new possible hidden
relations between these invariants; and further knot invariant interrelations
were identified in [40]. An especially useful application of these ideas has
been developed in [41], where the recognition of ribbon knots has been pushed
beyond the bounds of human capabilities through these techniques. Besides
knots, ML methods have been used for the study of a particular kind of closed
$3$-manifolds [42], where graph $3$-manifolds ($3$-manifolds whose Jaco-
Shalen-Johansson decomposition contain no hyperbolic piece) where studied via
their presentation through surgeries on plumbing graphs and various ML
algorithms where implemented to reduce presentations of such $3$-manifolds to
easier ones via so-called Neumann’s moves.

In this paper a different approach to representation of $3$-manifolds is
considered, and one that has many direct practical applications:
triangulations. As proved by Casler [43], every $3$-manifold admits a
triangulation, i.e. a decomposition into $3$-dimensional simplexes
(tetrahedra). By compactness only a finite number of these is sufficient and
the (finite) datum of how to glue them can be summarised most succinctly in a
single string of characters: the isomorphism signature (IsoSig). IsoSigs,
defined in [44] and reexplained in Appendix A, are especially compact
encodings of $3$-manifold triangulations, making bulk storage and study of
triangulations far more accessible. Our first interest in this paper is to
examine how amenable ML methods, and in particular NNs, are to extracting the
highly-convoluted information about the triangulations from this highly-
compressed representation.

Eight $3$-manifolds were selected for focus in this study, chosen due to their
importance within the field and variety of properties: $S^{3},S^{2}\times
S^{1}$, $\mathbb{RP}^{3}$, $L(7,1)$ and $L(7,2)$ (homotopy equivalent but not
homeomorphic lens spaces), the three torus $T^{3}$, the Poincaré homology
sphere $PHS$, and the ‘smallest closed hyperbolic’ $3$-manifold with lowest
volume $H_{SC}$ (a.k.a. the Weeks manifold). After producing thousands of
different triangulations of each of these manifolds we trained NNs (and
transformers) to distinguish them pairwise, observing some striking
performances, which gradient saliency techniques allowed interpretation of in
terms of the IsoSig components (see §4.1).

A single $3$-manifold can be encoded via infinitely many distinct
triangulations, where each IsoSig completely and uniquely encodes one of these
triangulations. It is a classical theorem [45] that two such triangulations of
the same $3$-manifold can always be connected to each other by a finite
sequence of local modifications, known as Pachner moves, which are of two
types (the $2-3$ move with its inverse, and the $1-4$ move with its inverse).
Therefore one can define an abstract graph associated to each $3$-manifold,
known as the Pachner graph, whose nodes are triangulations and edges are
associated to Pachner moves between them.

In this work, Pachner graphs were generated up to depth $5$ for the eight
$3$-manifolds of focus, starting from a minimal triangulation. As well as
these Pachner graphs providing the IsoSig data used in ML, their graph
structure is of its own independent interest. Through a range of network
analysis techniques these Pachner graphs were comparatively studied, with
results in §3.1. Techniques related to network clustering, shortest paths,
centrality, and cycles were employed; notably identifying $L(7,2)$’s most
central triangulation was not the initial (minimal) one but one which was at
distance two from it, containing $9$ tetrahedra. Also, the Weeks manifold (and
other hyperbolic manifolds not of focus here) exhibited significantly faster
Pachner graph growth with depth, reaching computational limits and leading us
to conjecture that Pachner graphs of closed hyperbolic $3$-manifolds grow much
faster than those of non-hyperbolic $3$-manifolds.

Further investigations extended network analysis to the Pachner graphs of the
snappy [46] census of cusped orientable hyperbolic $3$-manifolds111A word of
caution here is needed: cusped hyperbolic $3$-manifolds are encoded in snappy
via their ideal triangulations, namely the (non-compact) manifolds are
homeomorphic to the complement of the vertices in the triangulations encoded
by the given IsoSigs. So our Pachner graphs describe such ideal triangulations
for these cusped hyperbolic $3$-manifolds., focusing on those with up to $7$
tetrahedra (there are 4815 of them), see §3.1.1. Our analyses evidenced an
unexpected behavior which led us to Conjecture 1 that the growth of the
Pachner graph for these manifolds is inversely related to the length of the
shortest closed geodesic (a.k.a. the systole). Additionally in §4.2, knot
complements where learnt via their cusped triangulation IsoSigs; focusing on
eight knot complement $3$-manifolds: the unknot, the trefoil knot, the figure
eight knot, the knots $5_{1},5_{2},6_{1}$, and $8_{2}$. The results are
comparable to those for closed $3$-manifolds and in interestingly show no
learning in distinguishing the figure eight knot from the knot $5_{2}$, which
are the two knots with smallest hyperbolic volume. We also supplemented the
analysis for these knot complements by a similar analysis for their $0$ and
$1$-surgeries: in §4.2.1 we showed how the unknot and the trefoil knot are
very accurately distinguished by these surgeries.

Computational work was completed in python, with use of the regina [47] and
snappy [46] libraries for manipulating IsoSigs, as inspired by work in [44,
48]. Pachner graphs were constructed and analysed using networkx [49], whilst
machine learning used the sci-kit learn [50] and tensorflow [51] libraries.
Coding scripts and data are made available at this work’s respective
GitHub222https://github.com/edhirst/IsoSigPGML.git repository, including an
introductory notebook with useful functions for ones own further
investigations manipulating and visualising Pachner graphs.

##  2 Preliminaries

###  2.1 Triangulation IsoSigs

Any compact connected $3$-manifold $M$ with boundary can be realised by gluing
a finite set of $T$ tetrahedra ($3$-simplices) along their faces via affine
maps and then by deleting a small open neighborhood of the vertices of the
tetrahedra. Such a structure is called an ideal triangulation and it induces a
triangulation of $\partial M$ by means of $4T$ triangles (as each tetrahedron
contributes $4$ triangles to the triangulation of $\partial M$)333Since we
allow self-gluing of tetrahedra, in some literature this is referred to as a
‘$\Delta$-triangulation’.. In the special case of a closed manifold one can
consider triangulations of $M$ minus a finite set of disjoint open balls:
indeed one can recover $M$ from $M\setminus B^{3}$ in a unique way by gluing
back a $B^{3}$ along its boundary $S^{2}$.

Each triangulation can be encoded by numbering the tetrahedra along with their
vertices, indicating which pairs of faces of two tetrahedra of the
triangulation are glued and how (there are $6$ possible identifications for
each pair of faces). All these data can be encoded in a single string of
characters defined in [48], called the isomorphism signature (IsoSig) of the
triangulation. The following holds:

######  THEOREM (Theorem 6 in [48]).

If two IsoSig strings $S_{1}$ and $S_{2}$ encode two triangulations then the
triangulations are combinatorially isomorphic iff $S_{1}=S_{2}$.

It should be noted though, that a $3$-manifold admits infinitely many
different (non-isomorphic) triangulations, which are all related to each other
via the so-called bistellar or Pachner moves [45]. When applying a Pachner
move, in general the IsoSig of a triangulation changes (for most moves even
the number of tetrahedra changes). One can then build a graph $\mathcal{P}$
whose nodes are the isomorphism types of triangulations of a fixed manifold
and whose edges represent that the two triangulations can be transformed into
one another via a possible Pachner move444Note that there may be (likely rare)
scenarios where two different moves can transform an input triangulation into
the same output triangulation, in these cases we still only connect the
respective nodes by a single edge.. By the above cited fundamental result this
graph is connected [45]. Before proceeding we remind the reader that these
moves are of four types: $2-3$, $3-2$, $1-4$ and $4-1$ moves where for
instance a $2-3$ move consists in exchanging two tetrahedra with a suitable
combination of three tetrahedra and a $1-4$-move consists in subdividing a
tetrahedron into four tetrahedra by coning from its barycenter to its
vertices. The moves $3-2$ and $4-1$ are the inverses of respectively the $2-3$
and the $1-4$-moves. Note that the number of vertices of the triangulation
does not change under $2-3$ and $3-2$ moves, but does change under $1-4$ and
$4-1$ moves, exactly by one unit. Diagrammatics for these moves are shown in
Figure 1.

(a)

(b)

Figure 1: Diagrammatics of the four Pachner moves, including (a) the $2-3$
Pachner move with its inverse $3-2$, and (b) the $1-4$ Pachner move, with its
inverse $4-1$. For the $2-3$ move the coloured lines bound a face which is
replaced by an edge which then bounds the three tetrahedra inside. For the
$1-4$ move a vertex (coloured) is introduced into the centre and then
connected to the remaining vertices, splitting the single tetrahedra into
four.

The ‘Pachner graph’ $\mathcal{P}$ described above is naturally endowed with
two functions which we will denote $v$ and $t$ respectively given by the
number of vertices and of tetrahedra of a triangulation. We will denote
$\mathcal{P}_{n}$ the full subgraph of $\mathcal{P}$ of triangulations whose
number of vertices is $n$: a particularly interesting subgraph is
$\mathcal{P}_{1}$. At first sight one might be puzzled by this but we remind
the reader that in our triangulations the tetrahedra are not embedded and
self-identifications are possible. In fact it was proved independently by
Matveev [52] and Piergallini [53] that for every 3-manifold the subgraph of
$\mathcal{P}_{1}$ formed by nodes corresponding to triangulations with at
least $2$ tetrahedra is non-empty and connected [52, 53]; there are only $3$
triangulations with only 1 tetrahedra and they correspond to manifolds
$L(3,1),L(5,1)$ and $S^{3}$, so excluding them is not a problem.

###  2.2 Algorithms for $3$-manifolds

In this subsection we review some main results concerning the existence of
algorithms for distinguishing $3$-manifolds and their complexity. Our account
is by no means complete nor exhaustive and we redirect the reader to the
excellent survey by M. Lackenby [54] and to S. Matveev’s book [55]. The rough
overall message is that although algorithms exist for basically all
interesting tasks in $3$-dimensional topology, when their theoretical
complexity bounds are known, they are huge. Still, extensive experiments have
been run for ‘small’ triangulations and they contrast sharply with the
theoretical bounds.

One of the main facts to keep in mind is that a theoretical algorithm exists
to tell whether two triangulations belong to the same $3$-manifold or not.
There are various proofs of this fact [56, 57], but they all use the proof of
the Geometrisation Conjecture by Perelman. However, the best ‘known’ upper
bound for the complexity of these algorithms, due to G. Kuperberg, is huge and
is of the form $2^{2^{\cdots^{t}}}$ where $t$ is the number of tetrahedra in
the triangulations and the length of the tower of powers is a universal yet
unknown constant [56].

The special case of recognising the $3$-sphere is known to be NP and has a
more explicit algorithm, due to Rubinstein [58]. The number of Pachner moves
needed to connect a $n$-tetrahedra triangulation of $S^{3}$ to the standard
one has been bound by Mijatović [59] to be $610^{6}n^{2}2^{20000n^{2}}$.

The fact that an algorithm exists to tell whether two triangulations belong to
the same manifold implies that there is also a theoretical computable function
which bounds the distance of two triangulations in the Pachner graph of a
given $3$-manifold (see [54] Theorem 4.3) based only on their numbers of
tetrahedra. But for general $3$-manifolds this is purely theoretical at
present555All the previous results can be largely improved when the
$3$-manifolds are link exteriors in the sphere, but we will not review the
main results here as in this paper we are mainly concerned with closed
orientable manifolds..

We also mention that, although the theoretical bounds, when they exist, are
huge, concrete experiments have been carried out and show quite a different
behavior. In [48] B. Burton showed that if one restricts to $1$-vertex
triangulations with less than $10$ tetrahedra (there are about $8210^{6}$ of
them!) then these can be connected to simpler ones (i.e. triangulations with
less tetrahedra) by a sequence of Pachner moves whose length does not exceed
$17$ (of course this is possible only if one does not start from a minimal
triangulation). In particular if one restricts to triangulations of $S^{3}$
only $9$ moves are needed. Furthermore in the same paper it is observed that
the sequence of simplifying moves can be found so that the number of
tetrahedra during the sequence never increases by more than $3$.

##  3 Data Generation & Analysis

To examine and learn the 3-manifold triangulation isomorphism via IsoSigs, we
select a variety of 3-manifolds to focus on, in particular those which span a
range of interesting properties. Eight 3-manifolds were selected for these
investigations, they include: the 3-sphere $S^{3}$; the product of the
2-sphere and the 1-sphere $S^{2}\times S^{1}$; 3-dimensional real projective
space $\mathbb{RP}^{3}$, the lens space $L(7,1)$, the lens space $L(7,2)$; the
3-torus $T^{3}$; the Poincaré homology sphere $PHS$; and the smallest closed
hyperbolic manifold $H_{SC}$. The 3-manifold abbreviations, along with the
initial IsoSigs used to generate the datasets of equivalent triangulation
IsoSigs are given in Table 1. Of these manifolds $S^{2}\times S^{1}$ is the
only one not admitting a constant curvature isotropic complete Riemannian
metric (we shall say for short a ‘non-isotropic manifold’), whilst the others
are split amongst their curvatures, with
$(S^{3},\mathbb{RP}^{3},L(7,1),L(7,2),PHS)$ positive curvature, $T^{3}$ zero
curvature, and $H_{SC}$ negative curvature. In addition they have properties
as listed in Table 2.

Manifold Name | Initial IsoSig | Number of Tetrahedra
---|---|---
$S^{3}$ | cMcabbgqs | 2
$S^{2}\times S^{1}$ | cMcabbjaj | 2
$\mathbb{RP}^{3}$ | cMcabbgqw | 2
$L(7,1)$ | eLAkbcbddhhjhk | 4
$L(7,2)$ | cMcabbjqw | 2
$T^{3}$ | gvLQQedfedffrwawrhh | 6
PHS | fvPQcdecedekrsnrs | 5
$H_{SC}=Weeks$ | jLvAzQQcfeghighiiuquanobwwr | 9
Table 1: The eight 3-manifolds of focus in this investigation, listed with the initial 1-vertex triangulation IsoSigs used to generate their Pachner graphs, and the respective number of tetrahedra in these initial triangulations. Property | Manifold
---|---
$S^{3}$ | $S^{2}\times S^{1}$ | $\mathbb{RP}^{3}$ | $L(7,1)$ | $L(7,2)$ | $T^{3}$ | $PHS$ | $H_{SC}$
Curvature | + | $\cdot$ | + | + | + | 0 | $+$ | $-$
Volume | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.94
Homology | 0 | $\mathbb{Z}$ | $\mathbb{Z}/2$ | $\mathbb{Z}/7$ | $\mathbb{Z}/7$ | $\mathbb{Z}+\mathbb{Z}+\mathbb{Z}$ | 0 | $\mathbb{Z}/5+\mathbb{Z}/5$
Fund Group | G | x | a | a | a | a | a, b, c | a, b | a, b
R | x | x | aa | aaaaaaa | aaaaaaa |  | bcBC,
---
abAB,
aCAc
| abbaB,
---
aaaabAb
| ababAbbAb,
---
abaBaaBab
Table 2: Table of selected manifold properties. Properties include the sign of
the curvature (note $S^{2}\times S^{1}$ is non-isotropic so curvature is not
applicable); Euler characteristic, hyperbolic volume, homology group, and
fundamental group (given as generators and relators).

For each 3-manifold’s initial triangulation and IsoSig, a dataset was
generated of equivalent triangulations (each represented with their respective
IsoSig) from the manifold’s Pachner graph computed exhaustively up to as high
a depth (i.e. integer number of moves away from the initial IsoSig) as
feasible within memory limits. The Pachner graphs were generated with moves
$\\{2-3,3-2\\}$ (with further functionality in the code to consider
$\\{1-4,4-1\\}$ moves). Initial investigations showed that ML architectures
relied heavily on the IsoSig length for distinguishing manifolds, with
performance measures $>0.99$ for near-perfect learning. Since the IsoSig
length is heavily correlated with the number of tetrahedra, when we initiate
generation using triangulations with a similar (e.g. small) number of
tetrahedra then the graphs will display the same IsoSig lengths throughout,
however the frequency distribution of the observed lengths varies, and this is
what the architectures can leverage to provide efficient estimates of the
considered manifold (note the final depth often all have the same length and
dominate these distributions). For the manifolds considered the IsoSig lengths
observed in the deep Pachner graph generation were:
$(9,11,14,17,19,22,25,27,30,33,35,38,41)$. The respective distributions are
shown in Figure 2.

Figure 2: IsoSig length frequency distributions across the deep Pachner graphs
generated for the 8 manifolds considered.

Thus the ML focus was shifted to IsoSigs of the same length, such that the
architectures could not shortcut to good performance and the true IsoSig
language representation would have to be learnt. The datasets were created by
randomly sampling all those of length 30 characters (the most evenly populous
across the Pachner graphs) from the generated Pachner graphs (often exhibiting
millions of IsoSigs). The sampled datasets of length 30 IsoSigs were all of
size 2000, except for $T^{3}$ with 391 and $H_{SC}$ with 136, where this was
the number of length 30 IsoSigs in the generated Pachner graphs. Therefore
investigations with these two manifolds had bias in their datasets from these
different sizes, which is mitigated by considering the MCC performance measure
(over accuracy) which accounts for imbalanced classes [60].

The code scripts were written in python, using the regina library [47] for
manipulating triangulations and applying Pachner moves, whilst also using the
orientable cusped census hosted on snappy [46] to source some manifold
IsoSigs. Scripts created Pachner graphs, as networkx objects [49], by
exhaustively searching all vertices, edges, faces, and tetrahedra of each
triangulation that Pachner moves could be applied to. Where performing a move
generated a new triangulation the respective IsoSig was listed as a new node
in the graph, connected by an edge (labelled with the move type) to the IsoSig
the move was applied to. Conversely, where performing a move lead to a
previously generated IsoSig an edge was introduced connecting the respective
nodes already in the graph (ignoring the trivial inversion of moves). This
Pachner graph generator function started from an initial input IsoSig and was
adaptable to perform (input-specified) Pachner moves up to an input-specified
depth from the initial IsoSig; outputting the Pachner graph and the list of
IsoSigs, one for each triangulation of the manifold.

###  3.1 Pachner Graph Network Analysis

The Pachner graphs used for IsoSig data generation are interesting
combinatorial objects in their own right. As one performs Pachner moves with
the hope of simplifying a triangulation, or looking to seek some specific
triangulation property, one is effectively performing a walk on this graph.
The graph network structure hence determines the potential success of these
search algorithms, and more information about their network properties can
guide the refinement of these search algorithms to make them as optimal as
possible.

Therefore, with this in mind, we study these 1-vertex Pachner graphs
$\mathcal{P}_{1}$ for the considered 3-manifolds, using only $\\{2-3,3-2\\}$
moves, generated to as large a depth as can be performed in 240 core hours on
a high-performance compute cluster [61]. Then with these large 1-vertex
Pachner graphs we perform extensive analysis of their network properties:
degrees, clustering, shortest paths, centrality, cycles. The distribution of
number of tetrahedra in the triangulations was also tracked, since seeking a
3-manifold triangulation with the minimum number of tetrahedra is highly
sought-after in the field (for simplicity in computing topological properties
and constructing composite 3-manifolds).

Example Pachner graphs for the $S^{3}$ manifold, generated to depths 3 and 4
are shown in Figure 3. The equivalent Pachner graphs for the remaining 7
considered manifolds are shown in Appendix B. Each of these Pachner graphs
were generated from the initial IsoSig given in Table 1, using moves
$\\{2-3,3-2\\}$; within these each Pachner graph node is an independent IsoSig
/ triangulation, with edges representing the moves connecting them (undirected
since each $3-2$ move changes the IsoSig in the opposite direction to the
equivalent $2-3$ move). The Pachner graph nodes are labelled with the number
of tetrahedra in the respective triangulation. Since each of the initial
IsoSigs represent 1-vertex triangulations, and only $\\{2-3,3-2\\}$ moves are
considered which preserves the number of vertices in the triangulation, these
graphs are (part of) the respective unique 1-vertex restricted Pachner graph
$\mathcal{P}_{1}$ for each manifold [48].

(a) Depth 3

(b) Depth 4

Figure 3: 1-vertex Pachner graphs for the $S^{3}$ manifold, generated with
$\\{2-3,3-2\\}$ moves up to the respective specified depths, from the initial
triangulation with IsoSig: cMcabbgqs. The nodes are labelled with the number
of tetrahedra in the respective triangulation.

These Pachner graph images highlight well the rapid growth rate of
triangulations. As can be seen for $S^{3}$ in Figure 3, it is only when depth
4 is considered that cycles begin to occur in this Pachner graph, at which
point many cycles start to occur. These cycles also indicate shorter paths
between different triangulations, compared to returning to the initial
triangulation. The graphs also exemplify how number of tetrahedra tends to
increase as one moves further from the initial triangulation in a Pachner
graph.

To probe further the graph structure we turn to tools from network science, in
particular applying an analysis technique from each of its core subfields:
node analysis, clustering analysis, shortest path analysis, centrality
analysis, cycle analysis. In addition, keeping track of the number of
tetrahedra in each triangulation.

The Pachner graphs for the 8 selected manifolds of focus in this work were
generated until memory limits deemed network analysis computationally
infeasible (in each case these were RAM limits of 200GB). Fortunately many of
these Pachner graphs failed generation at the same depth of 5, making
comparison between them at this depth more meaningful. However, the final
hyperbolic manifold $H_{SC}$ grew too quickly and thus failed generation
earlier, this makes its comparison less useful, but it is still included for
completeness.

The Pachner rapid growth rate is well represented in Figure 4, where the
number of nodes in the Pachner graphs at each depth are shown. This plot
clearly shows the final hyperbolic manifold having a much quicker growth rate
leading to memory failure at lower depth. Generally, there will be more
positions in a triangulation to apply a $2-3$ move than a $3-2$ move and so
the number of tetrahedra tends to increase with depth, equivalently with more
tetrahedra there are more positions to apply moves and thus this positive
growth rate of triangulations in the Pachner graph appears. Respectively the
graph density drops with depth, as each time a new node is introduced to the
Pachner graph with $N$ nodes, $(N-1)$ potential edges are not introduced. As
depth increases this contribution to density clearly beats any increase in
density from introducing cycles, as displayed in the apparent convergence in
density towards 0 with depth in Figure 4.

(a) Number of Nodes

(b) Density

Figure 4: The growth rates of the Pachner graphs with depth for the 8 selected manifolds of focus in this work. Plot (a) shows how number of nodes increases with depth, whilst (b) shows the respective decreases in graph density. | Manifold
---
(depth)
| Number
---
of Nodes
Density |  | Clustering
---
(tri, squ)
| Wiener Index
---
(full, norm)
| Centrality
---
(centre, range)
| Minimum Cycle Basis
---
[[length, frequency]]
| # Tetrahedra
---
(index, min)
$S^{3}$ (5) | 2979 | 0.0009 | (0, 0.018) | (30734710, 6.93) | (7, 0.160) | [[4, 861], [6, 201], [8, 18]] | (0, 2)
$S^{2}\times S^{1}$ (5) | 1123 | 0.0023 | (0, 0.018) | (4041442, 6.41) | (11, 0.220) | [[4, 305], [6, 61], [8, 2]] | (0, 2)
$\mathbb{RP}^{3}$ (5) | 1636 | 0.0017 | (0, 0.018) | (8738384, 6.53) | (13, 0.198) | [[4, 480], [6, 108], [8, 12]] | (0, 2)
$L(7,1)$ (5) | 3161 | 0.0010 | (0, 0.022) | (33280736, 6.66) | (20, 0.201) | [[4, 1812], [6, 132], [8, 9]] | (0, 4)
$L(7,2)$ (5) | 1368 | 0.0020 | (0, 0.019) | (5996840, 6.41) | (2, 0.202) | [[4, 417], [6, 78], [8, 9]] | (0, 2)
$T^{3}$ (5) | 1280 | 0.0030 | (0, 0.027) | (4250674, 5.19) | (13, 0.215) | [[4, 1119], [6, 22]] | (0, 6)
$PHS$ (5) | 2060 | 0.0017 | (0, 0.022) | (12064060, 5.69) | (6, 0.215) | [[4, 1469], [6, 49]] | (0, 5)
$H_{SC}$ (3) | 3553 | 0.0010 | (0, 0.016) | (34673464, 5.49) | (0, 0.230) | [[4, 2489], [6, 49]] | (0, 9)
Table 3: Network analysis properties for the 1-vertex Pachner graphs of the 8
manifolds of focus in this work, generated to as a high depth as
computationally feasible. Note that all were to depth 5, except for the last
hyperbolic manifold which terminated generation at a lower depth. Analysis
includes counts of the number of graph nodes, the graph density, the triangle
and square clustering coefficients, the Wiener index in full and normalised
form, the index of the most central node via eigenvector centrality as well as
the range in centrality values across the graph, the decomposition of a
minimum cycle basis, and the index of the node with the minimum number of
tetrahedra and that minimum number.

These network analysis results are presented for the eight manifolds’ 1-vertex
Pachner graphs in Table 3. This table lists the manifolds as well as the depth
they were generated to (using input initial IsoSigs from Table 1); each
measure is discussed below with definitions.

Nodes: For each Pachner graph, the number of nodes is then listed,
representing the number of unique triangulations generated. One striking fact
is that the number of nodes for the depth 3 Pachner graph of the hyperbolic
manifold $H_{SC}$ is bigger than the number of nodes of the depth $5$ Pachner
graphs for the remaining (non-hyperbolic) manifolds. But for these remaining
manifolds, we note the number of nodes does not seem to correlate with
topological properties as the more populous graphs represent manifolds with
varying curvatures, fundamental group sizes, etc; and the high number of
$S^{3}$ nodes contradicts an argument that it is based on the number of
tetrahedra in the initial IsoSig. Respectively the graph density is listed,
where density is the ratio between the number of edges in the graph and the
number of edges in the complete graph with the same number of nodes (i.e. the
maximum number of possible edges), which expresses the usual approximate
inverse correlation behaviour with the number of nodes.

Clustering: Next the graph triangle and square clustering coefficients are
listed [62, 63], which represent the proportion of 3 and 4 cycles that could
exist in the graph that are there; i.e. all combinations of 3 nodes could be
connected into a 3-cycle, the triangle clustering coefficient is the ratio
between the number of 3-cycles in the graph to the number of combinations of
choosing 3 nodes. The first observation is that all the Pachner graphs exhibit
no 3-cycles, this is because any Pachner move changes the number of tetrahedra
by 1, hence any 2 moves either change the number of tetrahedra by 2 or keep it
the same (adding then removing, or removing then adding). Therefore any third
move following these two must change the number of tetrahedra by 1 again, such
that the total change in the number of tetrahedra after 3 moves cannot be 0
and then the same as the original triangulation. This argument actually lifts
quite nicely to any odd cycle, such that all cycles in a 1-vertex Pachner
graph must be even. The square clustering coefficients may then be non-zero,
with all graphs exhibiting 4-cycles, and $T^{3}$ having the highest
proportion.

Shortest Paths: The Wiener index [64] is the sum of the lengths of the
shortest paths over all pairs of nodes666i.e. select a pair of nodes in the
graph, find the shortest path between them (if there are multiple select one
arbitrarily), count the number of edges in the path to get the length of this
path, repeat for all pair of nodes in the graph, take the sum., and is hence
also presented in a normalised form with respect to the number of pairs of
nodes (number of nodes $N$ choose 2). A smaller normalised Wiener index
indicates the graph is easier to walk around, with a high connectivity, which
is the case for the non-positive curvature manifolds with the lowest values.

Centrality: Centrality measures determine the most central nodes, and how
skewed the connectivity is away from uniform constant degree. The centrality
measure examined in this work is eigenvector centrality, which assigns scores
to the nodes based on their respective entries in the normalised eigenvector
corresponding to the unique largest eigenvalue of the graph’s adjacency matrix
(via the Peron-Frobenius Theorem [65, 66]) [67]. A graph’s adjacency matrix is
intrinsically linked to potential paths through it, and such raising it to the
$k$th power counts the number of $k$-paths between the indexed nodes. This
limiting behaviour is then dictated by the largest eigenmode, and hence the
eigenvector centrality score provides a means of determining the limiting
connectivity of nodes. In Table 3, the node index with the highest centrality
score is listed, as well as the range of these scores across the graph.
Interestingly, only for $H_{SC}$ is the most central node the initial IsoSig
triangulation, indicating the other Pachner graphs may be more symmetrically
generated about alternative initial IsoSigs. In some cases, such as for
$L(7,1)$ the index is as high as 20, such that it is the 20th triangulation
produced when exhaustively generating the Pachner graph, and is 2 moves away
from the initial triangulation; it is a $9$-tetrahedra triangulation.
Iteratively, this measure may be used in this way to search for useful
starting triangulations. The range of centrality scores are largest for the
non-positive curvature manifolds, which then turn out to have more skewed
Pachner graphs and knowledge of the most central node becomes important as a
key triangulation many paths will pass through (this could be a useful
information when designing paths to minimise the number of tetrahedra).

Cycles: Cycles in a Pachner graph represent availability of different paths to
move between selected nodes. As mentioned previously, since $3-2$ and $2-3$
moves each change the number of tetrahedra by 1, this leads to all cycles
being even. 2-cycles enact the inverse of any move, so are trivial on these
undirected graphs. This causes 4-cycles to be the first cycles that can occur,
whose frequency is assessed through the square clustering coefficient. In
general, a $(2k)$-cycle amounts to $k$ $2-3$ moves and $k$ $3-2$ moves and
there are no a priori restrictions on their order. Where the number of moves
is small relative to the number of tetrahedra, cycles are likely caused by the
more trivial case where each of the $k$ $2-3$ moves may be paired with its
respective inverse $3-2$ move removing the same tetrahedra introduced, but in
a different order such that the intermediary triangulations are distinct.
However as the number of moves gets larger there’re less untouched tetrahedra
to perform the new moves on, and then moves start to overlap in the same part
of the triangulation leading to less trivial cycles.

As can be seen in the Pachner graph plots, cycles often intersect, and where
two smaller cycles intersect a larger cycle can easily be created by
traversing the exterior of them both. To circumvent redundancies due to this,
it is standard practice to consider a basis for the cycles [68], and
additionally to focus on bases where the sum of the cycle lengths is
minimised: a minimum cycle basis. However there is still redundancy in which
cycles form part of this bases, and therefore the analysis in Table 3 instead
focuses on its properties, notably counting the frequencies of cycles of each
length in the basis (which is unique across all minimum cycle bases). As can
be seen, all the graphs exhibit 4-cycles, some with an order of magnitude more
than others. Where the number of 4-cycles is higher the number of 6-cycles
tends to be lower (except for $\mathbb{RP}^{3}$ which has a high number of
6-cycles, and $S^{2}\times S^{1}$ with a surprisingly low number). Up to depth
5 the maximum cycle size which can occur is 10, and in none of the graphs does
this occur, and interestingly it is only for the manifolds with simplest
fundamental group presentation that 8-cycles occur.

Number of Tetrahedra: The final analysis tracks the node index with the fewest
number of tetrahedra, often desirable for use in manifold computation and
construction, as well as listing that number of tetrahedra. All manifolds have
index 0 as their minimum (i.e. index 0 is the first triangulation in the
generation process which is the initial triangulation), expected since a
minimal triangulation was selected as an initial point for the generation. A
final remark to emphasise is that the node with the minimum number of
tetrahedra does not correlate with centrality, only in the case of $H_{SC}$
does the most central triangulation have the minimum number of tetrahedra.

####  3.1.1 Orientable Cusped Census

Beyond the eight selected 3-manifolds that we focus on in this paper, the
snappy Orientable Closed Census provides a list of 11031 orientable closed
hyperbolic manifolds. These however are represented as cusped manifolds which
when filled have a range of tetrahedra for their initial triangulations from 9
to 37 – too large for sensible Pachner graph analysis as the number of
triangulations would grow too quickly with depth to compute to a meaningful
size.

Therefore we instead consider the respective snappy Orientable Cusped Census,
which lists all 61911 orientable cusped hyperbolic manifolds which can be
represented by triangulations with at most 9 tetrahedra. We partition off the
4815 with $<8$ tetrahedra for an exhaustive analysis of their equivalent
Pachner graphs. Each of these manifolds are represented by an initial
triangulation (and hence IsoSig) in the database.

Despite the large number of manifolds in the census, with use of the high-
performance compute cluster it became computationally feasible to generate
Pachner graphs for all hyperbolic manifolds in this partition of the census,
and perform the equivalent network analysis. Pachner graphs were generated for
both move combinations $\\{2-3,3-2\\}$ and $\\{1-4,4-1\\}$, up to depth 3,
which we denote ‘3_23’ and ‘3_14’ respectively. The subsequent bulk network
analysis provides insight into the triangulation deformation structure of
these Pachner moves, how they each impact the graph structure, as well as
general insight into how Pachner graphs grow. Considering the same set of
network analysis techniques used to examine the depth 5 Pachner graphs for the
eight manifolds of focus in Table 3, we created plots of these properties for
the census as shown in Figure 5.

(a) Nodes

(b) Density

(c) Mean Degree Distribution

Figure 5: Network analysis of the orientable cusped census Pachner graphs
(where number of initial tetrahedra $<8$). Analysis considers building the
Pachner graphs to depth 3 with either only the $\\{1-4,4-1\\}$ moves (denoted
3_14), or only the $\\{2-3,3-2\\}$ (denoted 3_23) moves, plotting histograms
of: (a) number of nodes in the graph; (b) graph density; and (c) the graph
degree distribution averaged across the census. Note the degrees take integer
values and the vertical lines are offsetted for visibility.

(a)

(b)

Figure 6: The distribution of the sizes of the Pachner graphs (i.e. number of
nodes) as a function of (a) the volume and of (b) the length of the shortest
geodesic. In blue the points corresponding to one cusped manifolds, in red
those corresponding to $2$-cusped manifolds, and in green the remaining ones.

(a)

(b)

Figure 7: The distribution of the sizes of the Pachner graphs (i.e. number of
nodes) as a function of (a) the volume and of (b) the length of the shortest
geodesic restricted to the manifolds whose drilling along the shortest
geodesic is a fixed one, here “m129” (in snappy’s cusped census). The symmetry
is not random and is related to the known relation between the volume of a
manifold and its Dehn fillings along ‘long’ meridians.

Nodes: First order analysis of the graphs considers the sizes of the node and
edge sets. A histogram for the number of nodes is shown in Figure 5(a),
demonstrating that the $2-3$ (and their inverse $3-2$) moves often lead to
many more nodes. Since the number of possible $1-4$ moves for a triangulation
equals the number of tetrahedra $N$, whereas the number of possible $2-3$
moves equals the number of common faces (which is half the total number of
faces $4N/2=2N$) this matches the expected approximate scaling that $2N>N$ for
triangulations of $N$ tetrahedra, causing more possible $2-3$ moves, and more
nodes in the 3_23 Pachner graphs. The $1-4$ moves also have much higher
frequencies, meaning their graph generation is more systematic, which is
perhaps to be expected since the number of tetrahedra alone (which many
manifolds will share) sets the number of $1-4$ moves which can be enacted,
whilst the specific triangulation gluing sets the number of $2-3$ and $3-2$
moves (and the rarer $4-1$ moves). The density in Figure 5(b) has a weak
inverse relationship to the number of nodes, where adding nodes to a large
graph introduces many more potential edges, and this respectively drops the
density value. Since the density does drop according to this behaviour this
demonstrates that the Pachner graph edge sets grow slower than the node sets.

We also analysed the size of the Pachner graphs as a function of the
hyperbolic volume of the manifolds and their number of cusps (which varies
from $1$ to $3$ in our dataset). The result is shown in Figure 6(a). Looking
at the figure one realises that there are ‘peaks’ in the sizes of the Pachner
graphs for one cusped manifolds and that these peaks correspond to the first
red dots, namely the lowest volume $2$-cusped manifolds. This is no random
phenomenon. The blue dot with highest size of the Pachner graph and volume
$<3.63$ turns out to be “v0117” (in snappy’s nomenclature, IsoSig:
hLALPkbcbefggghxwnxibk) and drilling out its shortest geodesic one gets “m129”
(IsoSig: eLPkbdcddhgggb) which is the second lowest volume manifold in
snappy’s census with number of cusps $2$ (it corresponds to one of the two
leftmost red dots in the figure). This leads us to think that the size of the
Pachner graph could be inversely related to the length of the shortest
geodesic in the hyperbolic manifold which, by Thurston-Jorgensen’s theorem on
hyperbolic Dehn fillings corresponds to Dehn fillings of manifolds with one
more cusp with very large filling slopes. In order to check this we plotted in
Figure 6(b), the sizes of the Pachner graphs with respect to the length $\ell$
of the shortest geodesic in the cusped manifold and the plot clearly shows
that such number is bounded below by a function of $1/\ell$. Furthermore, a
closer look reveals that the dots come in families, corresponding to which
manifold is obtained by drilling the shortest geodesic. This is exemplified in
Figures 7(a) and 7(b) where the same analysis as before is restricted to the
manifolds whose drilling is a fixed one, here “m129” (chosen just as an
example). All this seems to corroborate the following

######  CONJECTURE 1.

The growth rate of the Pachner graph of a cusped hyperbolic $3$-manifold $M$
is correlated to the inverse of the length of the shortest geodesic in $M$.

Degrees: The node degree distribution of a graph can be described by a
histogram showing the frequency of the nodes that have a certain number of
edges incident to them. Averaging the degree distributions over the entire
considered census partition produces the plot given in Figure 5(c) (i.e. the
mean frequency of 3_23 nodes with degree 1 across the 4815 manifolds in this
census subset is 368.9). For both move styles all graphs had at least one
edge, so that a move of either form could always be performed on the initial
triangulation. This is shown by a 0 mean frequency of degree zero, so that no
Pachner graphs were the trivial empty graph formed by a single node and no
edges. For both move styles the degree distributions were bimodal, with 2
peaks, indicating that some moves (in both cases) significantly open up the
number of new subsequent move possibilities and thus have much higher degree
in this exhaustive graph generation. The peaks in the distributions
(particularly for degree 1) are due to the leaves of the Pachner graphs
created in the latter moves at the limit of the generation truncation, however
they can occur otherwise as exemplified in Figure 3(a). The 3_23 graphs have a
larger relative size between the bimodal peaks than the 3_14 graphs
($368.90/13.94=26.46>8.48=107.04/12.63$), so that the 3_14 graphs’ nodes are
more skewed to higher degrees as these moves are more likely to open up many
move possibilities, despite there being less possibilities demonstrated by the
degree value for the second peak. The 3_23 graphs also have a larger
difference between their two peaks ($18-1>14-2$), indicating that the edges
are less evenly distributed between the nodes. This is linked to the move
possibility scaling, where as a $2-3$ move changes the number of tetrahedra in
a triangulation from $N$ to $(N+1)$ the approximate scaling of the $2-3$ move
possibilities grows at a rate of order $2N$ (i.e. the number of faces mod the
number of tetrahedra per face, $4/2=2$). Alternatively as a $1-4$ move changes
the number of tetrahedra from $N$ to $N+3$ the scaling of the $1-4$ move
possibilities grows exactly at a rate of $N$. Therefore, particularly as moves
increase the number of tetrahedra, there are on average relatively more $2-3$
moves which can be made, leading to higher degree nodes777Note in this crude
leading behaviour approximation we neglect contributions from the less
probably inverse $3-2$ and $4-1$ moves..

(a) Clustering

(b) Shortest Path

(c) Centrality

(d) Cycles

Figure 8: Core network analysis properties of the Pachner graphs for the
orientable cusped census partition with number of initial tetrahedra $<8$.
Analysis considers building the Pachner graphs to depth 3 with either the
$\\{1-4,4-1\\}$ (denoted 3_14) or the $\\{2-3,3-2\\}$ (denoted 3_23) moves,
plotting histograms of: (a) the square clustering coefficients; (b) the
normalised Wiener index; (c) the range of eigenvector centrality values; and
(d) the length of the minimum cycle basis.

Clustering: As in the previous Pachner graph analysis the triangle clustering
coefficients for graphs across the census were all zero, since these graphs
can only exhibit even length cycles. However the square clustering
coefficients had (min,mean,max) across the census for the 3_14 graphs of
$(0.028,0.038,0.104)$ and for the 3_23 graphs of $(0.000,0.018,0.035)$, with
only the 3_23 graphs having examples of 0 square clustering coefficients,
occurring for 2 manifolds. The full distributions are shown in Figure 8(a),
they show that 4-cycles are always introduced with $1-4$ moves since all the
initial triangulations have at least 2 tetrahedra so a $1-4$ move on each
followed by their inverses in the other order automatically creates a 4-cycle.
In general 4-cycles are less likely with $2-3$ moves since the gluings change
more non-trivially and hence alternating inverses may be obstructed. The 3_14
graphs again have higher frequencies, indicating they are more likely to have
similar graph structure.

Shortest Paths: The normalised Wiener index provides a global measure of the
average shortest path length between any two nodes in the Pachner graph, that
can be appropriately compared between graphs. The (min,mean,max) values for
the 3_14 graphs were $(2.04,4.54,4.87)$ and for the 3_23 graphs were
$(3.08,5.08,5.48)$. In Figure 8(b) a histogram of these values are plotted
also, showing that the 3_14 graphs tend to have shorter shortest paths between
nodes so that they can be traversed more easily, and it may be better to enact
first these moves were possible in triangulation simplification methods. The
3_14 graphs have higher frequencies, again supporting that graphs created by
these moves are more similar and less dependent on the underlying manifold
topology.

Centrality: Eigenvector centrality uses the eigenvector values corresponding
to the adjacency matrix’s unique largest eigenvalue to assign centrality
scores. Since these scores are relative their absolute values are less
relevant, and instead focus in this work is placed on the range of values
across a given Pachner graph (highest $-$ lowest centrality score). The
(min,mean,max) values of the centrality ranges for the 3_14 graphs were
$(0.175,0.271,0.553)$ and for the 3_23 graphs were $(0.190,0.261,0.502)$; with
487 of the 4815 3_14 graphs having the initial triangulation as the most
central, and 485 times for the 3_23 graphs. Therefore, of the 4815 manifolds
only $\sim\frac{1}{4}$ have the initial node as the most central node in both
cases, implying the generation process is highly non-symmetric. The similar
centrality ranges for both move styles indicate similar adjacency
eigendecompositions. Again higher 3_14 frequencies indicate similar graph
structures.

Cycles: As previously observed, Pachner graphs can only exhibit even cycles,
and additionally 2-cycles are not possible in this Pachner graph design where
undirected edges represent the ability to move between triangulations (not a
unique move). Since the graphs generated in the census were truncated at depth
3, the largest cycle size possible is 6, and hence the cycle bases for all
these graphs were spanned by 4-cycles and 6-cycles. The average number of 4
and 6-cycles in each minimum cycle basis for the census partition’s generated
Pachner graphs were $(155.16,0.00)$ for 3_14 graphs and $(354.58,12.87)$ for
3_23 graphs. These results show that although the Pachner graphs are only
generated to depth 3 they are higher interconnected with a huge number of
cycles. The 3_23 graphs have more cycles on average as there are many more
move choices, and hence much more path degeneracy. Surprisingly the 3_14
graphs never exhibit 6-cycles, presumably because in all scenarios they are
visible they were decomposable into 4-cycles in the basis length minimisation
process (as the reordered inversion of any 3 $1-4$ moves to make a 6-cycle
would have all reorderings of 2 moves making sub 4-cycles). Higher frequencies
for these 3_14 graphs again indicate similar graph structures with similar
cycle decompositions, less dependent on underlying topology.

(a) Number of Tetrahedra

(b) Pachner Graph Size

Figure 9: Distributions of number of tetrahedra in triangulations across the
4815 Pachner graphs of the orientable cusped census partition with number of
initial tetrahedra $<8$. Analysis considers building the Pachner graphs to
depth 3 with either the $\\{1-4,4-1\\}$ (denoted 3_14) or the $\\{2-3,3-2\\}$
(denoted 3_23) moves, plotting (a) a histogram of the average number of
tetrahedra across each Pachner graph; and (b) the number of tetrahedra in the
initial triangulation against the number of nodes in the Pachner graph. Note
the number of initial tetrahedra take integer values and the vertical lines
are offsetted for visibility.

Number of Tetrahedra: The number of tetrahedra in each triangulation across a
Pachner graph can only take 1 of 4 values (as only generated up to depth 3),
based on an initial triangulation with $N$ tetrahedra and a move set of
$\\{2-3,3-2\\}$ then the values are $\\{N,N+1,N+2,N+3\\}$, alternatively for
move set $\\{1-4,4-1\\}$ the values are $\\{N,N+3,N+6,N+9\\}$. This is because
the moves always change the number of tetrahedra by a fixed amount, and
therefore the number of tetrahedra in the initial triangulation is paramount
to determining the spectrum, which is selected for the dataset to be a local
minimum. We note that this is not always a unique minimum as the frequency of
triangulations with as many tetrahedra as the initial triangulation is
occasionally $>1$. The number of tetrahedra in the initial triangulation takes
values of $(2,3,4,5,6,7)$ across the census partition, with respective
frequencies $(2,9,56,234,962,3552)$. Therefore most manifolds are initialised
with triangulations with 7 tetrahedra.

Figure 9(a) shows a histogram of the average number of tetrahedra across each
Pachner graph, plotted for all members of the census partition. It shows that
the 3_14 graphs have a higher average number of tetrahedra, expected since the
$1-4$ moves introduce more tetrahedra than the $2-3$ moves (and both these are
more common than their inverses). There are also higher frequencies for these
graphs as the graph structures are similar with each tetrahedron available to
perform a $1-4$ move irrespective of its gluing. Moreover, Figure 9(b) shows
how the number of tetrahedra in the initial triangulation correlates with the
number of nodes in the generated Pachner graph. Generally, more initial
tetrahedra leads to more nodes and larger graphs, with larger ranges for the
graph sizes as the initial number increases; this is related to more
tetrahedra providing more possibilities for moves, facilitating the rapid
graph growth with depth. Since the number of places to apply $2-3$ moves grows
quicker than for $1-4$ moves (each new tetrahedra introduce $>1$ new common
faces) these 3_23 graphs are more responsive to the initial number of
tetrahedra but also exhibit a greater range of values as the combinatorics is
more susceptible to limitations caused by complicated gluings.

Considering the limiting behaviour in the $3\\_23$ graphs of a tree-like
Pachner graph (no IsoSigs are repeated during generation) for the case of only
considering $2-3$ moves (ignoring the $3-2$ inverse move), if one were to
start with a triangulation of $N$ tetrahedra, in this limiting case this means
there are $2N$ common faces to perform $2-3$ moves and hence $2N$ nodes at
depth 1 of the Pachner graph. Each of these triangulations will have $N+1$
tetrahedra, and hence $2(N+1)$ faces for $2-3$ moves, leading to $4N(N+1)$
nodes at depth 2. Similarly, these triangulations will now have $N+2$
tetrahedra, $2(N+2)$ faces for $2-3$ moves, leading to $8N(N+1)(N+2)$ nodes at
depth 3. In this limiting case one would then expect
$8N(N+1)(N+2)+4N(N+1)+2N+1=8N^{3}+28N^{2}+22N+1=8N^{3}+\mathcal{O}(N^{2})$
nodes of the Pachner graph. Mapping this leading order behaviour to the
initial $N$ values considered in Figure 9(b), the predicted number of nodes
would respectively be $(64,216,512,1000,1728,2744)$ for the $N$ range $[2,7]$,
which does approximately match the observed maximum counts in the plots. The
deviations from the maxima are when this limiting tree-like Pachner graph
approximation breaks down, as triangulations are repeated in generation and
the graph exhibits cycles (as well as minor effects from the less frequently
occurring $3-2$ moves). Equivalently in the $3\\_14$ graphs for the limit case
of only $1-4$ moves in a tree-like Pachner graph, an initial triangulation
with $N$ tetrahedra has exactly this many tetrahedra to perform $1-4$ moves,
leading to $N$ Pachner graph nodes at depth 1. Respectively there are then
$N(N+1)$ nodes at depth 2, and $N(N+1)(N+2)$ at depth 3, for an overall
estimate of $N^{3}+4N^{2}+4N+1=N^{3}+\mathcal{O}(N^{2})$. The respective
estimates would then be $(8,27,64,125,216,343)$, again matching the observed
order of the maxima in Figure 9(b).

##  4 Machine Learning IsoSigs

In recent decades, machine learning methods have seen a wealth of successes
across many fields academia. This can largely be attributed to the exponential
growth in computational power, allowing the generation of ever-larger datasets
for broader and more thorough analysis.

Mathematical data has a unique advantage in that it is exact, there is no
noise from experimental apparatus, and as such any statistical patterns in
data can be interpreted to have more direct meaning about the data’s
underlying structure. However, new mathematical data can often be generated
infinitely, and thus exhaustive computation becomes impossible, relying on
appropriate sampling. Hence there is a true need for statistical methods when
performing analysis on these large datasets. The computational statistical
methods we explore here come under machine learning.

In this work we examine the IsoSig representation of 3-manifold
triangulations, testing how well can machine learning methods learn to
identify manifolds from these IsoSigs. Already, as demonstrated in §2.2,
identifying the equivalence of the triangulations is highly computationally
intensive. Where sequences of Pachner moves between two triangulations are not
known to exist, the results from machine learning can provide a probability of
existence of such a sequence moves. Successes in learning IsoSig equivalence
for 3-manifolds then opens up the scope for development into learning manifold
properties and finding explicitly the connecting paths between triangulations.

For these investigations the IsoSig input data is paired with an output label
which identifies to which manifold the triangulation belongs to. The machine
learning problem is in the style of supervised classification, where the
network seeks to sort IsoSigs corresponding to different manifolds into
separate classes. In this setup, the networks are learning the combinatoric
structure of triangulations which differentiates the manifolds, directly
linked to their respective topology.

Specifically, for each of the eight 3-manifolds considered, a large Pachner
graph was generated to depth 8 as described in §3. From there the frequency
distribution of IsoSig lengths was computed across all IsoSigs in each
manifold’s Pachner graph. Then an appropriate length was selected such that
sufficiently large samples could be taken from each Pachner graph to produce
datasets of fixed length IsoSigs888As noted previously, initial testing showed
that padding mixed length IsoSigs caused the architectures to focus
exclusively on the distribution of lengths, which was sufficiently different
between manifolds to lead to good classification results. This simplification
was avoided by considering a fixed length.; the fixed length considered was 30
characters.

For computational processing these IsoSigs were converted to arrays of
integers, using one-hot encoding of each character in the IsoSig. Since the
vocabulary consists of $64$ characters
{a,b,c,...z,A,B,C,...,Z,0,1,2,...9,+,-}, the encoding of each character is a
$64$-dimensional sparse vector of 0s with a single 1 in the dimension indexing
that character in the vocabulary. Therefore, because all IsoSigs considered
for ML were $30$ characters long, each IsoSig was encoded by a $30\times
64=1920$-dimensional vector. Despite this representation being rather memory
intensive, requiring more computational resources for training any
architecture, the naturalness of the one-hot encoding style (where each
character is an independent dimension) makes learning clearer and more
interpretable999The other natural encoding of just mapping each character to a
number $0\mapsto 63$ was tested however lead to lower learning performance
scores..

###  4.1 Differentiating Manifolds

In this section, the machine learning architectures of neural networks (NNs)
and transformers are both applied to the problem of binary classifying IsoSigs
belonging to different manifolds. For the eight 3-manifolds focused on in this
work, this creates ${8\choose 2}=28$ pairs of manifolds to design paired data
for, and perform binary classification on. Creating 28 binary datasets to
learn: {IsoSig} $\longmapsto\\{0,1\\}$, the performance can then be compared
between different manifold pairings, providing insight into what topological
properties about the manifolds, encoded in the IsoSigs, the networks use to
differentiate between manifolds.

The NN architecture is the prototypical machine learning model, it is very
adaptable, and used ubiquitously with great success throughout many fields.
Any NN is made up of sets of neurons organised into layers, where each neuron
takes in a vector of inputs, and outputs a single number. The neuron acts on
the input vector x with a linear function, then a non-linear ‘activation’
function101010Here we use the leaky-ReLU activation function, which has
significant speed advantages due to its simplicity, and effectively makes the
training process the fitting of a piecewise linear function., such that:
$\textbf{x}\mapsto act(\textbf{w}\cdot\textbf{x}+b)$ for the trainable
parameters of weights vector w and bias scalar $b$.

Conversely, the transformer architecture is much more sophisticated, and
involves many stages of sub-NNs for encoding and decoding, primarily relying
on the concept of attention [69] to learn context amongst the input strings –
note transformers do not require the tensorial encoding of the IsoSigs, but do
require substantial computational resources, so are tested less extensively in
this work.

####  4.1.1 Neural Networks

The NNs used in these investigations were built using tensorflow [51], with
architecture of three dense layers (sizes 256, 128, 64) then a final dense
layer of size 2 for the one-hot encoded binary output; all layers used leaky-
ReLU activation (factor 0.01), L2 regularisation, and dropout (factor 0.01) –
except for the output layer using softmax activation for the binary
classification. The NNs were trained with an Adam optimiser to minimise the
binary cross-entropy loss for 30 epochs with a batch size of 64 and a learning
rate of 0.001.

Binary classification performances were measured with accuracy (the proportion
of correctly classified test IsoSigs), and Matthew’s correlation coefficient
MCC (an unbiased alternative to accuracy). Both measures evaluate to 1 for
perfect learning, whereas for no learning in a binary classification problem
accuracy is 0.5 and MCC is 0. Each binary classification investigation was
performed 5 times on 5 different partitions of the IsoSig data into train and
test sets, providing statistical confidence in the mean performance measures
reported (this process is known as cross-validation).

The performance measure results are arranged in a matrix format in Figure 10.
Each entry in the matrix $M_{ij}$ represents the mean measure score across the
cross-validation runs for the binary classification of IsoSigs pairs between
manifolds with index $i$ and index $j$ in the list: $(S^{3},S^{2}\times
S^{1},\mathbb{RP}^{3},L(7,1),L(7,2),T^{3},PHS,H_{SC})$111111The diagonal cases
$M_{ii}$ do not represent sensible experiments so had values set to 1, whilst
the symmetric nature of the investigations was enforced by setting the lower
diagonal equal to the upper diagonal.. Heat maps of these matrices are also
shown for ease of comparison.

(a) Accuracy

$\begin{pmatrix}1.0&0.49&0.5&0.737&0.484&0.923&0.828&0.947\\\
0.49&1.0&0.502&0.796&0.582&0.909&0.845&0.96\\\
0.5&0.502&1.0&0.778&0.545&0.919&0.839&0.955\\\
0.737&0.796&0.778&1.0&0.705&0.941&0.883&0.953\\\
0.484&0.582&0.545&0.705&1.0&0.908&0.814&0.948\\\
0.923&0.909&0.919&0.941&0.908&1.0&0.836&0.937\\\
0.828&0.845&0.839&0.883&0.814&0.836&1.0&0.943\\\
0.947&0.96&0.955&0.953&0.948&0.937&0.943&1.0\end{pmatrix}$

(b) MCC

$\begin{pmatrix}1.0&0.001&0.011&0.477&0.0&0.715&0.658&0.504\\\
0.001&1.0&-0.003&0.594&0.166&0.663&0.692&0.623\\\
0.011&-0.003&1.0&0.56&0.083&0.695&0.68&0.594\\\
0.477&0.594&0.56&1.0&0.409&0.788&0.767&0.57\\\
0.0&0.166&0.083&0.409&1.0&0.664&0.629&0.489\\\
0.715&0.663&0.695&0.788&0.664&1.0&0.317&0.834\\\
0.658&0.692&0.68&0.767&0.629&0.317&1.0&0.458\\\
0.504&0.623&0.594&0.57&0.489&0.834&0.458&1.0\end{pmatrix}$

Figure 10: Matrices and their corresponding heat maps representing the (a)
mean accuracy and (b) mean MCC scores for the binary classification between
the datasets of length 30 IsoSigs generated using $\\{2-3,3-2\\}$ moves;
averaged over the 5-fold cross-validation runs. Lighter colours represent
higher performance scores, where accuracy evaluates in the range $[0,1]$, and
MCC in the range $[-1,1]$. The matrix is manifestly symmetric as the pair
order is irrelevant, and the diagonals are trivially 1 where no classification
was required. The manifolds are ordered: $(S^{3},S^{2}\times
S^{1},\mathbb{RP}^{3},L(7,1),L(7,2),T^{3},PHS,H_{SC})$.

For each matrix the off-diagonal scores respectively have (min, mean, max):
(a) Accuracy (0.4835, 0.800, 0.960), (b) MCC (-0.003, 0.487, 0.834); showing a
range from no learning to near-perfect learning. Comparing between manifolds,
the positive curvature manifolds are harder to differentiate amongst each
other. The other binary classifications have surprisingly high performances in
(a) and (b), noting particularly the success of the $L(7,1)$ vs $L(7,2)$
classification which are notoriously difficult manifolds to differentiate
(they are homotopy equivalent but not homeomorphic). To exemplify the learning
behaviour, for this classification the accuracy performance measure was
tracked throughout the training process on the training data used for updating
the NN parameters and the independent validation data. The accuracy scores
throughout training, evaluating at each epoch, are shown in Figure 11. This
plot highlights that the performance improves quickly as the general behaviour
can be learnt, but does plateau at the limiting score – indicating there are
triangulations which are truly difficult to differentiate the manifold
structure between.

Figure 11: Example NN binary classification training curve, between length 30
IsoSigs for manifolds $L(7,1)$ and $L(7,2)$ generated using $\\{2-3,3-2\\}$
moves up to depth 8. The plot shows that the accuracy performance measure for
both training and validation sets increased quickly, converging to the final
performance within a few epochs.

Interestingly, the manifold which is best distinguished from all the other $7$
is the Weeks manifold, the only hyperbolic one in the lot. At the opposite,
$S^{3},S^{2}\times S^{1}$ and $\mathbb{RP}^{3}=L(2,1)=SO(3)$ are not
distinguished at all.

##### NN Gradient Saliency

We performed an in-depth analysis of the gradient saliency values used by our
NN to distinguish $L(7,1)$ vs $L(7,2)$. A trained NN represents a function
from inputs to outputs, in the case of these problems this is an input of a
single IsoSig, one-hot encoded from length 30 in a length 64 alphabet to a
length 1920 vector and an output of a length 2 vector with each entry
evaluating in the range $[0,1]$ (as a probability distribution over the 2
classes) whose larger value indicates the predicted manifold the input IsoSig
triangulation represents.

Computing the derivatives of the NN function outputs with respect to each of
the inputs (i.e. for each index of each encoded letter in the IsoSig) provides
a gradient function for each input. Evaluating these functions on each IsoSig
in the test data gives numerical values for how sensitive the output
classification is to each input value. Averaging over all inputs in the test
data, and across multiple cross-validation runs, then normalising the output
gradients, provides relative gradient measures with greater statistical
confidence.

Figure 12: Image representation of the gradient saliency results for NN binary
classification between IsoSigs from manifolds $L(7,1)$ and $L(7,2)$ generated
using $\\{2-3,3-2\\}$ moves. Each row is the encoding of one of the 30 IsoSig
characters in the length $64$ alphabet, reshaping the 1920 length input vector
into a $(30,64)$ size matrix. Lighter colours indicate a more significant
sensitivity to that input for the output classification.

For the $L(7,1)$ vs $L(7,2)$ classification, these gradient saliency values
were averaged over 100 cross-validation runs, and the final gradient values
are represented in Figure 12, where each of the 30 rows is an IsoSig character
one-hot encoded into the length 64 alphabet. Lighter colours indicate more
sensitivity of the classification output to that input. The results in the
figure show that the most important parts of the IsoSig input are later
characters in the IsoSig and that these are more likely to be lower case
letters from the start of the alphabet.

The rough behaviour of the Figure 12, respects the IsoSig encoding structure
as described in Appendix §A. The first row is $\pi(n)$, and as all these
triangulations have 10 tetrahedra only the 10th character in the alphabet (j)
has a non-zero saliency and a slightly brighter colour. The next rows show
importance on characters deeper in the alphabet, matching the triple encoding
structure of the type sequence where higher index characters are regularly
expressed. Following this is a wide-diagonal-like structure up to the 10th
character, which coordinates with the destination sequence being bound by $n$,
which here is 10. Since the tetrahedra are numbered as the destination
sequence is built this explains why higher index characters are more important
later on as the earlier new tetrahedra seen would be allocated lower numbers.
The final section of Figure 12 shows a box of important values, up to the 23rd
character, matching the permutation sequence behaviour where there’re only 23
permutations in $S_{4}$ for relabelling vertices. This part shows that all
potentially observed permutations are important for the architecture’s
classification, and since the brightest colour are exhibited in this part this
information tends to be the most useful for distinguishing triangulations of
these geometries.

Further examining the actual saliency values (represented by colours in Figure
12), averaged over all of the cross-validation runs as well as each runs test
dataset, we can plot a histogram of the average saliency size, as shown in
Figure 13(a). This image shows a partition of values with a selection having
normalised gradients $>10^{-4}$ and the majority having values $<10^{-6}$.
There is therefore a clear selection of ‘important’ inputs and ‘non-important’
ones. Taking the input indices corresponding to the larger ‘important’
saliency values $>10^{-4}$, these can be sorted into what character in the
alphabet they correspond to (as plotted in a histogram in Figure 13(b)), or
into what character in the length 30 IsoSig they correspond to (as plotted in
a histogram in Figure 13(c)).

(a)

(b)

(c)

Figure 13: Saliency analysis for the $L(7,1)$ vs $L(7,2)$ binary
classification, averaged over 100 NNs. A histogram of the average saliency
absolute values across the 1920 input vectors is shown in (a), demonstrating a
partition into more/less important features. Subsequently (b) shows a
histogram of the more important features with saliency value $>10^{-4}$ sorted
according to the letter in the alphabet they correspond to; whilst (c) shows a
histogram of the same set sorted according to which of the 30 characters in
the input IsoSig they correspond to.

Figure 13(b) shows that the 363 ‘important’ inputs correspond to only a subset
of the full alphabet – predominantly the beginning of this alphabet with a few
letters deeper in. Equivalently, these same important input features have much
higher frequencies towards the end of the IsoSig as shown in Figure 13(c).
From this saliency analysis the NNs are hence relying most on the final
entries of the IsoSigs (the permutation sequence) to determine the manifold,
and the value of these entries becomes discriminant. Additionally the
occurrence of specific letters (like h or i with the highest frequency in
Figure 13(b)) can significantly help the architectures confidence in
classification.

####  4.1.2 Transformers

Since the IsoSig data closely resembles that of text, one may sensibly
question how transformer architectures, which have seen great performance in
many natural language processing problems [70, 71], perform when classifying
this data.

A popular baseline for performing binary classification tasks with
transformers is to use the BERT (Bidirectional Encoder Representations from
Transformers) architecture [72]. In a similar vein to that employed in §4.1.1,
the BERT model is now used to classify whether a given pair of IsoSigs
represent the triangulations of the same manifold. This model is implemented
using the transformers library [73].

Transformers are primarily successful as large language models, and due to
this tend to have a very large number of trainable parameters. To make
training feasible, their use often relies upon the principle of transfer
learning, where the models are pre-trained on a large standard set of data,
and then retrained on a smaller specialised set. This use of pre-trained
models can avoid tens of thousands of core hours in retraining, and is what
makes these large language models feasible to use at all. However, the pre-
trained models publicly available are trained on language data (often English
language text). This hence, raises appropriate concerns about the success of
transfer learning onto this IsoSig 3-manifold ‘language’ data, which does not
resemble the syntactical and grammatical structure of the English language.

Nevertheless, due to their paramount successes in recent times, it is
interesting to examine their performance in this context. To do so we take the
binary classification of the $L(7,1)$ and $L(7,2)$ datasets, as performed by
the NNs to Accuracy and MCC scores of (0.705, 0.409) respectively, and repeat
the training and testing using the BERT model. Using a single layer output
classifier to change the standard 768 output dimension of the BERT model to
the 2 binary classes, along with equivalent hyperparameters such as training
with the Adam optimiser and cross-entropy loss for 30 epochs with a batch size
of 64 and learning rate of 0.001. The transformer performance scores were:

$\begin{split}\text{Accuracy}&=0.689\;,\\\ \text{MCC}&=0.381\;.\end{split}$
(4.1)

Unfortunately, whilst some learning was achieved, the performance was not as
good as the NN models, likely due to the inappropriate nature of the English
language pre-training misleading the classification. In addition to worse
performance, the transformers also required significantly more computational
resources (time, power, memory). To exemplify this, whilst the NNs took the
order of seconds to train and test, this simplest transformer model took the
order of hours, and required orders of magnitude more memory to run.

Therefore, although it was relevant experimentation, these results support the
motivation to focus on the NN architecture for learning of triangulation
IsoSig properties.

###  4.2 Differentiating Knots

By a famous result of Gordon and Luecke, the complement of a knot entirely
determines the knot [74]. This allows one to identify knots with
$3$-manifolds, as the knot complement embedded within $S^{3}$; and with this
motivation the workflow we have set-up may also be directly extended to study
and distinguish knots.

In this work, we again put focus on a selection of knots, in particular
focusing on the most fundamental knots with a low number of crossings. These
knots are labelled: {Unknot, Trefoil, FigureEight, $5_{1}$, $5_{2}$, DT
$6a_{3}$ (a.k.a. $6_{1}$), DT $8n_{1}$ (a.k.a. $8_{2}$)}, where the final knot
is hyperbolic non-alternating. The figure eight and the $5_{2}$ knot are the
smallest hyperbolic knots in the $3$-sphere and indeed it turns out that they
are more difficult to distinguish. In a similar way one could expect some
difficulties in distinguishing the torus knots $3_{1}$ (the trefoil) and
$5_{1}$ (the cinquefoil) but it is not so much the case (see Figure 14).

Again all the initial IsoSigs are 1-vertex, and are generated using only $2-3$
and $3-2$ moves. The initial IsoSigs for these knot complement 3-manifolds are
given in Table 4, along with the respective number of tetrahedra in each
initial triangulation.

Knot | Initial IsoSig | # Tetrahedra
---|---|---
Unknot | cMcabbgds | 2
Trefoil | cPcbbbadu | 2
Figure Eight | cPcbbbiht | 2
$5_{1}$ | dLQbcccaekv | 3
$5_{2}$ | dLQbcccdero | 3
DT $6a_{3}$=$6_{1}$ knot | eLPkbcddddcwjb | 4
DT $8n_{1}$=$8_{2}$ knot | fLLQcbcdeeedowxxd | 5
Table 4: The knot IsoSigs used to start the generation of Pachner graphs using
only $2-3$ and $3-2$ moves. Each knot was used to construct a knot-complement
3-manifold, which were triangulated to give a 1-vertex triangulation. The
respective IsoSigs are listed in this table, along with the number of
tetrahedra in this initial triangulation.

The Pachner graphs were generated up to a depth that provided a suitable
amount of data for a fixed IsoSig length. Again searching for 2000 IsoSigs per
Pachner graph, the selected IsoSig length was 25 characters. From there the
same NN architecture was trained to perform binary classification between the
knot complement manifolds. The binary classification learning was performed
for each pairing of knot-complement 3-manifolds, where the accuracy and MCC
scores are displayed in Figure 14.

$\begin{pmatrix}1.0&0.632&0.612&0.576&0.629&0.714&0.752\\\
0.632&1.0&0.657&0.6&0.71&0.748&0.782\\\
0.612&0.657&1.0&0.583&0.491&0.612&0.662\\\
0.576&0.6&0.583&1.0&0.584&0.681&0.718\\\
0.629&0.71&0.491&0.584&1.0&0.544&0.658\\\
0.714&0.748&0.612&0.681&0.544&1.0&0.626\\\
0.752&0.782&0.662&0.718&0.658&0.626&1.0\end{pmatrix}$

$\begin{pmatrix}1.0&0.265&0.224&0.153&0.259&0.429&0.505\\\
0.265&1.0&0.313&0.201&0.42&0.499&0.565\\\
0.224&0.313&1.0&0.168&0.0&0.227&0.33\\\
0.153&0.201&0.168&1.0&0.168&0.366&0.437\\\
0.259&0.42&0.0&0.168&1.0&0.092&0.316\\\
0.429&0.499&0.227&0.366&0.092&1.0&0.254\\\
0.505&0.565&0.33&0.437&0.316&0.254&1.0\end{pmatrix}$

Figure 14: Matrices and corresponding heat maps representing the (a) mean
accuracy and (b) mean MCC scores for the binary classification between the
datasets of length 25 knot complement IsoSigs generated using $\\{2-3,3-2\\}$
moves; averaged over the 5-fold cross-validation runs. Lighter colours
represent higher performance scores, where accuracy evaluates in the range
$[0,1]$, and MCC in the range $[-1,1]$. The matrix is manifestly symmetric as
the pair order is irrelevant, and the diagonals are trivially 1 where no
classification was required. The manifolds are ordered: (Unknot, Trefoil,
FigureEight, $5_{1}$, $5_{2}$, DT $6a_{3}$, DT $8n_{1}$).

The results show comparable performances between knots, however with worse
maximum performances compared to the general 3-manifold learning in §4.1. Some
pairings had close to no learning, better exemplified by the near-zero MCC
scores for the (FigureEight,$5_{2}$) and the ($5_{2}$,DT $6a_{3}$) pairings.
Generally, as shown by the images, the colours are darker closer to the
diagonal, indicating worse performance, and suggesting that in general the
more disparate the crossing structure of the knot the easier the NNs can
distinguish them. These accuracies obtained in the task of comparing with the
unknot are by far less good than those shown for this specific task in [37].

####  4.2.1 Supplementing with Dehn Surgery

In addition to learning with their knot-complement manifolds, we also perform
two Dehn surgery operations (0-surgery and 1-surgery) whereby a tubular
neighbourhood of a knot is drilled out and then filled with a solid torus
[75].

Dehn surgery is a standard operation in topology allowing modification of the
topology of a $3$-manifold by a ‘cut and paste’ operation on the $D^{2}\times
S^{1}$-neighborhood of a knot consisting in re-gluing the solid torus as
$S^{1}\times D^{2}$. This operation is also called $0$-Dehn surgery and more
in general $n$-Dehn surgery consists in regluing the solid torus after
twisting the image of the meridian $n$-times along the longitude. In
particular operating $0$ or $1$ surgeries along knots in $S^{3}$ one produces
closed oriented $3$-manifolds with the homology respectively of $S^{2}\times
S^{1}$ and of $S^{3}$. These manifolds are themselves canonically associated
to the knots so their homeomorphism type is by itself a knot invariant, albeit
a complicated one. Here we try and distinguish knots by distinguishing these
surgery manifolds.

Focus is put on the differentiation between the Unknot and Trefoil binary
classification problem, which for the knot complement $3$-manifolds classified
with accuracy 0.632 and MCC 0.265, neither particularly impressive scores. In
this extension, the initial knot complement triangulation IsoSigs, as given in
Table 4, had either 0-surgery or 1-surgery performed on them, to produce
further $3$-manifolds whose IsoSigs are given in Table 5. We remind the reader
that the $0$ and $1$ surgeries on the unknot are respectively $S^{2}\times
S^{1}$ and $S^{3}$ and on the left handed trefoil they are two Seifert fibered
manifolds, respectively $(S^{2},(2,1),(3,1),(6,-5))$ and
$(S^{2},(2,1),(3,1),(7,-6))$ (the latter _not_ being the Poincaré homology
sphere, which is the $1$ surgery over the _right_ handed trefoil). Each of
these was used to seed Pachner graph generation to generate databases of 2000
length 30 IsoSigs. Noting that in this subsection length 30 was used again
instead of the length 25 as used in §4.2, this is because the initial IsoSigs
after surgery lead to length distributions with very few length 25
IsoSigs121212This is also why just these two simplest knots are considered
since the length distributions for some knot complements after surgery did not
even include any length 25 or 30 IsoSigs.. Another comment worth emphasising
is that whilst the IsoSigs in Table 5 have a range of initial number of
tetrahedra, since only a fixed length IsoSig is taken from the graph for ML
these IsoSigs will also correspond to triangulations with the same number of
tetrahedra. Additionally, it is worth noting that the initial IsoSig from
0-surgery of the Unknot is a triangulation with 3-vertices (whilst the others
are still all 1-vertex), this means this Pachner graph is a no longer a
1-vertex Pachner graph.

Manifold | Surgery | IsoSig | # Tetrahedra
---|---|---|---
Unknot | 0 | cMcabbjaj | 2
1 | cMcabbgag | 2
Trefoil | 0 | gvLQQcdefeffnjndspx | 6
1 | hLLLQkcdefgfgghsdaenjw | 7
Table 5: The surgery Isosigs used to start generation of Pachner graphs using
only $2-3$ and $3-2$ moves.

With these datasets of 2000 length 30 IsoSigs corresponding to surgeries of
these knot complements, the respective ML binary classification between the
knots was repeated for each surgery operation. The NN architecture used was
the same as throughout this work, as quoted in §4.1.1. The 5-fold cross-
validation performance scores are given in Table 6, including the values for
the knot complements without surgery repeated from §4.2.

Investigation | Accuracy | MCC
---|---|---
Knot Complement | $0.632$ | $0.265$
0-surgery | $0.935$ | $0.871$
1-surgery | $0.974$ | $0.949$
Table 6: NN binary classification performance scores for the knot complements,
the 0-surgeries, and the 1-surgeries, between the Unknot and Trefoil knots.
Scores were averaged over 5 cross-validation runs.

Performances are substantially higher after surgery, for either surgery
actions. It is interesting to observe that since $0$ and $1$-surgeries over
the unknot are $S^{2}\times S^{1}$ and $S^{3}$ respectively, the problem
discussed here is yet another instance of the problem analysed in §4.1 and the
accuracies for the $0$-surgery and $1$-surgery cases are comparable with those
seen in Figure 10. These performances are quite high and show that one can
easily complement the initial performances for the simple knot complements
with further parallel analyses. The potential for distinguishing knots seems
therefore quite high.

##  5 Conclusions and Outlook

In this work triangulations of 3-manifolds were studied via their IsoSig
representation. A selection of 3-manifolds were chosen to be of focus in this
study, along with a selection of knot complements from knots exhibiting a low
number of crossings. Their databases of triangulations were generated through
their Pachner graphs, exhaustively performing $\\{2-3,3-2\\}$ moves on an
initial triangulation up to some pre-specified depth. The graph structure of
these graph was also analysed through a variety of network analysis
techniques.

Pachner graph network analysis made some preliminary connections between the
3-manifold topological properties and how their respective Pachner graph
grows, particularly using eigenvector centrality and decomposition of their
minimum cycle bases. This included proposal of a conjectural relation
(Conjecture 1) between the growth rate of the Pachner graph and the systole of
a hyperbolic $3$-manifold. Machine learning results showed that through a one-
hot encoding of the IsoSigs that simple neural network architectures could
learn to well distinguish which manifold a triangulations’ IsoSig corresponded
to – a feat very difficult by eye due to the high information density of this
encoding scheme. Gradient saliency analysis then demonstrated that the neural
networks were using the IsoSig characters in a manner which respected the
encoding schemes decomposition into type, destination, and permutation
sequences.

Transformers could not reach the same performance scores as the neural
networks, likely due to the highly unique language-style of this
representation. However, the neural network architectures could generalise
well to differentiating these IsoSig representations of knot complements, and
particularly well manifolds after the operation of Dehn surgery.

At this work’s respective GitHub, code functionality is provided for
generating and visually representing Pachner graphs for generic 3-manifolds;
as well as performing a range of network analysis techniques. Scripts for
repeating the machine learning investigations performed here are also
provided, as well as databases of IsoSigs for the use of interested readers.

Future work would aim to make the connections between Pachner graph network
properties and manifold topological properties more concrete. Further to this,
machine learning methods may be applied directly to the Pachner graphs,
approximating optimal search techniques for problems such as minimising number
of tetrahedra in a representation, or conversely using graph-neural-network
techniques to study them. Additionally the study of more manifolds, and of
triangulations deeper into the Pachner graphs would be interesting to
corroborate results observed here.

## Acknowledgments

F.C. was supported by CIMI Labex ANR 11-LABX-0040 at IMT Toulouse within the
program ANR-11-IDEX-0002-02. YHH would like to thank STFC for grant
ST/J00037X/2 and a Leverhulme project grant. E. Heyes would like to thank
SMCSE at City, University of London for the PhD studentship, as well as the
Jersey Government for a postgraduate grant. E. Hirst acknowledges support from
Pierre Andurand over the course of this research. This research utilised Queen
Mary’s Apocrita HPC facility [61], supported by QMUL Research-IT.

## References

  * [1] W. P. Thurston, “Three-dimensional manifolds, Kleinian groups and hyperbolic geometry,” Bulletin of the American Mathematical Society 6 no. 3, (1982) 357–381.
  * [2] G. Perelman, “The Entropy formula for the Ricci flow and its geometric applications,” arXiv:math/0211159.
  * [3] G. Perelman, “Ricci flow with surgery on three-manifolds,” arXiv:math/0303109.
  * [4] E. Witten, “Quantum Field Theory and the Jones Polynomial,” Commun. Math. Phys. 121 (1989) 351–399.
  * [5] C. N. Yang, M.-L. Ge, and Y.-H. He, eds., Topology and Physics.  World Scientific, March, 2019.
  * [6] A. J. Zomorodian, Topology for Computing.  Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2005.
  * [7] C. R. Brodie, A. Constantin, R. Deen, and A. Lukas, “Machine Learning Line Bundle Cohomology,” Fortsch. Phys. 68 no. 1, (2020) 1900087, arXiv:1906.08730 [hep-th].
  * [8] M. R. Douglas, S. Lakshminarasimhan, and Y. Qi, “Numerical Calabi-Yau metrics from holomorphic networks,” arXiv:2012.04797 [hep-th].
  * [9] S. Krippendorf and M. Spannowsky, “A duality connecting neural network and cosmological dynamics,” Mach. Learn. Sci. Tech. 3 no. 3, (2022) 035011, arXiv:2202.11104 [gr-qc].
  * [10] B. Aslan, D. Platt, and D. Sheard, “Group invariant machine learning by fundamental domain projections,” in NeurIPS Workshop on Symmetry and Geometry in Neural Representations, pp. 181–218, PMLR.  2023\.
  * [11] D. S. Berman, M. S. Klinger, and A. G. Stapleton, “Bayesian renormalization,” Mach. Learn. Sci. Tech. 4 no. 4, (2023) 045011, arXiv:2305.10491 [hep-th].
  * [12] J. Halverson and F. Ruehle, “Metric Flows with Neural Networks,” arXiv:2310.19870 [hep-th].
  * [13] R. Alawadhi, D. Angella, A. Leonardo, and T. S. Gherardini, “Constructing and Machine Learning Calabi-Yau Five-Folds,” Fortsch. Phys. 72 no. 2, (2024) 2300262, arXiv:2310.15966 [hep-th].
  * [14] G. Butbaia, D. Mayorga Peña, J. Tan, P. Berglund, T. Hübsch, V. Jejjala, and C. Mishra, “Physical Yukawa Couplings in Heterotic String Compactifications,” arXiv:2401.15078 [hep-th].
  * [15] Y.-H. He, E. Hirst, and T. Peterken, “Machine-learning dessins d’enfants: explorations via modular and Seiberg–Witten curves,” J. Phys. A 54 no. 7, (2021) 075401, arXiv:2004.05218 [hep-th].
  * [16] J. Bao, S. Franco, Y.-H. He, E. Hirst, G. Musiker, and Y. Xiao, “Quiver Mutations, Seiberg Duality and Machine Learning,” Phys. Rev. D 102 no. 8, (2020) 086013, arXiv:2006.10783 [hep-th].
  * [17] J. Bao, Y.-H. He, E. Hirst, J. Hofscheier, A. Kasprzyk, and S. Majumder, “Hilbert series, machine learning, and applications to physics,” Phys. Lett. B 827 (2022) 136966, arXiv:2103.13436 [hep-th].
  * [18] J. Bao, Y.-H. He, and E. Hirst, “Neurons on Amoebae,” J. Symb. Comput. 116 (2022) 1–38, arXiv:2106.03695 [math.AG].
  * [19] J. Bao, Y.-H. He, E. Hirst, J. Hofscheier, A. Kasprzyk, and S. Majumder, “Polytopes and Machine Learning,” Math. Sci. 01 (2023) 181–211, arXiv:2109.09602 [math.CO].
  * [20] D. S. Berman, Y.-H. He, and E. Hirst, “Machine learning Calabi-Yau hypersurfaces,” Phys. Rev. D 105 no. 6, (2022) 066002, arXiv:2112.06350 [hep-th].
  * [21] G. Arias-Tamargo, Y.-H. He, E. Heyes, E. Hirst, and D. Rodriguez-Gomez, “Brain webs for brane webs,” Phys. Lett. B 833 (2022) 137376, arXiv:2202.05845 [hep-th].
  * [22] P.-P. Dechant, Y.-H. He, E. Heyes, and E. Hirst, “Cluster Algebras: Network Science and Machine Learning,” J. Comput. Algebra 8 (2023) , arXiv:2203.13847 [math.CO].
  * [23] D. Aggarwal, Y.-H. He, E. Heyes, E. Hirst, H. N. S. Earp, and T. S. R. Silva, “Machine learning Sasakian and G2 topology on contact Calabi-Yau 7-manifolds,” Phys. Lett. B 850 (2024) 138517, arXiv:2310.03064 [math.DG].
  * [24] Y.-H. He, V. Jejjala, C. Mishra, and M. Sharnoff, “Learning to be Simple,” arXiv:2312.05299 [cs.LG].
  * [25] E. Hirst and T. S. Gherardini, “Calabi-Yau four-, five-, sixfolds as $\mathbb{P}_{w}^{n}$ hypersurfaces: Machine learning, approximation, and generation,” Phys. Rev. D 109 no. 10, (2024) 106006, arXiv:2311.17146 [hep-th].
  * [26] R.-K. Seong, “Unsupervised machine learning techniques for exploring tropical coamoeba, brane tilings and Seiberg duality,” Phys. Rev. D 108 no. 10, (2023) 106009, arXiv:2309.05702 [hep-th].
  * [27] E. Choi and R.-K. Seong, “Machine learning regularization for the minimum volume formula of toric Calabi-Yau 3-folds,” Phys. Rev. D 109 no. 4, (2024) 046015, arXiv:2310.19276 [hep-th].
  * [28] S. Chen, P.-P. Dechant, Y.-H. He, E. Heyes, E. Hirst, and D. Riabchenko, “Machine Learning Clifford Invariants of ADE Coxeter Elements,” Adv. Appl. Clifford Algebras 34 no. 3, (2024) 20, arXiv:2310.00041 [cs.LG].
  * [29] J. Halverson, B. Nelson, and F. Ruehle, “Branes with Brains: Exploring String Vacua with Deep Reinforcement Learning,” JHEP 06 (2019) 003, arXiv:1903.11616 [hep-th].
  * [30] S. Abel, A. Constantin, T. R. Harvey, and A. Lukas, “Evolving Heterotic Gauge Backgrounds: Genetic Algorithms versus Reinforcement Learning,” Fortsch. Phys. 70 no. 5, (2022) 2200034, arXiv:2110.14029 [hep-th].
  * [31] A. Cole, S. Krippendorf, A. Schachner, and G. Shiu, “Probing the Structure of String Theory Vacua with Genetic Algorithms and Reinforcement Learning,” in 35th Conference on Neural Information Processing Systems.  11, 2021.  arXiv:2111.11466 [hep-th].
  * [32] V. Niarchos, C. Papageorgakis, P. Richmond, A. G. Stapleton, and M. Woolley, “Bootstrability in line-defect CFTs with improved truncation methods,” Phys. Rev. D 108 no. 10, (2023) 105027, arXiv:2306.15730 [hep-th].
  * [33] P. Berglund, Y.-H. He, E. Heyes, E. Hirst, V. Jejjala, and A. Lukas, “New Calabi–Yau manifolds from genetic algorithms,” Phys. Lett. B 850 (2024) 138504, arXiv:2306.06159 [hep-th].
  * [34] S. Gukov, J. Halverson, and F. Ruehle, “Rigor with Machine Learning from Field Theory to the Poincaré Conjecture,” arXiv:2402.13321 [hep-th].
  * [35] M. C. Hughes, “A neural network approach to predicting and computing knot invariants,” 2016.
  * [36] V. Jejjala, A. Kar, and O. Parrikar, “Deep Learning the Hyperbolic Volume of a Knot,” Phys. Lett. B 799 (2019) 135033, arXiv:1902.05547 [hep-th].
  * [37] S. Gukov, J. Halverson, F. Ruehle, and P. Sułkowski, “Learning to Unknot,” Mach. Learn. Sci. Tech. 2 no. 2, (2021) 025035, arXiv:2010.16263 [math.GT].
  * [38] J. Craven, V. Jejjala, and A. Kar, “Disentangling a deep learned volume formula,” JHEP 06 (2021) 040, arXiv:2012.03955 [hep-th].
  * [39] J. Craven, M. Hughes, V. Jejjala, and A. Kar, “Learning knot invariants across dimensions,” SciPost Phys. 14 no. 2, (2023) 021, arXiv:2112.00016 [hep-th].
  * [40] A. Davies, P. Veličković, L. Buesing, S. Blackwell, D. Zheng, N. Tomašev, R. Tanburn, P. Battaglia, C. Blundell, A. Juhász, M. Lackenby, G. Williamson, D. Hassabis, and P. Kohli, “Advancing mathematics by guiding human intuition with ai,” Nature 600 no. 7887, (12, 2021) 70–74.
  * [41] S. Gukov, J. Halverson, C. Manolescu, and F. Ruehle, “Searching for ribbons with machine learning,” 2023.
  * [42] P. Putrov and S. J. Ri, “Graph neural networks and 3-dimensional topology,” 2023\.
  * [43] Casler, “An embedding theorem for connected 3 –manifolds with boundary,” Proc. Amer. Math. Soc. no. 16, (1965) 559–566.
  * [44] B. A. Burton, “Structures of small closed non-orientable 3-manifold triangulations,” Journal of Knot Theory and Its Ramifications 16 no. 05, (May, 2007) 545–574.
  * [45] W. Lickorish, “Simplicial moves on complexes and manifolds,” Geometry & Topology Monographs Volume 2: Proceedings of the Kirbyfest (1999) 299–320.
  * [46] M. Culler, N. M. Dunfield, M. Goerner, and J. R. Weeks, “SnapPy, a computer program for studying the geometry and topology of $3$-manifolds.” Available at http://snappy.computop.org.
  * [47] B. A. Burton, R. Budney, W. Pettersson, et al., “Regina: Software for low-dimensional topology.” HTTP://REGINA-NORMAL.GITHUB.IO/, 1999–2021.
  * [48] B. A. Burton, “The Pachner graph and the simplification of 3-sphere triangulations,” in Proceedings of the 27th annual ACM symposium on Computational geometry - SoCG '11.  ACM Press, 2011.
  * [49] A. A. Hagberg, D. A. Schult, and P. Swart, “Exploring network structure, dynamics, and function using networkx,”  2008\.
  * [50] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, “Scikit-learn: Machine learning in Python,” Journal of Machine Learning Research 12 (2011) 2825–2830.
  * [51] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng, “TensorFlow: Large-scale machine learning on heterogeneous systems,” 2015.  https://www.tensorflow.org/. Software available from tensorflow.org.
  * [52] S. Matveev, “Transformations of special spines and the Zeeman conjecture,” Math. USSR Izvestia 31 (1988) 423–434.
  * [53] R. Piergallini, “Standard moves for standard polyhedra and spines,” Rend. Circ. Mat. Palermo 37 no. 19, (1988) 391–414.
  * [54] M. Lackenby, “Algorithms in $3$-manifold theory,” (2020) 44, arXiv:2002.02179.
  * [55] S. Matveev, Algorithmic topology and classification of 3-manifolds.  No. 9 in Algorithms and computation in mathematics. Springer, 2003.
  * [56] G. Kuperberg, “Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization,” Pacific Journal of Mathematics 301 no. 1, (Sep, 2019) 189–241.
  * [57] P.Scott and H. Short, “The homeomorphism problem for closed $3$-manifolds,” Algebr.Geom. Topol. 14 no. 4, (2014) 2431–2444.
  * [58] H. Rubinstein, “An algorithm to recognize the three sphere,” in Proceedings of the International Congress of Mathematicians (Zurich 1994), pp. 601–611.  Birkhäuser, 1995.
  * [59] A. Mijatović, “Simplifying triangulations of $S^{3}$,” Pacific J. Math. 208 no. 2, (2003) 291–324.
  * [60] D. Chicco and G. Jurman, “The advantages of the matthews correlation coefficient (mcc) over f1 score and accuracy in binary classification evaluation,” BMC Genomics 21 no. 1, (Jan, 2020) 6.
  * [61] T. King, S. Butcher, and L. Zalewski, Apocrita - High Performance Computing Cluster for Queen Mary University of London, Mar., 2017.  https://doi.org/10.5281/zenodo.438045.
  * [62] P. W. Holland and S. Leinhardt, “Transitivity in structural models of small groups,” Comparative Group Studies 2 no. 2, (1971) 107–124.
  * [63] D. J. Watts and S. Strogatz, “Collective dynamics of ’small-world’ networks,” Nature 393 no. 6684, (June, 1998) 440–442.
  * [64] H. Wiener, “Structural determination of paraffin boiling points,” Journal of the American Chemical Society 69 no. 1, (1947) 17–20.
  * [65] O. Perron, “Zur theorie der matrices,” Mathematische Annalen 64 no. 2, (1907) 248–263.
  * [66] G. Frobenius, “Ueber matrizen aus nicht negativen elementen,” Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften (May, 1912) 456–477.
  * [67] P. Bonacich, “Power and centrality: A family of measures,” American Journal of Sociology 92 no. 5, (1987) 1170–1182. http://www.jstor.org/stable/2780000.
  * [68] C. Liebchen and R. Rizzi, “Classes of cycle bases,” Discrete Applied Mathematics 155 no. 3, (2007) 337–355.
  * [69] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” 2023.
  * [70] OpenAI, “Gpt-4 technical report,” 2023.
  * [71] M. R. Douglas, “Large Language Models,” arXiv:2307.05782 [cs.CL].
  * [72] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” 2019.
  * [73] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shleifer, P. von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. L. Scao, S. Gugger, M. Drame, Q. Lhoest, and A. M. Rush, “Transformers: State-of-the-art natural language processing,” in Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 38–45.  Association for Computational Linguistics, Online, Oct., 2020.  https://www.aclweb.org/anthology/2020.emnlp-demos.6.
  * [74] C. M. Gordon and J. Luecke, “Knots are determined by their complements,” Bulletin (New Series) of the American Mathematical Society 20 no. 1, (1989) 83 – 87.
  * [75] M. Dehn, “Die Gruppe der Abbildungsklassen: Das arithmetische Feld auf Flächen,” Acta Mathematica 69 no. none, (1938) 135 – 206. https://doi.org/10.1007/BF02547712.
  * [76] B. A. Burton, “Simplification paths in the pachner graphs of closed orientable 3-manifold triangulations,” 2011.
  * [77] ANSI, “ISO-IR-6: ASCII Graphic character set,” Dec, 1975.  PDF. ITSCJ/IPSJ.

##  Appendix A IsoSig Encoding

Isomorphism Signatures, or IsoSigs, as introduced in [76], are a way of
representing 3-manifold triangulations. In addition to uniquely representing
each isomorphism class, they are both low memory and fast to
compute/check/search.

The algorithm to produce an IsoSig for a given 3-manifold triangulation with
$N$ tetrahedra starts with the generation of canonical labellings. Before
defining a canonical labelling we will first define a labelling, which is
generated as follows:

  1. 1.

Arbitrarily label the tetrahedra from 0 to $N-1$.

  2. 2.

Arbitrarily label each tetrahedra’s four vertices from 0 to 3. Respectively
the face opposite each vertex $i$ is given the same label $i$.

  3. 3.

Using the notation $A_{t,f}$ to equal the label of the tetrahedra glued to
face $f$ on tetrahedra $t$ (such that $A_{t,f}\in\\{0,...,N-1\\}$); list the
gluings as:
$(A_{0,0},A_{0,1},A_{0,2},A_{0,3},A_{1,0},...A_{N-1,3})$ to define the
labelling.

The are many possible labellings that uniquely define a triangulation, we
first reduce this set to only consider canonical labellings, which are defined
as labellings with the properties:

  * •

Tetrahedron $t$ first appears in the labelling before tetrahedron $t^{\prime}$
iff $t<t^{\prime}$, for $t,t^{\prime}\geq 1$ since 0 is implicitly first.

  * •

Where tetrahedron $t$ first appears in the list at position
$A_{t^{\prime},f^{\prime}}$, the labelling of tetrahedra $t$’s vertices
matches the labelling of tetrahedra $(t^{\prime})$’s – i.e. each of the three
vertices in face $f^{\prime}$ of tetrahedra $t$ has the same vertex labelling
as the vertex it is glued too in tetrahedra $t^{\prime}$, the remaining fourth
vertex labelling is then inferred from these three.

For any triangulation, a canonical labelling can be directly generated by
first selecting any of the $N$ tetrahedra as the $0$th tetrahedron; then
arbitrarily labelling its vertices (of which there’re $4!=24$ ways). From this
choice the remainder of the canonical labelling can be inferred by following
the gluings list – each time a new tetrahedron is introduced label it as the
next one in the list and label its vertices using the identity map such that
its vertex labels match the current tetrahedron in accordance with the
canonical labelling definition above. Through this labelling process, it can
be seen that there’re $24N$ canonical labellings for any triangulation [76].

This process of allocating a canonical labelling is clearly still redundant.
To resolve this many-to-one map from labellings to triangulations, all
canonical labellings are computed, encoded as IsoSigs, then the
lexicographically smallest encoding is selected to represent the
triangulation. How the labellings are encoded is what gives the IsoSigs their
character-based / language-like representation, as well as being significantly
more efficient.

A first step in improving the encoding efficiency is using an alphabet, and
when the number of tetrahedra $N$ is large this becomes particularly
effective. The alphabet131313To encode larger numbers
$d=\lfloor\text{log}_{64}(N)\rfloor+1$ characters can be used by just
converting all numbers to base 64, fixing $d$ characters for all encoded
integers, and using padding when necessary. To exemplify, for $N=80$, then
$d=2$ characters are needed, and the number $12$ would be written as $(12,0)$
in the $(64^{0},64^{1})$ basis, such that the encoding would be ma.
implemented is in base 64, such that:

Integer | 0 | $\cdots$ | 25 | 26 | $\cdots$ | 51 | 52 | $\cdots$ | 61 | 62 | 63
---|---|---|---|---|---|---|---|---|---|---|---
Character | a | $\cdots$ | z | A | $\cdots$ | Z | 0 | $\cdots$ | 9 | + | -

Redundant information in the gluings list can also be omitted. In this
process, the gluings list through the triangulation faces $A_{t,f}$ is re-
encoded into three parts: (i) destination sequence, (ii) type sequence, (iii)
permutation sequence. Next we describe each of these part individually:

  1. (i)

Destination Sequence: Since each face gluing involves two faces, the gluings
list for each face naturally includes the information about each gluing twice.
Therefore, from the gluings list $(A_{0,0},A_{1,0},...,A_{N-1,3})$, each time
a face $A_{t,f}$ is glued to another face $A_{t^{\prime},f^{\prime}}$ which
has already been listed (i.e. $t^{\prime}<t$, or $t^{\prime}=t$ and
$f^{\prime}<f$), the entry $A_{t,f}$ is omitted from the gluings list. In
addition for more general triangulations with boundary, a character $\partial$
may be used instead of the tetrahedron number for $A_{t,f}$ to evaluate to,
when the face $f$ is a boundary of the triangulation. The destination sequence
is then a list of all the unique gluings (and boundaries).

  2. (ii)

Type Sequence: Each term in the destination sequence is then classified as one
of three types. Either type 0 $\rightarrow$ the face is a boundary
($A_{t,f}=\partial$); type 1 $\rightarrow$ the face is glued to a new
tetrahedron; or type 2 $\rightarrow$ the face is glued to a previously seen
tetrahedron. The type sequence is then a list of the numbers 0, 1, or 2 for
each term in the destination sequence.

  3. (iii)

Permutation Sequence: For each non-boundary face, the gluing information is
described by a permutation of the vertices from the face in the first
tetrahedron to the face in the second (each of the three vertices in the face
are appropriately paired, and the remaining fourth vertex in each case can
then be inferred). Indexing all the 24 possible permutations $p_{t,f}\in
S_{4}$ from $0$ up to $23$ (i.e.
$(0,1,2,3)\vcentcolon=0,(0,1,3,2)\vcentcolon=1$, etc.), the permutation
sequence is then a number for each non-boundary term in the destination
sequence.

The full IsoSig is then a further reduction of this information. The map
$\pi(\cdot)$ takes any integer into its alphabet encoding; if $N<63$ the
IsoSig starts with $\pi(N)$; when $N\geq 63$, the sequence starts141414Since
63 is the highest number which can be encoded if the sequence starts $\pi(63)$
it is considered as ‘63 or above’, then the next character is taken to be
$\pi(d)$ followed by the full $\pi(N)$ (which may be 63 again). with
$\pi(63)\pi(d)\varepsilon(N)$, where $\varepsilon(\cdot)$ encodes each of the
digits of $N$ written modulo $64$ (so when $N<64$ the $d=1$ encoding is
implicit).

Next the type sequence is encoded and listed, collecting three consecutive
terms into each printable character via
$\pi(\tau_{i}+4\tau_{i+1}+16\tau_{i+2})$ (since each integer
$\tau\in\\{0,1,2\\}$), padding the end with zeros if necessary. Then the
destination sequence is encoded and listed via $\pi(A_{t,f})$, but only for
the type 2 faces (since type 0 are boundary, and type 1 can be deduced as the
next tetrahedra label since the labelling is canonical). Finally, the
permutation sequence is encoded and listed, but again only for the type 2
faces (since the type 0 faces have no gluing, and the type 1 faces are
implicitly the identity permutations since the labelling is canonical).

This produces the encoding of the canonical labelling, however as previously
mentioned there are $24N$ of these. To uniquely specify the IsoSig, each of
these encoded canonical labellings is computed, and the lexicographically
smallest is selected as the IsoSig. The lexicographical ordering used is the
ASCII computational standard [77].

##### Example: Triangular Bipyramid

As a simple example let us consider the triangular bipyramid, as depicted in
Figure 15. This has two tetrahedra, which is far less than 63, so the encoding
begins with c$=\pi(2)$ (the $d=1$ is implicit).

Arbitrarily starting with the top tetrahedron as our tetrahedron 0, let us
choose the vertex labelling such that the single glued face has vertices 0, 1,
and 2; with the remaining vertex labelled 3 (which matches the labelling of
the glued face as it is opposite). The gluings list then reads
$A_{0,0}=\partial$, $A_{0,1}=\partial$, $A_{0,2}=\partial$, $A_{0,3}=1$, now
this is the first occurrence of this new tetrahedron (bottom) and hence sets
its tetrahedron label to the next integer which is 1; furthermore the
canonical nature of the labelling sets the vertex labellings for this second
tetrahedron, each vertex on the glued face in tetrahedron 0 is glued to a
vertex of the same labelling in tetrahedron 1. The gluings list hence
continues $A_{1,0}=\partial$, $A_{1,1}=\partial$, $A_{1,2}=\partial$,
$A_{1,3}=0$. The overall gluings list is then:
$(\partial,\partial,\partial,1,\partial,\partial,\partial,0)$.

Figure 15: The triangular bipyramid, an example 3-manifold triangulation,
where the coloured edges indicate the glued face.

This reduces to the destination sequence:
$(\partial,\partial,\partial,1,\partial,\partial,\partial)$, removing the
repetition of the initial tetrahedron at the end of the gluings list. The type
sequence is then defined as: $(0,0,0,1,0,0,0)$ over the destination sequence,
i.e. there are no non-trivial gluings (type 2’s). Finally the permutation
sequence is computed, which is only defined for non-boundary terms in the
destination sequence: $(0)$.

These sequences are then encoded and combined, after the initial c, the type
sequence is then split into threes and padded as $((0,0,0),(1,0,0),(0,0,0))$,
becoming $\pi(0+4\times 0+16\times 0)=\pi(0)=$ a, $\pi(1+4\times 0+16\times
0)=\pi(1)=$ b, $\pi(0+4\times 0+16\times 0)=\pi(0)=$ a, which together is aba.
Following this, since there are no type 2 faces, the destination and
permutation sequences are trivially empty, and this defines the full encoded
canonical labelling as caba, which to check is canonical we would have to
consider all $24\times 2=48$ canonical labellings and choose the
lexicographically smallest (which in this case it is!).

##  Appendix B Pachner Graphs

The Pachner graphs generated with moves $\\{2-3,3-2\\}$ up to depths 3 and 4,
for the remaining 8 considered manifolds, starting from triangulations with
IsoSigs specified in Table 1. The nodes represent triangulations and are
labelled with the triangulation’s respective number of tetrahedra, edges
represent Pachner moves which transform the triangulations they connect into
each other.

The smallest closed hyperbolic manifold $H_{SC}$ had too many IsoSigs in its
Pachner graph to plot at even depth 3, therefore the depths 1 and 2 are shown
instead. To exemplify the speed of Pachner graph growth, the depth 5 $S^{3}$
Pachner graph is also given at the end.

$S^{2}\times S^{1}$ Depth 3

$S^{2}\times S^{1}$ Depth 4

$\mathbb{RP}^{3}$ Depth 3

$\mathbb{RP}^{3}$ Depth 4

$L(7,1)$ Depth 3

$L(7,1)$ Depth 4

$L(7,2)$ Depth 3

$L(7,2)$ Depth 4

$T^{3}$ Depth 3

$T^{3}$ Depth 4

PHS Depth 3

PHS Depth 4

$H_{SC}$ Depth 1

$H_{SC}$ Depth 2

$S^{3}$ depth 5