Benjamin Burton — Code

Last updated: 1 December 2011

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

Computational topology (various papers) Fundamental normal surfaces and the enumeration of Hilbert bases 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.sourceforge.net.

Fundamental normal surfaces and the enumeration of Hilbert bases

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 29 November 2011)

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 28 November 2011.

Full Regina data files containing the vertex and fundamental normal surfaces will be posted as soon as possible. These files are very large—2.7 GB in total—and I need to find the best place to host them. Please check again later for updates; in the meantime, you are welcome to mail me and I can arrange a temporary download location for you (1 December 2011).

Computing the crosscap number of a knot using integer programming and normal surfaces

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 (“Fundamental normal surfaces and the enumeration of Hilbert bases”) 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...)