Working with Elements of a Braid Group

Contents

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 [p1, ..., pk] of permutations on n points, such that Dl c1 ... ck Dr is the representation of u in terms of simple elements, where D is the fundamental element and cj is the simple element defined by pj (j=1, ..., 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 s_{i_1}^{e_1}...s_{i_k}^{e_k} in the Artin generators with 0<ij<n and ej∈{-1, 1} for j=1, ..., k, the sequence of integers [ e1 i1, ..., ek ik ] is returned.

For a representing word ar1, t1e1...ark, tkek in the BKL generators with 1≤tj < rj≤n and ej∈{-1, 1} for j=1, ..., k, the sequence of tuples [ <e1 r1, e1 t1>, ..., <ek rk, ek tk> ] 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 Dl c1 ... ck 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 Dl c1 ... ck 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 GrpBrd_Access (H82E2)

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.)

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 T1 and T2 defining products v1 ... vk and w1 ... wl, respectively, of simple elements for the indicated presentation, such that v1 ... vk and w1 ... wl are in left normal form, the left-gcd of v1 and w1 is trivial and u = (v1 ... vk) - 1 (w1 ... wl).

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 `!'.

RightMixedCanonicalForm(u: parameters) : GrpBrdElt -> Tup, Tup
    Presentation: MonStgElt             Default:
Given an element u of a braid group B, return two tuples T1 and T2 defining products v1 ... vk and w1 ... wl, respectively, of simple elements for the indicated presentation, such that v1 ... vk and w1 ... wl are in right normal form, the right-gcd of v1 and w1 is trivial and u = (v1 ... vk) (w1 ... wl) - 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 `!'.

Example GrpBrd_NormalForm (H82E3)

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>

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 H82E4.

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 un 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 un.
u ^ v : GrpBrdElt, GrpBrdElt -> GrpBrdElt
Given elements u and v belonging to the same braid group B, return the conjugate uv = v - 1uv 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 uv = v - 1uv.
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 - 1v 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 - 1v.

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 Dl c1 ... ck of the argument u∈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∈B with left normal form Dl c1 ... ck, return the result of a cycling operation on u, that is, u^((c1^(D - l))) as new element of B in left normal form.
Cycle(~u: parameters) : GrpBrdElt ->
    Presentation: MonStgElt             Default:
Given an element u∈B with left normal form Dl c1 ... ck, replace u by the result of a cycling operation on u, that is, by u^((c1^(D - l))) in left normal form.
Decycle(u: parameters) : GrpBrdElt -> GrpBrdElt
    Presentation: MonStgElt             Default:
Given an element u∈B with left normal form Dl c1 ... ck, return the result of a decycling operation on u, that is, u^((ck - 1)) as new element of B in left normal form.
Decycle(~u: parameters) : GrpBrdElt ->
    Presentation: MonStgElt             Default:
Given an element u∈B with left normal form Dl c1 ... ck, replace u by the result of a decycling operation on u, that is, by u^((ck - 1)) in left normal form.

Example GrpBrd_Arithmetic (H82E4)

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 ws1 where s_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 * wv;
> 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 := wv;
>    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 * wv;
>    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..

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.

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∈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∈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 - 1v 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∈B satisfying uc = v if u and v are conjugate and return false otherwise.

The function first computes representatives us and vs 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 vs is found, proving that u and v are conjugate, or the ultra summit set of u is seen not to contain vs, proving that u and v are not conjugate. See Example H82E8 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 GrpBrd_Boolean (H82E5)

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");
(1)
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

(2)
This example shows that the Artin presentation and the BKL presentation give rise to distinct partial orderings on B.

s1 - 1 s2 s1 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, s1not preceq s2 s1 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, s1 - 1 s2 s1 is equal to the BKL generator a3, 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, s1preceq s2 s1 in the partial ordering defined with respect to the BKL presentation. 

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

(3)
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, s1 and s1 s2 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
s1 and s2, 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 σ1: s1: to σ2: s2:. 

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

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 - 1b 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∈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∈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∈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∈S, where succeq is defined as above.

Example GrpBrd_Boolean (H82E6)

We define the braid group B on 6 strings. 

> B := BraidGroup(6);
> SetElementPrintFormat(~B, "CFP");
(1)
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
(2)
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 u1 ... ur of simple elements is in left normal form, if and only if the left greatest common divisor of ui - 1D and ui + 1 is trivial for all i=1, ..., 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 !. 

> 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

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∈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 us of the super summit set of u with respect to the specified presentation of B and an element c of B satisfying uc = us.

Note that us is a positive conjugate of u, if us has non-negative infimum and that u does not have any positive conjugates if the infimum of us 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 us of the ultra summit set of u with respect to the specified presentation of B and an element c of B satisfying uc = us.

Note that us is an element of the super summit set of u, that us is a positive conjugate of u, if us has non-negative infimum and that u does not have any positive conjugates if the infimum of us 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 GrpBrd_Conjugates (H82E7)

(1)
In the braid group B on 4 strings we compute the sets of positive conjugates and the super summit sets of u = s1 s2 s1 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 H82E8.

(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].
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 bc = 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 GrpBrd_ConjugatesProcess (H82E8)

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 H82E7, 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 H82E10.
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 rx(s) satisfying s preceq rx(s) and xrx(s) ∈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 Sx and a simple element s, return the minimal simple element ρx(s) satisfying s preceq ρx(s) and xρx(s) ∈Sx.
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 Ux and a simple element s, return the minimal simple element cx(s) satisfying s preceq cx(s) and xcx(s) ∈Ux.
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 xs are super summit elements, return the transport of s along x -> cyc(x), that is, the element φx(s) = (D ^l xD - inf(x)) - 1 .s .(D ^l xsD - inf(x)), where D is the fundamental element of B. The transport is a simple element satisfying cyc(xs) = cyc(x)φ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 Sx and a simple element s, return the pullback of s along x -> cyc(x), that is, the unique preceq-minimal element πx(s) satisfying xπx(s) ∈Sx and s preceq φx(πx(s)) [Geb03].

Example GrpBrd_MinimalSimpleElements (H82E9)

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;
[Next][Prev] [Right] [Left] [Up] [Index] [Root]


Version: V2.29 of Fri Nov 28 15:14:01 AEDT 2025
Search: