• « Previous
• Up
• Contents
• Index
• Search
• Next »

Base and Strong Generating Set

The key concept for representing a permutation group is that of a base and strong generating set (BSGS). Given a BSGS for a group, its order may be deduced immediately. Brownie, Cannon and Sims (1991) showed that it is practical, in some cases at least, to construct a BSGS for short-base groups having degree up to ten million.

The great majority of functions for computing with permutation groups require a BSGS to be present. If one is not known, Magma will attempt to automatically compute one. For large degree groups, the computation of a BSGS may be expensive and in such cases the user may achieve better performance through directly invoking a function which creates a BSGS. For example, if the group order is known in advance, it may be supplied to Magma and then a random method for computing a BSGS is applied which will use the group order as a termination condition.

In the first part of this section we present the elementary functions that use a BSGS, while towards the end we describe firstly, functions which allow the user to select and control the algorithm employed, and secondly, functions which provide access to the BSGS data structures. The material specific to BSGS should be omitted on a first reading.

Construction of 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 Ω. A base B for G is a sequence of distinct points from Ω 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⁽ⁱ⁾, 1 ≤i ≤n + 1, where G⁽ⁱ⁾ is the stabilizer of the first i - 1 points of B. (In particular, G⁽¹⁾=G and G^{(n + 1)} is trivial.) Given a base B for G, a subset S of G is said to be a strong generating set for G (with respect to B) if G⁽ⁱ⁾ = < S ∩G⁽ⁱ⁾ >, for i = 1, ..., n.

BSGS(G) : GrpPerm ->

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

SimsSchreier(G: parameters) : GrpPerm ->

    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.

RandomSchreier(G: parameters) : GrpPerm ->

    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₂, then the algorithm terminates after n₂ 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.

If the order of the group is known then construction of a BSGS stops when a BSGS of this order is reached.

ToddCoxeterSchreier(G: parameters) : GrpPerm ->

Construct a BSGS for G using the Todd-Coxeter Schreier algorithm.

SolubleSchreier(G: parameters) : GrpPerm ->

SolvableSchreier(G: parameters) : GrpPerm ->

    Depth: RngIntElt                    Default: See below

Construct a base and strong generating set for the soluble permutation group G using the algorithm of Sims [Sim90]. 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 value, ⌈1.6 log₂ Degree(G) ⌉, is based on an upper limit (due to Dixon) on the length of the derived series of a soluble permutation group. This algorithm is often significantly faster than the general Schreier-Sims algorithm.

Verify(G: parameters ) : GrpPerm ->

    Levels: RngIntElt                   Default: 0

    OrbitLimit: RngIntElt               Default: 4,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 two parameters Levels and OrbitLimit define how many levels the Todd-Coxeter-Schreier-Sims verifies before switching to the Brownie-Cannon-Sims algorithm. If Levels is set to n non-zero then n levels are verified by the TCSS algorithm before switching. If Levels is zero, the switch-over point is determined by the value of the parameter OrbitLimit. All levels with basic orbit length at most OrbitLimit are verified using TCSS. When a level is encountered with orbit length greater than this, a decision based on expected amount of work to do for this level by each algorithm determines what strategy is used for this level. Once one level uses the BCS method, all levels from then on will use it.

> 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

> 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 ]

Defining Values for Attributes

If the order of a permutation group is known in advance, the construction of a base and strong generating set can be greatly speeded up by taking advantage of this knowledge. The AssertAttribute constructor may be used to communicate this and other useful information to Magma.

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, GrpPermBSGS ->

Define the base and strong generating set structure S to be the BSGS 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

Accessing the Base and Strong Generating Set

Base(G) : GrpPerm -> [Elt]

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.

BasePoint(G, i) : GrpPerm, RngIntElt -> Elt

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

BasicOrbit(G, i) : GrpPerm, RngIntElt -> SetIndx

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.

BasicOrbits(G) : GrpPerm -> [SetIndx]

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.

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

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.

BasicOrbitLengths(G) : GrpPerm -> [RngIntElt]

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.

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

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.

BasicStabilizerChain(G) : GrpPerm -> [GrpPerm]

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.

IsMemberBasicOrbit(G, i, a) : GrpPerm, RngIntElt, Elt -> BoolElt

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

NumberOfStrongGenerators(G) : GrpPerm -> RngIntElt

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.

SchreierVectors(G) : GrpPerm -> [ [RngIntElt] ]

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

SchreierVector(G, i) : GrpPerm, RngIntElt -> [RngIntElt]

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.

StrongGenerators(G) : GrpPerm -> SetIndx(GrpPermElt)

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.

Working with a Base and Strong Generating Set

BaseImage(x) : GrpPermElt -> [Elt]

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.

Permutation(G, Q) : GrpPerm, [Elt] -> GrpPermElt

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

SVPermutation(G, i, a) : GrpPerm, RngIntElt, Elt -> GrpPermElt

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

SVWord(G, i, a) : GrpPerm, RngIntElt, Elt -> GrpFPElt

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

Strip(H, x) : GrpPerm, GrpPermElt -> BoolElt, GrpPermElt, RngIntElt

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

(a)

the value of x in H

(b)

The residual permutation y resulting from the stripping of x with respect to the BSGS for H; and

(c)

The first level i such that y is not contained in H⁽ⁱ⁾.

WordStrip(H, x) : GrpPerm, GrpPermElt -> BoolElt, GrpFPElt, RngIntElt

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

(a)

the value of x in H

(b)

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,

(c)

The first level i such that y is not contained in H⁽ⁱ⁾.

BaseImageWordStrip(H, x) : GrpPerm, GrpPermElt -> BoolElt, GrpFPElt, RngIntElt

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

(a)

Whether the base image strip succeeded at all levels. Note that a true value here does not, on its own, imply x ∈H.

(b)

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,

(c)

The first level i such that the strip could not continue.

WordInStrongGenerators(H, x) : GrpPerm, GrpPermElt -> GrpFPElt

Given an element x of a permutation group H for which a base and strong generating set is known, returns a word in the strong generators of H which represents x. This function uses base images to determine the word for x, so giving x not∈H will have unpredictable results. This function returns the inverse of the second return value of BaseImageWordStrip, when the latter is successful.

Modifying a Base and Strong Generating Set

ChangeBase(~G, Q) : GrpPerm, [Elt] ->

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.

AddNormalizingGenerator(~H, x) : GrpPerm, GrpPermElt ->

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

ReduceGenerators(~G) : GrpPerm ->

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

• « Previous
• Up
• Contents
• Index
• Search
• Next »