25 Finite Polycyclic Groups

Ag groups (see Words in Finite Polycyclic Groups) are a subcategory of finitely generated groups (see Groups).

The following sections describe how subgroups of ag groups are represented (see More about Ag Groups), additional operators and record components of ag groups (see Ag Group Operations and Ag Group Records) and functions which work only with ag groups (see Ag Group Functions and Subgroups and Properties of Ag Groups). Some additional information about generating systems of subgroups and factor groups are given in Generating Systems of Ag Groups and Factor Groups of Ag Groups.

One Cohomology Group describes how to compute the groups of one coboundaries and one cocycles for given ag groups. Complements gives informations how to obtain complements and conjugacy classes of complements for given ag groups.

Subsections

Let G be a finite polycyclic group with PAG system (g1, ..., gn) as described in Words in Finite Polycyclic Groups. Let U be a subgroup of G. A generating system (u1, ..., ur) of U is called the canonical generating system, CGS for short, of U with respect to (g1, ..., gn) if and only if

\begintabularcl (i) & (u1, ..., ur) is a PAG system for U,
(ii) & δ( ui ) > δ( uj ) for i > j,
(iii) & λ( ui ) = 1 for i = 1, ..., r,
(iv) & νδ(ui)(uj) = 0 for i ≠ j.
\endtabular

If a generating system (u1, ..., ur) fulfills only conditions (i) and (ii) this system is called an induced generating system, IGS for short, of U. With respect to the PAG system of G a CGS but not an IGS of U is unique.

If a power-commutator or power-conjugate presentation of G is known, a finite polycyclic group with collector can be initialized in GAP3 using `AgGroupFpGroup` (see AgGroupFpGroup). `AgGroup` (see AgGroup) converts other types of finite solvable groups, for instance solvable permutation groups, into an ag group. The collector can be changed by `ChangeCollector` (see ChangeCollector). The elements of these group are called ag words.

A canonical generating system of a subgroup U of G is returned by `Cgs` (see Cgs) if a generating set of ag words for U is known. See Generating Systems of Ag Groups for details.

We call G a parent, that is a ag group with collector and U a subgroup, that is a group which is obtained as subgroup of a parent group. An ag group is either a parent group with PAG system or a subgroup of such a parent group.

Although parent groups need only an AG system, only `AgGroupFpGroup` (see AgGroupFpGroup) and `RefinedAgSeries` (see RefinedAgSeries) work correctly with a parent group represented by an AG system which is not a PAG system, because subgroups are identified by canonical generating systems with respect to the PAG system of the parent group. Inconsistent power-conjugate or power-commutator presentations are not allowed (see IsConsistent). Some functions support factor group arguments. See Factor Groups of Ag Groups and FactorArg for details.

Our standard example in the following sections is the symmetric group of degree 4, defined by the following sequence of GAP3 statements. You should enter them before running any example. For details on `AbstractGenerators` see AbstractGenerator.

```    gap> a  := AbstractGenerator( "a" );;  # (1,2)
gap> b  := AbstractGenerator( "b" );;  # (1,2,3)
gap> c  := AbstractGenerator( "c" );;  # (1,3)(2,4)
gap> d  := AbstractGenerator( "d" );;  # (1,2)(3,4)
gap> s4 := AgGroupFpGroup( rec(
>        generators := [ a, b, c, d ],
>        relators   := [ a^2, b^3, c^2, d^2, Comm( b, a ) / b,
>                        Comm( c, a ) / d, Comm( d, a ),
>                        Comm( c, b ) / ( c*d ), Comm( d, b ) / c,
>                        Comm( d, c ) ] ) );;
gap> s4.name := "s4";;
gap> a := s4.generators;; b := s4.generators;;
gap> c := s4.generators;; d := s4.generators;; ```

25.2 Construction of Ag Groups

The most fundamental way to construct a new finite polycyclic group is `AgGroupFpGroup` (see AgGroupFpGroup) together with `RefinedAgSeries` (see RefinedAgSeries), if a presentation for an AG system of a finite polycyclic group is known.

But usually new finite polycyclic groups are constructed from already existing finite polycyclic groups. The direct product of known ag groups can be formed by `DirectProduct` (see DirectProduct); also, if for instance a permutation representation P of a finite polycyclic group G is known, `WreathProduct` (see WreathProduct) returns the P-wreath product of G with a second ag group. If a homomorphism of a finite polycyclic group G into the automorphism group of another finite polycyclic group H is known, `SemidirectProduct` returns the semi direct product of G with H.

Fundamental finite polycyclic groups, such as elementary abelian, arbitrary finite abelian groups, and cyclic groups, are constructed by the appropriate functions (see The Basic Groups Library).

25.3 Ag Group Operations

In addition to the operators described in Operations for Groups the following operator can be used for ag groups.

`G mod H`

`mod` returns a record representing an factor group argument, which can be used as argument for some functions (see Exponents). See Factor Groups of Ag Groups and FactorArg for details.

25.4 Ag Group Records

In addition to the record components described in Group Records the following components may be present in the group record of an ag group G.

`isAgGroup`:

is always `true`.

`isConsistent`:

is `true` if G has a consistent presentation (see IsConsistent).

`compositionSeries`:

contains a composition series of G (see CompositionSeries).

`cgs`:

contains a canonical generating system for G. If G is a parent group, it is always present. See Generating Systems of Ag Groups for details.

`igs`:

contains an induced generating system for G. See Generating Systems of Ag Groups for details.

`elementaryAbelianFactors`:

see ElementaryAbelianSeries.

`sylowSystem`:

contains a Sylow system (see SylowSystem).

25.5 Set Functions for Ag Groups

As already mentioned in the introduction of the chapter, ag groups are domains. Thus all set theoretic functions, for example `Intersection` and `Size`, can be applied to ag groups. This and the following sections give further comments on the definition and implementations of those functions for ag groups. All set theoretic functions not mentioned here not treated special for ag groups.

`Elements( G )`

The elements of a group G are constructed using a canonical generating system. See Elements for Ag Groups.

`g in G`

Membership is tested using `SiftedAgWord` (see SiftedAgWord), if g lies in the parent group of G. Otherwise `false` is returned.

`IsSubset( G, H )`

If G and H are groups then `IsSubset` tests if the generators of H are elements of G. Otherwise `DomainOps.IsSubset` is used.

`Intersection( G, H )`

The intersection of ag groups G and H is computed using Glasby's algorithm. See Intersection for Ag Groups.

`Size( G )`

The size of G is computed using a canonical generating system of G. See Size for Ag Groups.

25.6 Elements for Ag Groups

`AgGroupOps.Elements( G )`

Let G be an ag group with canonical generating system (g1, ..., gn) where the relative order of gi is oi. Then { g1e1 ... gnen ; 0 ≤ ei < oi } is the set of elements of G.

25.7 Intersection for Ag Groups

`AgGroupOps.Intersection( U, V )`

If either V or U is not an ag group then `GroupOps.Intersection` is used in order to compute the intersection of U and V. If U and V have different parent groups then the empty list is returned.

Let U and V be two ag group with common parent group G. If one subgroup if known to be normal in G the `NormalIntersection` (see NormalIntersection) is used in order to compute the intersection.

If the size of U or V is smaller than `GS_SIZE` then the intersection is computed using `GroupOps.Intersection`. By default `GS_SIZE` is 20.

If an elementary abelian ag series of G is known, Glasby's generalized covering algorithm is used (see GS90). Otherwise a warning is given and `GroupOps.Intersection` is used, but this may be too slow.

```    gap> d8_1 := Subgroup( s4, [ a, c, d ] );
Subgroup( s4, [ a, c, d ] )
gap> d8_2 := Subgroup( s4, [ a*b, c, d ] );
Subgroup( s4, [ a*b, c, d ] )
gap> Intersection( d8_1, d8_2 );
Subgroup( s4, [ c, d ] )
gap> Intersection( d8_1^b, d8_2^b );
Subgroup( s4, [ c*d, d ] ) ```

25.8 Size for Ag Groups

`AgGroupOps.Size( G )`

Let G be an ag group with induced generating system (g1, ..., gn) where the relative order of gi is oi. Then the size of G is o1 * ... * on.

`AgGroupOps.Size` allows a factor argument (see FactorArg) for G. It uses `Index` (see Index) in such a case.

25.9 Group Functions for Ag Groups

As ag groups are groups, all group functions, for example `IsAbelian` and `Normalizer`, can be applied to ag groups. This and the following sections give further comments on the definition and implementations of those functions for ag groups. All group functions not mentioned here are not treated in a special way.

`Group( U )`

`CompositionSeries( G )`

Let (g1, ..., gn) be an induced generating system of G with respect to the parent group of G. Then for i∈ {1,...,n} the i.th composition subgroup Si of the AG system is generated by (gi, ...,gn). The n+1.th composition subgroup Sn+1 is the trivial subgroup of G. The AG series of G is the series {S1, ..., Sn+1}.

`Centralizer( U )`

The centralizer of an ag group U in its parent group is computed using linear methods while stepping down an elementary abelian series of its parent group.

`Centralizer( U, H )`

This function call computes the centralizer of H in U using linear methods. H and U must have a common parent.

`Centralizer( U, g )`

The centralizer of a single element g in an ag group U may be computed whenever g lies in the parent group of U. In that case the same algorithm as for the centralizer of subgroups is used.

`ConjugateSubgroup( U, g )`

If g is an element of U then U is returned. Otherwise the remainder of the shifting of g through U is used to conjugate an induced generating system of U. In that case the information bound to `U.isNilpotent`, `U.isAbelian`, `U.isElementaryAbelian` and `U.isCyclic`, if known, is copied to the conjugate subgroup.

`Core( S, U )`

`AgGroupOps.Core` computes successively the core of U stepping up a composition series of S. See Thi87.

`CommutatorSubgroup( G, H )`

See CommutatorSubgroup for Ag Groups for details.

`ElementaryAbelianSeries( G )`

`AgGroupOps.ElementaryAbelianSeries` returns a series of normal subgroups of G with elementary abelian factors.

```    gap> ElementaryAbelianSeries( s4 );
[ s4, Subgroup( s4, [ b, c, d ] ), Subgroup( s4, [ c, d ] ),
Subgroup( s4, [  ] ) ]
gap> d8 := Subgroup( s4, [ a*b^2, c, d ] );
Subgroup( s4, [ a*b^2, c, d ] )
gap> ElementaryAbelianSeries( d8 );
[ Subgroup( s4, [ a*b^2, c, d ] ), Subgroup( s4, [ c, d ] ),
Subgroup( s4, [  ] ) ] ```

If G is no parent group then `AgGroupOps.ElementaryAbelianSeries` will compute a elementary abelian series for the parent group and intersect this series with G. If G is a parent group then `IsElementaryAbelianAgSeries` (see IsElementaryAbelianAgSeries) is used in order to check if such a series exists. Otherwise an elementary abelian is computed refining the derived series (see LNS84,Gla87).

`ElementaryAbelianSeries( L )`

L must be a list of ag groups S1 = H, ..., Sm = {1} with a common parent group such that Si is a subgroup of Si-1 and Si is normal in G for all i∈ {2, ..., m}. Then the function returns a series of normal subgroups of G with elementary abelian factors refining the series L.

`NormalIntersection( V, W )`

If V is an element of the AG series of G, then `AgGroupOps.NormalIntersection` uses the depth of V in order to compute the intersection. Otherwise it uses the Zassenhaus sum-intersection algorithm (see GS90).

`Normalizer( G, U )`

`SylowSubgroup( G, p )`

`AgGroupOps.SylowSubgroup` uses `HallSubgroup` (see HallSubgroup) in order to compute the sylow subgroup of G.

`DerivedSeries( G )`

`AgGroupOps.DerivedSeries` uses `DerivedSubgroup` (see DerivedSubgroup) in order to compute the derived series of G. It checks if G is normal in its parent group H. If it is normal all the derived subgroups are also normal in H. G is always the first element of this list and the trivial group always the last one since G is soluble.

`LowerCentralSeries( G )`

`AgGroupOps.LowerCentralSeries` uses `CommutatorSubgroup` (see CommutatorSubgroup) in order to compute the lower central series of G. It checks if G is normal in its parent group H. If it is normal all subgroups of the lower central series are also normal in H.

`Random( U )`

Let (u1, ..., ur) be a induced generating system of U. Let e1, ..., er be the relative order of u1, ..., ur. Then for r random integers νi between 0 and ei - 1 the word u1ν1* ...* urνr is returned.

`IsCyclic( G )`

`IsFinite( G )`

As G is a finite solvable group `AgGroupOps.IsFinite` returns `true`.

`IsNilpotent( U )`

`AgGroupOps.IsNilpotent` uses Glasby's nilpotency test for ag groups (see Gla87).

`IsNormal( G, U )`

`IsPerfect( G )`

As G is a finite solvable group it is perfect if and only if G is trivial.

`IsSubgroup( G, U )`

`ConjugacyClasses( H )`

