Let G be a polycyclic group and let G = C1 \rhd C2 ¼Cn\rhd Cn+1 = 1 be a polycyclic series, that is, a subnormal series of G with non-trivial cyclic factors. For 1 £ i £ n we choose gi Î Ci such that Ci = ági, Ci+1 ñ. Then the sequence (g1, ¼, gn) is called a polycyclic generating sequence of G. Let I be the set of those i Î {1, ¼, n} with ri : = [Ci : Ci+1] finite. Each element of G can be written uniquely as g1e1¼gnen with ei Î Z for 1 £ i £ n and 0 £ ei < ri for i Î I.
Each polycyclic generating sequence of G gives raise to a
power-conjugate (pc-) presentation for G with the conjugate
relations
|
|
|
Vice versa, we say that a group G is defined by a pc-presentation if G is given by a presentation of the form above on generators g1,¼,gn. These generators are the defining generators of G. Here, I is the set of 1 £ i £ n such that gi has a power relation. The positive integer ri for i Î I is called the relative order of gi. If G is given by a pc-presentation, then G is polycyclic. The subgroups Ci = ági, ¼, gn ñ form a subnormal series G = C1 ³ ¼ ³ Cn+1 = 1 with cyclic factors and we have that giri Î Ci+1. However, some of the factors of this series may be smaller than ri for i Î I or finite if i Ï I·
If G is defined by a pc-presentation, then each element of G can be described by a word of the form g1e1¼gnen in the defining generators with ei Î Z for 1 £ i £ n and 0 £ ei < ri for i Î I. Such a word is said to be in collected form. In general, an element of the group can be represented by more than one collected word. If the pc-presentation has the property that each element of G has precisely one word in collected form, then the presentation is called confluent or consistent. If that is the case, the generators with a power relation correspond precisely to the finite factors in the polycyclic series and ri is the order of Ci/Ci+1.
The polycyclic share package is designed for computations with polycyclic groups which are given by consistent pc-presentations. In particular, all the functions described below assume that we compute with a group defined by a consistent pc-presentation. See Section Collectors for a routine that checks the consistency of a pc-presentation.
Let G be a group defined by a pc-presentation as described in Section Introduction.
The process for computing the collected form for an arbitrary word in the generators of G is called collection. The basic idea in collection is the following. Given a word in the defining generators, one scans the word for occurrences of adjacent generators (or their inverses) in the wrong order or occurrences of subwords giei with i Î I and ei not in the range 0¼ri-1. In the first case, the appropriate conjugacy relation is used to move the generator with the smaller index to the left. In the second case, one uses the appropriate power relation to move the exponent of gi into the required range. These steps are repeated until a collected word is obtained.
There are a number of different strategies for collecting a given word to collected form. The strategy implemented in this package is collection from the left as described by LS90 and Sims94. We note that the collection method in this package is currently implemented in GAP code. As this is a very time-critical function, we plan to translate this to C-code in the near future.
The first step in defining a pc-presented group is setting up a data structure that knows the pc-presentation and has routines that perform the collection algorithm with words in the generators of the presentation. Such a data structure is called a collector. In this section we describe how to set up a collector by hand.
To describe the right hand sides of the relations in a pc-presentation we use either words from a free group or generator exponent lists. The latter are lists of integers which represent a word in a free group; while a word in a free group is a product of generators and inverses, a generator exponent list is a list in which generator numbers and exponents alternate. Each factor giei in a word is represented by the entries i, j.
FromTheLeftCollector( n )
returns an empty data structure for a collector with n generators. No generator has a relative order and no conjugate relations are defined. Two generators for which no conjugate relations are defined commute. Therefore, the collector returned by this function can be used to define a free abelian group of rank n.
gap> ftl := FromTheLeftCollector( 4 ); <<from the left collector with 4 generators>> gap> UpdatePolycyclicCollector( ftl ); gap> PcpGroupByCollector( ftl ); Pcp-group with orders [ 0, 0, 0, 0 ] gap> IsAbelian(last); true
SetRelativeOrder( coll, i, ro )
set the relative order in collector coll for generator i to ro. The parameter coll is a collector as returned by the function FromTheLeftCollector, i is a generator number, i.e. an integer in the range 1,¼,n where n is the number of generators of the collector and ro is a non-negative integer. If ro is 0, then the generator with number i has infinite order and no power relation can be specified. A previously defined power relation is deleted.
SetPower( coll, i, rhs )
set the right hand side of the power relation for generator i in collector coll to rhs. An attempt to set the right hand side for a generator without a relative order results in an error. Right hand sides are by default assumed to be trivial. The parameter coll is a collector, i is a generators number and rhs is a generators exponent list or an element from a free group.
SetConjugate( coll, j, i, rhs )
set the right hand side of the conjugate relation for the generators j and i. Negative generators numbers refer to inverses of the generators. Conjugate relations are by default assumed to be trivial The parameter coll is a collector, i is a generators number and rhs is a generators exponent list or an element from a free group.
UpdatePolycyclicCollector( coll )
completes the data structures of a collector. This is usually the last step in setting up a collector. Among the steps performed is the completion of the conjugate relations. For each non-trivial conjugate relation of a generator, the corresponding conjugate relation of the inverse generator is calculated.
IsConfluent( coll )
tests if the collector coll is confluent. The function return true or false accordingly.
The following example specifies a collector for the infinite dihedral group.
gap> ftl := FromTheLeftCollector( 2 ); <<from the left collector with 2 generators>> gap> SetRelativeOrder( ftl, 1, 2 ); gap> SetConjugate( ftl, 2, 1, [2,-1] ); gap> UpdatePolycyclicCollector( ftl ); gap> IsConfluent( ftl ); true gap>
2.3 Pcp-elements -- elements of a pc-presented group
A pcp-element is an element of a group defined by a consistent pc-presentation given by a collector. Suppose that g1, ¼, gn are the defining generators of the collector. Recall that each element g in this group can be written uniquely as collected word g1e1 ¼gnen with ei Î Z and 0 £ ei < ri for i Î I. The integer vector [e1, ¼, en] is called the exponent vector of g. The following functions can be used to define pcp-elements via their exponent vector or via an arbitrary generator exponent word as introduced in Section Collectors.
PcpElementByExponentsNC( coll, exp )
PcpElementByExponents( coll, exp )
returns the pcp-element with exponent vector exp. The exponent vector is considered relative to the defining generators of the pc-presentation.
PcpElementByGenExpListNC( coll, word )
PcpElementByGenExpList( coll, word )
returns the pcp-element with generators exponent list word. The generators exponent list is considered relative to the defining generators of the pc-presentation.
These functions return pcp-elements in the category IsPcpElement.
Presently, the only representation implemented for this category
is IsPcpElementRep.
(This allows us to be a little sloppy right now. The basic set of
operations for IsPcpElement has not been defined yet. This is
going to happen in one of the next version, certainly as soon as the
need for different representations arises.)
IsPcpElement( obj )
returns true if the object obj is a pcp-element.
IsPcpElementRep( obj )
returns true if the object obj is represented as a pcp-element.
Now we can describe attributes and functions for pcp-elements. The
four basic attributes of a pcp-element, Collector, Exponents,
GenExpList and NameTag are computed at the creation of the
pcp-element. All other attributes are determined at runtime.
Let g be a pcp-element and g1, ¼, gn a polycyclic generating sequence of the underlying pc-presented group. Let C1, ¼, Cn be the polycyclic series defined by g1, ¼, gn.
The depth of a non-trivial element g of a pcp-group (with respect to the defining generators) is the integer i such that g Î Ci \Ci+1. The depth of the trivial element is defined to be n+1. If g ¹ 1 has depth i and giei ¼gnen is the collected word for g, then ei is the leading exponent of g.
If g has depth i, then we call ri = [Ci:Ci+1] the factor order of g. If r < ¥, then the smallest positive integer l with gl Î Ci+1 is the called relative order of g. If r=¥, then the relative order of g is defined to be 0. The index e of ág,Ci+1ñ in Ci/Ci+1 is called relative index of g. We have that r = el.
We call a pcp-element normed, if its leading exponent is equal to its relative index. For each pcp-element g there exists an integer e such that ge is normed.
Collector( g )
the collector to which the pcp-element g belongs.
Exponents( g )
returns the exponent vector of the pcp-element g wrt the defining generating set of the underlying collector.
GenExpList( g )
returns the generators exponent list of the pcp-element g wrt the defining generating set of the underlying collector.
NameTag( g )
the name used for printing the pcp-element g. Printing is done by using the name tag and appending the generator number of g.
Depth( g )
returns the depth of the pcp-element g relative to the defining generators.
LeadingExponent( g )
returns the leading exponent of pcp-element g relative to the defining generators. If g is the identity element, the functions returns 'fail'
RelativeOrder( g )
returns the relative order of the pcp-element g with respect to the defining generators.
RelativeIndex( g )
returns the relative index of the pcp-element g with respect to the defining generators.
FactorOrder( g )
returns the factor order of the pcp-element g with respect to the defining generators.
NormingExponent( g )
returns a positive integer e such that the pcp-element g raised to the power of e is normed.
NormedPcpElement( g )
returns the normed element corresponding to the pcp-element g.
2.5 Pcp-groups - groups of pcp-elements
labelpcpgroup
A pcp-group is a group consisting of pcp-elements such that all pcp-elements in the group share the same collector. Thus the group G defined by a polycyclic presentation and all its subgroups are pcp-groups.
PcpGroupByCollectorNC( coll )
PcpGroupByCollector( coll )
returns a pcp-group build from the collector coll.
Group( gens, id )
returns the group generated by the pcp-elements gens with identity id.
Subgroup( G, gens )
returns a subgroup of the pcp-group G generated by the list gens of pcp-elements from G.
gap> ftl := FromTheLeftCollector( 2 );;
gap> SetRelativeOrder( ftl, 1, 2 );
gap> SetConjugate( ftl, 2, 1, [2,-1] );
gap> UpdatePolycyclicCollector( ftl );
gap> G:= PcpGroupByCollectorNC( ftl );
Pcp-group with orders [ 2, 0 ]
gap> Subgroup( G, GeneratorsOfGroup(G){[2]} );
Pcp-group with orders [ 0 ]
2.6 Basis methods and functions for pcp-groups
labelmethods
Pcp-groups are groups in the GAP sense and hence all generic GAP methods for groups can be applied for pcp-groups. However, for a number of group theoretic questions GAP does not provide generic methods that can be applied to pcp-groups. For some of these questions there are functions provided in polycyclic.
In this section we describe some important basic functions which are available for pcp-groups. A number of higher-level functions are outlined in later sections and chapters.
Let U, V and N are subgroups of a pcp-group.
`U = V
decides if U and V are equal as sets.
Size( U )
returns the size of U.
Random( U )
returns a random element of U.
Index( U, V )
returns the index of V in U if V is a subgroup of U. The function does not check if V is a subgroup of U and if it is not, the result is not meaningful.
`g Î U
checks if g is an element of U.
Elements( U )
returns a list containing all elements of U. This functions will not terminate if U is infinite.
IsSubgroup( U, V )
tests if V is a subgroup of U.
IsNormal( U, V )
tests if V is normal in U.
ClosureGroup( U, V )
returns the group generated by U and V.
NormalClosure( U, V )
returns the normal closure of V under action of U.
`U / N
return the factor group of U modulo N. Clearly, N must be normal in U.
HirschLength( U )
returns the Hirsch length of U.
CommutatorSubgroup( U, V )
returns the group generated by all commutators [u,v] with u in U and v in V.
PRump( U, p )
returns the subgroup U¢Up of U where p is a prime number.
IsNilpotentGroup( U )
checks whether U is nilpotent.
IsAbelian( U )
checks whether U is abelian.
IsElementaryAbelian( U )
checks whether U is elementary abelian.
IsFreeAbelian( U )
checks whether U is free abelian.
2.7 Igs - induced generating sequences for subgroups
A subgroup of a pcp-group G can be defined by a set of generators as described in Section pcpgroup. However, many computations with a subgroup U need an induced generating sequence or igs of U. An igs is a sequence of generator of U whose list of exponent vectors form a matrix in upper triangular form. Note that there may exist many igs of U. The first one calculated for U is stored as an attribute.
An induced generating sequence of a subgroup of a pcp-group G is a list of elements of G. An igs is called normed, if each element in the list is normed. Moreover, it is canonical, if the exponent vector matrix is in Hermite Normal Form. The following functions can be used to compute induced generating sequence for a given subgroup U of G.
Igs( U )
Igs( gens )
IgsParallel( gens, gens2 )
returns an induced generating sequence of the subgroup U of a pcp-group. In the second for the subgroup is given via a generating set gens. The third form computes an igs for the subgroup generated by gens carrying gens2 through as shadows.
Ngs( U )
Ngs( igs )
returns a normed induced generating sequence of the subgroup U of a pcp-group. The second form takes an igs as input and norms it.
Cgs( U )
Cgs( igs )
CgsParallel( gens, gens2 )
returns a canonical generating sequence of the subgroup U of a pcp-group. In the second form the function takes an igs as input and returns a canonical generating sequence. The third version takes a generating set and computes a canonical generating sequence carrying gens2 through as shadows.
For a large number of methods for pcp-groups U we will first of all determine an igs for U. Hence it might speed up computations, if a known igs for a group U is set a priori. The following functions can be used for this purpose.
SubgroupByIgs( G, igs )
SubgroupByIgs( G, igs, gens )
returns the subgroup of the pcp-group G generated by the elements of the induced generating sequence igs. Note that igs must be an induced generating sequence of the subgroup generated by the elements of the igs. In the second form igs is a igs for a subgroup and gens are some generators. The function returns the subgroup generated by igs and gens.
AddToIgs( igs, gens )
AddToIgsParallel( igs, gens, igs2, gens2 )
AddIgsToIgs( igs, igs2 )
sifts the elements in the list gens into igs. The second version has the same functionality and carries shadows. The third version is available for efficiency reasons and assumes that the second list igs2 is not only a generating set, but an igs.
2.8 Pcps -- polycyclic presentation sequences for subfactors
labelpcps
A subfactor of a pcp-group G is again a polycyclic group for which a polycyclic presentation can computed. However, to compute a polycyclic presentation for a given subfactor can be time-consuming. Hence we introduce polycyclic presentation sequences or Pcp to compute more efficiently with subfactors. (Note that a subgroup is also a subfactor and thus can be handled by a pcp)
A pcp for a pcp-group U or a subfactor U / N can be created with one of the following functions.
Pcp( U )
Pcp( U, N )
Pcp( U, "snf" )
Pcp( U, N, "snf" )
returns a polycyclic presentation sequence for the subgroup U or the
quotient group U modulo N. If the parameter "snf" is present,
the function can only be applied to an abelian subgroup U or abelian
subfactor U/N. The pcp returned will correspond to a
decomposition of the abelian group into a direct product of cyclic
groups.
A pcp is a component object which behaves similar to a list representing an igs of the subfactor in question. The basic functions to obtain the stored values of this component object are as follows. Let pcp be a pcp for a subfactor U/N of the defining pcp-group G.
GeneratorsOfPcp( pcp )
this returns a list of elements of U corresponding to an igs of U/N.
`pcp [i]
returns the i-th element of pcp.
Length( pcp )
returns the number of generators in pcp.
RelativeOrdersOfPcp( pcp )
the relative orders of the igs in U/N.
DenominatorOfPcp( pcp )
returns an igs of N.
NumeratorOfPcp( pcp )
returns an igs of U.
GroupOfPcp( pcp )
returns U.
OneOfPcp( pcp )
returns the identity element of G.
bigbreak The two main features of pcp are the possibility to compute exponent vectors wrt to a pcp and to compute the group defined by the corresponding igs of U/N.
ExponentsByPcp( pcp, g )
returns the exponent vector of g with respect to the generators of pcp. This is the exponent vector of gN with respect to the igs of U/N.
PcpGroupByPcp( pcp )
returns the group whose defining generators correspond to the generators of pcp.
gap> G := DihedralPcpGroup(0); Pcp-group with orders [ 2, 0 ] gap> pcp := Pcp(G); Pcp [ g1, g2 ] with orders [ 2, 0 ] gap> pcp[1]; g1 gap> Length(pcp); 2 gap> RelativeOrdersOfPcp(pcp); [ 2, 0 ] gap> DenominatorOfPcp(pcp); [ ] gap> NumeratorOfPcp(pcp); [ g1, g2 ] gap> GroupOfPcp(pcp); Pcp-group with orders [ 2, 0 ] gap> OneOfPcp(pcp); identity
gap> G := PcpExamples[5]; Pcp-group with orders [ 2, 0, 0, 0 ] gap> D := DerivedSubgroup( G ); Pcp-group with orders [ 0, 0, 0 ] gap> GeneratorsOfGroup( G ); [ g1, g2, g3, g4 ] gap> GeneratorsOfGroup( D ); [ g2^-2, g3^-2, g4^2 ] # an ordinary pcp for G / D gap> pcp1 := Pcp( G, D ); Pcp [ g1, g2, g3, g4 ] with orders [ 2, 2, 2, 2 ] # a pcp for G/D in independent generators gap> pcp2 := Pcp( G, D, "snf" ); Pcp [ g2, g3, g1 ] with orders [ 2, 2, 4 ] gap> g := Random( G ); g1*g2^-4*g3*g4^2 # compute the exponent vector of g in G/D wrt pcp1 gap> ExponentsByPcp( pcp1, g ); [ 1, 0, 1, 0 ] # compute the exponent vector of g in G/D wrt pcp2 gap> ExponentsByPcp( pcp2, g ); [ 0, 1, 1 ]
2.9 Factor groups of pcp-groups
Pcp's for subfactors of pcp-groups have already been described above. These are usually used within algorithms to compute with pcp-groups. However, it is also possible to explicitly construct factor groups and their corresponding natural homomorphisms.
NaturalHomomorphism( G, N )
returns the natural homomorphism G \ra G/N. Its image is the factor group G/N.
`G/N
FactorGroup( G, N )
returns the desired factor as pcp-group without giving the explicit
homomorphism. This function is just a wrapper for
PcpGroupByPcp( Pcp( G, N ) ).
2.10 Homomorphisms for pcp-groups
IsPcpGHBI is a representation used to define group homomorphisms by generators and images from a pcp-group into another pcp-group. Such homomorphisms can be compared and multiplied. Moreover, we provide the following functions.
bigbreak IsToPcpGHBI is a representation used to define group homomorphisms by generators and images from an arbitrary group into a pcp-group. Here, only very restricted functionality is provided. This is mostly used for converting other groups to pcp-groups.
GroupHomomorphismByImages( G, H, gens, imgs )
returns the homomorphism from the (pcp-) group G to the pcp-group H mapping the generators of G in the list gens to the corresponding images in the list imgs of elements of H.
Kernel( hom )
returns the kernel of the homomorphism hom from a pcp-group to a pcp-group.
Image( hom )
Image( hom, U )
Image( hom, g )
returns the image of the whole group, of U and of g, respectively, under the homomorphism hom.
PreImage( hom, U )
returns the complete preimage of the subgroup U under the homomorphism home. If the domain of hom is not a pcp-group, then this function only works properly if hom is injective.
PreImagesRepresentative( hom, g )
returns a preimage of the element g under the homomorphism hom.
IsInjective( hom )
checks if the homomorphism hom is injective.
2.11 Changing the defining pc-presentation
The following functions should actually return isomorphisms.
RefinedPcpGroup( G )
returns a new pcp-group isomorphic to G whose defining polycyclic presentation is refined; that is, the corresponding polycyclic series has prime or infinite factors only. If H is the new group, then H!·bijection is the isomorphism G \ra H.
PcpGroupBySeries( ser )
returns a new pcp-group isomorphic to the first subgroup G of the given series ser such that its defining pcp refines the given series. The series must be subnormal and H!·bijection is the isomorphism G \ra H.
gap> G := DihedralPcpGroup(0); Pcp-group with orders [ 2, 0 ] gap> U := Subgroup( G, [Pcp(G)[2]^1440]); Pcp-group with orders [ 0 ] gap> F := G/U; Pcp-group with orders [ 2, 1440 ] gap> RefinedPcpGroup(F); Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 3, 3, 5 ] gap> ser := [G, U, TrivialSubgroup(G)]; [ Pcp-group with orders [ 2, 0 ], Pcp-group with orders [ 0 ], Pcp-group with orders [ ] ] gap> PcpGroupBySeries(ser); Pcp-group with orders [ 2, 1440, 0 ]
IsomorphismPcpGroup( G )
returns a pcp-group isomorphic to G if G is a pc-group or a soluble permutation group.
IsomorphismPcGroup( G )
returns a pc-group if G is a finite pcp-group.
There are the following generic pcp-groups available.
AbelianPcpGroup( n, rels )
constructs the abelian group on n generators such that generator i has order rels[i]. If this order is infinite, then rels[i] should be either unbound or 0.
DihedralPcpGroup( n )
constructs the dihedral group of order n. If n is not an even integer, then 'fail' is returned. If n is not an integer, then the infinite dihedral group is returned.
UnitriangularPcpGroup( n )
returns a pcp-group isomorphic to the group of upper triangular matrices in GL(n, Z).
SubgroupUnitriangularPcpGroup( mats )
returns the subgroup generated by the upper triangular matrices in mats as a pcp-group.
ExampleOfMetabelianGroup( a, k )
returns an example of a metabelian group.
PcpExamples
is a list of pcp-groups which can serve as first examples to try some of the functions in this package.
EddiesExamples
a list with more examples provided by Eddie Lo.
NqExamples
a list of nilpotent pcp-groups generated by the Nilpotent Quotient Algorithm.
[Up] [Previous] [Next] [Index]
Polycyclic manual