24 Words in Finite Polycyclic Groups

Ag words are the GAP 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 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.

Subsections

  1. More about Ag Words
  2. Ag Word Comparisons
  3. CentralWeight
  4. CompositionLength
  5. Depth
  6. IsAgWord
  7. LeadingExponent
  8. RelativeOrder
  9. CanonicalAgWord
  10. DifferenceAgWord
  11. ReducedAgWord
  12. SiftedAgWord
  13. SumAgWord
  14. ExponentAgWord
  15. ExponentsAgWord

24.1 More about Ag Words

Let G be a group and G = G_0 > G_1 > ... > G_n = 1 be a subnormal series of G neq 1 with finite cyclic factors, i.e., G_i lhd G_{i-1} for all i=1, ..., n and G_{i-1} = < G_i, g_i > . Then G will be called an ag group indexag group with AG generating sequence indexAG generating sequence or, for short, AG system / G_i. If all o_1, ..., o_n are primes the system (g_1, ..., g_n) is called a *PAG system* index{PAG system}. With respect to a given AG system the group G has a so called *power-commutator presentation*

begintabularlcll {g_i}^{o_i} & = & w_{ii}(g_{i+1},..., g_n) & for 1leq ileq n,
[g_i,g_j] & = & w_{ij}(g_{j+1},...,g_n) & for 1leq j< ileq n
endtabular

and a so called power-conjugate presentation

begintabularlcll {g_i}^{o_i} & = & w_{ii}(g_{i+1},..., g_n) & for 1leq ileq n,
g_i^{g_j} & = & w^{prime}_{ij}(g_{j+1},...,g_n) & for 1leq j< ileq n.
endtabular

For both kinds of presentations we shall use the term AG presentation. Each element g of G can be expressed uniquely in the form

begintabularcc g = g_1^{nu_1}* ...* g_n^{nu_n} & for 0 leq nu_i < o_i. endtabular

We call the composition series G_0 > G_1 > ... > G_n the AG series of G and define nu_i( g ) := nu_i. If nu_i = 0 for i = 1, ..., k-1 and nu_k neq 0, we call nu_k the leading exponent and k the depth of g and denote them by nu_k =: lambda( g ) and k =: delta( g ). We call o_k 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 GAP 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 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 ) ] ) );
    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];; 

24.2 Ag Word Comparisons

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 

24.3 CentralWeight

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 ] 

24.4 CompositionLength

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 

24.5 Depth

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=G_0 > ... > G_n={1} the AG series of G. Let delta be the maximal positive integer such that g is an element of G_{delta-1}. Then delta 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 

24.6 IsAgWord

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 

24.7 LeadingExponent

LeadingExponent( g )

LeadingExponent returns the leading exponent of an ag word g as integer.

Let G be the parent group of g and (g_1, ..., g_n) the AG system of G and let o_i be the relative order of g_i. Then the element g can be expressed uniquely in the form g_1^{nu_1}* ...* g_n^{nu_n} for integers nu_i such that 0 leq nu_i < o_i. The leading exponent of g is the first nonzero nu_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 

24.8 RelativeOrder

RelativeOrder( g )

RelativeOrder returns the relative order of an ag word g as integer.

Let G be the parent group of g and G=G_0 > ... > G_n={1} the AG series of G. Let delta be the maximal positive integer such that g is an element of G_{delta-1}. The relative order of g is the index of G_{delta+1} in G_delta, that is the order of the factor group G_delta/G_{delta+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 

24.9 CanonicalAgWord

CanonicalAgWord( U, g )

Let U be an ag group with parent group G, let g be an element of G. Let (u_1, ..., u_m) be an induced generating system of U and (g_1, ..., g_n) be a canonical generating system of G. Then CanonicalAgWord returns a word x = <g> * u = g_{i_1}^{e_1} * ... * g_{i_k}^{e_k} such that u in <U> and no i_j is equal to the depth of any generator u_l.

    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 

24.10 DifferenceAgWord

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 (g_1, ..., g_n) be the AG system of G and o_i be the relative order or g_i. Then u can be expressed uniquely as g_1^{u_1}* ...* g_n^{u_n} for integers u_i between 0 and o_i-1 and v can be expressed uniquely as g_1^{v_1}* ...* g_n^{v_n} for integers v_i between 0 and o_i-1. The function DifferenceAgWord returns an ag word s = g_1^{s_1}* ...* g_n^{s_n} with integer s_i such that 0 leq s_i < o_i and s_i equiv u_i - v_i mod o_i.

    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 

24.11 ReducedAgWord

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 beta and xi be the leading exponent of b and x respectively. Then there exits an integer i such that xi * i = beta 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 

24.12 SiftedAgWord

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 u_1, ..., u_m be an induced generating system of U. If there exists an u_i such that u_i and g have the same depth, then g is reduced with u_i using ReducedAgWord (see ReducedAgWord). The process is repeated until no u_i can be found or the g is reduced to the identity.

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 

24.13 SumAgWord

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 (g_1, ..., g_n) be the AG system of G and o_i be the relative order or g_i. Then u can be expressed uniquely as g_1^{u_1}* ...* g_n^{u_n} for integers u_i between 0 and o_i-1 and v can be expressed uniquely as g_1^{v_1}* ...* g_n^{v_n} for integers v_i between 0 and o_i-1. Then SumAgWord returns an ag word s = g_1^{s_1}* ...* g_n^{s_n} with integer s_i such that 0 leq s_i < o_i and s_i equiv u_i + v_i mod o_i.

    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 

24.14 ExponentAgWord

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 (g_1, ..., g_n) the AG system of G and let o_i be the relative order of g_i. Then the element g can be expressed uniquely in the form g_1^{nu_1}* ...* g_n^{nu_n} for integers nu_i between 0 and o_i-1. The exponent of the k.th generator is nu_{<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 

24.15 ExponentsAgWord

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 (g_1, ..., g_n) the AG system of G and let o_i be the relative order of g_i. Then the element g can be expressed uniquely in the form g_1^{nu_1}* ...* g_n^{nu_n} for integers nu_i between 0 and o_i-1. The exponent vector of g is the list [nu_1, ..., nu_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 

Previous Up Next
Index

GAP 3.4.4
April 1997