%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A word.tex GAP documentation Martin Schoenert %% %A @(#)$Id: word.tex,v 3.5 1993/05/04 12:01:33 fceller Rel $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes the word data type, its operations and functions. %% %H $Log: word.tex,v $ %H Revision 3.5 1993/05/04 12:01:33 fceller %H fixed example in 'AbstractGenerator' %H %H Revision 3.4 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.3 1993/02/02 10:53:11 felsch %H PositionWord fixed %H %H Revision 3.2 1993/02/02 08:22:45 felsch %H examples fixed %H %H Revision 3.1 1992/04/06 00:10:41 martin %H initial revision under RCS %H %% \Chapter{Words in Abstract Generators} \index{words}\index{type!words} \index{IdWord} *Words in abstract generators* are a type of group elements in {\GAP}. In the following we will abbreviate their full name to *words*. A word is just a sequence of letters, where each letter is an abstract generator or its inverse. Words are multiplied by concatenating them and removing adjacent pairs of a generator and its inverse. Abstract generators are created by the function 'AbstractGenerator' (see "AbstractGenerator"). Note that words do not belong to a certain group. Any two words can be multiplied. In effect we compute with words in a free group of potentially infinite rank (potentially infinite because we can always create new abstract generators with 'AbstractGenerator'). Words are entered as expressions in abstract generators and are displayed as product of abstract generators (and powers thereof). The trivial word can be entered and is displayed as 'IdWord'. | gap> a := AbstractGenerator( "a" ); a gap> b := AbstractGenerator( "b" ); b gap> w := (a^2*b)^5*b^-1; a^2*b*a^2*b*a^2*b*a^2*b*a^2 gap> a^0; IdWord | The first sections in this chapter describe the functions that create abstract generators (see "AbstractGenerator" and "AbstractGenerators"). The next sections define the operations for words (see "Comparisons of Words" and "Operations for Words"). The next section describes the function that tests whether an object is a word (see "IsWord"). The next sections describe the functions that compute the number of letters of a word (see "LengthWord" and "ExponentSumWord"). The next sections describe the functions that extract or find a subword (see "Subword" and "PositionWord"). The final sections describe the functions that modify words (see "SubstitutedWord", "EliminatedWord", and "MappedWord"). Note that words in abstract generators are different from words in finite polycyclic groups (see "Words in Finite Polycyclic Groups"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{AbstractGenerator} 'AbstractGenerator( )' 'AbstractGenerator' returns a new abstract generator. This abstract generator is printed using the string passed as argument to 'AbstractGenerator'. | gap> a := AbstractGenerator( "a" ); a gap> a^5; a^5 | Note that the string is only used to print the abstract generator and to order abstract generators (see "Comparisons of Words"). It is possible for two different abstract generators to use the same string and still be different. | gap> b := AbstractGenerator( "a" ); a gap> a = b; false | Also when you define abstract generators interactively it is a good idea to use the identifier of the variable as the name of the abstract generator, because then what {\GAP} will output for a word is equal to what you can input to obtain this word. The following is an example of what you should probably *not* do. | gap> c := AbstractGenerator( "d" ); d gap> d := AbstractGenerator( "c" ); c gap> (c*d)^3; d*c*d*c*d*c gap> d*c*d*c*d*c; c*d*c*d*c*d | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{AbstractGenerators} 'AbstractGenerators( , )' 'AbstractGenerators' returns a list of new abstract generators. These new generators are printed using '1', '2', ..., ''. | gap> AbstractGenerators( "a", 3 ); [ a1, a2, a3 ] | 'AbstractGenerators' could be defined as follows (see "AbstractGenerator"). | AbstractGenerators := function ( string, n ) local gens, i; gens := []; for i in [1..n] do Add( gens, AbstractGenerator( ConcatenationString( string, String(i) ) ) ); od; return gens; end; | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Comparisons of Words} ' = '\\ ' \<> ' The equality operator '=' evaluates to 'true' if the two words and are equal and to 'false' otherwise. The inequality operator '\<>' evaluates to 'true' if the two words and are not equal and to 'false' otherwise. You can compare words with objects of other types, but they are never equal of course. | gap> a := AbstractGenerator( "a" );; gap> b := AbstractGenerator( "b" );; gap> a = b; false gap> (a^2*b)^5*b^-1 = a^2*b*a^2*b*a^2*b*a^2*b*a^2; true | ' \<\ ' \\ ' \<= ' \\ ' > ' \\ ' >= ' The operators '\<', '\<=', '>', and '=>' evaluate to 'true' if the word is less than, less than or equal to, greater than, and greater than or equal to the word . Words are ordered as follows. One word is considered smaller than another word it it is shorted, or, if they have the same length, if it is first in the lexicographical ordering implied by the ordering of the abstract generators. The ordering of abstract generators is as follows. The abstract generators are ordered with respect to the strings that were passed to 'AbstractGenerator' when creating these abstract generators. Each abstract generator is also smaller than its inverse, but this inverse is smaller than any abstract generator that is larger than . Words can also be compared with objects of other types. Integers, rationals, cyclotomics, finite field elements, and permutations are smaller than words, everything else is larger. | gap> IdWord \*\ ' The operator '\*' evaluates to the product of the two words and . Note that words do not belong to a specific group, thus any two words can be multiplied. Multiplication of words is done by concatenating the words and removing adjacent pairs of an abstract generator and its inverse. \vspace{5mm} ' / ' The operator '/' evaluates to the quotient $w1\*w2^{-1}$ of the two words and . Inversion of a word is done by reversing the order of its letters and replacing each abstract generator with its inverse. \vspace{5mm} ' \^\ ' The operator '\^' evaluates to the conjugate $w2^{-1}\* w1\* w2$ of the word under the word . \vspace{5mm} ' \^\ ' The powering operator '\^' returns the -th power of the word , where must be an integer. If is zero, the value is 'IdWord'. \vspace{5mm} ' \*\ ' \\ ' \*\ ' In this form the operator '\*' returns a new list where each entry is the product of and the corresponding entry of . Of course multiplication must be defined between and each entry of . \vspace{5mm} ' / ' In this form the operator '/' returns a new list where each entry is the quotient of and the corresponding entry of . Of course division must be defined between and each entry of . 'Comm( , )' 'Comm' returns the commutator $w1^{-1}\* w2^{-1}\* w1\* w2$ of two words and . \vspace{5mm} 'LeftQuotient( , )' 'LeftQuotient' returns the left quotient $w1^{-1}\* w2$ of two words and . %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsWord} 'IsWord( )' 'IsWord' returns 'true' if the object , which may be an object of arbitrary type, is a word and 'false' otherwise. Signals an error if is an unbound variable. | gap> a := AbstractGenerator("a");; gap> b := AbstractGenerator("b");; gap> w := (a^2*b)^5*b^-1; a^2*b*a^2*b*a^2*b*a^2*b*a^2 gap> IsWord( w ); true gap> a := (1,2,3);; gap> IsWord( a^2 ); false | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{LengthWord} \index{length!of a word} 'LengthWord( )' 'LengthWord' returns the length of the word , i.e., the number of letters in the word. | gap> a := AbstractGenerator("a");; gap> b := AbstractGenerator("b");; gap> w := (a^2*b)^5*b^-1; a^2*b*a^2*b*a^2*b*a^2*b*a^2 gap> LengthWord( w ); 14 gap> LengthWord( a^13 ); 13 gap> LengthWord( IdWord ); 0 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ExponentSumWord} 'ExponentSumWord( , )' 'ExponentSumWord' returns the number of times the generator appears in the word minus the number of times its inverse appears in . If and its inverse do no occur in , 0 is returned. may also be the inverse of a generator of course. | gap> a := AbstractGenerator("a");; gap> b := AbstractGenerator("b");; gap> w := (a^2*b)^5*b^-1; a^2*b*a^2*b*a^2*b*a^2*b*a^2 gap> ExponentSumWord( w, a ); 10 gap> ExponentSumWord( w, b ); 4 gap> ExponentSumWord( (a*b*a^-1)^3, a ); 0 gap> ExponentSumWord( (a*b*a^-1)^3, b^-1 ); -3 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Subword} 'Subword( , , )' 'Subword' returns the subword of the word that begins at position and ends at position . and must be positive integers. Indexing is done with origin 1. | gap> a := AbstractGenerator("a");; gap> b := AbstractGenerator("b");; gap> w := (a^2*b)^5*b^-1; a^2*b*a^2*b*a^2*b*a^2*b*a^2 gap> Subword( w, 5, 8 ); a*b*a^2 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{PositionWord} 'PositionWord( , , )' 'PositionWord' returns the position of the first occurence of the word in the word starting at position . If there is no such occurence, 'false' is returned. must be a positive integer. Indexing is done with origin 1. In other words, 'PositionWord(,,)' returns the smallest integer larger than or equal to such that 'Subword( , , +LengthWord()-1 ) = ' (see "Subword"). | gap> a := AbstractGenerator("a");; gap> b := AbstractGenerator("b");; gap> w := (a^2*b)^5*b^-1; a^2*b*a^2*b*a^2*b*a^2*b*a^2 gap> PositionWord( w, a^2*b, 2 ); 4 gap> PositionWord( w, a*b^2, 2 ); false | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SubstitutedWord} 'SubstitutedWord( , , , )' 'SubstitutedWord' returns a new word where the subword of the word that begins at position and ends at position is replaced by the word . and must be positive integers. Indexing is done with origin 1. In other words 'SubstitutedWord(,,,)' is the word 'Subword(,1,-1) \*\ \*\ Subword(,+1,LengthWord()' (see "Subword"). | gap> a := AbstractGenerator("a");; gap> b := AbstractGenerator("b");; gap> w := (a^2*b)^5*b^-1; a^2*b*a^2*b*a^2*b*a^2*b*a^2 gap> SubstitutedWord(w,5,8,b^-1); a^2*b*a^3*b*a^2 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{EliminatedWord} 'EliminatedWord( , , )' 'EliminatedWord' returns a new word where each occurence of the generator is replaced by the word . | gap> a := AbstractGenerator("a");; gap> b := AbstractGenerator("b");; gap> w := (a^2*b)^5*b^-1; a^2*b*a^2*b*a^2*b*a^2*b*a^2 gap> EliminatedWord( w, b, b^2 ); a^2*b^2*a^2*b^2*a^2*b^2*a^2*b^2*a^2 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{MappedWord} 'MappedWord( , , )' 'MappedWord' returns the new group element that is obtained by replacing each occurence of a generator in the list of generators by the corresponding group element in the list of group elements . The lists and must of course have the same length. | gap> a := AbstractGenerator("a");; gap> b := AbstractGenerator("b");; gap> w := (a^2*b)^5*b^-1; a^2*b*a^2*b*a^2*b*a^2*b*a^2 gap> MappedWord( w, [a,b], [(1,2,3),(1,2)] ); (1,3,2) | If the images in are all words, and some of them are equal to the corresponding generators in , then those may be omitted. | gap> MappedWord( w, [a], [a^2] ); a^4*b*a^4*b*a^4*b*a^4*b*a^4 | Note that the special case that the list and have only length 1 is handled more efficiently by 'EliminatedWord' (see "EliminatedWord"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%