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 Ag Group Functions and Subgroups and Properties of Ag Groups). Some additional information about generating systems of subgroups and factor groups are 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

  1. More about Ag Groups
  2. Construction of Ag Groups
  3. Ag Group Operations
  4. Ag Group Records
  5. Set Functions for Ag Groups
  6. Elements for Ag Groups
  7. Intersection for Ag Groups
  8. Size for Ag Groups
  9. Group Functions for Ag Groups
  10. AsGroup for Ag Groups
  11. Group for Ag Groups
  12. CommutatorSubgroup for Ag Groups
  13. Normalizer for Ag Groups
  14. IsCyclic for Ag Groups
  15. IsNormal for Ag Groups
  16. IsSubgroup for Ag Groups
  17. Stabilizer for Ag Groups
  18. CyclicGroup for Ag Groups
  19. ElementaryAbelianGroup for Ag Groups
  20. DirectProduct for Ag Groups
  21. WreathProduct for Ag Groups
  22. RightCoset for Ag Groups
  23. FpGroup for Ag Groups
  24. Ag Group Functions
  25. AgGroup
  26. IsAgGroup
  27. AgGroupFpGroup
  28. IsConsistent
  29. IsElementaryAbelianAgSeries
  30. MatGroupAgGroup
  31. PermGroupAgGroup
  32. RefinedAgSeries
  33. ChangeCollector
  34. The Prime Quotient Algorithm
  35. PQuotient
  36. Save
  37. PQp
  38. InitPQp
  39. FirstClassPQp
  40. NextClassPQp
  41. Weight
  42. Factorization for PQp
  43. The Solvable Quotient Algorithm
  44. SolvableQuotient
  45. InitSQ
  46. ModulesSQ
  47. NextModuleSQ
  48. Generating Systems of Ag Groups
  49. AgSubgroup
  50. Cgs
  51. Igs
  52. IsNormalized
  53. Normalize
  54. Normalized
  55. MergedCgs
  56. MergedIgs
  57. Factor Groups of Ag Groups
  58. FactorGroup for AgGroups
  59. CollectorlessFactorGroup
  60. FactorArg
  61. Subgroups and Properties of Ag Groups
  62. CompositionSubgroup
  63. HallSubgroup
  64. PRump
  65. RefinedSubnormalSeries
  66. SylowComplements
  67. SylowSystem
  68. SystemNormalizer
  69. MinimalGeneratingSet
  70. IsElementAgSeries
  71. IsPNilpotent
  72. NumberConjugacyClasses
  73. Exponents
  74. FactorsAgGroup
  75. MaximalElement
  76. Orbitalgorithms of Ag Groups
  77. AffineOperation
  78. AgOrbitStabilizer
  79. LinearOperation
  80. Intersections of Ag Groups
  81. ExtendedIntersectionSumAgGroup
  82. IntersectionSumAgGroup
  83. SumAgGroup
  84. SumFactorizationFunctionAgGroup
  85. One Cohomology Group
  86. OneCoboundaries
  87. OneCocycles
  88. Complements
  89. Complement
  90. Complementclasses
  91. CoprimeComplement
  92. ComplementConjugatingAgWord
  93. HallConjugatingWordAgGroup
  94. Example, normal closure

25.1 More about Ag Groups

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

(i) & (u_1, ..., u_r) is a PAG system for U,
(ii) & delta( u_i ) > delta( u_j ) for i > j,
(iii) & lambda( u_i ) = 1 for i = 1, ..., r,
(iv) & nu_{delta(u_i)}(u_j) = 0 for i neq j.

If a generating system (u_1, ..., u_r) 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 GAP 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 GAP 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[1];; b := s4.generators[2];;
    gap> c := s4.generators[3];; d := s4.generators[4];; 

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 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 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 (g_1, ..., g_n) where the relative order of g_i is o_i. Then { g_1^{e_1} ... g_n^{e_n} ; 0 leq e_i < o_i } 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 (g_1, ..., g_n) where the relative order of g_i is o_i. Then the size of G is o_1 * ... * o_n.

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 )

See Group for Ag Groups.

CompositionSeries( G )

