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.
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];;
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).
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.
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
:true
.
isConsistent
:true
if G has a consistent presentation (see
IsConsistent).
compositionSeries
:
cgs
:
igs
:
elementaryAbelianFactors
:
sylowSystem
: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.
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.
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 ] )
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.
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 )
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 )
IsFinite( G )
As G is a finite solvable group AgGroupOps.IsFinite
returns true
.
IsNilpotent( U )
AgGroupOps.IsNilpotent
uses Glasby's nilpotency test for ag groups
(see Gla87).
IsNormal( G, U )
IsPerfect( G )
As G is a finite solvable group it is perfect if and only if G is trivial.
IsSubgroup( G, U )
ConjugacyClasses( H )
The conjugacy classes of elements are computed using linear methods. The algorithm depends on the ag series of the parent group of H being a refinement of an elementary abelian series. Thus if this is not true or if H is not a member of the elementary abelian series, an isomorphic group, in which the computation can be done, is created.
The algorithm that is used steps down an elementary abelian series of the parent group of H, basically using affine operation to construct the conjugacy classes of H step by step from its factorgroups.
Orbit( U, pt, op )
AgGroupOps.Orbit
returns the orbit of pt under U using the
operation op. The function calls AgOrbitStabilizer
in order to
compute the orbit, so please refer to AgOrbitStabilizer for details.
Stabilizer( U, pt, op )
AsGroup( D )
FpGroup( U )
RightCoset( U, g )
AbelianGroup( D, L )
Let L be the list [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.
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.
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.
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.
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.
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).
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.
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.
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.
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 )
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 )
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 )
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 )
AgGroupOps.Coset( G )
A coset C = <G>{*}x is represented as record with the following components.
representative
:
group
:
isDomain
:true
.
isRightCoset
:true
.
isFinite
:true
.
operations
: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.
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.
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.
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.
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
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
.
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;;
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, [ ] ) ]
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 ] ] )
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) )
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 )
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.
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.
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
:
pcp
:
dimensions
:dimensions[i]
is the dimension of the i-th
factor in the lower exponent-p central series calculated by the
p-quotient algorithm.
prime
:
definedby
:[ j, i ]
:generators
.i
:generators
.-i
:
epimorphism
: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
.
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 ] ] ) );
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> )
.
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.
FirstClassPQp( G, p )
FirstClassPQp
returns a PQp record for the exponent-p class 1
quotient of G.
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
.
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.
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.
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.
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
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 >>
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) );;
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 >>
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.
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 ] )
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
.
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
.
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.
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).
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.
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 ] )
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.
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).
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
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
:
isFactorGroupElement
contains true
.
info
:
operations
:FactorGroupAgWordsOps
.
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
:true
.
factorNum
:
factorDen
:
identity
:
generators
:
operations
: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 ]
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.
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, [ ] )
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 ] )
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
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, [ ] ) ]
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
:
sylowComplements
: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
: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 ] ) ] )
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
:
sylowComplements
: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
: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 ] ) ] )
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 ] )
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
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.
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
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
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 ]
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 ]
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.
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.
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 ] ] )
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 ] )
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 ] ] )
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.
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
:
sum
:
leftSide
:
rightSide
: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 ] ) )
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 ] ) )
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 )
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
:
sum
:
factorization
: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 )
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.
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
:
generators
:
cocycleToList
:
listToCocycles
: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 ]
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
:
oneCocycles
:
generators
:
isSplitExtension
: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
:
cocycleToList
:
listToCocycles
:cocycleToList
.
cocycleToComplement
:
complementToCocycle
:
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 )
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.
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 ] )
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 ] ) ]
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 ] )
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 ] )
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
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