Definitions of Braid Functions

(Text by Juan Gonzalez-Meneses)

Left Normal Form

Computes the left greedy normal form of a braid.

Find details in:
W. P. Thurston, Braid Groups, Chapter 9 of: D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson and W. P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992.

Example: The left normal form of the braid on 4 strands: 1 -3 2, is the following: D^(-1) . 2 1 3 2 1 . 1 2.

In our notation, D is Garside's Delta, the digits represent Artin generators, and the factors in the normal form are separated by dots.

Right Normal Form

Computes the right greedy normal form of a braid.

Find details in:
W. P. Thurston, Braid Groups, Chapter 9 of: D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson and W. P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992.

Example: The right normal form of the braid on 4 strands: 1 -3 2, is the following: 1 2 3 . 1 2 3 2 . D^(-1).

In our notation, D is Garside's Delta, the digits represent Artin generators, and the factors in the normal form are separated by dots.

Permutation

Computes the permutation induced by a braid on its base points. The result is given as a product of cycles.

Example: The permutation induced by the braid on 6 strands: 1 2 -4, is the following: (132)(45).

Conjugacy Test

Determines whether two given braids are conjugate, and in that case, it computes a conjugating element.

The conjugacy algorithm used by this program is due to Volker Gebhardt, and is explained in:
Volker Gebhardt, A new Approach to the Conjugacy Problem in Garside Groups. Preprint.

Example: The braids on 4 strands: 1 2 and 3 2 are conjugate. A conjugating element is the following: 1 3 2 1.

Crossing Numbers

Computes a table containing the algebraic number of crossings for every pair of strands on a given braid. Since the crossing number is symmetric, the output only lists the number of crossings between strand i and strand j when i < j. As an example, consider the braid the braid on 3 strands 2 -1 2 1. The output is the following:
The crossing numbers of the braid on 3 strands 2 -1 2 1 are: 2 3 +------ 1| 1 -1 | 2| 2
This describes the following matrix, indicating for instance that strand 2 and strand 3 have 2 crossing points algebraically:

  1 2 3
1 * 1 -1
2 * * 2
3 * * *

Least Common Multiple

Computes the least common multiple of two braids a and b. This means a braid m such that ap=bq=m for some positive braids p and q, which are the smallest possible ones.

Example: The least common multiple of the braids on 5 strands: 2 and 3 is the following: 2 3 2.

Example: The least common multiple of the braids on 5 strands: -1 2 and 2 is the following: 2 1.

Greatest Common Divisor

Computes the greatest common divisor of two braids a and b. This means a braid d such that dp=a and dq=b for some positive braids p and q, which are the smallest possible ones.

Example: The greatest common divisor of the braids on 5 strands: 2 3 4 and 1 2 1 is the following: 2.

Example: The greatest common divisor of the braids on 5 strands: -1 2 and 2 is the following: -1.

Centralizer

Computes a generating set for the centralizer of a given braid.

The algorithm used by the program is an improved version of the one in:
N. Franco, J. Gonzalez-Meneses. Computation of centralizers in braid groups and Garside groups. Rev. Mat. Iberoamericana 19 (2003), no. 2, 367-384.

Example: The centralizer of the braid on 5 strands: 1 is generated by: 1, 3, 2 1 1 2, and D^(-1). 2 1 3 2 1. 2 1. 1 2 3.
(Actually, the fourth generator is redundant.)

Super Summit Set

Computes the Super Summit Set of a given braid a, which is the set of all braids, conjugate to a, having the smallest canonical length.

Find details in:
E. A. El-Rifai, H. R. Morton, Algorithms for positive braids, Quart. J. Math. Oxford Ser. (2) 45 (1994), no. 180, 479-497.

Example: The SSS of the braid on 5 strands: 2, consists of the following braids: 1, 2, 3, 4.

Ultra Summit Set

Computes the Ultra Summit Set of a given braid a, which is the set of all braids, conjugate to a, having the smallest canonical length, and belonging to an orbit under cycling.

Find details in: Volker Gebhardt, A new Approach to the Conjugacy Problem in Garside Groups. Preprint.

Example: The USS of the braid on 5 strands: 2, consists of the following braids: 1, 2, 3, 4.