The conjugacy classes of elements are computed using linear methods. The algorithm depends on the ag series of the parent group of H being a refinement of an elementary abelian series. Thus if this is not true or if H is not a member of the elementary abelian series, an isomorphic group, in which the computation can be done, is created.

The algorithm that is used steps down an elementary abelian series of the parent group of H, basically using affine operation to construct the conjugacy classes of H step by step from its factorgroups.

`Orbit( U, pt, op )`

`AgGroupOps.Orbit` returns the orbit of pt under U using the operation op. The function calls `AgOrbitStabilizer` in order to compute the orbit, so please refer to AgOrbitStabilizer for details.

`Stabilizer( U, pt, op )`

`AsGroup( D )`

`FpGroup( U )`

`RightCoset( U, g )`

`AbelianGroup( D, L )`

Let L be the list [o1, ..., on] of nonnegative integers oi > 1. Then `AgWordsOps.AbelianGroup` returns the direct product of the cyclic groups of order oi using the domain description D. The generators of these cyclic groups are named beginning with ``a'', ``b'', ``c'', ... followed by a number if oi is a composite integer.

`CyclicGroup( D, n )`

`ElementaryAbelianGroup( D, n )`

`DirectProduct( L )`

`WreathProduct( G, H, α )`

25.10 AsGroup for Ag Groups

`AgGroupOps.AsGroup( G )`

`AgGroupOps.AsGroup` returns a copy H of G. It does not change the parent status. If G is a subgroup so is H.

`AgWordsOps.AsGroup( L )`

Let L be a list of ag words. Then `AgWordsOps.AsGroup` uses `MergedCgs` (see MergedCgs) in order to compute a canonical generating system for the subgroup generated by L in the parent group of the elements of L.

25.11 Group for Ag Groups

`AgGroupOps.Group( G )`

`AgGroupOps.Group` returns an isomorphic group H such that H is a parent group and `H.bijection` is bond to an isomorphism between H and G.

`AgWordsOps.Group( D, gens, id )`

Constructs the group G generated by gens with identity id. If these generators do not generate a parent group, a new parent group H is construct. In that case new generators are used and `H.bijection` is bound to isomorphism between H and G.

25.12 CommutatorSubgroup for Ag Groups

`AgGroupOps.CommutatorSubgroup( G, H )`

Let g1, ..., gn be an canonical generating system for G and h1, ..., hm be an canonical generating system for H. The normal closure of the subgroup S generated by Comm( gi, hj ) for 1 ≤ i ≤ n and 1 ≤ j ≤ m under G and H is the commutator subgroup of G and H.

But if G or H is known to be normal in the common parent of G amd H then the subgroup S is returned because if G normalizes H or vice versa then S is already the commutator subgroup (see Gla87).

If <G> = H the commutator subgroup is generated by Comm( gi, gj ) for 1 ≤ i < j ≤ n (see LNS84). Note that `AgGroupOps.CommutatorSubgroup` checks `G.derivedSubgroup` in that case.

25.13 Normalizer for Ag Groups

`AgGroupOps.Normalizer( S, U )`

Note that the AG series of G should be the refinement of an elementary abelian series, see IsElementaryAbelianAgSeries. Otherwise the calculation of the normalizer is done using an orbit algorithm, which is generally too slow or space extensive. You can construct a new polycyclic presentation for G such that AG series is a refinement of an elementary abelian series with `ElementaryAbelianSeries` (see ElementaryAbelianSeries) and `IsomorphismAgGroup`.

For details on the implementation see GS90,CNW90.

25.14 IsCyclic for Ag Groups

`AgGroupOps.IsCyclic( G )`

`AgGroupOps.IsCyclic` returns `false` if G is no abelian group. Otherwise G is finite of order p1e1 ... pnen where the pi are distinct primes then G is cyclic if and only if each <G>pi has index pi in G.

`AgGroupOps.IsCyclic` computes the groups <G>pi using the fact that the map x → xpi is a homomorphism of G, so that the pi.th powers of an induced generating system of G are a homomorphic image of an igs (see Cel92).

25.15 IsNormal for Ag Groups

`AgGroupOps.IsNormal( G, U )`

Let G be a parent group. Then `AgGroupOps.IsNormal` checks if the conjugate of each generator of U under each induced generator of G which has a depth not contained in U is an element of U. Otherwise `AgGroupOps.IsNormal` checks if the conjugate of each generator of U under each generator of G is an element of U.

25.16 IsSubgroup for Ag Groups

`AgGroupOps.IsSubgroup( G, U )`

If G is a parent group of U, then `AgGroupOps.IsSubgroup` returns `true`. If the CGS of U is longer than that of G, U cannot be a subgroup of G. Otherwise `AgGroupOps.IsSubgroup` shifts each generator of U through G (see SiftedAgWord) in order to check if U is a subgroup of G.

25.17 Stabilizer for Ag Groups

`AgGroupOps.Stabilizer( U, pt, op )`

Let U be an ag group acting on a set Ω by op. Let pt be an element of Ω. Then `AgGroupOps.Stabilizer` returns the stabilizer of pt in U.

op must be a function taking two arguments such that op( p, u ) is the image of a point p∈Ω under the action of an element u of U. If conjugation should be used op must be `OnPoints`.

The stabilizer is computed by stepping up the composition series of U. The whole orbit <pt>U is not stored during the computation (see LNS84). Of course this saving of space is bought at the cost of time. If you need a faster function, which may use more memory, you can use `AgOrbitStabilizer` (see AgOrbitStabilizer) instead.

25.18 CyclicGroup for Ag Groups

`AgWordsOps.CyclicGroup( D, n )`
`AgWordsOps.CyclicGroup( D, n, str )`

Let n be a nonnegative integer. `AgWordsOps.CyclicGroup` returns the cyclic group of order n.

Let n be a composite number with r prime factors. If no str is given, the names of the r generators are cn\1, ..., cn\r. Otherwise, the names of the r generators are <str>1, ..., strr, where str must be a string of letters, digits and the special symbol ``\_".

If the order n is a prime, the name of the generator is either cn or <str>.

```    gap> CyclicGroup( AgWords, 31 );
Group( c31 )
gap> AgWordsOps.CyclicGroup( AgWords, 5 * 5, "e" );
Group( e1, e2 ) ```

25.19 ElementaryAbelianGroup for Ag Groups

`AgWordsOps.ElementaryAbelianGroup( D, n )`
`AgWordsOps.ElementaryAbelianGroup( D, n, str )`

`AgWordsOps.ElementaryAbelianGroup` returns the elementary abelian group of order n, which must be a prime power.

Let n be a prime power pr. If no str is given the names of the r generators are mn\1, ..., mn\r. Otherwise the names of the r generators are <str>1, ..., strr, where str must be a string of letters, digits and the special symbol ``\_".

If the order n is a prime, the name of the generator is either mn or <str>.

```    gap> ElementaryAbelianGroup( AgWords, 31 );
Group( m31 )
gap> ElementaryAbelianGroup( AgWords, 31^2 );
Group( m961_1, m961_2 )
gap> AgWordsOps.ElementaryAbelianGroup( AgWords, 31^2, "e" );
Group( e1, e2 ) ```

25.20 DirectProduct for Ag Groups

`AgGroupOps.DirectProduct( L )`

L must be list of groups or pairs of group and name as described below. If not all groups are ag groups `GroupOps.DirectProduct` (see DirectProduct) is used in order to construct the direct product.

Let L be a list of ag groups <L> = [ U1, ..., Un ]. `AgGroupOps.DirectProduct` returns the direct product of all Ui as new ag group with collector.

If L is a pair `[ Ui, S ]` instead of a group Ui the generators of the direct product corresponding to Ui are named `Sj` for integers j starting with 1 up to the number of induced generators for Ui. If the group is cyclic of prime order the name is just `S`.

`AgGroupOps.DirectProduct` computes for each Ui its natural power-commutator presentation for an induced generating system of Ui.

Note that the arguments need no common parent group.

```    gap> z3 := CyclicGroup( AgWords, 3 );;
gap> g := AgGroupOps.DirectProduct( [ [z3, "a"], [z3, "b"] ] );
Group( a, b ) ```

25.21 WreathProduct for Ag Groups

`AgGroupOps.WreathProduct( G, H, α )`

If H and G are not both ag group `GroupOps.WreathProduct` (see WreathProduct) is used.

Let H and G be two ag group with possible different parent group and let α be a homomorphism H into a permutation group of degree d.

Let (g1, ..., gr) be an IGS of G, (h1, ..., hn) an IGS of H. The wreath product has a PAG system (b1, ..., bn, a11, ..., a1r, ad1, ..., adr) such that b1, ..., bn generate a subgroup isomorph to H and ai1, ..., air generate a subgroup isomorph to G for each i in {1, ..., r}. The names of b1, ..., bn are h1, ..., hn, the names of ai1, ..., air are ni\1, ..., ni\r.

`AgGroupOps.WreathProduct` uses the natural power-commutator presentations of H and G for induced generating system of H and G (see Thi87).

```    gap> s3 := Subgroup( s4, [ a, b ] );
Subgroup( s4, [ a, b ] )
gap> c2 := Subgroup( s4, [ a ] );
Subgroup( s4, [ a ] )
gap> r := RightCosets( s3, c2 );;
gap> S3 := Operation( s3, r, OnRight );
Group( (2,3), (1,2,3) )
gap> f := GroupHomomorphismByImages(s3,S3,[a,b],[(2,3),(1,2,3)]);
GroupHomomorphismByImages( Subgroup( s4, [ a, b ] ), Group( (2,3),
(1,2,3) ), [ a, b ], [ (2,3), (1,2,3) ] )
gap> WreathProduct( c2, s3, f );
Group( h1, h2, n1_1, n2_1, n3_1 ) ```

25.22 RightCoset for Ag Groups

`AgGroupOps.Coset( G )`

A coset C = G*x is represented as record with the following components.

`representative`:

contains the representative x.

`group`:

contains the group G.

`isDomain`:

is `true`.

`isRightCoset`:

is `true`.

`isFinite`:

is `true`.

`operations`:

contains the operations record `RightCosetAgGroupOps`.

`RightCosetAgGroupOps.<( C1, C2 )`

If C1 and C2 do not have a common group or if one argument is no coset then the functions uses `DomainOps.<` in order to compare C1 and C2. Note that this will compute the set of elements of C1 and C2.

If C1 and C2 have a common group then `AgGroupCosetOps.<` will use `SiftedAgWord` (see SiftedAgWord) and `ConjugateSubgroup` (see ConjugateSubgroup) in order to compare C1 and C2. It does not compute the set of elements of C1 and C2.

25.23 FpGroup for Ag Groups

`AgGroupOps.FpGroup( U )`
`AgGroupOps.FpGroup( U, str )`

`AgGroupOps.FpGroup` returns a finite presentation of an ag group U.

If no str is given, the abstract group generators have the same names as the generators of the ag group U. Otherwise they have names of the form `str` for integers i from 1 to the number of induced generators.

`AgGroupOps.FpGroup` computes the natural power-commutator presentation of an induced generating system of the finite polycyclic group U.

25.24 Ag Group Functions

The following functions either construct new parent ag group (see AgGroup and AgGroupFpGroup), test properties of parent ag groups (see IsConsistent and IsElementaryAbelianAgSeries) or change the collector (see ChangeCollector) but they do not compute subgroups. These functions are either described in general in chapter Groups or in Subgroups and Properties of Ag Groups for specialized functions.

25.25 AgGroup

`AgGroup( D )`

`AgGroup` converts a finite polycyclic group D into an ag group G. `G.bijection` is bound to isomorphism between G and D.

```    gap> S4p := Group( (1,2,3,4), (1,2) );
Group( (1,2,3,4), (1,2) )
gap> S4p.name := "S4_PERM";;
gap> S4a := AgGroup( S4p );
Group( g1, g2, g3, g4 )
gap> S4a.name := "S4_AG";;
gap> L := CompositionSeries( S4a );
[ S4_AG, Subgroup( S4_AG, [ g2, g3, g4 ] ),
Subgroup( S4_AG, [ g3, g4 ] ), Subgroup( S4_AG, [ g4 ] ),
Subgroup( S4_AG, [  ] ) ]
gap> List( L, x -> Image( S4a.bijection, x ) );
[ Subgroup( S4_PERM, [ (1,2), (1,3,2), (1,4)(2,3), (1,2)(3,4) ] ),
Subgroup( S4_PERM, [ (1,3,2), (1,4)(2,3), (1,2)(3,4) ] ),
Subgroup( S4_PERM, [ (1,4)(2,3), (1,2)(3,4) ] ),
Subgroup( S4_PERM, [ (1,2)(3,4) ] ), Subgroup( S4_PERM, [  ] ) ] ```

Note that the function will not work for finitely presented groups, see AgGroupFpGroup for details.

25.26 IsAgGroup

`IsAgGroup( obj )`

