Benjamin Burton — Code

Last updated: 15 Mar 2021

This page contains supporting software and data for a variety of papers:

Computational topology (various papers) Connecting 3-manifold triangulations with semi-monotonic sequences of bistellar flips The cusped hyperbolic census is complete Enumerating fundamental normal surfaces: Algorithms, experiments and invariants Computing closed essential surfaces in knot complements Computing the crosscap number of a knot using integer programming and normal surfaces Locating regions in a sequence under density constraints The Weber-Seifert dodecahedral space is non-Haken

Computational topology (various papers)

Almost all of my computational topology code is included in Regina, a software package for 3-manifold topologists.

You can download Regina from regina-normal.github.io.

Connecting 3-manifold triangulations with semi-monotonic sequences of bistellar flips

This paper (joint with Alexander He) includes exhaustive experimental data on how well-connected 3-manifold triangulations are in the flip graph.

You can download the preliminary source code here; this source code is currently “raw”, and will be tidied up at some future date.

Download monotonic-v0.zip (last updated 15 Mar 2021)

The cusped hyperbolic census is complete

This paper: (i) proves that the cusped hyperbolic census has no false positives, no false negatives and no duplicates; (ii) extends the census to 9 tetrahedra; and (iii) extends the census to include all minimal triangulations (both geometric and non-geometric) of every census manifold.

You can download a zip file containing the full census data here:

Download hypcensus.zip (last updated 12 May 2014)

This zip file contains files 1-or.dat, …, 9-or.dat that list all orientable manifolds by number of tetrahedra, and files 1-nor.dat, …, 9-nor.dat that list all non-orientable manifolds by number of tetrahedra. Each file is a plain text file, with one line per manifold. Each line is of the following form:

m043 3.2529080485 0.2718806311 0.1824397261 Z+Z/5 2 eLAkaccddjnjak eLAkbbcdddhwhk

• The name of the manifold.
  For orientable manifolds with ≤ 8 tetrahedra and non-orientable manifolds with ≤ 7 tetrahedra, this is the “common name” used by SnapPea and SnapPy (such as m002, or t12840). For orientable manifolds with 9 tetrahedra and non-orientable manifolds with ≥ 8 tetrahedra, the name is the form o9_44249 (indicating the 44250th orientable manifold with 9 tetrahedra), or n8_0012 (indicating the 13th non-orientable manifold with 8 tetrahedra). The apparent off-by-one error in indexing is because the first manifold in each list is numbered zero.
• The hyperbolic volume.
• The length of the shortest geodesic.
• The Chern-Simons invariant.
  This is only given for orientable manifolds. For non-orientable manifolds, a dash (–) will appear here instead.
• The first homology group.
• The full list of all minimal triangulations.
  This begins with the number of minimal triangulations (in the example above this is 2), followed by encodings of the triangulations themselves. Each triangulation is encoded as an isomorphism signature, which is a short (and case-sensitive) string of letters that you can feed into Regina to reconstruct the full triangulation.

This paper gives algorithms for enumerating fundamental normal surfaces in a 3-manifold triangulation, and uses these to compute previously-unknown crosscap numbers of knots. You can download a CSV file containing the new crosscap numbers here:

Download fund_results.csv (last updated 1 October 2013)

You should be able to open this file in your favourite spreadsheet application. The columns in this table are:

• name: The name of the knot as used in the KnotInfo database.
• dt_name: The Dowker-Thistlethwaite name of the knot, as retrieved from the KnotInfo database.
• old_cc: The previous range of possible values for the crosscap number of the knot, as retrieved from the KnotInfo database.
• new_cc: The newly-computed (and precise) crosscap number of the knot.
• n: The number of tetrahedra in the knot complement. See the triangulation field below.
• triangulation: The triangulation of the knot complement that was used. This triangulation is presented as an isomorphism signature, which is a short string of (case-sensitive) letters that you can feed into Regina to reconstruct the full triangulation.

The crosscap numbers computed in this paper and the paper below (“Computing the crosscap number of a knot using integer programming and normal surfaces”) cover different knots, and so the two sets of downloads provide different information.

All KnotInfo data were retrieved on 30 September 2013.

Computing closed essential surfaces in knot complements

This paper (joint with Alexander Coward and Stephan Tillmann) includes a significant amount of supporting data for computations on the 2977 non-trivial prime knots with ≤12 crossings, as well as the two 20-crossing dodecahedral knots.

You can download two files with supporting data:

• Download knots-large.rga (data for ≤12-crossing knots, last updated 12 December 2012)
• Download dodecahedral.rga (data for the dodecahedral knots, last updated 12 December 2012)

