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 canonical factors 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, ..., p_k] of permutations on n points, such that D^l c_1 ... c_k D^r is the representation of u in terms of canonical factors, where D is the fundamental element and c_j is the canonical factor defined by p_j (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<i_j<n and e_j in {-1, 1} for j=1, ..., k, the sequence of integers [ e_1 i_1, ..., 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 <= t_j < r_j <= n and e_j in {-1, 1} for j=1, ..., k, the sequence of tuples [ <e_1 r_1, e_1 t_1>, ..., <e_k r_k, e_k t_k> ] 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.
For the following description of the functions CanonicalLength, Infimum and Supremum, let D be the fundamental element and let D^l c_1 ... 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.
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.
For the following description of the functions SuperSummitCanonicalLength, SuperSummitInfimum and SuperSummitSupremum, let D be the fundamental element and let D^l c_1 ... 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.
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 canonical factors 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 canonical factors 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 T_1 and T_2 defining products v_1 ... v_k and w_1 ... w_l, respectively, of canonical factors for the indicated presentation, such that v_1 ... v_k and w_1 ... w_l are in left normal form, the left-gcd of v_1 and w_1 is trivial and u = (v_1 ... v_k)^(-1) (w_1 ... 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 `!'.
Presentation: MonStgElt Default:
Given an element u of a braid group B, return two tuples T_1 and T_2 defining products v_1 ... v_k and w_1 ... w_l, respectively, of canonical factors for the indicated presentation, such that v_1 ... v_k and w_1 ... w_l are in right normal form, the right-gcd of v_1 and w_1 is trivial and u = (v_1 ... v_k) (w_1 ... 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 := 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 canonical factors 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>
> 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 canonical
factors 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 canonical factors.
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 canonical factors; 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 H29E4.
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 u^n as a new element of B.
Given an element u of a braid group B and an integer n, replace u with the power u^n.
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.
Given elements u and v belonging to the same braid group B, replace u with the conjugate u^v := v^(-1)uv.
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^(-1)v as a new element of B.
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 ... c_k of the argument u in B in terms of canonical factors 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 in B with left normal form D^l c_1 ... 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.
Presentation: MonStgElt Default:
Given an element u in B with left normal form D^l c_1 ... 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.
Presentation: MonStgElt Default:
Given an element u in B with left normal form D^l c_1 ... 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.
Presentation: MonStgElt Default:
Given an element u in B with left normal form D^l c_1 ... c_k, replace u by the result of a decycling operation on u, that is, by u^((c_k^(-1))) in left normal form.
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^(s_1) 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 * w^v; > end for;This, however, yields an extremely complicated representation for the result; the representation in terms of canonical factors 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 the arithmetic operations and 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 canonical factors 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 the arithmetic operations and 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 in B and false otherwise.
Given an element u of a braid group and a braid group B, return false if u in 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 canonical factor 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 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^(-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.
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 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 super 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 super summit set of u until either the element v_s is found, proving that u and v are conjugate, or the super summit set of u is seen not to contain v_s, proving that u and v are not conjugate. See Example H29E8 for a more detailed description.
Note that testing elements for conjugacy is a very hard problem and may require significant amounts of memory and CPU time even for small examples.
> 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, s_1not preceq s_2 s_1 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, s_1^(-1) s_2 s_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>; trueHence, s_1preceq s_2 s_1 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, s_1 and s_1 s_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); falses_1 and s_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.1c, as desired, conjugates sigma_1: s_1: to sigma_2: s_2:.
> 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 for 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^(-1)b 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 in 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 in 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 in 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 in 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
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 canonical factors.
> 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 canonical factors
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 canonical factors.
> 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 available for computing the set of positive conjugates and the super summit set for elements of a braid group B.
The set of positive conjugates and the super summit set of an element 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, both the set of its positive conjugates and its super summit set are finite and can be computed in principle. However, the sets can get very large fast with increasing length of u or with increasing braid index of B.
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 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 the infimum of u_s 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 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.1*B.2*B.1; > v := B.1^-1*B.2*B.1;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.
> InducedPermutation(u); (1, 3) > InducedPermutation(v); (1, 3)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 this test see Example H29E8.
Process versions of the algorithms used by the functions PositiveConjugates and SuperSummitSet are available for positive conjugates or super summit elements of an element u one at a time. The functions relevant for this interactive versions are described in this section.
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.
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 b^c = 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.
We sketch how the functions described in the preceeding 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 a super summit element for v > sv, cv := SuperSummitRepresentative(v); > > // set up a process for computing super summit elements of u > P := SuperSummitProcess(u); > > // compute super summit elements of u until sv is found > // or sv is seen not to be in the super 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 H29E7, the following elements u and v are not conjugate.
> u := B.1*B.2*B.1; > v := B.1^-1*B.2*B.1;To prove this, our function has to compute the whole super summit set of u.
> MyIsConjugate(u,v); 2 elements computed false > #SuperSummitSet(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*B.1*B.2*B.3*B.1*B.2*B.3^2*B.2*B.1; > isconj, c := MyIsConjugate(r,s); 5 elements computed > isconj; true > r^c eq s; trueThe super summit representative of s was the 5th super summit element of r found. Note that the function did not have to compute the whole super summit set of r to find the answer.
> #SuperSummitSet(r); 22