`IsAgGroup` returns `true` if obj, which can be an arbitrary object, is an ag group and `false` otherwise.

```    gap> IsAgGroup( s4 );
true
gap> IsAgGroup( a );
false ```

25.27 AgGroupFpGroup

`AgGroupFpGroup( F )`

`AgGroupFpGroup` returns an ag group isomorphic to a finitely presented finite polycyclic group F.

A finitely presented finite polycyclic group F must be a record with components `generators` and `relators`, such that `generators` is a list of abstract generators and `relators` a list of words in these generators describing a power-commutator or power-conjugate presentation.

Let g1, ..., gn be the generators of F. Then the words of `relators` must be the power relators gkek * wkk-1 and commutator relator Comm( gi, gj ) * wij-1 or conjugate relators gigj * wij-1 for all 1 ≤ k ≤ n and 1 ≤ j < i ≤ n, such that wkk are words in gk+1, ..., gn and wij are words in gj+1, ..., gn. It is possible to omit some of the commutator or conjugate relators. Pairs of generators without commutator or conjugate relator are assumed to commute.

The relative order ei of gi need not to be primes, but as all functions for ag groups need a PAG system, not only an AG system, you must refine the AG series using `RefinedAgSeries` (see RefinedAgSeries) in case some ei are composite numbers.

Note that it is not checked if the AG presentation is consistent. You can use `IsConsistent` (see IsConsistent) to test the consistency of a presentation. Inconsistent presentations may cause other ag group functions to return incorrect results.

Initially a collector from the left following the algorithm described in LS90 is used in order to collect elements of the ag group. This could be changed using `ChangeCollector` (see ChangeCollector).

Note that `AgGroup` will not work with finitely presented groups, you must use the function `AgGroupFpGroup` instead. As no checks are done you can construct an ag group with inconsistent presentation using `AgGroupFpGroup`.

25.28 IsConsistent

`IsConsistent( G )`
`IsConsistent( G, all )`

`IsConsistent` returns `true` if the finite polycyclic presentation of a parent group G is consistent and `false` otherwise.

If all is `true` then `G.inconsistencies` contains a list for pairs [ w1, w2 ] such that the words w1 and w2 are equal in G but have different normal forms.

Note that `IsConsistent` check and sets `G.isConsistent`.

```    gap> InfoAgGroup2 := Print;;
gap> x := AbstractGenerator( "x" );;
gap> y := AbstractGenerator( "y" );;
gap> z := AbstractGenerator( "z" );;
gap> G := AgGroupFpGroup( rec(
>       generators := [ x, y, z ],
>       relators   := [ x^2 / y, y^2 / z, z^2,
>                       Comm( y, x ) / ( y * z ),
>                       Comm( z, x ) / ( y * z )] ) );
Group( x, y, z )
gap> IsConsistent( G );
#I  IsConsistent: y * ( y * x ) <> ( y * y ) * x
false
gap> IsConsistent( G, true );
#I  IsConsistent: y * ( y * x ) <> ( y * y ) * x
#I  IsConsistent: z * ( z * x ) <> ( z * z ) * x
#I  IsConsistent: y * ( x * x ) <> ( y * x ) * x
#I  IsConsistent: z * ( x * x ) <> ( z * x ) * x
#I  IsConsistent: x * ( x * x ) <> ( x * x ) * x
false
gap> G.inconsistencies;
[ [ x, x*y ], [ x*z, x ], [ z, y ], [ y*z, y ], [ x*y, x ] ]
gap> InfoAgGroup2 := Ignore;; ```

25.29 IsElementaryAbelianAgSeries

`IsElementaryAbelianAgSeries( G )`

Let G be a parent group. `IsElementaryAbelianAgSeries` returns `true` if and only if the AG series of G is the refinement of an elementary abelian series of G.

The function sets `G.elementaryAbelianSeries` G in case of a `true` result. This component is described in ElementaryAbelianSeries.

```    gap> IsElementaryAbelianAgSeries( s4 );
true
gap> ElementaryAbelianSeries( s4 );
[ s4, Subgroup( s4, [ b, c, d ] ), Subgroup( s4, [ c, d ] ),
Subgroup( s4, [  ] ) ]
gap> CompositionSeries( s4 );
[ s4, Subgroup( s4, [ b, c, d ] ), Subgroup( s4, [ c, d ] ),
Subgroup( s4, [ d ] ), Subgroup( s4, [  ] ) ] ```

25.30 MatGroupAgGroup

`MatGroupAgGroup( U, M )`

Let U and M be two ag groups with a common parent group and let M be a elementary abelian group normalized by U. Then `MatGroupAgGroup` returns the matrix representation of U acting on M.

```    gap> v4 := AgSubgroup( s4, [ c, d ], true );
Subgroup( s4, [ c, d ] )
gap> a4 := AgSubgroup( s4, [ b, c, d ], true );
Subgroup( s4, [ b, c, d ] )
gap> MatGroupAgGroup( s4, v4 );
Group( [ [ Z(2)^0, Z(2)^0 ], [ 0*Z(2), Z(2)^0 ] ],
[ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, Z(2)^0 ] ] ) ```

25.31 PermGroupAgGroup

`PermGroupAgGroup( G, U )`

Let U be a subgroup of a ag group G. Then `PermGroupAgGroup` returns the permutation representation of G acting on the cosets of U.

```    gap> v4 := AgSubgroup( s4, [ s4.1, s4.4 ], true );
Subgroup( s4, [ a, d ] )
gap> PermGroupAgGroup( s4, v4 );
Group( (3,5)(4,6), (1,3,5)(2,4,6), (1,2)(3,4), (3,4)(5,6) ) ```

25.32 RefinedAgSeries

`RefinedAgSeries( G )`

`RefinedAgSeries` returns a new parent group isomorphic to a parent group G with a PAG series, if the ag group G has only an AG series.

Note that in the case that G has a PAG series, G is returned without any further action.

The names of the new generators are constructed as follows. Let (g1,..., gn) be the AG system of the ag group G and n(gi) the name of gi. If the relative order of gi is a prime, then n(gi) is the name of a new generator. If the relative order is a composite number with r prime factors, then there exist r new generators with names n(gi)\1, ..., n(gi)\r.

```    gap> c12 := AbstractGenerator( "c12" );;
gap> F := rec( generators := [ c12 ],
>              relators   := [ c12 ^ ( 2 * 2 * 3 ) ] );
rec(
generators := [ c12 ],
relators := [ c12^12 ] )
gap> G := AgGroupFpGroup( F );
#W  AgGroupFpGroup: composite index, use 'RefinedAgSeries'
Group( c12 )
gap> RefinedAgSeries( G );
Group( c121, c122, c123 ) ```

25.33 ChangeCollector

`ChangeCollector( G, name )`
`ChangeCollector( G, name, n )`

`ChangeCollector` changes the collector of a parent group G and all its subgroups. name is the name of the new collector. The following collectors are supported.

``single'' initializes a collector from the left following the algorithm described in LS90.

``triple'' initializes a collector from the left collecting with triples gi\gjr for j < i and r = 1, ..., n (see Bis89).

``quadruple'' initializes a collector from the left collecting with quadruples gis\gjr for j < i, r = 1, ..., n and s = 1, ..., n. Note that r and s have the same upper bound (see Bis89).

``combinatorial'' initializes a combinatorial collector from the left for a p-group G. In that case the commutator or conjugate relations of the G must be of the form gigj = wij or Comm( gi, gj ) = wij for 1 ≤ j < i ≤ n, such that wij are words in gi+1, ..., gn fulfilling the central weight condition (see HN80,Vau84). If these conditions are not fulfilled, the collector could not be initialized, a warning will be printed and collection will be done with the old collector.

For collectors which collect with tuples a maximal bound of those tuples is n, set to 5 by default.

25.34 The Prime Quotient Algorithm

The following sections describe the np-quotient functions. `PQuotient` allows to compute quotient of prime power order of finitely presented groups. For further references see HN80 and Vau84.

There is a C standalone version of the p-quotient algorithm, the ANU p-Quotient Program, which can be called from GAP3. For further information see chapter ANU Pq.

25.35 PQuotient

`PQuotient( G, p, cl )`
`PrimeQuotient( G, p, cl )`

`PQuotient` computes quotients of prime power order of finitely presented groups. G must be a group given by generators and relations. `PQuotient` expects G to be a record with the record fields `generators` and `relators`. The record field `generators` must be a list of abstract generators created by the function `AbstractGenerator` (see AbstractGenerator). The record field `relators` must be a list of words in the generators which are the relators of the group. p must be a prime. cl has to be an integer, which specifies that the quotient of prime power order computed by `PQuotient` is the largest p-quotient of G of class at most cl. `PQuotient` returns a record `Q`, the PQp record, which has, among others, the following record fields describing the p-quotient Q.

`generators`:

A list of abstract generators which generate Q.

`pcp` :

The internal power-commutator presentation for Q.

`dimensions`:

A list, where `dimensions[i]` is the dimension of the i-th factor in the lower exponent-p central series calculated by the p-quotient algorithm.

`prime`:

The integer p, which is a prime.

`definedby`:

A list which contains the definition of the k-th generator in the k-th place. There are three different types of entries, namely lists, positive and negative integers.
`[ j, i ]`:
the generator is defined to be the commutator of the j-th and the i-th element in `generators`.
`i`:
the generator is defined as the p-th power of the i-th element in `generators`.
`-i`:
the generator is defined as an image of the i-th generator in the finite presentation for G, consequently it must be a generator of weight 1.

`epimorphism`:

A list containing an image in Q of each generator of G. The image is either an integer `i` if it is the i-th element of `generators` of Q or an abstract word `w` if it is the abstract word `w` in the generators of Q.

An example of the computation of the largest quotient of class 4 of the group given by the finite presentation { x,y | x25/(x. y)5, [x,y]5, (xy)25 } .

```    # Define the group
gap> x := AbstractGenerator("x");;
gap> y := AbstractGenerator("y");;
gap> G := rec( generators := [x,y],
>              relators := [ x^25/(x*y)^5, Comm(x,y)^5, (x^y)^25] );
rec(
generators := [ x, y ],
relators :=
[ x^25*y^-1*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1*x^-1,
x^-1*y^-1*x*y*x^-1*y^-1*x*y*x^-1*y^-1*x*y*x^-1*y^-1*x*y*x^-1*y^-\
1*x*y, y^-1*x^25*y ] )

# Call pQuotient
gap> P := PQuotient( G, 5, 4 );
#I  PQuotient: class 1 : 2
#I  PQuotient: Runtime : 0
#I  PQuotient: class 2 : 2
#I  PQuotient: Runtime : 27
#I  PQuotient: class 3 : 2
#I  PQuotient: Runtime : 1437
#I  PQuotient: class 4 : 3
#I  PQuotient: Runtime : 1515
PQp( rec(
generators  := [ g1, g2, a3, a4, a6, a7, a11, a12, a14 ],
definedby   := [ -1, -2, [ 2, 1 ], 1, [ 3, 1 ], [ 3, 2 ],
[ 5, 1 ], [ 5, 2 ], [ 6, 2 ] ],
prime       := 5,
dimensions  := [ 2, 2, 2, 3 ],
epimorphism := [ 1, 2 ],
powerRelators := [ g1^5/(a4), g2^5/(a4^4), a3^5, a4^5, a6^5, a7^
5, a11^5, a12^5, a14^5 ],
commutatorRelators := [ Comm(g2,g1)/(a3), Comm(a3,g1)/(a6), Comm(a3\
,g2)/(a7), Comm(a6,g1)/(a11), Comm(a6,g2)/(a12), Comm(a7,g1)/(a12), Co\
mm(a7,g2)/(a14) ],
definingCommutators := [ [ 2, 1 ], [ 3, 1 ], [ 3, 2 ], [ 5, 1 ],
[ 5, 2 ], [ 6, 1 ], [ 6, 2 ] ] ) )```

The p-quotient algorithm returns a PQp record for the exponent-5 class 4 quotient. Note that instead of printing the PQp record `P` an equivalent representation is printed which can be read in to GAP3. See PQp for details.

The quotient defined by `P` has nine generators, `g1, g2, a3, a4, a6, a7,a11, a12, a14`, stored in the list `P.generators`. From `powerRelators` we can read off that `g1^5 =: a4` and `g2^5 = a4^4` and all other generators have trivial 5-th powers. From the list `commutatorRelators` we can read off the non-trivial commutator relations `Comm(g2,g1) =: a3`, `Comm(a3,g1) =: a6`, `Comm(a3,g2) =: a7`, `Comm(a6,g1) =: a11`,`Comm(a6,g2) =: a12`, `Comm(a7,g1) = a12` and `Comm(a7,g2) =: a14`. In this list `=:` denotes that the generator on the right hand side is defined as the left hand side. This information is given by the list `definedby`. The list `dimensions` shows that `P` is a class-4 quotient of order 52. 52. 52. 53 = 59. The epimorphism of `G` onto the quotient `P` is given by the map `x` `g1` and `y` `g2`.

