This sections describes how the internal representations of an element and a number of basic invariants can be accessed.
Given an element u of a braid group B, return the parent group of u, that is B.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
> 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 stringsAs 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"); 3Finally, we compute for both presentations the canonical lengths of a super summit representative of u.
> SuperSummitCanonicalLength(u : Presentation := "Artin"); 2 > SuperSummitCanonicalLength(u : Presentation := "BKL"); 3Obviously, 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.)
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.
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.
Presentation: MonStgElt Default:
Given an element u of a braid group B, bring u into left normal form with respect to the indicated presentation.
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.
Presentation: MonStgElt Default:
Given an element u of a braid group B, bring u into right normal form with respect to the indicated presentation.
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 `!'.
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 `!'.
> 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); 1Note 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>
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 H80E4.
Given elements u and v belonging to the same braid group B, return the product uv as a new element of B.
Given elements u and v belonging to the same braid group B, replace u with the product uv.
Given elements u and v belonging to the same braid group B, return the product uv - 1 as a new element of B.
Given elements u and v belonging to the same braid group B, replace u with the product uv - 1.
Given an element u of a braid group B and an integer n, return the power un as a new element of B.
Given an element u of a braid group B and an integer n, replace u with the power un.
Given elements u and v belonging to the same braid group B, return the conjugate uv = v - 1uv as a new element of B.
Given elements u and v belonging to the same braid group B, replace u with the conjugate uv = v - 1uv.
Given an element u of a braid group B, return its inverse u - 1 as a new element of B.
Given an element u of a braid group B, replace u with its inverse u - 1.
Given elements u and v belonging to the same braid group B, return the "left conjugate" vuv - 1 as a new element of B.
Given elements u and v belonging to the same braid group B, replace u with the "left conjugate" vuv - 1.
Given elements u and v belonging to the same braid group B, return the product u - 1v as a new element of B.
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.
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.
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.
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.
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.
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]; 114686Performing 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.229One 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.53However, 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.171Unfortunately, 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]; 114686Performing 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.229One 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.53However, 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.171Unfortunately, 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.
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.
Given an element u of a braid group and a braid group B, return true if u∈B and false otherwise.
Given an element u of a braid group and a braid group B, return false if u∈B and true otherwise.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 H80E8 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.
> B:= BraidGroup(6); > SetElementPrintFormat(~B, "CFP");
> 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
> Infimum(B.1^-1*B.2*B.1 : Presentation := "Artin"); -1Consequently, s1not preceq s2 s1 in the partial ordering defined with respect to the Artin presentation.
> B.1 le B.2*B.1; falseWe can also use the function version to check this.
> IsLE(B.1, B.2*B.1 : Presentation := "Artin"); falseHowever, 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>; trueHence, s1preceq s2 s1 in the partial ordering defined with respect to the BKL presentation.
> IsLE(B.1, B.2*B.1 : Presentation := "BKL"); true
> 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); falses1 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.1c, as desired, conjugates σ1: s1: to σ2: s2:.
> B.1^c eq B.2; true
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.
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.
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.
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.
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.
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.
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.
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.
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.
> B := BraidGroup(6); > SetElementPrintFormat(~B, "CFP");
> 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
> 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])); falseWe 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
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.
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.
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.
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.
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.
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.
> 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; trueThe converse inclusion does not hold.
> #p_Artin; 10 > #p_BKL; 36For 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
> 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); trueAgain, we cannot conclude anything. We decide to compare the super summit sets of u and v.
> SuperSummitSet(u) eq SuperSummitSet(v); falseSuccess! 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 H80E8.
> 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; 36The 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; 18The 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].
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.
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.
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.
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.
Return the element used for the construction of the process P.
Return the number of elements that have been found by the process P.
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.
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.
Return an indexed set containing the elements found so far by the process P.
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.
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.
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.
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.
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 H80E7, 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); 2We 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; trueThe 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); 6In 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); 22A more challenging application of the function MyIsConjugate from above will be presented in Example H80E10.
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.
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^ +.
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.
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.
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].
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].
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;