Let (g_1, ..., g_n) be an induced generating system of G with respect to the parent group of G. Then for i in {1,...,n} the i.th composition subgroup S_i of the AG system is generated by (g_i, ...,g_n). The n+1.th composition subgroup S_{n+1} is the trivial subgroup of G. The AG series of G is the series {S_1, ..., S_{n+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 citeLNS84,Gla87).

ElementaryAbelianSeries( L )

L must be a list of ag groups S_1 = H, ..., S_m = {1} with a common parent group such that S_i is a subgroup of S_{i-1} and S_i is normal in G for all i in {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 )

See Normalizer for Ag Groups.

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 (u_1, ..., u_r) be a induced generating system of U. Let e_1, ..., e_r be the relative order of u_1, ..., u_r. Then for r random integers nu_i between 0 and e_i - 1 the word u_1^{nu_1}* ...* u_r^{nu_r} is returned.

IsCyclic( G )

See IsCyclic for Ag Groups.

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 )

See IsNormal for Ag Groups.

IsPerfect( G )

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

IsSubgroup( G, U )

See IsSubgroup for Ag Groups.

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 )

See Stabilizer for Ag Groups.

AsGroup( D )

See AsGroup for Ag Groups.

FpGroup( U )

See FpGroup for Ag Groups.

RightCoset( U, g )

See RightCoset for Ag Groups.

AbelianGroup( D, L )

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

CyclicGroup( D, n )

See CyclicGroup for Ag Groups.

ElementaryAbelianGroup( D, n )

See ElementaryAbelianGroup for Ag Groups.

DirectProduct( L )

See DirectProduct for Ag Groups.

WreathProduct( G, H, alpha )

See WreathProduct for Ag Groups.

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 g_1, ..., g_n be an canonical generating system for G and h_1, ..., h_m be an canonical generating system for H. The normal closure of the subgroup S generated by Comm( g_i, h_j ) for 1 leq i leq n and 1 leq j leq 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( g_i, g_j ) for 1 leq i < j leq 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 citeGS90,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 p_1^{e_1} ... p_n^{e_n} where the p_i are distinct primes then G is cyclic if and only if each <G>^{p_i} has index p_i in G.

AgGroupOps.IsCyclic computes the groups <G>^p_i using the fact that the map x mapsto x^{p_i} is a homomorphism of G, so that the p_i.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 Omega by op. Let pt be an element of Omega. 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 in Omega 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 c<n>_1, ..., c<n>_r. Otherwise, the names of the r generators are <str>1, ..., <str>r, 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 c<n> 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 p^r. If no str is given the names of the r generators are m<n>_1, ..., m<n>_r. Otherwise the names of the r generators are <str>1, ..., <str>r, 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 m<n> 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> = [ U_1, ..., U_n ]. AgGroupOps.DirectProduct returns the direct product of all U_i as new ag group with collector.

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

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

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, alpha )

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 alpha be a homomorphism H into a permutation group of degree d.

Let (g_1, ..., g_r) be an IGS of G, (h_1, ..., h_n) an IGS of H. The wreath product has a PAG system (b_1, ..., b_n, a_{11}, ..., a_{1r}, a_{d1}, ..., a_{dr}) such that b_1, ..., b_n generate a subgroup isomorph to H and a_{i1}, ..., a_{ir} generate a subgroup isomorph to G for each i in {1, ..., r}. The names of b_1, ..., b_n are h1, ..., hn, the names of a_{i1}, ..., a_{ir} 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 stri 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 g_1, ..., g_n be the generators of F. Then the words of relators must be the power relators g_k^{e_k} * w_{kk}^{-1} and commutator relator Comm( g_i, g_j ) * w_{ij}^{-1} or conjugate relators g_i^{g_j} * w_{ij}^{-1} for all 1 leq k leq n and 1leq j < i leq n, such that w_{kk} are words in g_{k+1}, ..., g_n and w_{ij} are words in g_{j+1}, ..., g_n. 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 e_i of g_i 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 e_i 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 [ w_1, w_2 ] such that the words w_1 and w_2 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.

See also LinearOperation.

    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 (g_1,..., g_n) be the AG system of the ag group G and n(g_i) the name of g_i. If the relative order of g_i is a prime, then n(g_i) 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(g_i)_1, ..., n(g_i)_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 g_i^{g_j^r} for j < i and r = 1, ..., <n> (see Bis89).

