Braid programme

The braid programme was originally written in support of work done with Roger Fenn to calculate matrix representations of virtual braid groups. It has evolved to include tasks that relate to virtual knots, long knots, welded knots and knotoids but that do not involve a braid representation. However, in the absence of anything better, the name 'braid' has been retained for the programme.

The tools provided by the programme support the following:

1. Alexander and Burau polynomial invariant
2. Alexander-like polynomial invariant of a classical doodle
3. Burau, or generalized Alexander, polynomial invariant
4. Commutative automorphism switch invariants
5. Finite-switch polynomial invariants (also known as rack polynomials)
6. Fixed-point invariant of the braid representation of a knot or doodle
7. Matrix-switch polynomial invariants
8. Quaternionic polynomial invariants
9. Sawollek's normalized Conway polynomial for a braid word
10. Weyl algebra switch polynomial invariants


11. Arrow polynomial of a classical or virtual knot, link, long knot, long virtual knot, knotoid or multi-knotoid
12. HOMFLY polynomial
13. Jones polynomial of a classical or virtual knot, link, knotoid or multi-knotoid
14. Kauffman's Affine Index Polynomial for virtual knots or knotoids
15. Kauffman bracket polynomial of a classical or virtual knot, link, knotoid or multi-knotoid
16. Turaev's extended bracket polynomial of a classical or virtual knotoid or multi-knotoid
17. Parity arrow polynomial of a classical or virtual knot or knotoid
18. Parity bracket polynomial of a classical or virtual knot or knotoid
19. Kim and Kim's Q polynomial for doodles with one component ([22])


20. Dynnikov test for the trivial braid
21. Hamiltonian circuits within classical or flat knot or link diagram
22. Vogel's algorithm for determining a braid word from a knot or link diagram
23. Prime test to determine whether a given diagram is prime; i.e is not a connected sum, or has a 3-connected shadow


24. Dowker(-Thistlethwaite) code for a braid or labelled peer code
25. Gauss code for a labelled peer code or the closure of a braid word
26. Labelled immersion code for a braid word
27. Labelled peer code for
    • braid word of a classical or virtual knot or link
    • labelled immersion code of a classical or virtual knot or link
    • Gauss code of a classical, virtual or flat link, knotoid, multi-knotoid or multi-linkoid
    • Labelled peer code for the planar diagram description (PD code) of a classical or virtual link
    • the n-parallel cable satellite of a knot's peer code

The source code is available, together with user documentation and some additional developers notes here: braid-28.0-src.tar.

When you unzip and extract the files from the source image archive braid-28.0-src.tar you will create a subdirectory called braid-28.0 containing subdirectories doc and prog and a README file with further details of the source distribution. The prog directory contains the source code in subdirectories called src and include, a sample input file and the programme help, and also a Makefile . The doc directory contains the user documentation in HTML format and some software developer's notes.

User documentation

Here is a link to the latest on-line version of the user documentation.

The braid programme is able to calculate quaternionic polynomial invariants as described in [1]. The source code used to search for the quaternionic switches used for these invariants is presented on the quaternionic switches page.

The first released version was 6.1.b1, supporting Burau and quaternion matrix representation, Alexander polynomial, 0^th and 1^st ideal polynomials for quaternionic representations, Dynnikov test and Dowker code calculation.

Version 7.0 (not released via the web) introduced calculation of Sawollek's normalized Conway polynomial.

Version 8.0 added the Vogel algorithm for evaluating braid words from Gauss codes, the ability to include programme options in input files, the writing of an output file in "input" format, and support of the alphabetical notation for classical braids.

Version 9.0 added the Gauss code and labelled immersion code calculations. It added the calculation of Delta_i^C and Delta_i^R as further options to the quaternionic representations. Version 9 changed the meaning of two programme options (see below), and aligned the terminology used for the Burau and Alexander representations to that in [1]. This meant that what had previously been referred to as the Burau representation was henceforth referred to as the Alexander representation and vice versa. The term Alexander polynomial was retained for Delta_1 of the Burau representation according to common practise.

The option changes introduced in version 9 are as follows:

    option               old meaning        new meaning           new option 
                                                                for old meaning 
      c                  dowker code     calculate Delta_1^C          d
      i                 input as output    imersion code              I

Version 9.0 also extended the Vogel algorithm to handle labelled immersion code descriptions of virtual knots. This corrected an error that was found in the version 8.0 implementation of the Vogel algorithm.

Version 10 was a major update to the structure of the code, making it much more object oriented. This was partly motivated by the requirement to add support for matrix switch invariants but was also long overdue from a coding standpoint. Version 10 introduced use of the fundamental equation ([5]) to calculate C and D from A and B when evaluating switch matrices. This version also included support of a simple web interface to the programme.

