Braid programme

Last updated 28th March, 2016

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. The Alexander and Burau polynomial invariants
  2. Various quaternionic polynomial invariants
  3. Various matrix-switch polynomial invariants
  4. Various Weyl algebra switch polynomial invariants
  5. Various finite-switch polynomial invariants (also known as rack polynomials)
  6. The fixed-point invariant of the braid representation of a knot or doodle
  7. Vogel's algorithm for determining a braid word from a knot or link diagram
  8. The HOMFLY polynomial
  9. The Kauffman bracket polynomial of a classical or virtual link
  10. The Jones polynomial of a classical or virtual link
  11. Turaev's extended bracket polynomial of a knotoid
  12. Kauffman's Affine Index Polynomial for virtual knots
  13. Sawollek's normalized Conway polynomial for a braid word
  14. The Dynnikov test for the trivial braid
  15. The Dowker(-Thistlethwaite) code for the braid
  16. The Gauss code for a braid word
  17. The labelled peer code for a braid word

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

Installation

When you unzip and extract the files from the source image archive braid-18.0-src.tar.gz you will create a subdirectory called braid-18.0 containing a subdirectory prog. 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 and a README file with further details of the source distribution. In the source distribution the prog directory also contains a subdirectory, doc, that 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.

Results obtained with the programme

Some results from the early version of the programme are presented on the braid results page.

Quaternionic switches

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.

Version History

The first released version was 6.1.b1, supporting Burau and quaternion matrix representation, Alexander polynomial, 0th and 1st 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 DeltaiC and DeltaiR 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 Delta1. Previous versions only calculated Delta1 when Delta0 was zero, now Delta1 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 E1 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 Delta1 for non-commutative switches when Delta0 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 Mn(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)

Bug Tracker
  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 Delta1 was calculated even when Delta0 was non-zero. However, in the non-commutative case Delta0 was not included as a generator of Delta1 which meant that when Delta0 was non-zero the value calculated for Delta1 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].
References:

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

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

[3] J. Sawollwk. 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. Biquandles of Small Size and some Invariants of Virtual and Welded Knots Corrigendum (to appear).

back to top   maths homepage