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. The Burau and Alexander 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 a braid
  7. Vogel's algorithm for determining a braid word from a knot or link diagram
  8. The HOMFLY polynomial
  9. Turaev's extended bracket polynomial of a knotoid
  10. Sawollek's normalized Conway polynomial for a braid word
  11. The Dynnikov test for the trivial braid
  12. The Dowker(-Thistlethwaite) code for the braid
  13. The Gauss code for a braid word
  14. The labelled peer code for a braid word

The programme is available as a binary image or a source distribution:

Binary image for Fedora 11 Linux together with user documentation: braid-16.0-F11.tar.gz.

Binary image for Windows together with user documentation: braid-16.0.zip.

If you have a different version of UNIX, you are likely to require the source distribution.

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

Note: from 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.

Installation

When you unzip and extract the files from the binary image archive you will create a sub-directory at the current location called braid-16.0 containing the braid programme, a sample input file, the programme help file, and the user documentation in HTML format. With the Linux distribution the directory also contains a programe Qbraid, the Qbraid wizard graphical front end to the braid programme based on the Nokia (origninally Trolltech's) Qt3 C++ GUI toolkit.

When you unzip and extract the files from the source image archive braid-15.0-src.tar.gz you will create a subdirectory called braid-16.0 containing subdirectories prog and Qt. The prog directory contains the source code in subdirectories called src and include, the 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. The Qt directory contains the source files and Qt 3.0 user interface files needed to build the GUI wizard and the QT3 Designer project file so you can modify the GUI more easily if you need to. You need Qt to be installed on your machine to build the wizard from source, the Qt directory also contains a README file that describes what you need to do.

User documentation

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

If you did not get a copy with the programme, you can download one from here.

If you have lost the file helpinfo.txt from your machine, you can get another copy here.

Results obtained with the programme

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

Quaternioniic 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

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.
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 (to appear)

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

back to top   maths homepage