Working with Elements of a Braid Group

Accessing Information

This sections describes how the internal representations of an element and a number of basic invariants can be accessed.

Parent(u): GrpBrdElt -> GrpBrd: Given an element \(u\) of a braid group \(B\), return the parent group of \(u\), that is \(B\).

# u: GrpBrdElt -> RngIntElt: Given an element \(u\) of a braid group \(B\), return the length of the representing word in the generators corresponding to the presentation selected for \(B\). Note that this is not an invariant of \(u\).

CanonicalFactorRepresentation(u: parameters): GrpBrdElt -> Tup

CFP(u: parameters): GrpBrdElt -> Tup

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return a tuple \(T = <s,l,S,r>\) describing the representation in terms of simple elements for the presentation indicated by the value of the parameter Presentation. If no value for Presentation is given, the presentation selected for \(B\) is used. The interpretation of the components of \(T\) is as follows: \(s\) is a string, either equal to "Artin" or equal to "BKL" indicating the presentation, \(l\) and \(r\) are integers, and \(S\) is a sequence \([p_1,\dots,p_k]\) of permutations on \(n\) points, such that

\[D^l c_1\cdots c_k D^r\]

is the representation of \(u\) in terms of simple elements, where \(D\) is the fundamental element and \(c_j\) is the simple element defined by \(p_j\) \((j=1,\dots,k)\) in the presentation indicated by \(s\).

WordToSequence(u: parameters): GrpBrdElt -> SeqEnum

ElementToSequence(u: parameters): GrpBrdElt -> SeqEnum

Eltseq(u: parameters): GrpBrdElt -> SeqEnum

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return a sequence describing the representing word in the generators corresponding to the presentation indicated by the value of the parameter Presentation. If no value for Presentation is given, the presentation selected for \(B\) is used. For a representing word

\[\sigma_{i_1}^{e_1}\cdots\sigma_{i_k}^{e_k}\]

in the Artin generators with \(0<i_j<n\) and \(e_j\in\{-1,1\}\) for \(j=1,\dots,k\), the sequence of integers

\[[ e_1 i_1,\dots,e_k i_k ]\]

is returned. For a representing word

\[a_{r_1,t_1}^{e_1}...a_{r_k,t_k}^{e_k}\]

in the BKL generators with \(1\le t_j < r_j\le n\) and \(e_j\in\{-1,1\}\) for \(j=1,\dots,k\), the sequence of tuples

\[[ <e_1 r_1, e_1 t_1>,\dots,<e_k r_k, e_k t_k> ]\]

is returned.

InducedPermutation(u): GrpBrdElt -> GrpPermElt: Given an element \(u\) of a braid group \(B\) on \(n\) strings, return the permutation on \(n\) points induced by \(u\) acting on the strings on which \(B\) is defined.

In the following descriptions of the functions CanonicalLength, Infimum, and Supremum, let \(D\) be the fundamental element and let \(D^l c_1\cdots c_k\) be the left normal form of the element \(u\) of the braid group \(B\) in the presentation indicated by the value of the parameter Presentation. If no value for Presentation is given, the presentation selected for \(B\) is used.

CanonicalLength(u: parameters): GrpBrdElt -> RngIntElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return the canonical length \(k\) of \(u\) for the appropriate presentation of \(B\). The argument is converted into left normal form.

Infimum(u: parameters): GrpBrdElt -> RngIntElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return the infimum \(l\) of \(u\) for the appropriate presentation of \(B\). The argument is converted into left normal form.

Supremum(u: parameters): GrpBrdElt -> RngIntElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return the supremum \(l+k\) of \(u\) for the appropriate presentation of \(B\). The argument is converted into left normal form.

In the descriptions of the functions SuperSummitCanonicalLength, SuperSummitInfimum, and SuperSummitSupremum which follow, let \(D\) be the fundamental element and let \(D^l c_1\cdots c_k\) be the normal form of a representative of the super summit set the element \(u\) of the braid group \(B\) with respect to the presentation indicated by the value of the parameter Presentation. If no value for Presentation is given, the presentation selected for \(B\) is used.

SuperSummitCanonicalLength(u: parameters): GrpBrdElt -> RngIntElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return the canonical length \(k\) of a representative of the super summit set of \(u\) with respect to the appropriate presentation of \(B\), that is, the minimal canonical length among all conjugates of \(u\). The argument is converted into left normal form.

SuperSummitInfimum(u: parameters): GrpBrdElt -> RngIntElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return the infimum \(l\) of a representative of the super summit set of \(u\) with respect to the appropriate presentation of \(B\), that is, the maximal infimum among all conjugates of \(u\). The argument is converted into left normal form.

SuperSummitSupremum(u: parameters): GrpBrdElt -> RngIntElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return the supremum \(l+k\) of a representative of the super summit set of \(u\) with respect to the appropriate presentation of \(B\), that is, the minimal supremum among all conjugates of \(u\). The argument is converted into left normal form.

Example: Access Functions for BKL Braids (ex-0cc874)

Run in calculator (opens in a new tab)

We define the braid group \(B\) on 6 strings using the BKL presentation and create an element \(u\) as a random word of length between 5 and 10 in the BKL generators.

> B := BraidGroup(6 : Presentation := "BKL");
> u := RandomWord(B, 5, 10);

The parent group of \(u\) can be accessed using the function Parent.

> Parent(u);
GrpBrd : B on 6 strings

As word in the BKL generators, \(u\) has length 5. We define a sequence describing the representation of \(u\) as word in the BKL generators.

> #u;
5
> seq_BKL := WordToSequence(u);
> seq_BKL;
[ <5, 1>, <5, 2>, <5, 4>, <4, 1>, <2, 1> ]

When we ask for a representation as word in the Artin generators, such a representation is created automatically.

> seq_Artin := WordToSequence(u : Presentation := "Artin");
> seq_Artin;
[ 4, 3, 2, 1, 2, 1, -2, -3, 1 ]

We now define the permutation \(p\) induced by \(u\) on the strings on which \(B\) is defined.

> p := InducedPermutation(u);
> p;
(4, 5)

The representation of \(u\) in terms of simple elements for the Artin presentation can be obtained using the function CanonicalFactorRepresentation.