25.36 Save

`Save( file, Q, N )`

`Save` saves the PQp record Q to the file file in such a way that the file can be read by GAP3. The name of the record in the file will be N. This differs from printing Q to a file in that the required abstract generators are also created in file.

```    gap> x := AbstractGenerator("x");;
gap> y := AbstractGenerator("y");;
gap> G := rec( generators := [x,y],
>              relators := [ x^25/(x*y)^5, Comm(x,y)^5, (x^y)^25] );;
gap> P := PQuotient( G, 5, 4 );;
#I  PQuotient: class 1 : 2
#I  PQuotient: Runtime : 0
#I  PQuotient: class 2 : 2
#I  PQuotient: Runtime : 27
#I  PQuotient: class 3 : 2
#I  PQuotient: Runtime : 78
#I  PQuotient: class 4 : 3
#I  PQuotient: Runtime : 156
gap> Save( "Quo54", P, "Q" );
gap> # The Unix command 'cat' in the next statement should be
gap> # replaced appropriately if you are working under a different
gap> # operating system.
gap> Exec( "cat Quo54" );
g1 := AbstractGenerator("g1");
g2 := AbstractGenerator("g2");
a3 := AbstractGenerator("a3");
a4 := AbstractGenerator("a4");
a6 := AbstractGenerator("a6");
a7 := AbstractGenerator("a7");
a11 := AbstractGenerator("a11");
a12 := AbstractGenerator("a12");
a14 := AbstractGenerator("a14");
Q := PQp( rec(
generators  := [ g1, g2, a3, a4, a6, a7, a11, a12, a14 ],
definedby   := [ -1, -2, [ 2, 1 ], 1, [ 3, 1 ], [ 3, 2 ],
[ 5, 1 ], [ 5, 2 ], [ 6, 2 ] ],
prime       := 5,
dimensions  := [ 2, 2, 2, 3 ],
epimorphism := [ 1, 2 ],
powerRelators := [ g1^5/(a4), g2^5/(a4^4), a3^5, a4^5, a6^5, a7^
5, a11^5, a12^5, a14^5 ],
commutatorRelators := [ Comm(g2,g1)/(a3), Comm(a3,g1)/(a6), Comm(a3\
,g2)/(a7), Comm(a6,g1)/(a11), Comm(a6,g2)/(a12), Comm(a7,g1)/(a12), Co\
mm(a7,g2)/(a14) ],
definingCommutators := [ [ 2, 1 ], [ 3, 1 ], [ 3, 2 ], [ 5, 1 ],
[ 5, 2 ], [ 6, 1 ], [ 6, 2 ] ] ) );```

25.37 PQp

`PQp( r )`

`PQp` takes as argument a record r containing all information necessary to restore a PQp record Q. A PQp record Q is printed as function call to `PQp` with an argument describing Q. This is necessary because the internal power-commutator representation cannot be printed. Therefore all information about Q is encoded in a record r and Q is printed as `PQp( <r> )`.

25.38 InitPQp

`InitPQp( n, p )`

`InitPQp` creates a PQp record for an elementary abelian group of rank n and of order <p>n for a prime p.

25.39 FirstClassPQp

`FirstClassPQp( G, p )`

`FirstClassPQp` returns a PQp record for the exponent-p class 1 quotient of G.

25.40 NextClassPQp

`NextClassPQp( G, P )`

Let P be the PQp record for the exponent-p class c quotient of G. `NextClassPQp` returns a PQp record for the class c+1 quotient of G, if such a quotient exists, and P otherwise. In latter case there exists a maximal p-quotient of G which has class c and this is indicated by a comment if `InfoPQ1` is set the `Print`.

25.41 Weight

`Weight( P, w )`

Let P be a PQp record and w a word in the generators of P. The function `Weight` returns the weight of w with respect to the lower exponent-p central series defined by P.

25.42 Factorization for PQp

`Factorization( P, w )`

Let P be a PQp record and w a word in the generators of P. The function `Factorization` returns a word in the weight 1 generators of P expressing w.

25.43 The Solvable Quotient Algorithm

The following sections describe the solvable quotient functions (or sq functions for short). `SolvableQuotient` allows to compute finite solvable quotients of finitely presented groups.

The solvable quotient algorithm tries to find solvable quotients of a given finitely presented group G. First it computes the commutator factor group Q, which must be finite. It then chooses a prime p and repeats the following three steps: (1) compute all irreducible modules of Q over GF(p), (2) for each module M compute (up to equivalence) all extensions of Q by M, (3) for each extension E check whether E is isomorphic to a factor group of G. As soon as a non-trivial extension of Q is found which is still isomorphic to a factor group of G the process is repeated.

25.44 SolvableQuotient

`SolvableQuotient( G, primes )`

Let G be a finitely presented group and primes a list of primes. `SolvableQuotient` tries to compute the largest finite solvable quotient Q of G, such that the prime decomposition of the order the derived subgroup Q' of Q only involves primes occuring in the list primes. The quotient Q is returned as finitely presented group. You can use `AgGroupFpGroup` (see AgGroupFpGroup) to convert the finitely presented group into a polycyclic one.

Note that the commutator factor group of G must be finite.

```    gap> f := FreeGroup( "a", "b", "c", "d" );;
gap> f4 := f / [ f.1^2, f.2^2, f.3^2, f.4^2, f.1*f.2*f.1*f.2*f.1*f.2,
>      f.2*f.3*f.2*f.3*f.2*f.3*f.2*f.3, f.3*f.4*f.3*f.4*f.3*f.4,
>      f.1^-1*f.3^-1*f.1*f.3, f.1^-1*f.4^-1*f.1*f.4,
>      f.2^-1*f.4^-1*f.2*f.4 ];
Group( a, b, c, d )
gap> InfoSQ1 := Ignore;;
gap> g := SolvableQuotient( f4,  );
Group( e1, e2, m3, m4 )
gap> Size(AgGroupFpGroup(g));
36
gap> g := SolvableQuotient( f4,  );
Group( e1, e2 )
gap> Size(AgGroupFpGroup(g));
4
gap> g := SolvableQuotient( f4, [2,3] );
Group( e1, e2, m3, m4, m5, m6, m7, m8, m9 )
gap> Size(AgGroupFpGroup(g));
1152 ```

Note that the order in which the primes occur in primes is important. If primes is the list [2,3] then in each step `SolvableQuotient` first tries a module over GF(2) and only if this fails a module over GF(3). Whereas if primes is the list [3,2] the function first tries to find a downward extension by a module over GF(3) before considering modules over GF(2).

`SolvableQuotient( G, n )`

Let G be a finitely presented group. `SolvableQuotient` attempts to compute a finite solvable quotient of G of order n.

Note that n must be divisible by the order of the commutator factor group of G, otherwise the function terminates with an error message telling you the order of the commutator factor group.

Note that a warning is printed if there does not exist a solvable quotient of order n. In this case the largest solvable quotient whose order divides n is returned.

Providing the order n or a multiple of the order makes the algorithm run much faster than providing only the primes which should be tested, because it can restrict the dimensions of modules it has to investigate. Thus if the order or a small enough multiple of it is known, `SolvableQuotient` should be called in this way to obtain a power conjugate presentation for the group.

```    gap> f := FreeGroup( "a", "b", "c", "d" );;
gap> f4 := f / [ f.1^2, f.2^2, f.3^2, f.4^2, f.1*f.2*f.1*f.2*f.1*f.2,
>       f.2*f.3*f.2*f.3*f.2*f.3*f.2*f.3, f.3*f.4*f.3*f.4*f.3*f.4,
>       f.1^-1*f.3^-1*f.1*f.3, f.1^-1*f.4^-1*f.1*f.4,
>       f.2^-1*f.4^-1*f.2*f.4 ];;
gap> g := SolvableQuotient( f4, 12 );
Group( e1, e2, m3 )
gap> Size(AgGroupFpGroup(g));
12
gap> g := SolvableQuotient( f4, 24 );
#W  largest quotient has order 2^2*3
Group( e1, e2, m3 )
gap> g := SolvableQuotient( f4, 2 );
Error, commutator factor group is of size 2^2 ```

`SolvableQuotient( G, l )`

If something is already known about the structure of the finite soluble quotient to be constructed then `SolvableQuotient` can be aided in its construction.

l must be a list of lists each of which is a list of integers occurring in pairs p, n.

`SolvableQuotient` first constructs the commutator factor group of G, it then tries to extend this group by modules over GF(p) of dimension at most n where p is a prime occurring in the first list of l. If n is zero no bound on the dimension of the module is imposed. For example, if l is [ [2,0,3,4], [5,0,2,0] ] then `SolvableQuotient` will try to extend the commutator factor group by a module over GF(2). If no such module exists all modules over GF(3) of dimension at most 4 are tested. If neither a GF(2) nor a GF(3) module extend `SolvableQuotient` terminates. Otherwise the algorithm tries to extend this new factor group with a GF(5) and then a GF(2) module.

Note that it is possible to influence the construction even more precisely by using the functions `InitSQ`, `ModulesSQ`, and `NextModuleSQ`. These functions allow you to interactively select the modules. See InitSQ, ModulesSQ, and NextModuleSQ for details.

Note that the ordering inside the lists of l is important. If l is the list [[2,0,3,0]] then `SolvableQuotient` will first try a module over GF(2) and attempt to construct an extension by a module over GF(3) only if the GF(2) extension fails, whereas in the case that l is the list [[3,0,2,0]] the function first attempts to extend with modules over GF(3) and then with modules over GF(2).

```    gap> f := FreeGroup( "a", "b", "c", "d" );;
gap> f4 := f / [ f.1^2, f.2^2, f.3^2, f.4^2, f.1*f.2*f.1*f.2*f.1*f.2,
>       f.2*f.3*f.2*f.3*f.2*f.3*f.2*f.3, f.3*f.4*f.3*f.4*f.3*f.4,
>       f.1^-1*f.3^-1*f.1*f.3, f.1^-1*f.4^-1*f.1*f.4,
>       f.2^-1*f.4^-1*f.2*f.4 ];;
gap> g := SolvableQuotient( f4, [[5,0],[2,0,3,0]] );
Group( e1, e2 )
gap> Size(AgGroupFpGroup(g));
4
gap> g := SolvableQuotient( f4, [[3,0],[2,0]] );
Group( e1, e2, m3, m4, m5, m6, m7, m8, m9 )
gap> Size(AgGroupFpGroup(g));
1152 ```

25.45 InitSQ

`InitSQ( G )`

Let G be a finitely presented group. `InitSQ` computes an SQ record for the commutator factor group of G. This record can be used to investigate finite solvable quotients of G .

Note that the commutator factor group of G must be finite otherwise an error message is printed.

```    gap> f := FreeGroup( "a", "b", "c", "d" );;
gap> f4 := f / [ f.1^2, f.2^2, f.3^2, f.4^2, f.1*f.2*f.1*f.2*f.1*f.2,
>       f.2*f.3*f.2*f.3*f.2*f.3*f.2*f.3, f.3*f.4*f.3*f.4*f.3*f.4,
>       f.1^-1*f.3^-1*f.1*f.3, f.1^-1*f.4^-1*f.1*f.4,
>       f.2^-1*f.4^-1*f.2*f.4 ];;
gap> s := InitSQ(f4);
<< solvable quotient of size 2^2 >> ```

25.46 ModulesSQ

`ModulesSQ( S, F )`
`ModulesSQ( S, F, d )`

Let S be an SQ record describing a finite solvable quotient Q of a finitely presented group G. `ModulesSQ` computes all irreducible representations of Q over the prime field F of dimension at most d. If d is zero or missing no restriction on the dimension is enforced.

```    gap> f := FreeGroup( "a", "b", "c", "d" );;
gap> f4 := f / [ f.1^2, f.2^2, f.3^2, f.4^2, f.1*f.2*f.1*f.2*f.1*f.2,
>       f.2*f.3*f.2*f.3*f.2*f.3*f.2*f.3, f.3*f.4*f.3*f.4*f.3*f.4,
>       f.1^-1*f.3^-1*f.1*f.3, f.1^-1*f.4^-1*f.1*f.4,
>       f.2^-1*f.4^-1*f.2*f.4 ];;
gap> s := InitSQ(f4);
<< solvable quotient of size 2^2 >>
gap> ModulesSQ( s, GF(2) );; ```

25.47 NextModuleSQ

`NextModuleSQ( s, M )`

Let S be an SQ record describing a finite solvable quotient Q of a finitely presented group G. `NextModuleSQ` tries to extend Q by the module M such that the extension is still a quotient of G

