Subsections

• Introduction
• Construction of a Base and Strong Generating Set
• Defining Values for Attributes
• Modifying a Base and Strong Generating Set
• Accessing the Base and Strong Generating Set
• Functions for Working with a Base and Strong Generating Set

Computing structural information for a permutation group G requires, in most cases, a representation of the set of elements of G. Magma represents this set by means of a base and strong generating set, or BSGS, for G. Suppose the group G acts on the set Omega. A base B for G is a sequence of distinct points from Omega with the property that the identity is the only element of G that fixes B pointwise. A base B of length n determines a sequence of subgroups G^((i)), 0 <= i <= n, where G^((i)) is the stabilizer of the first i - 1 points of B. Given a base B for G, a subset S of G is said to be a strong generating set for G if G^((i)) = S intersect G^((i)), for i = 1, ..., n.

Construction of a Base and Strong Generating Set

The general procedure for constructing a BSGS. This version uses the default algorithm choices.

    SV: BoolElt                         Default: true

Construct a base and strong generating set for the group G using the standard Schreier-Sims algorithm. If the parameter SV is set true (default) the transversals are stored in the form of Schreier vectors. If SV is set false, then the transversals are stored both as lists of permutations and as Schreier vectors. If the base attribute has been previously defined for G, a variant of the Sims-Schreier algorithm will be employed, in which permutation multiplications are replaced by base image calculations wherever possible.

    Max: RngIntElt                      Default: 100

    Run: RngIntElt                      Default: 20

Construct a probable base and strong generating set for the group G. The strong generators are constructed from a set of randomly chosen elements of G. The expectation is that, if sufficient random elements are taken, then, upon termination, the algorithm will have produced a BSGS for G. If the attribute Order is defined for G, the random Schreier will continue until a BSGS defining a group of the indicated order is obtained. In such circumstances this method is the fastest method of constructing a base and strong generating set for G. This is particularly so for groups of large degree. If nothing is known about G, the random Schreier algorithm provides a cheap way of obtaining lower bounds on the group's order and, in the case of a permutation group, on its degree of transitivity. This parameter has two associated parameters, Max and Run, which take positive integer values. The parameter Max specifies the number of random elements to be used (default 100). If the value of Run is n_2, then the algorithm terminates after n_2 consecutive random elements are found to lie in the set defined by the current BSGS (default 20). The two limits are independent of one another. It should be emphasized that unpredictable results may arise if the programmer uses the base and strong generators produced by this algorithm when, in fact, it does not constitute a BSGS for G.

    Random: BoolElt                     Default: true

    Max: RngIntElt                      Default: 200

    Run: RngIntElt                      Default: 50

Construct a BSGS for G using the Todd-Coxeter Schreier algorithm. If the parameter Random is defined true, the random Schreier algorithm is first applied to create a probable BSGS, using the values of the parameters Max and Run (see RandomSchreier above).

    Depth: RngIntElt                    Default: 2*Degree(G)

Construct a base and strong generating set for the soluble permutation group G using the algorithm of Sims (JSC, May/June 1990). The algorithm proceeds by recursively constructing the terms of the derived series. If G is not soluble then the algorithm will not terminate. In order to avoid non-termination, a limit on the number of terms in the normal subgroup chain constructed must be prescribed. The user may set this limit as the value of the parameter Depth. The default is twice the degree of G. This algorithm is often significantly faster than the general Schreier-Sims algorithm.

    Levels: RngIntElt                   Default: 0

    OrbitLimit: RngIntElt               Default: 100,000

Given a permutation group G for which a probable BSGS is stored, verify the correctness of the BSGS. If it is not complete, proceed to complete it. The parameter Levels defines how many levels the TCS verifies before switching to the Brownie-Cannon-Sims algorithm. If Levels is zero, the switch-over point is determined by the default value for the parameter OrbitLimit is used. The parameter OrbitLength, if assigned a positive integer value, indicates that the TCS algorithm is to be used when the basic orbit lengths exceed OrbitLimit.

    StrongGenerators: BoolElt           Default: false

    Random: BoolElt                     Default: true

    Max: RngIntElt                      Default: 100

    Run: RngIntElt                      Default: 20