> CanonicalFactorRepresentation(u : Presentation := "Artin");
<Artin, 0, [
    (1, 5, 4, 3),
    (1, 2),
    (1, 6)(2, 5, 3),
    (5, 6)
], -1>

We now compute the canonical lengths of \(u\) with respect to the Artin presentation and with respect to the BKL presentation. Note that these lengths are different.

> CanonicalLength(u : Presentation := "Artin");
4
> CanonicalLength(u : Presentation := "BKL");
3

Finally, we compute for both presentations the canonical lengths of a super summit representative of \(u\).

> SuperSummitCanonicalLength(u : Presentation := "Artin");
2
> SuperSummitCanonicalLength(u : Presentation := "BKL");
3

Obviously, \(u\) does not belong to its super summit set with respect to the Artin presentation. (We cannot tell for the BKL presentation from the information we have computed.)

Run in calculator (opens in a new tab)

Computing Normal Forms of Elements

This section describes functions and procedures for computing various normal forms of elements of a braid group \(B\). All normal forms are defined in terms of representations of elements as products of simple elements and depend on the presentation of \(B\) which is used. The functions documented in this section all accept a parameter Presentation which can be used to specify the presentation of \(B\) with respect to which the computation should be performed. Possible values for this parameter are the strings "Artin" and "BKL" If no value is given for Presentation, the presentation selected for \(B\) is used.

LeftNormalForm(u: parameters): GrpBrdElt -> GrpBrdElt

NormalForm(u: parameters): GrpBrdElt -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return a new element of \(B\) defined by the left normal form of \(u\) with respect to the indicated presentation.

LeftNormalForm(~u: parameters): GrpBrdElt

NormalForm(~u: parameters): GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), bring \(u\) into left normal form with respect to the indicated presentation.

RightNormalForm(u: parameters): GrpBrdElt -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return a new element of \(B\) defined by the right normal form of \(u\) with respect to the indicated presentation.

RightNormalForm(~u: parameters): GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), bring \(u\) into right normal form with respect to the indicated presentation.

LeftMixedCanonicalForm(u: parameters): GrpBrdElt -> Tup, Tup

MixedCanonicalForm(u: parameters): GrpBrdElt -> Tup, Tup

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return two tuples \(T_1\) and \(T_2\) defining products \(v_1\cdots v_k\) and \(w_1\cdots w_l\), respectively, of simple elements for the indicated presentation, such that \(v_1\cdots v_k\) and \(w_1\cdots w_l\) are in left normal form, the left-gcd of \(v_1\) and \(w_1\) is trivial and

\[u = (v_1\cdots v_k)^{-1} (w_1\cdots w_l).\]

See the entry for CanonicalFactorRepresentation for a description of the tuple format. Note that the tuples can be coerced into elements of \(B\) using the coercion operator ‘B ! T’.

RightMixedCanonicalForm(u: parameters): GrpBrdElt -> Tup, Tup

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return two tuples \(T_1\) and \(T_2\) defining products \(v_1\cdots v_k\) and \(w_1\cdots w_l\), respectively, of simple elements for the indicated presentation, such that \(v_1\cdots v_k\) and \(w_1\cdots w_l\) are in right normal form, the right-gcd of \(v_1\) and \(w_1\) is trivial and

\[u = (v_1\cdots v_k) (w_1\cdots w_l)^{-1}.\]

See the entry for CanonicalFactorRepresentation for a description of the tuple format. Note that the tuples can be coerced into elements of \(B\) using the coercion operator ‘B ! T’.

Example: Normal Forms of Braids (ex-9c32e6)

Run in calculator (opens in a new tab)

We define the braid group \(B\) on 6 strings using the Artin presentation, set the print format for elements to "CFP" and define an element \(u\) of \(B\).

> B := BraidGroup(6);
> SetElementPrintFormat(~B, "CFP");
>
> u := B ! <"Artin",
>          0,
>          [ Sym(6) | (1,6)(3,5,4), (1,3)(2,6)(4,5), (2,3)],
>          0>;
> u;
<Artin, 0, [
    (1, 6)(3, 5, 4),
    (1, 3)(2, 6)(4, 5),
    (2, 3)
], 0>

We compute and print the left normal form of \(u\) with respect to the Artin presentation of \(B\).

> u_Artin := LeftNormalForm(u);
> u_Artin;
<Artin, 1, [
    (1, 2, 6, 5, 4, 3),
    (2, 3)
], 0>

We now compute the left normal form of \(u\) with respect to the BKL presentation of \(B\). Since elements are printed with respect to the presentation selected for the parent group, that is, in the Artin presentation in our example, we use the function CanonicalFactorRepresentation to print the representation in terms of simple elements for the BKL presentation.

> u_BKL := LeftNormalForm(u : Presentation := "BKL");
> CFP(u_BKL : Presentation := "BKL");
<BKL, 2, [
    (2, 6, 5, 4, 3),
    (2, 6, 5, 4),
    (2, 6, 5),
    (2, 6),
    (2, 3)
], 0>

We define another element \(v\) of \(B\) in left normal form.

> v := LeftNormalForm(B.5*B.2^-2*B.4*B.3^-1*B.5^-1*B.3^-1*B.5);
> v;
<Artin, -3, [
    (1, 6)(2, 4, 3, 5),
    (1, 2, 6)(3, 5),
    (1, 6, 2, 5)(3, 4),
    (3, 5)(4, 6)
], 0>

As can easily be read off the representation of \(v\) in terms of simple elements which is in left normal form, \(v\) has infimum -3, canonical length 4, and supremum 1 with respect to the Artin presentation.

> Infimum(v);
-3
> CanonicalLength(v);
4
> Supremum(v);
1

Note that infimum, canonical length, and supremum of an element can also be obtained from its right normal form.

> RightNormalForm(v);
<Artin, 0, [
    (4, 6, 5),
    (1, 6)(2, 5, 3, 4),
    (1, 6)(2, 4, 5),
    (1, 6)(2, 5)
], -3>

Run in calculator (opens in a new tab)

Arithmetic Operators and Functions for Elements