Version 11 added support for Weyl algebra switches, calaulation mod p for all switches, control over the use of the variable t, and changed the default behaviour for calculating Delta₁. Previous versions only calculated Delta₁ when Delta₀ was zero, now Delta₁ is always calculated, unless the user specifies otherwise. Version 11 was also supplied with a much more feature rich web interface that allowed access to most of the common command line options.

Version 11.1 tidied up the internal structure of the code and made several behind-the-scenes changes, but did not alter the functionality from Version 11.0.

Version 11.2 added an option for the programme to report explicitly whether polynomial invariant switch elements satisfy A=D and B=C. It also corrected an error in the HTML used for the web interface that caused a problem with some browsers.

Version 12.0 introduced support for long knots, termination of further calculation of E₁ generators if a unit is encountered, and added various improvements to the web interface for the programme. It also corrected an error in the calculation of Delta₁ for non-commutative switches when Delta₀ was non-zero (see the bug tracker below).

In version 12.0, one of the source code header files was renamed from Quaternion.h to quaternion-scalar.h. This was done to avoid a conflict with another header file quaternion.h experienced in some operating systems, such as Windows and MAC OS X.

In version 12.0, the matrix representation produced from a labelled immersion code was changed so that the switch action at a real crossing was more natural, whilst not affecting the results.

In version 12.0, the option for mapping quaternionic matrix representations into M_n(R[t,t^-1]) was removed, since it proved to be of no theoretical value.

Version 12.1 was a maintenance release, see the bug tracker below.

Version 12.2 added automatic handling of the concatenation product for long knots via the # syntax in an input file.

Version 12.3 was a maintenance release: it corrected an error in processing an unusual input polynomial case (see the bug tracker below) and added some additional error checking on input strings.

Version 13.0 added support for the HOMFLY polynomial and introduced the Qbraid graphical front end to the programme. It also changed the CLI syntax if the programme is run from the command line.

Version 14.0 added support for the fixed-point invariant and finite-switch polynomial invariants.

Version 15.0 added the bracket polynomial for knotoids and extended the dowker code tool to accommodate labelled immersion codes as input.

Version 16.0 added support of labelled peer codes and the silent option for batch processing. The Vogel algorithm was updated to support labelled peer codes and had support for Gauss codes and labelled immersion codes removed. This reflected the cleaner structure of the January 2011 update to the Vogel algorithm.

Version 16.0 removed support for the (erroneous) Nicholson polynomial.

Version 16.1 and 16.2 (September 2011 and November 2012 respectively) added the flip-braid option and "flip" braid qualifier that renumbers the strands of a braid in the opposite order (equivalent to turning over a braid in R^3) before calculating fixed point invariants.

Version 17.0 (January 2013)added the Kauffman bracket and Jones Polynomial to the function bracket_polynomial, it also added support for Gauss codes when calculating these two polynomials, which entailed creating a modified form of the generic code data structure for Gauss codes to allow for the fact that Gauss codes describe only classical crossings and not virtual crossings. Version 17.0 also introduced support for the affine index polynomial invariant for virtual knots. A tool for converting labelled peer codes or immersion codes was added to allow testing of the affine index polynomial.

Version 18.0 (January 2015) introduced the fixed point invariant for virtual doodles and aligned the code for fixed-point invariants from [11] to [12].

Version 18.1: Added invert-braid, line-reflect-braid and plane-reflect-braid options and {invert, line-reflect, plane-reflect} braid qualifiers (March 2015)

Version 19.0 (March 2017) added satellite knot calculation for r-parallel cables of knots.

Version 19.1 (July 2017) modified write_gauss_code and read_gauss_code to handle doodle Gauss codes.

Version 20.0 (February 2018) added support for commutative automorphism switches.

Version 20.1 (April 2018) added Kamada double covering calculation for braids.

Version 21.0 (November 2019) added support for links and multi-knotoids in bracket_polynomial, added gauss code to peer code conversion for classical links.

Version 21.1 (April 2020) modified the bracket polynomial so that the kauffman-bracket and jones-polynomial options evaluated the normalized bracket polynomial and Jones polynomial for knotoids and multi-knotoids as well as knots and links. The knotoid-bracket option calculates Turaev's extended bracket polynomial for knotoids and multi-knotoids as before. Added TeX output format option for bracket polynomials

