Base and Strong Generating Sets

The key concept for representing a permutation group in Magma is the base and strong generating set (BSGS). Given a BSGS for a group, its order may be deduced immediately, and the great majority of functions for computing with permutation groups rely on one being present. If a BSGS is not already known, Magma will attempt to compute one automatically whenever it is needed.

What a BSGS Is

Suppose a group G acts on a set Omega. A base B is a sequence of distinct points from Omega such that the identity is the only element of G fixing every point of B. A base of length n determines a chain of subgroups G^(1), ..., G^(n+1), where G^(i) is the stabilizer of the first i-1 points of B (so G^(1) = G and G^(n+1) is trivial). A strong generating set for G, relative to B, is a subset S of G such that each G^(i) is generated by the strong generators it contains.

Because a BSGS may be expensive to compute for large-degree groups, Magma provides several algorithms so a user who knows something about the group in advance (for instance its order) can pick the fastest route.

Constructing a BSGS

BSGS(G) runs the general-purpose procedure with default algorithm choices. Underneath, several specific algorithms are available:

• SimsSchreier(G) applies the standard deterministic Schreier-Sims algorithm, storing transversals as Schreier vectors (parameter SV).
• RandomSchreier(G) builds a probable BSGS from randomly chosen elements of G. It is typically the fastest method, especially for large degree, and if the Order attribute has been set on G it will keep going until a BSGS accounting for that order is found. The parameters Max (default 100) and Run (default 20) bound the number of random elements tried and the number of consecutive elements that must lie in the current BSGS before stopping.
• ToddCoxeterSchreier(G) builds a BSGS via the Todd-Coxeter Schreier algorithm.
• SolubleSchreier(G) (also spelled SolvableSchreier) is specialized for soluble groups, recursively working down the derived series; it will not terminate on a non-soluble group unless the Depth parameter bounds the number of derived-series terms considered.
• Verify(G) checks (and if necessary completes) a probable BSGS obtained by a randomized method such as RandomSchreier, switching between the Todd-Coxeter-Schreier-Sims and Brownie-Cannon-Sims algorithms according to the Levels and OrbitLimit parameters.

> 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

This is the Higman-Sims simple group, presented on 100 points. ToddCoxeterSchreier builds a BSGS from the two given generators, and Order(G) then reads the group order straight off it.

Speeding Things Up with a Known Order

If the order of G is known in advance, telling Magma via AssertAttribute(G, "Order", n) lets RandomSchreier terminate as soon as it has found a BSGS accounting for that order — often the fastest way to obtain a complete BSGS, particularly for large-degree groups.

> G := WreathProduct(Sym(42), Alt(8));
> AssertAttribute(G, "Order", Factorial(42)^8 * (Factorial(8) div 2));
> RandomSchreier(G);
> Order(G);

For a group where the order is not known beforehand, the same random-Schreier-then-verify pattern is common: run RandomSchreier with generous Max and Run values, then call Verify to confirm (and if needed complete) the result.

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

Here G is the Rudvalis group in its degree-4060 permutation representation. The base has length 4, and the basic orbit lengths shrink at each level of the stabilizer chain — from the full orbit of size 4060 down to 20.

Accessing the BSGS Data

Once a BSGS is present, a family of functions expose its internal structure. Base(G) returns the base as a sequence of points, and BasePoint(G, i) gives just the i-th one. BasicOrbit(G, i) and BasicOrbitLengths(G) describe the orbits of the stabilizer chain at each level, and BasicStabilizer(G, i) returns the actual subgroup fixing the first i-1 base points — together these form the BasicStabilizerChain(G). StrongGenerators(G) returns the current strong generating set, and NumberOfStrongGenerators(G) (or Nsgens(G)) counts them.

Working with the BSGS

The BSGS also supports element-level operations. BaseImage(x) computes the sequence of images of the base points under a permutation x, which acts as a compact "coordinate" for x relative to the BSGS; conversely Permutation(G, Q) recovers the permutation from such a sequence of images. Strip(H, x) tests membership of x in H by successively factoring it through the stabilizer chain, returning whether x in H, the residual permutation, and the level at which stripping stopped. WordInStrongGenerators(H, x) expresses x as a word in the strong generators of H.

Finally, a BSGS can be modified in place: ChangeBase(~G, Q) rearranges the base so the points of Q come first, AddNormalizingGenerator(~H, x) extends a BSGS for H to one for <H, x> when x normalizes H, and ReduceGenerators(~G) strips out redundant strong generators.