This section describes the basic arithmetic operations for elements of a braid group. Strictly speaking, all functions should be considered as functions on representatives of elements, that is, words in the generators or products of simple elements. Unless stated otherwise, arithmetic operations with elements of a braid group \(B\) are performed using representations with respect to the presentation selected for \(B\). This presentation can be changed using the function SetPresentation. By default, arithmetic operations with elements of \(B\) are performed using representations in terms of simple elements; such representations are created if necessary. Experienced users can change this behaviour, if desired, using the function SetForceCFP. The complexity of all basic arithmetic operations is linear in the length of the representations of the input elements. No normalisations are performed automatically, as doing so would restrict the user’s control of operations with elements. It is, however, recommended to use the function NormalForm or its procedural version in time critical situations to limit the length of representations of elements; see Example Arithmetic with Braids in Normal Form.

u * v: GrpBrdElt, GrpBrdElt -> GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return the product \(uv\) as a new element of \(B\).

u *:= v: GrpBrdElt, GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), replace \(u\) with the product \(uv\).

u / v: GrpBrdElt, GrpBrdElt -> GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return the product \(uv^{-1}\) as a new element of \(B\).

u /:= v: GrpBrdElt, GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), replace \(u\) with the product \(uv^{-1}\).

u ^ n: GrpBrdElt, RngIntElt -> GrpBrdElt: Given an element \(u\) of a braid group \(B\) and an integer \(n\), return the power \(u^n\) as a new element of \(B\).

u ^:= n: GrpBrdElt, RngIntElt: Given an element \(u\) of a braid group \(B\) and an integer \(n\), replace \(u\) with the power \(u^n\).

u ^ v: GrpBrdElt, GrpBrdElt -> GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return the conjugate \(u^v = v^{-1}uv\) as a new element of \(B\).

u ^:= v: GrpBrdElt, GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), replace \(u\) with the conjugate \(u^v = v^{-1}uv\).

Inverse(u): GrpBrdElt -> GrpBrdElt: Given an element \(u\) of a braid group \(B\), return its inverse \(u^{-1}\) as a new element of \(B\).

Inverse(~u): GrpBrdElt: Given an element \(u\) of a braid group \(B\), replace \(u\) with its inverse \(u^{-1}\).

LeftConjugate(u, v): GrpBrdElt, GrpBrdElt -> GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return the “left conjugate” \(vuv^{-1}\) as a new element of \(B\).

LeftConjugate(~u, v): GrpBrdElt, GrpBrdElt -> GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), replace \(u\) with the “left conjugate” \(vuv^{-1}\).

LeftDiv(u, v): GrpBrdElt, GrpBrdElt -> GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return the product \(u^{-1}v\) as a new element of \(B\).

LeftDiv(u, ~v): GrpBrdElt, GrpBrdElt -> GrpBrdElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), replace \(v\) with the product \(u^{-1}v\).

The following functions Cycle and Decycle accept a parameter Presentation which can be set either to "Artin" or to "BKL". The results of the cycling and decycling operations are defined in terms of the left normal form \(D^l c_1\cdots c_k\) of the argument \(u\in B\) in terms of simple elements for a presentation of \(B\) and the results in general depend on the presentation used. The results of these functions are returned in left normal form. If no value for the parameter Presentation is given, the presentation selected for the parent group of the argument will be used.

Cycle(u: parameters): GrpBrdElt -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\in B\) with left normal form \(D^l c_1\cdots c_k\), return the result of a cycling operation on \(u\), that is,

\[u^{(c_1^{D^{-l}})}\]

as new element of \(B\) in left normal form.

Cycle(~u: parameters): GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\in B\) with left normal form \(D^l c_1\cdots c_k\), replace \(u\) by the result of a cycling operation on \(u\), that is, by

\[u^{(c_1^{D^{-l}})}\]

in left normal form.

Decycle(u: parameters): GrpBrdElt -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\in B\) with left normal form \(D^l c_1\cdots c_k\), return the result of a decycling operation on \(u\), that is,

\[u^{(c_k^{-1})}\]

as new element of \(B\) in left normal form.

Decycle(~u: parameters): GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\in B\) with left normal form \(D^l c_1\cdots c_k\), replace \(u\) by the result of a decycling operation on \(u\), that is, by

\[u^{(c_k^{-1})}\]

in left normal form.

Example: Arithmetic with Braids in Normal Form (ex-be378e)

Run in calculator (opens in a new tab)

We illustrate the importance of limiting the length of representations of elements using the function NormalForm when performing a sequence of arithmetic operations on an element. Consider the following computation in the braid group \(B\) on 6 strings. Starting with an element \(w\), we repeatedly replace \(w\) by the product \(w w^{\sigma_1}\) where \(\sigma_1\) is the first Artin generator of \(B\). A naive way of implementing this computation would be as follows.

> B := BraidGroup(6);
> u := B.5*B.2^-2*B.4*B.3^-1;
> v := B.1;
> N := 14;
>
> T := Cputime();
> w := u;
> for i := 1 to N do
>    w := w * w^v;
> end for;

This, however, yields an extremely complicated representation for the result; the representation in terms of simple elements has the length 114686.

> #CFP(w)[3];
114686

Performing subsequent computations with the result, for example computing its normal form, is very expensive.

> NormalForm(~w);
> print "total time used: ", Cputime()-T;
total time used:  149.229

One might be tempted to solve this problem by working only with elements in normal form, that is, by bringing every result of an arithmetic operation into normal form after computing it. Using this approach, computing the result of the above iteration is indeed much faster.

> T := Cputime();
> w := u;
> for i := 1 to N do
>    t := w^v;
>    NormalForm(~t);
>    w := w * t;
>    NormalForm(~w);
> end for;
> print "total time used: ", Cputime()-T;
total time used:  0.53

However, this strategy is not optimal either. For the above example, the optimal performance is obtained if the result is normalised every third pass through the iteration.

> T := Cputime();
> w := u;
> for i := 1 to N do
>    w := w * w^v;
>    if i mod 3 eq 0 then
>       NormalForm(~w);
>    end if;
> end for;
> NormalForm(~w);
> print "total time used: ", Cputime()-T;
total time used:  0.171

Unfortunately, the frequency of normalisation giving best results depends heavily on the situation, that is, both on the arithmetic operations and on the characteristics of the arguments. As a rule of thumb, the effects of normalising results too frequently are less of a problem than normalising results not often enough or not at all.

Run in calculator (opens in a new tab)

Boolean Predicates for Elements