Version 22.0 (May 2020) added support for the arrow polynomial for classical and virtual knots, links, knotoids and multi-knotoids, added no-expand-bracket and no-normalize-bracket options, added support for "An Alexander type invariant for doodles", added mapped polynomials for improved arrow polynomial presentation and to prepare for the parity bracket polynomial, added support for knotoids to affine_index_polynomial, added support for knotoids to the Gauss code task, added the lpgd and ulpgd options to the Gauss code task, added the parity bracket polynomial and the parity arrow polynomial for classical or virtual knots or knotoids.

Version 23.0 (November 2021)) Updated the syntax for knot-type knotoids and long knots to be "K:" and "L:", extended the ability to convert Gauss codes of virtual knots and links to labelled peer codes based on Jeremy Green's algorithm for drawing virtual knots from Gauss codes, added support for reading Gauss codes of the form sequence{(O|U), e.g. O1-O2+U1-O3+O4+U2+U3+U4+

Version 24.0 (December 2021) Added the opgc and uopgc options to the Gauss code task, added OU format for Gauss code output. Added support for knotoids and long-knots to be specified via Gauss codes using the "K:" and "L:" syntax.

Version 25.0 (March 2022) Added planar diagram support as an alternative input format, added support for Gauss code and planar diagram input to the knotoid bracket, parity bracket and parity arrow polynomial tasks.

Version 25.1 (September 2022) Updated the handling of input files containing switches specifying the t-variable. Updated the behaviour of "satellite" to make it an option rather than a task, this allowed the cabling of entries in an input file prior to carrying out the specified task. Corrected an error in the Vogel algorithm, see bug tracker below. Documented the use of the Burau representation for calculating the Generalized Alexander polynomial. Updated the sawollek implementation of matrix P to be more clearly aligned with Sawollek's paper. Added draft mock Alexander option for knotoids. Added the ability to read Dowker-Thistlethwaite codes for prime knots and convert them to labelled peer codes.

Version 25.2 (April 2023) Added support for multi-linkoids to the peer code and Gauss code input and output functions and modified gauss_to_peer_code to convert multi-knotoid Gauss codes to peer codes.

Version 26.0 (October 2023) Added Hamiltonian task to find Hamiltonian circuits in a diagram of a classical or flat knot or link. Removed the start menu.

Version 27.0 (October 2023) Added prime task to test whether (the shadow of) a diagram is prime; i.e 3-connected. Cleaned up handling of multi-linkoids.

Version 28.0 (October 2024) Added turning number calculation, changed RACK_POLYNOMIAL task to accept peer codes in addition to braid words. Cleaned up the validation of braid input and harmonized the checking of braid qualifiers across the various tasks that use them. Implemented Kim and Kim's Q-polynomial invariant for single component doodles

1. The braid word algebra of assignment statements and braid statements did not work in version 6.1.b1, since they were confused with switch definitions in the code(!). This was corrected in version 8.0
2. In version 8.0 the degrees of variables in quotient polynomials with two or more variables was calculated incorrectly. This bug caused the programme to hang in an infinite loop. It was corrected in version 9.0
3. In version 8.0 the function that sets s=1 when evaluating Alexander polynomials was called without first checking that there were indeed variables present in the polynomial. This bug caused a segmentation fault, it was corrected in version 9.0.
4. In version 8.0 the implementation of the Vogel algorithm for virtual braids was found to have a theoretical bug that invalidated the braid words produced in some cases. This was corrected in version 9.0.
5. Version 10 added support for matrix switch representations but the R_module representation for immersion codes set an internal variable incorrectly that made the Delta_1 calculation cause a segmentation fault. This was corrected in version 11.1.
6. In version 11.0 the bigint right-shift operator left redundant leading zeros in the bigint representation that caused the bigint division operator to generate a floating point exception. This was corrected in version 11.1.
7. In version 11.0 the rational<bigint> scalar variant absolute value member function returned the value, not the absolute value(!). This was corrected in version 11.1.
8. In version 11.0 the quaternion class abs() function returned it's argument unchanged so that the polynomial output operator worked properly, which meant that the abs function was mathematically incorrect (it should return the quaternion's modulus). Therefore in 11.1 the abs() function was removed for the quaternion class, since the modulus function is not required, and the polynomial output operator rewritten.
9. In version 11.0 the inverse of the quantum Weyl algebra switch matrix was set incorrectly from a formula, rather than being calculated directly, therefore giving incorrect values for the polynomial invariants calculated with the switch. This was corrected in version 11.1.
10. In version 11.0 the HTML used to generate part of the web interface was incorrect: although some browsers tollerated the error, later versions of Firefox do not. This was corrected in version 11.2.
11. In version 11.0 the default behaviour was changed so that Delta₁ was calculated even when Delta₀ was non-zero. However, in the non-commutative case Delta₀ was not included as a generator of Delta₁ which meant that when Delta₀ was non-zero the value calculated for Delta₁ was not always correct. This error was corrected in version 12.0.
12. Version 12.1 corrected a memory leak in the absolute function for scalars, abs(const scalar& c). It also corrected a memory leak in the function used to calculate R-module representations from labelled immersion codes.
13. Reference [6] contains a typographic error in the description of a Weyl algebra over a truncated poynomial ring, interchanging the matrices u and v. The error was included in version 11.0 and corrected in version 12.1.
14. Version 12.1 also corrected an error for the cases n >= 3 in the setting up of the matrix v for the Weyl algebra over the truncated polynomial ring .
15. Version 12.1 corrected an error that displayed polynomial coefficients equal to -1 mod p incorrectly for the case p > 2.
16. Version 12.2 corrected an error in the renumbering of a labelled immersion code for long knots when the point at infinity is moved by an even number of semi-arcs.
17. Version 12.3 corrected an error in the polynomial input routine when the entire polynomial was enclosed in parentheses.
18. Version 18.0 corrected the ambiguity in the code described in [12].
19. Version 25.1 corrected an error in the Vogel algorithm that could have resulted in a segmentation fault by using a negative value rather than an absolute value.