``quadruple'' initializes a collector from the left collecting with quadruples {g_i^s}^{g_j^r} 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 g_i^{g_j} = w_{ij} or Comm( g_i, g_j ) = w_{ij} for 1 leq j < i leq n, such that w_{ij} are words in g_{i+1}, ..., g_n fulfilling the central weight condition (see citeHN80,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 GAP. 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 mid x^{25}/(xcdot y)^5, [x,y]^5, (x^y)^{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 GAP. 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 5^2cdot 5^2cdot 5^2cdot 5^3 = 5^9. The epimorphism of G onto the quotient P is given by the map x mapsto g1 and y mapsto 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 GAP. 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^prime 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, [3] );
    Group( e1, e2, m3, m4 )
    gap> Size(AgGroupFpGroup(g));
    36
    gap> g := SolvableQuotient( f4, [2] );
    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.

See also ModulesSQ and NextModuleSQ.

    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[1] );
    << solvable quotient of size 2^2 >>
    gap> NextModuleSQ( s, m[2] );
    << solvable quotient of size 2^2*3 >>
    gap> NextModuleSQ( s, m[3] );
    << solvable quotient of size 2^2 >>
    gap> NextModuleSQ( s, m[4] );
    << 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 u_i of U of depth d_i such that no induced generator in N has depth d_i.

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 (g_1, ..., g_n) 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 (g_i, ..., g_n).

    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 pi-Hall-subgroup of G for the set pi of all prime divisors of the integer n or the join pi 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 G_1, ..., G_n, such that G_{i+1} is a normal subgroup of G_i. Then the function computes a composition series H_1 = G_1, ..., H_m = G_n 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 { S_1, ... , S_n } is known, SylowComplements computes the various Hall subgroups H_i using the fact that H_i is the product of all S_j except S_i.

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 { S_1, ... , S_n } 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 S_i for each prime divisor of the group order of U such that S_i * S_j = S_j * S_i is fulfilled for each pair i,j.

SylowSystem uses SylowComplements (see SylowSystem) in order to compute the various Sylow complements H_i of U. Then the Sylow system is constructed using the fact that the intersection S_i of all Sylow complements H_j except H_i is a Sylow subgroup and that all these subgroups S_i 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 (u_1, ..., u_r) be an induced generating system of U. Then u can be uniquely written as u_1^{nu_1}* ...* u_r^{nu_r} for integer nu_i. The exponent vector of u is [nu_1, ..., nu_r].

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 (g_1, ..., g_n) and let (u_1, ..., u_m) be the canonical generating system of U, d_i is the depth of u_i with respect to G. Then an ag word u =g_1^{nu_1}* ...* g_n^{nu_n} in U is returned such that sum_{i=1}^m nu_{d_i} 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, varphi, tau )

Let U be an ag group with an induced generating system u_1, ..., u_m and let V be a vector space with base (o_1, ..., o_n). Further U should act affinely on V. So if v is an element of V and u is an element of U, then v^u = v_u + x_u, such that the function which maps v to v_u is linear and x_u is an element of V. These actions are given by the functions varphi and tau as follows. <varphi>( v, u) must return the representation of v_u with respect to the base (o_1, ..., o_n) as sequence of finite field elements. <tau>( u ) must return the representation of x_u in the base (o_1, ..., o_n) 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 m_i, such that m_i describes the action of u_i and m_i is of the form

left( beginarraycc L_u_i & 0
x_u_i & 1
endarray right),

where L_u is the matrix which describes the linear operation v in Vmapsto v_u.

    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, omega )
AgOrbitStabilizer( U, gens, omega, f )

Let U be an ag group acting on a set Omega. Let omega be an element of Omega. Then AgOrbitStabilizer returns the point-stabilizer of omega in the group U and the orbit of omega 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 omega. R.orbit is the list of the elements of <omega> ^ <U>.

Let (u_1, ..., u_n) be an induced generating system of U and gens be a list h_1, ..., h_n of generators of a group H, such that the map u_imapsto h_i extends to an homomorphism alpha from U to H, which is compatible with the action of G and H on Omega, such that g in Stab_U( <omega> ) if and only if g^alpha in Stab_H( <omega> ). 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 Omega. Otherwise f must be a function, which takes two arguments, the first one must be a point p of Omega 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, varphi )

Let U be an ag group with an induced generating system u_1, ..., u_m and V a vector space with base (o_1, ..., o_n). 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 v^u = a_1*o_1+ ... +a_n*o_n, then the function <varphi>( v, u ) must return (a_1, ..., a_n) 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 m_i, such that m_i describes the action of u_i.

    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> leq 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> cap <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 v_1, ..., v_a, W be generated by w_1, ..., w_b. Then the matrix

left( beginarraycc v_1 & 1
vdots & vdots
v_a & 1
w_1 & w_1
vdots & vdots
w_b & w_b
endarray right)

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