```    gap> f := FreeGroup( "a", "b", "c", "d" );;
gap> f4 := f / [ f.1^2, f.2^2, f.3^2, f.4^2, f.1*f.2*f.1*f.2*f.1*f.2,
>       f.2*f.3*f.2*f.3*f.2*f.3*f.2*f.3, f.3*f.4*f.3*f.4*f.3*f.4,
>       f.1^-1*f.3^-1*f.1*f.3, f.1^-1*f.4^-1*f.1*f.4,
>       f.2^-1*f.4^-1*f.2*f.4 ];;
gap> s := InitSQ(f4);
<< solvable quotient of size 2^2 >>
gap> m := ModulesSQ( s, GF(3) );;
gap> NextModuleSQ( s, m );
<< solvable quotient of size 2^2 >>
gap> NextModuleSQ( s, m );
<< solvable quotient of size 2^2*3 >>
gap> NextModuleSQ( s, m );
<< solvable quotient of size 2^2 >>
gap> NextModuleSQ( s, m );
<< solvable quotient of size 2^2*3 >> ```

25.48 Generating Systems of Ag Groups

For an ag group G there exists three different types of generating systems. The generating system in `G.generators` is a list of ag words generating the group G with the only condition that none of the ag words is the identity of G. If an induced generating system for G is known it is bound to `G.igs`, while an canonical generating system is bound to `G.cgs`. But as every canonical generating system is also an induced one, `G.cgs` and `G.igs` may contain the same system.

The functions `Cgs`, `Igs`, `Normalize`, `Normalized` and `IsNormalized` change or manipulate these systems. The following overview shows when to use this functions. For details see Cgs, Igs, Normalize, Normalized and IsNormalized.

`Igs` returns an induced generating system for G. If neither `G.igs` nor `G.cgs` are present, it uses `MergedIgs` (see MergedIgs) in order to construct an induced generating system from `G.generators`. In that case the induced generating system is bound to `G.igs`. If `G.cgs` but not `G.igs` is present, this is returned, as every canonical generating system is also an induced one. If `G.igs` is present this is returned.

`Cgs` returns a canonical generating system for G. If neither `G.igs` nor `G.cgs` are present, it uses `MergedCgs` (see MergedCgs) in order to construct a canonical generating system from `G.generators`. In that case the canonical generating system is bound to `G.cgs`. If `G.igs` but not `G.cgs` is present, this is normalized and bound to `G.cgs`, but `G.igs` is left unchanged. If `G.cgs` is present this is returned.

`Normalize` computes a canonical generating system, binds it to `G.cgs` and unbinds an induced generating bound to `G.igs`. `Normalized` normalizes a copy without changing the original ag group. This function should be preferred.

`IsNormalized` checks if an induced generating system is a canonical one and, if being canonical, binds it to `G.cgs` and unbinds `G.igs`. If `G.igs` is unbound `IsNormalized` computes a canonical generating system, binds it to `G.cgs` and returns `true`.

Most functions need an induced or canonical generating system, all function descriptions state clearly what is used, if this is relevant, see Exponents for example.

25.49 AgSubgroup

`AgSubgroup( U, gens, flag )`

Let U be an ag group with ag group G, gens be an induct or canonical generating system for a subgroup S of U and flag a boolean. Then `AgSubgroup` returns the record of an ag group representing this finite polycyclic group S as subgroup of G.

If flag is `true`, gens must be a canonical generating with respect to G. If flag is `false` gens must be a an induced generating with respect to G.

gens will be bound to `S.generators`. If flag is `true`, it is also bound to `S.cgs`, if it is `false`, gens is also bound to `S.igs`. Note that `AgSubgroup` does not copy gens.

Note that it is not check whether gens are an induced or canonical system. If gens fails to be one, all following computations with this group are most probably wrong.

```    gap> v4 := AgSubgroup( s4, [ c, d ], true );
Subgroup( s4, [ c, d ] ) ```

25.50 Cgs

`Cgs( U )`

`Cgs` returns a canonical generating system of U with respect to the parent group of U as list of ag words (see More about Ag Groups).

If `U.cgs` is bound, this is returned without any further action. If `U.igs` is bound, a copy of this component is normalized, bound to `U.cgs` and returned. If neither `U.igs` nor `U.cgs` are bound, a canonical generating system for U is computed using `MergedCgs` (see MergedCgs) and bound to `U.cgs`.

25.51 Igs

`Igs( U )`

`Igs` returns an induced generating system of U with respect to the parent group of U as list of ag words (see More about Ag Groups).

If `U.igs` is bound, this is returned without any further action. If `U.cgs` but not `U.igs` is bound, this is returned. If neither `U.igs` nor `U.cgs` are bound, an induced generating system for U is computed using `MergedIgs` (see MergedIgs) and bound to `U.igs`.

25.52 IsNormalized

`IsNormalized( U )`

`IsNormalized` returns `true` if no induced generating system but an canonical generating system for U is known.

If `U.cgs` but not `U.igs` is bound, `true` is returned. If neither `U.cgs` nor `U.igs` are bound, a canonical generating system is computed, bound to `U.cgs` and `true` is retuned. If `U.igs` is present, it is check, if `U.igs` is a canonical generating. If so, the canonical generating system is bound to `U.cgs` and `U.igs` is unbound.

25.53 Normalize

`Normalize( U )`

`Normalize` converts an induced generating system of an ag group U into a canonical one.

If `U.cgs` and not `U.igs` is bound, U is returned without any further action. If U contains both components `U.cgs` and `U.igs`, `U.igs` is unbound. If only `U.igs` but not `U.cgs` is bound the generators in `U.igs` are converted into a canonical generating and bound to `U.cgs`, while `U.igs` is unbound. If neither `U.igs` nor `U.cgs` are bound a canonical generating system is computed using `Cgs` (see Cgs).

25.54 Normalized

`Normalized( U )`

`Normalized` returns a normalized copy of an ag group U. For details see Normalize.

Note that this function does not alter the record of U and always returns a copy of U, even if U is already normalized.

25.55 MergedCgs

`MergedCgs( U, objs )`

Let U be an ag group with parent group G and objs be a list of elements and subgroups of U. Then `MergedCgs` returns the subgroup S of G generated by the elements and subgroups in the list objs. The subgroup S contains a canonical generating system bound to `S.cgs`.

As objs contains only elements and subgroups of U, the subgroup S is not only a subgroup of G but also of U. Its parent group is nevertheless G and `MergedCgs` computes a canonical generating system of S with respect to G.

If subgroups of S are known at least the largest should be an element of objs, because `MergedCgs` is much faster in such cases.

Note that this function may return a wrong subgroup, if the elements of objs do not belong to U. See also Generating Systems of Ag Groups for differences between canonical and induced generating systems.

```    gap> d8 := MergedCgs( s4, [ a*c, c ] );
Subgroup( s4, [ a, c, d ] )
gap> MergedCgs( s4, [ a*b*c*d, d8 ] );
s4
gap> v4 := MergedCgs( d8, [ c*d, c ] );
Subgroup( s4, [ c, d ] ) ```

25.56 MergedIgs

`MergedIgs( U, S, gens, normalize )`

Let U and S be ag groups with a common parent group G such that S is a subgroup of U. Let gens be a list of elements of U. Then `MergedIgs` returns the subgroup K of G generated by S and gens.

As gens contains only elements of U, the subgroup K is not only a subgroup of G but also of U. Its parent group is nevertheless G and `MergedIgs` computes a induced generating system of S with respect to G.

If normalize is `true`, a canonical generating system for K is computed and bound to `K.cgs`. If normalize is `false` only an induced generating system is computed and bound to `K.igs` or `K.cgs`. If no subgroup S is known, `rec()` can be given instead.

Note that U must be an ag group which contains S and gens.

25.57 Factor Groups of Ag Groups

It is possible to deal with factor groups of ag groups in three different ways. If an ag group G and a normal subgroup N of G is given, you can construct a new polycyclic presentation for F=G/N using `FactorGroup`. You can apply all functions for ag groups to that new parent group F and even switch between G and F using the homomorphisms returned by `NaturalHomomorphism`. See FactorGroup for more information on that kind of factor groups.

But if you are only interested in an easy way to test a property or an easy way to calculate a subgroup of a factor group, the first approach might be too slow, as it involves the construction of a new polycyclic presentation for the factor group together with the creation of a new collector for that factor group. In that case you can use `CollectorlessFactorGroup` in order to construct a new ag group without initializing a new collector but using records faking ag words instead. But now multiplication is still done in G and the words must be canonicalized with respect to N, so that multiplication in this group is rather slow. However if you for instance want to check if a chief factor, which is not part of the AG series, is central this may be faster then constructing a new collector. But generally `FactorGroup` should be used.

The third possibility works only for `Exponents` (see Exponents) and `SiftedAgWord` (see SiftedAgWord). If you want to compute the action of G on a factor M/N then you can pass M/N as factor group argument using M `mod` N or `FactorArg` (see FactorArg).

25.58 FactorGroup for AgGroups

`AgGroupOps.FactorGroup( U, N )`

Let N and U be ag groups with a common parent group, such that N is a normal subgroup of U. Let H be the factor group <U> / N. `FactorGroup` returns the finite polycyclic group H as new parent group.

If the ag group U is not a parent group or if N is not an element of the AG series of U (see IsElementAgSeries), then `FactorGroup` constructs a new polycyclic presentation and collector for the factor group using both `FpGroup` (see FpGroup for Ag Groups) and `AgGroupFpGroup` (see AgGroupFpGroup). Otherwise `FactorGroup` copies the old collector of U and cuts of the tails which lie in N.

Note that N must be a normal subgroup of U. You should keep in mind, that although the new generators and the old ones may have the same names, they cannot be multiplitied as they are elements of different groups. The only way to transfer information back and forth is to use the homomorphisms returned by `NaturalHomomorphism` (see FactorGroup).

```    gap> c2 := Subgroup( s4, [ d ] );
Subgroup( s4, [ d ] )
gap> d8 := Subgroup( s4, [ a, c, d ] );
Subgroup( s4, [ a, c, d ] )
gap> v4 := FactorGroup( d8, c2 );
Group( g1, g2 )
gap> v4.2 ^ v4.1;
g2
gap> d8 := Subgroup( s4, [ a, c, d ] );
Subgroup( s4, [ a, c, d ] )
gap> d8.2^d8.1;
c*d ```

25.59 CollectorlessFactorGroup

`CollectorlessFactorgroup( G, N )`

`CollectorlessFactorgroup` constructs the factorgroup F = G/N without initializing a new collector. The elements of F are records faking ag words.

Each element f of F contains the following components.

`representative`:

a canonical representative d in G for f.

`isFactorGroupElement` contains `true`.

`info`:

a record containing information about the factor group.

`operations`:

the operations record `FactorGroupAgWordsOps`.

25.60 FactorArg

`FactorArg( U, N )`

Let N be a normal subgroup of an ag group U. Then `FactorArg` returns a record with the following components with can be used as argument for `Exponents`.

`isFactorArg`:

is `true`.

`factorNum`:

contains U.

`factorDen`:

contains N.

`identity`:

contains the identity of U.

`generators`:

contains a list of those induced generators ui of U of depth di such that no induced generator in N has depth di.

`operations`:

contains the operations record `FactorArgOps`.

Note that `FactorArg` is bound to `AgGroupOps.mod`.

```    gap> d8 := Subgroup( s4, [ a, c, d ] );
Subgroup( s4, [ a, c, d ] )
gap> c2 := Subgroup( s4, [ d ] );
Subgroup( s4, [ d ] )
gap> M := d8 mod c2;;
gap> d8.1 * d8.2 * d8.3;
a*c*d
gap> Exponents( M, last );
[ 1, 1 ]
gap> d8 := AgSubgroup( s4, [ a*c, c, d ], false );
Subgroup( s4, [ a*c, c, d ] )
gap> M := d8 mod c2;;
gap> Exponents( M, a*c*d );
[ 1, 0 ] ```

25.61 Subgroups and Properties of Ag Groups

The subgroup functions compute subgroups or series of subgroups from given ag groups, e.g. `PRump` (see PRump) or `ElementaryAbelianSeries` (see ElementaryAbelianSeries). They return group records described in Group Records and Ag Group Records for the computed subgroups.

All the following functions only work for ag groups. Subgroup functions which work for various types of groups are described in Subgroups. Properties and property tests which work for various types of groups are described in Properties and Property Tests.

25.62 CompositionSubgroup

`CompositionSubgroup( G, i )`

`CompositionSubgroup` returns the i.th subgroup of the AG series of an ag group G.

Let (g1, ..., gn) be an induced generating system of G with respect to the parent group of G. Then the i.th composition subgroup S of the AG series is generated by (gi, ..., gn).

```    gap> CompositionSubgroup( s4, 2 );
Subgroup( s4, [ b, c, d ] )
gap> CompositionSubgroup( s4, 4 );
Subgroup( s4, [ d ] )
gap> CompositionSubgroup( s4, 5 );
Subgroup( s4, [  ] ) ```

25.63 HallSubgroup

`HallSubgroup( G, n )`
`HallSubgroup( G, L )`

Let G be an ag group. Then `HallSubgroup` returns a π-Hall-subgroup of G for the set π of all prime divisors of the integer n or the join π of all prime divisors of the integers of L.

