Presentations

In this section we describe how to compute a presentation in terms of generators and relations for a permutation group and also how to obtain a representation of a permutation as word in the defining generators.

Generators and Relations

FPGroup(G) : GrpPerm :-> GrpFP, Hom(Grp)

Construct a presentation for the permutation group G on the set of defining generators and return the presentation in the form of a finitely presented group F that is isomorphic to G. The presentation is obtained by first computing the regular representation of G and then using the Todd-Coxeter Schreier algorithm to construct a presentation on the strong generators. In this situation the strong generators are identical to the defining generators.

A group homomorphism φ: F -> G, defining G as a permutation representation of F, is also returned.

FPGroup(G, N) : GrpPerm, GrpPerm :-> GrpFP, Hom(Grp)

FPQuotient(G, N) : GrpPerm, GrpPerm :-> GrpFP, Hom(Grp)

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

FPGroupStrong(G: parameters) : GrpPerm :-> GrpFP, Hom(Grp)

    Random: BoolElt                     Default: true

    Run: RngIntElt                      Default: 20

Construct a presentation for the permutation group G on a set of strong generators and return the presentation in the form of a finitely presented group F that is isomorphic to G. In Magma, a combination of the Schreier Todd-Coxeter Sims algorithm and the Brownie-Cannon-Sims verification procedure is used to construct the presentation. See Leon [Leo80] and Gebhardt [Geb00] for more details of the individual algorithms.

If strong generators are not already known for G, they will be constructed. If strong generators have to be constructed, the parameters Random and Run may be used to control the application of the random schreier algorithm to construct a probable BSGS before commencing the construction of the presentation. If Random is set to false then no randomising is performed, and the algorithm becomes the straight STCS algorithm. In the case in which strong generators are already known for G, the presentation will be on these strong generators.

The presentation will have the property that it includes a presentation for each group in the stabilizer chain of the BSGS.

The group isomorphism φ: F -> G, defining G as a permutation representation of F, is also returned.

Permutations as Words

Consider a permutation group G defined on d generators. The word group of G is a free group W of rank d. Then we regard G as a homomorphic image of F with associated homomorphism φ: W -> G. All operations involving words in the generators of G will be performed in W.

WordGroup(G) : GrpPerm -> GrpBB, Map

Given a permutation group G defined on d generators, return (a) a free group W on d generators represented as a group whose elements are defined by straight-line programs (SLP group), and (b) the homomorphism φ from W to G such that W.i -> G.i, for i = 1, ..., d. The group W associated with G by this function will be referred to as the word group for G.

InverseWordMap(G) : GrpPerm -> Map

Given a permutation group G and its associated word group W with canonical homomorphism φ:W -> G, construct the inverse mapping ρ. Thus, given a permutation g of G, g@ρ returns an element in the preimage of g under φ. If the word group W does not already exist, it will be created.

ActingWord(G, x, y) : GrpPerm, Elt, Elt -> GrpFPElt

Given points x and y belonging to the same G-orbit of the natural G-set X, return a word w in the word group W of G such that x^φ(w) = y. Here φ is the canonical homomorphism from W to G.