This section describes the tests for membership, equality, and partial orderings which are available for elements of a braid group \(B\). Unless stated otherwise, all computations are performed in the presentation selected for \(B\) or in the presentation specified by the value of the parameter Presentation, either "Artin" or "BKL" if a value for this parameter is given.

u in B: GrpBrdElt, GrpBrd -> BoolElt: Given an element \(u\) of a braid group and a braid group \(B\), return true if \(u\in B\) and false otherwise.

u notin B: GrpBrdElt, GrpBrd -> BoolElt: Given an element \(u\) of a braid group and a braid group \(B\), return false if \(u\in B\) and true otherwise.

IsEmptyWord(u: parameters): GrpBrdElt -> BoolElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group, return true if \(u\) is the represented by the empty word in the specified presentation and false otherwise.

AreIdentical(u, v: parameters): GrpBrdElt, GrpBrdElt -> BoolElt

Presentation: MonStgElt                    Default: 

Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return true if \(u\) and \(v\) are represented by identical words in the specified presentation and false otherwise.

IsSimple(u: parameters): GrpBrdElt -> BoolElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group, return true if \(u\) is a simple element with respect to the specified presentation and false otherwise. The argument is converted into normal form.

IsSuperSummitRepresentative(u: parameters): GrpBrdElt -> BoolElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group, return true if \(u\) is an element of its super summit set with respect to the specified presentation and false otherwise. The argument is converted into normal form.

IsUltraSummitRepresentative(u: parameters): GrpBrdElt -> BoolElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group, return true if \(u\) is an element of its ultra summit set with respect to the specified presentation and false otherwise. The argument is converted into normal form.

IsIdentity(u: parameters): GrpBrdElt -> BoolElt

IsId(u: parameters): GrpBrdElt -> BoolElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return true if \(u\) is the identity element of \(B\) and false otherwise. The argument is converted into normal form.

u eq v: GrpBrdElt, GrpBrdElt -> BoolElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return true if \(u = v\) and false otherwise. Both arguments are converted into normal form.

u ne v: GrpBrdElt, GrpBrdElt -> BoolElt: Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return false if \(u = v\) and true otherwise. Both arguments are converted into normal form.

u le v: GrpBrdElt, GrpBrdElt -> BoolElt

IsLE(u, v: parameters): GrpBrdElt, GrpBrdElt -> BoolElt

IsLe(u, v: parameters): GrpBrdElt, GrpBrdElt -> BoolElt

Presentation: MonStgElt                    Default: 

Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return true if \(u \preceq v\), that is, if \(u^{-1}v\) is a positive element, with respect to the specified presentation and false otherwise. Note that the parameter Presentation is not available for the operator version of this predicate.

u ge v: GrpBrdElt, GrpBrdElt -> BoolElt

IsGE(u, v: parameters): GrpBrdElt, GrpBrdElt -> BoolElt

IsGe(u, v: parameters): GrpBrdElt, GrpBrdElt -> BoolElt

Presentation: MonStgElt                    Default: 

Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return true if \(u \succeq v\), that is, if \(uv^{-1}\) is a positive element, with respect to the specified presentation and false otherwise. Note that the parameter Presentation is not available for the operator version of this predicate.

IsConjugate(u, v: parameters): GrpBrdElt, GrpBrdElt -> BoolElt, GrpBrdElt

Presentation: MonStgElt                    Default: 

Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return true and an element \(c\in B\) satisfying \(u^c = v\) if \(u\) and \(v\) are conjugate and return false otherwise. The function first computes representatives \(u_s\) and \(v_s\) of the ultra summit sets of \(u\) and \(v\), respectively, with respect to the specified presentation. If this does not prove that the elements are not conjugate, the function tries to compute elements of the ultra summit set of \(u\) until either the element \(v_s\) is found, proving that \(u\) and \(v\) are conjugate, or the ultra summit set of \(u\) is seen not to contain \(v_s\), proving that \(u\) and \(v\) are not conjugate. See Example Interactive Braid Conjugacy Testing for a more detailed description. Note that testing elements for conjugacy is a hard problem and may require significant amounts of memory and CPU time.

Example: Boolean Predicates for Braids (ex-58fe4b)

Run in calculator (opens in a new tab)

We define the braid group \(B\) on 6 strings using the Artin presentation and set the print format for elements to "CFP".

> B := BraidGroup(6);
> SetElementPrintFormat(~B, "CFP");

We create pseudo-random elements of \(B\) until we find an element \(u\) which is contained in its super summit set with respect to the Artin presentation of \(B\).

> repeat
>    u := Random(B, 5, 10);
> until IsSuperSummitRepresentative(u);
> NormalForm(u);
<Artin, -2, [
    (1, 5)(2, 3, 6),
    (1, 5, 6, 3, 2, 4),
    (2, 6)(3, 4, 5)
], 0>

\(u\) is not contained in its super summit set with respect to the BKL presentation of \(B\), showing that the super summit set of an element in general depends on the presentation with respect to which it is defined.

> IsSuperSummitRepresentative(u : Presentation := "Artin");
true
> IsSuperSummitRepresentative(u : Presentation := "BKL");
false

This example shows that the Artin presentation and the BKL presentation give rise to distinct partial orderings on \(B\). \(\sigma_1^{-1}\sigma_2\sigma_1\) has negative infimum with respect to the Artin presentation and hence is not a positive element with respect to this presentation.

> Infimum(B.1^-1*B.2*B.1 : Presentation := "Artin");
-1

Consequently, \(\sigma_1\not\preceq\sigma_2\sigma_1\) in the partial ordering defined with respect to the Artin presentation.

> B.1 le B.2*B.1;
false

We can also use the function version to check this.

> IsLE(B.1, B.2*B.1 : Presentation := "Artin");
false

However, \(\sigma_1^{-1}\sigma_2\sigma_1\) is equal to the BKL generator \(a_{3,1}\) and hence is, in particular, a positive element with respect to the BKL presentation. in the BKL generators.

> B.1^-1*B.2*B.1 eq B.<3,1>;
true

Hence, \(\sigma_1\preceq\sigma_2\sigma_1\) in the partial ordering defined with respect to the BKL presentation.

> IsLE(B.1, B.2*B.1 : Presentation := "BKL");
true

We change the print format for elements of \(B\) so that only words in the Artin generators are printed.