The Hall-subgroup is constructed using Glasby's algorithm (see Gla87), which descends along an elementary abelian series for G and constructs complements in the coprime case (see CoprimeComplement). If no such series is known for G the function uses `ElementaryAbelianSeries` (see ElementaryAbelianSeries) in order to construct such a series for G.

```    gap> HallSubgroup( s4, 2 );
Subgroup( s4, [ a, c, d ] )
gap> HallSubgroup( s4, [ 3 ] );
Subgroup( s4, [ b ] )
gap> z5 := CyclicGroup( AgWords, 5 );
Group( c5 )
gap> DirectProduct( s4, z5 );
Group( a1, a2, a3, a4, b )
gap> HallSubgroup( last, [ 5, 3 ] );
Subgroup( Group( a1, a2, a3, a4, b ), [ a2, b ] ) ```

25.64 PRump

`PRump( G, p )`

`PRump` returns the p-rump of an ag group G for a prime p.

The p-rump of a group G is the normal closure under G of the subgroup generated by the commutators and p.th powers of the generators of G.

```    gap> PRump( s4, 2 );
Subgroup( s4, [ b, c, d ] )
gap> PRump( s4, 3 );
s4 ```

25.65 RefinedSubnormalSeries

`RefinedSubnormalSeries( L )`

Let L be a list of ag groups G1, ..., Gn, such that Gi+1 is a normal subgroup of Gi. Then the function computes a composition series H1 = G1, ..., Hm = Gn which refines the given subnormal series L and has cyclic factors of prime order (see also SubnormalSeries).

```    gap> v4 := Subgroup( s4, [ c, d ] );
Subgroup( s4, [ c, d ] )
gap> T := TrivialSubgroup( s4 );
Subgroup( s4, [  ] )
gap> RefinedSubnormalSeries( [ s4, v4, T ] );
[ s4, Subgroup( s4, [ b, c, d ] ), Subgroup( s4, [ c, d ] ),
Subgroup( s4, [ d ] ), Subgroup( s4, [  ] ) ] ```

25.66 SylowComplements

`SylowComplements( U )`

`SylowComplements` returns a Sylow complement system of U. This system S is represented as a record with at least the components `S.primes` and `S.sylowComplements`, additionally there may be a component `S.sylowSubgroups` (see SylowSystem).

`primes`:

A list of all prime divisors of the group order of U.

`sylowComplements`:

contains a list of Sylow complements for all primes in `S.primes`, so that if the i.th element of `S.primes` is p, then the i.th element of `sylowComplements` is a Sylow-p-complement of U.

`sylowSubgroups`:

contains a list of Sylow subgroups for all primes in `S.primes`, such that if the i.th element of `S.primes` is p, then the i.th element of `S.sylowSubgroups` is a Sylow-p-subgroup of U.

`SylowComplements` uses `HallSubgroup` (see HallSubgroup) in order to compute the various Sylow complements of U, if no Sylow system is known for U. If a Sylow system { S1, ... , Sn } is known, `SylowComplements` computes the various Hall subgroups Hi using the fact that Hi is the product of all Sj except Si.

`SylowComplements` sets and checks `U.sylowSystem`.

```    gap> SylowComplements( s4 );
rec(
primes := [ 2, 3 ],
sylowComplements :=
[ Subgroup( s4, [ b ] ), Subgroup( s4, [ a, c, d ] ) ] ) ```

25.67 SylowSystem

`SylowSystem( U )`

`SylowSystem` returns a Sylow system { S1, ... , Sn } of an ag group U. The system S is represented as a record with at least the components `S.primes` and `S.sylowSubgroups`, additionally there may be a component `S.sylowComplements`, see SylowComplements for information about this addtional component.

`primes`:

A list of all prime divisors of the group order of U.

`sylowComplements`:

contains a list of Sylow complements for all primes in `S.primes`, so that if the i.th element of `S.primes` is p, then the i.th element of `sylowComplements` is a Sylow-p-complement of U.

`sylowSubgroups`:

contains a list of Sylow subgroups for all primes in `S.primes`, such that if the i.th element of `S.primes` is p, then the i.th element of `S.sylowSubgroups` is a Sylow-p-subgroup of U.

A Sylow system of a group U is a system of Sylow subgroups Si for each prime divisor of the group order of U such that Si * Sj = Sj * Si is fulfilled for each pair i,j.

`SylowSystem` uses `SylowComplements` (see SylowSystem) in order to compute the various Sylow complements Hi of U. Then the Sylow system is constructed using the fact that the intersection Si of all Sylow complements Hj except Hi is a Sylow subgroup and that all these subgroups Si form a Sylow system of U. See Gla87.

`SylowSystem` sets and checks `S.sylowSystem`.

```    gap> z5 := CyclicGroup( AgWords, 5 );
Group( c5 )
gap> D := DirectProduct( z5, s4 );
Group( a, b1, b2, b3, b4 )
gap> D.name := "z5Xs4";;
gap> SylowSystem( D );
rec(
primes := [ 2, 3, 5 ],
sylowComplements :=
[ Subgroup( z5Xs4, [ a, b2 ] ), Subgroup( z5Xs4, [ a, b1, b3, b4
] ), Subgroup( z5Xs4, [ b1, b2, b3, b4 ] ) ],
sylowSubgroups :=
[ Subgroup( z5Xs4, [ b1, b3, b4 ] ), Subgroup( z5Xs4, [ b2 ] ),
Subgroup( z5Xs4, [ a ] ) ] ) ```

25.68 SystemNormalizer

`SystemNormalizer( G )`

`SystemNormalizer` returns the system normalizer of a Sylow system of the group G.

The system normalizer of a Sylow system is the intersection of all normalizers of subgroups in the Sylow system in G.

```    gap> SystemNormalizer( s4 );
Subgroup( s4, [ a ] )
gap> SystemNormalizer( D );
Subgroup( z5Xs4, [ a, b1 ] )```

25.69 MinimalGeneratingSet

`MinimalGeneratingSet( G )`

Let G be an ag group. Then `MinimalGeneratingSet` returns a subset L of G of minimal cardinality with the property that L generates G.

```    gap> l := MinimalGeneratingSet(s4);
[ b, a*c*d ]
gap> s4 = Subgroup( s4, l );
true ```

25.70 IsElementAgSeries

`IsElementAgSeries( U )`

`IsElementAgSeries` returns `true` if the ag group U is part of the AG series of the parent group G of U and `false` otherwise.

25.71 IsPNilpotent

`IsPNilpotent( U, p )`

`IsPNilpotent` returns `true`, if the ag group U is p-nilpotent for the prime p, and `false` otherwise.

`IsPNilpotent` uses Glasby's p-nilpotency test (see Gla87).

```    gap> IsPNilpotent( s4, 2 );
false
gap> s3 := Subgroup( s4, [ a, b ] );
Subgroup( s4, [ a, b ] )
gap> IsPNilpotent( s3, 2 );
true
gap> IsPNilpotent( s3, 3 );
false ```

25.72 NumberConjugacyClasses

`NumberConjugacyClasses( H )`

This functions computes the number of conjugacy classes of elements of a group H.

The function uses an algorithm that steps down an elementary abelian series of the parent group of H and computes the number of conjugacy classes using the same method as `AgGroupOps.ConjugacyClasses` does, up to the last factor group. In the last step the Cauchy-Frobenius-Burnside lemma is used.

This algorithm is especially designed to supply at least the number of conjugacy classes of H, whenever `ConjugacyClasses` fails because of storage reasons. So one would rather use this function if the last normal subgroup of the elementary abelian series is too big to be dealt with `ConjugacyClasses`.

`NumberConjugacyClasses( U, H )`

This version of the call to `NumberConjugacyClasses` computes the number of conjugacy classes of H under the operation of U. Thus for the operation to be well defined, U must be a subgroup of the normalizer of H in their common parent group.

```    gap> a4 := DerivedSubgroup(s4);;
gap> NumberConjugacyClasses( s4 );
5
gap> NumberConjugacyClasses( a4, s4 );
6
gap> NumberConjugacyClasses( a4 );
4
gap> NumberConjugacyClasses( s4, a4 );
3 ```

25.73 Exponents

`Exponents( U, u )`
`Exponents( U, u, F )`

`Exponents` returns the exponent vector of an ag word u with respect to an induced generating system of U as list of integers if no field F is given. Otherwise the product of the exponent vector and `F.one` is returned. Note that u must be an element of U.

Let (u1, ..., ur) be an induced generating system of U. Then u can be uniquely written as u1ν1* ...* urνr for integer νi. The exponent vector of u is [ν1, ..., νr].

`Exponents` allows factor group arguments. See Factor Groups of Ag Groups for details.

Note that `Exponents` adds a record component `U.shiftInfo`. This entry is used by subsequent calls with the same ag group in order to speed up computation. If you ever change the component `U.igs` by hand, not using `Normalize`, you must unbind the component `U.shiftInfo`, otherwise all following results of `Exponents` will be corrupted. In case U is a parent group you can use `ExponentsAgWord` (see ExponentsAgWord), which is slightly faster but requires a parent group U.

Note that you you may get a weird error message if u is no element of U. So it is strictly required that u is an element of U.

Note that `Exponents` uses `ExponentsAgWord` but not `ExponentAgWord`, so for records that mimic agwords `Exponents` may be used in `ExponentAgWord`.

```    gap> v4 := AgSubgroup( s4, [ c, d ], true );
Subgroup( s4, [ c, d ] )
gap> Exponents( v4, c * d );
[ 1, 1 ]
gap> Exponents( s4 mod v4, a * b^2 * c * d );
[ 1, 2 ] ```

25.74 FactorsAgGroup

`FactorsAgGroup( U )`

`FactorsAgGroup` returns the factorization of the group order of an ag group U as list of positive integers.

Note that it is faster to use `FactorsAgGroup` than to use `Factors` and `Size`.

```    gap> v4 := Subgroup( s4, [ c, d ] );;
gap> FactorsAgGroup( s4 );
[ 2, 2, 2, 3 ]
gap> Factors( Size( s4 ) );
[ 2, 2, 2, 3 ] ```

25.75 MaximalElement

`MaximalElement( U )`

`MaximalElement` returns the ag word in U with maximal exponent vector.

Let G be the parent group of U with canonical generating system (g1, ..., gn) and let (u1, ..., um) be the canonical generating system of U, di is the depth of ui with respect to G. Then an ag word u =g1ν1* ...* gnνn∈ U is returned such that i=1m νdi is maximal.

25.76 Orbitalgorithms of Ag Groups

The functions `Orbit` (see Orbit) and `Stabilizer` (see Stabilizer and Stabilizer for Ag Groups) compute the orbit and stabilizer of an ag group acting on a domain.

`AgOrbitStabilizer` (see AgOrbitStabilizer) computes the orbit and stabilizer in case that a compatible homomorphism into a group H exists, such that the action of H on the domain is more efficient than the operation of the ag group; for example, if an ag group acts linearly on a vector space, the operation can by described using matrices.

The functions `AffineOperation` (see AffineOperation) and `LinearOperation` (see LinearOperation) compute matrix groups describing the affine or linear action of an ag group on a vector space.

25.77 AffineOperation

`AffineOperation( U, V, φ, τ )`

Let U be an ag group with an induced generating system u1, ..., um and let V be a vector space with base (o1, ..., on). Further U should act affinely on V. So if v is an element of V and u is an element of U, then vu = vu + xu, such that the function which maps v to vu is linear and xu is an element of V. These actions are given by the functions φ and τ as follows. <φ>( v, u) must return the representation of vu with respect to the base (o1, ..., on) as sequence of finite field elements. <τ>( u ) must return the representation of xu in the base (o1, ..., on) as sequence of finite field elements. If these conditions are fulfilled, `AffineOperation` returns a matrix group M describing this action.

Note that `M.images` contains a list of matrices mi, such that mi describes the action of ui and mi is of the form

(
 Lui 0 xui 1
),

where Lu is the matrix which describes the linear operation v∈ V→ vu.

```    gap> v4 := AgSubgroup( s4, [ c, d ], true );
Subgroup( s4, [ c, d ] )
gap> v4.field := GF( 2 );
GF(2)
gap> phi := function( v, g )
>      return Exponents( v4, v^g, v4.field );
>    end;
function ( v, g ) ... end
gap> tau := g -> Exponents( v4, v4.identity, v4.field );
function ( g ) ... end
gap> V := rec( base := [ c, d ], isDomain := true );
rec(
base := [ c, d ],
isDomain := true )
gap> AffineOperation( s4, V, phi, tau );
Group( [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, 0*Z(2) ],
[ 0*Z(2), 0*Z(2), Z(2)^0 ] ],
[ [ 0*Z(2), Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, 0*Z(2) ],
[ 0*Z(2), 0*Z(2), Z(2)^0 ] ] ) ```

25.78 AgOrbitStabilizer

`AgOrbitStabilizer( U, gens, ω )`
`AgOrbitStabilizer( U, gens, ω, f )`

