A group G is polycyclic if there exists a subnormal series G = C1 > C2 > ¼ > Cn > Cn+1 = {1} with cyclic factors. Such a series is called pc series of G.
Every polycyclic group is solvable and every finite solvable group is polycyclic. However, there are infinite solvable groups which are not polycyclic.
In GAP there exists a large number of methods for polycyclic groups which are based upon the polycyclic structure of these groups. These methods are usually very efficient and hence GAP tries to use them whenever possible.
In GAP 3 these methods have been available for AgGroups only; that is, for groups defined via a power-commutator presentation, see Chapter Pc Groups for the GAP 4 analogon. This has changed in GAP 4 where these methods can be applied to many types of groups. For example, the methods can be applied to permutation groups or matrix groups which are known to be polycyclic. The only exeption is the representation as finitely presented group for which the polycyclic methods cannot be used in general.
At the current state of implementations the methods for polycyclic groups can only be applied to finite groups. However, a more general implementation is planned.
40.1 Polycyclic Generating Systems
Let G be a polycyclic group with a pc series as above. A polycyclic generating sequence (pcgs for short) of G is a sequence P : = (g1, ¼, gn) of elements of G such that Ci = áCi+1, gi ñ for 1 £ i £ n. Note that each polycyclic group has a pcgs, but except for very small groups, a pcgs is not unique.
For each index i the subsequence of elements (gi, ¼, gn) forms a pcgs of the subgroup Ci. In particular, these tails generate the subgroups of the pc series and hence we say that the pc series is determined by P.
Let ri be the index of Ci+1 in Ci which is either a finite positive number or infinity. Then ri is the order of gi Ci+1 and we call the resulting list of indices the relative orders of the pcgs P.
Moreover, with respect to a given pcgs (g1, ¼, gn) each element g of G can be represented in a unique way as a product g = g1e1 ·g2e2 ¼gnen with exponents ei Î {0, ¼, ri-1}, if ri is finite, and ei Î Z otherwise. Words of this form are called normal words or words in normal form. Then the integer vector [e1, ¼, en] is called the exponent vector of the element g. Furthermore, the smallest index k such that ek ¹ 0 is called the depth of g and ek is the leading exponent of g.
For many applications we have to assume that each of the relative orders ri is either a prime or infinity. This is equivalent to saying that there are no trivial factors in the pc series and the finite factors of the pc series are maximal refined. Then we obtain that ri is the order of g Ci+1 for all elements g in Ci \Ci+1 and we call ri the relative order of the element g.
Suppose a group G is given; for example, let G be a permutation
or matrix group. Then we can ask GAP to compute a pcgs of this group.
If G is not polycyclic, the result will be fail.
Note that these methods can only be applied if G is not given as finitely presented group. For finitely presented groups one can try to compute a pcgs via the polycyclic quotient methods, see Quotient Methods.
Note also that a pcgs behaves like a list.
Pcgs( G ) A
returns a pcgs for the group G.
If grp is not polycyclic it returns fail and this result is not
stored as attribute value, in particular in this case the filter
HasPcgs is not set for G!
IsPcgs( obj ) C
The category of pcgs.
gap> G := Group((1,2,3,4),(1,2));; gap> p := Pcgs(G); [ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ] gap> IsPcgs( p ); true gap> p[1]; (3,4)
gap> G := Group((1,2,3,4,5),(1,2));; gap> Pcgs(G); fail
CanEasilyComputePcgs( grp ) F
This filter indicates whether it is possible to compute a pcgs for grp cheaply. Clearly, grp must be polycyclic in this case. However, not for every polycyclic group there is a method to compute a pcgs at low costs. This filter is used in the method selection mainly. Note that this filter may change its value from false to true.
gap> G := Group( (1,2,3,4),(1,2) ); Group([ (1,2,3,4), (1,2) ]) gap> CanEasilyComputePcgs(G); false gap> Pcgs(G); [ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ] gap> CanEasilyComputePcgs(G); true
In a number of situations it might be useful to supply a pgcs to a group.
PcgsByPcSequence( fam, pcs ) O
PcgsByPcSequenceNC( fam, pcs ) O
constructs a pcgs for the elements family fam from the elements in the
list pcs. The elements must lie in the family fam.
PcgsByPcSequence(NC) will always create a new pcgs which is not
induced by any other pcgs.
gap> fam := FamilyObj( (1,2) );; # the family of permutations gap> p := PcgsByPcSequence( fam, [(1,2),(1,2,3)] ); [ (1,2), (1,2,3) ] gap> RelativeOrders(p); [ 2, 3 ] gap> ExponentsOfPcElement( p, (1,3,2) ); [ 0, 2 ]
Note that the elementary operations for such a pcgs might be rather
inefficient, since GAP has to use generic methods in this case.
It might be helpful to supply the relative orders of the self-defined
pcgs as well by SetRelativeOrders( pcgs, orders ).
See also IsPrimeOrdersPcgs.
RelativeOrders( pcgs ) A
returns the list of relative orders of the pcgs pcgs.
the list of relative orders of the pcgs pcgs.
IsFiniteOrdersPcgs( pcgs ) P
tests whether the relative orders of pcgs are all finite.
IsPrimeOrdersPcgs( pcgs ) P
tests whether the relative orders of pcgs are prime numbers.
Many algorithms require a pcgs to have this property. The
operation IsomorphismRefinedPcGroup (see IsomorphismRefinedPcGroup)
can be of help here.
PcSeries( pcgs ) A
returns the subnormal series determined by pcgs.
GroupOfPcgs( pcgs ) A
The group generated by pcgs.
OneOfPcgs( pcgs ) A
The identity of the group generated by pcgs.
gap> G := Group( (1,2,3,4),(1,2) );; p := Pcgs(G);; gap> RelativeOrders(p); [ 2, 3, 2, 2 ] gap> IsFiniteOrdersPcgs(p); true gap> IsPrimeOrdersPcgs(p); true gap> PcSeries(p); [ Group([ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ]), Group([ (2,4,3), (1,4)(2,3), (1,2)(3,4) ]), Group([ (1,4)(2,3), (1,2)(3,4) ]), Group([ (1,2)(3,4) ]), Group(()) ]
RelativeOrderOfPcElement( pcgs, elm ) O
The relative order of elm with respect to the prime order pcgs pcgs.
ExponentOfPcElement( pcgs, elm, pos ) O
returns the pos-th exponent of elm with respect to pcgs.
ExponentsOfPcElement( pcgs, elm ) O
ExponentsOfPcElement( pcgs, elm, posran ) O
returns the exponents of elm with respect to pcgs. The second form returns the exponents in the positions given in posran.
DepthOfPcElement( pcgs, elm ) O
returns the depth of the element elm with respect to pcgs.
LeadingExponentOfPcElement( pcgs, elm ) O
returns the leading exponent of elm with respect to pcgs.
PcElementByExponents( pcgs, list ) O
PcElementByExponentsNC( pcgs, list ) O
PcElementByExponentsNC( pcgs, basisind, list ) O
returns the element corresponding to the exponent vector list with
respect to pcgs. The exponents in list must be in the range of
permissible exponents for pcgs. It is not guaranteed that
PcElementByExponents will reduce the exponents modulo the relative
orders. (You should use the operation LinearCombinationPcgs for this
purpose.) The NC version does not check that the lengths of the
lists fit together and does not check the exponent range.
The third version gives exponents only wrt. the generators in pcgs indexed by basisind.
LinearCombinationPcgs( pcgs, list ) O
returns the product Õipcgs [i]list [i]. In contrast to
PcElementByExponents this permits negative exponents.
gap> G := Group( (1,2,3,4),(1,2) );; P := Pcgs(G);; gap> g := PcElementByExponents(P, [0,1,1,1]); (1,3,4) gap> ExponentsOfPcElement(P, g); [ 0, 1, 1, 1 ]
SiftedPcElement( pcgs, elm ) O
sifts elm through pcgs, reducing it if the depth is the same as the depth of one of the generators in pcgs. Thus the identity is returned if elm lies in the group generated by pcgs.
CanonicalPcElement( ipcgs, elm ) O
reduces elm at the induces pcgs ipcgs such that the exponents of the reduced result r are zero at the depths for which there are generators in ipcgs. Elements, whose quotient lies in the group generated by ipcgs yield the same canonical element.
ReducedPcElement( pcgs, x, y ) O
reduces the element x by dividing off (from the left) a power of y such that the leading coefficient of the result with repect to pcgs becomes zero. The elements x and y therefore have to have the same depth.
CleanedTailPcElement( pcgs, elm, dep ) O
returns an element in the span of pcgs whose exponents for indices 1 to dep -1 with respect to pcgs are the same as those of elm, the remaining exponents are undefined. This can be used to obtain more ``simple'' elements if only representatives in a factor are required, see Factor Groups of Polycyclic Groups - Modulo Pcgs.
The difference to HeadPcElementByNumber (see HeadPcElementByNumber)
is that HeadPcElementByNumber is guaranteed to zero out trailing
coefficients while CleantedTailPcElement will only do this if it can be
done cheaply.
HeadPcElementByNumber( pcgs, elm, dep ) O
returns an element in the span of pcgs whose exponents for indices 1 to dep -1 with respect to pcgs are the same as those of elm, the remaining exponents are zero. This can be used to obtain more ``simple'' elements if only representatives in a factor are required.
40.6 Exponents of Special Products
There are certain products of elements whose exponents are used often within algorithms, and which might be obtained more easily than by computing the product first and to obtain its exponents afterwards. The operations in this section provide a way to obtain such exponent vectors directly.
(The circumstances under which these operations give a speedup depend very much on the pcgs and the representation of elements that is used. So the following operations are not guaranteed to give a speedup in every case, however the default methods are not slower than to compute the exponents of a product and thus these operations should always be used if applicable.)
ExponentsConjugateLayer( mpcgs, elm, e ) O
Computes the exponents of elm e with respect to mpcgs. elm must be in the span of mpcgs, e an pc element in the span of the parent pcgs of mpcgs and mpcgs must be the modulo pcgs for an abelian layer. (This is the usual case when acting on a chief factor). In this case if mpcgs is induced by the family pcgs, the exponents can be computed directly by looking up htm#SECT011">Pcgs and Normal Series
40.1 Polycyclic Generating Systems
Let G be a polycyclic group with a pc series as above. A polycyclic generating sequence (pcgs for short) of G is a sequence P : = (g1, ¼, gn) of elements of G such that Ci = áCi+1, gi ñ for 1 £ i £ n. Note that each polycyclic group has a pcgs, but except for very small groups, a pcgs is not unique.
For each index i the subsequence of elements (gi, ¼, gn) forms a pcgs of the subgroup Ci. In particular, these tails generate the subgroups of the pc series and hence we say that the pc series is determined by P.
Let ri be the index of Ci+1 in Ci which is either a finite positive number or infinity. Then ri is the order of gi Ci+1 and we call the resulting list of indices the relative orders of the pcgs P.
Moreover, with respect to a given pcgs (g1, ¼, gn) each element g of G can be represented in a unique way as a product g = g1e1 ·g2e2 ¼gnen with exponents ei Î {0, ¼, ri-1}, if ri is finite, and ei Î Z otherwise. Words of this form are called normal words or words in normal form. Then the integer vector [e1, ¼, en] is called the exponent vector of the element g. Furthermore, the smallest index k such that ek ¹ 0 is called the depth of g and ek is the leading exponent of g.
For many applications we have to assume that each of the relative orders ri is either a prime or infinity. This is equivalent to saying that there are no trivial factors in the pc series and the finite factors of the pc series are maximal refined. Then we obtain that ri is the order of g Ci+1 for all elements g in Ci \Ci+1 and we call ri the relative order of the element g.
Suppose a group G is given; for example, let G be a permutation
or matrix group. Then we can ask GAP to compute a pcgs of this group.
If G is not polycyclic, the result will be fail.
Note that these methods can only be applied if G is not given as finitely presented group. For finitely presented groups one can try to compute a pcgs via the polycyclic quotient methods, see Quotient Methods.
Note also that a pcgs behaves like a list.
Pcgs( G ) A
returns a pcgs for the group G.
If grp is not polycyclic it returns fail and this result is not
stored as attribute value, in particular in this case the filter
HasPcgs is not set for G!
IsPcgs( obj ) C
The category of pcgs.
gap> G := Group((1,2,3,4),(1,2));; gap> p := Pcgs(G); [ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ] gap> IsPcgs( p ); true gap> p[1]; (3,4)
gap> G := Group((1,2,3,4,5),(1,2));; gap> Pcgs(G); fail
CanEasilyComputePcgs( grp ) F
This filter indicates whether it is possible to compute a pcgs for grp cheaply. Clearly, grp must be polycyclic in this case. However, not for every polycyclic group there is a method to compute a pcgs at low costs. This filter is used in the method selection mainly. Note that this filter may change its value from false to true.
gap> G := Group( (1,2,3,4),(1,2) ); Group([ (1,2,3,4), (1,2) ]) gap> CanEasilyComputePcgs(G); false gap> Pcgs(G); [ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ] gap> CanEasilyComputePcgs(G); true
In a number of situations it might be useful to supply a pgcs to a group.
PcgsByPcSequence( fam, pcs ) O
PcgsByPcSequenceNC( fam, pcs ) O
constructs a pcgs for the elements family fam from the elements in the
list pcs. The elements must lie in the family fam.
PcgsByPcSequence(NC) will always create a new pcgs which is not
induced by any other pcgs.
gap> fam := FamilyObj( (1,2) );; # the family of permutations gap> p := PcgsByPcSequence( fam, [(1,2),(1,2,3)] ); [ (1,2), (1,2,3) ] gap> RelativeOrders(p); [ 2, 3 ] gap> ExponentsOfPcElement( p, (1,3,2) ); [ 0, 2 ]
Note that the elementary operations for such a pcgs might be rather
inefficient, since GAP has to use generic methods in this case.
It might be helpful to supply the relative orders of the self-defined
pcgs as well by SetRelativeOrders( pcgs, orders ).
See also IsPrimeOrdersPcgs.
RelativeOrders( pcgs ) A
returns the list of relative orders of the pcgs pcgs.
the list of relative orders of the pcgs pcgs.
IsFiniteOrdersPcgs( pcgs ) P
tests whether the relative orders of pcgs are all finite.
IsPrimeOrdersPcgs( pcgs ) P
tests whether the relative orders of pcgs are prime numbers.
Many algorithms require a pcgs to have this property. The
operation IsomorphismRefinedPcGroup (see IsomorphismRefinedPcGroup)
can be of help here.
PcSeries( pcgs ) A
returns the subnormal series determined by pcgs.
GroupOfPcgs( pcgs ) A
The group generated by pcgs.
OneOfPcgs( pcgs ) A
The identity of the group generated by pcgs.
gap> G := Group( (1,2,3,4),(1,2) );; p := Pcgs(G);; gap> RelativeOrders(p); [ 2, 3, 2, 2 ] gap> IsFiniteOrdersPcgs(p); true gap> IsPrimeOrdersPcgs(p); true gap> PcSeries(p); [ Group([ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ]), Group([ (2,4,3), (1,4)(2,3), (1,2)(3,4) ]), Group([ (1,4)(2,3), (1,2)(3,4) ]), Group([ (1,2)(3,4) ]), Group(()) ]
RelativeOrderOfPcElement( pcgs, elm ) O
The relative order of elm with respect to the prime order pcgs pcgs.
ExponentOfPcElement( pcgs, elm, pos ) O
returns the pos-th exponent of elm with respect to pcgs.
ExponentsOfPcElement( pcgs, elm ) O
ExponentsOfPcElement( pcgs, elm, posran ) O
returns the exponents of elm with respect to pcgs. The second form returns the exponents in the positions given in posran.
DepthOfPcElement( pcgs, elm ) O
returns the depth of the element elm with respect to pcgs.
LeadingExponentOfPcElement( pcgs, elm ) O
returns the leading exponent of elm with respect to pcgs.
PcElementByExponents( pcgs, list ) O
PcElementByExponentsNC( pcgs, list ) O
PcElementByExponentsNC( pcgs, basisind, list ) O
returns the element corresponding to the exponent vector list with
respect to pcgs. The exponents in list must be in the range of
permissible exponents for pcgs. It is not guaranteed that
PcElementByExponents will reduce the exponents modulo the relative
orders. (You should use the operation LinearCombinationPcgs for this
purpose.) The NC version does not check that the lengths of the
lists fit together and does not check the exponent range.
The third version gives exponents only wrt. the generators in pcgs indexed by basisind.
LinearCombinationPcgs( pcgs, list ) O
returns the product Õipcgs [i]list [i]. In contrast to
PcElementByExponents this permits negative exponents.
gap> G := Group( (1,2,3,4),(1,2) );; P := Pcgs(G);; gap> g := PcElementByExponents(P, [0,1,1,1]); (1,3,4) gap> ExponentsOfPcElement(P, g); [ 0, 1, 1, 1 ]
SiftedPcElement( pcgs, elm ) O
sifts elm through pcgs, reducing it if the depth is the same as the depth of one of the generators in pcgs. Thus the identity is returned if elm lies in the group generated by pcgs.
CanonicalPcElement( ipcgs, elm ) O
reduces elm at the induces pcgs ipcgs such that the exponents of the reduced result r are zero at the depths for which there are generators in ipcgs. Elements, whose quotient lies in the group generated by ipcgs yield the same canonical element.
ReducedPcElement( pcgs, x, y ) O
reduces the element x by dividing off (from the left) a power of y such that the leading coefficient of the result with repect to pcgs becomes zero. The elements x and y therefore have to have the same depth.
CleanedTailPcElement( pcgs, elm, dep ) O
returns an element in the span of pcgs whose exponents for indices 1 to dep -1 with respect to pcgs are the same as those of elm, the remaining exponents are undefined. This can be used to obtain more ``simple'' elements if only representatives in a factor are required, see Factor Groups of Polycyclic Groups - Modulo Pcgs.
The difference to HeadPcElementByNumber (see HeadPcElementByNumber)
is that HeadPcElementByNumber is guaranteed to zero out trailing
coefficients while CleantedTailPcElement will only do this if it can be
done cheaply.
HeadPcElementByNumber( pcgs, elm, dep ) O
returns an element in the span of pcgs whose exponents for indices 1 to dep -1 with respect to pcgs are the same as those of elm, the remaining exponents are zero. This can be used to obtain more ``simple'' elements if only representatives in a factor are required.
40.6 Exponents of Special Products
There are certain products of elements whose exponents are used often within algorithms, and which might be obtained more easily than by computing the product first and to obtain its exponents afterwards. The operations in this section provide a way to obtain such exponent vectors directly.
(The circumstances under which these operations give a speedup depend very much on the pcgs and the representation of elements that is used. So the following operations are not guaranteed to give a speedup in every case, however the default methods are not slower than to compute the exponents of a product and thus these operations should always be used if applicable.)
ExponentsConjugateLayer( mpcgs, elm, e ) O
Computes the exponents of elm e with respect to mpcgs. elm must be in the span of mpcgs, e an pc element in the span of the parent pcgs of mpcgs and mpcgs must be the modulo pcgs for an abelian layer. (This is the usual case when acting on a chief factor). In this case if mpcgs is induced by the family pcgs, the exponents can be computed directly by looking up htm#SECT011">Pcgs and Normal Series
40.1 Polycyclic Generating Systems
Let G be a polycyclic group with a pc series as above. A polycyclic generating sequence (pcgs for short) of G is a sequence P : = (g1, ¼, gn) of elements of G such that Ci = áCi+1, gi ñ for 1 £ i £ n. Note that each polycyclic group has a pcgs, but except for very small groups, a pcgs is not unique.
For each index i the subsequence of elements (gi, ¼, gn) forms a pcgs of the subgroup Ci. In particular, these tails generate the subgroups of the pc series and hence we say that the pc series is determined by P.
Let ri be the index of Ci+1 in Ci which is either a finite positive number or infinity. Then ri is the order of gi Ci+1 and we call the resulting list of indices the relative orders of the pcgs P.
Moreover, with respect to a given pcgs (g1, ¼, gn) each element g of G can be represented in a unique way as a product g = g1e1 ·g2e2 ¼gnen with exponents ei Î {0, ¼, ri-1}, if ri is finite, and ei Î Z otherwise. Words of this form are called normal words or words in normal form. Then the integer vector [e1, ¼, en] is called the exponent vector of the element g. Furthermore, the smallest index k such that ek ¹ 0 is called the depth of g and ek is the leading exponent of g.
For many applications we have to assume that each of the relative orders ri is either a prime or infinity. This is equivalent to saying that there are no trivial factors in the pc series and the finite factors of the pc series are maximal refined. Then we obtain that ri is the order of g Ci+1 for all elements g in Ci \Ci+1 and we call ri the relative order of the element g.
Suppose a group G is given; for example, let G be a permutation
or matrix group. Then we can ask GAP to compute a pcgs of this group.
If G is not polycyclic, the result will be fail.
Note that these methods can only be applied if G is not given as finitely presented group. For finitely presented groups one can try to compute a pcgs via the polycyclic quotient methods, see Quotient Methods.
Note also that a pcgs behaves like a list.
Pcgs( G ) A
returns a pcgs for the group G.
If grp is not polycyclic it returns fail and this result is not
stored as attribute value, in particular in this case the filter
HasPcgs is not set for G!
IsPcgs( obj ) C
The category of pcgs.
gap> G := Group((1,2,3,4),(1,2));; gap> p := Pcgs(G); [ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ] gap> IsPcgs( p ); true gap> p[1]; (3,4)
gap> G := Group((1,2,3,4,5),(1,2));; gap> Pcgs(G); fail
CanEasilyComputePcgs( grp ) F
This filter indicates whether it is possible to compute a pcgs for grp cheaply. Clearly, grp must be polycyclic in this case. However, not for every polycyclic group there is a method to compute a pcgs at low costs. This filter is used in the method selection mainly. Note that this filter may change its value from false to true.
gap> G := Group( (1,2,3,4),(1,2) ); Group([ (1,2,3,4), (1,2) ]) gap> CanEasilyComputePcgs(G); false gap> Pcgs(G); [ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ] gap> CanEasilyComputePcgs(G); true
In a number of situations it might be useful to supply a pgcs to a group.
PcgsByPcSequence( fam, pcs ) O
PcgsByPcSequenceNC( fam, pcs ) O
constructs a pcgs for the elements family fam from the elements in the
list pcs. The elements must lie in the family fam.
PcgsByPcSequence(NC) will always create a new pcgs which is not
induced by any other pcgs.
gap> fam := FamilyObj( (1,2) );; # the family of permutations gap> p := PcgsByPcSequence( fam, [(1,2),(1,2,3)] ); [ (1,2), (1,2,3) ] gap> RelativeOrders(p); [ 2, 3 ] gap> ExponentsOfPcElement( p, (1,3,2) ); [ 0, 2 ]
Note that the elementary operations for such a pcgs might be rather
inefficient, since GAP has to use generic methods in this case.
It might be helpful to supply the relative orders of the self-defined
pcgs as well by SetRelativeOrders( pcgs, orders ).
See also IsPrimeOrdersPcgs.
RelativeOrders( pcgs ) A
returns the list of relative orders of the pcgs pcgs.
the list of relative orders of the pcgs pcgs.
IsFiniteOrdersPcgs( pcgs ) P
tests whether the relative orders of pcgs are all finite.
IsPrimeOrdersPcgs( pcgs ) P
tests whether the relative orders of pcgs are prime numbers.
Many algorithms require a pcgs to have this property. The
operation IsomorphismRefinedPcGroup (see IsomorphismRefinedPcGroup)
can be of help here.
PcSeries( pcgs ) A
returns the subnormal series determined by pcgs.
GroupOfPcgs( pcgs ) A
The group generated by pcgs.
OneOfPcgs( pcgs ) A
The identity of the group generated by pcgs.
gap> G := Group( (1,2,3,4),(1,2) );; p := Pcgs(G);; gap> RelativeOrders(p); [ 2, 3, 2, 2 ] gap> IsFiniteOrdersPcgs(p); true gap> IsPrimeOrdersPcgs(p); true gap> PcSeries(p); [ Group([ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ]), Group([ (2,4,3), (1,4)(2,3), (1,2)(3,4) ]), Group([ (1,4)(2,3), (1,2)(3,4) ]), Group([ (1,2)(3,4) ]), Group(()) ]
RelativeOrderOfPcElement( pcgs, elm ) O
The relative order of elm with respect to the prime order pcgs pcgs.
ExponentOfPcElement( pcgs, elm, pos ) O
returns the pos-th exponent of elm with respect to pcgs.
ExponentsOfPcElement( pcgs, elm ) O
ExponentsOfPcElement( pcgs, elm, posran ) O
returns the exponents of elm with respect to pcgs. The second form returns the exponents in the positions given in posran.
DepthOfPcElement( pcgs, elm ) O
returns the depth of the element elm with respect to pcgs.
LeadingExponentOfPcElement( pcgs, elm ) O
returns the leading exponent of elm with respect to pcgs.
PcElementByExponents( pcgs, list ) O
PcElementByExponentsNC( pcgs, list ) O
PcElementByExponentsNC( pcgs, basisind, list ) O
returns the element corresponding to the exponent vector list with
respect to pcgs. The exponents in list must be in the range of
permissible exponents for pcgs. It is not guaranteed that
PcElementByExponents will reduce the exponents modulo the relative
orders. (You should use the operation LinearCombinationPcgs for this
purpose.) The NC version does not check that the lengths of the
lists fit together and does not check the exponent range.
The third version gives exponents only wrt. the generators in pcgs indexed by basisind.
LinearCombinationPcgs( pcgs, list ) O
returns the product Õipcgs [i]list [i]. In contrast to
PcElementByExponents this permits negative exponents.
gap> G := Group( (1,2,3,4),(1,2) );; P := Pcgs(G);; gap> g := PcElementByExponents(P, [0,1,1,1]); (1,3,4) gap> ExponentsOfPcElement(P, g); [ 0, 1, 1, 1 ]
SiftedPcElement( pcgs, elm ) O
sifts elm through pcgs, reducing it if the depth is the same as the depth of one of the generators in pcgs. Thus the identity is returned if elm lies in the group generated by pcgs.
CanonicalPcElement( ipcgs, elm ) O
reduces elm at the induces pcgs ipcgs such that the exponents of the reduced result r are zero at the depths for which there are generators in ipcgs. Elements, whose quotient lies in the group generated by ipcgs yield the same canonical element.
ReducedPcElement( pcgs, x, y ) O
reduces the element x by dividing off (from the left) a power of y such that the leading coefficient of the result with repect to pcgs becomes zero. The elements x and y therefore have to have the same depth.
CleanedTailPcElement( pcgs, elm, dep ) O
returns an element in the span of pcgs whose exponents for indices 1 to dep -1 with respect to pcgs are the same as those of elm, the remaining exponents are undefined. This can be used to obtain more ``simple'' elements if only representatives in a factor are required, see Factor Groups of Polycyclic Groups - Modulo Pcgs.
The difference to HeadPcElementByNumber (see HeadPcElementByNumber)
is that HeadPcElementByNumber is guaranteed to zero out trailing
coefficients while CleantedTailPcElement will only do this if it can be
done cheaply.
HeadPcElementByNumber( pcgs, elm, dep ) O
returns an element in the span of pcgs whose exponents for indices 1 to dep -1 with respect to pcgs are the same as those of elm, the remaining exponents are zero. This can be used to obtain more ``simple'' elements if only representatives in a factor are required.
40.6 Exponents of Special Products
There are certain products of elements whose exponents are used often within algorithms, and which might be obtained more easily than by computing the product first and to obtain its exponents afterwards. The operations in this section provide a way to obtain such exponent vectors directly.
(The circumstances under which these operations give a speedup depend very much on the pcgs and the representation of elements that is used. So the following operations are not guaranteed to give a speedup in every case, however the default methods are not slower than to compute the exponents of a product and thus these operations should always be used if applicable.)
ExponentsConjugateLayer( mpcgs, elm, e ) O
Computes the exponents of elm e with respect to mpcgs. elm must be in the span of mpcgs, e an pc element in the span of the parent pcgs of mpcgs and mpcgs must be the modulo pcgs for an abelian layer. (This is the usual case when acting on a chief factor). In this case if mpcgs is induced by the family pcgs, the exponents can be computed directly by looking up htm#SECT011">Pcgs and Normal Series
40.1 Polycyclic Generating Systems
Let G be a polycyclic group with a pc series as above. A polycyclic generating sequence (pcgs for short) of G is a sequence P : = (g1, ¼, gn) of elements of G such that Ci = áCi+1, gi ñ for 1 £ i £ n. Note that each polycyclic group has a pcgs, but except for very small groups, a pcgs is not unique.
For each index i the subsequence of elements (gi, ¼, gn) forms a pcgs of the subgroup Ci. In particular, these tails generate the subgroups of the pc series and hence we say that the pc series is determined by P.
Let ri be the index of Ci+1 in Ci which is either a finite positive number or infinity. Then ri is the order of gi Ci+1 and we call the resulting list of indices the relative orders of the pcgs P.
Moreover, with respect to a given pcgs (g1, ¼, gn) each element g of G can be represented in a unique way as a product g = g1e1 ·g2e2 ¼gnen with exponents ei Î {0, ¼, ri-1}, if ri is finite, and ei Î Z otherwise. Words of this form are called normal words or words in normal form. Then the integer vector [e1, ¼, en] is called the exponent vector of the element g. Furthermore, the smallest index k such that ek ¹ 0 is called the depth of g and ek is the leading exponent of g.
For many applications we have to assume that each of the relative orders ri is either a prime or infinity. This is equivalent to saying that there are no trivial factors in the pc series and the finite factors of the pc series are maximal refined. Then we obtain that ri is the order of g Ci+1 for all elements g in Ci \Ci+1 and we call ri the relative order of the element g.
Suppose a group G is given; for example, let G be a permutation
or matrix group. Then we can ask GAP to compute a pcgs of this group.
If G is not polycyclic, the result will be fail.
Note that these methods can only be applied if G is not given as finitely presented group. For finitely presented groups one can try to compute a pcgs via the polycyclic quotient methods, see Quotient Methods.
Note also that a pcgs behaves like a list.
Pcgs( G ) A
returns a pcgs for the group G.
If grp is not polycyclic it returns fail and this result is not
stored as attribute value, in particular in this case the filter
HasPcgs is not set for G!
IsPcgs( obj ) C
The category of pcgs.
gap> G := Group((1,2,3,4),(1,2));; gap> p := Pcgs(G); [ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ] gap> IsPcgs( p ); true gap> p[1]; (3,4)
gap> G := Group((1,2,3,4,5),(1,2));; gap> Pcgs(G); fail
CanEasilyComputePcgs( grp ) F
This filter indicates whether it is possible to compute a pcgs for grp cheaply. Clearly, grp must be polycyclic in this case. However, not for every polycyclic group there is a method to compute a pcgs at low costs. This filter is used in the method selection mainly. Note that