You can open each of these files in Regina to examine the ideal triangulations of the knot complements, as well as the lists of admissible extreme rays of the corresponding cones Q₀(T). See the paper for details on how these data feature in the tests for whether these knots are large.

For convenience, you can also download the list of all 1019 large knots from the census of non-trivial prime knots with ≤12 crossings (i.e., the list of knots from the table at the end of the paper). This is a plain text file, and the knots within it are listed using their names from the KnotInfo database.

• Download knots-large-results.txt (last updated 12 December 2012)

Finally, you can download the source code that produced this data:

• Download essential-20121215.zip (last updated 15 December 2012)

This paper (joint with Melih Ozlen) gives three algorithms for computing the crosscap number of a knot and/or reducing the number of possible solutions, and uses the final algorithm to improve data in existing knot tables. You can download a CSV file containing this new data here:

• Download crosscap_results_v2.csv (version 2, 15 July 2011):

  This contains stronger results than the original data file (version 1). The improvement: if the optimal solution to the integer program is an orientable surface, instead of just accepting this solution (and outputting the upper bound 2-χ) we non-deterministically keep searching for a non-orientable optimal solution (which improves the upper bound to 1-χ).

• Download crosscap_results_v1.csv (version 1, 12 July 2011):

  This contains the original data as reported in the paper.

You should be able to open this file in your favourite spreadsheet application. Most of the new data are for non-alternating knots, so you may need to scroll down a little way before you see these new results. The columns in this table are:

• name: The name of the knot as used in the KnotInfo database.
• dt_name: The Dowker-Thistlethwaite name of the knot, as retrieved from the KnotInfo database.
• genus: The (orientable) genus of the knot, as retrieved from the KnotInfo database.
• old_cc: The crosscap number of the knot, if this was previously known, as retrieved from the KnotInfo database.
• old_cc_min, old_cc_max: Previous best-known lower and upper bounds on the crosscap number, as retrieved from the KnotInfo database.
• new_cc: The precise crosscap number of the knot, as identified by the new algorithm. If the crosscap number was already known (old_cc) then this field is left empty.
• new_cc_max: An upper bound on the crosscap number of the knot, as identified by the new algorithm. If this is no better than the previous upper bound (old_cc_max) then this field is left empty.
• n: The number of tetrahedra in the knot complement. See the triangulation field below.
• triangulation: A suitable triangulation of the knot complement (see Section 3 of the paper). The triangulation is presented as an isomorphism signature; this is a short string of (case-sensitive) letters that can be fed into Regina to reconstruct the full triangulation.

The crosscap numbers computed in this paper and the paper above (“Enumerating fundamental normal surfaces: Algorithms, experiments and invariants”) cover different knots, and so the two sets of downloads provide different information.

All KnotInfo data were retrieved on 2 June 2011.

You can also download a Regina data file containing full normal coordinates for each spanning surface found by these algorithms. These normal surfaces are, in effect, certificates that allow third parties to verify that the new crosscap numbers and upper bounds reported here are correct.

Download crosscap_data.rga

This data file matches version 2 of the CSV file above, and can be opened using Regina (a software package for 3-manifold topology with rich support for the enumeration and analysis of normal surfaces).

Locating regions in a sequence under density constraints

This paper (joint with Mathias Hiron) describes a number of sequence processing algorithms. You can download C++ implementations of these algorithms here:

Download density.zip

The programs in this archive search through long strings of 0s and 1s for regions of particular interest. They include:

• longest-range.cc, for finding the longest substring with density in a given range [θ₁,θ₂];
• shortest.cc, for finding the shortest substring with density in a given range [θ₁,θ₂];
• maxset.cc, for finding a maximal cardinality set of disjoint substrings whose densities all lie in the given range [θ₁,θ₂];
• longest-precise.cc, for finding the longest substring whose density precisely matches a given value θ.

The archive also includes a file README.txt with instructions for building and using these programs.

All of these programs are offered under the GNU General Public License.

Some of these programs use van Emde Boas trees, the implementation of which is taken from the MIT-licensed libveb by Jani Lahtinen. This is available from code.google.com, but the necessary portions are also included in the archive above.

The Weber-Seifert dodecahedral space is non-Haken

This paper (joint with J. Hyam Rubinstein and Stephan Tillmann) includes a significant amount of supporting data, including the 23-tetrahedron triangulation of the Weber-Seifert dodecahedral space and its 1751 standard vertex normal surfaces.

You can download this data from the Regina website.

(Back to home page...)