Let U be an ag group acting on a set Ω. Let ω be an element of Ω. Then `AgOrbitStabilizer` returns the point-stabilizer of ω in the group U and the orbit of ω under this group. The stabilizer and orbit are returned as record R with components `R.stabilizer` and `R.orbit`. `R.stabilizer` is the point-stabilizer of ω. `R.orbit` is the list of the elements of <ω> U .

Let (u1, ..., un) be an induced generating system of U and gens be a list h1, ..., hn of generators of a group H, such that the map ui→ hi extends to an homomorphism α from U to H, which is compatible with the action of G and H on Ω, such that g∈ StabU( ω ) if and only if gα∈ StabH( ω ). If f is missing `OnRight` is assumed, a typical application of this function being the linear action of U on an vector space. If f is `OnPoints` then `^` is used as operation of H on Ω. Otherwise f must be a function, which takes two arguments, the first one must be a point p of Ω and the second an element h of H and which returns p h.

```    gap> AgOrbitStabilizer( s4, [a,b,c,d], d, OnPoints );
rec(
stabilizer := Subgroup( s4, [ a, c, d ] ),
orbit := [ d, c*d, c ] ) ```

25.79 LinearOperation

`LinearOperation( U, V, φ )`

Let U be an ag group with an induced generating system u1, ..., um and V a vector space with base (o1, ..., on). U must act linearly on V. Let v be an element of V, u be an element of U. The action of U on V should be given as follows. If vu = a1*o1+ ... +an*on, then the function <φ>( v, u ) must return (a1, ..., an) as list of finite field elements. If these condition are fulfilled, `LinearOperation` returns a matrix group M describing this action.

Note that `M.images` is bound to a list of matrices mi, such that mi describes the action of ui.

```    gap> v4 := AgSubgroup( s4, [ c, d ], true );
Subgroup( s4, [ c, d ] )
gap> v4.field := GF( 2 );
GF(2)
gap> V := rec( base := [ c, d ], isDomain := true );
rec(
base := [ c, d ],
isDomain := true )
gap> phi := function( v, g )
>      return Exponents( v4, v^g, v4.field );
>    end;
function ( v, g ) ... end
gap> LinearOperation( s4, V, phi );
Group( [ [ Z(2)^0, Z(2)^0 ], [ 0*Z(2), Z(2)^0 ] ],
[ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, Z(2)^0 ] ] ) ```

25.80 Intersections of Ag Groups

There are two kind of intersection algorithms. Whenever the product of two subgroups is a subgroup, a generalized Zassenhaus algorithm can be used in order to compute the intersection and sum (see GS90). In case one subgroup is a normalized by the other, an element of the sum can easyly be decomposed. The functions `IntersectionSumAgGroup` (see IntersectionSumAgGroup), `NormalIntersection` (see NormalIntersection ), `SumFactorizationFunctionAgGroup` (see SumFactorizationFunctionAgGroup) and `SumAgGroup` (see SumAgGroup) should be used in such cases.

These functions are faster than the general function `Intersection` (see Intersection and Intersection for Ag Groups), which can compute the intersection of two subgroups even if their product is no subgroup.

25.81 ExtendedIntersectionSumAgGroup

`ExtendedIntersectionSumAgGroup( V, W )`

Let V and W be ag groups with a common parent group, such that <W> ≤ N(V). Then <V> * W is a subgroup and `ExtendedIntersectionSumAgGroup` returns the intersection and the sum of V and W. The information about these groups is returned as a record with the components `intersection`, `sum` and the additional information `leftSide` and `rightSide`.

`intersection`:

is bound to the intersection <W> ∩ V.

`sum`:

is bound to the sum <V> * W.

`leftSide`:

is lists of ag words, see below.

`rightSide`:

is lists of agwords, see below.

The function uses the Zassenhaus sum-intersection algorithm. Let V be generated by v1, ..., va, W be generated by w1, ..., wb. Then the matrix

(
 v1 1 ⋅ ⋅ va 1 w1 w1 ⋅ ⋅ wb wb
)

is echelonized by using the sifting algorithm to produce the following matrix

(
 l1 k1 ⋅ ⋅ lc kc 1 kc+1 ⋅ ⋅ 1 ka+b
).

Then l1, ..., lc is a generating sequence for the sum, while the sequence kc+1, ..., ka+b is is a generating sequence for the intersection. `leftSide` is bound to a list, such that the i.th list element is lj, if there exists a j, such that lj has depth i, and `IdAgWord` otherwise. `rightSide` is bound to a list, such that the i.th list element is kj, if there exists a j less than c+1, such that kj has depth i, and `IdAgWord` otherwise. See also SumFactorizationFunctionAgGroup.

Note that this functions returns an incorrect result if <W> \not ≤ N(V).

```    gap> v4_1 := AgSubgroup( s4, [ a*b, c ], true );
Subgroup( s4, [ a*b, c ] )
gap> v4_2 := AgSubgroup( s4, [ c, d ], true );
Subgroup( s4, [ c, d ] )
gap> ExtendedIntersectionSumAgGroup( v4_1, v4_2 );
rec(
leftSide := [ a*b, IdAgWord, c, d ],
rightSide := [ IdAgWord, IdAgWord, c, d ],
sum := Subgroup( s4, [ a*b, c, d ] ),
intersection := Subgroup( s4, [ c ] ) ) ```

25.82 IntersectionSumAgGroup

`IntersectionSumAgGroup( V, W )`

Let V and W be ag groups with a common parent group, such that <W> ≤ N (V). Then <V> * W is a subgroup and `IntersectionSumAgGroup` returns the intersection and the sum of V and W as record R with components `R.intersection` and `R.sum`.

Note that this functions returns an incorrect result if <W> \not ≤ N(V).

```    gap> d8_1 := AgSubgroup( s4, [ a, c, d ], true );
Subgroup( s4, [ a, c, d ] )
gap> d8_2 := AgSubgroup( s4, [ a*b, c, d ], true );
Subgroup( s4, [ a*b, c, d ] )
gap> IntersectionSumAgGroup( d8_1, d8_2 );
rec(
sum := Group( a*b, b^2, c, d ),
intersection := Subgroup( s4, [ c, d ] ) ) ```

25.83 SumAgGroup

`SumAgGroup( V, W )`

Let V and W be ag groups with a common parent group, such that <W> ≤ N (V). Then <V> * W is a subgroup and `SumAgGroup` returns <V> * W.

The function uses the Zassenhaus sum-intersection algorithm (see GS90).

Note that this functions returns an incorrect result if <W> \not ≤ N(V).

```    gap> d8_1 := Subgroup( s4, [ a, c, d ] );
Subgroup( s4, [ a, c, d ] )
gap> d8_2 := Subgroup( s4, [ a*b, c, d ] );
Subgroup( s4, [ a*b, c, d ] )
gap> SumAgGroup( d8_1, d8_2 );
Group( a*b, b^2, c, d ) ```

25.84 SumFactorizationFunctionAgGroup

`SumFactorizationFunctionAgGroup( U, N )`

Let U and N be ag group with a common parent group such that U normalizes N. Then the function returns a record R with the following components.

`intersection`:

is bound to the intersection <U> ∩ N.

`sum`:

is bound to the sum <U> * N.

`factorization`:

is bound to function, which takes an element g of <U> * N and returns the factorization of g in an element u of U and n of N, such that g = u * n. This factorization is returned as record r with components `r.u` and `r.n`, where `r.u` is bound to the ag word u, `r.n` to the ag word n.

Note that N must be a normal subgroup of <U> * N, it is not sufficient that <U> * N = N * U.

```    gap> v4 := AgSubgroup( s4, [ a*b, c ], true );
Subgroup( s4, [ a*b, c ] )
gap> a4 := AgSubgroup( s4, [ b, c, d ], true );
Subgroup( s4, [ b, c, d ] )
gap> sd := SumFactorizationFunctionAgGroup;
function ( U, N ) ... end
gap> sd := SumFactorizationFunctionAgGroup( v4, a4 );
rec(
sum := Group( a*b, b, c, d ),
intersection := Subgroup( s4, [ c ] ),
factorization := function ( un ) ... end )
gap> sd.factorization( a*b*c*d );
rec(
u := a*b*c,
n := d )
gap> sd.factorization( a*b^2*c*d );
rec(
u := a*b*c,
n := b*c ) ```

25.85 One Cohomology Group

Let G be a finite group, M a normal p-elementary abelian subgroup of G. Then the group of one coboundaries B1( G/M, M ) is defined as

 B1( G/M, M ) = { γ : G/M → M ; ∃ m∈ M∀ g∈ G : γ( gM ) = (m-1)g . m }

and is a Zp-vector space. The group of cocycles Z1( G/M, M ) is defined as

 Z1( G/M, M ) = { γ : G/M → M ; ∀ g1, g2∈ G : γ(g1M . g2M ) = γ(g1M)g2 . γ(g2M) }

and is also a Zp-vector space.

Let α be the isomorphism of M into a row vector space W and (g1, ..., gl) representatives for a generating set of G/M. Then there exists a monomorphism β of Z1( G/M, M ) in the l-fold direct sum of W, such that β( γ ) = ( α( γ( g1M ) ), ..., α( γ( glM ) ) ) for every γ∈ Z1( G/M, M ).

`OneCoboundaries` (see OneCoboundaries) and `OneCocycles` (see OneCocycles) compute the group of one coboundaries and one cocyles given a ag group G and a elementary abelian normal subgroup M. If `Info1Coh1`, `Info1Coh2` and `Info1Coh3` are set to `Print` information about the computation is given.

25.86 OneCoboundaries

`OneCoboundaries( G, M )`

Let M be a normal p-elementary abelian subgroup of G. Then `OneCoboundaries` computes the vector space V = β( B1( G/M, M ) ), which is isomorphic to the group of one coboundaries B1( G, M ) as described in One Cohomology Group. The functions returns a record C with the following components.

`oneCoboundaries`:

contains the vector space V.

`generators`:

contains representatives (g1, ..., gl) for the canonical generating system of <G> / M

`cocycleToList`:

contains a functions which takes an element v of V as argument and returns a list [ n1, ..., nl ], where ni is an element of M, such that ni = ( β-1( v ) )( gi M ).

`listToCocycles`:

is the inverse of `cocycleToList`.

`OneCoboundaries( G, α, M )`

In that form `OneCoboundaries` computes the one coboundaries in the semidirect product of G and M where G acts on M using α (see SemidirectProduct).

```    gap> s4xc2 := DirectProduct( s4, CyclicGroup( AgWords, 2 ) );
Group( a1, a2, a3, a4, b )
gap> m := CompositionSubgroup( s4xc2, 3 );
Subgroup( Group( a1, a2, a3, a4, b ), [ a3, a4, b ] )
gap> oc := OneCoboundaries( s4xc2, m );
rec(
oneCoboundaries := RowSpace( GF(2),
[ [ 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ],
[ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2) ] ] ),
generators := [ a1, a2 ],
cocycleToList := function ( c ) ... end,
listToCocycle := function ( L ) ... end )
gap> v := Base( oc.oneCoboundaries );
[ [ 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ],
[ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2) ] ]
gap> oc.cocycleToList( v );
[ a4, a4 ]
gap> oc.cocycleToList( v );
[ IdAgWord, a3 ]
gap> oc.cocycleToList( v+v );
[ a4, a3*a4 ] ```

25.87 OneCocycles

`OneCocycles( G, M )`

Let M be a normal p-elementary abelian subgroup of G. Then `OneCocycles` computes the vector space V = β( Z1( G/M, M ) ), which is isomorphic to the group of one cocyles Z1( G, M ) as described in One Cohomology Group. The function returns a record C with the following components.

`oneCoboundaries`:

contains the vector space isomorphic to B1( G, M ).

`oneCocycles`:

contains the vector space V.

`generators`:

contains representatives (g1, ..., gl) for the canonical generating system of <G> / M

`isSplitExtension`:

If G splits over M, `C.isSplitExtension` is `true`, otherwise it is `false`. In case of a split extension three more components `C.complement`, `C.cocycleToComplement` and `C.complementToCycles` are returned.

`complement`:

contains a subgroup of G which is a complement of M.

`cocycleToList`:

contains a functions which takes an element v of V as argument and returns a list [ n1, ..., nl ], where ni is an element of M, such that ni = ( β-1( v ) )( gi M ).

`listToCocycles`:

is the inverse of `cocycleToList`.

`cocycleToComplement`:

contains a function which takes an element of V as argument and returns a complement of M.

`complementToCocycle`:

is its inverse. This is possible, because in a split extension there is a one to one correspondence between the elements of V and the complements of M.

`OneCocycles( G, α, M )`

In that form `OneCocycles` computes the one cocycles in the semidirect product of G and M where G acts on M using α (see SemidirectProduct). In that case C only contains `C.oneCoboundaries`, `C.oneCocycles`, `C.generators`, `C.cocycleToList` and `C.listToCocycle`.

