%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A agwords.tex GAP documentation Frank Celler %% %A @(#)$Id: agwords.tex,v 3.12 1993/03/11 17:53:24 fceller Rel $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file contains descriptions of the ag word datatype, the operations %% and functions for this type. %% %H $Log: agwords.tex,v $ %H Revision 3.12 1993/03/11 17:53:24 fceller %H strings are now lists %H %H Revision 3.11 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.10 1993/02/15 15:00:11 fceller %H removed "%T" lines %H %H Revision 3.9 1993/02/15 14:23:56 felsch %H DefineName eliminated %H %H Revision 3.8 1993/02/02 15:11:45 felsch %H examples fixed %H %H Revision 3.7 1993/01/04 10:59:55 fceller %H changed 'DepthAgWord' applied to the identity %H %H Revision 3.6 1992/04/07 08:25:20 fceller %H fixed a few typos %H %H Revision 3.5 1992/04/03 13:15:38 fceller %H chnaged 'Shifted...' into 'Sifted...' %H %H Revision 3.4 1992/03/30 07:51:02 fceller %H changed 'Exponents' slightly %H %H Revision 3.3 1992/02/07 18:27:21 fceller %H Initial GAP 3.1 release. %H %H Revision 3.1 1991/04/11 11:34:01 martin %H Initial revision under RCS %% \Chapter{Words in Finite Polycyclic Groups}% \index{Ag Words} 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 "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". %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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} = \langle G_i, g_i \rangle$. Then $G$ will be called an *ag group* with *AG generating sequence* or, for short, *AG-system* $(g_1, ..., g_n)$. Let $o_i$ be the order of $G_{i-1} / G_i$. If all $o_1, ..., o_n$ are primes the system $(g_1, ..., g_n)$ is called a *PAG-system*. With respect to a given AG-system the group $G$ has a so called *power-commutator presentation* \begin{center} \begin{tabular}{lcll} ${g_i}^{o_i}$ & $=$ & $w_{ii}(g_{i+1},..., g_n)$ & for $1\leq i\leq n$,\\ $[g_i,g_j]$ & $=$ & $w_{ij}(g_{j+1},...,g_n)$ & for $1\leq j\< i\leq n$\\ \end{tabular} \end{center} and a so called *power-conjugate presentation* \begin{center} \begin{tabular}{lcll} ${g_i}^{o_i}$ & $=$ & $w_{ii}(g_{i+1},..., g_n)$ & for $1\leq i\leq n$,\\ $g_i^{g_j}$ & $=$ & $w^{\prime}_{ij}(g_{j+1},...,g_n)$ & for $1\leq j\< i\leq n$.\\ \end{tabular} \end{center} For both kinds of presentations we shall use the term *AG-presentation*. Each element $g$ of $G$ can be expressed uniquely in the form \begin{center} \begin{tabular}{cc} $g = g_1^{\nu_1}\* ...\* g_n^{\nu_n}$ & for $0 \leq \nu_i \< o_i$. \end{tabular} \end{center} 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];; | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Ag Word Comparisons} \index{equality!of ag words}% \index{ordering!of ag words} ' \<\ ' \\ ' \<= ' \\ ' >= ' \\ ' > ' The operators '\<', '>', '\<=' and '>=' return 'true' if is strictly less, strictly greater, not greater, not less, respectively, than . Otherwise they return 'false'. If and 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 and 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{CentralWeight} 'CentralWeight( )' 'CentralWeight' returns the central weight of an ag word , with respect to the central series used in the combinatorial collector, as integer. This presumes that belongs to a parent group for which the combinatorial collector is used. See "ChangeCollector" for details. If 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 ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{CompositionLength} 'CompositionLength( )' Let $G$ be the parent group of the ag word . 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Depth} 'Depth( )' 'Depth' returns the depth of an ag word with respect to the AG-series of its parent group as integer. Let $G$ be the parent group of and $G=G_0 > ... > G_n=\{1\}$ the AG-series of $G$. Let $\delta$ be the maximal positive integer such that is an element of $G_{\delta-1}$. Then $\delta$ is the *depth* of . Note that 'Depth' allows record that mimic ag words as arguments. | gap> Depth( a ); 1 gap> Depth( d ); 4 gap> Depth( a^0 ); 5 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsAgWord} 'IsAgWord( )' 'IsAgWord' returns 'true' if , which can be an arbitrary object, is an ag word and 'false' otherwise. | gap> IsAgWord( 5 ); false gap> IsAgWord( a ); true | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{LeadingExponent} 'LeadingExponent( )' 'LeadingExponent' returns the leading exponent of an ag word as integer. Let $G$ be the parent group of and $(g_1, ..., g_n)$ the AG-system of $G$ and let $o_i$ be the relative order of $g_i$. Then the element 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 is the first nonzero $\nu_i$. If is the identity 0 is returned. Although 'ExponentAgWord( , Depth( ) )' returns the leading exponent of , 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{RelativeOrder} 'RelativeOrder( )' 'RelativeOrder' returns the relative order of an ag word as integer. Let $G$ be the parent group of and $G=G_0 > ... > G_n=\{1\}$ the AG-series of $G$. Let $\delta$ be the maximal positive integer such that is an element of $G_{\delta-1}$. The *relative order* of is the index of $G_{\delta+1}$ in $G_\delta$, that is the order of the factor group $G_\delta/G_{\delta+1}$. If 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{CanonicalAgWord} 'CanonicalAgWord( , )' Let be an ag group with parent group $G$, let be an element of $G$. Let $(u_1, ..., u_m)$ be an induced generating system of and $(g_1, ..., g_n)$ be a canonical generating system of $G$. Then 'CanonicalAgWord' returns a word $x = \* u = g_{i_1}^{e_1} \* ... \* g_{i_k}^{e_k}$ such that $u\in $ 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{DifferenceAgWord} 'DifferenceAgWord( , )' 'DifferenceAgWord' returns an ag word $s$ representing the difference of the exponent vectors of and . Let $G$ be the parent group of and . Let $(g_1, ..., g_n)$ be the AG-system of $G$ and $o_i$ be the relative order or $g_i$. Then can be expressed uniquely as $g_1^{u_1}\* ...\* g_n^{u_n}$ for integers $u_i$ between $0$ and $o_i-1$ and 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ReducedAgWord} 'ReducedAgWord( , )' Let and be ag words of the same depth, then 'ReducedAgWord' returns an ag word such that is an element of the coset $U $, where $U$ is the cyclic group generated by , and has a higher depth than and . Note that the relative order of and must be a prime. Let $p$ be the relative order of and . 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 $ = ^{-i} $. Typically this function is used when and occur in a generating set of a subgroup $W$. Then b can be replaced by in the generating set of , but and have different depth. | gap> ReducedAgWord( a*b^2*c, a ); b^2*c gap> ReducedAgWord( last, b ); c | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SiftedAgWord} 'SiftedAgWord( , )' 'SiftedAgWord' tries to sift an ag word , which must be an element of the parent group of an ag group , through an induced generating system of . 'SiftedAgWord' returns the remainder of this shifting process. The identity is returned if and only if is an element of . Let $u_1, ..., u_m$ be an induced generating system of . If there exists an $u_i$ such that $u_i$ and have the same depth, then is reduced with $u_i$ using 'ReducedAgWord' (see "ReducedAgWord"). The process is repeated until no $u_i$ can be found or the 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 '.shiftInfo' to the ag group record of . This entry is used by subsequent calls with the same ag group in order to speed up computation. If you ever change the component '.igs' by hand, not using 'Normalize', you must unbind '.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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SumAgWord} 'SumAgWord( , )' 'SumAgWord' returns an ag word $s$ representing the sum of the exponent vectors of and . Let $G$ be the parent group of and . Let $(g_1, ..., g_n)$ be the AG-system of $G$ and $o_i$ be the relative order or $g_i$. Then can be expressed uniquely as $g_1^{u_1}\* ...\* g_n^{u_n}$ for integers $u_i$ between $0$ and $o_i-1$ and 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ExponentAgWord} 'ExponentAgWord( , )' 'ExponentAgWord' returns the exponent of the .th generator in an ag word as integer, where refers to the numbering of generators of the parent group of . Let $G$ be the parent group of and $(g_1, ..., g_n)$ the AG-system of $G$ and let $o_i$ be the relative order of $g_i$. Then the element 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 .th generator is $\nu_{}$. 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ExponentsAgWord} 'ExponentsAgWord( )'\\ 'ExponentsAgWord( , , )'\\ 'ExponentsAgWord( , , , )' In its first form 'ExponentsAgWord' returns the exponent vector of an ag word , with respect to the AG-system of the supergroup of , as list of integers. In the second form 'ExponentsAgWord' returns the sublist of the exponent vector of starting at position and ending at position as list of integers. In the third form the vector is returned as list of finite field elements over the same finite field as . Let $G$ be the parent group of and $(g_1, ..., g_n)$ the AG-system of $G$ and let $o_i$ be the relative order of $g_i$. Then the element 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 is the list '[$\nu_1$, ..., $\nu_n$]'. Note that you must use 'Exponents' if you want to get the exponent list of with respect not to the parent group of but to a given subgroup, which contains . 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %Emacs setup %E Local Variables: %E mode: outline %E outline-regexp: "\\\\Chapter\\|\\\\Section\\|\\%Emacs" %E fill-column: 73 %E eval: (hide-body) %E End: %%