Construct a presentation for the permutation group G on a set of strong generators (if the parameter StrongGenerators has the value true) and return the presentation in the form of a finitely presented group F that is isomorphic to G. In Magma, the Todd-Coxeter Schreier algorithm is used to construct the presentation. If strong generators are not already known for G, they will be constructed. If strong generators have to be constructed, the parameter Random with its associated parameters Max and Run may be used to apply the Random Schreier algorithm to construct a probable BSGS before commencing the construction of the presentation. In the case in which strong generators are already known for G, the presentation will be on these strong generators. The group homomorphism f: F -> G, defining G as a permutation representation of F, is also returned. If the parameter StrongGenerators has the value false, then the regular representation of G is computed in which the given generators are also strong generators. The remaining parameters are ignored.

Given a normal subgroup N of G, compute an fp-group representation F of the quotient G/N and the homomorphism phi: G -> F.

• The Higman-Sims simple group represented on 100 letters is generated by two permutations. To create a base and strong generating set for it using the Todd-Coxeter-Schreier algorithm, we can use the ToddCoxeterSchreier procedure as follows:

> G := sub<Sym(100) |
>    (2,8,13,17,20,22,7)(3,9,14,18,21,6,12)(4,10,15,19,5,11,16)
>        (24,77,99,72,64,82,40)(25,92,49,88,28,65,90)(26,41,70,98,91,38,75)
>        (27,55,43,78,86,87,45)(29,69,59,79,76,35,67)(30,39,42,81,36,57,89)
>        (31,93,62,44,73,71,50)(32,53,85,60,51,96,83)(33,37,58,46,84,100,56)
>        (34,94,80,61,97,48,68)(47,95,66,74,52,54,63),
>    (1,35)(3,81)(4,92)(6,60)(7,59)(8,46)(9,70)(10,91)(11,18)(12,66)(13,55)
>        (14,85)(15,90)(17,53)(19,45)(20,68)(21,69)(23,84)(24,34)(25,31)(26,32)
>        (37,39)(38,42)(40,41)(43,44)(49,64)(50,63)(51,52)(54,95)(56,96)(57,100)
>        (58,97)(61,62)(65,82)(67,83)(71,98)(72,99)(74,77)(76,78)(87,89) >;
> ToddCoxeterSchreier(G);
> Order(G);
44352000

• The simple group of Rudvalis has a permutation representation of degree 4060. A generating set for the Rudvalis group, Ru, may be found in the standard Magma database pergps, where it is called ru. We use the random Schreier algorithm followed by the Verify procedure to produce a base and strong generating set. We increase the limits for RandomSchreier to increase the probability that a complete base and strong generating set is found. This is done as follows:

> load "ru";
> RandomSchreier(G : Max := 50, Run := 20);
> Order(G);
145926144000
> Verify(G);
> Order(G);
145926144000
> Base(G);
[ 1, 2, 3, 4 ]
> BasicOrbitLengths(G);
[ 4060, 2304, 780, 20 ]

The sequence Q is defined to be the base for the permutation group G.

AssertAttribute(G, "Order", n) : GrpPerm, MonStgElt, RngIntElt ->

Define the order attribute for the permutation group G.

AssertAttribute(G, "Order", Q) : GrpPerm, MonStgElt, [<RngIntElt, RngIntElt>] ->

Define the (factored) order of the permutation group G to be Q.

[Future release] AssertAttribute(G, "BSGS", S) : GrpPerm, MonStgElt, Set(GrpPermElt) ->

Define strong generators for the permutation group G. Note that the user must have already defined a base for G.

> G := WreathProduct(Sym(42), Alt(8));
> AssertAttribute(G, "Order", Factorial(42)^8 * (Factorial(8) div 2));
> RandomSchreier(G);
> Order(G);
3061373016723610165203127456307122124535329726578404327\
5428034073188691030999256052666924787022950130890371891\
0525089665194187638747340938406861181340150889944654752\
7025207255845130274434558221633869210079882581975069742\
1672055466250914291002570275499685768646240411055766098\
2370739110690651875215676663235534126138270781440155683\
9906515353600000000000000000000000000000000000000000000\
00000000000000000000000000000