```    gap> s4xc2 := DirectProduct( s4, CyclicGroup( AgWords, 2 ) );;
gap> s4xc2.name := "s4xc2";;
gap> m := CompositionSubgroup( s4xc2, 3 );
Subgroup( s4xc2, [ a3, a4, b ] )
gap> oc := OneCocycles( s4xc2, m );;
gap> oc.oneCocycles;
RowSpace( GF(2), [ [ 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ],
[ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2) ],
[ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2) ] ] )
gap> v := Base( oc.oneCocycles );
[ [ 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ],
[ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2) ],
[ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2) ] ]
gap> oc.cocycleToList( v );
[ a4, a4 ]
gap> oc.cocycleToList( v );
[ b, IdAgWord ]
gap> oc.cocycleToList( v );
[ b, IdAgWord ]
gap> oc.cocycleToList( v );
[ IdAgWord, a3 ]
gap> Igs( oc.complement );
[ a1, a2 ]
gap> Igs( oc.cocycleToComplement( v+v+v ) );
[ a1*a4*b, a2*a3*a4 ]
gap> z4 := CyclicGroup( AgWords, 4 );
Group( c4_1, c4_2 )
gap> m := CompositionSubgroup( z4, 2 );
Subgroup( Group( c4_1, c4_2 ), [ c4_2 ] )
gap> OneCocycles( z4, m );
rec(
oneCoboundaries := RowSpace( GF(2), [ [ 0*Z(2) ] ] ),
oneCocycles := RowSpace( GF(2), [ [ Z(2)^0 ] ] ),
generators := [ c4_1 ],
isSplitExtension := false ) ```

25.88 Complements

`Complement` (see Complement) tries to find one complement to a given normal subgroup, while `Complementclasses` (see Complementclasses) finds all complements and returns representatives for the conjugacy classes of complements in a given ag group.

If `InfoAgCo1` and `InfoAgCo2` are set to `Print` information about the computation is given.

25.89 Complement

`Complement( U, N )`

Let N and U be ag group such that N is a normal subgroup of U. `Complement` returns a complement of N in U if the U splits over N. Otherwise `false` is returned.

`Complement` descends along an elementary abelian series of U containing N. See CNW90 for details.

```    gap> v4 := Subgroup( s4, [ c, d ] );
Subgroup( s4, [ c, d ] )
gap> Complement( s4, v4 );
Subgroup( s4, [ a, b ] )
gap> z4 := CyclicGroup( AgWords, 4 );
Group( c4_1, c4_2 )
gap> z2 := Subgroup( z4, [ z4.2 ] );
Subgroup( Group( c4_1, c4_2 ), [ c4_2 ] )
gap> Complement( z4, z2 );
false
gap> m9 := ElementaryAbelianGroup( AgWords, 9 );
Group( m9_1, m9_2 )
gap> m3 := Subgroup( m9, [ m9.2 ] );
Subgroup( Group( m9_1, m9_2 ), [ m9_2 ] )
gap> Complement( m9, m3 );
Subgroup( Group( m9_1, m9_2 ), [ m9_1 ] ) ```

25.90 Complementclasses

`Complementclasses( U, N )`

Let U and N be ag groups such that N is a normal subgroup of U. `Complementclasses` returns a list of representatives for the conjugacy classes of complements of N in U.

Note that the empty list is returned if U does not split over N.

`Complementclasses` descends along an elementary abelian series of U containing N. See CNW90 for details.

```    gap> v4 := Subgroup( s4, [ c, d ] );
Subgroup( s4, [ c, d ] )
gap> Complementclasses( s4, v4 );
[ Subgroup( s4, [ a, b ] ) ]
gap> z4 := CyclicGroup( AgWords, 4 );
Group( c4_1, c4_2 )
gap> z2 := Subgroup( z4, [ z4.2 ] );
Subgroup( Group( c4_1, c4_2 ), [ c4_2 ] )
gap> Complementclasses( z4, z2 );
[  ]
gap> m9 := ElementaryAbelianGroup( AgWords, 9 );
Group( m9_1, m9_2 )
gap> m3 := Subgroup( m9, [ m9.2 ] );
Subgroup( Group( m9_1, m9_2 ), [ m9_2 ] )
gap> Complementclasses( m9, m3 );
[ Subgroup( Group( m9_1, m9_2 ), [ m9_1 ] ),
Subgroup( Group( m9_1, m9_2 ), [ m9_1*m9_2 ] ),
Subgroup( Group( m9_1, m9_2 ), [ m9_1*m9_2^2 ] ) ] ```

25.91 CoprimeComplement

`CoprimeComplement( U, N )`

`CoprimeComplement` returns a complement of a normal p-elementary abelian Hall subgroup N of U.

Note that, as N is a normal Hall-subgroup of U, the theorem of Schur guarantees the existence of a complement.

```    gap> s4xc25 := DirectProduct( s4, CyclicGroup( AgWords, 25 ) );
Group( a1, a2, a3, a4, b1, b2 )
gap> s4xc25.name := "s4xc25";;
gap> a4xc25 := Subgroup( s4xc25,
>                  Sublist( s4xc25.generators, [2..5] ) );
Subgroup( s4xc25, [ a2, a3, a4, b1 ] )
gap> N := Subgroup( s4xc25, [ s4xc25.3, s4xc25.4 ] );
Subgroup( s4xc25, [ a3, a4 ] )
gap> CoprimeComplement( a4xc25, N );
Subgroup( s4xc25, [ a2, b1, b2 ] ) ```

25.92 ComplementConjugatingAgWord

`ComplementConjugatingAgWord( N, U, V )`
`ComplementConjugatingAgWord( N, U, V, K )`

Let N, U, V and K be ag groups with a common parent group G, such that N is p-elementary abelian and normal in G, <U>*N = V*N, <U>∩ N = VN = {1}, K is a normal subgroup of <U> N contained in <U>∩ V and U is conjugate to V under an element n of N. Then this function returns an element n of N such that <U>n = V as ag word. If K is not given, the trivial subgroup is assumed.

In a typical application N is a normal p-elementary abelian subgroup and U, V and K are subgroups such that U/K is a q-group with q ≠ p.

Note that this function does not check any of the above conditions. So the result may either be `false` or an ag word with does not conjugate U into V, if U and V are not conjugate.

```    gap> c3a := Subgroup( s4, [ b ] );
Subgroup( s4, [ b ] )
gap> c3b := Subgroup( s4, [ b*c ] );
Subgroup( s4, [ b*c ] )
gap> v4 := Subgroup( s4, [ c, d ] );
Subgroup( s4, [ c, d ] )
gap> ComplementConjugatingAgWord( v4, c3a, c3b );
d
gap> c3a ^ d;
Subgroup( s4, [ b*c ] ) ```

25.93 HallConjugatingWordAgGroup

`HallConjugatingAgWord( S, H, K )`

Let H, K and S be ag group with a common parent group such that H and K are Hall-subgroups of S, then `HallConjugatingAgWord` returns an element g of S as ag word, such that <H>g = K.

```    gap> d8 := HallSubgroup( s4, 2 );
Subgroup( s4, [ a, c, d ] )
gap> d8 ^ b;
Subgroup( s4, [ a*b^2, c*d, d ] )
gap> HallConjugatingAgWord( s4, d8, d8 ^ b );
b
gap> HallConjugatingAgWord( s4, d8 ^ b, d8 );
b^2 ```

25.94 Example, normal closure

We will now show you how to write a GAP3 function, which computes the normal closure of an ag group. Such a function already exists in the library (see NormalClosure), but this should be an example on how to put functions together. You should at least be familiar with the basic definitions and functions for ag groups, so please refer to Words in Finite Polycyclic Groups, Finite Polycyclic Groups and More about Ag Groups for the definitions of finite polycyclic groups and its subgroups, see Generating Systems of Ag Groups for information about calculating induced or canonical generating system for subgroups.

Let U and S be subgroups of a group G. Then the normal closure N of U under S is the smallest subgroup in G, which contains U and is invariant under conjugation with elements of S. It is clear that N is invariant under conjugating with generators of S if and only if it is invariant under conjugating with all elements of S.

So in order to compute the normal closure of U, we can start with N:= U, conjugate N with a generator s of S and set N to the subgroup generated by N and Ns. Then we take the next generator of S. The whole process is repeated until N is stable. A GAP3 function doing this looks like

```    NormalClosure := function( S, U )

local   G,  #  the common supergroup of S and U
N,  #  closure computed so far
M,  #  next closure under generators of S
s;  #  one generator of S

G := Parent( S, U );
M := U;
repeat
N := M;
for s  in Igs( S )  do
M := MergedCgs( G, [ M ^ s, M ] );
od;
until M = N;
return N;

end; ```

Let S = G be the wreath product of the symmetric group on four points with itself using the natural permutation representation. Let U be a randomly chosen subgroup of order 12. The above functions needs, say, 100 time units to compute the normal closure of U under S, which is a subgroup N of index 2 in G.

```    gap> prms := [ (1,2), (1,2,3), (1,3)(2,4), (1,2)(3,4) ];
[ (1,2), (1,2,3), (1,3)(2,4), (1,2)(3,4) ]
gap> f := GroupHomomorphismByImages( s4, Group( prms, () ),
>             s4.generators, prms );;
gap> G := WreathProduct( s4, s4, f );
Group( h1, h2, h3, h4, n1_1, n1_2, n1_3, n1_4, n2_1, n2_2, n2_3,
n2_4, n3_1, n3_2, n3_3, n3_4, n4_1, n4_2, n4_3, n4_4 )
gap> G.name := "G";;
gap> u := Random( G );
h1*h3*h4*n1_1*n1_3*n1_4*n2_1*n2_2*n2_3*n2_4*n3_2*n3_3*n4_1*n4_3*n4_4
gap> U := MergedCgs( G, [ u ] );
Subgroup( G,
[ h1*h3*n1_2^2*n1_3*n1_4*n2_1*n2_3*n3_1*n3_2*n3_4*n4_1*n4_3,
h4*n1_4*n2_1*n2_4*n3_1*n3_2*n4_2^2*n4_4,
n1_1*n2_1*n3_1*n3_2^2*n3_3*n3_4*n4_1*n4_4 ] )
gap> Size( U );
8 ```

Now we can ask to speed up things. The first observation is that computing a canonical generating system is usablely a more time consuming task than computing a conjugate subgroup. So we form a canonical generating system after we have computed all conjugate subgroups, although now an additional repeat-until loop could be necessary.

```    NormalClosure := function( S, U )
local   G,  N,  M,  s,  gens;

G := Parent( S, U );
M := U;
repeat
N := M;
gens := [ M ];
for s  in Igs( S )  do
Add( gens, M ^ s );
od;
M := MergedCgs( G, gens );
until M = N;
return N;

end; ```

If we now test this new normal closure function with the above groups, we see that the running time has decreased to 48 time units. The canonical generating system algorithm is faster if it knows a large subgroup of the group which should be generated but it does not gain speed if it knows several of them. A canonical generating system for the conjugated subgroup `M^s` is computed, although we only need generators for this subgroup. So we can rewrite our algorithm.

```    NormalClosure := function( S, U )

local   G,      #  the common supergroup of S and U
N,      #  closure computed so far
M,      #  next closure under generators of S
gensS,  #  generators of S
gens;   #  generators of next step

G := Parent( S, U );
M := U;
gens := Igs( S );
repeat
N := M;
gens := Concatenation( [ M ], Concatenation( List( S, s ->
List( Igs( M ), m -> m ^ s ) ) ) );
M := MergedCgs( G, gens );
until M = N;
return N;

end; ```

Now a canonical generating system is generated only once per repeat-until loop. This reduces the running time to 33 time units. Let m∈ M and s∈ S. Then ⟨ M, ms = ⟨ M, m-1 ms. So we can substitute `m^s` by `Comm( m, s )`. If m is invariant under s the new generator would be 1 instead of m. With this modification the running times drops to 23 time units.

As next step we can try to compute induced generating systems instead of canonical ones. In that case we cannot compare aggroups by `=`, but as N is a subgroup M it is sufficient to compare the composition lengths.

```    NormalClosure := function( S, U )

local   G,      #  the common supergroup of S and U
N,      #  closure computed so far
M,      #  next closure under generators of S
gensS,  #  generators of S
gens;   #  generators of next step

G := Parent( S, U );
M := U;
gens := Igs( S );
repeat
N := M;
gens := Concatenation( List( S, s -> List( Igs( M ),
m -> Comm( m, s ) ) ) );
M := MergedIgs( G, N, gens, false );
until Length( Igs( M ) ) = Length( Igs( M ) );
Normalize( N );
return N;

end; ```

But if we try the example above the running time has increased to 31. As the normal closure has index 2 in G the agwords involved in a canonical generating system are of length one or two. But agwords of induced generating system may have much large length. So we have avoided some collections but made the collection process itself much more complicated. Nevertheless in examples with subgroups of greater index the last function is slightly faster. Previous Up Next
Index

gap3-jm
11 Mar 2019