N: RngIntElt Default: 0
Extension: BoolElt Default: false
Epsilon: FldRElt Default: 0.01
Asymptotic: BoolElt Default: false
The input group G is isomorphic to H, the alternating or symmetric group for some n ≥5. Note that G can be either a matrix or permutation representation of H.The algorithm used is that of [JLNP13]. Since this is Las Vegas, there is a small probability controlled by the optional parameter Epsilon that it returns false incorrectly.
If the algorithm succeeds, then it returns true, an isomorphism from G to H, an isomorphism from H to G, the map from G to its word group, and the map from the word group to G. The sixth value returned is true if H is the symmetric group, otherwise false.
The optional parameter N is an upper bound for the degree of H. If N is 0, then the maximal theoretically possible bound for the degree is assumed; this is the degree of G if G is a permutation group, and max(9, d + 2) or max(9, d + 1) if G is a matrix group of degree d, depending on the characteristic of the field. If the optional parameter Extension is true, then G is isomorphic to a central extension of H for some n ≥5. Now the first two maps returned are an epimorphism from G onto H with kernel Z(G) and a map from H to G that induces an isomorphism from H onto G/Z(G).
If the optional parameter Asymptotic is true, then the map from H to G implements the asymptotically efficient algorithm of Beals et al. [BLGN+03]. Otherwise, the algorithm employed for this map is that of [BP00], which is usually faster for moderate degrees.
If the algorithm is not successful, then false is returned.
The algorithm consists of two parts. The first part finds the degree of the alternating group and constructs standard generators, cf. [JLNP13]. The second part verifies that these elements generate G, and constructs isomorphisms between G and H, cf. [BLGN+03]. The implementation of the first part was developed by Sebastian Jambor. The implementation of the second part was developed by Jonathan Conder; he also extended the algorithm to work for both n ∈{5, ..., 10} and central extensions.
If g ∈G and G has been recognised by RecogniseAlternatingOrSymmetric, this function returns true and an element of the word group for G which evaluates to g. Otherwise, it returns false. This facilitates membership testing in G.The implementation was developed by Jonathan Conder.
> A:= AlternatingGroup (13);
> H:= Stabiliser(A, {1,2});
> G := CosetImage (A, H);
> Degree (G);
78
> success, bb_to_perm, perm_to_bb, bb_to_wg, wg_to_bb, is_sym :=
> RecogniseAlternatingOrSymmetric (G);
>
> success;
true
> is_sym;
false
>
> x:= Sym(78)!(1, 35, 16, 28, 14, 26, 69, 5, 74)(2, 54,
> 67, 18, 51, 63, 6, 50, 77)(3, 33, 78, 12, 34, 29, 19, 15, 73)
> (4, 52, 61, 24, 49, 60, 68, 38, 64)(7, 20, 71, 17,
> 32, 11, 72, 8, 36)(9, 76, 47, 31, 56, 62, 13, 53, 59)
> (10, 70, 57, 23, 37, 22, 21, 27, 25)(30, 45, 46, 43, 42,
> 44, 40, 41, 75)(39, 55, 65)(48, 66, 58);
>
> flag, w := AlternatingOrSymmetricElementToWord (G, x);
> "Is x in G?", flag;
Is x in G? true
> Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq x;
true
>
> perm_image:= bb_to_perm(x);
> perm_image;
(1, 4, 9)(2, 6, 3, 5, 10, 7, 8, 11, 12)
>
> y := Random (G);
> w := bb_to_wg (y);
> Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq y;
true
maxtries: RngIntElt Default: 100n + 5000
Extension: BoolElt Default: false
The group G should be known to be isomorphic to the symmetric group Sn for some n ≥8. The Bratus-Pak algorithm [BP00] (implemented by Derek Holt) is used to define an isomorphism between G and Sn. If successful, return true, homomorphism from G to Sn, homomorphism from Sn to G, the map from G to its word group and the map from the word group to G.If the optional parameter Extension is set, then the group G should be known to be isomorphic either to Sn or to a perfect central extension 2.Sn. In that case, the first two maps returned will be a homomorphism from G to Sn and a map from Sn to G that induces a homomorphism onto G/Z(G). The sixth value returned will be true, if G isomorphic to 2.Sn and false, if G isomorphic to 2.An.
If unsuccessful, false is returned. This will always occur if the input group is not isomorphic to Sn (or 2.Sn when Extension is set) with n ≥8, and may occur occasionally even when G is isomorphic to Sn. The optional parameter maxtries (default 100n + 5000) can be used to control the number of random elements chosen before giving up.
If g is an element of G which has been constructively recognised to be isomorphic to Sn (or 2.Sn), then return true and element of word group for G which evaluates to g. Otherwise return false. This facilitates membership testing in G.
maxtries: RngIntElt Default: 100n + 5000
Extension: BoolElt Default: false
The group G should be known to be isomorphic to the alternating group An for some n ≥9. The Bratus-Pak algorithm [BP00] (implemented by Derek Holt) is used to define an isomorphism between G and An. If successful, return true, homomorphism from G to An, homomorphism from An to G, the map from G to its word group and the map from the word group to G.If the optional parameter Extension is set, then the group G should be known to be isomorphic either to An or to a perfect central extension 2.An. In that case, the first two maps returned will be a homomorphism from G to An and a map from An to G that induces a homomorphism onto G/Z(G). The sixth value returned will be true, if G isomorphic to 2.An and false otherwise.
If unsuccessful, false is returned. This will always occur if the input group is not isomorphic to An (or 2.An when Extension is set) with n ≥9, and may occur occasionally even when G is isomorphic to An. The optional parameter {tt maxtries} (default 100n + 5000) can be used to control the number of random elements chosen before giving up.
If g is an element of G which has been constructively recognised to be isomorphic to An (or 2.An), then return true and element of word group for G which evaluates to g. Otherwise return false. This facilitates membership testing in G.
maxtries: RngIntElt Default: 5000
Extension: BoolElt Default: false
The group G should be believed to be isomorphic to Sn or An for some n > 6, or to 2.Sn or 2.An if the optional parameter Extension is set. This function attempts to determine n and whether G is symmetric or alternating. It does this by sampling orders of elements. It returns either false, if it is unable to make a decision after sampling maxtries elements (default 5000), or true, type and n, where type is "Symmetric" or "Alternating", and n is the degree. If G is not isomorphic to Sn or An (or 2.Sn or 2.An when Extension is set) for n > 6, then the output is meaningless - there is no guarantee that false will be returned. There is also a small probability of a wrong result or false being returned even when G is Sn or An with n > 6. This function was written by Derek Holt.
> G:= sub< GL(10,5) | > PermutationMatrix(GF(5),Sym(10)![2,3,4,5,6,7,8,9,1,10]), > PermutationMatrix(GF(5),Sym(10)![1,3,4,5,6,7,8,9,10,2]) >; > GuessAltsymDegree(G); true Alternating 10 > flag, m1, m2, m3, m4 := RecogniseAlternating(G,10); > flag; true > x:=Random(G); Order(x); 8 > m1(x); (1, 2, 4, 9, 10, 8, 6, 3)(5, 7) > m2(m1(x)) eq x; true > m4(m3(x)) eq x; true > flag, w := AlternatingElementToWord(G,x); > flag; true > m4(w) eq x; true > y := Random(Generic(G)); > flag, w := AlternatingElementToWord(G,y); > flag; false > flag, m1, m2, m3, m4 := RecogniseAlternating(G,11); > flag; false > flag, m1, m2, m3, m4 := RecogniseSymmetric(G,10); > flag; false
The nature of the GuessAltsymDegree function is that it assumes that its input is either an alternating or symmetric group and then tries to guess which one and the degree. As such, it is almost always correct when the input is an alternating or symmetric group, but will often return a bad guess when the input group is not of this form, as in the following example.
> GuessAltsymDegree(Sym(50)); true Symmetric 50 > GuessAltsymDegree(Alt(73)); true Alternating 73 > GuessAltsymDegree(PSL(5,5)); true Alternating 82
Given a finite quasisimple group of Lie type in any representation, the functions in this section apply probabilistic algorithms to determine its defining characteristic and type as a Lie group.
NumberRandom: RngIntElt Default: 100
Verify: BoolElt Default: true
Given a finite quasisimple permutation or matrix group G which is of Lie type, determine its defining characteristic. The Monte Carlo algorithm implemented by this function is that of Liebeck and O'Brien [LO07]. Since it is Monte Carlo, there is a small probability of error. The number of random elements considered is NumberRandom. If Verify is true, then we first verify that G is perfect by applying IsProbablyPerfect.
> F := GF (4); > w := PrimitiveElement (F); > a := [ > 0,w^3,0,0,0, > w^3,0,0,0,0, > 0,0,0,w^3,0, > 0,0,w^3,0,0, > w^2,w^2,w^3,w^3,w^3]; > b := [ > 0,0,w^3,0,0, > w^1,w^2,w^2,0,0, > w^2,w^1,w^2,0,0, > 0,0,0,0,w^3, > w^2,w^2,w^2,w^3,w^3]; > G := sub <GL(5, F) | a, b>; > LieCharacteristic(G); 11
NumberRandom: RngIntElt Default: 100
If the matrix or permutation group G is nearly simple, and its non-abelian composition factor is isomorphic to a group of Lie type in characteristic p, then this function returns true and its standard Chevalley name. Otherwise it returns false.The algorithm is that of Babai, Kantor, Pálfy and Seress [BKPS02]; this implementation was developed by Malle and O'Brien. Since it is Monte Carlo, there is a small probability of error. The number of random elements considered is NumberRandom.
The standard name is a tuple that defines the isomorphism type of the composition factor. It is similar to that employed by CompositionFactors, described in the Permutation Groups chapter.
If the composition factor is a group of Lie type, then the tuple is <s, n, q> and it defines the adjoint Chevalley group of Lie series s and Lie rank n over GF (q). The tuple entries are valid arguments for ChevalleyGroup.
If the composition factor is an alternating group, and so lies in family 17, then the tuple is <17, n, 0> and it defines the alternating group of degree n.
If the composition factor is a sporadic group and so lies in family 18, then the tuple is <18, n, s>; the string s is its standard Atlas name and n is the number of the group in family 18.
NumberRandom: RngIntElt Default: 100
If the matrix or permutation group G is nearly simple, this function returns true and a list of possible names for its non-abelian simple composition factor; otherwise it returns false. Since it is Monte Carlo, there is a small probability of error. The number of random elements considered is NumberRandom. The list of standard names follows the convention described above.The algorithm and implementation were developed by Malle and O'Brien; it uses LieType and LieCharacteristic.
We create the classical group Ω(7, 5) in its natural representation and apply SimpleGroupName to it.
> SetSeed(1); > G := Omega(7, 5); > flag, name := SimpleGroupName(G); > name; [* <B, 3, 5> *]
We create a certain 5-dimensional matrix group over GF(3) and determine which simple group it is.
> F := GF(3); > P := GL(5,F); > gens := [ > P![2,1,2,1,2,2,0,0,0,2,0,2,0,0,0,0,1,2,0,1,1,0,2,2,1], > P![2,1,0,2,1,1,2,0,2,2,1,1,2,1,1,0,2,0,1,1,1,1,2,2,2]]; > G := sub <P | gens>; > flag, name := SimpleGroupName(G); > flag; true > name; [* <18, 1, M11> *] > /* naming an alternating group */ > G := MatrixGroup<4, GF(2) | > [ 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0 ], > [ 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0 ] >; > flag, name := SimpleGroupName(G); > flag; true > /* this is A5 */ > name; [* <17, 5, 0> *] > /* naming a classical group */ > F := GF(7^2); > P := GL (6,F); > w := PrimitiveElement (F); > gens := [ > P![w^12,w^36, 0, 5, 2, 0,w^44,w^36, 0, 6, 2, 0, > w^42,w^42,w^28,w^22,w^22, 3, 4, 3, 0,w^36,w^12, 0, > 2, 3, 0,w^20,w^12, 0,w^14,w^14, 1,w^18,w^18, w^4], > > P![w^38,w^26,w^25,w^21, w^9, 3,w^21,w^45,w^33, w^4,w^28, > 2, 6, 4, w^1, w^7,w^15, 4, 1,w^36,w^35, w^5,w^41, 5, > w^31, w^7,w^43,w^36,w^12, 1,w^34,w^42,w^11,w^39,w^47, 2] > ]; > G := sub <P | gens>; > flag, name := LieType(G, 5); > flag; true > name; <A, 1, 5> > /* so this is SL(2, 5) */
Let G be an absolutely irreducible subgroup of GL(d, q). The following functions compute symplectic, unitary and orthogonal forms of the underlying vector space V left invariant by the action of G.
A bilinear form is a bilinear function κ from V x V -> F. It is G-invariant modulo scalars if for each g ∈G there is a μg ∈F such that κ(vg, wg) = μg κ(v, w) for all v, w ∈V.
Now suppose that a |-> bar(a) is an automorphism of F of order 2. A sesquilinear form is a biadditive function κ from V x V -> F such that κ( au, bv) = a bar(b) κ(u, v) for all u, v ∈V and a, b∈F. It is G-invariant modulo scalars if for each g ∈G there is a μg ∈F such that κ(vg, wg) = μg κ(v, w) for all v, w ∈V.
A quadratic form is a function χ : V -> F such that
A bilinear form which is G-invariant (modulo scalars) is represented by a matrix B such that g * B * (g)tr = μg B for all g∈G and is unique up to multiplication by an element of F. Assume F has an automorphism a |-> bar(a) of order 2; a sesquilinear form is a matrix B such that g * B * bar(g)tr = μg B for all g∈G and is unique up to multiplication by an element of F (where bar(g) denotes the matrix obtained from g by replacing each entry gij by bar(gij)). A quadratic form is represented by an upper triangular matrix Q such that the matrix g * Q * gtr, normalized into an upper triangular matrix, equals μg Q.
The functions below will exit with an error message if the input group G is reducible. They may also exit with error if G is not absolutely irreducible, or if Scalars is true and the derived subgroup [G, G] of G is not absolutely irreducible. They may however sometimes succeed in finding a fixed form when G is irreducible but not absolutely irreducible.
Scalars: BoolElt Default: false
Given as input a matrix group G acting absolutely irreducibly on the underlying vector space V over the field F, ClassicalForms will try to find a classical form which is G-invariant or prove that no such form exists. If the optional argument Scalars is true then it will look for a form which is G-invariant modulo scalars. When Scalars is true, it is only guaranteed to succeed when [G, G] acts absolutely irreducibly on V. If it finds a fixed form, then it will stop and will not look for alternative fixed forms of different types.The classical forms are: symplectic (non-degenerate, alternating bilinear), unitary (non-degenerate sesquilinear) or orthogonal (a symmetric bilinear form and a quadratic form).
The function ClassicalForms returns a record forms which contains the components formType, sign, bilinearForm, sesquilinearForm, quadraticForm and scalars. Depending on the entry formType the record components are set to indicate:
- "unknown": it is not known whether G fixes a classical form.
- "linear": it is known that G does not fix a classical form modulo scalars.
- "symplectic": G fixes a symplectic form modulo scalars. The matrix of the form is stored in bilinearForm and the scalars for each generator of G are stored in scalars. In characteristic two this also implies that no quadratic form is fixed.
- "unitary": G fixes a unitary form (modulo scalars). The matrix of the form is stored in sesquilinearForm. The scalars for each generator of G are stored in scalars.
- "orthogonalcircle":
- "orthogonalplus":
- "orthogonalminus": G fixes an orthogonal form modulo scalars. The matrix of the bilinear form is stored in bilinearForm and the corresponding quadratic form in quadraticForm. The scalars for each generator of G are stored in scalars. In the orthogonal case, sign is set to 0, 1, or -1 when formType is "orthogonalcircle", "orthogonalplus", or "orthogonalminus", respectively.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves a symplectic form (modulo scalars if the optional argument Scalars is true), this function returns true and the matrix of the form. If it is known that G does not preserve such a form it returns false. If it cannot decide (perhaps because the group does not act absolutely irreducibly), then it exits with an error message. If Scalars is true, then the list of scalars for the generators of G is also returned.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves an orthogonal form (modulo scalars if the optional argument Scalars is true), then this function returns true, the matrix of the symmetric bilinear form, and the type of the form (as in ClassicalForms). If it is known that G does not preserve such a form, it returns false. If it cannot decide, then it exits with an error message. If Scalars is true, then the list of scalars for the generators of G is also returned.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves a quadratic form (modulo scalars if the optional argument Scalars is true), this function returns true, the matrix of the form in upper triangular form, and the type of the form (as in ClassicalForms). If it is known that G does not preserve such a form it returns false. If it cannot decide, then it exits with an error message. If Scalars is true, then the list of scalars for the generators of G is also returned.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves a unitary form (non-degenerate sesquilinear) (modulo scalars if the optional argument Scalars is true), then this function returns true and the matrix of the form. If it is known that G does not preserve such a form, it returns false. If it cannot decide, then it exits with an error message. If Scalars is true, then the list of scalars for the generators of G is also returned.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves a classical form (modulo scalars if the optional argument Scalars is true), this function returns its type (see ClassicalForms). Otherwise it returns "unknown".
> G := Omega( 9, 11 ); > ClassicalForms( G ); rec<recformat<bilinearForm, quadraticForm, sesquilinearForm, bilinFlag, sesquiFlag, scalars, formType, bc, n> | bilinearForm := [ 0 0 0 0 0 0 0 0 1] [ 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 0 1 0 0] [ 0 0 0 0 0 1 0 0 0] [ 0 0 0 0 6 0 0 0 0] [ 0 0 0 1 0 0 0 0 0] [ 0 0 1 0 0 0 0 0 0] [ 0 1 0 0 0 0 0 0 0] [ 1 0 0 0 0 0 0 0 0], quadraticForm := [ 0 0 0 0 0 0 0 0 1] [ 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 0 1 0 0] [ 0 0 0 0 0 1 0 0 0] [ 0 0 0 0 3 0 0 0 0] [ 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0], sesquilinearForm := false, bilinFlag := true, sesquiFlag := false, scalars := [ 1, 1 ], formType := orthogonalcircle, sign := 0> > FormType( G ); orthogonalcircle > SymplecticForm( G ); false
Return a matrix m such that Gm lies in the classical group returned by the Magma function GU, Sp, or GO(Plus/Minus). The argument form should be a classical form of type type fixed by an absolutely irreducible subgroup G of GL(d, q). It should be the bilinear or sesquilinear form fixed by G, except when G is orthogonal in characteristic 2, in which case it should be the quadratic form. The argument type should be as in the formType component of the record returned by ClassicalForms; i.e. one of "symplectic", "unitary", "orthogonalcircle", "orthogonalplus", or "orthogonalminus".The code for this function for all cases other than orthogonal in characteristic 2 was written by Giovanni de Franceschi and James Wilson.
Scalars: BoolElt Default: false
This function calls ClassicalForms to find a form fixed by the absolutely irreducible subgroup G of GL(d, q). If Scalars is true, then ClassicalForms is called with Scalars set to true, so that a form fixed module scalars is found. If a form form of type type is fixed, then it returns TransformForm(form, type). Otherwise it returns false.
The group element g should be an element of the finite orthogonal group that preserves the given symmetric bilinear form with matrix form. If the characteristic is odd, this function returns the spinor norm of g. If the characteristic is even it returns the Dickson invariant of g; namely the rank modulo 2 of g - I. Thus for an element g of the special orthogonal group the return value is 0 if g belongs to the Omega(Plus/Minus) subgroup of index 2; otherwise the return value is 1. However, as illustrated in the following example, the spinor norm alone cannot be used to check whether an element of the orthogonal group is in Ω.
> isInOmega := func< g,form | > Determinant(g) eq 1 and SpinorNorm(g,form) eq 0 >; > G := GOPlus(6,3); > g := G![ > [ 1, 0, 0, 0, 0, 0], > [ 0, 0, 0, 0, 2, 0], > [ 0, 0, 1, 0, 0, 0], > [ 0, 0, 0, 1, 0, 0], > [ 0, 2, 0, 0, 0, 0], > [ 0, 0, 0, 0, 0, 1] ]; > _, form := SymmetricBilinearForm(G); > SpinorNorm(g,form); 0 > isInOmega(g,form); false
Let G be an irreducible subgroup of GL(d, q). The following algorithm is designed to test whether G contains the corresponding classical group Ω and is contained in Δ. Here Ω and Δ are defined as follows:
Case: MonStgElt Default: "unknown"
NumberOfElements: RngIntElt Default: 25
SetVerbose("Classical", n): Maximum: 3
RecognizeClassical takes as input a group G, which is a subgroup of GL(d, q).The parameter Case is one of "linear", "symplectic", "orthogonalplus", "orthogonalminus", "orthogonalcircle", "unitary" or "unknown"; if Case is supplied, then the algorithm seeks to decide for this case only.
The parameter NumberOfElements is the number of random elements selected from G during the execution of the algorithm.
The output of RecognizeClassical is either true, false or "Does not apply". If the algorithm returns true, then we know with certainty that G contains Ω and is contained in Δ. Note that the proof of correctness of the algorithm depends on the finite simple group classification. If it returns false then either G does not contain Ω, or G is not contained in Δ, or G is not irreducible, or there is a small chance that G is contained in Δ and contains Ω. More precisely, if the irreducible group G is contained in Δ and really does contain Ω then the probability with which the algorithm returns false is less than ε, where ε is a real number between 0 and 1. The smaller the value of ε, the larger NumberOfElements must be. If the algorithm returns "Does not apply" then it is not applicable to the given group.
If "Classical" is set to verbose then, where RecognizeClassical returns true, it also prints the statement "Proved that the group contains a classical group of type case in n random selections", where n is the number of selections needed. If it returns false, it prints a statement giving some indication of why the algorithm reached this conclusion.
Theoretical details of the algorithms used may be found in Niemeyer & Praeger [NP97][NP98] [NP99] and Praeger [Pra99]. Its approach is based on the SL-recognition algorithm (Neumann & Praeger, [NP92]). This implementation also uses algorithms described in Celler & Leedham-Green [CLG97a][CLG97b] and Celler et al. [CLGM+95].
For small fields (q < 216), the cost of this implementation for a given value of NumberOfElements is O( d3 log d ) bit operations.
This function tests whether the subgroup G of GL(d, q) contains SL(d, q). If the function can establish this fact, it returns true and otherwise false. Hence, if IsLinearGroup returns false, there is a small chance that G nevertheless contains SL(d, q). See RecognizeClassical for more details.
This function tests whether the subgroup G of CSp(d, q) contains Sp(d, q). If the function can establish this fact, it returns true and otherwise false. Hence, if IsSymplecticGroup returns false, there is a small chance that G nevertheless contains Sp(d, q). See RecognizeClassical for more details.
This function tests whether the subgroup G of COε(d, q) contains Ωε(d, q). If the function can establish this fact, it returns true and otherwise false. Hence, if IsOrthogonalGroup returns false, there is a small chance that G nevertheless contains Ωε(d, q). See RecognizeClassical for more details.
This function tests whether the subgroup G of CU(d, q) contains SU(d, q). If the function can establish this fact, it returns true and otherwise false.
If G is known to be a classical subgroup of GL(d, q) this function returns the appropriate classical type as a string, i.e. "linear", "symplectic", "orthogonalplus", "orthogonalminus", "orthogonalcircle", or "unitary". Otherwise the function returns false.
This is a refinement of ClassicalType developed by O'Brien and Taylor. If G can be identified as a natural classical group in its natural representation, return true and the type of the group -- one of the strings listed under `subtype'; otherwise return false.type subtype --------------------------------------------------- linear GL, SL symplectic CSp, Sp, ExtSp orthogonalplus CGO+, GO+, SO+, Omega+, ExtOmega+ orthogonalminus CGO-, GO-, SO-, Omega-, ExtOmega- orthogonalcircle CGO, GO, SO, Omega, ExtOmega unitary CGU, GU, SU, ExtSU, AltSU ---------------------------------------------------A group of type "ExtSp" is properly contained between the symplectic group and the conformal symplectic group. A group of type "ExtSU" is properly contained between the special unitary group and the general unitary group whereas a group of type "AltSU" is a subgroup of the conformal unitary group which contains the special unitary group but is not contained in the general unitary group. A group of type "ExtOmega" is a subgroup of the conformal orthogonal group not of type "CGO", "GO", "SO" or "Omega". (Similarly for types "ExtOmega+" and "ExtOmega-".)
> G := SU (60, 9); > G := RandomConjugate (G); > RecognizeClassical (G); true > IsLinearGroup (G); false > IsUnitaryGroup (G); true > IsSymplecticGroup (G); false > IsOrthogonalGroup (G); false > ClassicalType (G); unitary > G := Sp (462, 3); > RecognizeClassical (G); true > ClassicalType (G); symplectic > ClassicalGroupType (G); true Sp > G := CGOPlus (14, 8); > G := RandomConjugate (G); > ClassicalGroupType (G); true CGO+
The functions in this section recognise whether or not a given group G is a specified linear group T. If it is, then an isomorphism between G and T is returned.
The function ClassicalConstructiveRecognition performs constructive recognition for all classical groups, and incorporates the recognition functions listed below for specific classical groups. See also ExceptionalConstructiveRecognition which deals with most finite exceptional groups of Lie type; the remaining cases -- Suzuki groups, large and small Ree groups -- are discussed here.
If G, a matrix or permutation group, is isomorphic, possibly modulo scalars, to (P)SL(2, q), then homomorphisms between G and (P)SL(2, q) are constructed. The function returns a homomorphism from G to (P)SL(2, q), a homomorphism from (P)SL(2, q) to G, the map from G to its word group, and the map from the word group to G.If q, the cardinality of the defining field for G, is known, it should be supplied. Otherwise, the function SL2Characteristic is used to determine q; if q is large, this calculation may be expensive.
If g is an element of the matrix or permutation group G which has been constructively recognised to have central quotient isomorphic to PSL(2, q), then return true and element of word group for G which evaluates to g, else false. This facilitates membership testing in G.
NumberRandom: RngIntElt Default: 100
Verify: BoolElt Default: true
Subject to the assumption that the group G has central quotient (P)SL(2, q), determine its characteristic and field size. The Monte Carlo algorithm implemented by this function is that of Liebeck and O'Brien [LO07]. Since it is Monte Carlo, there is a small probability of error. The number of random elements considered is NumberRandom. If Verify is true, then we first verify that G is perfect by applying IsProbablyPerfect.The constructive recognition algorithms for SL(2, q) were developed by Conder, Leedham-Green and O'Brien [CLGO06]. The algorithm used for other representations was developed by Brooksbank and O'Brien.
Our first example uses G = SL(2, 32) in its natural representation. We first recognise the group and then express a random matrix of G as a word in the generators of G.
> G := SL(2, 3^2); > flag, phi, tau, gamma, delta := RecogniseSL2(G, 3^2); > g := G![1, 2, 0, 1]; > w := gamma(g); > delta(w) eq g; true
We now consider a representation of a 2-dimensional linear group inside GL(6, GF(57) ).
> K<w> := GF(5, 7); > G := > MatrixGroup<6, GF(5, 7) | > [w^19035, w^14713, w^50617, w^14957, w^51504, w^48397, w^16317, w^3829, > w^35189, w^2473, w^19497, w^77192, w^46480, w^6772, w^29577, w^61815, > w^54313, w^16757, w^43765, w^64406, w^58788, w^30789, w^13579, w^66728, > w^7733, w^45434, w^42411, w^61613, w^12905, w^6889, w^50116, w^16117, > w^56717, w^25226, w^49940, w^36836 ], > [w^63955, w^40568, w^45004, w^11642, w^39536, w^11836, w^52594, w^71166, > w^47015, w^74450, w^32373, w^37021, w^76381, w^18155, w^57943, w^31194, > w^62524, w^65864, w^11868, w^76867, w^26483, w^41335, w^64856, w^41125, > w^43990, w^40104, w^24842, w^3153, w^23777, w^60024, w^14454, w^68648, > w^43403, w^26710, w^39779, w^22074 ] >; > > flag, phi, tau, gamma, delta := RecogniseSL2(G, 5^7); > phi; Mapping from: GrpMat: G to SL(2, GF(5, 7)) given by a rule [no inverse] > g := Random(G); > h := phi (g); > h; [w^40430 w^970] [ w^5607 w^11606] > k := tau(h); > w := gamma(k); > m := delta(w);
Recall that we are working modulo scalars.
> IsScalar(m * g^-1); true > H := SL(2, 5^7); > h := H![1,1,0,1]; > g := tau(h); > Order(g); 5
We now test a random element of GL(6, GF(57) ) for membership of our group.
> g := Random(GL(6, 5^7)); > SL2ElementToWord(G, g); false
Verify: BoolElt Default: true
If G ≤GL(d, F), is isomorphic, possibly modulo scalars, to (P)SL(3, q), then construct homomorphisms between G and (P)SL(3, q). Return homomorphism from G to (P)SL(3, q), homomorphism from (P)SL(3, q) to G, the map from G to its word group and the map from the word group to G.If q, the cardinality of the defining field for G, is known, it should be supplied. Otherwise, it is computed using the functions LieCharacteristic and LieType.
If Verify is false, then assume G is isomorphic, possibly modulo scalars, to (P)SL(3, q).
If g is an element of G which has been constructively recognised to have central quotient isomorphic to PSL(3, q), then return true and element of word group for G which evaluates to g, else false. This facilitates membership testing in G.The constructive recognition algorithms for SL(3, q) were developed by Lübeck, Magaard, and O'Brien [LMO07]. Its current implementation, which is part of the CompositionTree package, was developed by Bäärnhielm and O'Brien.
> G := SL(3, 5^4); > flag, phi, tau, gamma, delta := RecogniseSL3(G); > w := PrimitiveElement (GF(5^4)); > g := GL(3, 5^4)! [1,2,1,0,w,1,0,0,w^-1]; > w := gamma (g); > delta (w) eq g; true > G := ActionGroup(SymmetricSquare(GModule(G))); > flag, phi, tau, gamma, delta := RecogniseSL3(G); > phi; Mapping from: GL(6, GF(5, 4)) to SL(3, GF(5, 4)) given by a rule [no inverse] > g := Random(G); > h := phi(g); > h; [$.1^40430 $.1^970] [ $.1^5607 $.1^11606] > k := tau(h); > w := gamma(k); > m := delta(w);
Recall that we are working modulo scalars. We conclude by testing whether a random element of GL(6, 54) is contained in our group.
> IsScalar(m * g^-1); true > g := Random(GL(6, 5^4)); > SL3ElementToWord(G, g); false
Use the Kantor-Seress algorithm to try to find an isomorphism between the finite group G (regarded as a black-box group) and SL(d, q) or PSL(d, q). The first return value indicates whether the attempt was successful. If so, then the second and third return values are mutually inverse homomorphisms (modulo scalars if G isomorphic to (PSL)(d, q)) from G to SL(d, q) and from SL(d, q) to G.Warning: This function often returns false even when G is isomorphic to SL(d, q) or PSL(d, q), so it should be called repeatedly until it returns true!
Use the Kantor-Seress algorithm to try to find an isomorphism between the finite group G (regarded as a black-box group) and Sp(d, q) or PSp(d, q) for odd q. The first return value indicates whether the attempt was successful. If so, then the second and third return values are mutually inverse homomorphisms (modulo scalars if G isomorphic to (PSp)(d, q)) from G to Sp(d, q) and from Sp(d, q) to G.Warning: This function often returns false even when G is isomorphic to Sp(d, q) or PSp(d, q), so it should be called repeatedly until it returns true!
Use an algorithm of Peter Brooksbank to try to find an isomorphism between the finite group G (regarded as a black-box group) and Sp(4, q). The first return value indicates whether the attempt was successful. If so, then the second and third return values are mutually inverse homomorphisms from G to (P)Sp(d, q) and from (P)Sp(d, q) to G. The fourth and fifth return values are mutually inverse homomorphisms from G to the word group W of G and from W to G. The sixth and seventh return values are standard generators for G and straight-line programs for these generators in the generators of G.
Use an algorithm of Peter Brooksbank to try to find an isomorphism between the finite group G (regarded as a black-box group) and SU(3, q) or PSU(3, q) for q>2. The first return value indicates whether the attempt was successful. If so, then the second and third return values are mutually inverse homomorphisms (modulo scalars if G isomorphic to (PSU)(3, q)) from G to SU(3, q) and from SU(3, q) to G. The third and fourth return values are mutually inverse homomorphisms from G to the word group W of G and from W to G.
Use an algorithm of Peter Brooksbank to try to find an isomorphism between the finite group G (regarded as a black-box group) and SU(4, q) or PSU(4, q). The first return value indicates whether the attempt was successful. If so, then the second and third return values are mutually inverse homomorphisms (modulo scalars if G isomorphic to (PSU)(4, q)) from G to SU(4, q) and from SU(4, q) to G. The third and fourth return values are mutually inverse homomorphisms from G to the word group W of G and from W to G.
Let H be a perfect classical group of degree d, and let H act absolutely irreducibly on a defining characteristic module W of dimension at most d2. Magaard, O'Brien & Seress [MOAS08] and Corr [Cor13] describe algorithms which, given as input the representation of H on W, construct a d-dimensional projective representation of H. Their implementations, prepared by Brian Corr and Eamonn O'Brien, are described below. Note that the algorithms have various limitations in terms of type of group, degree d, and defining field size; if an algorithm does not apply to the input case, it returns false.
If G is a perfect defining characteristic absolutely irreducible representation of a classical group H of degree d and G has degree in [d + 1, ..., d2], then return true and H, otherwise false.In the second signature, we supply the information that H has degree d, defining field GF(q), and its type is one of SL, Sp, SU, Omega, Omega+, Omega-.
G is a perfect defining characteristic absolutely irreducible representation of a classical group H of small degree, to which RecogniseSmallDegree has been successfully applied; if g is in G, return true and a preimage of g in H, otherwise false.
G is a perfect defining characteristic absolutely irreducible representation of a classical group H of small degree, to which RecogniseSmallDegree has been successfully applied; if h is in H, return true and the image of h in G, otherwise false. Note that SmallDegreePreimage and this function are inverses only up to a choice of scalars.
> G := SL(4, 9);
> M := GModule (G);
> M := SymmetricPower (M, 2);
> G := MatrixGroup (M);
> G := RandomConjugate (G);
> flag, H := RecogniseSmallDegree (G, "SL", 4, 9);
> flag;
true
> H;
MatrixGroup(4, GF(3^2))
Generators:
[ 0 1 0 0]
[ 0 0 0 1]
[$.1^6 2 2 $.1]
[ 2 $.1 0 $.1]
[ 0 0 1 0]
[$.1^2 $.1^7 1 $.1^6]
[ 1 2 $.1^6 $.1^6]
[ $.1 0 $.1^7 0]
> g := Random (G);
> flag, h := SmallDegreePreimage (G, g);
> h;
[$.1^6 0 0 $.1^2]
[$.1^6 0 $.1^3 0]
[$.1^2 $.1^5 2 $.1]
[ 0 $.1^3 $.1^5 $.1]
> flag, gbar := SmallDegreeImage (G, h);
> flag;
true
> IsScalar (g * gbar^-1);
true
A description of the functionality for constructive recognition and constructive membership testing of the Suzuki groups (Sz)(q), with q = 22m + 1 for some m > 0 follows.
The main intrinsics of the package are RecogniseSz(G) which performs constructive recognition of G isomorphic to (Sz)(q), SzElementToWord(G, g) which returns a GrpSLPElt for g in the generators of G, and IsSuzukiGroup(G) which is a non-constructive test for isomorphism between G and (Sz)(q).
Informative printing can be obtained using one of a number of verbose flags:
Given a matrix group G, this function determines (non-constructively) whether or not G is isomorphic to (Sz)(q). The corresponding finite field cardinality q is also returned.If the group G is defined over a field of odd characteristic or has degree greater than 4, the Monte Carlo algorithm of LieType is used. If G has degree 4 and is over a field of characteristic 2, then a fast Las Vegas algorithm is used, described in [Baccent127aaccent127a06].
Verify: BoolElt Default: true
FieldSize: RngIntElt Default:
Optimise: BoolElt Default: false
Let G be a group that is absolutely irreducible and is defined over a minimal field. This function constructively recognises G as a Suzuki group. If G is isomorphic to (Sz)(q), where q is the size of the defining field of G, then return:The isomorphisms are composed of maps that are defined by rules, so Function should be used on each component to avoid unnecessary built-in membership testing. The word group is the GrpSLP group which is the parent of the elements returned by SzElementToWord. In general this is not the same as WordGroup(G), but is created from it using AddRedundantGenerators.
- Isomorphism from G to (Sz)(q).
- Isomorphism from (Sz)(q) to G.
- Map from G to the word group of G.
- Map from the word group of G to G.
If Verify is true, then it is checked if G is isomorphic to (Sz)(q), using IsSuzukiGroup. In that case, FieldSize must be set to the correct value of q. Constructive recognition of 2.(Sz)(8) is also handled.
If Optimise is true, then the third map returns element in an optimised word group (using AddRedundantGenerators). Then each invocation of the map will be faster, but the initialisation will take longer.
The algorithms used for constructive recognition are described in [Baccent127aaccent127a06] and [Baccent127aaccent127a05].
If G has been constructively recognised as a Suzuki group, and if g is an element of G, then return true and a GrpSLPElt from the word group of G which evaluates to g, else return false.This facilitates membership testing in G.
If q = 22m + 1 for some m > 0, return a short presentation of (Sz)(q) on the Magma standard generators, i.e. the generators returned by the Sz intrinsic.
G is constructively recognised as (Sz)(q) for some q. Verify that it satisfies a presentation for this group.
CheckInput: BoolElt Default: true
Let F be a finite field of cardinality q = 22m + 1 for some m > 0, and let twists be a sequence of n distinct integers in the range [0 ... 2m]. The function returns an absolutely irreducible representation of (Sz)(q) having dimension 4n, being a tensor product of twisted powers of the copy returned by the Sz intrinsic, where the twists are given by the input sequence.If CheckInput is true, then it is verified that F and twists satisfy the above requirements. Otherwise this is not checked.
We illustrate the basic facilities starting with a random conjugate of the standard version of the Suzuki group Sz(32). We first perform non-constructive recognition.
> G := Sz(32); > G ^:= Random(Generic(G)); > flag, q := SuzukiRecognition(G); > flag, q eq 32; true true
The next step is to perform constructive recognition. The explicit isomorphisms will be the values of iso and inv.
> flag, iso, inv, g2slp, slp2g := RecognizeSz(G); > flag; true > iso, inv; Mapping from: GrpMat: G to MatrixGroup(4, GF(2^5)) given by a rule [no inverse] Mapping from: MatrixGroup(4, GF(2^5)) to GrpMat: G given by a rule [no inverse]
We now experiment with membership testing. We use Function to avoid Magma's built-in membership testing but in doing so, we may not obtain the shortest possible SLP.
> w := Function(g2slp)(G.1); > #w; 284
The algorithm is probabilistic, so different executions will most likely give different results.
> ww := Function(g2slp)(G.1); > w eq ww; false
Note that the resulting SLPs are from a word group that is not the word group W corresponding to the defining generators of G. However, they can be coerced into W.
> W := WordGroup(G); > NumberOfGenerators(Parent(w)), NumberOfGenerators(W); 7 3 > flag, ww := IsCoercible(W, w); > flag; true > slp2g(w) eq Evaluate(ww, UserGenerators(G)); true
So there are two ways to get the element back. An alternative is to use the intrinsic SzElementToWord, which is better if the elements are not known to lie in the group.
> flag, ww := SzElementToWord(G, G.1); > flag, slp2g(w) eq slp2g(ww); true true
We take an element just outside the group.
> H := Sp(4, 32); > flag, ww := SzElementToWord(G, H.1); > flag; false > // in this case we will not get an SLP > ww := Function(g2slp)(H.1); > ww; false > SatisfiesSzPresentation(G); true
As a variation we apply the machinery to 2.Sz(8). We demonstrate constructive recognition and constructive membership testing.
> A := ATLASGroup("2Sz8");
> reps := MatRepKeys(A);
> G := MatrixGroup(reps[3]);
> Degree(G), CoefficientRing(G);
40 Finite field of size 7
> flag, iso, inv, g2slp, slp2g := RecognizeSz(G);
> flag;
true
> R := RandomProcess(G);
> g := Random(R);
> w := Function(g2slp)(g);
> slp2g(w) eq g;
true
For the next example we consider a case where the dimension is large. We construct the Suzuki group in a 64-dimensional matrix representation and then take a random conjugate and also rewrite is over a smaller field.
> F := GF(2, 9); > twists := [0, 3, 6]; > G := SuzukiIrreducibleRepresentation(F, twists); > Degree(G), IsAbsolutelyIrreducible(G); 64 true > G ^:= Random(Generic(G)); > flag, GG := IsOverSmallerField(G); > flag, CoefficientRing(GG); true Finite field of size 2^3
Non-constructive recognition is harder in this case and will give us the defining field size. Constructive recognition will decompose the tensor product.
> time SuzukiRecognition(GG); true 512 Time: 2.330 > time flag, iso, inv, g2slp, slp2g := RecogniseSz(GG); Time: 4.800 > iso; Mapping from: GrpMat: GG to MatrixGroup(4, GF(2^9)) given by a rule [no inverse]
Constructive membership is again easy
> R := RandomProcess(GG); > g := Random(R); > time w := Function(g2slp)(g); Time: 0.020 > // but SLP evaluation is harder in large dimensions > time slp2g(w) eq g; true Time: 0.370 > time SatisfiesSzPresentation(GG); true Time: 10.930
The final example will be in cross characteristic. We build a representation of Sz(8) in cross characteristic.
> G := Sz(8);
> _, P := SuzukiPermutationRepresentation(G);
> // for example over GF(9)
> M := PermutationModule(P, GF(3, 2));
> factors := CompositionFactors(M);
> exists(m64){f : f in factors | Dimension(f) eq 64};
true
> m64;
GModule m64 of dimension 64 over GF(3^2)
> H := ActionGroup(m64);
> IsAbsolutelyIrreducible(H);
true
> flag, G := IsOverSmallerField(H);
> Degree(G), CoefficientRing(G);
64 Finite field of size 3
We actually end up with a group in characteristic 3.
> time flag, iso, inv, g2slp, slp2g := RecogniseSz(G); Time: 3.490 > iso; Mapping from: GrpMat: G to MatrixGroup(4, GF(2^3)) given by a rule [no inverse] > R := RandomProcess(G); > g := Random(R); > time w := Function(g2slp)(g); Time: 0.010 > time slp2g(w) eq g; true Time: 0.110 > time SatisfiesSzPresentation(G); true Time: 0.330
This machinery provides functionality for constructive recognition and constructive membership testing of the small Ree groups ((2)G2)(q) = (Ree)(q), with q = 32m + 1 for some m > 0.
The important intrinsics are RecogniseRee which performs constructive recognition of G isomorphic to (Ree)(q), ReeElementToWord which returns a GrpSLPElt for g in the generators of G, and IsReeGroup which is a non-constructive test for isomorphism between G and (Ree)(q).
There are a few verbose flags used in the package.
Verify: BoolElt Default: true
FieldSize: RngIntElt Default:
Optimise: BoolElt Default: false
The matrix group G is absolutely irreducible and defined over minimal field. Constructively recognise G as a Ree group. If G is isomorphic to (Ree)(q) where q is the size of the defining field of G, then return:The isomorphisms are composed of maps that are defined by rules, so Function should be used on each component to avoid unnecessary built-in membership testing.
- Isomorphism from G to (Ree)(q).
- Isomorphism from (Ree)(q) to G.
- Map from G to the word group of G.
- Map from the word group of G to G.
The word group is the GrpSLP which is the parent of the elements returned by ReeElementToWord. In general this is not the same as WordGroup(G), but is created from it using AddRedundantGenerators.
If Verify is true, then it is checked that G is isomorphic to (Ree)(q), using IsReeGroup, otherwise this is not checked. In that case, FieldSize must be set to the correct value of q.
If Optimise is true, then the third map returns element in an optimised word group (using AddRedundantGenerators). Then each invocation of the map will be faster, but the initialisation will take longer.
The algorithm for constructive recognition is described in [Baccent127aaccent127a14].
If G has been constructively recognised as a Ree group, and if g is an element of G, then return true and a GrpSLPElt from the word group of G which evaluates to g, else return false.This facilitates membership testing in G.
Determine (non-constructively) if G is isomorphic to (Ree)(q). The corresponding q is also returned.If G is over a field of characteristic not 3 or has degree greater than 7, the Monte Carlo algorithm of LieType is used. If G has degree 7 and is over a field of characteristic 3, then a fast Las Vegas algorithm is used.
CheckInput: BoolElt Default: true
The finite field F must have size q = 32m + 1 for some m > 0, and twists should be a sequence of n distinct pairs of integers (i, j) where i is 7 or 27 and j in the range [0 ... 2m].Return an absolutely irreducible representation of (Ree)(q), a tensor product of twisted powers of the representation of dimension 7 or 27, where the twists are given by the input sequence.
If CheckInput is true, then it is verified that F and twists satisfy the above requirements. Otherwise this is not checked.
Our first example shows off the recognition machinery for the Ree group defined over GF(27).
> SetSeed(1); > F := GF(3, 3); > G := ReeGroup(F); > G ^:= Random(Generic(G)); > flag, q := ReeRecognition(G); > flag, q eq #F; true true > flag, iso, inv, g2slp, slp2g := RecognizeRee(G); > flag; true > iso, inv; Mapping from: GrpMat: G to MatrixGroup(7, GF(3^3)) given by a rule [no inverse] Mapping from: MatrixGroup(7, GF(3^3)) to GrpMat: G given by a rule [no inverse]
We now experiment with membership testing. As the algorithm is probabilistic, different executions will most likely give different results.
> w := Function(g2slp)(G.1); > #w; 342 > ww := Function(g2slp)(G.1); > w eq ww; false
The resulting SLPs are from another word group but can be coerced into W.
> W := WordGroup(G); > NumberOfGenerators(Parent(w)), NumberOfGenerators(W); 7 3 > flag, ww := IsCoercible(W, w); > flag; true > // so there are two ways to get the element back > slp2g(w) eq Evaluate(ww, UserGenerators(G)); true
If the elements are not known to lie in the group, a better alternative is to use the intrinsic ReeElementToWord. We take a generator of Ω(7, F) as an example of an element not lying in G2(27).
> flag, ww := ReeElementToWord(G, G.1); > flag, slp2g(w) eq slp2g(ww); true true > H := Omega(7, #F); > flag, ww := ReeElementToWord(G, H.1); > flag; false > ww := Function(g2slp)(H.1); > ww; false
This machinery provides functionality for constructive recognition and constructive membership testing of the large Ree groups ((2)F4)(q) = (LargeRee)(q), with q = 22m + 1 for some m > 0.
The important intrinsics are RecogniseLargeRee which performs constructive recognition of G isomorphic to (LargeRee)(q), LargeReeElementToWord which returns a GrpSLPElt for g in the generators of G, and IsLargeReeGroup which is a non-constructive test for isomorphism between G and (LargeRee)(q).
There are a few verbose flags used in the package.
Verify: BoolElt Default: true
FieldSize: RngIntElt Default:
Optimise: BoolElt Default: false
The matrix group G is absolutely irreducible and defined over minimal field. Constructively recognise G as a Large Ree group. If G is isomorphic to (LargeRee)(q) where q is the size of the defining field of G, then return:The isomorphisms are composed of maps that are defined by rules, so Function should be used on each component to avoid unnecessary built-in membership testing.
- Isomorphism from G to (LargeRee)(q).
- Isomorphism from (LargeRee)(q) to G.
- Map from G to the word group of G.
- Map from the word group of G to G.
The word group is the GrpSLP which is the parent of the elements returned by LargeReeElementToWord. In general this is not the same as WordGroup(G), but is created from it using AddRedundantGenerators.
If Verify is true, then it is checked that G is isomorphic to (LargeRee)(q), using IsLargeRee, otherwise this is not checked. In that case, FieldSize must be set to the correct value of q.
If Optimise is true, then the third map returns element in an optimised word group (using AddRedundantGenerators). Then each invocation of the map will be faster, but the initialisation will take longer.
If G has been constructively recognised as a Large Ree group, and if g is an element of G, then return true and a GrpSLPElt from the word group of G which evaluates to g, else return false.This facilitates membership testing in G.
Determine (non-constructively) if G is isomorphic to (LargeRee)(q). The corresponding q is also returned.If G is over a field of characteristic not 2 or has degree greater than 26, the Monte Carlo algorithm of LieType is used. If G has degree 26 and is over a field of characteristic 2, then a fast Las Vegas algorithm is used.