Given a group H with a base B and strong generating set X, and an element x that normalizes H belonging to a group that contains H, extend the existing BSGS for H so that they form a BSGS for the subgroup <H, x>.

Given a group H with a base B and strong generating set X, and an element x that belongs to a group containing H, replace S by S union x. The base for H will be extended, if necessary, and the relevant Schreier vectors recomputed. Thus the subgroup H may be replaced by a subgroup K = < H, x > that properly contains it.

Given a group G with a base and strong generating set, recompute the Schreier vector at level i. Note if that additional strong generators have been included since the Schreier vector was first computed, this function should produce a Schreier vector having a smaller average height.

Given a group H with a base and strong generating set, change the base of G, so that the points in the sequence Q form an initial segment of the new base.

Given a group G with a base and strong generating set, remove redundant strong generators.

A base for the permutation group G. The base is returned as a sequence of points of its natural G-set. If a base is not known, one will be constructed.

The i-th base point for the permutation group G. A base and strong generating set must be known for G.

The basic orbit at level i as defined by the current base for the permutation group G. This function assumes that a BSGS is known for G.

The basic orbits as defined by the current base for the permutation group G. This function assumes that a BSGS is known for G. The orbits are returned as a sequence of indexed sets.

The length of the basic orbit at level i as defined by the current base for the permutation group G. This function assumes that a BSGS is known for G.

The lengths of the basic orbits as defined by the current base for the permutation group G. This function assumes that a BSGS is known for G. The lengths are returned as a sequence of integers.

BasicStabiliser(G, i) : GrpPerm, RngIntElt -> GrpPerm

Given a permutation group G for which a base and strong generating set are known, and an integer i, where 1 <= i <= k with k the length of the base, return the subgroup of G which fixes the first i - 1 points of the base.

BasicStabiliserChain(G) : GrpPerm -> [GrpPerm]

Given a permutation group G, return the stabilizer chain defined by the base as a sequence of subgroups of G. If a BSGS is not already known for G, it will be created.

True if the point a of Omega lies in the basic orbit at level i. This function assumes that a BSGS is known for G.

Nsgens(G) : GrpPerm -> RngIntElt

The number of elements in the current strong generating set for G.

NumberOfStrongGenerators(G, i) : GrpPerm, RngIntElt -> RngIntElt

Nsgens(G, i) : GrpPerm, RngIntElt -> RngIntElt

The number of elements in the strong generating set for the i-th term of the stabilizer chain for G.

The Schreier vectors corresponding to the current BSGS for the permutation group G. The vectors are returned as a sequence of integer sequences.

The Schreier vector corresponding the i-th term of the stabilizer chain defined by the current BSGS for the permutation group G. The vector is returned as a sequence of integers.

A set of strong generators for the permutation group G. If they are not currently available, they will be computed.

StrongGenerators(G, i) : GrpPerm, RngIntElt -> SetIndx(GrpPermElt)

A set of strong generators for the i-th term in the stabilizer chain for the permutation group G. A BSGS must be known for G.

Given a permutation x belonging to the group G, for which a base and strong generating set is known, form the base image of x.

Given a permutation group G acting on the set Omega, for which a base and strong generating set are known, and a sequence Q of distinct points of Omega defining an element x of G, return x as a permutation.

The permutation of G defined by the Schreier vector at level i, which takes the point a of Omega to the base point at level i. This function assumes that a BSGS is known for G.

An element in the word group of G defined by the Schreier vector at level i, which takes the point a of Omega to the base point at level i. This function assumes that a BSGS is known for G.

Given an element x of a permutation group G, and given a group G for which a base and strong generating set is known, returns:

• The residual permutation y resulting from the stripping of x with respect to the BSGS for H; and
• The first level i such that y is not contained in G^((i)).

Given an element x of a permutation group G, and given a group G for which a base and strong generating set is known, returns:

• The residual word w (an element in the word group of G) resulting from the stripping of x with respect to the BSGS for H; and
• The first level i such that x is not contained in G^((i)).