> SetElementPrintFormat(~B, "Word");

Inducing permutations with different cycle structure, \(\sigma_1\) and \(\sigma_1\sigma_2\) cannot be conjugate in \(B\).

> InducedPermutation(B.1);
(1, 2)
> InducedPermutation(B.2*B.1);
(1, 2, 3)
> IsConjugate(B.1, B.2*B.1);
false

\(\sigma_1\) and \(\sigma_2\), however, are conjugate in \(B\). We compute a conjugating element \(c\).

> res, c := IsConjugate(B.1, B.2);
> res;
true
> NormalForm(c);
B.2 * B.1

\(c\), as desired, conjugates \(\sigma_1\) to \(\sigma_2\).

> B.1^c eq B.2;
true

Run in calculator (opens in a new tab)

Lattice Operations

This section describes the functions available for computing lattice operations, least common multiple and greatest common divisor, for elements of a braid group \(B\). The results of all lattice operations depend on the presentation used for \(B\) and on the partial ordering considered. The functions documented in this section all accept a parameter Presentation which can be used to specify the presentation of \(B\) with respect to which the computation should be performed. Possible values for this parameter are the strings "Artin" and "BKL". If no value is given for Presentation, the presentation selected for \(B\) is used.

LeftGCD(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

LeftGcd(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

LeftGreatestCommonDivisor(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

GCD(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Gcd(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

GreatestCommonDivisor(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return the left-gcd of \(u\) and \(v\), that is, the with respect to \(\preceq\) maximal element \(d\) of \(B\) satisfying \(d\preceq u\) and \(d\preceq v\). Here, \(\preceq\) is the partial ordering on \(B\) defined as follows: \(a\preceq b\) iff \(a^{-1}b\) is representable as a positive word in the specified presentation of \(B\).

RightGCD(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

RightGcd(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

RightGreatestCommonDivisor(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return the right-gcd of \(u\) and \(v\), that is, the with respect to \(\succeq\) maximal element \(d\) of \(B\) satisfying \(u\succeq d\) and \(v\succeq d\). Here, \(\succeq\) is the partial ordering on \(B\) defined as follows: \(a\succeq b\) iff \(ab^{-1}\) is representable as a positive word in the specified presentation of \(B\).

LeftGCD(S: parameters): Setq -> GrpBrdElt

LeftGcd(S: parameters): Setq -> GrpBrdElt

LeftGreatestCommonDivisor(S: parameters): Setq -> GrpBrdElt

GCD(S: parameters): Setq -> GrpBrdElt

Gcd(S: parameters): Setq -> GrpBrdElt

GreatestCommonDivisor(S: parameters): Setq -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given a set or a sequence \(S\) containing elements of a braid group \(B\), return the left-gcd of the elements of \(S\), that is, the with respect to \(\preceq\) maximal element \(d\) of \(B\) satisfying \(d\preceq s\) for all \(s\in S\), where \(\preceq\) is defined as above.

RightGCD(S: parameters): Setq -> GrpBrdElt

RightGcd(S: parameters): Setq -> GrpBrdElt

RightGreatestCommonDivisor(S: parameters): Setq -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given a set or a sequence \(S\) containing elements of a braid group \(B\), return the right-gcd of the elements of \(S\), that is, the with respect to \(\succeq\) maximal element \(d\) of \(B\) satisfying \(s\succeq d\) for all \(s\in S\), where \(\succeq\) is defined as above.

LeftLCM(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

LeftLcm(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

LeftLeastCommonMultiple(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

LCM(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Lcm(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

LeastCommonMultiple(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return the left-lcm of \(u\) and \(v\), that is, the with respect to \(\preceq\) minimal element \(d\) of \(B\) satisfying \(u\preceq d\) and \(v\preceq d\), where \(\preceq\) is defined as above.

RightLCM(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

RightLcm(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

RightLeastCommonMultiple(u, v: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given elements \(u\) and \(v\) belonging to the same braid group \(B\), return the right-lcm of \(u\) and \(v\), that is, the with respect to \(\succeq\) minimal element \(d\) of \(B\) satisfying \(d\succeq u\) and \(d\succeq v\), where \(\succeq\) is defined as above.

LeftLCM(S: parameters): Setq -> GrpBrdElt

LeftLcm(S: parameters): Setq -> GrpBrdElt

LeftLeastCommonMultiple(S: parameters): Setq -> GrpBrdElt

LCM(S: parameters): Setq -> GrpBrdElt

Lcm(S: parameters): Setq -> GrpBrdElt

LeastCommonMultiple(S: parameters): Setq -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given a set or a sequence \(S\) containing elements of a braid group \(B\), return the left-gcd of the elements of \(S\), that is, the with respect to \(\preceq\) minimal element \(d\) of \(B\) satisfying \(s\preceq d\) for all \(s\in S\), where \(\preceq\) is defined as above.

RightLCM(S: parameters): Setq -> GrpBrdElt

RightLcm(S: parameters): Setq -> GrpBrdElt

RightLeastCommonMultiple(S: parameters): Setq -> GrpBrdElt

Presentation: MonStgElt                    Default: 

Given a set or a sequence \(S\) containing elements of a braid group \(B\), return the right-lcm of the elements of \(S\), that is, the with respect to \(\succeq\) minimal element \(d\) of \(B\) satisfying \(d\succeq s\) for all \(s\in S\), where \(\succeq\) is defined as above.

Example: Lattice Operations on Braids (ex-3e6267)

Run in calculator (opens in a new tab)

We define the braid group \(B\) on 6 strings.

> B := BraidGroup(6);
> SetElementPrintFormat(~B, "CFP");

For both Artin and BKL presentation, the fundamental element is the (left or right) least common multiple of the generators. We check this for the Artin presentation…

> D_Artin := LeftLCM({B.i : i in [1..NumberOfGenerators(B)]});
> D_Artin eq FundamentalElement(B);
true
> D_Artin eq RightLCM({B.i : i in [1..NumberOfGenerators(B)]});
true

…and for the BKL presentation.

> idx := { <r,t> : r,t in {1..NumberOfStrings(B)} | r gt t };
> D_BKL := LeftLCM({B.T : T in idx} : Presentation := "BKL");
> D_BKL eq FundamentalElement(B : Presentation := "BKL");
true
> D_BKL eq RightLCM({B.T : T in idx} : Presentation := "BKL");
true

In general, left and right least common multiple of elements are different.

> LeftLCM(B.1,B.1*B.2) eq RightLCM(B.1,B.1*B.2);
false

For both Artin and BKL presentation, the following hold. Let \(D\) denote the fundamental element.

The simple elements are those positive elements \(s\) satisfying \(s\preceq D\) (or \(D\succeq s\)).
A product \(u_1\cdots u_r\) of simple elements is in left normal form, if and only if the left greatest common divisor of \(u_i^{-1}D\) and \(u_{i+1}\) is trivial for all \(i=1,\dots,r-1\). We illustrate this for the Artin presentation.

> D := FundamentalElement(B);
> forall{ s : s in Sym(6) | B!1 le B!s and B!s le D };
true
> forall{ s : s in Sym(6) | D ge B!s and B!s ge B!1 };
true

We create an element \(u\) as product of random simple elements.

> u := Random(B, 0, 0, 3, 5);
> u;
<Artin, 0, [
    (1, 5, 2)(3, 6),
    (1, 6, 5, 3),
    (1, 6, 5, 3, 2)
], 0>

We define a sequence of elements of \(B\), containing the simple elements of the above representation of \(u\) using the function CanonicalFactorRepresentation and the coercion operator B ! p.

> cfu := [ B!x : x in CFP(u)[3] ];

This representation is not in left normal form, as the above condition is violated for \(i=1\).

> IsId(LeftGCD(cfu[1]^-1*D, cfu[2]));
false

We now bring \(u\) into left normal form and extract again the sequence of simple elements.

> n := NormalForm(u);
> n;
<Artin, 0, [
    (1, 5, 3, 6, 2),
    (1, 6, 3, 2, 5)
], 0>
> cfn := [ B!x : x in CFP(n)[3] ];

This time, the above condition is satisfied.

> IsId(LeftGCD(cfn[1]^-1*D, cfn[2]));
true

Run in calculator (opens in a new tab)

Invariants of Conjugacy Classes

This section describes the functions for computing the set of positive conjugates, the super summit set, and the ultra summit set for an element of a braid group \(B\) as defined in Section Conjugacy Testing and Conjugacy Search, as well as related Magma functions. All the class invariants in general depend on the presentation of \(B\) used for their definition. Many functions documented in this section accept a parameter Presentation which can be used to specify the presentation of \(B\) with respect to which the computation should be performed. Possible values for this parameter are the strings "Artin" and "BKL". If no value is given for Presentation, the presentation selected for \(B\) is used. For any given element \(u\in B\), all the invariants defined in Section Conjugacy Testing and Conjugacy Search are finite and can be computed in principle. In practice, however, computations may fail because the sets can get very large with increasing canonical length of \(u\) or with increasing braid index of \(B\). This is in particular the case for sets of positive conjugates and for super summit sets.

PositiveConjugates(u: parameters): GrpBrdElt -> SetIndx

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return an indexed set containing the conjugates of \(u\) which can be represented as positive words in the specified presentation of \(B\).

SuperSummitRepresentative(u: parameters): GrpBrdElt -> GrpBrdElt, GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return an element \(u_s\) of the super summit set of \(u\) with respect to the specified presentation of \(B\) and an element \(c\) of \(B\) satisfying \(u^c = u_s\). Note that \(u_s\) is a positive conjugate of \(u\), if \(u_s\) has non-negative infimum and that \(u\) does not have any positive conjugates if the infimum of \(u_s\) is negative.

SuperSummitSet(u: parameters): GrpBrdElt -> SetIndx

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return the super summit set of \(u\) with respect to the specified presentation as indexed set of elements of \(B\).

UltraSummitRepresentative(u: parameters): GrpBrdElt -> GrpBrdElt, GrpBrdElt

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return an element \(u_s\) of the ultra summit set of \(u\) with respect to the specified presentation of \(B\) and an element \(c\) of \(B\) satisfying \(u^c = u_s\). Note that \(u_s\) is an element of the super summit set of \(u\), that \(u_s\) is a positive conjugate of \(u\), if \(u_s\) has non-negative infimum, and that \(u\) does not have any positive conjugates if the infimum of \(u_s\) is negative.

UltraSummitSet(u: parameters): GrpBrdElt -> SetIndx

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return the ultra summit set of \(u\) with respect to the specified presentation as indexed set of elements of \(B\).

Example: Super Summit Sets of Braids (ex-ea29be)

Run in calculator (opens in a new tab)

(1): In the braid group \(B\) on 4 strings we compute the sets of positive conjugates and the super summit sets of \(u = \sigma_1 \sigma_2 \sigma_1\) with respect to both Artin presentation and BKL presentation.

> B := BraidGroup(4);
> u := B.1*B.2*B.1;
> p_Artin := PositiveConjugates(u : Presentation := "Artin");
> p_BKL := PositiveConjugates(u : Presentation := "BKL");
> s_Artin := SuperSummitSet(u : Presentation := "Artin");
> s_BKL := SuperSummitSet(u : Presentation := "BKL");

Since the Artin generators form a subset of the BKL generators, every element which is positive with respect to the Artin presentation is also positive with respect to the BKL presentation. In particular, p_Artin is a subset of p_BKL.

> p_Artin subset p_BKL;
true

The converse inclusion does not hold.

> #p_Artin;
10
> #p_BKL;
36

For both presentations the super summit set is a subset of the set of positive conjugates, as \(u\) is positive. The converse inclusions do not hold.

> s_Artin subset p_Artin;
true
> s_BKL subset p_BKL;
true
> #s_Artin;
2
> #s_BKL;
12

(2): As we have seen in Section Conjugacy Testing and Conjugacy Search, we can decide whether two braids are conjugate by checking whether their super summit sets are equal. We illustrate this approach with two elements of \(B\), using the Artin presentation of \(B\).

> u := B.2 * B.1 * B.2^2 * B.1 * B.2;
> v := B.2^2 * B.1 * B.3 * B.1 * B.3;

Suppose we want to prove that \(u\) and \(v\) are not conjugate in \(B\). We could start by checking the cycle structure of the induced permutations on the strings on which \(B\) acts.

> CycleStructure(InducedPermutation(u));
[ <1, 4> ]
> CycleStructure(InducedPermutation(v));
[ <1, 4> ]

This does not help. Next we can check the infima and the suprema of super summit representatives.

> SuperSummitInfimum(u) eq SuperSummitInfimum(v);
true
> SuperSummitSupremum(u) eq SuperSummitSupremum(v);
true

Again, we cannot conclude anything. We decide to compare the super summit sets of \(u\) and \(v\).

> SuperSummitSet(u) eq SuperSummitSet(v);
false

Success! The super summit sets of \(u\) and \(v\) are different, proving that \(u\) and \(v\) are not conjugate. For a more efficient version of conjugacy testing see Example Interactive Braid Conjugacy Testing.

(3): Finally, we illustrate the significant difference in the sizes of super summit sets and ultra summit sets for slightly larger values of braid index and canonical length.

> B := BraidGroup(8);

We create a pseudo-random element of \(B\) as product of 5 simple elements independently chosen at random.

> x := B.4 * B.3 * B.2 * B.1 * B.5 * B.4 * B.5 *
> B.6 * B.7 * B.6 * B.5;
> x := x^2;
> Sx := SuperSummitSet(x);
> #Sx;
10972
> Ux := UltraSummitSet(x);
> #Ux;
36

The ultra summit set is much smaller than the super summit set. We try again.

> x := B.4 * B.3 * B.2 * B.1 * B.5 * B.4 * B.5;
> x := x^3;
> Sx := SuperSummitSet(x);
> #Sx;
882
> Ux := UltraSummitSet(x);
> #Ux;
18

The difference in sizes is still large. The behaviour exhibited by these examples is quite typical. In particular, the sizes of super summit sets for braids on a given number of strings and with a given canonical length show much larger fluctuations than the sizes of ultra summit sets. For a more detailed analysis we refer to [Geb03].

Run in calculator (opens in a new tab)

Computing Class Invariants Interactively

This section describes the functions relevant for interactive computation of the set of positive conjugates, the super summit set, and the ultra summit set for a given element of a braid group \(B\) as defined in Section Conjugacy Testing and Conjugacy Search.

Process versions of the algorithms used by the functions PositiveConjugates, SuperSummitSet, and UltraSummitSet are available for computing these invariants one element at a time.

PositiveConjugatesProcess(u: parameters): GrpBrdElt -> GrpBrdClassProc

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return a process for constructing the conjugates of \(u\) which can be represented as positive words in the specified presentation of \(B\). The returned process contains the first positive conjugate of \(u\) if positive conjugates exist and is empty otherwise.

SuperSummitProcess(u: parameters): GrpBrdElt -> GrpBrdClassProc

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return a process for constructing the super summit elements of \(u\) with respect to the specified presentation of \(B\). The returned process contains the first super summit element of \(u\).

UltraSummitProcess(u: parameters): GrpBrdElt -> GrpBrdClassProc

Presentation: MonStgElt                    Default: 

Given an element \(u\) of a braid group \(B\), return a process for constructing the ultra summit elements of \(u\) with respect to the specified presentation of \(B\). The returned process contains the first ultra summit element of \(u\).

BaseElement(P): GrpBrdClassProc -> GrpBrdElt: Return the element used for the construction of the process \(P\).

# P: GrpBrdClassProc -> RngIntElt: Return the number of elements that have been found by the process \(P\).

Representative(P): GrpBrdClassProc -> GrpBrdElt
Rep(P): GrpBrdClassProc -> GrpBrdElt: Given a non-empty process \(P\), return the element most recently found by \(P\). If \(P\) is empty, a runtime error will occur. The function IsEmpty can be used for checking whether a process is empty, in order to avoid runtime errors in loops and user written functions.

IsEmpty(P): GrpBrdClassProc -> BoolElt: Return true if \(P\) is empty and false otherwise. This function can be used to check whether Representative can be called for a process \(P\).

Elements(P): GrpBrdClassProc -> SetIndx: Return an indexed set containing the elements found so far by the process \(P\).

u in P: GrpBrdElt, GrpBrdClassProc -> BoolElt, GrpBrdElt: Given an element \(u\) of a braid group and a process \(P\) for computing positive conjugates or super summit elements of the element \(b\), return true and an element \(c\) satisfying \(b^c = u\) if \(u\) is one of the elements that have been constructed by \(P\) and false otherwise.

u notin P: GrpBrdElt, GrpBrdClassProc -> BoolElt: Given an element \(u\) of a braid group and a process \(P\), return false if \(u\) is one of the elements that have been constructed by \(P\) and true otherwise.

NextElement(~P): GrpBrdClassProc: Given a process \(P\), continue searching for elements until the next element is found or the search completes without finding a new element. If a new element if found, it can subsequently be accessed using the function Representative. If the search completes without finding a new element, \(P\) is marked as empty. Calling NextElement on an empty process has no effect.

Complete(~P): GrpBrdClassProc: Given a process \(P\), complete the search for elements. After executing this procedure, \(P\) is empty and the set of all elements found by \(P\) can be accessed using the function Elements. Calling Complete on an empty process has no effect.

Example: Interactive Braid Conjugacy Testing (ex-a3dd2a)

Run in calculator (opens in a new tab)

We sketch how the functions described in the preceding section could be used for testing whether two elements are conjugate and for computing a conjugating element if they are. The approach outlined here is basically the algorithm used by the function IsConjugate.

> function MyIsConjugate(u, v)
>
>  // check obvious invariants
>  infu := SuperSummitInfimum(u);
>  infv := SuperSummitInfimum(v);
>  supu := SuperSummitSupremum(u);
>  supv := SuperSummitSupremum(v);
>  if infu ne infv or supu ne supv then
>     return false, _;
>  end if;
>
>  // compute an ultra summit element for v
>  sv, cv := UltraSummitRepresentative(v);
>
>  // set up a process for computing the ultra summit set of u
>  P := UltraSummitProcess(u);
>
>  // compute ultra summit elements of u until sv is found
>  //    or sv is seen not to be in the ultra summit set of u
>  while sv notin P and not IsEmpty(P) do
>     NextElement(~P);
>  end while;
>
>  print #P, "elements computed";
>  isconj, c := sv in P;
>  if isconj then
>     // return true and an element conjugating u to v
>     return true, c*cv^-1;
>  else
>     return false, _;
>  end if;
>
> end function;

We test our function using two pairs of elements of the braid group \(B\) on 4 strings.

> B := BraidGroup(4);

As we have seen in Example Super Summit Sets of Braids, the following elements \(u\) and \(v\) are not conjugate.

> u := B.2 * B.1 * B.2^2 * B.1 * B.2;
> v := B.2^2 * B.1 * B.3 * B.1 * B.3;

To prove this, our function has to compute the whole ultra summit set of \(u\).

> MyIsConjugate(u,v);
2 elements computed
false
> #UltraSummitSet(u);
2

We try our function on another pair of elements.

> r := B.3*B.2*B.3*B.2^2*B.1*B.3*B.1*B.2;
> s := B.3^-1*B.2^-1*B.3*B.2*B.3*B.2^2*B.1*B.3*B.1*B.2^2*B.3;
> isconj, c := MyIsConjugate(r,s);
3 elements computed
> isconj;
true
> r^c eq s;
true

The ultra summit representative of \(s\) was the 3rd ultra summit element of \(r\) found. Note that the function did not have to compute the whole ultra summit set of \(r\) to find the answer.

> #UltraSummitSet(r);
6

In this small example, we could also have used super summit sets for conjugacy testing, as the super summit set of \(r\) is not much larger than its ultra summit set.

>  #SuperSummitSet(r);
22

A more challenging application of the function MyIsConjugate from above will be presented in Example Braid Group onto Symmetric Group.

Run in calculator (opens in a new tab)

Computing Minimal Simple Elements

This section describes the functions for computing minimal simple elements as introduced in Section Computing the Class Invariants and functions for computing the transport and the pullback as defined in [Geb03].

All functions documented in this section accept two parameters, Presentation and CheckArguments. The parameter Presentation can be used to specify the presentation of a braid group \(B\) with respect to which the computation should be performed. Possible values for this parameter are the strings "Artin" and "BKL". If no value is given for Presentation, the presentation selected for \(B\) is used. The parameter CheckArguments can be used to turn off argument checking for performance reasons. It should be noted that the results are undefined if functions are called with invalid arguments and argument checking is disabled.

MinimalElementConjugatingToPositive(x, s: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Presentation  : MonStgElt                    Default: 
CheckArguments: BoolElt                      Default: true

Given a positive element \(x\) of a braid group \(B\) and a simple element \(s\), return the minimal simple element \(r_x(s)\) satisfying \(s\preceq r_x(s)\) and \(x^{r_x(s)} \in B^+\).

MinimalElementConjugatingToSuperSummit(x, s: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Presentation  : MonStgElt                    Default: 
CheckArguments: BoolElt                      Default: true

Given an element \(x\) of a braid group \(B\) which is contained in its super summit set \(S_x\) and a simple element \(s\), return the minimal simple element \(\rho_x(s)\) satisfying \(s\preceq \rho_x(s)\) and \(x^{\rho_x(s)} \in S_x\).

MinimalElementConjugatingToUltraSummit(x, s: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Presentation  : MonStgElt                    Default: 
CheckArguments: BoolElt                      Default: true

Given an element \(x\) of a braid group \(B\) which is contained in its ultra summit set \(U_x\) and a simple element \(s\), return the minimal simple element \(c_x(s)\) satisfying \(s\preceq c_x(s)\) and \(x^{c_x(s)} \in U_x\).

Transport(x, s: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Presentation  : MonStgElt                    Default: 
CheckArguments: BoolElt                      Default: true

Given an element \(x\) of a braid group \(B\) and a simple element \(s\) such that both \(x\) and \(x^s\) are super summit elements, return the transport of \(s\) along \(x\rightarrow{\bf c}(x)\), that is, the element \(\phi_x(s) = (D \,\wedge_l\, xD^{-\inf(x)})^{-1} \cdot s \cdot (D \,\wedge_l\, x^sD^{-\inf(x)})\), where \(D\) is the fundamental element of \(B\). The transport is a simple element satisfying \({\bf c}(x^s) = {\bf c}(x)^{\phi_x(s)}\) [Geb03].

Pullback(x, s: parameters): GrpBrdElt, GrpBrdElt -> GrpBrdElt

Presentation  : MonStgElt                    Default: 
CheckArguments: BoolElt                      Default: true

Given an element \(x\) of a braid group \(B\) which is contained in its super summit set \(S_x\) and a simple element \(s\), return the pullback of \(s\) along \(x\rightarrow{\bf c}(x)\), that is, the unique \(\preceq\)-minimal element \(\pi_x(s)\) satisfying \(x^{\pi_x(s)} \in S_x\) and \(s \preceq \phi_x(\pi_x(s))\) [Geb03].

Example: Ultra Summit Sets from Minimal Simple Elements (ex-3ccfd3)

Run in calculator (opens in a new tab)

The following function uses the technique sketched in Section Conjugacy Testing and Conjugacy Search for computing the ultra summit set of a given braid. This is basically the algorithm used by the Magma function UltraSummitSet.

> function MyUltraSummitSet(x)
>
> // create a subset of the ultra summit set of x
> U := {@ UltraSummitRepresentative(x) @};
> gens := Generators(Parent(x));
> pos := 1;
>
> // close U under conjugation with minimal simple elements
> while pos le #U do
>    y := U[pos];
>    // add missing conjugates of y
>    for z in { y^MinimalElementConjugatingToUltraSummit(y, s)
>                  : s in gens } do
>       if z notin U then
>          Include(~U, z);
>       end if;
>    end for;
>    pos +:= 1;
> end while;
>
> return U;
>
> end function;

Run in calculator (opens in a new tab)

Working with Elements of a Braid Group#

Accessing Information#

Computing Normal Forms of Elements#

Arithmetic Operators and Functions for Elements#

Boolean Predicates for Elements#

Lattice Operations#

Invariants of Conjugacy Classes#

Computing Class Invariants Interactively#

Computing Minimal Simple Elements#

Working with Elements of a Braid Group

Accessing Information

Computing Normal Forms of Elements

Arithmetic Operators and Functions for Elements

Boolean Predicates for Elements

Lattice Operations

Invariants of Conjugacy Classes

Computing Class Invariants Interactively

Computing Minimal Simple Elements