[1] A. Bartholomew and R. Fenn. Quaternionic Invariants of Virtual Knots and Links (J Knot Theory and Its Ramifications Vol. 17 No. 2 (2008) 231-251).

[2] A. Bartholomew. An Application of Vogel's Algorithm to Classical Links and Virtual Knots

[3] J. Sawollek. On Alexander-Conway Polynomials For Virtual Knots and Links

[4] P. Dehornoy. Braids and Self-Distributivity. Progress in Mathematics no 192 Birkha user,(2000)

[5] P. Budden and R. Fenn. The equation [B,(A-1)(A,B)]=0 and Virtual Knots and Links Fund. Math 184 (2004).19 29

[6] R. Fenn and V. Turaev. Weyl Algebras and Knots. J. Geometry and Physics 57 (2007) 1313-1324

[7] A. Bartholomew, R. Fenn, N. Kamada, S. Kamada, New Invariants of Long Virtual Knots, Kobe J. Math 27 (2010) 21-33

[8] L. H. Kauffman. Introduction to Virtual Knot Theory, arXiv:1101.0665v1

[9] V. Turaev. Knotoids, arXiv:1002.4133v4

[10] L. H. Kauffman. An Affine Index Polynomial Invariant of Virtual Knots, arXiv:1211.1601v1

[11] A. Bartholomew and R. Fenn. Biquandles and Welded Knot Invariants of Small Size (arXiv:1001.5127v1).

[12] A. Bartholomew and R. Fenn. Erratum: Biquandles of Small Size and some Invariants of Virtual and Welded Knots (J Knot Theory and Its Ramifications Vol. 26 No. 8 (2017)).

[13] A. Bartholomew, R. Fenn, N. Kamada, S. Kamada, Colorings and Doubled colorings of Virtual Doodles (arXiv:1809:04205).

[14] A. Bartholomew, R. Fenn, N. Kamada, S. Kamada, On Gauss codes of virtual doodles (Journal of Knot Theory and Its Ramifications Vol. 27, No. 11, 1843013 (2018), arXiv:1806.05885 ).

[15] H. A. Dye, L. H. Kauffman, Virtual Crossing Number and the Arrow Polynomial arXiv:0810.3858

[16] N. Gugumcu, L, H. Kauffman, New invariants of knotoids, European Journal of Combinatorics 65 (2017) 186–229

[17] L. H. Kauffman, An Extended Bracket Polynomial for Virtual Knots and Links, arXiv:0712.2546

[18] A. Kaestner, L, H, Kauffman, Parity, Skein Polynomials and Categorification, arXiv:1110.4911v1

[19] B. Cisneros, M. Flores, J. Juyumaya, C.Roque-Márquez, An Alexander type invariant for doodles, arXiv:2005.06290v1

[20] V. O. Manturov. Parity in knot theory. (Russian) Mat. Sb. 201 (2010), no. 5, 65–110; translation in Sb. Math. 201 (2010), no. 5-6, 693733.

[21] A. Kaestner, L. H. Kauffman, Parity, Skein Polynomials and Categorification, arXiv:1110.4911

[22] Kim J. and Kim T-K., Some polynomial invariants of virtual doodles. Journal of Knot Theory and Its Ramifications Vol. 33, No. 04, 2450010 (2024)

back to top   maths homepage