left( beginarraycc l_1 & k_1
vdots & vdots
l_c & k_c
1 & k_c+1
vdots & vdots
1 & k_a+b
endarray right).

Then l_1, ..., l_c is a generating sequence for the sum, while the sequence k_{c+1}, ..., k_{a+b} is is a generating sequence for the intersection. leftSide is bound to a list, such that the i.th list element is l_j, if there exists a j, such that l_j has depth i, and IdAgWord otherwise. rightSide is bound to a list, such that the i.th list element is k_j, if there exists a j less than c+1, such that k_j has depth i, and IdAgWord otherwise. See also SumFactorizationFunctionAgGroup.

Note that this functions returns an incorrect result if <W> not leq 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> leq 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.

The function uses the Zassenhaus sum-intersection algorithm. See also NormalIntersection and SumAgGroup. For more information about the Zassenhaus algorithm see ExtendedIntersectionSumAgGroup and SumFactorizationFunctionAgGroup.

Note that this functions returns an incorrect result if <W> not leq 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> leq 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 leq 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> cap <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 B^1( G/M, M ) is defined as

B^1( G/M, M ) = { gamma : G/M rightarrow M ; ; ; exists min Mforall gin G : gamma( gM ) = (m^-1)^g cdot m }

and is a Z_p-vector space. The group of cocycles Z^1( G/M, M ) is defined as

Z^1( G/M, M ) = { gamma : G/M rightarrow M ; ; ; forall g_1, g_2in G : gamma(g_1M cdot g_2M ) = gamma(g_1M)^g_2 cdot gamma(g_2M) }

and is also a Z_p-vector space.

Let alpha be the isomorphism of M into a row vector space {cal W} and (g_1, ..., g_l) representatives for a generating set of G/M. Then there exists a monomorphism beta of Z^1( G/M, M ) in the l-fold direct sum of {cal W}, such that beta( gamma ) = ( alpha( gamma( g_1M ) ), ..., alpha( gamma( g_lM ) ) ) for every gamma in Z^1( 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 {cal V} = beta( B^1( <G>/<M>, <M> ) ), which is isomorphic to the group of one coboundaries B^1( G, M ) as described in One Cohomology Group. The functions returns a record C with the following components.

oneCoboundaries:

contains the vector space {cal V}.

generators:

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

cocycleToList:

contains a functions which takes an element v of {cal V} as argument and returns a list [ n_1, ..., n_l ], where n_i is an element of M, such that n_i = ( beta^{-1}( v ) )( g_i <M> ).

listToCocycles:

is the inverse of cocycleToList.

OneCoboundaries( G, alpha, M )

In that form OneCoboundaries computes the one coboundaries in the semidirect product of G and M where G acts on M using alpha (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[1] );
    [ a4, a4 ]
    gap> oc.cocycleToList( v[2] );
    [ IdAgWord, a3 ]
    gap> oc.cocycleToList( v[1]+v[2] );
    [ 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 {cal V} = beta( Z^1( <G>/<M>, <M> ) ), which is isomorphic to the group of one cocyles Z^1( 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 B^1( G, M ).

oneCocycles:

contains the vector space {cal V}.

generators:

contains representatives (g_1, ..., g_l) 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 {cal V} as argument and returns a list [ n_1, ..., n_l ], where n_i is an element of M, such that n_i = ( beta^{-1}( v ) )( g_i <M> ).

listToCocycles:

is the inverse of cocycleToList.

cocycleToComplement:

contains a function which takes an element of {cal 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 {cal V} and the complements of M.

OneCocycles( G, alpha, M )

In that form OneCocycles computes the one cocycles in the semidirect product of G and M where G acts on M using alpha (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[1] );
    [ a4, a4 ]
    gap> oc.cocycleToList( v[2] );
    [ b, IdAgWord ]
    gap> oc.cocycleToList( v[2] );
    [ b, IdAgWord ]
    gap> oc.cocycleToList( v[3] );
    [ IdAgWord, a3 ]
    gap> Igs( oc.complement );
    [ a1, a2 ]
    gap> Igs( oc.cocycleToComplement( v[1]+v[2]+v[3] ) );
    [ 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> cap <N> = <V> cap <N> = {1}, K is a normal subgroup of <U> <N> contained in <U> cap <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 qneq 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 GAP 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 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 N^s. Then we take the next generator of S. The whole process is repeated until N is stable. A GAP 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 in M and s in S. Then < M, m^s > = < M, m^{-1} m^s > . 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

GAP 3.4.4
April 1997