Math Solutions 1995 October

home *** CD-ROM | disk | FTP | other *** search

/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / fpgrp.tex < prev next >

Wrap

Text File | 1993-05-05 | 82.2 KB | 1,731 lines

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A fpgrp.tex GAP documentation Martin Schoenert %% %A @(#)$Id: fpgrp.tex,v 3.6 1993/02/19 10:48:42 gap Exp $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes finitely presented groups and their implementation. %% %H $Log: fpgrp.tex,v $ %H Revision 3.6 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.5 1993/02/12 11:59:20 felsch %H examples adjusted to line length 72 %H %H Revision 3.4 1993/02/11 17:46:09 martin %H changed '@' to '&' %H %H Revision 3.3 1993/02/02 14:59:29 felsch %H examples fixed %H %H Revision 3.2 1993/01/22 19:31:45 felsch %H added RRS, MTC, and Tietze %H %H Revision 3.1 1992/04/06 17:06:14 martin %H initial revision under RCS %H %% \Chapter{Finitely Presented Groups} A *finitely presented group* is a group generated by a set of *abstract generators* subject to a set of *relations* that these generators satisfy. Each group can be represented as finitely presented group. A finitely presented group is constructed as follows. First create the abstract generators with 'AbstractGenerator' (see "AbstractGenerator"). Then create the free group generated by those abstract generators with 'Group' (see "Group"). Finally add the relations to the group. | gap> a := AbstractGenerator( "a" ); a gap> b := AbstractGenerator( "b" ); b gap> a5 := Group( a, b ); Group( a, b ) gap> a5.relators := [ a^2, b^3, (a*b)^5 ]; [ a^2, b^3, a*b*a*b*a*b*a*b*a*b ] gap> Size( a5 ); 60 | Note that the relations are entered as *relators*, i.e., as words in the abstract generators. To enter an equation use the quotient operator, i.e., for the relation $a^b = ab$ you have to enter 'a\^b/(a\*b)'. Alternatively you can use 'FreeGroup' (see "FreeGroup"). | gap> a5 := FreeGroup( 2, "a5" ); Group( a5.1, a5.2 ) gap> a5.relators := [ a5.1^2, a5.2^3, (a5.1*a5.2)^5 ]; [ a5.1^2, a5.2^3, a5.1*a5.2*a5.1*a5.2*a5.1*a5.2*a5.1*a5.2*a5.1*a5.2 ] gap> Size( a5 ); 60 | After you have performed *any* computation with a finitely presented group you must *not* change its relators any more. If you want to use a different set of relators make a new group. The elements of a finitely presented group are words. There is one fundamental problem with this. Different words can correspond to the same element in a finitely presented group. For example in the group 'a5' defined above, 'a' and 'a\^3' are actually the same element. However, 'a' is not equal to 'a\^3' (in the sense that 'a = a\^3' is 'false'). This leads to the following anomaly{\:} 'a\^3 in a5' is 'true', but 'a\^3 in Elements(a5)' is 'false'. *Some set and group functions will not work correctly because of this problem*. You should therefore only use the functions mentioned in "Set Functions for Finitely Presented Groups" and "Group Functions for Finitely Presented Groups". The first section in this chapter describes the function 'FreeGroup' that creates a free group (see "FreeGroup"). The next sections describe which set theoretic and group functions are implemented specially for finitely presented groups and how they work (see "Set Functions for Finitely Presented Groups" and "Group Functions for Finitely Presented Groups"). The next section describes the basic function 'CosetTableFpGroup' that is used by most other functions for finitely presented groups (see "CosetTableFpGroup"). The next section describes how you can compute a permutation group that is a homomorphic image of a finitely presented group (see "OperationCosetsFpGroup"). The final section describes the function that finds all subgroups of a finitely presented group of small index (see "LowIndexSubgroupsFpGroup"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{FreeGroup} 'FreeGroup( <n> )' \\ 'FreeGroup( <n>, <string> )' 'FreeGroup' returns the free group on <n> generators. The generators are displayed as '<string>.1', '<string>.2', ..., '<string>.<n>'. If <string> is missing it defaults to '\"f\"'. If <string> is the name of the variable that you use to refer to the group returned by 'FreeGroup' you can also enter the generators as '<string>.'. | gap> a5 := FreeGroup( 2, "a5" ); Group( a5.1, a5.2 ) gap> a5.relators := [ a5.1^2, a5.2^3, (a5.1*a5.2)^5 ]; [ a5.1^2, a5.2^3, a5.1*a5.2*a5.1*a5.2*a5.1*a5.2*a5.1*a5.2*a5.1*a5.2 ] gap> Size( a5 ); 60 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Set Functions for Finitely Presented Groups} \index{Size!for finitely presented groups} \index{in!for finitely presented groups} \index{Elements!for finitely presented groups} \index{Intersection!for finitely presented groups} Finitely presented groups are domains, thus in principle all set theoretic functions are applicable to them (see chapter "Domains"). However because words that are not equal may denote the same element of a finitely presented group many of them will not work correctly. This sections describes which set theoretic functions are implemented specially for finitely presented groups and how they work. You should *not* use the set theoretic functions that are not mentioned in this section. The general information that enables {\GAP} to work with a finitely presented group <G> is a *coset table* (see "CosetTableFpGroup"). Basically a coset table is the permutation representation of the finitely presented group on the cosets of a subgroup (which need not be faithful if the subgroup has a nontrivial core). Most of the functions below use the regular representation of <G>, i.e., the coset table of <G> over the trivial subgroup. Such a coset table is computed by a method called *coset enumeration*. \vspace{5mm} 'Size( <G> )' The size is simply the degree of the regular representation of <G>. \vspace{5mm} '<w> in <G>' A word <w> lies in a parent group <G> if all its letters are among the generators of <G>. \vspace{5mm} '<w> in <H>' To test whether a word <w> lies in a subgroup <H> of a finitely presented group <G>, {\GAP} computes the coset table of <G> over <H>. Then it tests whether the permutation one gets by replacing each generator of <G> in <w> with the corresponding permutation is trivial. \vspace{5mm} 'Elements( <G> )' The elements of a finitely presented group are computed by computing the regular representation of <G>. Then for each point {\GAP} adds the smallest word <w> that, when viewed as a permutation, takes 1 to to the set of elements. Note that this implies that each word in the set returned is the smallest word that denotes an element of <G>. \vspace{5mm} 'Elements( <H> )' The elements of a subgroup <H> of a finitely presented group <G> are computed by computing the elements of <G> and returning those that lie in <H>. \vspace{5mm} 'Intersection( <H1>, <H2> )' The intersection of two subgroups <H1> and <H2> of a finitely presented group <G> is computed as follows. First {\GAP} computes the coset tables of <G> over <H1> and <H2>. Then it computes the tensor product of those two permutation representations. The coset table of the intersection is the transitive constituent of 1 in this tensored permutation representation. Finally {\GAP} computes a set of Schreier generators for the intersection by performing another coset enumeration using the already complete coset table. The intersection is returned as the subgroup generated by those Schreier generators. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Group Functions for Finitely Presented Groups} \index{Order!for finitely presented groups} \index{Index!for finitely presented groups} \index{Normalizer!for finitely presented groups} \index{CommutatorFactorGroup!for finitely presented groups} \index{AbelianInvariants!for finitely presented groups} Finitely presented groups are after all groups, thus in principle all group functions are applicable to them (see chapter "Groups"). However because words that are not equal may denote the same element of a finitely presented group many of them will not work correctly. This sections describes which group functions are implemented specially for finitely presented groups and how they work. You should *not* use the group functions that are not mentioned in this section. The general information that enables {\GAP} to work with a finitely presented group <G> is a *coset table* (see "CosetTableFpGroup"). Basically a coset table is the permutation representation of the finitely presented group on the cosets of a subgroup (which need not be faithful if the subgroup has a nontrivial core). Most of the functions below use the regular representation of <G>, i.e., the coset table of <G> over the trivial subgroup. Such a coset table is computed by a method called *coset enumeration*. \vspace{5mm} 'Order( <G>, <g> )' The order of an element <g> is computed by translating the element into the regular permutation representation and computing the order of this permutation (which is the length of the cycle of 1). \vspace{5mm} 'Index( <G>, <H> )' The index of a subgroup <H> in a finitely presented group <G> is simply the degree of the permutation representation of the group <G> on the cosets of <H>. \vspace{5mm} 'Normalizer( <G>, <H> )' The normalizer of a subgroup <H> of a finitely presented group <G> is the union of those cosets of <H> in <G> that are fixed by all the generators of <H> when viewed as permutations in the permutation representation of <G> on the cosets of <H>. The normalizer is returned as the subgroup generated by the generators of <H> and representatives of such cosets. \vspace{5mm} 'CommutatorFactorGroup( <G> )' The commutator factor group of a finitely presented group <G> is returned as a new finitely presented group. The relations of this group are the relations of <G> plus the commutator of all the pairs of generators of <G>. \vspace{5mm} 'AbelianInvariants( <G> )' The abelian invariants of a abelian finitely presented group (e.g., a commutator factor group of an arbitrary finitely presented group) are computed by building the relation matrix of <G> and transforming this matrix to diagonal form with 'ElementaryDivisorsMat' (see "ElementaryDivisorsMat"). The following functions are not implemented specially for finitely presented groups, but they work nevertheless. However, you probably should not use them for larger finitely presented groups. 'Core( <G>, )' \\ 'SylowSubgroup( <G>, )' \\ 'FittingSubgroup( <G> )' %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{CosetTableFpGroup} 'CosetTableFpGroup( <G>, <H> )' 'CosetTableFpGroup' returns the coset table of the finitely presented group <G> on the cosets of the subgroup <H>. Basically a coset table is the permutation representation of the finitely presented group on the cosets of a subgroup (which need not be faithful if the subgroup has a nontrivial core). Most of the set theoretic and group functions use the regular representation of <G>, i.e., the coset table of <G> over the trivial subgroup. The coset table is returned as a list of lists. For each generator of <G> and its inverse the table contains a generator list. A generator list is simply a list of integers. If <l> is the generator list for the generator <g> and '<l>[] = <j>' then generator <g> takes the coset to the coset <j> by multiplication from the right. Thus the permutation representation of <G> on the cosets of <H> is obtained by applying 'PermList' to each generator list (see "PermList"). The coset table is standardized, i.e., the cosets are sorted with respect to the smallest word that lies in each coset. | gap> a5 := FreeGroup( 2, "a5" ); Group( a5.1, a5.2 ) gap> a5.relators := [ a5.1^2, a5.2^3, (a5.1*a5.2)^5 ]; [ a5.1^2, a5.2^3, a5.1*a5.2*a5.1*a5.2*a5.1*a5.2*a5.1*a5.2*a5.1*a5.2 ] gap> CosetTableFpGroup( a5, > Subgroup( a5, [ a5.1, a5.2*a5.1*a5.2*a5.1*a5.2^-1 ] ) ); [ [ 1, 3, 2, 5, 4 ], [ 1, 3, 2, 5, 4 ], # inverse of above, 'a5.1' is an involution [ 2, 4, 3, 1, 5 ], [ 4, 1, 3, 2, 5 ] ] # inverse of above gap> List( last, PermList ); [ (2,3)(4,5), (2,3)(4,5), (1,2,4), (1,4,2) ] | The coset table is computed by a method called *coset enumeration*. A *Felsch strategy* is used to decide how to define new cosets. The variable 'CosetTableFpGroupDefaultLimit' determines for how many cosets the table has initially room. 'CosetTableFpGroup' will automatically extend this table if need arises, but this is an expensive operation. Thus you should set 'CosetTableFpGroupDefaultLimit' to the number of cosets that you expect will be needed at most. However you should not set it too high, otherwise too much space will be used by the coset table. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{OperationCosetsFpGroup} 'OperationCosetsFpGroup( <G>, <H> )' 'OperationCosetsFpGroup' returns the permutation representation of the finitely presented group <G> on the cosets of the subgroup <H> as a permutation group. Note that this permutation representation is faithful if and only if <H> has a trivial core in <G>. | gap> a5 := FreeGroup( 2, "a5" ); Group( a5.1, a5.2 ) gap> a5.relators := [ a5.1^2, a5.2^3, (a5.1*a5.2)^5 ]; [ a5.1^2, a5.2^3, a5.1*a5.2*a5.1*a5.2*a5.1*a5.2*a5.1*a5.2*a5.1*a5.2 ] gap> OperationCosetsFpGroup( a5, > Subgroup( a5, [ a5.1, a5.2*a5.1*a5.2*a5.1*a5.2^-1 ] ) ); Group( (2,3)(4,5), (1,2,4) ) gap> Size( last ); 60 | 'OperationCosetsFpGroup' simply calls 'CosetTableFpGroup', applies 'PermList' to each row of the table, and returns the group generated by those permutations (see "CosetTableFpGroup", "PermList"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{LowIndexSubgroupsFpGroup} 'LowIndexSubgroupsFpGroup( <G>, <H>, <index> )' 'LowIndexSubgroupsFpGroup' returns a list of representatives of the conjugacy classes of subgroups of the finitely presented group <G> that contain the subgroup <H> of <H> and that have index less than or equal to <index>. | gap> a5 := FreeGroup( 2, "a5" );; a5.name := "a5";; gap> a5.relators := [ a5.1^2, a5.2^3, ( a5.1*a5.2 )^5 ];; gap> s := LowIndexSubgroupsFpGroup( a5, TrivialSubgroup( a5 ), 12 ); [ a5, Subgroup( a5, [ a5.1, a5.2*a5.1*a5.2^-1 ] ), Subgroup( a5, [ a5.1, a5.2*a5.1*a5.2*a5.1^-1*a5.2^-1 ] ), Subgroup( a5, [ a5.1, a5.2*a5.1*a5.2*a5.1*a5.2^-1*a5.1^-1*a5.2^-1 ] ), Subgroup( a5, [ a5.2*a5.1^-1 ] ) ] gap> List( s, h -> Index( a5, h ) ); [ 1, 6, 5, 10, 12 ] # the indices of the subgroups gap> List( s, h -> Index( a5, Normalizer( a5, h ) ) ); [ 1, 6, 5, 10, 6 ] # the lengths of the conjugacy classes | 'LowIndexSubgroupsFpGroup' systematically constructs all permutation representations of <G>. How large you can choose <index> depends on the presentation of <G>, but you should be careful. Usually the time required grows exponentially with <index>. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Presentation Records}% In {\GAP}, *finitely presented groups* are distinguished from *group presentations* which are {\GAP} objects of their own and which are stored in *presentation records*. The reason is that very often presentations have to be changed (e.g. simplified) by Tietze transformations, but since in these new generators and relators are introduced, all words in the generators of a finitely presented group would also have to be changed if such a Tietze transformation were applied to the presentation of a finitely presented group. Therefore, in {\GAP} the presentation defining a finitely presented group is never changed; changes are only allowed for group presentations which are not considered to define a particular group. {\GAP} offers a bundle of commands to perform Tietze transformations on finite group presentations (see "SimplifiedFpGroup", "Tietze Transformations"). In order to speed up the respective routines, the relators in such a presentation record are not represented by ordinary {\GAP} words, but by lists of positive or negative generator numbers. The term \"*Tietze record*\" will sometimes be used as an alias for \"*presentation record*\". It occurs, in particular, in certain error messages. \index{Tietze record} The following two commands can be used to create a presentation record from a finitely presented group or, vice versa, to create a finitely presented group from a presentation. \vspace{5mm} 'PresentationFpGroup( <G> )' \index{PresentationFpGroup} \\ 'PresentationFpGroup( <G>, <printlevel> )' 'PresentationFpGroup' returns a presentation record containing a copy of the presentation of the given finitely presented group <G> on the same set of generators. The optional <printlevel> parameter can be used to restrict or to extend the amount of output provided by Tietze transformation commands when being applied to the created presentation record. The default value 1 is designed for interactive use and implies explicit messages to be displayed by most of these commands. A <printlevel> value of 0 will suppress these messages, whereas a <printlevel> value of 2 will enforce some additional output. \vspace{5mm} 'FpGroupPresentation( )' \index{FpGroupPresentation} 'FpGroupPresentation' returns a finitely presented group defined by the presentation in the given presentation record . If some presentation record , say, contains a large presentation, then it would be nasty to wait for the end of an unintentionally started printout of all of its components (or, more precisely, of its component '.tietze' which contains the essential lists). Therefore, whenever you use the standard print facilities to display a presentation record, {\GAP} will provide just one line of text containing the number of generators, the number of relators, and the total length of all relators. Of course, you may use the 'RecFields' and 'PrintRec' commands to display all components of . In addition, you may use the following commands to extract and print different amounts of information from a presentation record. \vspace{5mm} 'TzPrintStatus( )' \index{TzPrintStatus} 'TzPrintStatus' prints the current state of a presentation record , i.e., the number of generators, the number of relators, and the total length of all relators. If you are working interactively, you can get the same information by just typing ';' \vspace{5mm} 'TzPrintGenerators( )' \index{TzPrintGenerators} \\ 'TzPrintGenerators( , <list> )' 'TzPrintGenerators' prints the current list of generators of a presentation record , providing for each generator its name, the total number of its occurrences in the relators, and, if that generator is known to be an involution, an appropriate message. If a list <list> has been specified as second argument, then it is expected to be a list of the position numbers of the generators to be printed. <list> need not be sorted and may contain duplicate elements. The generators are printed in the order in which and as often as their numbers occur in <list>. Position numbers out of range (with respect to the list of generators) will be ignored. \vspace{5mm} 'TzPrintRelators( )' \index{TzPrintRelators} \\ 'TzPrintRelators( , <list> )' 'TzPrintRelators' prints the current list of relators of a presentation record . If a list <list> has been specified as second argument, then it is expected to be a list of the position numbers of the relators to be printed. <list> need not be sorted and may contain duplicate elements. The relators are printed in the order in which and as often as their numbers occur in <list>. Position numbers out of range (with respect to the list of relators) will be ignored. \vspace{5mm} 'TzPrintPresentation( )' \index{TzPrintPresentation} 'TzPrintPresentation' prints the current lists of generators and relators and the current state of a presentation record . In fact, the command | TzPrintPresentation( P ) | is an abbreviation of the command sequence | Print( "generators:\n" ); TzPrintGenerators( P ); Print( "relators:\n" ); TzPrintRelators( P ); TzPrintStatus( P ); | \vspace{5mm} 'TzPrint( )' \index{TzPrint} \\ 'TzPrint( , <list> )' 'TzPrint' provides a kind of *fast print out* for a presentation record . Remember that in order to speed up the Tietze transformation routines, each relator in a presentation record is internally represented by a list of positive or negative generator numbers, i.e., each factor of the proper {\GAP} word is represented by the position number of the corresponding generator with respect to the current list of generators, or by the respective negative number, if the factor is the inverse of a generator which is not known to be an involution. In contrast to the commands 'TzPrintRelators' and 'TzPrintPresentation' described above, 'TzPrint' does not convert these lists back to the corresponding {\GAP} words. 'TzPrint' prints the current list of generators, and then for each relator its length and its internal representation as a list of positive or negative generator numbers. If a list <list> has been specified as second argument, then it is expected to be a list of the position numbers of the relators to be printed. <list> need not be sorted and may contain duplicate elements. The relators are printed in the order in which and as often as their numbers occur in <list>. Position numbers out of range (with respect to the list of relators) will be ignored. There are three more print commands for presentation records which are convenient in the context of the interactive Tietze transformation commands\: \vspace{5mm} 'TzPrintLengths( )' See "Tietze Transformations". \vspace{5mm} 'TzPrintPairs( )' \\ 'TzPrintPairs( , <n> )' See "Tietze Transformations". \vspace{5mm} 'TzPrintOptions( )' See "Tietze Transformations". \vspace{5mm} 'Save( <file>, , <name> )' \index{Save!for presentation records} 'Save' writes the presentation record to the file <file> in such a way that the file can be read by {\GAP}. This allows you, in particular, to restart a computation with the current presentation not only in the present, but also in a later {\GAP} session. Then, when you read the file, a copy of will be assigned to the variable specified by the argument <name> in the current call of the 'Save' command. Example. | gap> a := AbstractGenerator("a");; b := AbstractGenerator("b");; gap> G := Group( [ a, b ], IdWord );; gap> G.relators := > [ a^2, b^7, Comm(a,a^b), Comm(a,a^(b^2))*(a^b)^-1 ];; gap> P := PresentationFpGroup( G ); << presentation with 2 gens and 4 rels of total length 30 >> gap> TzPrintGenerators( P ); &I 1. a 11 occurrences involution &I 2. b 19 occurrences gap> TzPrintRelators( P ); &I 1. a^2 &I 2. b^7 &I 3. a*b^-1*a*b*a*b^-1*a*b &I 4. a*b^-2*a*b^2*a*b^-2*a*b*a*b gap> TzPrint( P ); &I generators: [ a, b ] &I relators: &I 1. 2 [ 1, 1 ] &I 2. 7 [ 2, 2, 2, 2, 2, 2, 2 ] &I 3. 8 [ 1, -2, 1, 2, 1, -2, 1, 2 ] &I 4. 13 [ 1, -2, -2, 1, 2, 2, 1, -2, -2, 1, 2, 1, 2 ] gap> TzPrintStatus( P ); &I there are 2 generators and 4 relators of total length 30 gap> Save( "checkpoint", P, "P0" ); gap> Read( "checkpoint" ); &I presentation record P0 read from file gap> P0; << presentation with 2 gens and 4 rels of total length 30 >> | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Changing Presentations}% The commands described in this section can be used to change the presentation in a presentation record. Note that, in general, they will change the isomorphism type of the group defined by the presentation. Hence, though they sometimes are called as subroutines by Tiet\-ze transformation commands like 'TzSubstitute' (see "Tietze Transformations"), they do *not* perform Tietze transformations themselves. \vspace{5mm} 'AddGenerator( )' \index{AddGenerator} \\ 'AddGenerator( , <generator> )' 'AddGenerator' adds a new generator to the list of generators. If you don\'t specify a second argument, then 'AddGenerator' will define a new abstract generator '\_x' and save it in a new component '.' of the given presentation record where is the least positive integer which has not yet been used as a generator number. Though this new generator will be printed as '\_x', you will have to use the external variable '.' if you want to access it. If you specify a second argument, then <generator> must be an abstract generator which does not yet occur in the presentation. 'AddGenerator' will add it to the presentation and save it in a new component '.' in the same way as described for \_x above. \vspace{5mm} 'AddRelator( , <word> )' \index{AddRelator} 'AddRelator' adds the word <word> to the list of relators. <word> must be a word in the generators of the given presentation. \vspace{5mm} 'RemoveRelator( , <n> )' \index{RemoveRelator} 'RemoveRelator' removes the <n>th relator and then resorts the list of relators in the given presentation record . %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Subgroup Presentations} 'PresentationSubgroupRrs( <G>, <H> )' \index{PresentationSubgroupRrs} \\ 'PresentationSubgroupRrs( <G>, <H>, <string> )' 'PresentationSubgroupRrs' returns a presentation record (see "Presentation Records") containing a presentation for the subgroup <H> of the finitely presented group <G>. It uses the Reduced Reidemeister-Schreier method to construct this presentation. \index{Reduced Reidemeister-Schreier} The generators in the resulting presentation will be named by '<string>1', '<string>2', ..., the default string is '\"\_x\"'. The Reduced Reidemeister-Schreier algorithm is a modification of the Reidemeister-Schreier algorithm of George Havas \cite{Hav74b}. It was proposed by Joachim Neub{\accent127u}ser and first implemented in 1986 by Andrea Lucchini and Volkmar Felsch in the SPAS system \cite{Spa89}. Like George Havas{\'} Reidemeister-Schreier algorithm, it needs only the presentation of <G> and a coset table of <H> in <G> to construct a presentation of <H>. Whenever you call the 'PresentationSubgroupRrs' command, it checks first whether a coset table of <H> in <G> has already been computed and saved in the subgroup record of <H> by a preceding call of some appropriate command like 'CosetTableFpGroup' (see "CosetTableFpGroup"), 'Index' (see "Index"), or 'LowIndexSubgroupsFpGroup' (see "LowIndexSubgroupsFpGroup"). Only if the coset table is not yet available, is it now constructed by 'PresentationSubgroupRrs' which calls 'CosetTableFpGroup' for this purpose. In this case, of course, a set of generators of <H> is required, but they will not be used any more in the subsequent steps. Next, a set of generators of <H> is determined by reconstructing the coset table and introducing in that process as many Schreier generators of <H> in <G> as are needed to do a Felsch strategy coset enumeration without any coincidences. (In general, though containing redundant generators, this set will be much smaller than the set of all Schreier generators. That\'s why we call the method the *Reduced* Reidemeister-Schreier.) After having constructed this set of *primary subgroup generators* , say, the coset table is extended to an *augmented coset table* which describes the action of the group generators on coset representatives, i.e., on elements instead of cosets. For this purpose, suitable words in the (primary) subgroup generators have to be associated to the coset table entries. In order to keep the lengths of these words short, additional *secondary subgroup generators* are introduced as abbreviations of subwords. Their number may be large. \index{primary subgroup generators} \index{secondary subgroup generators} \index{augmented coset table} Finally, a Reidemeister rewriting process is used to get defining relators for <H> from the relators of <G>. As the resulting presentation of <H> is a presentation on primary *and* secondary generators, in general you will have to simplify it by appropriate Tietze transformations (see "Tietze Transformations") or by the 'DecodeTree' command (see "DecodeTree") before you can use it. Therefore it is returned in the form of a presentation record. Compared with the Modified Todd-Coxeter method described below, the Reduced Rei\-de\-mei\-ster-Schreier method (as well as Havas{\'} original Reidemeister-Schreier program) has the advantage that it does not require generators of <H> to be given if a coset table of <H> in <G> is known. This provides a possibility to compute a presentation of the normal closure of a given subgroup (see the 'PresentationNormalClosureRrs' command below). A few examples are given in section "Tietze Transformations". \vspace{5mm} 'PresentationSubgroupMtc( <G>, <H> )' \index{PresentationSubgroupMtc} \\ 'PresentationSubgroupMtc( <G>, <H>, <string> )' \\ 'PresentationSubgroupMtc( <G>, <H>, <printlevel> )' \\ 'PresentationSubgroupMtc( <G>, <H>, <string>, <printlevel> )' 'PresentationSubgroupMtc' returns a presentation record (see "Presentation Records") containing a presentation for the subgroup <H> of the finitely presented group <G>. It uses a Modified Todd-Coxeter method to construct this presentation. \index{Modified Todd-Coxeter} The generators in the resulting presentation will be named by '<string>1', '<string>2', ..., the default string is '\"\_x\"'. The optional <printlevel> parameter can be used to restrict or to extend the amount of output provided by the 'PresentationSubgroupMtc' command. In particular, by specifying the <printlevel> parameter to be 0, you can suppress the output of the 'DecodeTree' command which is called by the 'PresentationSubgroupMtc' command (see below). The default value of <printlevel> is 1. The so called Modified Todd-Coxeter method was proposed, in slightly different forms, by Nathan S.~Mendelsohn and William O.~J.~Moser in 1966. Moser\'s method was proved by Michael J.~Beetham and Colin M.~Campbell (see \cite{BC76}). Another proof for a special version was given by D.~H.~McLain (see \cite{McL77}). It was generalized to cover a broad spectrum of different versions (see the survey \cite{Neu82}). Moser\'s method was implemented by Harvey A.~Campbell (see \cite{Cam71}. Later, a Modified Todd-Coxeter program was implemented in St.~Andrews by David G.~Arrell, Sanjiv Manrai, and Michael F.~Worboys (see \cite{AMW82}) and further developed by David G.~Arrel and Edmund F.~Robertson (see \cite{AR84}) and by Volkmar Felsch in the SPAS system \cite{Spa89}. The 'Modified Todd-Coxeter' method performs an enumeration of coset representatives. It proceeds like an ordinary coset enumeration (see 'CosetTableFpGroup' "CosetTableFpGroup"), but as the product of a coset representative by a group generator or its inverse need not be a coset representative itself, the Modified Todd-Coxeter has to store a kind of correction element for each coset table entry. Hence it builds up a so called *augmented coset table* of <H> in <G> consisting of the ordinary coset table and a second table in parallel which contains the associated subgroup elements. \index{augmented coset table} Theoretically, these subgroup elements could be expressed as words in the given generators of <H>, but in general these words tend to become unmanageable because of their enormous lengths. Therefore, a highly redundant list of subgroup generators is built up starting from the given (\"*primary*\") generators of <H> and adding additional (\"*secondary*\") generators which are defined as abbreviations of suitable words of length two in the preceding generators such that each of the subgroup elements in the augmented coset table can be expressed as a word of length at most one in the resulting (primary *and* secondary) subgroup generators. \index{primary subgroup generators} \index{secondary subgroup generators} Then a rewriting process (which is essentially a kind of Reidemeister rewriting process) is used to get relators for <H> from the defining relators of <G>. The resulting presentation involves all the primary, but not all the secondary generators of <H>. In fact, it contains only those secondary generators which explicitly occur in the augmented coset table. If we extended this presentation by those secondary generators which are not yet contained in it as additional generators, and by the definitions of all secondary generators as additional relators, we would get a presentation of <H>, but, in general, we would end up with a large number of generators and relators. On the other hand, if we avoid this extension, the current presentation will not necessarily define <H> although we have used the same rewriting process which in the case of the 'SubgroupPresentationRrs' command computes a defining set of relators for <H> from an augmented coset table and defining relators of <G>. The different behaviour here is caused by the fact that coincidences may have occurred in the Modified Todd-Coxeter coset enumeration. To overcome this problem without extending the presentation by all secondary generators, the 'SubgroupPresentationMtc' command applies the so called *tree decoding* algorithm which provides a more economical approach. The reader is strongly recommended to carefully read section "DecodeTree" where this algorithm is described in more detail. Here we will only mention that this procedure adds many fewer additional generators and relators in a process which in fact eliminates all secondary generators from the presentation and hence finally provides a presentation of <H> on the primary, i.e., the originally given, generators of <H>. This is a remarkable advantage of the 'SubgroupPresentationMtc' command compared to the 'SubgroupPresentationRrs' command. But note that, for some particular subgroup <H>, the Reduced Reidemeister-Schreier method might quite well produce a more concise presentation. The resulting presentation is returned in the form of a presentation record. Though the tree decoding routine already involves a lot of Tietze transformations, we recommend that you try to further simplify the presentation by appropriate Tietze transformations (see "Tietze Transformations"). An example is given in section "DecodeTree". \vspace{5mm} 'PresentationSubgroup( <G>, <H> )' \index{PresentationSubgroup} \\ 'PresentationSubgroup( <G>, <H>, <string> )' 'PresentationSubgroup' returns a presentation record (see "Presentation Records") containing a presentation for the subgroup <H> of the finitely presented group <G>. The current {\GAP} implementation offers a choice between two different methods for constructing subgroup presentations, namely the Reduced Reidemeister-Schreier and the Modified Todd-Coxeter procedure. You can specify either of them by calling the commands 'PresentationSubgroupRrs' or 'PresentationSubgroupMtc', respectively. Further methods may be added in a later {\GAP} version. If, in some concrete application, you don\'t care for the method to be selected, you may use the 'PresentationSubgroup' command as a kind of default command. In the present installation, it will call the Reduced Reidemeister-Schreier method, i.e., it is identical with the 'PresentationSubgroupRrs' command. A few examples are given in section "Tietze Transformations". \vspace{5mm} 'PresentationNormalClosureRrs( <G>, <H> )' \index{PresentationNormalClosureRrs} \\ 'PresentationNormalClosureRrs( <G>, <H>, <string> )' 'PresentationNormalClosureRrs' returns a presentation record (see "Presentation Records") containing a presentation for the normal closure of the subgroup <H> of the finitely presented group <G>. It uses the Reduced Reidemeister-Schreier method to construct this presentation. This provides a possibility to compute a presentation for a normal subgroup for which only \"normal subgroup generators\", but not necessarily a full set of generators are known. The generators in the resulting presentation will be named by '<string>1', '<string>2', ..., the default string is '\"\_x\"'. 'PresentationNormalClosureRrs' first establishes an intermediate group record for the factor group of <G> by the normal closure <N>, say, of <H> in <G>. Then it performs a coset enumeration of the trivial subgroup in that factor group. The resulting coset table can be considered as coset table of <N> in <G>, hence a presentation for <N> can be constructed using the Reduced Reidemeister-Schreier algorithm as described for the 'PresentationSubgroupRrs' command. \vspace{5mm} 'PresentationNormalClosure( <G>, <H> )' \index{PresentationNormalClosure} \\ 'PresentationNormalClosure( <G>, <H>, <string> )' 'PresentationNormalClosure' returns a presentation record (see "Presentation Records") containing a presentation for the normal closure of the subgroup <H> of the finitely presented group <G>. This provides a possibility to compute a presentation for a normal subgroup for which only \"normal subgroup generators\", but not necessarily a full set of generators are known. If, in a later release, {\GAP} offers different methods for the construction of normal closure presentations, then 'PresentationNormalClosure' will call one of these procedures as a kind of default method. At present, however, the Reduced Reidemeister-Schreier algorithm is the only one implemented so far. Therefore, at present the 'PresentationNormalClosure' command is identical with the 'PresentationNormalClosureRrs' command described above. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SimplifiedFpGroup} 'SimplifiedFpGroup( <G> )' 'SimplifiedFpGroup' applies Tietze transformations to a copy of the presentation of the given finitely presented group <G> in order to reduce it with respect to the number of generators, the number of relators, and the relator lengths. 'SimplifiedFpGroup' returns the resulting finitely presented group (which is isomorphic to <G>). | gap> G := FreeGroup( 6, "G" ); Group( G.1, G.2, G.3, G.4, G.5, G.6 ) gap> G.relators := [ G.1^2, G.2^2, G.4*G.6^-1, G.5^2, G.6^2, > G.1*G.2^-1*G.3, G.1*G.5*G.3^-1, G.2*G.4^-1*G.3, > G.3*G.4*G.5^-1, G.1*G.6*G.3^-2, G.3^4 ];; gap> H := SimplifiedFpGroup( G ); Group( G.1, G.3 ) gap> H.relators; [ G.1^2, G.1*G.3^-1*G.1*G.3^-1, G.3^4 ] | In fact, the command | H := SimplifiedFpGroup( G ); | is an abbreviation of the command sequence | P := PresentationFpGroup( G, 0 );; SimplifyPresentation( P ); H := FpGroupPresentation( P ); Unbind( P ); | which applies a rather simple-minded strategy of Tietze transformations to the intermediate presentation record (see "Presentation Records"). If for some concrete group the resulting presentation is unsatisfying, then you should try a more sophisticated, interactive use of the available Tietze transformation commands (see "Tietze Transformations"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Tietze Transformations}% The {\GAP} commands being described in this section can be used to modify a group presentation in a presentation record by Tietze transformations. In general, the aim of such modifications will be to *simplify* the given presentation, i.e., to reduce the number of generators and the number of relators without increasing too much the sum of all relator lengths which we will call the *total length* of the presentation. Depending on the concrete presentation under investigation one may end up with a nice, short presentation or with a very huge one. \index{total length of a presentation} Unfortunately there is no algorithm which could be applied to find the shortest presentation which can be obtained by Tietze transformations from a given one. Therefore, what {\GAP} offers are some lower-level Tietze transformation commands and, in addition, some higher-level commands which apply the lower-level ones in a kind of default strategy which of course cannot be the optimal choice for all presentations. The design of these commands follows closely the concept of the ANU Tietze transformation program designed by George Havas \cite{Hav69} which has been available from Canberra since 1977 in a stand-alone version implemented by Peter Kenne and James Richardson and later on revised by Edmund F.~Robertson (see \cite{HKRR84}, \cite{Rob88}). \vspace{5mm} In this section, we first describe the higher-level commands 'SimplifyPresentation', 'TzGo', and 'TzGoGo' (the first two of these commands are identical). Then we describe the lower-level commands 'TzEliminate', 'TzSearch', 'TzSearchEqual', and 'TzFindCyclicJoins'. They are the bricks of which the preceding higher-level commands have been composed. You may use them to try alternative strategies, but if you are satisfied by the performance of 'TzGo' and 'TzGoGo', then you don\'t need them. Some of the Tietze transformation commands listed so far may eliminate generators and hence change the given presentation to a presentation on a subset of the given set of generators, but they all do *not* introduce new generators. However, sometimes you will need to substitute certain words as new generators in order to improve your presentation. Therefore {\GAP} offers the two commands 'TzSubstitute' and 'TzSubstituteCyclicJoins' which introduce new generators. These commands will be described next. Subsequently we describe some print commands, namely 'TzPrintLengths', 'TzPrintPairs', and 'TzPrintOptions', which are useful if you run the Tietze transformations interactively. At the end of this section we list the *Tietze options* and give their default values. These are parameters which essentially influence the performance of the commands mentioned above. However, they are not specified as arguments of function calls. Instead, they are associated to the presentation records{\:} Each presentation record keeps its own set of Tietze option values in the form of ordinary record components. \vspace{5mm} 'SimplifyPresentation( )' \index{SimplifyPresentation} \\ 'TzGo( )' \index{TzGo} 'SimplifyPresentation' performs Tietze transformations on a presentation . It is perhaps the most convenient of the interactive Tietze transformation commands. It offers a kind of default strategy which, in general, saves you from explicitly calling the lower-level commands it involves. Roughly speaking, 'SimplifyPresentation' consists of a loop over a procedure which involves two phases{\:} In the *search phase* it calls 'TzSearch' and 'TzSearchEqual' described below which try to reduce the relator lengths by substituting common subwords of relators, in the *elimination phase* it calls the command 'TzEliminate' described below (or, more precisely, a subroutine of 'TzEliminate' in order to save some administrative overhead) which tries to eliminate generators that can be expressed as words in the remaining generators. If 'SimplifyPresentation' succeeds in reducing the number of generators, the number of relators, or the total length of all relators, then it displays the new status before returning (provided that you did not set the print level to zero). However, it does not provide any output if all these three values have remained unchanged, even if the 'TzSearchEqual' command involved has changed the presentation such that another call of 'SimplifyPresentation' might provide further progress. Hence, in such a case it makes sense to repeat the call of the command for several times (or to call instead the 'TzGoGo' command which we will describe next). As an example we compute a presentation of a subgroup of index 408 in $PSL(2,17)$. | gap> a := AbstractGenerator( "a" );; b := AbstractGenerator( "b" );; gap> G := Group( [ a, b ], IdWord );; gap> G.relators := [ a^9, b^2, (a*b)^4, (a^2*b)^3 ];; gap> H := Subgroup( G, [ (a*b)^2, (a^-1*b)^2 ] );; gap> Index( G, H ); 408 gap> P := PresentationSubgroup( G, H ); << presentation with 8 gens and 36 rels of total length 111 >> gap> P.printLevel := 2;; gap> SimplifyPresentation( P ); &I there are 4 generators and 8 relators of total length 21 &I there are 4 generators and 7 relators of total length 18 &I eliminating _x4 = _x3^-1*_x2^-1 &I eliminating _x1 = _x3^-1*_x2 &I there are 2 generators and 5 relators of total length 18 &I there are 2 generators and 4 relators of total length 13 &I there are 2 generators and 3 relators of total length 9 gap> TzPrintRelators( P ); &I 1. _x3^2 &I 2. _x2^3 &I 3. _x3*_x2*_x3*_x2 | Note that the number of loops over the two phases as well as the number of subword searches or generator eliminations in each phase are determined by a set of option parameters which may heavily influence the resulting presentation and the computing time (see Tietze options below). 'TzGo' is just another name for the 'SimplifyPresentation' command. It has been introduced for the convenience of those {\GAP} users who are used to that name from the *go* option of the ANU Tietze transformation stand-alone program or from the *go* command in SPAS. \vspace{5mm} 'TzGoGo( )' \index{TzGoGo} 'TzGoGo' performs Tietze transformations on a presentation . It repeatedly calls the 'TzGo' command until neither the number of generators nor the number of relators nor the total length of all relators have changed during five consecutive calls of 'TzGo'. This may remarkably save you time and effort if you handle small presentations, however it may lead to annoyingly long and fruitless waiting times in case of large presentations. \vspace{5mm} 'TzEliminate( )' \index{TzEliminate} \\ 'TzEliminate( , <gen> )' \\ 'TzEliminate( , <n> )' 'TzEliminate' tries to eliminate a generator from a presentation via Tietze transformations. Any relator which contains some generator just once can be used to substitute that generator by a word in the remaining generators. If such generators and relators exist, then 'TzEliminate' chooses a generator for which the product of its number of occurrences and the length of the substituting word is minimal, and then it eliminates this generator from the presentation, provided that the resulting total length of the relators does not exceed the associated Tietze option parameter '.spaceLimit'. The default value of '.spaceLimit' is 'infinity', but you may alter it appropriately (see Tietze options below). If you specify a generator <gen> as second argument, then 'TzEliminate' only tries to eliminate that generator. If you specify an integer <n> as second argument, then 'TzEliminate' tries to eliminate up to <n> generators. Note that the calls 'TzEliminate( )' and 'TzEliminate( , 1 )' are equivalent. \vspace{5mm} 'TzSearch( )' \index{TzSearch} 'TzSearch' performs Tietze transformations on a presentation . It tries to reduce the relator lengths by substituting common subwords of relators by shorter words. The idea is to find pairs of relators $r_1$ and $r_2$ of length $l_1$ and $l_2$, respectively, such that $l_1 \le l_2$ and $r_1$ and $r_2$ coincide (possibly after inverting or conjugating one of them) in some maximal subword $w$, say, of length greater than $l_1/2$, and then to substitute each copy of $w$ in $r_2$ by the inverse complement of $w$ in $r_1$. Two of the Tietze option parameters which are listed at the end of this section may strongly influence the performance and the results of the 'TzSearch' command. These are the parameters '.saveLimit' and '.searchSimultaneous'. The first of them has the following effect. When TzSearch has finished its main loop over all relators, then, in general, there are relators which have changed and hence should be handled again in another run through the whole procedure. However, experience shows that it really does not pay to continue this way until no more relators change. Therefore, 'TzSearch' starts a new loop only if the loop just finished has reduced the total length of the relators by at least '.saveLimit' per cent. The default value of '.saveLimit' is 10. To understand the effect of the parameter '.searchSimultaneous', we have to look in more detail at how 'TzSearch' proceeds. First, it sorts the list of relators by increasing lengths. Then it performs a loop over this list. In each step of this loop, the current relator is treated as *short relator* $r_1$, and a subroutine is called which loops over the succeeding relators, treating them as *long relators* $r_2$ and performing the respective comparisons and substitutions. As this subroutine performs a very expensive process, it has been implemented as a C routine in the {\GAP} kernel. For the given relator $r_1$ of length $l_1$, say, it first determines the *minimal match length* $l$ which is $l_1/2+1$, if $l_1$ is even, or $(l_1+1)/2$, otherwise. Then it builds up a hash list for all subwords of length $l$ occurring in the conjugates of $r_1$ or $r_1^{-1}$, and finally it loops over all long relators $r_2$ and compares the hash values of their subwords of length $l$ against this list. A comparison of subwords which is much more expensive is only done if a hash match has been found. To improve the efficiency of this process we allow the subroutine to handle several short relators simultaneously provided that they have the same minimal match length. If, for example, it handles $n$ short relators simultaneously, then you save $n - 1$ loops over the long relators $r_2$, but you pay for it by additional fruitless subword comparisons. In general, you will not get the best performance by always choosing the maximal possible number of short relators to be handled simultaneously. In fact, the optimal choice of the number will depend on the concrete presentation under investigation. You can use the parameter '.searchSimultaneous' to prescribe an upper bound for the number of short relators to be handled simultaneously. The default value of '.searchSimultaneous' is 20. \vspace{5mm} 'TzSearchEqual( )' \index{TzSearchEqual} 'TzSearchEqual' performs Tietze transformations on a presentation . It tries to alter relators by substituting common subwords of relators by subwords of equal length. The idea is to find pairs of relators $r_1$ and $r_2$ of length $l_1$ and $l_2$, respectively, such that $l_1$ is even, $l_1 \le l_2$, and $r_1$ and $r_2$ coincide (possibly after inverting or conjugating one of them) in some maximal subword $w$, say, of length at least $l_1/2$. Let $l$ be the length of $w$. Then, if $l > l_1/2$, the pair is handled as in 'TzSearch'. Otherwise, if $l = l_1/2$, then 'TzSearchEqual' substitutes each copy of $w$ in $r_2$ by the inverse complement of $w$ in $r_1$. The Tietze option parameter '.searchSimultaneous' is used by 'TzSearchEqual' in the same way as described for 'TzSearch'. However, 'TzSearchEqual' does not use the parameter '.saveLimit'{\:} The loop over the relators is executed exactly once. \vspace{5mm} 'TzFindCyclicJoins( )' \index{TzFindCyclicJoins} 'TzFindCyclicJoins' performs Tietze transformations on a presentation . It searches for pairs of generators which generate the same cyclic subgroup and eliminates one of the two generators of each such pair it finds. More precisely{\:} 'TzFindCyclicJoins' searches for pairs of generators $a$ and $b$ such that (possibly after inverting or conjugating some relators) the set of relators contains the commutator $[a,b]$, a power $a^n$, and a product of the form $a^s b^t$ with $s$ prime to $n$. For each such pair, 'TzFindCyclicJoins' uses the Euclidian algorithm to express $a$ as a power of $b$, and then it eliminates $a$. \vspace{5mm} 'TzSubstitute( )' \index{TzSubstitute} \\ 'TzSubstitute( , <n> )' \\ 'TzSubstitute( , <n>, <eliminate> )' 'TzSubstitute' performs Tietze transformations on a presentation . Basically, it substitutes a squarefree word of length 2 as a new generator and then eliminates a generator from the extended generator list. We will describe this process in more detail. The parameters <n> and <eliminate> are optional. If you specify arguments for them, then <n> is expected to be a positive integer, and <eliminate> is expected to be 0, 1, or 2. The default values are $n = 1$ and $eliminate = 0$. 'TzSubstitute' first determines the <n> most frequently occurring squarefree relator subwords of length 2 and sorts them by decreasing numbers of occurrences. Let $ab$ be the <n>th word in that list, and let be the smallest positive integer which has not yet been used as a generator number. Then 'TzSubstitute' defines a new generator '.' (see 'AddGenerator' for details), adds it to the presentation together with a new relator $P.i^{-1}ab$, and replaces all occurrences of $ab$ in the given relators by '.'. Finally, it eliminates some generator from the extended presentation. The choice of that generator depends on the actual value of the <eliminate> parameter\: If <eliminate> is zero, then the generator to be eliminated is chosen as by the 'TzEliminate' command. This means that in this case it may well happen that it is the generator '.' just introduced which is now deleted again so that you do not get any remarkable progress in transforming your presentation. On the other hand, this procedure guaranties that the total length of the relators will not be increased by a call of 'TzSubstitute' with $eliminate = 0$. Otherwise, if <eliminate> is 1 or 2, then 'TzSubstitute' eliminates the respective factor of the substituted word $ab$, i.e., $a$ for $eliminate = 1$ or $b$ for $eliminate = 2$. In this case, it may well happen that the total length of the relators increases, but sometimes such an intermediate extension is the only way to finally reduce a given presentation. In order to decide which arguments might be appropriate for the next call of 'TzSubstitute', often it is helpful to print out a list of the most frequently occurring squarefree relator subwords of length 2. You may use the 'TzPrintPairs' command described below to do this. As an example we handle a subgroup of index 266 in the Janko group $J_1$. | gap> a := AbstractGenerator("a");; b := AbstractGenerator("b");; gap> J1 := Group ( [ a, b ], IdWord );; gap> J1.relators := [ a^2, b^3, (a*b)^7, > Comm(a,b)^10, Comm(a,b^-1*(a*b)^2)^6 ];; gap> H := Subgroup ( J1, [ a, b^(a*b*(a*b^-1)^2) ] );; gap> P := PresentationSubgroup( J1, H ); << presentation with 23 gens and 82 rels of total length 530 >> gap> TzGoGo( P ); &I there are 3 generators and 47 relators of total length 1368 &I there are 2 generators and 46 relators of total length 3773 &I there are 2 generators and 46 relators of total length 2570 gap> TzGoGo( P ); &I there are 2 generators and 46 relators of total length 2568 gap> TzGoGo( P ); gap> & We do not get any more progress without substituting a new gap> & generator gap> TzSubstitute( P ); &I substituting new generator _x28 defined by _x6*_x23^-1 &I eliminating _x28 = _x6*_x23^-1 gap> & GAP cannot substitute a new generator without extending the gap> & total length, so we have to explicitly ask for it gap> TzPrintPairs( P ); &I 1. 504 occurrences of _x6 * _x23^-1 &I 2. 504 occurrences of _x6^-1 * _x23 &I 3. 448 occurrences of _x6 * _x23 &I 4. 448 occurrences of _x6^-1 * _x23^-1 gap> TzSubstitute( P, 2, 1 ); &I substituting new generator _x29 defined by _x6^-1*_x23 &I eliminating _x6 = _x23*_x29^-1 &I there are 2 generators and 46 relators of total length 2867 gap> TzGoGo( P ); &I there are 2 generators and 45 relators of total length 2417 &I there are 2 generators and 45 relators of total length 2122 gap> TzSubstitute( P, 1, 2 ); &I substituting new generator _x30 defined by _x23*_x29^-1 &I eliminating _x29 = _x30^-1*_x23 &I there are 2 generators and 45 relators of total length 2192 gap> TzGoGo( P ); &I there are 2 generators and 42 relators of total length 1637 &I there are 2 generators and 40 relators of total length 1286 &I there are 2 generators and 36 relators of total length 807 &I there are 2 generators and 32 relators of total length 625 &I there are 2 generators and 22 relators of total length 369 &I there are 2 generators and 18 relators of total length 213 &I there are 2 generators and 13 relators of total length 141 &I there are 2 generators and 12 relators of total length 121 &I there are 2 generators and 10 relators of total length 101 gap> TzPrintPairs( P ); &I 1. 19 occurrences of _x23 * _x30^-1 &I 2. 19 occurrences of _x23^-1 * _x30 &I 3. 14 occurrences of _x23 * _x30 &I 4. 14 occurrences of _x23^-1 * _x30^-1 gap> & If we save a copy of the current presentation, then later we gap> & will be able to restart the computation from the current state gap> P1 := Copy( P );; gap> & Just for demonstration, let's make an inconvenient choice gap> TzSubstitute( P, 3, 1 ); &I substituting new generator _x31 defined by _x23*_x30 &I eliminating _x23 = _x31*_x30^-1 &I there are 2 generators and 10 relators of total length 122 gap> TzGoGo( P ); &I there are 2 generators and 9 relators of total length 105 gap> & The presentation is worse than the one we have saved, so let's gap> & restart from that one again gap> P := Copy( P1 ); << presentation with 2 gens and 10 rels of total length 101 >> gap> TzSubstitute( P, 2, 1); &I substituting new generator _x31 defined by _x23^-1*_x30 &I eliminating _x23 = _x30*_x31^-1 &I there are 2 generators and 10 relators of total length 107 gap> TzGoGo( P ); &I there are 2 generators and 9 relators of total length 84 &I there are 2 generators and 8 relators of total length 75 gap> TzSubstitute( P, 2, 1); &I substituting new generator _x32 defined by _x30^-1*_x31 &I eliminating _x30 = _x31*_x32^-1 &I there are 2 generators and 8 relators of total length 71 gap> TzGoGo( P ); &I there are 2 generators and 7 relators of total length 56 &I there are 2 generators and 5 relators of total length 36 gap> TzPrintRelators( P ); &I 1. _x32^5 &I 2. _x31^5 &I 3. _x31^-1*_x32^-1*_x31^-1*_x32^-1*_x31^-1*_x32^-1 &I 4. _x31*_x32*_x31^-1*_x32*_x31^-1*_x32*_x31*_x32^-2 &I 5. _x31^-1*_x32^2*_x31*_x32^-1*_x31^2*_x32^-1*_x31*_x32^2 | As shown in the preceding example, you can use the 'Copy' command to save a copy of a presentation record and to restart from it again if you want to try an alternative strategy. However, this copy will be lost as soon as you finish your current {\GAP} session. If you use the 'Save' command (see "Presentation Records") instead, then you get a permanent copy on a file which you can read in again in a later session. \vspace{5mm} 'TzSubstituteCyclicJoins( )' \index{TzSubstituteCyclicJoins} 'TzSubstituteCyclicJoins' performs Tietze transformations on a presentation . It tries to find pairs of generators $a$ and $b$, say, for which among the relators (possibly after inverting or conjugating some of them) there are the commutator $[a,b]$ and powers $a^m$ and $b^n$ with mutually prime exponents $m$ and $n$. For each such pair, it substitutes the product $ab$ as a new generator, and then it eliminates the generators $a$ and $b$. \vspace{5mm} 'TzPrintLengths( )' \index{TzPrintLengths} 'TzPrintLengths' prints the list of the lengths of all relators of the given presentation . \vspace{5mm} 'TzPrintPairs( )' \index{TzPrintPairs} \\ 'TzPrintPairs( , <n> )' 'TzPrintPairs' determines in the given presentation the <n> most frequently occurring squarefree relator subwords of length 2 and prints them together with their numbers of occurrences. The default value of <n> is 10. A value $n = 0$ is interpreted as 'infinity'. This list is a useful piece of information in the context of using the 'TzSubstitute' command described above. \vspace{5mm} 'TzPrintOptions( )' \index{TzPrintOptions} Several of the Tietze transformation commands described above are controlled by certain parameters, the *Tietze options*, which often have a tremendous influence on their performance and results. However, in each application of the commands, an appropriate choice of these option parameters will depend on the concrete presentation under investigation. Therefore we have implemented the Tietze options in such a way that they are associated to the presentation records{\:} Each presentation record keeps its own set of Tietze option parameters in the form of ordinary record components. In particular, you may alter the value of any of these Tietze options by just assigning a new value to the respective record component. \index{Tietze options} 'TzPrintOptions' prints the Tietze option components of the specified presentation . \vspace{5mm} The Tietze options have the following meaning. 'eliminationsLimit': \\ Whenever the elimination phase of the 'TzGo' command is entered for a presentation , then it will eliminate at most '.eliminationsLimit' generators (except for further ones which have turned out to be trivial). Hence you may use the 'eliminationsLimit' parameter as a break criterion for the 'TzGo' command. Note, however, that it is ignored by the 'TzEliminate' command. The default value of 'eliminationsLimit' is 100. 'expandLimit': \\ Whenever the routine for eliminating more than 1 generators is called for a presentation by the 'TzEliminate' command or the elimination phase of the 'TzGo' command, then it saves the given total length of the relators, and subsequently it checks the current total length against its value before each elimination. If the total length has increased to more than '.expandLimit' per cent of its original value, then the routine returns instead of eliminating another generator. Hence you may use the 'expandLimit' parameter as a break criterion for the 'TzGo' command. The default value of 'expandLimit' is 150. 'generatorsLimit': \\ Whenever the elimination phase of the 'TzGo' command is entered for a presentation with $n$ generators, then it will eliminate at most $n - $'.generatorsLimit' generators (except for generators which turn out to be trivial). Hence you may use the 'generatorsLimit' parameter as a break criterion for the 'TzGo' command. The default value of 'generatorsLimit' is 0. 'lengthLimit': \\ The Tietze transformation commands will never eliminate a generator of a presentation , if they cannot exclude the possibility that the resulting total length of the relators exceeds the value of '.lengthLimit'. The default value of 'lengthLimit' is 'infinity'. 'loopLimit': \\ Whenever the 'TzGo' command is called for a presentation , then it will loop over at most '.loopLimit' of its basic steps. Hence you may use the 'loopLimit' parameter as a break criterion for the 'TzGo' command. The default value of 'loopLimit' is 'infinity'. 'printLevel': \\ Whenever Tietze transformation commands are called for a presentation with '.printLevel' $= 0$, they will not provide any output except for error messages. If '.printLevel' $= 1$, they will display some reasonable amount of output which allows you to watch the progress of the computation and to decide about your next commands. In the case '.printLevel' $= 2$, you will get a much more generous amount of output. Finally, if '.printLevel' $= 3$, various messages on internal details will be added. The default value of 'printLevel' is 1. 'saveLimit': \\ Whenever the 'TzSearch' command has finished its main loop over all relators of a presentation , then it checks whether during this loop the total length of the relators has been reduced by at least '.saveLimit' per cent. If this is the case, then 'TzSearch' repeats its procedure instead of returning. Hence you may use the 'saveLimit' parameter as a break criterion for the 'TzSearch' command and, in particular, for the search phase of the 'TzGo' command. The default value of 'saveLimit' is 10. 'searchSimultaneous': \\ Whenever the 'TzSearch' or the 'TzSearchEqual' command is called for a presentation , then it is allowed to handle up to '.searchSimultaneously' short relators simultaneously (see for the description of the 'TzSearch' command for more details). The choice of this parameter may heavily influence the performance as well as the result of the 'TzSearch' and the 'TzSearchEqual' commands and hence also of the search phase of the 'TzGo' command. The default value of 'searchSimultaneous' is 20. \vspace{5mm} As soon as a presentation record has been defined, you may alter any of its Tietze option parameters at any time by just assigning a new value to the respective component. To demonstrate the effect of the 'eliminationsLimit' parameter, we will give an example in which we handle a subgroup of index 240 in a group of order 40320 given by a presentation due to B.~H. Neumann. First we construct a presentation of the subgroup, and then we apply to it the 'TzGoGo' command for different values of the 'eliminationsLimit' parameter (including the default value 100). In fact, we also alter the 'printLevel' parameter, but this is only done in order to suppress most of the output. In all cases the resulting presentations cannot be improved any more by applying the 'TzGoGo' command again, i.e., they are the best results which we can get without substituting new generators. | gap> a := AbstractGenerator( "a" );; gap> b := AbstractGenerator( "b" );; gap> c := AbstractGenerator( "c" );; gap> G := Group( [ a, b, c ], IdWord );; gap> G.relators := [ a^3, b^3, c^3, (a*b)^5, (a^-1*b)^5, (a*c)^4, > (a*c^-1)^4, a*b^-1*a*b*c^-1*a*c*a*c^-1, (b*c)^3, (b^-1*c)^4 ];; gap> H := Subgroup( G, [ a, c ] );; gap> P := PresentationSubgroup( G, H ); << presentation with 224 gens and 593 rels of total length 2769 >> gap> for i in [ 28, 29, 30, 94, 100 ] do > Pi := Copy( P ); > Pi.eliminationsLimit := i; > Print( "&I eliminationsLimit set to ", i, "\n" ); > Pi.printLevel := 0; > TzGoGo( Pi ); > TzPrintStatus( Pi ); > od; &I eliminationsLimit set to 28 &I there are 2 generators and 95 relators of total length 10817 &I eliminationsLimit set to 29 &I there are 2 generators and 5 relators of total length 35 &I eliminationsLimit set to 30 &I there are 3 generators and 98 relators of total length 2928 &I eliminationsLimit set to 94 &I there are 4 generators and 78 relators of total length 1667 &I eliminationsLimit set to 100 &I there are 3 generators and 90 relators of total length 3289 | Similarly, we demonstrate the influence of the 'saveLimit' parameter by just continuing the preceding example for some different values of the 'saveLimit' parameter (including its default value 10), but without changing the 'eliminationsLimit' parameter which keeps its default value 100. | gap> for i in [ 9, 10, 11, 12, 15 ] do > Pi := Copy( P ); > Pi.saveLimit := i; > Print( "&I saveLimit set to ", i, "\n" ); > Pi.printLevel := 0; > TzGoGo( Pi ); > TzPrintStatus( Pi ); > od; &I saveLimit set to 9 &I there are 3 generators and 97 relators of total length 5545 &I saveLimit set to 10 &I there are 3 generators and 90 relators of total length 3289 &I saveLimit set to 11 &I there are 3 generators and 103 relators of total length 3936 &I saveLimit set to 12 &I there are 2 generators and 4 relators of total length 21 &I saveLimit set to 15 &I there are 3 generators and 143 relators of total length 18326 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{DecodeTree}% 'DecodeTree( )' \index{tree decoding} 'DecodeTree' eliminates the secondary generators from a presentation constructed by the Modified Todd-Coxeter (see 'PresentationSubgroupMtc') or the Reduced Reidemeister-Schreier procedure (see 'PresentationSubgroupRrs', 'PresentationNormalClosureRrs'). It is called automatically by the 'PresentationSubgroupMtc' command where it reduces to a presentation on the given subgroup generators. \index{secondary subgroup generators} In order to explain the effect of this command we need to insert a few remarks on the subgroup presentation commands described in section "Subgroup Presentations". All these commands have the common property that in the process of constructing a presentation for a given subgroup <H> of a finitely presented group <G> they first build up a highly redundant list of generators of <H> which consists of an (in general small) list of \"primary\" generators, followed by an (in general large) list of \"secondary\" \ generators, and then construct a presentation $P_0$, say, *on a sublist of these generators* by rewriting the defining relators of <G>. This sublist contains all primary, but, at least in general, by far not all secondary generators. \index{primary subgroup generators} The role of the primary generators depends on the concrete choice of the subgroup presentation command. If the Modified Todd-Coxeter method is used, they are just the given generators of <H>, whereas in the case of the Reduced Reidemeister-Schreier algorithm they are constructed by the program. Each of the secondary generators is defined by a word of length two in the preceding generators and their inverses. By historical reasons, the list of these definitions is called the *subgroup generators tree* though in fact it is not a tree but rather a kind of bush. \index{subgroup generators tree} Now we have to distinguish two cases. If $P_0$ has been constructed by the Reduced Rei\-de\-mei\-ster-Schreier routines, it is a presentation of <H>. However, if the Modified Todd-Coxeter routines have been used instead, then the relators in $P_0$ are valid relators of <H>, but they do not necessarily define <H>. We handle these cases in turn, starting with the latter one. Also in the case of the Modified Todd-Coxeter method, we could easily extend $P_0$ to a presentation of <H> by adding to it all the secondary generators which are not yet contained in it and all the definitions from the generators tree as additional generators and relators. Then we could recursively eliminate all secondary generators by Tietze transformations using the new relators. However, this procedure turns out to be too inefficient to be of interest. Instead, we use the so called *tree decoding* procedure which has been developed in St.~Andrews by David G.~Arrell, Sanjiv Manrai, Edmund F.~Robertson, and Michael F.~Wor\-boys (see \cite{AMW82}, \cite{AR84}). It proceeds as follows. Starting from $P = P_0$, it runs through a number of steps in each of which it eliminates the current \"last\" \ generator (with respect to the list of all primary and secondary generators). If the last generator <g>, say, is a primary generator, then the procedure finishes. Otherwise it checks whether there is a relator in the current presentation which can be used to substitute <g> by a Tietze transformation. If so, this is done. Otherwise, and only then, the tree definition of <g> is added to as a new relator, and the generators involved are added as new generators if they have not yet been contained in . Subsequently, <g> is eliminated. Note that the extension of by one or two new generators is *not* a Tietze transformation. In general, it will change the isomorphism type of the group defined by . However, it is a remarkable property of this procedure, that at the end, i.e., as soon as all secondary generators have been eliminated, it provides a presentation $P = P_1$, say, which defines a group isomorphic to <H>. In fact, it is this presentation which is returned by the 'DecodeTree' command and hence by the 'PresentationSubgroupMtc' command. If, in the other case, the presentation $P_0$ has been constructed by the Reduced Reidemeister-Schreier algorithm, then $P_0$ itself is a presentation of <H>, and the corresponding subgroup presentation command ('PresentationSubgroupRrs' or 'PresentationNormalClosureRrs') just returns $P_0$. As mentioned in section "Subgroup Presentations", we recommend further simplifying this presentation before using it. The standard way to do this is to start from $P_0$ and to apply suitable Tietze transformations, e.g., by calling the 'TzGo' or 'TzGoGo' commands. This is probably the most efficient approach, but you will end up with a presentation on some unpredictable set of generators. As an alternative, {\GAP} offers you the 'DecodeTree' command which you can use to eliminate all secondary generators (provided that there are no space or time problems). For this purpose, the subgroup presentation commands do not only return the resulting presentation, but also the tree (together with some associated lists) as a kind of side result in a component '.tree' of the resulting presentation record . Note, however, that the tree decoding routines will not work correctly any more on a presentation from which generators have already been eliminated by Tietze transformations. Therefore, to prevent you from getting wrong results by calling the 'DecodeTree' command in such a situation, {\GAP} will automatically remove the subgroup generators tree from a presentation record as soon as one of the generators is substituted by a Tietze transformation. Nevertheless, a certain misuse of the command is still possible, and we want to explicitly warn you from this. The reason is that the Tietze option parameters described in section "Tietze Transformations" apply to the 'DecodeTree' command as well. Hence, in case of inadequate values of these parameters, it may happen that the 'DecodeTree' routine stops before all the secondary generators have vanished. In this case {\GAP} will display an appropriate warning. Then you should change the respective parameters and continue the process by calling the 'DecodeTree' command again. Otherwise, if you would apply Tietze transformations, it might happen because of the convention described above that the tree is removed and that you end up with a wrong presentation. After a successful run of the 'DecodeTree' command it is convenient to further simplify the resulting presentation by suitable Tietze transformations. As an example of an explicit call of the 'DecodeTree' command we compute two presentations of a subgroup of order $384$ in a group of order $6912$. In both cases we use the Reduced Reidemeister-Schreier algorithm, but in the first run we just apply the Tietze transformations offered by the 'TzGoGo' command with its default parameters, whereas in the second run we call the 'DecodeTree' command before. | gap> a := AbstractGenerator( "a" );; b := AbstractGenerator( "b" );; gap> G := Group( [ a, b ], IdWord );; gap> G.relators := [ > a*b^2*a^-1*b^-1*a^3*b^-1, b*a^2*b^-1*a^-1*b^3*a^-1 ];; gap> H := Subgroup( G, [ Comm(a^-1,b^-1), Comm(a^-1,b), Comm(a,b) ] );; gap> & gap> & We use the Reduced Reidemeister Schreier method and default gap> & Tietze transformations to get a presentation for H. gap> P := PresentationSubgroupRrs( G, H ); << presentation with 18 gens and 35 rels of total length 169 >> gap> TzGoGo( P ); &I there are 3 generators and 20 relators of total length 488 &I there are 3 generators and 20 relators of total length 466 gap> & We end up with 20 relators of total length 466. gap> & gap> & Now we repeat the procedure, but we call the tree decoding gap> & algorithm before doing the Tietze transformations. gap> P := PresentationSubgroupRrs( G, H ); << presentation with 18 gens and 35 rels of total length 169 >> gap> DecodeTree( P ); &I there are 9 generators and 26 relators of total length 185 &I there are 6 generators and 23 relators of total length 213 &I there are 3 generators and 20 relators of total length 252 &I there are 3 generators and 20 relators of total length 244 gap> TzGoGo( P ); &I there are 3 generators and 19 relators of total length 168 &I there are 3 generators and 17 relators of total length 138 &I there are 3 generators and 15 relators of total length 114 &I there are 3 generators and 13 relators of total length 96 &I there are 3 generators and 12 relators of total length 84 gap> & This time we end up with a shorter presentation. | As an example of an implicit call of the command via the 'PresentationSubgroupMtc' command we handle a subgroup of index 240 in a group of order 40320 given by a presentation due to B.~H.~Neumann. | gap> a := AbstractGenerator( "a" );; gap> b := AbstractGenerator( "b" );; gap> c := AbstractGenerator( "c" );; gap> G := Group( [ a, b, c ], IdWord );; gap> G.relators := [ a^3, b^3, c^3, (a*b)^5, (a^-1*b)^5, (a*c)^4, > (a*c^-1)^4, a*b^-1*a*b*c^-1*a*c*a*c^-1, (b*c)^3, (b^-1*c)^4 ];; gap> H := Subgroup( G, [ a, c ] );; gap> InfoFpGroup1 := Print;; gap> P := PresentationSubgroupMtc( G, H );; &I index is 240 &I MTC defined 2 primary and 4472 secondary subgroup generators &I there are 246 generators and 617 relators of total length 2893 &I calling DecodeTree &I there are 114 generators and 380 relators of total length 1829 &I there are 72 generators and 293 relators of total length 1849 &I there are 47 generators and 252 relators of total length 2062 &I there are 36 generators and 214 relators of total length 2341 &I there are 25 generators and 188 relators of total length 2957 &I there are 20 generators and 170 relators of total length 3313 &I there are 20 generators and 158 relators of total length 4155 &I there are 21 generators and 155 relators of total length 6088 &I there are 24 generators and 155 relators of total length 9014 &I there are 27 generators and 155 relators of total length 13812 &I there are 31 generators and 155 relators of total length 20654 &I there are 36 generators and 155 relators of total length 32444 &I there are 39 generators and 155 relators of total length 51121 &I there are 42 generators and 155 relators of total length 74713 &I there are 40 generators and 153 relators of total length 85251 &I there are 12 generators and 140 relators of total length 29401 &I there are 7 generators and 131 relators of total length 18067 &I there are 4 generators and 122 relators of total length 20325 &I there are 2 generators and 115 relators of total length 21588 &I there are 2 generators and 114 relators of total length 16370 gap> TzGoGo( P ); &I there are 2 generators and 112 relators of total length 13126 &I there are 2 generators and 99 relators of total length 7572 &I there are 2 generators and 62 relators of total length 3384 &I there are 2 generators and 24 relators of total length 1506 &I there are 2 generators and 20 relators of total length 1000 &I there are 2 generators and 13 relators of total length 494 &I there are 2 generators and 10 relators of total length 314 &I there are 2 generators and 9 relators of total length 252 &I there are 2 generators and 8 relators of total length 192 &I there are 2 generators and 7 relators of total length 92 &I there are 2 generators and 6 relators of total length 52 gap> TzPrintGenerators( P ); &I 1. _x1 26 occurrences &I 2. _x2 26 occurrences | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%