Ag words are the GAP3 datatype for elements of finite polycyclic groups. Unlike permutations, which are all considered to be elements of one large symmetric group, each ag word belongs to a specified group. Only ag words of the same finite polycyclic group can be multiplied.
The following sections describe ag words and their parent groups (see More about Ag Words), how ag words are compared (see Ag Word Comparisons), functions for ag words and some low level functions for ag words (starting at CentralWeight and CanonicalAgWord).
For operations and functions defined for group elements in general see Comparisons of Group Elements, Operations for Group Elements.
Let G be a group and G = G0 > G1 > ... > Gn = 1 be a subnormal series of G ≠ 1 with finite cyclic factors, i.e., Gi \lhd Gi-1 for all i=1, ..., n and Gi-1 = 〈 Gi, gi 〉. Then G will be called an ag group with AG generating sequence or, for short, AG system (g1, ..., gn). Let oi be the order of Gi-1 / Gi. If all o1, ..., on are primes the system (g1, ..., gn) is called a PAG system . With respect to a given AG system the group G has a so called power-commutator presentation
and a so called power-conjugate presentation
For both kinds of presentations we shall use the term AG presentation. Each element g of G can be expressed uniquely in the form
We call the composition series G0 > G1 > ... > Gn the AG series of G and define νi( g ) := νi. If νi = 0 for i = 1, ..., k-1 and νk ≠ 0, we call νk the leading exponent and k the depth of g and denote them by νk =: λ( g ) and k =: δ( g ). We call ok the relative order of g.
Each element g of G is called ag word and we say that G is the
parent group of g. A parent group is constructed in GAP3 using
AgGroup
(see AgGroup) or AgGroupFpGroup
(see AgGroupFpGroup).
Our standard example in the following sections is the symmetric group of
degree 4, defined by the following sequence of GAP3 statements. You
should enter them before running any example. For details on
AbstractGenerators
see AbstractGenerator.
gap> a := AbstractGenerator( "a" );; # (1,2) gap> b := AbstractGenerator( "b" );; # (1,2,3) gap> c := AbstractGenerator( "c" );; # (1,3)(2,4) gap> d := AbstractGenerator( "d" );; # (1,2)(3,4) gap> s4 := AgGroupFpGroup( rec( > generators := [ a, b, c, d ], > relators := [ a^2, b^3, c^2, d^2, Comm( b, a ) / b, > Comm( c, a ) / d, Comm( d, a ), > Comm( c, b ) / ( c*d ), Comm( d, b ) / c, > Comm( d, c ) ] ) ); Group( a, b, c, d ) gap> s4.name := "s4";; gap> a := s4.generators[1];; b := s4.generators[2];; gap> c := s4.generators[3];; d := s4.generators[4];;
g < h
g <= h
g >= h
g > h
The operators <
, >
, <=
and >=
return true
if g is strictly
less, strictly greater, not greater, not less, respectively, than h.
Otherwise they return false
.
If g and h have a common parent group they are compared with respect to the AG series of this group. If two ag words have different depths, the one with the higher depth is less than the other one. If two ag words have the same depth but different leading exponents, the one with the smaller leading exponent is less than the other one. Otherwise the leading generator is removed in both ag words and the remaining ag words are compared.
If g and h do not have a common parent group, then the composition lengths of the parent groups are compared.
You can compare ag words with objects of other types. Field elements, unkowns, permutations and abstract words are smaller than ag words. Objects of other types, i.e., functions, lists and records are larger.
gap> 123/47 < a; true gap> (1,2,3,4) < a; true gap> [1,2,3,4] < a; false gap> true < a; false gap> rec() < a; false gap> c < a; true gap> a*b < a*b^2; true
CentralWeight( g )
CentralWeight
returns the central weight of an ag word g, with
respect to the central series used in the combinatorial collector, as
integer.
This presumes that g belongs to a parent group for which the combinatorial collector is used. See ChangeCollector for details.
If g is the identity, 0 is returned.
Note that CentralWeight
allows records that mimic ag words as
arguments.
gap> d8 := AgGroup( Subgroup( s4, [ a, c, d ] ) ); Group( g1, g2, g3 ) gap> ChangeCollector( d8, "combinatorial" ); gap> List( d8.generators, CentralWeight ); [ 1, 1, 2 ]
CompositionLength( g )
Let G be the parent group of the ag word g. Then CompositionLength
returns the length of the AG series of G as integer.
Note that CompositionLength
allows records that mimic ag words as
arguments.
gap> CompositionLength( c ); 5
Depth( g )
Depth
returns the depth of an ag word g with respect to the AG series
of its parent group as integer.
Let G be the parent group of g and G=G0 > ... > Gn={1} the AG series of G. Let δ be the maximal positive integer such that g is an element of Gδ-1. Then δ is the depth of g.
Note that Depth
allows record that mimic ag words as arguments.
gap> Depth( a ); 1 gap> Depth( d ); 4 gap> Depth( a^0 ); 5
IsAgWord( obj )
IsAgWord
returns true
if obj, which can be an arbitrary object, is
an ag word and false
otherwise.
gap> IsAgWord( 5 ); false gap> IsAgWord( a ); true
LeadingExponent( g )
LeadingExponent
returns the leading exponent of an ag word g as
integer.
Let G be the parent group of g and (g1, ..., gn) the AG system of G and let oi be the relative order of gi. Then the element g can be expressed uniquely in the form g1ν1* ...* gnνn for integers νi such that 0 ≤ νi < oi. The leading exponent of g is the first nonzero νi.
If g is the identity 0 is returned.
Although ExponentAgWord( g, Depth( g ) )
returns the leading
exponent of g, too, this function is faster and is able to handle the
identity.
Note that LeadingExponent
allows records that mimic ag words as
arguments.
gap> LeadingExponent( a * b^2 * c^2 * d ); 1 gap> LeadingExponent( b^2 * c^2 * d ); 2
RelativeOrder( g )
RelativeOrder
returns the relative order of an ag word g as integer.
Let G be the parent group of g and G=G0 > ... > Gn={1} the AG series of G. Let δ be the maximal positive integer such that g is an element of Gδ-1. The relative order of g is the index of Gδ+1 in Gδ, that is the order of the factor group Gδ/Gδ+1.
If g is the identity 1 is returned.
Note that RelativeOrder
allows records that mimic agwords as arguments.
gap> RelativeOrder( a ); 2 gap> RelativeOrder( b ); 3 gap> RelativeOrder( b^2 * c * d ); 3
CanonicalAgWord( U, g )
Let U be an ag group with parent group G, let g be an element of
G. Let (u1, ..., um) be an induced generating system of U and
(g1, ..., gn) be a canonical generating system of G. Then
CanonicalAgWord
returns a word x = g * u = gi1e1 * ... *
gikek such that u∈ U and no ij is equal to the depth of
any generator ul.
gap> v4 := MergedCgs( s4, [ a*b^2, c*d ] ); Subgroup( s4, [ a*b^2, c*d ] ) gap> CanonicalAgWord( v4, a*c ); b^2*d gap> CanonicalAgWord( v4, a*b*c*d ); b gap> (a*b*c*d) * (a*b^2); b*c*d gap> last * (c*d); b
DifferenceAgWord( u, v )
DifferenceAgWord
returns an ag word s representing the difference of
the exponent vectors of u and v.
Let G be the parent group of u and v. Let (g1, ..., gn) be the
AG system of G and oi be the relative order or gi. Then u can
be expressed uniquely as g1u1* ...* gnun for integers ui
between 0 and oi-1 and v can be expressed uniquely as g1v1*
...* gnvn for integers vi between 0 and oi-1. The
function DifferenceAgWord
returns an ag word s = g1s1* ...*
gnsn with integer si such that 0 ≤ si < oi and si
≡ ui - vi mod oi.
gap> DifferenceAgWord( a * b, a ); b gap> DifferenceAgWord( a, b ); a*b^2 gap> z27 := CyclicGroup( AgWords, 27 ); Group( c27_1, c27_2, c27_3 ) gap> x := z27.1 * z27.2; c27_1*c27_2 gap> x * x; c27_1^2*c27_2^2 gap> DifferenceAgWord( x, x ); IdAgWord
ReducedAgWord( b, x )
Let b and x be ag words of the same depth, then ReducedAgWord
returns an ag word a such that a is an element of the coset U b,
where U is the cyclic group generated by x, and a has a higher
depth than b and x.
Note that the relative order of b and x must be a prime.
Let p be the relative order of b and x. Let β and ξ be the leading exponent of b and x respectively. Then there exits an integer i such that ξ * i = β modulo p. We can set <a> = x-i b.
Typically this function is used when b and x occur in a generating set of a subgroup W. Then b can be replaced by a in the generating set of W, but a and x have different depth.
gap> ReducedAgWord( a*b^2*c, a ); b^2*c gap> ReducedAgWord( last, b ); c
SiftedAgWord( U, g )
SiftedAgWord
tries to sift an ag word g, which must be an element of
the parent group of an ag group U, through an induced generating system
of U. SiftedAgWord
returns the remainder of this shifting process.
The identity is returned if and only if g is an element of U.
Let u1, ..., um be an induced generating system of U. If there
exists an ui such that ui and g have the same depth, then g is
reduced with ui using ReducedAgWord
(see ReducedAgWord). The
process is repeated until no ui can be found or the g is reduced to
the identity.
SiftedAgWord
allows factor group arguments. See Factor Groups of Ag
Groups for details.
Note that SiftedAgGroup
adds a record component U.shiftInfo
to the
ag group record of U. 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
U.shiftInfo
, otherwise all following results of SiftedAgWord
will
be corrupted.
gap> s3 := Subgroup( s4, [ a, b ] ); Subgroup( s4, [ a, b ] ) gap> SiftedAgWord( s3, a * b^2 * c ); c
SumAgWord( u, v )
SumAgWord
returns an ag word s representing the sum of the exponent
vectors of u and v.
Let G be the parent group of u and v. Let (g1, ..., gn) be the
AG system of G and oi be the relative order or gi. Then u can
be expressed uniquely as g1u1* ...* gnun for integers ui
between 0 and oi-1 and v can be expressed uniquely as g1v1*
...* gnvn for integers vi between 0 and oi-1. Then
SumAgWord
returns an ag word s = g1s1* ...* gnsn with
integer si such that 0 ≤ si < oi and si ≡ ui + vi
mod oi.
gap> SumAgWord( b, a ); a*b gap> SumAgWord( a*b, a ); b gap> RelativeOrderAgWord( a ); 2 gap> z27 := CyclicGroup( AgWords, 27 ); Group( c27_1, c27_2, c27_3 ) gap> x := z27.1 * z27.2; c27_1*c27_2 gap> y := x ^ 2; c27_1^2*c27_2^2 gap> x * y; c27_2*c27_3 gap> SumAgWord( x, y ); IdAgWord
ExponentAgWord( g, k )
ExponentAgWord
returns the exponent of the k.th generator in an ag
word g as integer, where k refers to the numbering of generators of
the parent group of g.
Let G be the parent group of g and (g1, ..., gn) the AG system of G and let oi be the relative order of gi. Then the element g can be expressed uniquely in the form g1ν1* ...* gnνn for integers νi between 0 and oi-1. The exponent of the k.th generator is νk.
See also ExponentsAgWord and Exponents.
gap> ExponentAgWord( a * b^2 * c^2 * d, 2 ); 2 gap> ExponentAgWord( a * b^2 * c^2 * d, 4 ); 1 gap> ExponentAgWord( a * b^2 * c^2 * d, 3 ); 0 gap> a * b^2 * c^2 * d; a*b^2*d
ExponentsAgWord( g )
ExponentsAgWord( g, s, e )
ExponentsAgWord( g, s, e, root )
In its first form ExponentsAgWord
returns the exponent vector of an ag
word g, with respect to the AG system of the supergroup of g, as list
of integers. In the second form ExponentsAgWord
returns the sublist of
the exponent vector of g starting at position s and ending at
position e as list of integers. In the third form the vector is
returned as list of finite field elements over the same finite field as
root.
Let G be the parent group of g and (g1, ..., gn) the AG system of
G and let oi be the relative order of gi. Then the element g
can be expressed uniquely in the form g1ν1* ...* gnνn
for integers νi between 0 and oi-1. The exponent vector of g
is the list [ν1, ..., νn]
.
Note that you must use Exponents
if you want to get the exponent list
of g with respect not to the parent group of g but to a given
subgroup, which contains g. See Exponents for details.
gap> ExponentsAgWord( a * b^2 * c^2 * d ); [ 1, 2, 0, 1 ] gap> a * b^2 * c^2 * d; a*b^2*d
gap3-jm