Home

ACE - Gap

1. General ACE Modes Interactive ACE Process Utility Functions and Interruption of an Interactive ACE Process Experimentation ACE Modes Interactive Query Functions and an Option Setting Function Interactive Versions of Non interactive ACE Functions Steering ACE Interactively Primitive ACE Read Write Functions The Meanings of ACE s output messages Progress Messages Results Messages Examples Example where ACE is made the Standard Coset Enumerator Example of Using ACECosetTableFromGensAndRels Example of Using ACE Interactively Using ACEStart Fun with ACEExample 36 39 39 39 40 Al 42 44 44 46 47 49 51 57 57 61 63 65 65 66 66 68 69 70 B 5 C 1 C 2 D 1 D 2 D 3 D 4 D 5 D 6 D 7 Using ACEReadResearchExample Finer Points with Examples Getting Started Emulating Sims Other ACE Options Experimentation Options Options that Modify a Presentation Mode Options Options that Interact with the Operating System Query Options Options that Modify the Coset Table Options for Comments Bibliography Index TT 79 79 92 94 94 96 98 99 99 102 103 104 105 The ACE Package The Advanced Coset Enumerator ACE ACE coset enumerator C 1995 2001 by George Havas and Colin Ramsay http www itee uq edu au cram ce html can be called from within GAP through an interface written by Alexander Hulpke and Greg Gamble which is descr
2. a b gt messages 1 I x I x 1 ACE 3 001 Run Parameters I Group Name A_5 I Group Generators ab I Group Relators a 2 b 3 ab 5 I Subgroup Name Id I Subgroup Generators ab I Wo 1000000 Max 333331 Mess 1 Ti 1 Ho 1 Loop 0 I As 0 Path 0 Row 1 Mend 0 No 3 Look 0 Com 10 I C 0 R 0 Fi 6 PMod 3 PSiz 256 DMod 4 DSiz 1000 1 Hoan I AD a 2 r 1 h 1 n 3 1 1 c 0 00 m 2 t 2 I SG a 2 r 1 h 1 n 3 1 1 c 0 00 m 2 t 2 I RD a 3 r 1 h 1 n 4 1 2 c 0 00 m 3 t 3 I RD a 4 r 2 h 1 n 5 1 2 c 0 00 m 4 t 4 I RD a 5 r 2 h 1 n 6 1 2 c 0 00 m 5 t 5 I RD a 6 r 2 h 1 n 7 1 2 c 0 00 m 6 t 6 I RD a 7 r 2 h 1 n 8 1 2 c 0 00 m 7 t 7 I RD a 8 r 2 h 1 n 9 1 2 c 0 00 m 8 t 8 I RD a 9 r 2 h 1 n 10 1 2 c 0 00 m 9 t 9 I CC a 8 r 2 h 1 n 10 1 2 c 0 00 d 0 I RD a 9 r 5 h 1 n 11 1 2 c 0 00 m 9 t 10 I RD a 10 r 5 h 1 n 12 1 2 c 0 00 m 10 t 11 I RD a 11 r 5 h 1 n 13 1 2 c 0 00 m 11 t 12 I RD a 12 r 5 h 1 n 14 1 2 c 0 00 m 12 t 13 I RD a 13 r 5 h 1 n 15 1 2 c 0 00 m 13 t 14 I RD a 14 r 5 h 1 n 16 1 2 c 0 00 m 14 t 15 I CC a 13 r 6 h 1 n 16 1 2 c 0 00 d 0 I CC a 12 r 6 h 1 n 16 1 2 c 0 00 d 0 I INDEX 12 a 12 r 16 h 1 n 16 1 3 c 0 00 m 14 t 15 1 Observe that we used ACERelators 1 see 6 5 2 to grab the value of the relators we had defined earlier We also used ACEGroupGenerators 1 see 6 5 1
3. ACEExample A5 hlt 4 Try the ed examples to explore how to modify options when an enumeration fails just follow the instructions you get within the break loop or see Notes 2 and 3 5 Try SetInfoACELevel 3 before calling ACEExample to see the effect of setting the mess messages option 6 To suppress a long output use a double semicolon after the ACEExample command However this does not suppress Info ed output 7 Also try SetInfoACELevel 2 or SetInfoACELevel 4 before calling ACEExample 72 Appendix B Examples Notice that the example we first met in Section 1 2 the Fibonacci group F 2 7 is available via examples F27 purec F27 fel0 and F27 fel1 with 2nd argument ACECosetTableFromGensAndRels to pro duce a coset table except that each of these enumerate the cosets of its trivial subgroup of index 29 Let s experiment with the first of these F 2 7 examples since this example uses the messages option we ought to set the InfoLevel of InfoACE to 3 first but since the coset table is quite long we will be content for the moment with applying the default function ACEStats to the example Before exhibiting the example we list a few observations that should be made Observe that the first group of Info lines list the commands that are executed these lines are followed by the result of the echo option see 4 11 12 which in turn are followed by Info messages from
4. A_5 Give the group G a meaningful name gt subg C_5 Give the subgroup a meaningful name ACEStart called with the following arguments Group generators a b Group relators a 2 b 3 a b a b a b a xb a b Subgroup generators a b I ACE 3 001 Sun Sep 30 22 11 42 2001 I oo SSssssssssssssssssssssssssssssssssssssss I Host information 1 name rigel ACEStart called with the following options echo true not passed to ACE enum A_5 subg C_5 I I INDEX 12 a 12 r 16 h 1 n 16 1 3 c 0 00 m 14 t 15 1 70 Appendix B Examples The return value on the last line is an index that identifies the interactive process we use this index with functions that need to interact with the interactive ACE process we now demonstrate this with the interactive version of ACEStats gap gt ACEStats 1 rec index 12 cputime 0 cputimeUnits 10 2 seconds activecosets 12 maxcosets 14 totcosets 15 gap gt Actually we didn t need to pass an argument to ACEStats gap gt we could have relied on the default gap gt ACEStats rec index 12 cputime 0 cputimeUnits 10 2 seconds activecosets 12 maxcosets 14 totcosets 15 Similarly we may use ACECosetTable with 0 or 1 arguments which is the interactive version of ACECoset TableFromGensAndRels and which returns a standard table since GAP 4 3 a standard table is a lenle
5. a b c d e x y Group relators a b c 1 b c d 1 c d e 1 d e x 1 e x y 1 x y xa 1 y a b 1 Subgroup generators ACECosetTableFromGensAndRels called with the following options aceexampleoptions true inserted by ACEExample not passed to ACE echo true not passed to ACE enum F 2 7 aka C_29 wo 2M mess 25000 purec no value passed to ACE via option pure c IN I sg c brackets are not passed to ACE subgroup lt c gt max 2 hlt no value I OVERFLOW a 2 r 1 h 1 n 3 1 4 c 0 00 m 2 t 2 Error no coset table the ACE coset enumeration failed with the result OVERFLOW a 2 r 1 h 1 n 3 1 4 c 0 00 m 2 t 2 Entering break read eval print loop try relaxing any restrictive options e g try the hard strategy or increasing workspace type strategy options for info on strategies type options for ACE for info on options type DisplayACEOptions to see current ACE options type SetACEOptions lt optioni gt lt valuel gt 76 to s i e Appendix B Examples et lt optioni gt to lt valuel gt etc pass options after the in the usual way and then type return to continue Othe brk gt brk gt brk gt brk gt brk gt rec rwise type quit to quit to outer loop Let s give ACE enough coset numbers to work with and while we re at it see the effect of
6. I Variables 78 Appendix B Examples 1 ACEResExample ALLRELS newrels F a b newF x y 1 L2_8 L2_16 L3_3s U3_3s M11 M12 L2_32 1 U3_4s Jis L3_5s PSp4_4s presentations 1 I Also 1 I TCENUM ACETCENUM Todd Coxeter Enumerator is now ACE 1 I For an example of their application you might like to try I gap gt ACEReadResearchExample doL28 g optex 1 2 4 5 8 I the output is 65 lines followed by a gap gt prompt 1 I For information type Using ACEReadResearchExample gap gt The output Info ed at InfoACELevel 1 states that a number of new functions are defined During a GAP session you can find out details of these functions by typing gap gt Using ACEReadResearchExample Finer Points with Examples The examples in this chapter are intended to provide the nearest GAP equivalent of the similarly named sections in Appendix A of ace3001 ps the standalone manual in directory standalone doc There is a lot of detail here which the novice ACE Package user won t want to know about Please despite the name of the first section of this chapter read the examples in Appendix B first C 1 Getting Started Each of the functions ACECosetTableFromGensAndRels see 1 2 1 ACEStats see 1 3 1 non interactive version and ACEStart see 6 1 1 may be called with three arguments fgens the group generators rels the group relators and sgens the subgroup generators While i
7. a 2 b 3 ab 5 Subgroup Name Id Subgroup Generators Wo 1000000 Max 333331 Mess 1000 Ti 1 Ho 1 Loop 0 As 0 Path 0 Row 1 Mend 0 No 3 Look 0 Com 10 C 0 R 0 Fi 6 PMod 3 PSiz 256 DMod 4 DSiz 1000 INDEX 60 a 60 r 77 h 1 n 77 1 3 c 0 00 m 66 t 76 87 Observe that the fgens and subgroup generators the empty list arguments are transmitted to ACE via the ACE binary s group and generators options respectively Observe also that the relator a b 5 is expanded by GAP to a b a b a b a b a b when transmitted to ACE and then ACE correctly deduces that it s a b 75 Since we did not specify a strategy the default see 5 1 1 strategy was followed and hence coset number definitions were R i e HLT style and a total of 76 coset numbers t 76 were defined if we had tried felsch we would have achieved the best possible t 60 Note that ACE already knew the group generators and subgroup generators so we could have avoided re transmitting that information by using the relators see D 2 2 option gap gt ACEStart 1 relators ToACEWords fgens a 2 b 3 a b 5 gt gt gt gt 1 1 1 1 1 1 1 1 enumeration A_5 subgroup Id max 0 messages 1000 Detected usage of a synonym of one or more of the options group relators generators Discarding current values of args The new args will be extracted from ACE later ToACE gt r
8. 3 2 Finding Deductions Coincidences and Preferred Definitions First let us broadly discuss strategies and how they influence definitions By definition we mean the allocation of a coset number In a complete coset table each group relator produces a cycle of cosets numbers at each coset number in particular at coset 1 i e for each relator w and for each coset number 7 successive application of the letters of w trace through a sequence of coset numbers that begins and ends in see Section 3 1 for an example It has been found to be a good general rule to use the given group relators as subgroup generators This ensures the early definition of some useful coset numbers and is the basis of the default strategy see 5 1 1 The number of group relators included as subgroup generators is determined by the no option see 4 13 4 Over a wide range of examples the use of group relators in this way has been shown to produce generally beneficial results in terms of the maximum number of cosets numbers defined at any one time and the total number of coset numbers defined In CDHW73 it was reported that for some Macdonald group G a 3 examples pure Felsch type strategies that don t include the given group relators as subgroup generators e g the felsch 0 strategy see 5 1 3 defined significantly more coset numbers than HLT type e g the hlt strategy see 5 1 5 strategies The comparison of these strategies in terms of total number o
9. 82 Appendix C Finer Points with Examples of obtaining a record containing enumeration statistics We have already seen an example of that in Sec tion 1 2 So here we will consider two options that prevent one entering a break loop namely the silent see 4 11 3 and incomplete see 4 11 6 options Firstly let s take the last ACEStats example but use ACECosetTableFromGensAndRels instead and include the silent option We still have the InfoACE level set at 3 gap gt ACECosetTableFromGensAndRels fgens start print 1 12 gt silent I ACE 3 001 Wed Oct 31 09 40 18 2001 I SSsSSsssssssssssssSSsSsssssssssssssssssse I Host information 1 name rigel I OVERFLOW a 249998 r 83333 h 83333 n 249999 1 337 c 0 09 m 249998 t 2499 98 I co a 249998 r 83333 h 83333 n 249999 c 0 00 1 coset a A b B order rep ve I 5 Sar a SO SS A LS 1 1 2 3 4 5 1 2 6 1 7 8 Oo a I 3 1 9 10 11 Oo A I 4 12 13 14 1 O b I 5 15 16 1 17 Oo B 1 6 18 2 19 20 O aa 1 7 21 22 23 2 QO ab 1 8 24 25 2 26 Oo aB I 9 3 27 28 29 Oo AA I 10 30 31 32 3 O Ab I 11 33 34 3 35 O AB 1 12 36 4 37 38 O ba I ex fail Since the enumeration overflowed and the silent option was set ACECosetTableFromGensAndRels simply returned fail But hang on ACE at least has a partial table we should be able to obtain it in GAP format in a situation like this We can We simply use the incomplete
10. ACECosetCoincidence i n F ACECosetCoincidence n F for the ith or default interactive ACE process started by ACEStart return the representative of coset n where n must be a positive integer and add it to the subgroup generators i e equates this coset with coset 1 the subgroup ACERedo is automatically invoked ACERandomCoincidences i subindex ACERandomCoincidences subindex ACERandomCoincidences i subindex ACERandomCoincidences subinder ACERandomCoincidences i subindex attempts ACERandomCoincidences subindex attempts gs ieo iie ie ie ie for the ith or default interactive ACE process started by ACEStart attempt up to attempts or in the first four forms 8 times to find nontrivial subgroups with index a multiple of subindex by repeatedly making random coset numbers coincident with coset 1 and seeing what happens The starting coset table must be non empty but must not be complete use ACERandomlyApplyCosetCoincidence see 6 7 9 if your table is already complete For each attempt by applying ACE s rc option see D 2 9 random coset representatives are repeatedly added to the subgroup and the enumeration redone If the table becomes too small the attempt is aborted the original subgroup generators restored and another attempt made If an attempt succeeds then the new set of subgroup generators is retained ACERandomCoincidences returns the list of new subgroup generators added Use ACESubg
11. ab ab ab ab ab 7 ab from CM72 and let H be the subgroup ab There is an isomorphism from G to Sg mapping a onto 1 2 and ab onto 1 2 3 4 5 6 It follows that maps ab into Ag So we know that the normal closure of H has index 2 in G Let us observe this via ACE First we start an enumeration with max set to 80 Section 8 Primitive ACE Read Write Functions 61 gap gt F FreeGroup a b gap gt a F 1 b F 2 gap gt fgens GeneratorsOfGroup F gap gt rels a 2 b 6 a b 1 a b 3 a b 1 a b 2 4 axb 5 gt a b 2xa b 2 2 gap gt sgens a b 3 gap gt i ACEStart fgens rels sgens max 80 gap gt IsCompleteACECosetTable i false gap gt ACEConjugatesForSubgroupNormalClosure i add I ACEConjugatesForSubgroupNormalClosure All traceable conjugates in subgp Though we know that H is not equal to its normal closure we did not get any new elements we had warned above of such a possibility Apparently our incomplete table is too small So let us increase max to 100 and continue gap gt ACEContinue i max 100 gap gt IsCompleteACECosetTable i false gap gt ACEConjugatesForSubgroupNormalClosure i add b 1 xa b 4 gap gt IsCompleteACECosetTable i true gap gt ACEStats i index 20 This time we got a new element and after adding it to the subgroup generators we obtained a comple
12. b ab a tb 1 There are 4 24 relator orderings and 24 16 combinations of relator or inverted relator Exponents are taken into account when rotating relators so the relators given give rise to 1 1 2 and 2 rotations respectively for a total of 1 1 2 2 4 combinations So for val 7 resp 3 24 16 4 1536 resp 16 4 64 equivalent presentations are tested Now we describe the output of ACEA11EquivPresentations it is a record with fields primingResult the ACE enumeration result message see Section A 2 of the priming run 50 Chapter 6 Functions for Using ACE Interactively primingStats the enumeration result of the priming run as a GAP record with fields index cputime cputime Units activecosets maxcosets and totcosets exactly as for the record returned by ACEStats see 1 3 1 equivRuns a list of data records one for each progressively best run where each record has fields rels the relators in the order used for the run enumResult the ACE enumeration result message see Section A 2 of the run and stats the enumeration result as a GAP record exactly like the record returned by ACEStats see 1 3 1 summary a record with fields successes the total number of successful i e having finite enumeration index runs runs the total number of equivalent presentation runs executed maxcosetsRange the range of values as a GAP list inside which each equivRuns i maxcosets li
13. in this way remain there until an explicit PopOptions call is made In contrast options passed in the usual way behind a colon following a function s arguments see 4 10 in the GAP Reference Manual are local and disappear from OptionsStack after the function has executed successfully nevertheless a function that is passed options this way will also see any global options or any options passed down recursively from functions calling that function unless those options are over ridden by options passed via the function Also note that duplication of option names for different programs may lead to misinterpretations Since a non empty OptionsStack is potentially a mine field for the unwary user the function ResetOptionsStack see 8 in the Reference Manual is now in the GAP library and FlushOptionsStack F introduced in version 3 001 of the ACE Package to perform the same function is now a synonym for Rese tOptionsStack it simply executes PopOptions until OptionsStack is empty However ResetOptionsStack or FlushOptionsStack does not wipe out the options already passed to an interactive ACE process We have provided GetACEOptions see 6 5 7 to keep track of options that the ACE binary process still considers active which may or may not be still on the OptionsStack There is the interactive SetACEOptions see 6 5 8 to change such options or of course you can always elect to use ACEQuit see 6 1 2 and then start a new interacti
14. index 0 cputime 10 cputimeUnits 10 2 seconds activecosets 249998 maxcosets 249998 totcosets 249998 The values we gave to the print option told ACE to print the first 12 lines and include coset representatives Note that since there are no relators the table has separate columns for generator inverses So the default workspace of 1000000 words allows a table of 249998 1000000 4 2 cosets Since row filling see 4 14 1 is on by default the table is simply filled with cosets in order Note that a compaction phase is done before printing the table but that this does nothing here the lowercase co tag since there are no dead cosets The coset representatives are simply all possible freely reduced words in length plus lexicographic i e lenlex see Section 3 4 order Using ACECosetTableFromGensAndRels The essential difference between the functions ACEStats and ACECosetTableFromGensAndRels is that ACES tats parses the results message from the ACE binary and outputs a GAP record containing statistics of the enumeration and ACECosetTableFromGensAndRels after parsing the results message goes on to parse ACE s coset table if it can and outputs a GAP list of lists version of that table So if we had used ACE CosetTableFromGensAndRels instead of ACEStats in our examples above we would have observed similar output except that we would have ended up in a break loop because the enumeration overflows instead
15. max 50 mess 10 but we use ACE options gt A5 274 gap gt GeneratorsOfGroup G Just to show we indeed have a perm n rep n 2 4 3 5 7 15 8 14 10 13 12 16 2 6 7 3 11 12 4 14 5 8 9 13 10 15 16 1 2 3 8 4 9 5 10 6 7 11 15 12 14 13 16 1 3 2 8 4 13 5 6 7 10 9 16 11 12 14 15 1 4 2 9 3 13 5 14 6 15 7 11 8 16 10 12 1 5 2 10 3 6 4 14 7 8 9 12 11 16 13 15 gap gt Order G 960 The call to PerfectGroup produced an output string that identifies the group G but we didn t see how ACE became involved here Let s redo that part of the above example after first setting the InfoLevel of InfoACE to 3 so that we may get to glimpse what s going on behind the scenes Section 1 Example where ACE is made the Standard Coset Enumerator gap gt SetInfoACELevel 3 Just to see what s going on behind the scenes gap gt Recall that we did TCENUM ACETCENUM gap gt G PerfectGroup IsPermGroup 16 60 1 Arguments as per usual gt max 50 mess 10 but we use ACE options gt I ACE 3 001 Sun Sep 30 22 08 11 2001 I SSsSssssssssssssssssSssssssssssssssssssee I Host information 1 name rigel I 1 ACE 3 001 Run Parameters I Group Name G I Group Generators abstuv I Group Relators a 2 s 72 t 72 u 2 v 72 b 73 st 72 uv 72 1 su 2 sv 2 tu 2 tv 2 asa
16. nevertheless we provide the following functions IsKnownACEOption optname F returns true if optname is a mixed case abbreviation of a field of KnownACEOptions or false otherwise IsKnownACEOption optname is equivalent to ACEOptionData optname known ACEPreferredOptionName optname F returns the lowercase unabbreviated first alternative of optname if it is a known ACE option or optname in lowercase otherwise ACEPreferredOptionName optname is equivalent to ACEOptionData optname synonyms 1 IsACEParameterOption optname E returns true if optname is an ACE parameter option ACE Parameter Options are described in Sec tion 4 12 1 IsACEParameterOption optname is equivalent to ACEPreferredOptionName optname in RecNames ACEParameterOptions IsACEStrategyOption optname F returns true if optname is an ACE strategy option see Section 4 9 IsACEStrategyOption optname is equivalent to ACEPreferredOptionName optname in ACEStrategy0ptions 4 9 The ACEStrategyOptions List ACEStrategyOptions V is a GAP list that contains the strategy options known to the ACE interface functions gap gt ACEStrategyOptions default easy felsch hard hlt purec purer sims See Chapter 5 for details regarding the ACE strategy options 4 10 ACE Option Synonyms ACEOptionSynonyms V is a GAP record A number of known ACE options have synonyms The fields of the ACEOptionSynonym
17. return the GAP relators of the ith or default interactive ACE process If no relators have been saved for the interactive ACE process possibly because the process was started via ACEStart 0 see 6 1 1 the ACE process is interrogated the equivalent in GAP is saved and returned Essentially ACERelators i interro gates ACE and establishes ACEData io i args rels if necessary and returns ACEData io i args rels As a side effect if any of the remaining fields of ACEData io i args or ACEData io i acegens are unset they are also set ACESubgroupGenerators i F ACESubgroupGenerators F return the GAP subgroup generators of the ith or default interactive ACE process If no subgroup generators have been saved for the interactive ACE process possibly because the process was started via ACEStart 0 see 6 1 1 the ACE process is interrogated the equivalent in GAP is saved and returned Essentially ACE SubgroupGenerators i interrogates ACE and establishes ACEData io i args sgens if necessary and returns ACEData io i args sgens As a side effect if any of the remaining fields of ACEData io i args or ACEData io 7z acegens are unset they are also set 9 gt 52 Chapter 6 Functions for Using ACE Interactively DisplayACEArgs i F DisplayACEArgs F display the arguments i e fgens rels and sgens of the ith or default process started by ACEStart In fact DisplayACEArgs i is just a pretty printer of th
18. see 6 7 2 ACECosetTable see 1 2 1 or ACEConju gatesForSubgroupNormalClosure see 6 7 10 is invoked ACEStandardCosetNumbering i F ACEStandardCosetNumbering F compact and then do a lenlex standardisation see Section 3 4 of the numbering of cosets in the coset table of the ith or default interactive ACE process started by ACEStart That is for a given ordering of 3 58 Chapter 6 Functions for Using ACE Interactively the generators in the columns of the table they produce a canonic table A table that includes a column for each generator inverse immediately following the column for the corresponding generator standardised according to the lenlex scheme has the property that a row major scan i e a scan of the successive rows of the body of the table row by row from left to right encounters previously unseen cosets in numeric order This function does not display the new table use ACEDisplayCosetTable see 6 5 12 for that Notes In a lenlex canonic table the coset representatives are ordered first according to length and then the lexicographic order defined by the order the generators and their inverses head the columns Note that unless special action is taken ACE avoids having an involutory generator in the first column by swapping the first two generators except when there is only one generator or when the second generator is also an involution so the lexicographic order used by ACE need not necessarily correspon
19. the same as that obtained with sr 1 no progress messages and the final results message Recall F is the free group we defined on generators fgens a and b Here we will be interested in seeing what is transmitted to the ACE binary so we will set the InfoACE level to 4 what is transmitted to ACE will now appear behind a ToACE gt prompt and we will still see the messages from ACE Note that when GAP prints F 1 fgens 1 it displays a but the variable a is at the moment unassigned so for convenience in defining relators for example we first assign the variable a to be F 1 and b to be F 2 gap gt SetInfoACELevel 4 gap gt a F 1 b F 2 gap gt Enumerating A_5 lt a b a 2 b 3 a b 5 gt gap gt over Id trivial subgp gap gt ACEStart 1 fgens a 2 b 3 a b 5 O gt 4th arg empty to define Id Section 1 Getting Started enumeration A_5 Define the Group Name subgroup Id Define the Subgroup Name max 0 Set max back to default no limit messages 1000 Progress messages every 1000 iter ns ToACE gt group ab ToACE gt relators a 2 b 3 a b axb axb xax xb axb ToACE gt generators ToACE gt enumeration A_5 ToACE gt subgroup Id ToACE gt max 0 ToACE gt messages 1000 ToACE gt text OK ToACE gt text OK ToACE gt Start ACE 3 001 Run Parameters Group Name A_5 Group Generators ab Group Relators
20. where n is the number of columns in the table This default fill factor allows a moderate amount of gap filling If fill is 1 then there is no gap filling A large value of fill can cause what is in effect infinite looping resolved by the coset enumeration failing However in general a large value does work well The effects of the various gap filling strategies vary widely It is not clear which values are good general defaults or indeed whether any strategy is always not too bad This option is identified as Fi in the Run Parameters block obtained when messages is non zero of the ACE output since for the ACE binary fi is an allowed abbreviation of i11 However fi is a GAP keyword and so the shortest abbreviation of fill allowed by the interface functions is fil Section 15 ACE Parameter Options for R Style Definitions 35 pmode val Option for preferred definitions val should be in the integer range 0 to 3 Shortest abbreviation pmod The value of the pmode option determines which definitions are preferred If the argument is 0 then Felsch style definitions are made using the next empty table slot If the argument is non zero then gaps of length one found during relator scans in Felsch style are preferentially filled subject to the value of 111 If the argument is 1 they are filled immediately and if it is 2 the consequent deduction is also made immediately of course these are also put on the deduction stac
21. 1 a b gt messages 0 lenlex I ToACE gt group ab I ToACE gt relators aa b 3 a xb a b a xb axkb axb I ToACE gt generators a b I ToACE gt asis 1 I ToACE gt messages 0 I ToACE gt text I ox I ToACE gt text I x I ToACE gt Start I INDEX 12 a 12 r 17 h 1 n 17 1 3 c 0 00 m 15 t 16 1 gap gt ACEStandardCosetNumbering I ToACE gt standard I CO ST a 12 r 13 h 1 n 13 c 0 00 gap gt The capitalised CO indicates space was recovered during compaction gap gt ACEDisplayCosetTable 12 I ToACE gt print 12 I co a 12 r 13 h 1 n 13 c 0 00 92 Appendix C Finer Points with Examples 1 coset a A b B order rep ve I eee Se SS aa ee ee See Se SSS 1 1 2 2 3 2 1 2 1 1 1 3 2 a 1 3 4 4 2 1 3 b I 4 3 3 5 6 5 ba 1 5 7 7 6 4 5 bab 1 6 8 8 4 5 2 baB I 7 5 5 8 9 5 baba I 8 6 6 9 7 5 baBa 1 9 10 10 7 8 3 babaB I 10 9 9 11 12 3 babaBa I 11 12 12 12 10 3 babaBab I 12 11 11 10 11 2 babaBaB 1 eese n a oea You may have noticed the use of ACE s text option several times above this just tells ACE to print the argument given to text as a comment This is used by the GAP interface as a sentinel when the string appears in the ACE output the GAP interface knows not to expect anything else C 2 Emulating Sims Here we consider the various sims strategies see 5 1 8 with respect to duplicating Sims
22. 34 1 1 b 8 35 35 9 2 36 37 38 38 xy 9 39 39 2 8 40 41 42 42 xY 10 43 43 44 45 46 2 47 47 xa 11 48 48 49 50 2 46 51 51 xA 12 52 52 53 54 55 56 2 2 xb 13 3 3 57 58 59 60 61 61 yx 14 62 62 63 64 65 3 66 66 ya 15 67 67 68 69 3 65 70 70 yA 16 71 71 72 73 74 75 3 3 yb 17 4 4 76 77 78 79 80 80 Yx 18 81 81 82 83 84 4 85 85 Ya 19 86 86 87 88 4 84 89 89 YA 20 90 90 91 92 93 94 4 4 Yb Another standardisation scheme for coset tables the default scheme of versions of GAP up to GAP 4 2 numbers cosets according to coset representative word length in the group generators and lexical ordering imposed by the user supplied ordering of the group generators it is known as semilenlex since though like lenlex generator inverses do not feature Here again is 20 lines of the coset table of the group with presentation x y a b x y3 af b this time semilenlex standardised coset no x y a b rep ve cee renee ers em A See ee E EN 1 2 3 4 5 2 1 6 T 8 x 3 9 10 11 12 y 4 13 14 15 16 a 5 17 18 19 1 b 6 20 21 22 23 xy 7 24 25 2 26 xa 8 27 28 29 2 xb 9 3 30 31 32 yx 10 33 1 34 35 yy 11 36 37 38 39 ya 12 40 41 42 3 yb 13 4 43 44 45 ax 14 46 4T 48 49 ay 15 50 51 52 53 aa 16 54 55 56 4 ab 17 5 57 58 59 bx 18 60 61 62 63 by 19 64 65 66 67 ba 20 6 68 69 70 xyx Section 6 Other Terminology 23 The term semilenlex was coined by Edmund Robertson and Joachim Neubtiser for the s
23. 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 30 lines omitted here 472 473 474 475 476 477 478 479 480 B 3 Example of Using ACE Interactively Using ACEStart 69 Now we illustrate a simple interactive process with an enumeration of an index 12 subgroup isomorphic to Cs within A Observe that we have relied on the default level of messaging from ACE messages 0 which gives a result line the I INDEX line here only without parameter information The result line is visible in the Info ed component of the output below because we set the InfoLevel of InfoACE to a value of at least 2 in fact we set it to 3 doing SetInfoACELevel 2 would make only the result line visible We have however used the option echo so that we can see how the interface handled the arguments and options On line try SetInfoACELevel 3 ACEExample A5 C5 ACEStart this is nearly equivalent to the sequence following but the variables F a b G are not accessible being local to ACEExamp1e gap gt SetInfoACELevel 3 So we can see output from ACE binary gap gt F FreeGroup a b a F 1 b F 2 gap gt G F a 2 b 3 a b 75 lt fp group on the generators a b gt gap gt ACEStart FreeGeneratorsOfFpGroup G RelatorsOfFpGroup G a b gt Options gt echo Echo handled by GAP not ACE gt enum
24. ACEStyle i F ACEStyle F returns the current enumeration style as one of the strings C Cr CR R R Rc R C or R C defaulted see Section 3 1 The next two functions of this section are really intended for ACE standalone gurus To fully understand their output you will need to consult the standalone manual and the C source code ACEDumpVariables i ACEDumpVariables ACEDumpVariables 7 level ACEDumpVariables level ACEDumpVariables i level detail ACEDumpVariables level detail gs ieo iie ie ie ie dump the internal variables of ACE of the ith or default process started by ACEStart level should be one of 0 1 or 2 and detail should be 0 or 1 The value of level determines which of the three levels of ACE to dump You will need to read the standalone manual to understand what Levels 0 1 and 2 are all about The value of detail determines the amount of detail detail 0 means less detail The first two forms of ACEDumpVariables with no list argument selects level 0 detail 0 The third and fourth forms with a list argument containing the integer level makes detail 0 This command is intended for gurus the source code should be consulted to see what the output means ACEDumpStatistics i F ACEDumpStatistics F dump ACE s internal statistics accumulated during the most recent enumeration of the ith or default process started by ACEStart provided the ACE binary
25. Com 10 I C 0 R 0 Fi 7 PMod 3 PSiz 256 DMod 4 DSiz 1000 1 Hoan rec enumeration G subgroup H workspace 1000000 max 249998 messages 0 time 1 hole 1 loop 0 asis 0 path 0 row 1 mendelsohn 0 no 0 lookahead 0 compaction 10 ct 0 rt 0 fill 7 pmode 3 psize 256 dmode 4 dsize 1000 Observe that the ACEStart call returned an integer 1 here All 8 forms of the ACEStart function return an integer that identifies the interactive ACE interface function initiated or communicated with We may use this integer to tell any interactive ACE interface function which interactive ACE process we wish to communicate with Above we passed 1 to the ACEParameters command which caused sr 1 see D 5 7 to be passed to the interactive ACE process indexed by 1 the process we just started and a record containing the parameter options see 4 12 1 is returned Note that the Run Parameters Group Generators Group Relators and Subgroup Generators are considered args i e arguments and a record containing these is returned by the GetACEArgs see 6 5 5 command or they may be obtained individually via the commands ACEGroupGenerators see 6 5 1 ACERelators see 6 5 2 or ACESubgroupGenerators see 6 5 3 We can obtain the enumeration statistics record via the interactive version of ACEStats see 6 6 2 gap gt ACEStats 1 The interactive version of A
26. GAP 62 Chapter 6 Functions for Using ACE Interactively values Be warned though that unless one of the modes ACEStart without a zero argument see 6 1 1 ACERedo see 6 2 3 or ACEContinue see 6 2 2 or their equivalent for the standalone ACE start redo or continue has been invoked since the last change of any parameter options see 4 12 1 some of the values reported by ACEParameters may well be incorrect ACEWrite i string F ACEWrite string F write string to the ith or default interactive ACE process string must be in exactly the form the ACE standalone expects The command is echoed via Info at InfoACE level 4 with a ToACE gt prompt i e do SetInfoACELevel 4 to see what is transmitted to the ACE binary ACEWrite returns true if successful in writing to the stream of the interactive ACE process and fail otherwise Note If ACEWrite returns fail which means that the ACE process has died you may like to try resur recting the interactive ACE process via ACEResurrectProcess see 6 3 4 ACERead i F ACERead F read a complete line of ACE output from the ith or default interactive ACE process if there is output to be read and returns fail otherwise When successful the line is returned as a string complete with trailing newline character Please note that it is possible to be too quick i e the return can be fail purely because the output from ACE is not there yet but if ACERead finds any
27. Note that we explicitly re set all of the listed enumerator options in all of the predefined strategies even though some of them have no effect For example the 111 value is irrelevant in HLT type enumeration see Section 3 1 The idea behind this is that if you later change some options individually then the enumeration retains the flavour of the last selected predefined strategy Note also that other options which may effect an enumeration are left untouched by setting one of the predefined strategies for example the values of max see 4 17 6 and asis see 4 13 1 These options have an effect which is independent of the selected strategy Note that apart from the felsch 0 and sims 9 strategies all of the strategies are distinct although some are very similar 5 1 The Strategies in Detail Please note that the strategies are based on various enumeration styles C style Cr style CR style R style R style Rc style R C style and defaulted R C style all of which are described in detail in Section 3 1 default Selects the default strategy Shortest abbreviation def This strategy is based on the defaulted R C style see Section 3 1 The idea here is that we assume that the enumeration is easy and start out in R style If it turns out not to be easy then we regard it as hard and switch to CR style after performing a lookahead see 4 15 2 on the entire table easy Selects an easy R styl
28. Options that don t affect the enumeration I echo enum F 2 7 aka C_29 subg Id I Other options I wo 2M mess 25000 purec I User Options I sg c I subgroup lt c gt I messages 0 ACECosetTableFromGensAndRels called with the following arguments Group generators a b c d e x y Group relators a b c 1 b c d 1 c d e 1 d e x 1 e x y 1 x y xa 1 y a b 1 Subgroup generators ACECosetTableFromGensAndRels called with the following options aceexampleoptions true inserted by ACEExample not passed to ACE echo true not passed to ACE enum F 2 7 aka C_29 wo 2M purec no value passed to ACE via option pure c sg c brackets are not passed to ACE subgroup lt c gt messages 0 I INDEX 1 a 1 r 2 h 2 n 2 1 4 c 0 00 m 332 t 332 E dd eb ede A E eels de a ae di bet e bls E E ob ae Pt dy bad betes bt a Now following on from our last example we shall demonstrate how one can recover from a break loop see Section 1 2 To force the break loop we pass max 2 see 4 17 6 while using the ACE interface function ACECosetTableFromGensAndRels with ACEExample in this way ACE will not be able to complete the enumeration and hence enters a break loop when it tries to provide a complete coset table While we re at it we ll pass the hlt see 5 1 5 strategy option which will over ride purec The InfoACE leve
29. a free froup with 2 generators since the second argument defines an empty relator list and since the third argument is an empty list of generators the subgroup defined is trivial So the enumeration overflows 80 Appendix C Finer Points with Examples gap gt ACEStats fgens I OVERFLOW a 249998 r 83333 h 83333 n 249999 1 337 c 0 10 m 249998 t 2499 98 rec index 0 cputime 10 cputimeUnits 10 2 seconds activecosets 249998 maxcosets 249998 totcosets 249998 The line starting with I is the Info ed results message from ACE see Appendix A for details on what it means Observe that since the enumeration overflowed ACE s result message has been translated into a GAP record with index field 0 To dump out the presentation and parameters associated with an enumeration ACE provides the sr see D 5 7 option However you won t see output of this command unless you set the InfoACELevel to at least 3 Also to ensure the reliability of the output of the sr option an enumeration should precede it for ACEStats and ACECosetTableFromGensAndRel1s the directive start see D 3 2 required to initiate an enumeration is inserted automatically after all the user s options except if the user herself supplies an option that initiates an enumeration namely one of start or begin see D 3 2 aep see D 1 1 or rep see D 1 2 Interactively the equivalent of the sr command is ACEParameters see 6 5 1
30. ab 5 I Subgroup Name H I Subgroup Generators a I Wo 1000000 Max 800 Mess 500 Ti 1 Ho 1 Loop 0 I As 0 Path 0 Row 1 Mend 1 No 28 Look 0 Com 10 I C 0 R 0 Fi 13 PMod 3 PSiz 256 DMod 4 DSiz 1000 1 aa I SG a 1 r 1 h 1 n 2 1 1 c 0 00 m 1 t 1 I RD a 321 r 68 h 1 n 412 1 5 c 0 00 m 327 t 411 I CC a 435 r 162 h 1 n 719 1 9 c 0 00 d 0 I CL a 428 r 227 h 1 n 801 1 13 c 0 00 m 473 t 800 I DD a 428 r 227 h 1 n 801 1 14 c 0 00 d 33 I CO a 428 r 192 h 243 n 429 1 15 c 0 00 m 473 t 800 I INDEX 480 a 480 r 210 h 484 n 484 1 18 c 0 00 m 480 t 855 I CO a 480 r 210 h 481 n 481 c 0 00 1 coset a A b B s t u v d I Grrr rer 1 1 1 1 7 6 2 3 4 5 1 1 2 4 4 22 36 1 8 10 11 2 476 lines omitted here Section 3 Example of Using ACE Interactively Using ACEStart 1 479 479 479 384 383 475 468 470 A471 479 1 480 480 480 421 420 470 469 475 476 480 1 8 13 6 7 4 5 2 34 35 32 33 3 48 49 46 47 57 59 28 21 25 62 64 22 26 66 20 67 69 74 11 12 9 10 89 65 87 30 lines omitted here 477 438 478 446 475 479 471 473 476 469 1 8 13 6 7 4 5 2 34 35 32 33 3 48 49 46 47 57 59 28 21 25 62 64 22 26 66 20 67 69 74 11 12 9 10 89 65 87 30 lines omitted here 477 438 478 446 475 479 471 473 476 469 363 lines omitted here 1 2 3 4 5 6 7
31. above is expensive and should be avoided unless really needed Additionally there may appear the statistics m and t as for the results message d or s d and c as for the DS progress message The meanings of the various statistics and tags will follow later The following is a sample progress message I AD a 2 r 1 h 1 n 3 h 66 67 1 1 c 0 00 m 2 t 2 with tag AD and values for the statistics a r h n h appears because messages lt 0 1 c m and t The following is a sample results message I INDEX 12 a 12 r 16 h 1 n 16 1 3 c 0 01 m 14 t 15 which in this case declares a successful enumeration of the coset numbers of a subgroup of index 12 within a group and as it turns out values for the same statistics as the sample progress message You should see all the above and a little more except that your dates and host information will no doubt differ by running gap gt ACEExample A5 C5 _ echo 0 messages 1 In the following table we list the statistics that can follow a progress or results message tag in order a number of active coset numbers r number of applied coset numbers h first potentially incomplete row n next coset number definition h percentage of holes in the table if messages lt 0 1 number of main loop passes c total CPU time m maximum number of active coset numbers t total number of coset numbers defined s new deduction stack size with DS tag d current deduction stack si
32. an ACE function for which those options are not intended the ACE function will pass those options to the ACE binary If those options are unknown to the ACE interface and ACEIgnoreUnknownDefault false and aceignoreunknown is not passed see 4 11 2 and 4 11 10 a warning is issued Options that are unknown to the ACE binary are simply ignored by ACE and a warning that the option was ignored appears in the ACE output which the user will not see unless the InfoLevel of InfoACE or InfoWarning is set to 1 This option enables the user to avoid such options being passed at all thus avoiding the warning messages and also any options that coincidentally are ACE options but are not intended for the ACE function being called 10 gt aceignoreunknown Directs an ACE function to ignore any options not known to the ACE interface Shortest abbrevia tion aceignoreu 11 gt 12 gt 13 gt 14 gt 15 gt 1 gt 32 Chapter 4 Options for ACE This option is provided for similar reasons to aceignore Normally it is safe to include it to avoid aberrant warning messages from the ACE interface However fairly obviously it should not be passed without a value or set to true in the situation where a new ACE binary has been installed with new options that are not listed among the fields of KnownACEOptions which you intend to use Omitting the aceignoreunknown option is equivalent to setting it to the value of ACEIgnoreUnknownDefault see 4 11
33. and last and by must be positive integers Shortest abbreviation pr In the first no value form print prints the entire coset table without orders or coset representatives In the second and third forms the absolute value of val is taken to be the last line of the table to be printed and 1 is taken to be the first in the fourth and fifth forms val is taken to be the first line of the table to be printed and last is taken to be the number of the last line to be printed In the last form the table is printed from line val to line last in steps of by If val is negative then the orders modulo the subgroup if available and coset representatives are printed also INTERACTIVELY use ACEDisplayCosetTable see 6 5 12 sc val stabilising val Print out the coset numbers whose elements normalise the subgroup val must be an integer Short est abbreviation of stabilising is stabil If val gt O the first val non trivial i e other than coset 1 coset numbers whose elements normalise the subgroup are printed If val 0 all non trivial coset numbers whose elements normalise the subgroup plus their representatives are printed If val lt 0 the first val non trivial coset numbers whose elements normalise the subgroup plus their representatives are printed Note The name of this option is an historical hangover It is named for the property that elements that normalise a subgroup may be said to stabilise that
34. b 1 Subgroup generators I ACE 3 001 Sun Sep 30 22 16 08 2001 I sss22senaaaa I Host information I name rigel ACEStats called with the following options echo true not passed to ACE enum F 2 7 aka C_29 subg Id wo 2M mess 25000 purec no value passed to ACE via option pure c I Section 4 Fun with ACEExample 73 1 ACE 3 001 Run Parameters I Group Name F 2 7 aka C_29 I Group Generators abcdexy I Group Relators abC bcD cdE deX exY xyA yaB I Subgroup Name Id I Subgroup Generators I Wo 2M Max 142855 Mess 25000 Ti 1 Ho 1 Loop 0 I As 0 Path 0 Row 0 Mend 0 No 0 Look 0 Com 100 I C 1000 R 0 Fi 1 PMod 0 PSiz 256 DMod 4 DSiz 1000 1 Po I DD a 5290 r 1 h 1050 n 5291 1 8 c 0 00 d 2 I CD a 10410 r 1 h 2149 n 10411 1 13 c 0 01 m 10410 t 10410 I DD a 15428 1 h 3267 n 15429 1 18 c 0 01 d 0 I DD a 20430 1 h 4386 n 20431 1 23 c 0 02 d 1 I DD a 25397 1 h 5519 n 25399 1 28 c 0 01 d 1 I CD a 30313 r 1 h 6648 n 30316 1 33 c 0 01 m 30313 t 30315 I DS a 32517 1 h 7326 n 33240 1 36 c 0 01 s 2000 d 997 c 4 I DS a 31872 1 h 7326 n 33240 1 36 c 0 00 s 4000 d 1948 c 53 I DS a 29077 1 h 7326 n 33240 1 36 c 0 00 s 8000 d 3460 c 541 I DS a 23433 1 h 7326 n 33240 1 36 c 0 01 s 16000 d 5940 c 2061 I DS a 4163 r 1 h 7326 n 33240 1 36 c 0 03 s 32000 d 447 c 15554 I INDEX 29 a 29 r 1
35. bse ly G igo bed as es dal E tal oe th ee tes 1 1 1 1 ACE needs to define a total number of only relatively speaking 332 coset numbers before the final collapse to 1 coset number Notes To initiate the coset enumeration the start option see D 3 2 is quietly inserted after the user s supplied options unless the user herself supplies one of the enumeration invoking options which are start or one of its synonyms aep see D 1 1 or rep see D 1 2 When a user calls ACECosetTable with the lenlex option see 4 11 4 occasionally it is necessary to enforce asis 1 see 4 13 1 which may be counter to the desires of the user The occasions where this action is necessary are precisely those for which for the arguments gens and rels of ACECosetTable IsACEGeneratorsInPreferredOrder would return false The non interactive ACECosetTable and ACECosetTableFromGensAndRels now use an iostream to commu nicate with the ACE binary in order to avoid filling up a temporary directory with an incomplete coset table in the case where an enumeration overflows This is generally advantageous However on some systems it may not be advisable to repeatedly call ACECosetTable or ACECosetTableFromGensAndRels e g in a loop since one may run out of the pseudo ttys used for iostreams If you encounter this problem consider using an adaptation of the usage of the interactive forms of ACECosetTable and ACEStats see 6 6 1 and 6 6 2 together with A
36. but also meticulously proof read all drafts and made many insightful comments Many thanks also to Volkmar Felsch who in testing the ACE Package discovered a number of bugs made a number of important suggestions on code improvement thoroughly checked all the examples and provided the example found at the end of Section 6 7 which demonstrates rather nicely how one can use the function ACEConjugatesForSubgroupNormalClosure Finally we wish to acknowledge the contribution of Charles Sims The inclusion of the incomplete see 4 11 6 and lenlex see 4 11 4 options were made in response to requests to the GAP developers to include such options for coset table functions Also the definition of lenlex standardisation of coset tables see Section 3 4 is due to him 1 11 Changes from earlier versions A reasonably comprehensive history of the evolution of pre release versions of the ACE Package is contained in the file CHANGES in the gap directory The 3 xxx versions of the ACE Package were compatible with GAP 4 2 but were built for use with GAP 4 3 However the current version of the ACE Package requires at least GAP 4 4 Users who still have GAP 4 3 will need to use ACE 4 1 One important change in GAP from GAP 4 2 to GAP 4 3 that has relevance for ACE Package users is the change of the default standard for the numbering of cosets in a coset table see Section 3 4 ACEPackageVersion F gives the current version of the ACE Package i
37. by a text see D 7 1 directive emitted to ACE so that ACE s response can be used as a sentinel to flush out any user errors or any output from a user s use of Appendix D options Next if the messages option see 4 18 1 is set to a non zero value what is observed is a heading like I ACE 3 001 Run Parameters where 3 001 may be replaced be some later version number of the ACE binary followed by the input pa rameters developed from the arguments and options passed to ACECosetTableFromGensAndRels ACEStats or ACEStart After these appears a separator I followed by any progress messages progress messages only occur if messages is non zero recall that by default messages 0 followed by a results message 64 Appendiz A The Meanings of ACE s output messages In the case of ACECosetTableFromGensAndRels the results message is followed by a compaction CO or co progress message and a coset table ACE s exit banner which should look something like ACE 3 001 Sun Sep 30 22 03 36 2001 is only seen when running ACE as a standalone Both progress messages and the results message consist of an initial tag followed by a list of statistics All messages have values for the statistics a r h n h 1 and c excepting that the second h the one following the n statistic is only given if hole monitoring has been turned on by setting messages lt 0 which as noted
38. by the group generators and their inverses Entries of the coset table that are not yet defined are known as holes typically they are filled with 0 i e an invalid coset number It is customary in talking about coset enumeration to speak of cosets when really coset numbers are meant While we try to avoid this in this interface manual in certain word combinations such as coset application we will follow this custom The definition of a coset number may lead to deductions from the closing of rows in subgroup or relator tables These are kept in a deduction stack Also it may be found that different words in the generators defining different coset numbers really lie in the same coset of the given subgroup This is called a coincidence and will eventually lead to the elimination of the larger of the two coset numbers Until this elimination has been performed pending coincidences are kept in a queue of coincidences A definition that will actually close a row in a subgroup or relator table will immediately yield twice as many entries in the coset table as other definitions Such definitions are called preferred definitions the places in rows of a subgroup or relator table that they close are also referred to as gaps of length one or minimal gaps Such gaps can be found at little extra cost when relators are traced from a given coset number ACE keeps a selection of them in a preferred definition stack for use in some definition s
39. command and a second form with one argument fewer where the integer i is discovered by a default mechanism namely by determining the least integer i for which there is a currently active interactive ACE process We will thus commonly say that for the ith or default interactive ACE process a certain function performs a given action In each case it is an error if is not the index of an active interactive process or there are no current active interactive processes Notes The global method of passing options via PushOptions should not be used with any of the interactive functions In fact the OptionsStack should be empty at the time any of the interactive functions is called On quitting GAP ACEQuitAl1 is executed which terminates all active interactive ACE processes If GAP is killed without quitting before all interactive ACE processes are terminated zombie processes still living child processes whose parents have died will result Since zombie processes do consume resources in such an event the responsible computer user should seek out and kill the still living ace children e g by piping the output of a ps with appropriate options usually aux or ef to grep ace to find the process ids and then using kill try man ps and man kill if these hints are unhelpful 6 1 Starting and Stopping Interactive ACE Processes ACEStart fgens rels sgens options ACEStart i options ACEStart options ACEStar
40. commands Note that the ACEStart command without 0 as first argument inserts a start directive after the user option max gap gt ACEStart 1 max 12 I xx I OVERFLOW a 12 r 4 h 4 n 13 1 5 c 0 00 m 12 t 12 1 Now the following ACEDisplayCosetTable command does the equivalent of the print 1 12 option gap gt ACEDisplayCosetTable 1 1 12 I co a 12 r 4 h 4 n 13 c 0 00 1 coset a A b B order rep ve I ga SS SSS ae eS Ce a Se aa 1 1 2 3 4 5 1 2 6 1 7 8 O a 1 3 1 9 10 11 Oo A I 4 12 0 0 1 O b I 5 0 0 1 0 Oo B I 6 0 2 0 0 O aa 1 7 0 0 0 2 QO ab 1 8 0 0 2 0 Oo aB I 9 3 0 0 0 O AA 1 10 0 0 0 3 O Ab 1 11 0 0 3 0 O AB 1 12 0 4 0 0 O ba HI am ca Cn a Finally we call ACECosetTable with 1 argument which invokes the interactive version of ACECosetTable FromGensAndRels with the option incomplete 86 Appendix C Finer Points with Examples gap gt ACECosetTable 1 incomplete I start yes continue yes redo yes I I OVERFLOW a 12 r 4 h 4 n 13 1 4 c 0 00 m 12 t 12 I co a 12 r 4 h 4 n 13 c 0 00 I coset a A b B I Pasa SSeS SSS HSS aS 1 1 2 3 4 5 1 2 6 1 7 8 1 3 1 9 10 11 1 4 12 0 0 1 1 5 0 0 1 0 1 6 0 2 0 0 1 7 0 0 0 2 1 8 0 0 2 0 1 9 3 0 0 0 1 10 0 0 0 3 1 11 0 0 3 0 1 12 0 4 0 0 I ACECosetTable Coset table is incomplete reduced amp lenlex standardised 2 6
41. echo 2 SetACEOptions max 0 echo 2 Let s check what the options are now DisplayACEOptions enum F 2 7 aka C_29 wo mes pur Sg sub hlt max ech brk gt brk gt ACECo Grou 2M s 25000 ec true c J group lt c gt true 0 o 2 That s ok so now we return to escape the break loop return setTableFromGensAndRels called with the following arguments p generators a b c d e x y Group relators a b c 1 b c d 1 c d e 1 d e x 1 e x y 1 x y Subg ACECo enum wo mess pure sg subg hilt max echo Other asis comp ct dmod dsiz fill hole look loop mend no path pmod psiz xa 1 y xa b 1 roup generators setTableFromGensAndRels called with the following options F 2 7 aka C_29 M 25000 c no value passed to ACE via option pure c c brackets are not passed to ACE roup lt c gt no value 0 2 not passed to ACE options set via ACE defaults 0 action 10 IN I 0 e 0 e 1000 1 1 ahead 1 0 elsohn 0 0 0 e 0 e 256 Section 5 Using ACEReadResearchExample 77 row 1 rt 1000 time 1 I INDEX 1 a 1 r 2 h 2 n 2 1 3 c 0 00 m 2049 t 3127 bike ted a A E Road Dy E S eds tbs deals E a a a S Dts 1 1 1 1 Observe that purec did not disappear from the option list nev
42. enumerator can make an early return when this count hits the value of loop A value of 0 the default turns this feature off Guru Notes You can do lots of really neat things using this feature but you need some understanding of the internals of ACE to get real benefit from it path Turns on path compression To correctly process multiple concidences a union find must be performed If both path compression and weighted union are used then this can be done in essentially linear time see e g CLR90 Weighted union alone in the worst case is worse than linear but is subquadratic In practice path compression is expensive since it involves many coset table accesses So by default path compression is turned off it can be turned on by path It has no effect on the result but may affect the running time and the internal statistics Guru Notes The whole question of the best way to handle large coincidence forests is problematic Formally ACE does not do a weighted union since it is constrained to replace the higher numbered of a coincident pair In practice this seems to amount to much the same thing Turning path compression on cuts down the amount of data movement during coincidence processing at the expense of having to trace the paths and compress them In general it does not seem to be worthwhile compaction val Percentage of dead coset numbers to trigger compaction val should be an integer percentage in the integer r
43. example statistics of his strategies given in Section 5 5 of Sim94 and giving approximations of his even numbered strategies In order to duplicate Sims maximum active coset numbers and total coset numbers statistics one needs to work with the formal inverses of the relators and subgroup generators from Sim94 since definitions are made from the front in Sims routines and from the rear in ACE Also in instances where IsACEGen eratorsInPreferredOrder gens rels returns false for group generators fgens and relators rels one will need to apply the lenlex option to stop ACE from re ordering the generators and relators see 1 2 3 and 4 11 4 In general we can match Sims values for the sims 1 and sims 3 strategies the R style and R style Sims strategies with mendelsohn off and for the sims 9 C style strategy but sometimes we may not exactly match Sims statistics for the sims 5 and sims 7 strategies the R style and R style Sims strategies with mendelsohn on Sims does not specify an order for the Mendelsohn processing of cycled relators and evidently ACE s processing order is different to the one Sims used in his CHLT algorithm to get his statistics see 4 13 5 Note HLT as it appears in Table 5 5 1 of Sim94 is achieved in ACE with the sequence hlt lookahead 0 and CHLT is nearly equivalent to hlt lookahead 0 mendelsohn also Sims save false equates to R style rt positive ct 0
44. forms random presentations val an integer in the range 1 to 7 acts as for ACEAL1EquivPresentations and Npresentations when given should be a positive integer The routine first turns asis see 4 13 1 on and messages see 4 18 1 off i e sets messages to 0 and then generates and tests the requested number of random equivalent presentations For each presentation the relators used and the summary result line are printed by ACE To observe these messages set the InfoLevel of InfoACE to at least 3 Section 5 Interactive Query Functions and an Option Setting Function 51 ACERandomEquivPresentations parses the ACE messages translating them to GAP and thus returns a list of records similar to the field equivRuns of the returned record of ACEAllEquivPresentations Each record of the returned list is the data derived from a presentation run and has fields rels the relators in the order used for the run enumResult the ACE enumeration result message see Section A 2 of the run and stats the enumeration result as a GAP record exactly like the record returned by ACEStats see 1 3 1 Notes The relator inversions and rotations are genuinely random The relator permuting is a little bit of a kludge with the quality of the permutations tending to improve with successive presentations When the ACERandomEquivPresentations command completes the presentation active is the last one generated Guru Notes It might appear that
45. h 33240 n 33240 1 37 c 0 15 m 33237 t 33239 rec index 29 cputime 15 cputimeUnits 10 2 seconds activecosets 29 maxcosets 33237 totcosets 33239 Now let s see that we can add some new options even ones that over ride the example s options but first we ll reduce the output a bit by setting the InfoLevel of InfoACE to 2 and since we are not going to observe any progress messages from ACE with that InfoACE level we ll set messages 0 also we ll use the function ACECosetTableFromGensAndRels and so it s like our first encounter with F 2 7 we ll add the subgroup generator c via sg c see D 2 4 Observe that c is a string not a GAP group generator to convert a list of GAP words sgens in generators fgens suitable for an assignment of the sg option use the construction ToACEWords fgens sgens see 6 3 6 Note again that if only single lowercase letter strings are used to identify the GAP group generators the same strings are used to identify those generators in ACE It s actually fortunate that we could pass the value of sg as a string here since the generators of each ACEExample example are local variables and so are not accessible though we could call ACEExample with 2nd argument ACEStart and use ACEGroupGenerators to get at them For good measure we also change the string identifying the subgroup since it will no longer be the trivial group via the subgroup option see 4 19 2 In consideri
46. illustrate the various ways in which the ACE Package may be used and give some interactions with the ACEExample function In a number of cases we have set the InfoLevel of InfoACE to 3 so that all output from ACE is displayed prepended by I Recall that to also see the commands directed to ACE behind a ToACE gt prompt you will need to set the InfoACE level to 4 We have omitted the line gap gt LoadPackage ace true which is of course required at the beginning of any session requiring ACE B 1 Example where ACE is made the Standard Coset Enumerator If ACE is made the standard coset enumerator one simply uses the method of passing arguments normally used with those commands that invoke CosetTableFromGensAndRels but one is able to use all options available via the ACE interface As an example we use ACE to compute the permutation representation of a perfect group from the data library GAP s perfect group library stores for each group a presentation together with generators of a subgroup as words in the group generators such that the permutation representation on the cosets of this subgroup will be a nice faithful permutation representation for the perfect group The example we have chosen is an extension of a group of order 16 by the simple alternating group As gap gt TCENUM ACETCENUM Make ACE the standard coset enumerator gap gt G PerfectGroup IsPermGroup 16 60 1 Arguments as per usual gt
47. in ACE and save true for Sims HLT and CHLT equates to R style rt negative ct 0 in ACE Sims Felsch strategy coincides with ACE s felsch 0 strategy i e sims 9 is identical to felsch 0 See the options 5 1 5 4 15 2 4 13 5 4 13 2 4 13 3 and 5 1 3 The following duplicates the Total totcosets in ACE and Max Active maxcosets in ACE statistics for Example 5 2 of Sim94 found in Sims Table 5 5 3 for the sims 3 strategy gap gt SetInfoACELevel 1 No behind the scenes info please gap gt F FreeGroup r s t r F 1 s F 2 t F 3 gap gt ACEStats r s t r t r 2 1 s r s 2 1 t s t 2 7 1 0 gt sims 3 rec index 1 cputime 0 cputimeUnits 10 2 seconds activecosets 1 maxcosets 673 totcosets 673 By replacing sims 3 with sims i for i equal to 1 5 7 or 9 one may verify that for i equal to 1 or 9 Sims statistics are again duplicated and observe a slight variance with Sims statistics for equal to 5 or 7 Section 2 Emulating Sims 93 Now we show how one can approximate any one of Sims even numbered strategies Essentially the idea is to start an interactive ACE process using ACEStart see 6 1 1 with sims i for equal to 1 3 5 7 or 9 and max set to some low value mazstart so that the enumeration stops after only completing a few rows of the coset table Then to approximate Sims strateg
48. internal use by ACEExamp1e for the above purpose In the portion of the output due to the echo option if one has passed options to ACEExample one will see aceexampleoptions listed first and the result of the interaction of examplename s options and the additional options Consider the example A5 The effect of running gap gt ACEExample A5 ACEStart is essentially equivalent to executing gap gt file Filename DirectoriesPackageLibrary ace examples A5 gap gt ACEfunc ACEStart gap gt ReadAsFunction file except that some internal magic of ACEExample edits the example file and displays equivalent commands a user would execute If the user has passed options to ACEExample these appear in a User Options block after the original options of the example in the Info portion of the output By comparing with the portion of the output from the echo option unless the user has over ridden the echo option the user may directly observe any over riding effects of user passed options Please see Section B 4 for some sample interactions with ACEExampl1le Notes Most examples use the mess messages option To see the effect of this it is recommended to do Set InfoACELevel 3 before calling ACEExample with an example The coset table output from ACEExample when called with many of the examples and with the ACE function ACECosetTableFromGensAndRels is often quite long Recall that the output
49. is passed internally by ACEExample to the ACE interface function it calls when one invokes ACEExample with options Its purpose is to provide a mechanism for the over riding of an example s options by the user The option name is deliberately long and has no abbreviation to discourage user use 4 12 ACE Parameter Options ACEParameterOptions V is a GAP record whose fields are the ACE Parameter Options The ACE Parameter Options are options which if not supplied a value by the user are supplied a default value by ACE In fact the ACE Parameter Options are those options that appear along with Group Generators Group Relators and Subgroup Generators which are defined from ACE interface function arguments in the Run Parameters block of ACE output when for example the messages option is non zero For each field ACE parameter option of the ACEParameterOptions record the value assigned is the default value or a record of default values that are supplied by ACE when the option is not given a value by the user either indirectly by selecting a strategy option or directly 1 gt Section 13 General ACE Parameter Options that Modify the Enumeration Process 33 In the cases where the value of a field of the ACEParameterOptions record is itself a record the fields of that record are default and strategies for which the value assigned by that strategy differs from the default strategy A strategy here is the
50. is returned This option is included to make the behaviour of ACECoset TableFromGensAndRels compatible with that of the function CosetTableFromGensAndRels it replaces If the option incomplete is also set it overrides option silent lenlex Ensures that ACECosetTable and ACECosetTableFromGensAndRels output a coset table that is lenlex standardised The lenlex scheme numbers cosets in such a way that their preferred coset representatives in an alphabet consisting of the user submitted generators and their inverses are ordered first according to length and then according to a lexical ordering In order to describe what the lenlex scheme s lexical ordering is let us consider an example Suppose the generators submitted by the user are in user supplied order x y a b and represent the inverses of these generators by the corresponding uppercase letters X Y A B then the lexical ordering of lenlex is that derived from defining x lt X lt y lt Y lt a lt A lt b lt B Notes In some circumstances ACE prefers to swap the first two generators such cases are detected by the function IsACEGeneratorsInPreferredOrder see 1 2 3 In such cases special action is taken to avoid ACE swapping the first two generators this action is described in the notes for ACEStandardCosetNumbering see 6 7 2 When this special action is invoked a side effect is that any setting of the asis see 4 13 1 option by the user is ignored The lenlex
51. its inverse and the generators appear in user supplied order See below for an example which gives the first 20 lines of the lenlex standard coset table of the infinite group with presentation x y a b x7 y a4 b In the table each inverse of a generator is represented by the corresponding uppercase letter X represents the inverse of x etc and the lexical ordering of the representatives is that implied by defining an ordering of the alphabet of user supplied generators and their inverses to be r lt X lt y lt Y lt a lt A lt d lt B A lenlex standard coset table whose columns correspond in order to the already described alphabet of generators and their inverses has an important property a scan of the body of the table row by row from left to right encounters new coset numbers in numeric order Observe that the table below has this property the definition of coset 1 is implicit the first coset number we encounter in the table body is 2 then 2 again 3 4 5 6 7 then 7 again etc With the lenlex option see 4 11 4 the coset table output by ACECosetTable or ACECosetTableFromGen sAndRels is standardised according to the lenlex scheme 22 Chapter 3 Some Basics coset no x X y Y a A b B rep ve EREET TEEPEE EEEE SEEE eee ee eee oe EEEE 1 2 2 3 4 5 6 7 7 2 1 1 8 9 10 11 12 12 x 3 13 13 4 1 14 15 16 16 y 4 17 17 1 3 18 19 20 20 Y 5 21 21 22 23 24 1 25 25 a 6 26 26 27 28 1 24 29 29 A 7 30 30 31 32 33
52. may be suppressed by following the ACEExample command with a double semicolon Also try SetInfoACELevel 2 before calling ACEExample with an example 12 Chapter 1 The ACE Package If you unexpectedly observe aceexampleoptions in your output then most probably you have unintention ally passed options by the global method by having a non empty OptionsStack One possible remedy is to use FlushOptionsStack see 4 2 1 before trying your ACEExample call again As discussed in Section 4 6 there is generally no sensible meaning that can be attributed to setting a strategy option see Chapter 5 to false if you wish to nullify the effect of a strategy option pass another strategy option e g pass the default see 5 1 1 strategy option Also provided are ACEReadResearchExample filename F ACEReadResearchExample F which perform Read see Section 9 7 1 in the GAP Reference Manual on filename or with no argument the file with filename pgrelfind g in the res examples directory e g the effect of running gap gt ACEReadResearchExample pgrelfind g is equivalent to executing gap gt Read Filename DirectoriesPackageLibrary ace res examples gt pgrelfind g The examples provided in the res examples directory were used to solve a genuine research problem the results of which are reported in CHHR02 Please see Section B 5 for a detailed description and examples of its use ACEPrintResearchE
53. numbers A CO message line is printed if any cosets were recovered and a co line if none were This routine is called automatically if the cycles nc print or standard options see D 5 1 D 5 4 D 5 8 and D 6 2 are invoked INTERACTIVELY use ACERecover see 6 7 1 standard Compacts ACE s coset table and standardises the numbering of cosets according to the lenlex scheme see Section 3 4 Shortest abbreviation st For a given ordering of the generators in the columns of the table it produces a canonical numbering of the cosets This function does not display the new table use the print see D 5 8 for that Such a table has the property that a scan of the successive rows of the body of the table row by row from left to right encounters previously unseen cosets in numeric order Notes In a lenlex standard table the coset representatives are ordered first according to length and then the lexicographic order defined by the order the generators and their inverses head the columns Note that since ACE avoids having an involutory generator in the first column when it can this lexicographic order does not necessarily correspond with the order in which the generators were first put to ACE Two tables are equivalent only if their canonic forms are the same Invoking this option directly does not affect the GAP coset table obtained via ACECosetTable use the lenlex see 4 11 4 option if you want your table lenlex standardised The lenlex
54. of Non interactive ACE Functions 57 Interpretation of ACE Options 26 interruption of an interactive ACE process 47 IsACEGeneratorsInPreferredOrder 9 interactive 57 non interactive 9 IsACEParameterO0ption 29 IsACEProcessAlive 47 IsACEStandardCosetTable 9 Index IsACEStrategyO0ption 29 IsCompleteACECosetTable 53 IsKnownACEOption 29 K KnownACEOptions 28 L lenlex standardisation 9 lenlex standardisation scheme 21 57 Loading the ACE Package 17 loop 23 M maxcosets 9 23 Mode Options 98 N Non ACE binary Options 30 NonACEbinOptions 30 O OnBreak 74 option aceecho 32 option aceexampleoptions 32 option aceignore 31 option aceignoreunknown 31 option aceincomment 32 different to option text 103 option aceinfile 31 option acenowarnings 32 option aceoutfile 31 39 option aep 94 option ai 99 option ao 39 option asis 33 option begin 98 option bye 99 option cc 97 option cfactor 33 option check 98 option compaction 37 option contiguous 102 option continu 98 option continue deprecated use continu 98 option ct 33 option cycles 99 option default 42 option dmode 36 option dr 97 107 option ds 97 option dsize 36 option dump 99 option easy 42 option echo 32 option enumeration 39 option exit 99 option felsch 42 option ffactor 34 option fill 34 option generators 96 option group 96 option hard 42 option help 99
55. of the options detailed in Chapter 4 all at once Please see Section 1 7 for a discussion regarding global and local passing of options and the non orthogonal nature of ACE s options Each of ACECosetTableFromGensAndRels and ACECosetTable calls the ACE binary and if successful re turns a standard coset table as a GAP list of lists At the time of writing two coset table standardisations schemes were possible lenlex and semilenlex see Section 3 4 The user may control which standardisa tion scheme is used by selecting either the lenlex see 4 11 4 or semilenlex see 4 11 5 option otherwise since GAP 4 3 the table is standardised according to GAP s the value of CosetTableStandard which by default is lenlex for GAP 4 2 the variable CosetTableStandard didn t exist and the default standardisa tion scheme was semilenlex We provide IsACEStandardCosetTable see 1 2 2 to determine whether a table list of lists is standard relative to GAP s default standardisation scheme or with the use of options e g lenlex or semilenlex to another standardisation scheme If the determination of a coset table is unsuccessful then one of the following occurs with the incomplete option see 4 11 6 an incomplete coset table is returned as a list of lists with zeros in positions where valid coset numbers could not be determined or with the silent option see 4 11 3 fail is returned or a break loop is entered This last poss
56. only in their place of definition removed and lenlex standardised regardless of whether the semilenlex option is in force For GAP 4 2 an incomplete table was returned unstandardised unless the lenlex option see 4 11 4 was also set and the table was also not reduced When an incomplete table is returned a warning is emitted at InfoACE or InfoWarning level 1 7 gt aceinfile filename Creates an ACE input file filename for use with the standalone only filename should be a string Shortest abbreviation acein This option is only relevant to ACECosetTableFromGensAndRels and is ignored if included as an option for invocations of ACEStats and ACEStart If this option is used GAP creates an input file with filename filename only and then exits i e the ACE binary is not called This option is provided for users who wish to work directly with the ACE standalone The full path to the input file normally used by ACE i e when option aceinfile is not used is stored in ACEData infile 8 gt aceoutfile filename Redirects ACE output to file filename filename should be a string Shortest abbreviation aceo This is actually a synonym for the ao option Please refer to 4 20 1 for further discussion of this option 9 gt aceignore optionList Directs an ACE function to ignore the options in optionList optionList should be a list of strings Shortest abbreviation aceig If a function called with its own options in turn calls
57. option hlt 43 option hole 38 option incomplete 31 option lenlex 30 option lookahead 35 option loop 37 option max 38 option mendelsohn 34 option messages 39 option mode 98 option monitor 39 option nc 100 option no 34 option normal 100 option oo 100 option options 100 option order 100 option path 37 option pkgbanner 17 option pmode 35 option print 101 option psize 35 option purec 43 option purer 43 option qui 99 option rc 97 option recover 102 option redo 98 option relators 96 option rep 95 option rfactor 33 option rl 97 option row 35 option rt 33 108 option sc 101 option semilenlex 31 Options for Comments 103 Options for redirection of ACE Output 39 option sg 96 option silent 30 option sims 43 option sr 100 option stabilising 101 option standard 102 option start 98 option statistics 101 option stats 101 Options that Interact with the Operating System 99 Options that Modify a Presentation 96 Options that Modify the Coset Table 102 option style 102 option subgroup 39 option system 99 option text 103 option time 37 option trace 102 option tw 102 option workspace 36 Other Options 40 Other Terminology 23 p pass 23 Passing ACE Options 24 PGRelFind 77 preferred definition 18 19 preferred definition stack 18 19 21 Primitive ACE Read Write Functions 61 Progress Messages 65 Q Query Options 99 R R C
58. output at all it waits for a complete line ACEReadAll 7 F ACEReadA11 F read and return as many complete lines of ACE output from the ith or default interactive ACE process as there are to be read at the time of the call as a list of strings with the trailing newlines removed and returns the empty list otherwise ACEReadA11 also writes each line read via Info at InfoACE level 3 Whenever ACEReadA11 finds only a partial line it waits for the complete line thus increasing the probability that it has captured all the output to be had from ACE ACEReadUntil i IsMyLine ACEReadUntil IsMyLine ACEReadUntil i IsMyLine Modify ACEReadUntil IsMyLine Modify gs ieo ies ies read complete lines of ACE output from the ith or default interactive ACE process chomps them i e re moves any trailing newline character emits them to Info at InfoACE level 3 and applies the function Modify where Modify is just the identity map function for the first two forms until a chomped line line for which IsMyLine Modify line is true ACEReadUntil returns the list of Modify ed chomped lines read Notes When provided by the user Modify should be a function that accepts a single string argument IsMyLine should be a function that is able to accept the output of Modify or take a single string argument when Modify is not provided and should return a boolean If IsMyLine Modify line is never true ACEReadUntil w
59. return the order modulo the subgroup of the coset with representative cosetrep a word in the free group generators Note ACECosetOrderFromRepresentative calls ACETraceWord to determine the coset number to which cosetrep belongs and then scans the output of ACEOrders to determine the order of the coset number 21 gt ACECosetsThatNormaliseSubgroup i n F gt ACECosetsThatNormaliseSubgroup n F for the ith or default interactive ACE process started by ACEStart determine non trivial i e other than coset 1 coset numbers whose representatives normalise the subgroup If n gt 0 the list of the first n non trivial coset numbers whose representatives normalise the subgroup is returned If n lt 0 a list of records with fields coset and rep which represent the coset number and a representa tive respectively of the first n non trivial coset numbers whose representatives normalise the subgroup is returned If n 0 a list of records with fields coset and rep which represent the coset number and a repre sentative respectively of all non trivial coset numbers whose representatives normalise the subgroup is returned Note You may wish to compact ACE s coset table first either explicitly via ACERecover see 6 7 1 or implicitly via any function call that invokes ACE s compaction routine see 6 7 1 note 22 gt 23 gt vvvy 24 gt 25 gt 56 Chapter 6 Functions for Using ACE Interactively
60. subgroup when they act by conjugation Also the option normal see D 5 4 already performs a different function INTERACTIVELY use ACECosetsThatNormaliseSubgroup see 6 5 21 statistics stats Dump enumeration statistics Shortest abbreviation of statistics is stat If the statistics package is compiled into the ACE code which it is by default see the options D 5 5 option then this option dumps the statistics accumulated during the most recent enumeration See the enum c source file for the meaning of the variables INTERACTIVELY use ACEDumpStatistics see 6 5 24 11 gt 12 gt Q2 gt 102 Appendiz D Other ACE Options style Prints the current enumeration style This option prints the current enumeration style as deduced from the current ct and rt parameters see 3 1 INTERACTIVELY use ACEStyle see 6 5 22 tw val word trace val word Trace word through the coset table starting at coset val val must be a positive integer and word must be a word in the group generators This option prints the final coset number of the trace if the trace completes INTERACTIVELY use ACETraceWord see 6 5 17 D 6 Options that Modify the Coset Table recover contiguous Recover space used by dead coset numbers Shortest abbreviation of recover is reco and shortest abbreviation of contiguous is contig This option invokes the compaction routine on the table to recover the space used by any dead coset
61. supplied options unless the user herself supplies one of the enumeration invoking options which are start or one of its synonyms aep see D 1 1 or rep see D 1 2 The fields of the ACEStats record are determined by parsing a results message see Appendix A from ACE ACEStats may also be called in a different way in an interactive ACE session see 6 6 2 1 4 Writing ACE Standalone Input Files to Generate a Coset Table If you want to use ACE as a standalone with its own syntax you can write an ACE standalone input file by calling ACECosetTable with three arguments see 1 2 1 and the option aceinfile filename see 4 11 7 This will keep the input file for the ACE standalone produced by the GAP interface under the file name filename and just return so that you can perform interactive work in the standalone 1 5 Using ACE Interactively An interactive ACE process is initiated with the command ACEStart fgens rels sgens options F whose arguments and options are exactly as for ACECosetTableFromGensAndRels and ACEStats as dis cussed in Sections 1 2 and 1 3 The usual warnings regarding options apply see Section 1 7 ACEStart has a number of other forms see 6 1 1 The return value is an integer numbering from 1 which represents the running process It is possible to have more than one interactive process running at once The integer returned may be used to index which of these processes an interactive ACE functio
62. table any existing information in the table is retained and the enumeration is restarted from coset 1 i e the subgroup Notes This option is really intended for the case where additional relators option rl see D 2 5 and or subgroup generators option sg see D 2 4 have been introduced The current table which may be incomplete or exhibit a finite index is still valid However the additional data may allow the enumeration to complete or cause a collapse to a smaller index INTERACTIVELY use ACERedo see 6 2 3 continu Continues the current enumeration building upon the existing table Shortest abbreviation cont If a previous run stopped without producing a finite index you can in principle change any of the parameters and continue on Of course if you make any changes which invalidate the current table you won t be allowed to continue although you may be allowed to redo see D 3 3 If redo is not allowed you must re start see D 3 2 Note The ACE standalone allows the option continue but this is as of GAP 4 3 a GAP keyword and so GAP users must use mixed case abbreviations of continu INTERACTIVELY use ACEContinue see 6 2 2 3 Section 5 Query Options 99 D 4 Options that Interact with the Operating System ai ai filename Alter input to standard input or filename filename must be a string By default commands to ACE are read from standard input i e the keyboard With no value ai causes
63. that the group s relators are left unchanged by running the aep option not that a non interactive user cares As discussed by Cannon Dimino Havas and Watson CDHW73 and Havas and Ramsay HRO1 such equiv alent presentations can yield large variations in the number of coset numbers required in an enumeration For this command we are interested in this variation After the final presentation is run some additional status information messages are printed to the ACE output file the number of runs which yielded a finite index Q2 gt Section 1 Experimentation Options 95 the total number of runs excluding the priming run and the range of values observed for m and t As an example drawn from the discussion in HR99 consider the enumeration of the 448 coset numbers of the subgroup a a b of the group 8 7 2 3 a b a b ab a d 1 There are 4 24 relator orderings and 2 16 combinations of relator or inverted relator Exponents are taken into account when rotating relators so the relators given give rise to 1 1 2 and 2 rotations respectively for a total of 1 1 2 2 4 combinations So for aep 7 resp 3 24 16 4 1536 resp 16 4 64 equivalent presentations are tested Notes There is no way to stop the aep option before it has completed other than killing the task So do a reality check beforehand on the size of the search space and the time for each enumeration I
64. the integer range 0 to 4 Shortest abbreviation look Although HLT style strategies are fast they are local in the sense that the implications of any defini tions deductions made while applying coset numbers may not become apparent until much later One way to alleviate this problem is to perform lookaheads occasionally that is to test the information in the table looking for deductions or concidences ACE can perform a lookahead when the table overflows before the compaction routine is called Lookahead can be done using the entire table or only that part of the table above the current coset number and it can be done R style scanning coset numbers from the beginning of relators or C style testing all definitions in all essentially different positions The following are the effects of the possible values of lookahead 0 disables lookahead 1 does a partial table lookahead R style 2 does a whole table lookahead C style 3 does a whole table lookahead R style and 4 does a partial table lookahead C style The default is 1 if the hlt strategy is used and 0 otherwise see Chapter 5 Section 3 1 describes the various enumeration styles and in particular R style and C style 36 Chapter 4 Options for ACE 4 16 ACE Parameter Options for Deduction Handling dmode val Deduction mode val should be in the integer range 0 to 4 Shortest abbreviation dmod A completed table is only valid if every table ent
65. the recovery of dead coset numbers that could be done was done earlier Section 1 Getting Started 91 gap gt ACEStandardCosetNumbering I co ST a 12 r 13 h 1 n 13 c 0 00 gap gt ACEDisplayCosetTable 12 I co a 12 r 13 h 1 n 13 c 0 00 1 coset b B a order rep ve I fa SSS SSS sas Sa Se aS SSS SS SS a Ses 1 1 2 3 3 1 2 3 1 4 3 b I 3 1 2 1 3 B I 4 5 6 2 5 ba 1 5 6 4 7 5 bab I 6 4 5 8 2 baB 1 7 8 9 5 5 baba I 8 9 7 6 5 baBa 1 9 7 8 10 3 babaB 1 10 11 12 9 3 babaBa I 11 12 10 12 3 babaBab I 12 10 11 11 2 babaBaB HL eA ae ea Of course the table above is not lenlex with respect to the order of the generators we had originally given to ACE to get that we would have needed to specify lenlex see 4 11 4 at the enumeration stage The effect of the lenlex option at the enumeration stage is the following behind the scenes it ensures that the relator a 2 is passed to ACE as aa and then it sets the option asis to 1 this bit of skulduggery stops ACE treating a as an involution allowing a and A the inverse of a to take up the first two columns of the coset table effectively stopping ACE from reordering the generators To see what is passed to ACE at the enumeration stage we set the InfoACELevel to 4 but since we don t really want to see messages this time we set messages 0 gap gt SetInfoACELevel 4 gap gt ACEStart 1 ACEGroupGenerators 1 ACERelators
66. use ACEOrders see 6 5 18 for the case val 0 or ACEOrder see 6 5 19 otherwise sr sr val Print out parameters of the current presentation val must be an integer in the range 0 to 5 vvvvy 10 gt Section 5 Query Options 101 No argument or val 0 prints out the Group Name the group s relators Subgroup Name and the sub group s generators If val 1 then the Group Generators and the current setting of the run parame ters is also printed The printout is the same as that produced at the start of a run when option messages see 4 18 1 is non zero Also val equal to 2 3 4 or 5 print out just the Group Name just the group s relators just the Subgroup Name or just the subgroup s generators respectively Notes The sr option should only be used after an enumeration run otherwise the value 0 for some options will be unreliable To ensure this occurs non interactively ensure one of the options that invokes an enumeration start see D 3 2 or aep see D 1 1 or rep see D 1 2 precedes the sr option When an enumeration invoking option is included non interactively the quiet inclusion step of the start option is omitted INTERACTIVELY use ACEGroupGenerators see 6 5 1 ACERelators see 6 5 2 ACESubgroupGener ators see 6 5 3 and ACEParameters see 6 5 10 print print val print val print val last print val last by Compact and print the coset table val must be an integer
67. value style name 0 gt 0 0 lt 0 gt 0 Cr gt 0 gt 0 CR gt 0 0 R lt 0 0 R gt 0 lt 0 Rc lt 0 lt 0 R C 0 0 R C defaulted C style In this style most definitions are made in the next empty coset table slot and are in principle tested in all essentially different positions in the relators i e this is a Felsch like style 20 Chapter 8 Some Basics However in C style some definitions may be made following a preferred definition strategy controlled by the pmode and psize options see 4 14 2 and 4 14 3 Cr style is like C style except that a single R style pass is done after the initial C style pass CR style In this style alternate passes of C style and R style are performed R style In this style all the definitions are made via relator scans i e this is an HLT like style R style makes definitions the same as R style but tests all definitions as for C style Rc style is like R style except that a single C style pass is done after the initial R style pass R C style In this style we run in R style until an overflow perform a lookahead on the entire table and then switch to CR style Defaulted R C R C defaulted style is the default style used if you call ACE without specifying options In it we use R C style with ct set to 1000 and rt set to approximately 2000 divided by the total length of the relators in an attempt to balance R style and C style definitions when we switch to CR style
68. 0 which gives an output record that is immediately GAP usable With the above in mind let s rerun the enumeration and get ACE s dump of the presentation and parameters gap gt SetInfoACELevel 3 gap gt ACEStats fgens start sr 1 I ACE 3 001 Wed Oct 31 09 36 39 2001 H I ssssssssssssssss SSS sSSSSSSSSSSSSSSSSS55 I Host information 1 name rigel I OVERFLOW a 249998 r 83333 h 83333 n 249999 1 337 c 0 09 m 249998 t 2499 98 1 ACE 3 001 Run Parameters I Group Name G I Group Generators ab I Group Relators I Subgroup Name H I Subgroup Generators I Wo 1000000 Max 249998 Mess 0 Ti 1 Ho 1 Loop 0 I As 0 Path 0 Row 1 Mend 0 No 0 Look 0 Com 10 I C 0 R 0 Fi 7 PMod 3 PSiz 256 DMod 4 DSiz 1000 1 f rec index 0 cputime 9 cputimeUnits 10 2 seconds activecosets 249998 maxcosets 249998 totcosets 249998 Observe that at InfoACE level 3 one also gets ACE s banner We could have printed out the first few lines of the coset table if we had wished using the print see D 5 8 option but note as with the sr option an enumeration should precede it Here s what happens if you disregard this recall we still have the InfoACE level set to 3 gap gt ACEStats fgens print 1 12 I ACE 3 001 Wed Oct 31 09 37 37 2001 H I ssssssssssssssssSsSSsSSSSSSSSSSSSSSSSS55 I Host information 1 name rigel I E
69. 1 12 0 0 O 0 3 0 0 0 3 1 9 0 0 2 0 0 0 0 0 4 4 7 10 0 1 0 0 2 0 0 3 0 5 8 11 1 0 O 2 O O 3 0 0 Observe the line beginning I start yes the first line in the output of ACECosetTable This line appears in response to the option mode see D 3 1 inserted by ACECosetTable after any user options it is inserted in order to check that no user options possibly made before the ACECosetTable call have invali dated ACE s coset table Since the line also says continue yes the mode continue the least expensive of the three modes see D 3 4 is directed at ACE which evokes a results message Then ACECosetTable extracts the incomplete table via a print see D 5 8 directive If you wish to see all the options that are directed to ACE set the InfoACE level to 4 then all such commands are Info ed behind a ToACE gt prompt see 1 9 3 Following the standalone manual we now set things up to do the alternating group As of order 60 We saw the group As with subgroup Cs earlier in Section B 3 here we are concerned with observing and remarking on the output from the ACE binary We turn messaging on via the messages see 4 18 1 option setting messages to 1 tells ACE to emit a progress message on each pass of its main loop In the example following we set messages 1000 which for our example sets the interval between messages so high that we only get the Run Parameters block
70. 18 20 21 23 coincidence queue 18 cosets 18 coset application 18 coset numbers 18 coset table 18 Coset Statistics Terminology 23 Coset Table Standardisation Schemes 21 CR style 20 42 Cr style 20 42 C style 19 42 definition 19 34 D dead coset number 20 23 37 38 57 102 debugging 27 deduction 18 20 deduction stack 18 Defaulted R C style 20 42 definition 20 preferred 18 DisplayACEArgs 52 DisplayACEOptions 52 E Emulating Sims 92 Enumeration Style 19 Index Example of Using ACECosetTableFromGensAn dRels 68 Example of Using ACE Interactively Using ACEStart 69 Example where ACE is made the Standard Coset Enumerator 66 Experimentation ACE Modes 49 Experimentation Options 94 F Felsch strategy 18 Finding Deductions Coincidences and Preferred Definitions 20 Finding Subgroups 21 FlushOptionsStack 25 Fun with ACEExample 70 G General ACE Modes 46 General ACE Parameter Options that Modify the Enumeration Process 33 General Warnings regarding the Use of Options 12 GetACEArgs 52 GetACEOptions 52 Getting Started 79 H HLT strategy 18 holes 18 Honouring of the order in which ACE Options are passed 26 InfoACE 14 InfoACELevel 14 Installing the ACE Package 16 Interactive ACE Process Utility Functions and Interruption of an Interactive ACE Process 47 Interactive Query Functions and an Option Setting Function 51 Interactive Versions
71. 2 i e it is superfluous if ACEIgnoreUnknownDefault true unless aceignoreunknown is set to false acenowarnings Inhibits the warning message unknown maybe new or bad option for options not listed in KnownACEOptions Shortest abbreviation acenow This option suppresses the warning messages for unknown options to the ACE interface but unlike aceignore and aceignoreunknown still allows them to be passed to the ACE binary echo echo 2 Echoes arguments and options and indicates how options were handled Unlike the previous options of this section there is an ACE binary option echo However the echo option is handled by the ACE interface and is not passed to the ACE binary If you wish to put echo in a standalone script use the aceecho option following If echo is passed with the value 2 then a list of the options together with their values that are set via ACE defaults are also echoed to the screen aceecho The ACE binary s echo command This option is only included so that a user can put an echo statement in an ACE standalone script Otherwise use echo above aceincomment string Print comment string in the ACE input string must be a string Shortest abbreviation aceinc This option prints the comment string behind a sharp sign in the input to ACE Only useful for adding comments that ACE ignores to standalone input files aceexampleoptions An internal option for ACEExample This option
72. 3 6 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 4 13 4 14 4 15 4 16 Contents Finding Subgroups Coset Table Standardisation Schemes Coset Statistics Terminology Other Terminology Options for ACE Passing ACE Options Warnings regarding Options Abbreviations and mixed case for ACE Options Honouring of the order in which ACE Options are passed What happens if no ACE Strategy Option or if no ACE Option is passed Interpretation of ACE Options An Example of passing Options The KnownACEOptions Record The ACEStrategyOptions List ACE Option Synonyms Non ACE binary Options ACE Parameter Options General ACE Parameter Options that Modify the Enumeration Process ACE Parameter Options eae C Style Definitions ACE Parameter Options for R Style Definitions ACE Parameter Options for Deduction Handling 21 21 23 23 24 24 25 25 26 26 26 28 28 29 29 30 32 33 34 35 36 Contents 4 17 4 18 4 19 4 20 4 21 5 5 1 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 A l A 2 B 1 B 2 B 3 B 4 Technical ACE Parameter Options ACE Parameter Options controlling ACE Output ACE Parameter Options that give Names to the Group and Subgroup Options for redirection of ACE Output Other Options Strategy Options for ACE The Strategies in Detail Functions for Using ACE Interactively Starting and Stopping Interactive ACE Processes
73. 4 some of which may over ride those options set by the strategy option Please refer to the introductory sections of Chapter 4 paying particular attention to Sections 4 2 4 5 and 4 6 which give various warnings hints and information on the interpretation of options There are eight strategy options Each is passed without a value see Section 4 6 except for sims which expects one of the integer values 1 3 5 7 or 9 and felsch can accept a value of 0 or 1 where 0 has the same effect as passing felsch with no value Thus the eight strategy options define thirteen standard strategies these are listed in the table below along with all but three of the options of Chapter 4 that they set Additionally each strategy sets path 0 psize 256 and dsize 1000 Recall mend look and com abbreviate mendelsohn see 4 13 5 lookahead see 4 15 2 and compaction see 4 17 5 respectively option strategy row mend no look com ct rt fill pmode dmode default 1 oO 1 0 10 0 0 0 3 4 easy 1 o 60 O 100 0 1000 1 0 0 felsch 0 0 o o 0 10 1000 0 1 0 4 felsch 1 0 0 1 0 10 1000 0 0 3 4 hard 1 QO i 0 10 1000 1 0 3 4 hlt 1 o 0 1 10 0 1000 1 0 0 purec 0 o o O 100 1000 0 1 0 4 purer 0 o 0 O 100 0 1000 1 0 0 sims 1 1 o 0 0 10 0 1000 1 0 0 sims 3 1 o 0 0 10 O 1000 1 0 4 sims 5 1 1 0 0 10 0 1000 1 0 0 sims 7 1 1 0 0 10 O 1000 1 0 4 sims 9 0 o o 0 10 1000 0 1 0 4 1 gt Q2 gt 4 gt 42 Chapter 5 Strategy Options for ACE
74. 4 12 1 in vogue for the ACE process use ACEParameters see 6 5 10 GetACEOptions i F GetACEOptions F return a record of the current options those that have been explicitly set by the user of the ith or default process started by ACEStart Please note that no value ACE options will appear with the assigned value true see Section 4 6 for how the ACE interface functions interpret such options The notes applying to DisplayACEOptions see 6 5 6 also apply here SetACEOptions i options F SetACEOptions options F modify the current options of the ith or default process started by ACEStart Please ensure that the OptionsStack is empty before calling SetACEOptions otherwise the options already present on the Op tionsStack will also be seen All interactive ACE interface functions that accept options actually call an internal version of SetACEOptions so it is generally important to keep the OptionsStack clear while working with ACE interactively After setting the options passed the first mode of the following ACECont inue see 6 2 2 ACERedo see 6 2 3 or ACEStart see 6 1 1 that may be applied is automatically invoked Since a user will sometimes have options in the form of a record e g via GetACEOptions we provide a PushOptions like alternative to the behind the colon syntax for the passing of options via SetACEOptions SetACEOptions i optionsRec F SetACEOptions optionsRec F In this form
75. 4 4 this is done by calling gap gt LoadPackage ace Loading ACE Advanced Coset Enumerator 5 1 GAP code by Greg Gamble lt Greg Gamble uwa edu au gt address for correspondence Alexander Hulpke http www math colostate edu hulpke uses ACE binary C code program version 3 001 C code by George Havas http www itee uq edu au havas Colin Ramsay http www itee uq edu au cram For help type ACE In version 4 1 of the ACE package there was an option pkgbanner that allowed the user some control on how the banner above was displayed This only worked with GAP 4 3 Since the ACE package now requires at least GAP 4 4 this option has been removed If you still have GAP 4 3 you will need to use ACE 4 1 The banner may be suppressed by providing the version string 5 1 as second argument and false as third argument to the LoadPackage command The LoadPackage command is described in Section 74 2 1 in the GAP Reference Manual If GAP cannot find a working binary the call to LoadPackage will fail If you want to load the ACE package by default you can put the LoadPackage command into your gaprc file see Section 3 4 in the GAP Reference Manual Some Basics Throughout this manual for the use of ACE as a GAP package we shall assume that the reader already knows the basic ideas of coset enumeration as can be found for example in Neu82 There a simple proof is given for the fact that a coset enumeration for a subgroup o
76. 5 gt Section 17 Technical ACE Parameter Options 37 time val Maximum execution time in seconds val must be an integer greater than or equal to 1 Shortest abbreviation ti The time command puts a time limit in seconds on the length of a run The default is 1 which is no time limit If the argument is gt 0 then the total elapsed time for this call is checked at the end of each pass through the enumerator s main loop and if it s more than the limit the run is stopped and the current table returned Note that a limit of 0 performs exactly one pass through the main loop since 0 gt 0 The time limit is approximate in the sense that the enumerator may run for a longer but never a shorter time So if there is e g a big collapse so that the time round the loop becomes very long then the run may run over the limit by a large amount Notes The time limit is CPU time not wall time As in all timing under UNIX the clock s granularity usually 10 milliseconds and the system load can affect the timing so the number of main loop iterations in a given time may vary loop val Loop limit val should be a non negative integer The core enumerator is organised as a state machine with each step performing an action i e lookahead compaction or a block of actions i e ct coset number definitions rt coset number applications The number of passes through the main loop i e steps is counted and the
77. ACE A GAP4 Package Version 5 1 Based on ACE Standalone Version 3 001 by George Havas and Colin Ramsay Centre for Discrete Mathematics and Computing Department of Information Technology and Electrical Engineering The University of Queensland St Lucia 4072 Australia GAP interface code by Alexander Hulpke Department of Mathematics Colorado State University Weber Building Fort Collins CO 80523 USA and Greg Gamble Department of Mathematics and Statistics Curtin University GPO Box U 1987 Perth WA 6845 Australia email Greg Gamble uwa edu au January 2012 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 2 1 2 2 3 1 3 2 The ACE Package Using ACE as a Default for Coset Enumerations Using ACE Directly to Generate a Coset Table a er LESS Using ACE Directly to Test whether a Coset Enumeration Terminates Writing ACE Standalone Input Files to Generate a Coset Table Using ACE Interactively Accessing ACE Examples with ACEExample and ACEReadResearchExample General toe eae the Use of Options The ACEData Record Setting the Verbosity of ACE via Info and InfoACE Acknowledgements Changes from earlier versions Installing and Loading the ACE Package Installing the ACE Package Loading the ACE Package Some Basics Enumeration Style Finding Deductions Coincidences and Preferred Definitions 10 10 11 12 13 14 15 15 16 16 17 18 19 20 3 3 3 4 3 5
78. ACE binary does not provide semilenlex standardisation and hence ACEDisplayCosetTable will never display a semilenlex standard coset table ACECosetRepresentative i n F ACECosetRepresentative n F return for the ith or default process started by ACEStart the coset representative of coset n of the current coset table held by ACE where n must be a positive integer ACECosetRepresentatives i F ACECosetRepresentatives F return for the ith or default process started by ACEStart the list of coset representatives of the current coset table held by ACE ACETransversal i F ACETransversal F return for the ith or default process started by ACEStart the list of coset representatives of the current coset table held by ACE if the current table is complete and fail otherwise Essentially ACETransversal i ACECosetRepresentatives i for a complete table ACECycles i ACECycles ACEPermutationRepresentation i ACEPermutationRepresentation ag a return for the ith or default process started by ACEStart a list of permutations corresponding to the group generators i e the permutation representation if the current coset table held by ACE is complete or fail otherwise In the event of failure a message is emitted to Info at InfoACE or InfoWarning level 1 ACETraceWord i n word F ACETraceWord n word F for the ith or default interactive ACE process started by ACEStart trace word throu
79. ACE courtesy of the non zero value of the messages option and we see these because we first set the InfoLevel of InfoACE to 3 and finally we get the output record of the ACEStats command Observe also that ACE uses the same generators as are input this will always occur if you stick to single lowercase letters for your generator names Note also that capitalisation is used by ACE as a short hand for inverses e g C c 1 see Group Relators in the ACE Run Parameters block gap gt SetInfoACELevel 3 gap gt ACEExample F27 purec I ACEExample F27 purec enumeration of cosets of H in G I where G F 2 7 C_29 H Id using purec strategy I I F G a b c d e x y are local to ACEExample I We define F 2 7 on 7 generators 1 F FreeGroup a pH Wo qt el yt y I a F 1 b F 2 c F 3 d F 4 I e F 5 x F 6 y F 7 I G F a b c 1 b c d 1 cxd xe 1 d e x 1 I e xx y 1 x y a 1 y xa b 1 I ACEStats I FreeGenerators0fFpGroup G I Relators0fFpGroup G I Generators of identity subgroup empty list I Options that don t affect the enumeration I echo enum F 2 7 aka C_29 subg Id I Other options I wo 2M mess 25000 purec ACEStats called with the following arguments Group generators a b c d e x y Group relators a b c 1 b c d 1 c d e 1 d e x 1 e x y 1 x y xa 1 y a
80. ACE to revert to reading from standard input otherwise the ai command closes the current input file and opens filename as the source of commands If filename can t be opened input reverts to standard input Notes If you switch to taking input from another file remember to switch back before the end of that file otherwise the EOF there will cause ACE to terminate bye exit qui Quit ACE Shortest abbreviation of qui is q This quits ACE nicely printing the date and the time An EOF end of file i e d has the same effect so proper termination occurs if ACE is taking its input from a script file Note that qui actually abbreviates the corresponding ACE directive quit but since quit is a GAP keyword it is not available via the GAP interface to ACE INTERACTIVELY use ACEQuit see 6 1 2 system string Does a shell escape to execute string string must be a string Shortest abbreviation sys Since GAP already provides Exec for this purpose this option is unlikely to have a use D 5 Query Options cycles Prints out the table in cycles Shortest abbreviation cy This option prints out the permutation representation INTERACTIVELY use ACECycles see 6 5 16 dump dump level dump level dump level detail Dump the internal variables of ACE level must be an integer in the range 0 to 2 and detail must be 0 or 1 Shortest abbreviation d The value of level determines which of the three leve
81. ACEStart is possible and an internal version of the first mode of these that is allowed is executed to ensure the resultant statistics are correct for the current options See Section B 3 for an example demonstrating both these functions within an interactive process IsACEGeneratorsInPreferredOrder i F IsACEGeneratorsInPreferredOrder F for the ith or default interactive ACE process started by ACEStart return true if the group generators of that process are in an order that will not be changed by ACE and false otherwise This function has greatest relevance to users who call ACECosetTable see 6 6 1 with the lenlex option see 4 11 4 For more details see the discussion for the non interactive version of IsACEGeneratorsInPreferredOrder 1 2 3 which is called with two arguments 6 7 Steering ACE Interactively ACERecover i F ACERecover F invoke the compaction routine on the coset table of the ith or default interactive ACE process started by ACEStart in order to recover the space used by the dead coset numbers A CO message line is printed if any rows of the coset table were recovered and a co line if none were See Appendix A for the meanings of these messages Note The compaction routine is called automatically when any of ACEDisplayCosetTable see 6 5 12 ACE CosetRepresentative see 6 5 13 ACECosetRepresentatives see 6 5 14 ACETransversal see 6 5 15 ACECycles see 6 5 16 ACEStandardCosetNumbering
82. CE binary except that the options purer and purec are first translated to pure r and pure c respectively When the ACE binary encounters an option that it doesn t understand it issues a warning and simply ignores it so options accidentally passed to ACE are unlikely to pose problems We also mention here since it is related to an option of this section the following ACEI gnoreUnknownDefault V is a global variable not an option that is initially set by the ACE package to true and is the default action that ACE takes for options that are unknown to the ACE package but may be new options provided in a new version of the ACE binary Despite the fact that it is normally set true it is recommended especially for the novice user of the ACE package to set ACEIgnoreUnknownDefault false the worst that can happen is being annoyed by a profusion of warnings of unknown options For individual functions the user may use the option aceignoreunknown see 4 11 10 to over ride the setting of ACEIgnoreUnknownDefault Here now are the few options that are available to the GAP interface to ACE that have no counterpart in the ACE standalone silent Inhibits an Error return when generating a coset table If a coset enumeration that invokes ACECosetTableFromGensAndRels does not finish within the preset lim its an error is raised by the interface to GAP unless the option silent or incomplete see 4 11 6 has been set in the former case fail
83. CEGeneratorsInPreferredOrder gens rels F returns true if gens a list of free group generators are in an order which will not be changed by ACE for the group with presentation gens rels where rels is a list of relators i e words in the generators gens IsACEGeneratorsInPreferredOrder may also be called in a different way for interactive ACE processes see 6 6 3 For a presentation with more than one generator the first generator of which is an involution and the second is not ACE prefers to switch the first two generators IsACEGeneratorsInPreferredOrder returns true if the order of the generators gens would not be changed within ACE and false otherwise Technically by involution above we really mean a generator x for which there is a relator in rels of form x x or x72 Such a generator may of course turn out to actually be the identity Guru Notes If IsACEGeneratorsInPreferredOrder gens rels would return false it is possible to enforce a user s order of the generators within ACE by setting the option asis see 4 13 1 to 1 and by passing the relator that determines that gens 1 which we will assume is x has order at most 2 as x x rather than x 2 Behind the scenes this is precisely what is done if necessary when ACECosetTable is called with the lenlex option The user may avoid all the technicalities by either not using the lenlex option and allowing GAP to take care of the lenlex standardisation o
84. CEStart command an ACE binary process in the UNIX sense is started up a GAP iostream is assigned to communicate with the ACE binary process and the essential defining data associated with the interactive ACE process is saved in ACEData iol i see 1 8 1 for precisely what is saved ACEQuit i F ACEQuit F terminate an interactive ACE process where 7 is the integer returned by ACEStart when the process was started If the second form is used i e without arguments then the interactive process of least index that is still running is terminated Note ACEQuit i terminates the ACE binary process of interactive ACE process i and closes its GAP iostream and unbinds the record ACEData io see 6 1 1 note It can happen that the ACE binary process and hence the GAP iostream assigned to communicate with it can die e g by the user typing a Ctrl C while the ACE binary process is engaged in a long calculation IsACEProcessAlive see 6 3 3 is provided to check the status of the GAP iostream and hence the status of the ACE binary process it was communicating with in the case that it is indeed dead ACEResurrect Process see 6 3 4 may be used to start a new ACE binary process and assign a new GAP iostream to communicate with it by using the defining data of the interactive ACE process saved in ACEData io i ACEQuitAl1 F is provided as a convenience to terminate all active interactive ACE processes wit
85. CEStart initialisation steps that is sketched in the schema below For the following code it is imagined the scenario is one of looping over several possibilities of fgens rels and sgens the two special forms of ACEStart used allow one to continually re use a single interactive ACE process i e only one iostream is used start the interactive ACE process with no group information procld ACEStart 0 while expr do fgens rels sgens ACEStart procId fgens rels sgens options if ACEStats procId index gt 0 then table ACECosetTable procId fi od For an already calculated coset table we provide the following function to determine whether or not it has been standardised Q2 gt 3 1 gt Section 3 Using ACE Directly to Test whether a Coset Enumeration Terminates 9 IsACEStandardCosetTable table option F returns true if table a list of lists of integers is standard according to GAP s default or the option either lenlex or semilenlex standardisation scheme or false otherwise See Section 3 4 for a detailed discussion of the lenlex and semilenlex standardisation schemes Note Essentially IsACEStandardCosetTable extends the GAP function IsStandardized Users who wish their coset tables to use ACECosetTable with the lenlex see 4 11 4 option which causes lenlex standardisation to occur at the ACE rather than GAP level should be aquainted with the following function IsA
86. CEStats takes 1 or no arg ts rec index 0 cputime 10 cputimeUnits 10 2 seconds activecosets 249998 maxcosets 249998 totcosets 249998 To display 12 lines of the coset table with coset representatives without invoking a further enumeration we could do ACEStart 0 1 print 1 12 Alternatively we may use the ACEDisplayCosetTable see 6 5 12 the table itself is emitted at InfoACE level 1 since by default we presumably want to see it Section 1 Getting Started 85 gap gt ACEDisplayCosetTable 1 1 12 I co a 249998 r 83333 h 83333 n 249999 c 0 00 1 coset a A b B order rep ve HI PSS SSS SRS aS eas SS a SS aS SS a 5S 1 1 2 3 4 5 1 2 6 1 7 8 O a 1 3 1 9 10 11 Oo A I 4 12 13 14 1 O b I 5 15 16 1 17 Oo B 1 6 18 2 19 20 QO aa 1 7 21 22 23 2 QO ab 1 8 24 25 2 26 Oo aB I 9 3 27 28 29 O AA I 10 30 31 32 3 O Ab 1 11 33 34 3 35 O AB 1 12 36 4 37 38 O ba Hl edeten rora Still with the same interactive ACE process we can now emulate the ACECosetTableFromGensAndRels ex change that gave us an incomplete coset table Note that it is still necessary to invoke an enumeration after setting the max see 4 17 6 option We could just call ACECosetTable with the argument 1 and the same 4 options we used for ACECosetTableFromGensAndRels Alternatively we can do the equivalent of the 4 options one or two at a time via their equivalent interactive
87. RROR continuing with next line 1 no information in table I Section 1 Getting Started 81 I I OVERFLOW a 249998 r 83333 h 83333 n 249999 1 337 c 0 09 m 249998 t 2499 98 rec index 0 cputime 9 cputimeUnits 10 2 seconds activecosets 249998 maxcosets 249998 totcosets 249998 Essentially because ACE had not done an enumeration prior to getting the print directive it complained with an ERROR recovered and went on with the start directive automatically inserted by the ACEStats command no ill effects at the GAP level but also no table Now let s do what we should have done to get those first few lines of the coset table namely insert the start option before the print option the InfoACE level is still 3 gap gt ACEStats fgens start print 1 12 I ACE 3 001 Wed Oct 31 09 38 28 2001 H I SsssssssssssSSSsSSSSSSSSSSSSSSSSSSS555555 I Host information 1 name rigel I OVERFLOW a 249998 r 83333 h 83333 n 249999 1 337 c 0 10 m 249998 t 2499 98 I co a 249998 r 83333 h 83333 n 249999 c 0 00 1 coset a A b B order rep ve HI a a a 1 1 2 3 4 5 1 2 6 1 T 8 0 a I 3 1 9 10 11 0 A I 4 12 13 14 1 0 b I 5 15 16 1 17 0 B I 6 18 2 19 20 0 aa I 7 21 22 23 2 0 ab I 8 24 25 2 26 0 aB I 9 3 27 28 29 0 AA 1 10 30 31 32 3 0 Ab I 11 33 34 3 35 0 AB I 12 36 4 37 38 0 ba I rec
88. already be complete use ACERandomCoinci dences see 6 7 8 if your table is not already complete ACERandomlyApplyCosetCoincidence provides the following four options controlOptions subindex subindex Sets the restriction that the final index should be a multiple of subindex subindex must be a positive integer divisor of the initial subgroup index hibound hibound Sets the restriction that the final index should be strictly less than hibound hibound must be an integer that is greater than 1 and at most the initial subgroup index lobound lobound Sets the restriction that the final index should be strictly greater than lobound lobound must be an integer that is at least 1 and strictly less than the initial subgroup index attempts attempts Sets the restriction that the number of applications of ACECosetCoincidence should be at most attempts attempts must be a positive integer By default subindex 1 hibound is the existing subgroup index lobound 1 and attempts 8 If after an attempt the new index is a multiple of subindezx less than hibound and greater than lobound then the process terminates and the list of new subgroup generators is returned Otherwise if an attempt reaches a stage where the criteria cannot be satisfied the attempt is aborted the original subgroup generators restored and another attempt made If no attempt is successful an empty list is returned Use ACESubgroupGenerators see 6 5 3 to
89. ange 0 to 100 Shortest abbreviation com The option compaction sets the percentage of dead coset numbers needed to trigger compaction of the coset table during an enumeration A dead coset number is a coset number found to be coincident with a smaller coset number The default is 10 or 100 depending on the strategy used see Chapter 5 Compaction recovers the space allocated to coset numbers which are flagged as dead It results in a table where all the active coset numbers are numbered contiguously from 1 and with the remainder of the table available for new coset numbers The coset table is compacted when a definition of a coset number is required there is no space for a new coset number available and provided that the given percentage of the coset table contains dead coset numbers 6 gt 7 38 Chapter 4 Options for ACE For example if compaction 20 then compaction will occur only if 20 or more of the coset numbers in the table are dead An argument of 100 means that compaction is never performed while an argument of 0 means always compact no matter how few dead coset numbers there are provided there is at least one of course Compaction may be performed multiple times during an enumeration and the table that results from an enumeration may or may not be compact depending on whether or not there have been any coincidences since the last compaction or from the start of the enumeration if there have been no compactio
90. at any stage and t the total number of coset numbers defined are tracked and each time the statistics are better than what we ve already seen the ACE binary emits a summary result line for the relators used See Appendix A for a discussion of the statistics m and t To observe these messages set the InfoLevel of InfoACE to 3 and it s recommended that you do this so that you get some idea of what the ACE binary is doing The order in which the equivalent presentations are generated and tested has no particular significance but note that the presentation as given after the initial priming run is the last presentation to be generated and tested so that the group s relators are left unchanged by running the ACEA11EquivPresentations command As discussed by Cannon Dimino Havas and Watson CDHW73 and Havas and Ramsay HR01 such equiv alent presentations can yield large variations in the number of coset numbers required in an enumeration For this command we are interested in this variation After the final presentation is run some additional status information messages are printed to the ACE output the number of runs which yielded a finite index the total number of runs excluding the priming run and the range of values observed for m and t As an example drawn from the discussion in HR99 consider the enumeration of the 448 coset numbers of the subgroup a a b of the group 8 7 2 3 a b a
91. bout any particular ACE option simply type option option where option is one of the options listed above without any quotes e g gap gt option echo will display the section in this manual that describes the echo option We begin this chapter with several sections discussing the nature of the options provided Please spend some time reading these sections To continue onto the next section on line using GAP s help browser type gap gt gt 4 1 Passing ACE Options Options are passed to the ACE interface functions in either of the two usual mechanisms provided by GAP namely options may be set globally using the function PushOptions see Chapter 8 in the GAP Reference Manual or 1 gt Section 3 Abbreviations and mixed case for ACE Options 25 options may be appended to the argument list of any function call separated by a colon from the argument list see 4 10 in the GAP Reference Manual in which case they are then passed on recursively to any subsequent inner function call which may in turn have options of their own In general if ACE is to be used interactively one should avoid using the global method of passing options In fact it is recommended that prior to calling ACEStart the OptionsStack be empty 4 2 Warnings regarding Options As mentioned above one can set options globally using the function PushOptions see Chapter 8 in the GAP Reference Manual however options pushed onto OptionsStack
92. cheme s appli cability to semigroups where generator inverses need not exist This scheme ensures that as one scans the columns corresponding to the group generators in user supplied order row by row one encounters new coset numbers in numeric order Observe that the representatives are ordered according to length and then the lexical ordering implied by defining x lt y lt a lt b with some words omitted due to their equivalence to words that precede them in the ordering Also observe that as one scans the body of the table row by row from left to right new coset numbers appear in numeric order without gaps 2 3 4 5 then 1 which we have implicitly already seen 6 7 etc 3 5 Coset Statistics Terminology There are three statistics involved in the counting of coset number definitions activecosets maxcosets and totcosets these are three of the fields of the record returned by ACEStats see Section 1 3 and they correspond to the a m and t statistics of an ACE results message see Appendix A As already described coset enumeration proceeds by defining coset numbers totcosets counts all such definitions made during an enumeration During the coset enumeration process coincidences usually occur resulting in the larger of each coincident pair becoming a dead coset number The statistic activecosets is the count of coset numbers left alive i e not dead at the end of an enumeration and maxcosets is the maximum number of al
93. cur see Section 3 3 which however may change the subgroup whose cosets are enumerated The key to performance of coset enumeration procedures is good selection of the next coset number to be defined Leech in Lee77 and Lee84 showed how a number of coset enumerations could be simplified by removing coset numbers needlessly defined by computer implementations Human enumerators intelligently choose which coset number should be defined next based on the value of each potential definition In particular definitions which close relator cycles or at least shorten gaps in cycles are favoured A definition which actually closes a relator cycle immediately yields twice as many table entries deductions as other definitions The value of the pmode option see 4 14 2 determines which definitions are preferred if the value of the pmode option is non zero depending on the pmode value gaps of length one found during relator C style i e Felsch like scans are either filled immediately subject to the value of 111 or noted in the preferred definition stack The preferred definition stack is implemented as a ring of size determined by the psize option see 4 14 3 However making preferred definitions carelessly can violate the conditions required for guaranteed termination of the coset enumeration procedure in the case of finite index To avoid such a violation ACE ensures a fraction of the coset table is filled before a preferred definition is made t
94. d the ACEStart see 6 1 1 function allows one to start up an ACE process and maintain a dialogue with it Moreover via the functions ACEStats and ACECosetTable on 1 or no arguments one is able to extract the same information that we could with the non interactive versions of these functions However we can also do a lot more Each ACE option that provides output that 84 Appendix C Finer Points with Examples can be used from within GAP has a corresponding interactive interface function that parses and translates that output into a form usable from within GAP Now we emulate our successful ACEStats exchanges above using interactive ACE interface functions We could do this with ACEStart 0 fgens start sr 1 where the O first argument tells ACEStart not to insert start after the options explicitly listed Alternatively we may do the following note that the InfoACE level is still 3 gap gt ACEStart fgens I ACE 3 001 Wed Oct 31 09 42 49 2001 H I ssssssssssssssssSssSsSSSSSSSSSSSSSSSSS55 I Host information 1 name rigel I I OVERFLOW a 249998 r 83333 h 83333 n 249999 1 337 c 0 10 m 249998 t 2499 98 1 gap gt ACEParameters 1 1 ACE 3 001 Run Parameters I Group Name G I Group Generators ab I Group Relators I Subgroup Name H I Subgroup Generators I Wo 1000000 Max 249998 Mess 0 Ti 1 Ho 1 Loop 0 I As 0 Path 0 Row 1 Mend 0 No 0 Look 0
95. d with the order in which the generators were first put to ACE We have used the term involution above what we really mean is a generator x for which there is a relator x x or x 2 Such a generator may of course turn out to actually be the identity The function IsACEGeneratorsInPreferredOrder see 1 2 3 detects cases when ACE would swap the first two generators Standardising the coset numbering within ACE does not affect the GAP coset table obtained via ACECoset Table see 1 2 1 If ACECosetTable is called without the lenlex option GAP s default standardisation is applied after conversion of ACE s output which undoes an ACE standardisation On the other hand if ACECosetTable is called with the lenlex option then after a check and special action if required the equivalent of a call to ACEStandardCosetNumbering is invoked irrespective of whether it has been done by the user beforehand The check that is done is a call to IsACEGeneratorsInPreferredOrder see 1 2 3 to ensure that ACE has not swapped the first two generators The special action taken when the call to IsACE GeneratorsInPreferredOrder returns false is the setting of the asis option see 4 13 1 to 1 and the resubmission of the relators to ACE taking care not to submit the relator that determines the first generator as an involution as that generator squared these two actions together avert ACE s swapping of the first two generators followed by the re starting of the
96. d with workspace set to 3300k The other ed examples enumerate overgroups of the group of order 2 of the 2p17 XXX examples It s recommended that you try these with second argument ACECosetTableFromGensAndRels so that you enter a break loop where you can experiment with modifying the options using SetACEOptions The example 2p18 feli can be made to succeed with hard mend workspace 10M why don t you see if you can do better There are no hints for the other two ed examples they are exercises for you to try Let s now restore the original value of OnBreak gap gt OnBreak Normal0nBreak Of course running ACEExample with ACEStart as second argument opens up far more flexibility Try it Have fun Play with as many options as you can B 5 Using ACEReadResearchExample Without an argument the function ACEReadResearchExample reads the file pgrelfind g in the res examples directory which defines GAP functions such as PGRe1Find that were used in CHHR02 to show that the group L3 5 has deficiency 0 The deficiency of a finite presentation X R of a finite group G is R X and the deficiency of the group G is the minimum of the deficiencies of all finite presentations of G Let us now invoke ACEReadResearchExample with no arguments gap gt ACEReadResearchExample I The following are now defined 1 I Functions 1 PGRelFind ClassesGenPairs TranslatePresentation 1 IsACEResExamp1e0K
97. defaulted style 20 42 R C style 20 42 Index R style 20 42 Re style 20 42 Results Messages 65 R style 20 42 definition 19 35 S semilenlex standardisation scheme 22 SetACEOptions 52 record version 52 SetInfoACELevel 14 Setting the Verbosity of ACE via Info and InfoACE 14 Starting and Stopping Interactive ACE Processes 44 state machine 23 Steering ACE Interactively 57 strategy 18 minimal gaps 19 T Technical ACE Parameter Options 36 The ACEData Record 13 The ACEStrategyOptions List 29 The KnownACEOptions Record 28 The Strategies in Detail 42 ToACEGroupGenerators 48 ToACEWords 48 totcosets 9 23 U Using ACE as a Default for Coset Enumerations 5 Using ACE Directly to Generate a Coset Table 6 Using ACE Directly to Test whether a Coset Enumeration Terminates 9 Using ACE Interactively 10 Using ACEReadResearchExample 77 W Warnings regarding Options 25 What happens if no ACE Strategy Option or if no ACE Option is passed 26 Writing ACE Standalone Input Files to Generate a Coset Table 10
98. determine the current subgroup generator list ACEConjugatesForSubgroupNormalClosure i ACEConjugatesForSubgroupNormalClosure ACEConjugatesForSubgroupNormalClosure i add ACEConjugatesForSubgroupNormalClosure add yy Ay Ay for the ith or default interactive ACE process started by ACEStart test each conjugate of a subgroup generator by a group generator for membership in the subgroup and return the possibly empty list of conjugates that were determined to not belong to the subgroup coset 1 and if called with the add option these conjugates are also added to the existing list of subgroup generators Notes A conjugate of a subgroup generator is tested for membership of the subgroup by checking whether it can be traced from coset 1 to coset 1 see ACETraceWord 6 5 17 For an incomplete coset table such a trace may not complete in which case ACEConjugatesForSubgroupNormalClosure may return an empty list even though the subgroup is not normally closed within the group The add option does not guarantee that the resultant subgroup is normally closed It is still possible that some conjugates of the newly added subgroup generators will not be elements of the subgroup Example To demonstrate the usage and features of ACEConjugatesForSubgroupNormalClosure let us consider an example where we know pretty well what to expect Let G be the group isomorphic to the symmetric group S6 with the presentation a b a 0 ab
99. ds as an ACE list of words ToACEWords may be used to provide suitable values for the options relators see D 2 2 generators see D 2 3 sg see D 2 4 and r1 see D 2 5 Section 4 Experimentation ACE Modes 49 6 4 Experimentation ACE Modes Now we describe the two experimentation modes The term mode was defined in Section 6 2 ACEA11EquivPresentations i val F ACEA11EquivPresentations val F for the ith or default interactive ACE process generates and tests an enumeration for combinations of relator ordering relator rotations and relator inversions val is in the integer range 1 to 7 The argument val is considered as a binary number Its three bits are treated as flags and control relator rotations the 2 bit relator inversions the 2 bit and relator orderings the 2 bit respectively where 1 means active and 0 means inactive See below for an example Before we describe the GAP output of ACEA11EquivPresentations let us spend some time considering what happens before the ACE binary output is parsed The ACEA11EquivPresentations command first performs a priming run using the options as they stand In particular the asis and messages options are honoured It then turns asis see 4 13 1 on and messages see 4 18 1 off i e sets messages to 0 and generates and tests the requested equivalent presentations The maximum and minimum values attained by m the maximum number of coset numbers defined
100. e the GAP code component the function ACEBinaryVersion see 6 5 25 gives details of the C code compilation History of release versions 001 First release 002 ACEIgnoreUnknownDefault see 4 11 2 added Option continue changed to continu see D 3 4 continue is a keyword in GAP 4 3 003 Initial value of ACEIgnoreUnknownDefault is now true previously it was false ACECosetTableFromGensAndRels and the non interactive ACECosetTable except when producing an input script via option ACEinfile and the non interactive ACEStats which previously used files all now invoke iostreams Option pkgbanner used to control the printing of the banner on loading see 2 2 4 0 Revised for GAP 4 4 for which the option pkgbanner is no longer available most of its function is now provided by the third argument of the LoadPackage function see 74 2 1 The package version number now has a single decimal place to avoid being confused with the binary version number 1 Added M 2 presentation to res examples pgrelfind g 5 0 Pre GAP 4 4 compatibility removed Now at least GAP 4 4 is required Option pkgbanner has been completely removed 5 1 The files configure and Makefile in were made more robust to ensure they will work well with both GAP 4 4 and GAP 4 Installing and Loading the ACE Package 2 1 Installing the ACE Package To install unpack the archive file which should have a name of form ace XXX zoo for some package version numb
101. e ACEData io i args record Use GetACEArgs see 6 5 7 in assignments Unlike ACEGroupGenerators see 6 5 1 ACERelators see 6 5 2 and ACESub groupGenerators see 6 5 3 DisplayACEArgs does not have the side effect of setting any of the fields of ACEData io z args if they are unset GetACEArgs i F GetACEArgs F return a record of the current arguments i e fgens rels and sgens of the ith or default process started by ACEStart In fact GetACEOptions 7 simply returns the ACEData io i args record or an empty record if that record is unbound Unlike ACEGroupGenerators see 6 5 1 ACERelators see 6 5 2 and ACESubgroupGenerators see 6 5 3 GetACEOptions does not have the side effect of setting any of the fields of ACEData io i args if they are unset DisplayACEOptions i F DisplayACEOptions F display the options explicitly set by the user of the ith or default process started by ACEStart In fact DisplayACEOptions i is just a pretty printer of the ACEData io z options record Use GetACEOptions see 6 5 7 in assignments Please note that no value ACE options will appear with the assigned value true see Section 4 6 for how the ACE interface functions interpret such options Notes Any options set via ACEWrite see 6 8 1 will not be displayed Also recall that if ACE is not given any options it uses the default strategy see Section 4 5 To discover the various settings of the ACE Parameter Options see
102. e strategy If this strategy is selected we follow a HLT type enumeration style i e R style see Section 3 1 but turn lookahead see 4 15 2 and compaction see 4 17 5 off For small and or easy enumerations this strategy is likely to be the fastest felsch felsch val Selects a Felsch strategy val should be 0 or 1 Shortest abbreviation fel Here a C style see Section 3 1 enumeration is selected Assigning felsch 0 or no value selects a pure Felsch strategy and a value of 1 selects a Felsch strategy with all relators in the subgroup i e no 1 see 4 13 4 and turns gap filling see 4 14 1 on hard Selects a mixed R style and C style strategy In many hard enumerations a mixture of R style and C style see Section 3 1 definitions all tested in all essentially different positions is appropriate This option selects such a mixed strategy The idea here is that most of the work is done C style with the relators in the subgroup i e no 1 see 4 13 4 and with gap filling see 4 14 1 on but that every 1000 C style definitions a further coset number is applied to all relators Guru Notes The 1000 1 mix is not necessarily optimal and some experimentation may be needed to find an acceptable balance see for example HRO1 Note also that the longer the total length of the presentation the more work needs to be done for each coset number application to the relators one coset number application can r
103. ed may be used to index which of these processes an interactive ACE interface function should be applied to The first four forms of ACEStart insert a start see D 3 2 directive after the user s options to invoke an enumeration The last four forms with 0 as first argument do not insert a start directive Moreover the last 3 forms of ACEStart with O as first argument only differ from the corresponding forms of ACEStart without the 0 argument in that they do not insert a start directive ACEStart 0 however is special unlike the no argument form of ACEStart it invokes a new interactive ACE process We will now further describe each form of ACEStart in the order they appear above The first form of ACEStart on three arguments is the usual way to start an interactive ACE process When ACEStart is called with one positive integer argument 7 it starts a new enumeration on the ith running process i e it scrubs a previously generated table and starts from scratch with the same parameters i e the same arguments and options except that if new options are included these will modify those given previously The only reason for doing such a thing without new options is to perhaps compare timings of runs a second run is quicker because memory has already been allocated If you are interested in this sort of information however you may be better off dealing directly with the standalone When ACEStart is called with no arguments it finds the
104. ed without a value from it being passed via hard true Passing hard false or hard val for any non true val will however produce a warning message unless the option acenowarnings is passed that the value 0 for false or val is unknown for that option Nevertheless despite the warning in this event the ACE interface function passes the value to the ACE binary When the ACE binary sees a line that it doesn t understand it prints a warning and simply ignores it So passing hard false will produce warnings but will have no ill effects The reason we still pass unknown values to the ACE binary is that it s conceivable a future version of the ACE binary might have several hard strategies in which case the ACE interface function will still complain until it s made aware of the Section 6 Interpretation of ACE Options 27 new possible values but it will perform in the correct manner if a value expected by the ACE binary is passed The felsch strategy option see 5 1 3 may be passed without a value which chooses the felsch 0 strategy or with the values 0 or 1 Despite the fact that GAP sees this option as boolean it is not There are two Felsch strategies felsch 0 and felsch 1 To get the felsch 1 strategy the user must pass felsch 1 If the user were to pass felsch false the result would be the felsch 0 strategy since false is always translated to 0 i e the same as how felsch true would be interpreted We could
105. ediately triggered the action of reinstantiating the value of ACEData io 1 args which is what the Info I No group generators saved Setting value s from ACE was all about Also observe that the Run Parameters block was Info ed twice the first time was due to ACEStart emitting sr with value 1 to ACE the response of which is used to re instantiate ACE Data io 1 args and the second is in response to transmitting Start to ACE In particular GAP no longer thinks fgens are the group generators gap gt ACEGroupGenerators 1 fgens false Groan We will just have to re instantiate everything gap gt fgens ACEGroupGenerators 1 gap gt F GroupWithGenerators fgens a F 1 b F 2 We now define a non trivial subgroup of small enough index to make the observation of all progress messages by setting messages 1 a not too onerous proposition As for defining the relators we could use the l argument version of ACEStart in which case we would use the subgroup see 4 19 2 option with the value ToACEWords fgens a xb However as we saw in the end we don t save anything by doing Section 1 Getting Started 89 this since afterwards the variables fgens a b and F would no longer be associated with ACEStart process 1 Instead we will use the more convenient 4 argument form and also switch the InfoACELevel back to 3 gap gt SetInfoACELevel 3 gap gt ACEStart 1 ACEGroupGenerators 1 ACERelators 1
106. elators a 2 b73 a b axb a b axb ax b ToACE gt enumeration A_5 ToACE gt subgroup Id ToACE gt max 0 88 Appendix C Finer Points with Examples I ToACE gt messages 1000 I No group generators saved Setting value s from ACE I ToACE gt sr 1 1 ACE 3 001 Run Parameters I Group Name A_5 I Group Generators ab I Group Relators a 2 bbb ababababab I Subgroup Name Id I Subgroup Generators I Wo 1000000 Max 333331 Mess 1000 Ti 1 Ho 1 Loop 0 I As 0 Path 0 Row 1 Mend 0 No 3 Look 0 Com 10 I C 0 R 0 Fi 6 PMod 3 PSiz 256 DMod 4 DSiz 1000 1 s So ee ee I ToACE gt text I I ToACE gt Start I ACE 3 001 Run Parameters I Group Name A_5 I Group Generators ab I Group Relators a 2 b 3 ab 5 I Subgroup Name Id I Subgroup Generators I Wo 1000000 Max 333331 Mess 1000 Ti 1 Ho 1 Loop 0 I As 0 Path 0 Row 1 Mend 0 No 3 Look 0 Com 10 I C 0 R 0 Fi 6 PMod 3 PSiz 256 DMod 4 DSiz 1000 1000 I INDEX 60 a 60 r 77 h 1 n 77 1 3 c 0 00 m 66 t 76 1 Note the usage of ToACEWords see 6 3 6 to provide the appropriate string value of the relators option Also observe the Info ed warning of the action triggered by using the relators option that says that the current values of the args i e what would be returned by GetACEArgs see 6 5 5 were discarded which imm
107. ement tell you exactly what to do for GAP 4 2 these lines are instead Info ed before the break loop announcement At the break loop prompt brk gt we relaxed all restrictions on max by re setting it to 0 and typed return to leave the break loop The coset enumeration was then successful allowing the computation of what turned out to be a trivial coset table Despite the fact that the eventual coset table only has one line i e there is exactly one coset number ACE did need to define more than 2 coset numbers To find out just how many were required before the final collapse let s set the InfoLevel of InfoACE see 1 9 3 to 2 so that the ACE enumeration result is printed 8 Chapter 1 The ACE Package gap gt SetInfoACELevel 2 gap gt ACECosetTable fgens rels c I INDEX 1 a 1 r 2 h 2 n 2 1 6 c 0 01 m 2049 t 3127 Rob Daas Pads bed E ids et ds Pts Eh Ts EG Et dy Pid Dads bts bald The enumeration result line is the Info line beginning I Appendix A explains how to interpret such output messages from ACE In particular it explains that t 3127 tells us that a total number of 3127 coset numbers needed to be defined before the final collapse to 1 coset number Using some of the many options that ACE provides one may achieve this result more efficiently e g with the purec strategy see 5 1 6 gap gt ACECosetTable fgens rels c purec I INDEX 1 a 1 r 2 h 2 n 2 1 4 c 0 00 m 332 t 332 Pb tsb tls
108. enumeration Guru Notes In five of the ten standard enumeration strategies of Sims Sim94 i e the five Sims strategies not provided by ACE the table is standardised repeatedly This is expensive computationally but can result in fewer cosets being necessary The effect of doing this can be investigated in ACE by repeatedly halting the enumeration via restrictive options standardising the coset numbering and continuing see Section C 2 for an example ACEAddRelators i wordlist F ACEAddRelators wordlist F add for the ith or default interactive ACE process started by ACEStart the words in the list wordlist to any relators already present and automatically invoke ACERedo if it can be applied or otherwise ACEStart Note that ACE sorts the resultant relator list unless the asis option see 4 13 1 has been set to 1 don t assume unless asis 1 that the new relators have been appended in user provided order to the previously existing relator list ACEAddRelators also returns the new relator list Use ACERelators see 6 5 2 to determine the current relator list ACEAddSubgroupGenerators i wordlist F ACEAddSubgroupGenerators wordlist F add for the ith or default interactive ACE process started by ACEStart the words in the list wordlist to any subgroup generators already present and automatically invoke ACERedo if it can be applied or otherwise ACEStart Note that ACE sorts the resultant subgroup generator lis
109. eorge Havas and Jane M Watson Implementation and analysis of the Todd Coxeter algorithm Mathematics of Computation 27 123 463 490 July 1973 Colin M Campbell George Havas Alexander Hulpke and Edmund F Robertson Efficient simple groups Communications in Algebra 30 9 4613 4619 2002 Thomas H Cormen Charles E Leiserson and Ronald L Rivest Introduction to Algorithms The MIT Press 1990 H S M Coxeter and W O J Moser Generators and Relations for Discrete Groups Springer Verlag 3rd edition 1972 George Havas Coset enumeration strategies In Proceedings of the International Symposium on Symbolic and Algebraic Computation ISSAC 91 Bonn 1991 pages 191 199 ACM Press 1991 George Havas and Colin Ramsay Coset enumeration ACE version 3 1999 ACE version 3 001 is available from http www csee uq edu au cram ce html George Havas and Colin Ramsay Groups and computation III In Ohio State University Mathematical Research Institute Publications volume 8 pages 183 192 de Gruyter 2001 John Leech Computer proof of relations in groups In Michael P J Curran editor Topics in Group Theory and Computation pages 38 61 Academic Press 1977 John Leech Coset enumeration In Michael D Atkinson editor Computational Group Theory pages 3 18 Academic Press 1984 Joachim Neubiiser An elementary introduction to coset table methods in computational group theory In Colin M Campbell and Edmund F Robertson edit
110. er XXX as a sub directory in the pkg hierarchy of your version of GAP 4 This might be the pkg directory of the GAP 4 home directory it is however also possible to keep an additional pkg directory in your private directories The only essential difference with installing ACE in a pkg directory different to the GAP 4 home directory is that one must start GAP with the 1 switch see Section 3 1 e g if your private pkg directory is a subdirectory of mygap in your home directory you might type gap 1 myhomedir mygap where myhomedir is the path to your home directory which since GAP 4 3 may be replaced by a tilde The empty path before the semicolon is filled in by the default path of the GAP 4 home directory After unpacking the archive go to the newly created ace directory and call configure path where path is the path to the GAP home directory So for example if you install the package in the main pkg directory call configure This will fetch the architecture type for which GAP has been compiled last and create a Makefile Now simply call make to compile the binary and to install it in the appropriate place Note that the current version of the configuration process only sets up directory paths If you need a different compiler or different compiler options you need to edit src Makefile in yourself prior to calling make If you use this installation of GAP on different hardware platforms you will have to compile the binary f
111. ertheless it is over ridden by the hlt option at the ACE level Observe the Other options set via ACE defaults list of options that has resulted from having the echo 2 option see 4 11 12 Observe also that hlt is nowhere near as good here as purec refer to Section 1 2 whereas purec completed the same enumeration with a total number of coset numbers of 332 the hlt strategy required 3127 Before we finish this section let us say something about the examples listed when one calls ACEExample with no arguments that have a beside them these are examples for which the enumeration fails to complete The first such example listed is 2p17 fel1 where a group of order 217 is enumerated over the identity subgroup with the felsch 1 strategy The enumeration fails after defining a total number of 416664 coset numbers In fact the enumeration can be made to succeed by simply increasing workspace to 4700k but in doing so a total of 783255 coset numbers are defined With the example 2p17 fel1la the same group is again enumerated again with the felsch 1 strategy but this time over the group itself and after tweaking a few options to see how well we can do The other 2p17 XXX examples are again enumerations of the same group but over smaller and smaller subgroups until we once again enumerate over the identity subgroup but far more efficiently this time only needing to define a total of 550659 coset numbers which can be achieve
112. es and totcosetsRange the range of values as a GAP list inside which each equivRuns i totcosets lies Notes In general the length of the equivRuns field list will be less than the number of runs executed There is no way to stop the ACEA11EquivPresentations command before it has completed other than killing the task So do a reality check beforehand on the size of the search space and the time for each enumeration If you are interested in finding a good enumeration it can be very helpful in terms of running time to put a tight limit on the number of coset numbers via the max option You may also have to set compaction 100 to prevent time wasting attempts to recover space via compaction This maximises throughput by causing the bad enumerations which are in the majority to overflow quickly and abort If you wish to explore a very large search space consider firing up many copies of ACE and starting each with a random equivalent presentation Alternatively you could use the ACERandomEquivPresentations command 2 gt ACERandomEquivPresentations i val gt ACERandomEquivPresentations val ACERandomEquivPresentations i val ACERandomEquivPresentations val ACERandomEquivPresentations i val Npresentations ACERandomEquivPresentations val Npresentations WV OV V AoyAyAyy for the ith or default interactive ACE process generates and tests up to Npresentations or 8 in the first 4
113. esult in more than 1000 definitions reversing the balance between R style and C style definitions 6 gt Section 1 The Strategies in Detail 43 hlt Selects ACE s standard HLT strategy Unlike Sims Sim94 default HLT strategy hlt sets the lookahead option see 4 15 2 However the option sequence hlt lookahead 0 easily achieves Sims default HLT strategy recall the ordering of options is respected see Section 4 4 This is an R style see Section 3 1 strategy purec Sets the strategy to basic C style see Section 3 1 In this strategy there is no compaction see 4 17 5 no gap filling see 4 14 1 and no relators in subgroup i e no 0 see 4 13 4 purer Sets the strategy to basic R style see Section 3 1 In this strategy there is no mendelsohn see 4 13 5 no compaction see 4 17 5 no lookahead see 4 15 2 and no row filling see 4 15 1 sims val Sets a Sims strategy val should be one of 1 3 5 7 or 9 In his book Sim94 Sims discusses and lists in Table 5 5 1 ten standard enumeration strategies The Sims strategies are effectively hlt see 5 1 5 without lookahead see 4 15 2 with or without mendelsohn see 4 13 5 set in R rt positive ct 0 or R style rt negative ct 0 and felsch see 5 1 3 all either with or without lenlex table standardisation see Section 3 4 and 6 7 2 or D 6 2 as the enumeration proceeds ACE does not implement table standardisation d
114. eviation dsiz Sets the size of the initial allocation for the deduction stack The size is in terms of the number of deductions with one deduction taking two words i e 8 bytes The default size of 1000 can be selected by a value of 0 See the dmode entry for a brief discussion of deduction handling 4 17 Technical ACE Parameter Options The following options do not affect how the coset enumeration is done but how it uses the computer s resources They might thus affect the runtime as well as the range of problems that can be tackled on a given machine workspace val Workspace size in words default 10 val should be an expression that evaluates to a positive integer or a string of digits ending in a k M or G representing a multiplication factor of 10 10 or 10 respectively e g both workspace 2 10 6 and workspace 2M specify a workspace of 2 x 10 words Actually if the value of workspace is entered as a string each of k M or G will be accepted in either upper or lower case Shortest abbreviation wo By default ACE has a physical table size of 10 words i e 4 x 10 bytes in the default 32 bit environment The number of coset numbers in the table is the table size divided by the number of columns Although the number of coset numbers is limited to 23t 1 if the C int type is 32 bits the table size can exceed the 4GByte 32 bit limit if a suitable machine is used Q2 gt 3 4 gt
115. f coset numbers defined in Hav91 for the enumeration of the cosets of a certain index 40 subgroup of the G 3 21 Macdonald group were 91 for HLT versus 16067 for a pure Felsch type strategy For the Felsch strategy with the group relators included as subgroup generators as for the felsch 1 strategy see 5 1 3 the total number of coset numbers defined reduced markedly to 59 A deduction occurs when the scanning of a relator results in the assignment of a coset table body entry A completed table is only valid if every table entry has been tested in all essentially different positions in all relators This testing can either be done directly Felsch strategy or via relator scanning HLT strategy If it is done directly then more than one deduction can be waiting to be processed at any one time The untested deductions are stored in a stack How this stack is managed is determined by the dmode option see 4 16 1 and its size is controlled by the dsize option see 4 16 2 As already mentioned a coincidence occurs when it is determined that two coset numbers in fact repre sent the same coset When this occurs the larger coset number becomes a dead coset number and the coincidence is placed in a queue When and how these dead coset numbers are eventually eliminated is Section 4 Coset Table Standardisation Schemes 21 controlled by the options dmode path and compaction see 4 16 1 4 17 4 and 4 17 5 The user may also force coincidences to oc
116. f finite index in a finitely presented group must eventually terminate with the correct result provided the enumeration process obeys a simple condition Mendelsohn s condition formulated in Lemma 1 and Theorem 2 of Neu82 This basic condition leaves room for a great variety of strategies for coset enumeration two classical ones have been known for a long time as the Felsch strategy and the HLT strategy for Haselgrove Leech and Trotter Extensive experimental studies on many strategies can be found in CDHW73 Hav91 HR99 and HRO1 in particular A few basic points should be particularly understood Subgroup generator and relator tables that are used in the description of coset enumeration in Neu82 and to which we will also occasionally refer in this manual do not physically exist in the im plementation of coset enumeration in ACE For a terminology that is closer to the actual implementation and also to the formulations in the manual for the ACE standalone see CDHW73 and Hav91 Coset enumeration proceeds by defining coset numbers that really denote possible representatives for cosets written as words in the generators of the group At the time of their generation it is not guaranteed that any two of these words do indeed represent different cosets The state of an enumeration at any time is stored in a 2 dimensional array known as a coset table whose rows are indexed by coset numbers and whose columns are indexed
117. f the ACE output when messages has a non zero value The default Group Name is G subgroup string Sets the Subgroup Name to string string must of course be a string Shortest abbreviation subg The default Subgroup Name is H 4 20 Options for redirection of ACE Output ao filename aceoutfile filename Redirects alters output to filename filename should be a string Non interactively ACE s output is normally directed to a temporary file whose full path is stored in ACE Data outfile which is parsed to produce a coset table or a list of statistics This option causes ACE s output to be directed to filename instead presumably because the user wishes to see and keep data out put by the ACE binary other than the coset table output from ACECosetTableFromGensAndRels or the statistics output by ACEStats Please refer to Appendix A where we discuss the meaning of the additional data to be found in the ACE binary s output The option aceoutfile is a GAP introduced synonym for ao that is translated to ao before submission to the ACE binary Do not use option aceoutfile when running the standalone directly Happily ao can also be regarded as mnemonical for aceoutfile 40 Chapter 4 Options for ACE 4 21 Other Options ACE has a number of other options but the GAP user will not ordinarily need them since in most cases alternative interactive functions exist These remaining options have been relegated to Appendix D The o
118. f you are interested in finding a good enumeration it can be very helpful in terms of running time to put a tight limit on the number of coset numbers via the max option You may also have to set compaction 100 to prevent time wasting attempts to recover space via compaction This maximises throughput by causing the bad enumerations which are in the majority to overflow quickly and abort If you wish to explore a very large search space consider firing up many copies of ACE and starting each with a random equivalent presentation Alternatively you could use the rep command INTERACTIVELY use ACEA11EquivPresentations see 6 4 1 rep val rep val Npresentations Run the enumeration for random equivalent presentations val is in the integer range 1 to 7 Npre sentations must be a positive integer The rep random equivalent presentations option complements the aep option It generates and tests some random equivalent presentations The argument val acts as for aep It is also possible to set the number Npresentations of random presentations used by default eight are used by using the extended syntax rep val Npresentations The routine first turns asis on and messages off i e sets messages to 0 and then generates and tests the requested number of random equivalent presentations For each presentation the relators used and the summary result line are printed To observe these messages either set the Inf
119. functions ACEModes i F ACEModes F for the ith or default interactive ACE process return a record whose fields are the modes ACEStart ACEContinue and ACERedo and whose values are true if the mode is possible for the process and false otherwise 2 gt Section 3 Interactive ACE Process Utility Functions and Interruption of an Interactive ACE Process 47 ACEContinue i options F ACEContinue options F for the ith or default interactive ACE process apply any options and then continue the current enumer ation building upon the existing table If a previous run stopped without producing a finite index you can in principle change any of the options and continue on Of course if you make any changes which invalidate the current table you won t be allowed to ACEContinue and an error will be raised However after quitting the break loop the interactive ACE process should normally still be active after doing so run ACEModes see 6 2 1 to see which of ACERedo or ACEStart is possible ACERedo i options F ACERedo options F for the ith or default interactive ACE process apply any options and then redo the current enumeration from coset 1 i e the subgroup keeping any existing information in the table Notes The difference between ACEContinue and ACERedo is somewhat technical and the user should regard it as a mode that is a little more expensive than ACEContinue but cheaper than ACES
120. g option nc with the value 1 It is still possible that some conjugates of the newly added subgroup generators will not be elements of the subgroup INTERACTIVELY use ACEConjugatesForSubgroupNormalClosure see 6 7 10 options Dumps version information of the ACE binary Shortest abbreviation opt A rather unfortunate name for an option this command dumps details of the options included in the version of ACE when the ACE binary was compiled A typical output is as follows Executable built Sat Feb 27 15 57 59 EST 1999 Level O options statistics package on coinc processing messages on dedn processing messages on Level 1 options workspace multipliers decimal Level 2 options host info on INTERACTIVELY and non interactively use the command ACEBinaryVersion see 6 5 25 for this information instead unless you want it in an ACE standalone input file 00 val order val Print a coset representative of a coset number with order a multiple of val modulo the subgroup val must be an integer This option finds a coset with order a multiple of val modulo the subgroup and prints out its coset representative If val lt 0 then all coset numbers meeting the requirement are printed If val gt 0 then just the first coset number meeting the requirement is printed Also val 0 is permitted this special value effects the printing of the orders modulo the subgroup of all coset numbers INTERACTIVELY
121. gh ACE s coset table starting at coset n and return the final coset number if the trace completes and fail otherwise In Group Theory terms if the cosets of a subgroup H in a group G are the subject of interactive ACE process i and the coset identified by that process by the integer n corresponds to some coset Hz for some x in G and word represents the element g of G then providing the current coset table is complete enough ACETraceWord i n word returns the integer identifying the coset Hzg Notes You may wish to compact ACE s coset table first either explicitly via ACERecover see 6 7 1 or implicitly via any function call that invokes ACE s compaction routine see 6 7 1 note If you actually wanted ACE s coset representative then for a compact table feed the output of ACETrace Word to ACECosetRepresentative see 6 5 13 Section 5 Interactive Query Functions and an Option Setting Function 55 18 gt ACEOrders i F gt ACEOrders F gt ACEOrders i suborder suborder F gt ACEOrders suborder suborder F for the ith or default interactive ACE process started by ACEStart search for all coset numbers whose representatives orders modulo the subgroup are either finite or if invoked with the suborder option are multiples of suborder where suborder should be a positive integer ACEOrders returns a possibly empty list of records each with fields coset order and rep which are respectively
122. h of compaction or lookahead is not off then some reuse of coset numbers may occur so that for the case where max is a positive integer the value of totcosets may be greater than max However whenever max is set to a positive integer both activecosets the number of alive coset numbers at the end of an enumeration and maxcosets the maximum number of alive coset numbers at any point of an enumeration are bounded by max See Section 3 5 for a discussion of the terminology activecosets and maxcosets hole val Maximum percentage of holes allowed during an enumeration val should be an integer in the range 1 to 100 Shortest abbreviation ho This is an experimental feature which allows an enumeration to be terminated when the percentage of holes in the table exceeds a given value In practice calculating this is very expensive and it tends to remain constant or decrease throughout an enumeration So the feature doesn t seem very useful The default value of 1 turns this feature off If you want more details read the source code 1 gt 2 gt Section 20 Options for redirection of ACE Output 39 4 18 ACE Parameter Options controlling ACE Output messages val monitor val Sets the verbosity of output from ACE val should be an integer Shortest abbreviation of messages is mess and shortest abbreviation of monitor is mon By default val 0 for which ACE prints out only a single line of information giving the
123. h a single command It is equivalent to executing ACEQuit i for all active interactive ACE processes i see 6 1 2 6 2 General ACE Modes For our purposes we define an interactive ACE interface command to be an ACE mode if it delivers an enu meration result see Section A 2 Thus ACEStart see 6 1 1 except when called with the argument 0 and the commands ACERedo and ACEContinue which we describe below are ACE modes we call these general ACE modes Additionally there are two other commands which deliver enumeration results ACEA1L1Equiv Presentations see 6 4 1 and ACERandomEquivPresentations see 6 4 2 we call these experimentation ACE modes and describe them in Section 6 4 Guru Note The ACE standalone uses the term mode in a slightly different sense There the commands start redo or continue put the ACE enumerator in start mode redo mode or continue mode In this manual we have used the term to mean the command itself and generalised it to include any command that produces enumeration results After changing any of ACE s parameters one of three general modes is possible one may be able to continue via ACEContinue see 6 2 2 or redo via ACERedo see 6 2 3 or if neither of these is possible one may have to re start the enumeration via ACEStart see 6 1 1 Generally the appropriate mode is invoked automatically when options are changed so most users should be able to ignore the following three
124. he reciprocal of this fraction the fill factor is manipulated via the fill option see 4 14 1 In Hav91 the felsch 1 type enumeration of the cosets of the certain index 40 subgroup of the G 3 21 Macdonald group was further improved to require a total number of coset numbers of just 43 by incorporating the use of preferred definitions 3 3 Finding Subgroups The ACE package via its interactive ACE interface functions described in Chapter 6 provides the possibility of searching for subgroups To do this one starts at a known subgroup possibly the trivial subgroup Then one may augment it by adding new subgroup generators either explicitly via ACEAddSubgroupGenerators see 6 7 4 or implicitly by introducing coincidences see ACECosetCoincidence 6 7 7 or ACERandom Coincidences 6 7 8 Also one may descend to smaller subgroups by deleting subgroup generators via ACEDeleteSubgroupGenerators see 6 7 6 3 4 Coset Table Standardisation Schemes The default standardisation scheme for GAP from GAP 4 3 and the standardisation scheme provided by ACE is the lenlex scheme of Charles Sims Sim94 This scheme numbers cosets first according to word length and then according to a lexical ordering of coset representatives Each coset representative is a word in an alphabet consisting of the user supplied generators and their inverses and the lexical ordering of lenlex is that implied by ordering that alphabet so that each generator is followed by
125. he ACE function with which the example is to be executed If ACEExamp1e is called with no arguments or with the argument index meant in the sense of list or with a non existent example name a list of available examples is displayed See Section B 4 where the list is displayed By default examples are executed via ACEStats However if ACEExample is called with a second argument choose from the other alternatives ACECosetTableFromGensAndRels or equivalently ACECosetTable or ACEStart the example is executed using that function instead Note that whereas the first argument appears in double quotes since it s a string the second argument does not since it s a function e g to ex ecute example A5 with function ACECosetTable one would type ACEExample A5 ACECosetTable ACEExample also accepts user options which may be passed either globally i e by using PushOptions to push them onto the OptionsStack or locally behind a colon after the ACEExample arguments and they are passed to ACEStats or ACEfunc as if they were appended to the existing options of examplename in this way the user may over ride any or all of the options of examplename This is done by passing an option aceexampleoptions see 4 11 15 which sets up a mechanism to reverse the usual order in which options of recursively called functions are pushed onto the OptionsStack The option aceexampleoptions is not a user option it is intended only for
126. here are no subgroup generators and the subgroup is trivial This command allows a list of subgroup generating words to be entered To convert a GAP list sgens of subgroup generators in the free group generators fgens into a form suitable for the generators option use the construction ToACEWords fgens sgens see 6 3 6 sg subgens Adds the words in subgens to any subgroup generators already present subgens must be a string or list of strings that the ACE binary can interpret as words in the group generators The enumeration must be re started or redone it cannot be continued 5 gt 6 gt 7 gt 8e v Section 2 Options that Modify a Presentation 97 To convert a GAP list sgens of subgroup generators in the free group generators fgens into a form suitable for the generators option use the construction ToACEWords fgens sgens see 6 3 6 INTERACTIVELY use ACEAddSubgroupGenerators see 6 7 4 rl relators Appends the relator list relators to the existing list of relators present relators must be a string or list of strings that the ACE binary can interpret as words in the group generators The enumeration must be re started or redone it cannot be continued To convert a GAP list rels of relators in the free group generators fgens into a form suitable for the r1 option use the construction ToACEWords fgens rels see 6 3 6 INTERACTIVELY use ACEAddRelators see 6 7 3 ds list Deletes subgroup generato
127. hus one will immediately get a consequence We will come back to the obvious question of where one obtains this preferred definition stack The enumeration style is mainly determined by the balance between C style and R style definitions which is controlled by the values of the ct and rt options see 4 13 2 and 4 13 3 However this still leaves us with plenty of freedom for the design of definition strategies freedom which can for example be used to great advantage in Felsch type strategies Though it is not strictly necessary before embarking on further enumeration Felsch type programs generally start off by ensuring that each of the given subgroup generators produces a cycle of coset numbers at coset 1 To explain the idea an example may help Suppose a b are the group generators and w Abab is a subgroup generator where A represents the inverse of a then to say that 1 i j k is a cycle of coset numbers produced at coset 1 by w means that the successive application of the letters A b a b of w takes one successively from coset 1 through cosets 7 7 and k and back to coset 1 i e A applied to coset 1 results in coset 1 b applied to coset i results in coset j a applied to coset j results in coset k and finally b applied to coset k takes us back to coset 1 In this way a hypothetical subgroup table is filled first The use of this and other possibilities leads to the following table of enumeration styles Rt value Ct
128. ibed in this manual The interface links to an external binary and therefore is only usable under UNIX see Section 2 1 for how to install ACE It will not work on Windows or a pre MacOSX Macintosh The current version requires at least GAP 4 4 Users who still have GAP 4 3 must use ACE 4 1 The first versions supported GAP 4 2 ACE can be used through this interface in a variety of ways one may supplant the usual GAP coset enumerator see Section 1 1 one may generate a coset table using ACE without redefining the usual GAP coset enumerator see Section 1 2 one may simply test whether a coset enumeration will terminate see Section 1 3 one may use GAP to write a script for the ACE standalone see Section 1 4 and one may interact with the ACE standalone from within GAP see Section 1 5 Among other things the interactive ACE interface functions described in Chapter 6 enable the user to search for subgroups of a group see the note of Section 1 5 Each of these ways gives the user access to a welter of options which are discussed in full in Chapters 4 and 5 Yet more options are provided in Appendix D but please take note of the Appendix s introductory paragraph Check out Appendix B for numerous examples of the ACE commands Note Some care needs to be taken with options be sure to read Section 1 7 and the introductory sections of Chapter 4 for some warnings regarding them and a general discussion of their u
129. ibility is discussed in detail via the example that follows The example given below is the call for a presentation of the Fibonacci group F 2 7 for which we shall discuss the impact of various options in Section B 4 Observe that in the example no options are passed which means that ACE uses the default strategy see Chapter 5 Section 2 Using ACE Directly to Generate a Coset Table 7 gap gt F gap gt a F 1 b F 2 c F 3 d F 4 e F gap gt fgens a b c d e x y l gap gt rels a xb c 1 b c d 1 c d e 1 d e x 1 gt e xx y 1 x y a 1 y xa b 1 gap gt ACECosetTable fgens rels c FreeGroup ol 5 pl E ten E nagn 5 el F Wy y 5 x F 6 y F 7 In computing the coset table ACECosetTableFromGensAndRels must first do a coset enumeration which is where ACE comes in If the coset enumeration does not finish in the preset limits a break loop is entered unless the incomplete see 4 11 6 or silent see 4 11 3 options is set In the event that a break loop is entered don t despair or be frightened by the word Error by tweaking ACE s options via the SetACEOptions function that becomes available in the break loop and then typing return it may be possible to help ACE complete the coset enumeration and hence successfully compute the coset table if not you will end up in the break loop again and you can have another go or quit if you ve had enough The SetACEOptions f
130. ignoreunknown option see 4 11 10 is passed or the aceignore option is passed and the option is an element of the list value of aceignore see 4 11 9 It is actually recommended that the user set ACEIgnoreUnknownDefault to false since this will allow the user to see when ACE functions have been passed options that are unknown to the ACE package In this way the user will be informed about misspelt options for example So it s a good debugging tool Also if the ACE binary is updated with a version with new options then these will not be known by the package the GAP part and it will be necessary to set ACEIgnoreUnknownDefault to false in order for the new options to be passed to the binary When an ACE function is invoked indirectly by some function that was called with non ACE options the warning messages may begin to be annoying and it s then a simple matter to set ACEIgnoreUnknownDefault back to the ACE 3 003 default value of true Warning messages regarding unknown options are printed unless the acenowarnings see 4 11 11 is passed or the option is ignored To see how options are interpreted by an ACE interface function pass the echo option As mentioned above any option that the ACE binary doesn t understand is simply ignored and a warning appears in the output from ACE If this occurs you may wish to check the input fed to ACE and the output from ACE which when ACE is run non interactively are stored in files whose fu
131. ill wait indefinitely The Meanings of ACE s output messages In this chapter we discuss the meanings of the messages that appear in output from the ACE binary the verbosity of which is determined by the messages option see 4 18 1 Actually our aim here is to concentrate on describing those messages that are controlled by the messages option namely the progress and results messages other output from ACE is fairly self explanatory We describe some other output to give points of reference Both interactively and non interactively ACE output is Info ed at InfoACE level 3 To see the Info ed ACE output set the InfoLevel of InfoACE to at least 3 e g gap gt SetInfoACELevel 3 This causes each line of ACE output to be prepended with I Below we describe the Info ed output observed when each of ACECosetTableFromGensAndRels ACECosetTable ACEStats or ACEStart is called with three arguments and presume that users will be able to extend the description to explain output observed from other ACE interface functions The first observed Info ed output from ACE is ACE s banner e g I ACE 3 001 Sun Sep 30 21 45 39 2001 H I 5555522222 I Host information I name rigel If there were any errors in the directives put to ACE or output from the options described in Appendix D they will appear next Then the next observed output is a row of three asterisks I Guru note The three asterisks are generated
132. ions are in general not orthogonal the order in which they are put to ACE is in general honoured see 4 4 Thirdly the ACE binary s concept of a boolean option is slightly different to that of GAP s Section 4 6 discusses in particular how an option detected by GAP as true is passed to the ACE binary Finally Section 4 5 discusses what happens if no option is selected Section 8 The ACEData Record 13 1 8 The ACEData Record 1 gt ACEData V is a GAP record in which the essential data for an ACE session within GAP is stored its fields are binary the path of the ACE binary tmpdir the path of the temporary directory containing the non interactive ACE input and output files also see 1 8 2 below ni the data record for a non interactive ACE process io list of data records for ACEStart see below and 6 1 1 processes infile the full path of the ACE input file outfile the full path of the ACE output file and version the version of the current ACE binary More detailed information regarding the compilation of the binary is given by ACEBinaryVersion see 6 5 25 Non interactive processes used to use files rather than streams hence the fields infile and outfile above these may disappear in a later version of the ACE package Each time an interactive ACE process is initiated via ACEStart see 6 1 1 an identifying number ioIndex is generated for the interactive process and a record ACEData io zoIndex with the followi
133. is that commonly one may specify a strategy option and override some of that strategy s defaults the general rule is that the later option prevails By the way it s not illegal to select more than one strategy but it s not sensible as just mentioned the later one prevails 4 5 What happens if no ACE Strategy Option or if no ACE Option is passed If an ACE interface function ACECosetTableFromGensAndRels ACEStats ACECosetTable or ACEStart is given no strategy option the default strategy see Chapter 5 is selected and a number of options that ACE needs to have a value for are given default values prior to the execution of any user options if any This ensures that ACE has a value for all its run parameters three of these are defined from the ACE interface function arguments and the remaining run parameters we denote by ACE Parameter Options For user convenience we have provided the ACEParameterOptions record see 4 12 1 the fields of which are the ACE Parameter Options The value of each field option of the ACEParameterOptions record is either a default value or in the case of an option that is set by a strategy a record of default values that ACE assumes when the user does not define a value for the option either indirectly by selecting a strategy option or directly If the default strategy does not suffice most usually a user will select one of the other strategies from among the ones listed in Chap
134. itions in C style that is filling the coset table line by line it can be very advantageous to switch to making definitions from the preferred definition stack Possible definitions can be extracted from this stack in various ways and the two options pmode and psize see 4 14 2 and 4 14 3 respectively regulate this However it should be clearly understood that making all definitions from a preferred definition stack one may violate the condition of Mendelsohn s theorem and the option fill see 4 14 1 can be used to avoid this fill val ffactor val Controls the preferred definition strategy by setting the fill factor val must be a non negative integer Shortest abbreviation of fill is fil and shortest abbreviation of ffactor is f Unless prevented by the fill factor gaps of length one found during deduction testing are preferentially filled see Hav91 However this potentially violates the formal requirement that all rows in the coset table are eventually filled and tested against the relators The fill factor is used to ensure that some constant proportion of the coset table is always kept filled Before defining a coset number to fill a gap of length one the enumerator checks whether fill times the completed part of the table is at least the total size of the table and if not fills coset table rows in standard order i e C style see Section 3 1 instead of filling gaps An argument of 0 selects the default value of 5 n 2 4
135. ive cosets at any point of an enumeration In practice the statistics maxcosets and totcosets tend to be of a similar order though of course max cosets can never be more than totcosets 3 6 Other Terminology In various places in this manual we will refer to a main loop or a pass through such a loop We don t intend to give a precise meaning to these terms The reader will need to forgive us for giving somewhat circular definitions in our attempt to make these terms less nebulous It is sufficient to appreciate that the ACE enumerator is organised as a state machine where each state is a value of the coset table held internally by ACE at the end of each main loop Each step from one state to the next i e each passage through the main loop performs an action i e lookahead compaction see 4 15 2 and 4 17 5 or a block of actions ie ct coset number definitions rt coset number applications ACE counts the number of passes through the main loop if the option loop see 4 17 3 is set to a positive integer ACE makes an early return when the loop count hits the value of loop Options for ACE ACE offers a wide range of options to direct and guide a coset enumeration most of which are available from GAP through the interface provided by the ACE Package We describe most of the options available via the interface in this chapter other options termed strategies are defined in Chapter 5 Strategies are merely special
136. k If the argument is 3 then the gaps of length one are noted in the preferred definition queue Provided such a gap survives and no coincidence occurs which causes the queue to be discarded the next coset number will be defined to fill the oldest gap of length one The default value is either 0 or 3 depending on the strategy selected see Chapter 5 If you want to know more details read the code psize val Size of preferred definition queue val must be 0 or 2 for some integer n gt 0 Shortest abbrevia tion psiz The preferred definition queue is implemented as a ring dropping earliest entries An argument of 0 selects the default size of 256 Each queue slot takes two words i e 8 bytes and the queue can store up to 2 1 entries 4 15 ACE Parameter Options for R Style Definitions row val Set the row filling option val is either 0 or 1 By default row filling is on i e true or 1 To turn it off set row to false or 0 both are translated to 0 when passed to the ACE binary When making HLT style i e R style see Section 3 1 definitions rows of the coset table are scanned for holes after its coset number has been applied to all relators and definitions are made to fill any holes encountered This will in particular guarantee fulfilment of the condition of Mendelsohn s Theorem Failure to do so can cause even simple enumerations to overflow lookahead val Lookahead val should be in
137. l is still 2 To avoid getting a trace back during the break loop which can look a little scary to the unitiated we will set OnBreak see 6 4 3 as follows gap gt NormalOnBreak OnBreak Save the old value to restore it later gap gt OnBreak function Where 0 end Note that there are some user input comments inserted at the brk gt prompt Section 4 Fun with ACEExample 75 gap gt ACEExample F27 purec ACECosetTableFromGensAndRels gt sg c subgroup lt c gt max 2 hlt I ACEExample F27 purec enumeration of cosets of H in G I where G F 2 7 C_29 H Id using purec strategy I I F G a b c d e x y are local to ACEExample I We define F 2 7 on 7 generators I F FreeGroup a b c d e x y 1 a F 1 b F 2 c F 3 d F 4 1 e F 5 x F 6 y F 7 I G F a b c 1 b c d 1 c d e7 1 d e x 1 I e xx y 1 x y a 1 y a b 1 I ACECosetTableFromGensAndRels I FreeGenerators0fFpGroup G I Relators0fFpGroup G I Generators of identity subgroup empty list I Options that don t affect the enumeration I echo enum F 2 7 aka C_29 subg Id I Other options I wo 2M mess 25000 purec I User Options I sg ce I subgroup lt c gt I max 2 I hlt true ACECosetTableFromGensAndRels called with the following arguments Group generators
138. least positive integer for which an interactive process is running and applies ACEStart 7 Most users will only run one interactive process at a time Hence ACEStart will be a useful shortcut for ACEStart 1 The fourth form of ACEStart on four arguments invokes a new enumeration on the ith running process with new generators fgens relators rels and subgroup generators sgens This is provided so a user can re use an already running process rather than start a new process This may be useful when pseudo ttys are a scarce resource See the notes for the non interactive ACECosetTable 1 2 1 which demonstrates an application of a usage of this and the following form of ACEStart in a loop The fifth form of ACEStart on the one argument 0 initiates an interactive ACE process processes any user options but does not insert a start see D 3 2 directive This form is mainly for gurus who are familiar with the ACE standalone and who wish at least initially to communicate with ACE using the primitive read write tools of Section 6 8 In this case after the group generators relators and subgroup generators have been set in the ACE process invocations of any of ACEGroupGenerators see 6 5 1 ACERelators see 6 5 2 ACESubgroupGenerators see 6 5 3 or ACEParameters see 6 5 10 will establish the corresponding GAP values Be warned though that unless one of the general ACE modes see Section 6 2 ACEStart without a zero argument ACERed
139. ll path names are recorded in the record fields ACEData infile and ACEData outfile respectively Alternatively both interactively and non interactively one can set the InfoLevel of InfoACE to 3 see 1 9 3 to see the output from ACE or to 4 to also see the commands directed to ACE 28 Chapter 4 Options for ACE 4 7 An Example of passing Options Continuing with the example of Section 1 2 one could set the echo option to be true use the hard strategy option increase the workspace to 10 words and turn messaging on but to be fairly infrequent by setting messages to a large positive value as follows gap gt ACECosetTable fgens rels c gt echo hard Wo 10 7 mess 10000 As mentioned in the previous section echo may be thought of as a boolean option whereas hard is a strategy option and hence should be thought of as a no value option Also observe that two options have been abbreviated Wo is a mixed case abbreviation of workspace and mess is an abbreviation of messages 4 8 The KnownACEOptions Record 1 gt KnownACEOptions V is a GAP record whose fields are the ACE options known to the ACE interface each field known ACE option is assigned to a list of the form i ListOrFunction where i is an integer representing the length of the shortest abbreviation of the option and ListOrFunction is either a list of known allowed values or a boolean function that may be used to determine if the given value is a known
140. ls of ACE to dump You will need to read the standalone manual acce3001 dvi in the standalone doc directory to understand what Levels 0 1 and 2 are all about The value of detail determines the amount of detail detail 0 means less detail The first form with no arguments selects level 0 detail 0 The second form of this command makes detail 0 This option is intended for gurus the source code should be consulted to see what the output means INTERACTIVELY use ACEDumpVariables see 6 5 23 help Prints the ACE help screen Shortest abbreviation h 4 gt v 5 gt 7 gt 100 Appendix D Other ACE Options This option prints the list of options of the ACE binary Note that this list is longer than a standard screenful nc nc val normal normal val Check or attempt to enforce normal closure val must be 0 or 1 This option tests the subgroup for normal closure within the group If a conjugate of a subgroup generator by a generator is determined to belong to a coset other than coset 1 it is printed out and if val 1 then any such conjugate is also added to the subgroup generators With no argument or if val 0 ACE does not add any new subgroup generators Notes The method of determination of whether a conjugate of a subgroup generator is in the subgroup is by testing whether it can be traced from coset 1 to coset 1 see trace D 5 12 The resultant subgroup need not be normally closed after executin
141. n when there are no currently active interactive ACE processes and in such a case ACEBinaryVersion emits a warning that there are no interactive ACE sessions currently active and initiates and closes again its own stream to obtain the information from the ACE binary For the current version of the ACE package the GAP code component use ACEPackageVersion see 1 11 1 6 6 Interactive Versions of Non interactive ACE Functions ACECosetTable i options F ACECosetTable options F return a coset table as a GAP object in standard form for GAP These functions perform the same function as ACECosetTableFromGensAndRels and ACECosetTable on three arguments see 1 2 1 albeit interactively on the ith or default process started by ACEStart If options are passed then an internal version of ACEModes is run to determine which of the general ACE modes see Section 6 2 ACEContinue ACERedo or ACEStart is possible and an internal version of the first mode of these that is allowed is executed to ensure the resultant table is correct for the current options ACEStats i options F ACEStats options F perform the same function as ACEStats on three arguments see 1 3 1 non interactive version albeit interactively on the ith or default process started by ACEStart If options are passed then an internal version of ACEModes is run to determine which of the general ACE modes see Section 6 2 ACEContinue ACERedo or
142. n routine called but nothing recovered CL n complete lookahead table as deduction stack UH n updated completed row counter RA n remaining coset numbers applied to relators SG n subgroup generator phase RS n relators in subgroup phase DS n stack overflowed compacted and doubled A 2 Results Messages The possible results are given in the following table any result not listed represents an internal error and should be reported to the ACE authors result tag meaning INDEX x finite index of x obtained OVERFLOW out of table space SG PHASE OVERFLOW out of space processing subgroup generators ITERATION LIMIT loop limit triggered TIME LIMT ti limit triggered HOLE LIMIT ho limit triggered INCOMPLETE TABLE all coset numbers applied but table has holes MEMORY PROBLEM out of memory building data structures Notes Recall that hole monitoring is switched on by setting a negative value for the messages see 4 18 1 option but note that hole monitoring is expensive so don t turn it on unless you really need it If you wish to print out the presentation and the options but not the progress messages then set messages non zero but very large You ll still get the SG DS etc messages but not the RD DD etc ones You can set messages to 1 to monitor all enumerator actions but be warned that this can yield very large output files Examples In this chapter we collect together a number of examples which
143. n should be applied to An interactive ACE process is terminated with the command ACEQuit i where 7 is the integer returned by ACEStart when the process was begun ACEQuit may also be called with no arguments see 6 1 2 We discuss each of these commands as well as the range of functions which enable one to access features of the ACE standalone not available non interactively in depth in Chapter 6 Note ACE not only allows one to do a coset enumeration of a group by a given and then fixed subgroup but it also allows one to search for subgroups by starting from a given one possibly the trivial subgroup and then aug menting it by adding new subgroup generators either explicitly via ACEAddSubgroupGenerators see 6 7 4 or implicitly by introducing coincidences see ACECosetCoincidence 6 7 7 or ACERandomCoincidences 6 7 8 or one can find smaller subgroups by deleting subgroup generators via ACEDeleteSubgroupGenera tors see 6 7 6 1 gt v Section 6 Accessing ACE Examples with ACEExample and ACEReadResearchExample 11 1 6 Accessing ACE Examples with ACEExample and ACEReadResearchExample There are a number of examples available in the examples directory which may be accessed via ACEExample ACEExample examplename options ACEExample ezamplename ACEfunc options z m 7 WN where examplename is a string the name of an example and corresponding file in the examples directory and ACEfunc is t
144. neglecting to restore the original presentation is an error In fact it is a useful feature Suppose that the space of equivalent presentations is too large to exhaustively test As noted in the entry for ACEA11EquivPresentations we can start up multiple copies of ACEA11EquivPresentations at random points in the search space Manually generating random equivalent presentations to serve as starting points is tedious and error prone The ACERandomEquivPresentations command provides a simple solution simply run ACERandomEquivPresentations i 7 before ACEA11EquivPresentations i 7 6 5 Interactive Query Functions and an Option Setting Function ACEGroupGenerators i F ACEGroupGenerators F return the GAP group generators of the ith or default interactive ACE process If no generators have been saved for the interactive ACE process possibly because the process was started via ACEStart 0 see 6 1 1 the ACE process is interrogated and the equivalent in GAP is saved and returned Essentially ACEGroupGenerators i interrogates ACE and establishes ACEData io i args fgens if necessary and returns ACEData io i args fgens As a side effect if any of the remaining fields of ACEData io i args or ACEData io i acegens are unset they are also set Note that GAP provides GroupWithGenerators see 37 2 2 in the GAP Reference Manual to establish a free group on a given set of already defined gener ators ACERelators i F ACERelators F
145. nfile aceoutfile aceignore aceignoreunknown acenowarnings aceincomment aceecho and echo discussed in Section 4 11 almost all single word ACE binary options and purer and purec The options purer and purec give the ACE binary options pure r and pure c respectively they are the only multiple word ACE binary options that do not have a single word alternative The only single word ACE binary options that are not available via the ACE interface are abbreviations that clash with GAP keywords e g fi for fill rec for recover and continu for continue The detail of this paragraph is probably of little importance to the GAP user these comments have been included for the user who wishes to reconcile the respective functionalities of the ACE interface and the ACE standalone and are probably of most value to standalone users 26 Chapter 4 Options for ACE 4 4 Honouring of the order in which ACE Options are passed It is important to realize that ACE s options even the non strategy options are not orthogonal i e the order in which they are put to ACE can be important For this reason except for a few options that have no effect on the course of an enumeration the order in which options are passed to the ACE interface is preserved when those same options are passed to the ACE binary One of the reasons for the non orthogonality of options is to protect the user from obtaining invalid enumerations from bad combinations of options another reason
146. ng fields is created A non interactive process has similar fields but is stored in the record ACEData ni proclid the identifying number of the process ioIndex for interactive processes and 0 for a non interactive process args a record with fields fgens rels sgens whose values are the corresponding arguments passed originally to ACEStart options the current options record of the interactive process acegens a list of strings representing the generators used by ACE if the names of the generators passed via the first argument fgens of ACEStart were all lowercase alphabetic characters then acegens is the String equivalent of fgens i e acegens 1 String fgens 1 etc stream the IOStream opened for an interactive ACE process initiated via ACEStart and enumResult the enumeration result string without the trailing newline output from ACE stats a record as output by the function ACEStats Q2 gt 1 gt Q2 gt 14 Chapter 1 The ACE Package enforceAsis a boolean that is set to true whenever the asis option see 4 13 1 must be set to 1 It is usually false See 1 2 3 Guru Notes for the details ACEDirectoryTemporary dir F calls the UNIX command mkdir to create dir which must be a string and if successful a directory object for dir is both assigned to ACEData tmpdir and returned The fields ACEData infile and ACEData outfile are also set to be files in ACEData tmpdir and on exit from GAP dir is removed M
147. ng the example following observe that in the Info block all the original example options are listed along with our new options sg c messages 0 after the tag User Options Following the Info block there is a block due to echo in its listing of the options first up there is aceexampleoptions alerting us that we passed some ACEExample options observe also that in this block subg Id and mess 25000 disappear they are over ridden by subgroup lt c gt messages 0 but the quotes for the value of subgroup are not visible note that we don t have to use the same abbreviations for options to over ride them Also observe that our new options are last gap gt SetInfoACELevel 2 gap gt ACEExample F27 purec ACECosetTableFromGensAndRels gt sg c subgroup lt c gt messages 0 I ACEExample F27 purec enumeration of cosets of H in G I where G F 2 7 C_29 H Id using purec strategy I 74 Appendix B Examples I F G a b c d e x y are local to ACEExample I We define F 2 7 on 7 generators I F FreeGroup a b c d e x y 1 a F 1 b F 2 c F 3 d F 4 I e F 5 x F 6 y F 7 I G F a b c 1 b c d 1 c d e 1 d e x 1 I e xx y 1 x y a 1 y xa b 1 I ACECosetTableFromGensAndRels I FreeGenerators0fFpGroup G I Relators0fFpGroup G I Generators of identity subgroup empty list I
148. niversally Sims Sim94 gives many examples where the even numbered strategies fail to show any significant improvement over the odd numbered strategies and one example see Table 5 5 7 where sims 2 gives a performance that is very much worse than any of the other Sims strategies As with any of the strategies what works well for some groups may not work at all well with other groups There are no general rules It s a bit of a game Let s hope you win most of the time 1 gt Other ACE Options Here we list all the known ACE options not provided earlier Most of the options provided here have interac tive function alternatives each such alternative is noted at the end of the section describing the corresponding option and introduced by INTERACTIVELY use A few options have only limited usefulness from GAP many options users will normally only wish to use if generating an input file by using the option aceinfile see 4 11 7 However all options here are functional both interactively and non interactively D 1 Experimentation Options aep val Runs the enumeration for all equivalent presentations val is in the integer range 1 to 7 The aep option runs an enumeration for combinations of relator ordering relator rotations and relator inversions The argument val is considered as a binary number Its three bits are treated as flags and control relator rotations the 2 bit relator inversions the 2 bit and rela
149. non interactive i e by their use a file with your input data in ACE readable format will be handed to ACE and you will get the answer back in GAP format At that moment however the ACE job is terminated that is you cannot send any further questions or requests about the result of that job to ACE For an interactive use of ACE from GAP see Section 1 5 and Chapter 6 Using the ACE interface directly to generate a coset table is done by either of ACECosetTableFromGensAndRels fgens rels sgens options F ACECosetTable fgens rels sgens options F Here fgens is a list of free generators rels a list of words in these generators giving relators for a finitely presented group and sgens the list of subgroup generators again expressed as words in the free generators All these are given in the standard GAP format see Chapter 45 of the GAP Reference Manual Note that the 3 argument form of ACECosetTable described here is merely a synonym for ACECosetTableFromGen sAndRels and that ACECosetTable may be called in a different way in an interactive ACE session see Sections 1 5 and 6 6 1 Behind the colon any selection of the options available for the interface see Chapters 4 and 5 can be given separated by commas like record components These can be used e g to preset limits of space and time to be used to modify input and output and to modify the enumeration procedure Note that strategies are simply special options that set a number
150. ns Notes In some strategies e g hlt see 5 1 5 a lookahead phase may be run before compaction is attempted In other strategies e g sims 3 see 5 1 8 compaction may be performed while there are outstanding deductions since deductions are discarded during compaction a final lookahead phase will automatically be performed Compacting a table destroys information and history in the sense that the coincidence list is deleted and the table entries for any dead coset numbers are deleted max val Sets the maximum coset number that can be defined val should be 0 or an integer greater than or equal to 2 By default which is the case max 0 all of the workspace is used if necessary in building the coset table So the table size in terms of the number of rows is an upper bound on how many coset numbers can be alive at any one time The max option allows a limit to be placed on how much physical table space is made available to the enumerator Enough space for at least two coset numbers i e the subgroup and one other must be made available Notes If the easy strategy see 5 1 2 is selected so that compaction see 4 17 5 is off i e set to 100 and lookahead see 4 15 2 is off i e set to 0 and max is set to a positive integer then coset numbers are not reused and hence max bounds the total number totcosets see Section 3 5 of coset numbers defined during an enumeration On the other hand if one or bot
151. o see 6 2 3 or ACEContinue see 6 2 2 or one of the mode options start see D 3 2 redo see D 3 3 or continu see D 3 4 has been invoked since the last change of any parameter options see 4 12 1 some of the values reported by ACEParameters may well be incorrect The sixth form of ACEStart on four arguments is like the first form of ACEStart on three arguments except that it does not insert a start see D 3 2 directive It initiates an interactive ACE process with a presentation defined by its last 3 arguments The seventh form of ACEStart on two arguments is like the second form of ACEStart on one argument except that it does not insert a start see D 3 2 directive It processes any new options for the ith interactive ACE process ACEStart 0 i options is similar to SetACEOptions i options see 6 5 8 but unlike the latter does not invoke a general mode see Section 6 2 Q2 gt 3 46 Chapter 6 Functions for Using ACE Interactively The last form of ACEStart on five arguments is like the fourth form of ACEStart on four arguments except that it does not insert a start see D 3 2 directive It re uses an existing interactive ACE process with a new presentation There is no form of ACEStart with the same functionality as this form where the i argument is omitted Note When an interactive ACE process is initiated by ACEStart a process number i is assigned to it the integer i returned by the A
152. oLevel of InfoACE to at least 3 or non interactively you can peruse the ACE output file see 4 11 8 Normally when a non interactive ACE interface function is called the option start see D 3 2 is quietly inserted after all the options provided by the user to initiate a coset enumeration Since the rep option invokes an enumeration the quiet insertion of the start option is neither needed nor done when a non interactive ACE interface function is called with the rep option Notes The relator inversions and rotations are genuinely random The relator permuting is a little bit of a kludge with the quality of the permutations tending to improve with successive presentations When the rep command completes the presentation active is the last one generated not that the non interactive user cares Guru Notes It might appear that neglecting to restore the original presentation is an error In fact it is a useful feature Suppose that the space of equivalent presentations is too large to exhaustively test As noted in the entry for aep we can start up multiple copies of aep at random points in the search space Manually generating random equivalent presentations to serve as starting points is tedious and error prone The rep option provides a simple solution simply run rep 7 before aep 7 INTERACTIVELY use ACERandomEquivPresentations see 6 4 2 1 gt 2 gt 3 gt 4 gt 96 Appendiz D Other ACE Options D 2 O
153. ome options may be reported with incorrect values if they have been changed recently without following up with one of the modes ACEContinue ACERedo or ACEStart Together the commands ACEGroupGenerators ACERelators ACESubgroupGenerators and ACEParameters give the equivalent GAP information that is obtained in ACE with sr 1 see D 5 7 which is the Run Parameters block obtained in the messaging output observable when the InfoLevel of InfoACE is set to at least 3 when messages see 4 18 1 is set a non zero value Notes One use for this function might be to determine the options required to replicate a previous run but be sure that if this is your purpose any recent change in the parameter option values has been followed by an invocation of one of ACEContinue see 6 2 2 ACERedo see 6 2 3 or ACEStart see 6 1 1 As a side effect for ACE process i any of the fields of ACEData io i args or ACEData io i acegens that are unset are set IsCompleteACECosetTable i F IsCompleteACECosetTable F return for the ith or default process started by ACEStart true if ACE s current coset table is complete or false otherwise Note The completeness of the coset table of the ith interactive ACE process is determined by checking whether ACEData io z stats index is positive a value of zero indicates the last enumeration failed to complete The record ACEData io i stats is what is returned by ACEStats i see 1 3 1 ACEDisplayCo
154. omplete reduced amp lenlex standardised 2 6 1 12 0 0 O 0 3 0 0 0 gt 1 9 0 O 2 0 0 0 0 0 4 7 10 O 1 0 O 2 O 0 3 0 gt 8 11 1 0 0 2 0 0 3 0 0 BODDODOONDOWOHW OO OO OOO OO Ome w ion DTO OWO OTO oono APUNE m TOGT O RN O O OF WW WOONDOFO ODOWOONDW OFF OH O OOWOOCO 0 Observe that despite the fact that ACE is able to define coset representatives for all 12 coset numbers defined the body of the coset table now contains a 0 at each place formerly occupied by a coset number larger than 12 0 essentially represents don t know To get a table that is the same in the first 12 rows as before we would have had to set max to 38 since that was the largest coset number that appeared in the body of the 12 line table previously Also note that the max option preceded the start option since the interface respects the order in which options are put by the user the enumeration invoked by start would otherwise have only been restricted by the size of workspace see 4 17 1 The warning that the coset table is incomplete is emitted at InfoACE or InfoWarning level 1 i e by default you will see it Using ACEStart The limitation of the functions ACEStats and ACECosetTableFromGensAndRels on three arguments is that they do not interact with ACE they call ACE with user defined input and collect and parse the output for either statistics or a coset table On the other han
155. option instead of the silent option However if we did that with the example above the result would be an enormous table the number of active cosets is 249998 so let us also set the max see 4 17 6 option in order that we should get a more modestly sized partial table Finally we will use print 12 since it is a shorter equivalent alternative to print 1 12 Note that the output here was obtained with GAP 4 3 and is the same with GAP 4 4 With GAP 4 2 the output was similar except that the last Info ed message before the final output states that the coset table result is incomplete only since no standardisation is done It turns out that the table displayed via the print option is already in lenlex standard form so despite the differences in the GAP versions each version of GAP since GAP 4 2 has output the same table gap gt ACECosetTableFromGensAndRels fgens max 12 gt start print 12 gt incomplete I ACE 3 001 Wed Oct 31 09 41 14 2001 HI SsssssssssssssssssSSssSSSSeSSSSSSSS5S S5 I Host information 1 name rigel I OVERFLOW a 12 r 4 h 4 n 13 1 5 c 0 00 m 12 t 12 I co a 12 r 4 h 4 n 13 c 0 00 Section 1 Getting Started 83 1 coset HI 1 1 1 2 1 3 1 4 1 5 6 vA 8 9 I I I I I 10 I 11 I 12 I I co a 12 r 4 h 4 n 13 c 0 00 I coset 1 n I I I I I I I I I I I 11 I 12 4 0 0 I ACECosetTable Coset table is inc
156. option restarts the enumeration if it is necessary to ensure the generators have not been rearranged Guru Notes In five of the ten standard enumeration strategies of Sims Sim94 i e the five Sims strategies not provided by ACE the table is standardised repeatedly This is expensive computationally but can result in fewer cosets being necessary The effect of doing this can be investigated in ACE by repeatedly halting the enumeration via restrictive options standardising the coset numbering and continuing see Section C 2 for an interactive example INTERACTIVELY use ACEStandardCosetNumbering see 6 7 2 1 gt Q2 gt Section 7 Options for Comments 103 D 7 Options for Comments text string Prints string in the output string must be a string This allows the user to add comments to the output from ACE Note Please avoid using this option to insert comments starting with three asterisks since this string is used as a sentinel internally in flushing output from ACE aceincomment string Prints comment string in the ACE input string must be a string Shortest abbreviation aceinc This option prints the comment string behind a sharp sign in the input to ACE Only useful for adding comments that ACE ignores to standalone input files CDHW73 CHHR02 CLR90 CM72 Hav91 HR99 HRO1 Lee77 Lee84 Neu82 Ram99 Sim94 Bibliography John J Cannon Lucien A Dimino G
157. options of ACE that set a number of options described in this chapter all at once Yet other options for which interactive function alternatives are provided in Chapter 6 or which most GAP users are unlikely to need are described in Appendix D From within a GAP session one may see the complete list of ACE options after loading the ACE Package see Section 2 2 by typing gap gt RecNames KnownACEOptions aceinfile aceignore aceignoreunknown acenowarnings aceecho aceincomment aceexampleoptions silent lenlex semilenlex incomplete sg rl aceoutfile asis begin start bye exit qui cc compaction continu cycles dmode dsize default ds dr dump easy echo enumeration felsch ffactor fill group generators relators hard help hlt hole lookahead loop max mendelsohn messages monitor mode nce normal no options oo order path pmode psize print purec purer rc recover contiguous rep rfactor rt row sc stabilising sims standard statistics stats style subgroup system text time tw trace workspace aep ai ao cfactor ct check redo sr n p See Section 4 8 Also from within a GAP session you may use GAP s help browser see Chapter 2 in the GAP Reference Manual to find out a
158. or each platform separately This is done by calling configure editing src Makefile in possibly and calling make for the package anew immediately after compiling GAP itself for the respective architecture If your version of GAP is already compiled and has last been compiled on the same architecture you do not need to compile GAP again it is sufficient to call the configure script in the GAP home directory The manual you are currently reading describes how to use the ACE Package it can be found in the doc subdirectory of the package If your manual does not have a table of contents or index or has these but with invalid page numbers please re generate the manual by executing make_doc in the doc subdirectory The subdirectory standalone doc contains the file ace3001 ps which holds a version of the user manual for the ACE standalone it forms part of Ram99 You should consult it if you are going to switch to the ACE standalone e g in order to directly use interactive facilities The src subdirectory contains a copy of the original source of ACE The only modification is that a file Makefile in was obtained from the different make xyz and will be used to create a Makefile You can replace the source by a newer version before compiling If you encounter problems in installation please read the README Section 2 Loading the ACE Package 17 2 2 Loading the ACE Package To use the ACE Package you have to request it explicitly With GAP
159. ors Groups St Andrews 1981 Proceedings of a conference St Andrews 1981 volume 71 of London Math Soc Lecture Note Series pages 1 45 Cambridge University Press 1982 Colin Ramsay ACE for amateurs version 3 001 Technical Report 14 Centre for Discrete Mathematics and Computing The University of Queensland St Lucia 4072 Australia 1999 Charles C Sims Computation with finitely presented groups Cambridge University Press 1994 Index This index covers only this manual A page number in italics refers to a whole section which is devoted to the indexed subject Keywords are sorted with case and spaces ignored e g PermutationCharacter comes before permutation group A Abbreviations and mixed case for ACE Options 25 Accessing ACE Examples with ACEExample and ACEReadResearchExample 11 ace 5 ACEAddRelators 58 ACEAddSubgroupGenerators 58 ACEA11EquivPresentations 49 ACEBinaryVersion 56 ACEConjugatesForSubgroupNormalClosure 60 ACEContinue 47 ACECosetCoincidence 59 ACECosetOrderFromRepresentative 55 ACECosetRepresentative 54 ACECosetRepresentatives 54 ACECosetsThatNormaliseSubgroup 55 ACECosetTable 6 break loop example 7 interactive 57 non interactive 6 ACECosetTableFromGensAndRe1s 6 example 81 ACECycles 54 ACEData 13 ACEDeleteRelators 59 ACEDeleteSubgroupGenerators 59 ACEDirectoryTemporary 14 ACEDisplayCosetTable 53 ACEDumpStatistics 56 ACEDumpVariables 56 ACEExample 11 ACEG
160. ost users will never need this command by default GAP typically chooses a random subdirectory of tmp for ACEData tmpdir which may occasionally have limits on what may be written there ACEDirectoryTemporary permits the user to choose a directory object where one is not so limited 1 9 Setting the Verbosity of ACE via Info and InfoACE Inf oACE V The output of the ACE binary is by default not displayed However the user may choose to see some or all of this output This is done via the Info mechanism see Chapter 7 4 in the GAP Reference Manual For this purpose there is the InfoClass InfoACE Each line of output from ACE is directed to a call to Info and will be displayed for the user to see if the InfoLevel of InfoACE is high enough By default the InfoLevel of InfoACE is 1 and it is recommended that you leave it at this level or higher Only messages which we think that the user will really want to see are directed to Info at InfoACE level 1 To turn off all InfoACE messaging set the InfoACE level to 0 see 1 9 3 For convenience we provide the function InfoACELevel F which returns the current InfoLevel of InfoACE i e it is simply a shorthand for InfoLevel InfoACE To set the InfoLevel of InfoACE we also provide SetInfoACELevel level F SetInfoACELevel F which for a non negative integer level sets the InfoLevel of InfoACE to level i e it is a shorthand for Set InfoLevel InfoACE level or with no arguments se
161. otherwise See the notes for 6 1 1 and 6 1 2 If the user does not yet have a gap gt prompt then usually ACE is still away doing something and an ACE interface function is still waiting for a reply from ACE Typing a Ctrl C i e holding down the Ctrl key and typing c will stop the waiting and send GAP into a break loop from which one has no option but to quit The typing of Ctrl C in such a circumstance usually causes the stream of the interactive ACE process to die to check this we provide IsACEProcessAlive see 6 3 3 If the stream of an interactive ACE process indexed by 7 say has died it may still be possible to recover enough of the state before the death of the stream from the information stored in the ACEData io record see Section 1 8 For such a purpose we have provided ACEResurrectProcess see 6 3 4 The GAP iostream of an interactive ACE process will also die if the ACE binary has a segmentation fault We do hope that this never happens to you but if it does and the failure is reproducible then it s a bug 5 gt 6 gt 48 Chapter 6 Functions for Using ACE Interactively and we d like to know about it Please read the README that comes with the ACE package to find out what to include in a bug report and who to email it to ACEResurrectProcess i options F ACEResurrectProcess options F re generate the GAP iostream of the ith or default interactive ACE process started by ACEStart see 6 1 1
162. p generator apdefn 1 and the remainder occurred during applications of the coset numbers to the relators rddefn 13 For more details on the meanings of the variables you will need to read the C code comments Now let us display all 12 lines of the coset table with coset representatives gap gt ACEDisplayCosetTable 12 I CO a 12 r 13 h 1 n 13 c 0 00 1 coset b B a order rep ve I Sa a a a a 1 1 3 2 2 1 2 1 3 1 3 B I 3 2 1 4 3 b I 4 8 5 3 5 ba 1 5 4 8 6 2 baB 1 6 9 7 5 5 baBa 1 7 6 9 8 3 baBaB 1 8 5 4 T 5 bab I 9 7 6 10 5 baBab I 10 12 11 9 3 baBaba I 11 10 12 12 2 baBabaB 1 12 11 10 11 3 baBabab HI eS a Se Note how the pre printout compaction phase now does some work indicated by the upper case CO tag since there were coincidences and hence dead coset numbers Note how b and B head the first two columns since ACE requires that the first two columns be occupied by a generator inverse pair or a pair of involutions The a column is also the A column as a is an involution We now use ACEStandardCosetNumbering to produce a lenlex standard table within ACE but note that this is only lenlex with respect to the ordering b a ofthe generators Then we call ACEDisplayCosetTable again to see it Observe that at both the standardisation and coset table display steps a compaction phase is invoked but on both occasions the lowercase co tag indicates that nothing is done all
163. protect the user more from such ideosyncrasies but we have erred on the side of simplicity in order to make the interface less vulnerable to upgrades of the ACE binary The lesson from the two examples is check the documentation for an option to see how it will be interpreted In general options documented in this chapter as only being no value options can be safely thought of as boolean i e you will get what you expect by assigning true or false whereas strategy no value options should not be thought of as boolean a false assignment will not give you what you might have expected Options that are unknown to the ACE interface functions and not ignored see below that are passed without a value are always passed to the ACE binary as no value options except when the options are ignored the user can over ride this behaviour simply by assigning the intended value Note that it is perfectly safe to allow the ACE binary to be passed unknown options since ACE simply ignores options it doesn t understand issues an error message which is just a warning and is output by GAP unless acenowarnings see 4 11 11 is passed and continues on with any other options passed in exactly the way it would have if the unknown options had not been passed An option is ignored if it is unknown to the ACE interface functions and one of the following is true the global variable ACEIgnoreUnknownDefault is set to false see 4 11 2 or the ace
164. ptions listed there may be used both interactively and non interactively but many are probably best used directly via the ACE standalone Strategy Options for ACE It can be difficult to select appropriate options when presented with a new enumeration The problem is compounded by the fact that no generally applicable rules exist to predict given a presentation which option settings are good To help overcome this problem ACE contains various commands which select particular enumeration strategies One or other of these strategies may work and if not the results may indicate how the options can be varied to obtain a successful enumeration If no strategy option is passed to ACE the default strategy is assumed which starts out presuming that the enumeration will be easy and if it turns out not to be so ACE switches to a strategy designed for more difficult enumerations The other straightforward options for beginning users are easy and hard Thus easy will quickly succeed or fail in the context of the given resources default may succeed quickly or if not will try the hard strategy and hard will run more slowly from the beginning trying to succeed Strategy options are merely options that set a number of the options seen in Chapter 4 all at once they are parsed in exactly the same way as other options order is important It is usual to specify one strategy option and possibly follow it with a number of options defined in Chapter
165. ptions that Modify a Presentation group grpgens Defines the group generators grpgens should be an integer that is the number of generators or a string that is the concatenation of or a list of single lowercase letter group generator names i e it should be in a form suitable for the ACE binary to interpret Shortest abbreviation gr The group generators should normally be input as one of the arguments of an ACE interface function though this option may be useful when ACEStart see 6 1 1 is called with the single argument 0 This option may also be useful for re using an interactive process for a new enumeration rather than using ACEQuit to kill the process and ACEStart to initiate a new process If the generators each have names that as strings are single lowercase letters those same strings are used to represent the same generators by ACE otherwise ACE will represent each generator by an integer numbered sequentially from 1 To convert a GAP list fgens of free group generators into a form suitable for the group option use the construction ToACEGroupGenerators fgens see 6 3 5 It is strongly recommended that users of the group option use this construction Notes Any use of the group command which actually defines generators invalidates any previous enumer ation and stays in effect until the next group command Any words for the group or subgroup must be entered using the nominated generator format and all printout will use
166. r by swapping the first two generators in those cases where IsACEGeneratorsInPreferredOrder gens rels would return false 1 3 Using ACE Directly to Test whether a Coset Enumeration Terminates If you only want to test whether a coset enumeration terminates and don t want to transfer the whole coset table to GAP you can call ACEStats fgens rels sgens options F which calls ACE non interactively to do the coset enumeration the result of which is parsed and returned as a GAP record with fields index the index of the subgroup sgens in fgens rels or 0 if the enumeration does not succeed cputime the total CPU time used as an integer number of cputimeUnits the next field cputimeUnits the units of the cputime field e g 107 2 seconds activecosets the number of currently active i e alive coset numbers see Section 3 5 maxcosets the maximum number of alive coset numbers at any one time in the enumeration see Section 3 5 and totcosets the total number of coset numbers that were defined in the enumeration see Section 3 5 1 gt Q2 gt 10 Chapter 1 The ACE Package Options see Chapters 4 and 5 are used in exactly the same way as for ACECosetTableFromGensAndRel1s discussed in the previous section and the same warnings alluded to previously regarding options see Section 1 7 apply Notes To initiate the coset enumeration the start option see D 3 2 is quietly inserted after the user s
167. relators to include in the subgroup val should be an integer greater than or equal to 1 It is sometimes helpful to include the group relators into the list of the subgroup generators in the sense that they are applied to coset number 1 at the start of an enumeration A value of 0 for this option turns this feature off and the default argument of 1 includes all the relators A positive argument includes the specified number of relators in order The no option affects only the C style procedures mendelsohn Turns on mendelsohn processing Shortest abbreviation mend Mendelsohn style processing during relator scanning closing is turned on by giving this option Off is the default and here relators are scanned only from the start and end of a relator Mendelsohn on means that all different cyclic permutations of a relator are scanned The effect of Mendelsohn style processing is case specific It can mean the difference between success or failure or it can impact the number of coset numbers required or it can have no effect on an enumeration s statistics Note Processing all cyclic permutations of the relators can be very time consuming especially if the presentation is large So all other things being equal the Mendelsohn flag should normally be left off 4 14 ACE Parameter Options Modifying C Style Definitions The next three options are relevant only for making C style definitions see Section 3 1 Making defin
168. result of each enumeration If val is non zero then the presentation and the parameters are echoed at the start of the run and messages on the enumeration s status as it progresses are also printed out The absolute value of val sets the frequency of the progress messages with a negative sign turning hole monitoring on Note that hole monitoring is expensive so don t turn it on unless you really need it Note that ordinarily one will not see these messages non interactively these messages are directed to file ACEData outfile or filename if option aceoutfile filename or ao filename is used and inter actively these messages are simply not displayed However one can change this situation both interactively and non interactively by setting the InfoLevel of InfoACE to 3 via gap gt SetInfoACELevel 3 Then ACE s messages are displayed prepended with I Please refer to Appendix A where the meanings of ACE s output messages are fully discussed 4 19 ACE Parameter Options that give Names to the Group and Subgroup These options may be safely ignored they only give names to the group or subgroup within the ACE output and have no effect on the enumeration itself enumeration string Sets the Group Name to string string must of course be a string Shortest abbreviation enum The ACE binary has a two word synonym for this option Group Name and this is how it is identified in the Run Parameters block o
169. roupGenerators 51 ACEI gnoreUnknownDefault 30 use as debugging tool 27 ACEModes 46 ACEOptionData 28 ACE Option Synonyms 29 ACEOptionSynonyms 29 ACEOrder 55 ACEOrders 55 ACEPackageVersion 15 ACE Parameter Options 32 ACEParameterOptions 32 ACE Parameter Options controlling ACE Output 39 ACE Parameter Options for Deduction Handling 36 ACE Parameter Options for R Style Definitions 35 ACE Parameter Options Modifying C Style Definitions 34 ACE Parameter Options that give Names to the Group and Subgroup 39 ACEParameters 53 ACEPermutationRepresentation 54 ACEPreferredOptionName 29 ACEPrintResearchExample 12 ACEProcessIndex 47 ACEProcessIndices 47 ACEQuit 46 details 46 introduction 10 ACEQuitAll 46 ACERandomCoincidences 59 ACERandomEquivPresentations 50 ACERandomlyApplyCosetCoincidence 59 ACERead 62 ACEReadA1l1 62 ACEReadResearchExample 12 ACEReadUntil 62 ACERecover 57 ACERedo 47 ACERelators 51 ACEResurrectProcess 48 ACEStandardCosetNumbering 57 ACEStart 44 details 44 example 83 106 introduction 10 ACEStats 9 example 79 interactive 57 non interactive 9 ACEStrategyOptions 29 ACEStyle 56 ACESubgroupGenerators 51 ACETraceWord 54 ACETransversal 54 ACEWrite 62 Acknowledgements 15 activecosets 9 23 alive coset number 23 An Example of passing Options 28 B banner suppression 17 break loop 7 47 53 74 C Changes from earlier versions 15 coincidence 10
170. roupGenerators see 6 5 3 to determine the current subgroup generator list Notes ACERandomCoincidences may add subgroup generators even if it failed to determine a nontrivial subgroup with index a multiple of subindex in such a case the original status may be restored by applying ACEDeleteSubgroupGenerators see 6 7 6 with the list returned by ACERandomCoincidences ACERandomCoincidences applies the rc option see D 2 9 of ACE which takes the line that if an enumeration has already obtained a finite index then either swbindez is already a divisor of that finite index or the request is impossible Thus an invocation of ACERandomCoincidences in the case where the coset table is already complete is an error Guru Notes A coset can have many different representatives Consider running ACEStandardCosetNum bering see 6 7 2 before ACERandomCoincidences to canonicise the table and the representatives ACERandomlyApplyCosetCoincidence i controlOptions F ACERandomlyApplyCosetCoincidence controlOptions F for the ith or default interactive ACE process started by ACEStart try to find a larger proper subgroup i e a subgroup of smaller but nontrivial index by repeatedly applying ACECosetCoincidence see 6 7 7 10 gt 60 Chapter 6 Functions for Using ACE Interactively and seeing what happens ACERandomlyApplyCosetCoincidence returns the possibly empty list of new subgroup generators added The starting coset table must
171. rs list must be a list of positive integers This command allows subgroup generators to be deleted from the presentation If the generators are num bered from 1 in the output of say the sr command see D 5 7 then the generators listed in list are deleted list must be a strictly increasing sequence INTERACTIVELY use ACEDeleteSubgroupGenerators see 6 7 6 dr list Deletes relators list must be a list of positive integers This command allows group relators to be deleted from the presentation If the relators are numbered from 1 in the output of say the sr command see D 5 7 then the relators listed in list are deleted list must be a strictly increasing sequence INTERACTIVELY use ACEDeleteRelators see 6 7 5 cc val Makes coset val coincide with coset 1 val should be a positive integer Prints out the representative of coset val and adds it to the subgroup generators i e forces coset val to coincide with coset 1 the subgroup INTERACTIVELY use ACECosetCoincidence see 6 7 7 re val rc val rc val attempts Enforce random coincidences val and attempts must be positive integers This option attempts upto attempts or in the first and second forms 8 times to find nontrivial subgroups with index a multiple of val by repeatedly making random coset numbers coincident with coset 1 and seeing what happens The starting coset table must be non empty but should not be complete For each attempt we repea
172. ry has been tested in all essentially different positions in all relators This testing can either be done directly felsch strategy see 5 1 3 or via relator scanning h1t strategy see 5 1 5 If it is done directly then more than one deduction i e table entry can be waiting to be processed at any one time So the untested deductions are stored in a stack Normally this stack is fairly small but during a collapse it can become very large This command allows the user to specify how deductions should be handled The value val has the following interpretations 0 discard deductions if there is no stack space left 1 as for 0 but purge any redundant coset numbers on the top of the stack at every coincidence 2 as for 0 but purge all redundant coset numbers from the stack at every coincidence 3 discard the entire stack if it overflows and 4 if the stack overflows double the stack size and purge all redundant coset numbers from the stack The default deduction mode is either 0 or 4 depending on the strategy selected see Chapter 5 and it is recommended that you stay with the default If you want to know more details read the well commented C code Notes If deductions are discarded for any reason then a final relator check phase will be run automatically at the end of the enumeration if necessary to check the result dsize val Deduction stack size val should be a non negative integer Shortest abbr
173. s record are the preferred option names and the values assigned to the fields are the lists of synonyms of those option names What makes an option name preferred is somewhat arbitrary in most cases it is simply the shortest of a list of synonyms For a preferred option name optname that has synonyms the complete list of synonyms may be obtained by concatenating optname and ACEOptionSynonyms Coptname e g gap gt Concatenation messages ACEOptionSynonyms messages messages monitor More generally for an arbitrary option name optname its list of synonyms which may be a list of one element may be obtained as the synonyms field of the record returned by ACEOptionData optname see 4 8 2 1 gt Q2 gt 3 gt 4 gt 30 Chapter 4 Options for ACE 4 11 Non ACE binary Options NonACEbin0ptions V is a GAP list of options that have meaning only for the ACE Package interface i e options in KnownACEOp tions that are not ACE binary options each such option is described in detail below Except for the options listed in NonACEbinOptions and those options that are excluded via the aceignore and aceignoreunknown options described below all options that are on the OptionsStack when an ACE interface function is called are passed to the ACE binary Even options that produce the warning message unknown maybe new or bad by virtue of not being a field of KnownACEOptions are passed to the A
174. s and subgroup generators in length increasing order If you do not want this you can switch it off by setting the asis option Notes As well as allowing you to use the presentation as it is given this is useful for forcing definitions to be made in a prespecified order by introducing dummy i e freely trivial subgroup generators Note that the exact form of the presentation can have a significant impact on the enumeration statistics For some fine points of the influence of asis being set on the treatment of involutory generators see the ACE standalone manual ct val cfactor val Number of C style definitions per pass val should be an integer Shortest abbreviation of cfactor is c The absolute value of val sets the number of C style definitions per pass through the enumerator s main loop The sign of val sets the style The possible combinations of the values of ct and rt described below are given in the table of enumeration styles in Section 3 1 rt val rfactor val Number of R style definitions per pass val should be an integer Shortest abbreviation of rfactor is r The absolute value of val sets the number of R style definitions per pass through the enumerator s main loop The sign of val sets the style The possible combinations of the values of ct described above and rt are given in the table of enumeration styles in Section 3 1 4 gt 5 gt 34 Chapter 4 Options for ACE no val The number of group
175. se before using any of the functions provided by this interface to the ACE binary 1 1 Using ACE as a Default for Coset Enumerations After loading ACE see Section 2 2 if you want to use the ACE coset enumerator as a default for all coset enumerations done by GAP which may also get called indirectly you can achieve this by setting the global variable TCENUM to ACETCENUM gap gt TCENUM ACETCENUM This sets the function CosetTableFromGensAndRels see Section 45 5 in the GAP Reference Manual to be the function ACECosetTableFromGensAndRels described in Section 1 2 which then can be called with all the options defined for the ACE interface not just the options max and silent If TCENUM is set to ACETCENUM without any further action the default strategy option of the ACE enumerator will be used see Chapter 5 You can switch back to the coset enumerator built into the GAP library by assigning TCENUM to GAPTCENUM gap gt TCENUM GAPTCENUM 1 gt 6 Chapter 1 The ACE Package 1 2 Using ACE Directly to Generate a Coset Table If on the other hand you do not want to set up ACE globally for your coset enumerations you may call the ACE interface directly which will allow you to decide for yourself for each such call which options you want to use for running ACE Please note the warnings regarding options in Section 1 7 The functions discussed in this and the following section ACECosetTableFromGensAndRels and ACEStats are
176. setTable i ACEDisplayCosetTable ACEDisplayCosetTable i val ACEDisplayCosetTable val ACEDisplayCosetTable i val last ACEDisplayCosetTable val last ACEDisplayCosetTable i val last by ACEDisplayCosetTable val last by Ao yAyAyAyAyy compact and display the possibly incomplete coset table of the ith or default process started by ACEStart val must be an integer and last and by must be positive integers In the first two forms of the command the entire coset table is displayed without orders or coset representatives In the third and fourth forms 13 gt 14 gt 15 gt 16 gt 17 gt 54 Chapter 6 Functions for Using ACE Interactively the absolute value of val is taken to be the last line of the table to be displayed and 1 is taken to be the first in the fifth and sixth forms val is taken to be the first line of the table to be displayed and last is taken to be the number of the last line to be displayed In the last two forms the table is displayed from line val to line last in steps of by If val is negative then the orders modulo the subgroup if available and coset representatives are displayed also Note The coset table displayed will normally only be lenlex standardised if the call to ACEDisplay CosetTable is preceded by ACEStandardCosetNumbering see 6 7 2 The options lenlex see 4 11 4 and semilenlex see 4 11 5 are only executed by ACECosetTable see 1 2 1 The
177. standardisation scheme is the default coset table standardisation scheme of GAP since version 4 3 However semilenlex was the standardisation scheme for versions of GAP up to GAP 4 2 Both schemes are described in detail in Section 3 4 Section 11 Non ACE binary Options 31 5 gt semilenlex Ensures that ACECosetTable and ACECosetTableFromGensAndRels output a coset table that is semilenlex standardised The semilenlex scheme numbers cosets in such a way that their preferred coset representatives in an alphabet consisting of only the user submitted generators are ordered first according to length and then according to a lexical ordering Note Up to GAP 4 2 semilenlex was the default standardisation scheme used by GAP see also 4 11 4 6 gt incomplete Allows the return of an incomplete coset table when a coset enumeration does not finish within preset limits If a coset enumeration that invokes ACECosetTableFromGensAndRels or ACECosetTable does not finish within the preset limits an error is raised by the interface to GAP unless the option silent see 4 11 3 or incomplete has been set in the latter case a partial coset table that is a valid GAP list of lists is returned Each position of the table without a valid coset number entry is filled with a zero If the option silent is also set incomplete prevails Since GAP 4 3 an incomplete table is returned reduced i e with insignificant coset numbers those appearing
178. strategy option itself if it is only a no value option or the strategy option concatenated with any of its integer values as strings otherwise e g felschO and sims9 are strategies and hlt is both a strategy and a strategy option As an exercise the reader might like to try to reproduce the table at the beginning of Chapter 5 using the ACEParameterOptions record Hint you first need to select those fields of the ACEParameterOptions record whose values are records with at least two fields Note Where an ACE Parameter Option has synonyms only the preferred option name see 4 10 1 appears as a field of ACEParameterOptions The complete list of ACE Parameter Options may be obtained by gap gt Concatenation List RecNames ACEParameterO0ptions gt optname gt ACEOptionData optname synonyms asis ct cfactor compaction dmode dsize enumeration fill ffactor hole lookahead loop max mendelsohn messages monitor no path pmode psize rt rfactor subgroup time workspace row We describe the ACE Parameter Options in the Sections 4 13 4 14 4 15 4 16 4 17 4 18 and 4 19 following 4 13 General ACE Parameter Options that Modify the Enumeration Process asis Do not reduce relators Shortest abbreviation as By default ACE freely and cyclically reduces the relators freely reduces the subgroup generators and sorts relator
179. t i fgens rels sgens options ACEStart O options ACEStart 0 fgens rels sgens options ACEStart 0 i options ACEStart 0 i fgens rels sgens options AA yAyAyAyAyy The variables are i a positive integer numbering from 1 that represents indexes an already running interactive ACE process fgens a list of free generators rels a list of words in the generators fgens giving relators for a finitely presented group and sgens a list of subgroup generators again expressed as words in Section 1 Starting and Stopping Interactive ACE Processes 45 the free generators fgens Each of fgens rels and sgens are given in the standard GAP format for finitely presented groups See Chapter 45 of the GAP Reference Manual All forms of ACEStart accept options described in Chapters 4 and 5 and Appendix D which are listed behind a colon in the usual way see 4 10 in the GAP Reference Manual The reader is strongly encouraged to read the introductory sections of Chapter 4 with regard to options The global mechanism via PushOptions of passing options is not recommended for use with the interactive ACE interface functions please ensure the OptionsStack is empty before calling an interactive ACE interface function The return value for all forms of ACEStart is an integer numbering from 1 which represents the running process It is possible to have more than one interactive process running at once The integer return
180. t unless the asis option see 4 13 1 has been set to 1 don t assume unless asis 1 that the new subgroup generators have been appended in user provided order to the previously existing subgroup generator list ACEAddSubgroupGenerators also returns the new subgroup generator list Use ACESubgroupGenerators see 6 5 3 to determine the current subgroup generator list 5 gt vvvvvy Section 7 Steering ACE Interactively 59 ACEDeleteRelators i list F ACEDeleteRelators list F for the ith or default interactive ACE process started by ACEStart delete list from the current relators if list is a list of words in the group generators or those current relators indexed by the integers in list if list is a list of positive integers and automatically invoke ACEStart ACEDeleteRelators also returns the new relator list Use ACERelators see 6 5 2 to determine the current relator list ACEDeleteSubgroupGenerators i list F ACEDeleteSubgroupGenerators list F for the ith or default interactive ACE process started by ACEStart delete list from the current subgroup generators if list is a list of words in the group generators or those current subgroup generators indexed by the integers in list if list is a list of positive integers and automatically invoke ACEStart ACEDeleteSub groupGenerators also returns the new subgroup generator list Use ACESubgroupGenerators see 6 5 3 to determine the current subgroup generator list
181. t is legal for the arguments rels and sgens to be empty lists it is always an error for fgens to be empty e g gap gt ACEStats 0 0 Error fgens arg 1 must be a non empty list of group generators called from CALL_ACE ACEStats arg 1 arg 2 arg 3 called from lt function gt lt arguments gt called from read eval loop Entering break read eval print loop type quit to quit to outer loop or type fgens lt val gt return to assign lt val gt to fgens to continue brk gt fgens FreeGeneratorsOfFpGroup FreeGroup a a brk gt return rec index 0 cputime 13 cputimeUnits 10 2 seconds activecosets 499998 maxcosets 499998 totcosets 499998 The example shows that the ACE package does allow you to recover from the break loop However the definition of fgens above is local to the break loop and in any case we shall want two generators for the examples we wish to consider and raise some other points so let us re define fgens and start again gap gt F FreeGroup a b fgens FreeGenerators0fFpGroup F An ACEStats example By default the presentation is not echoed use the echo see 4 11 12 option if you want that Also by default the ACE binary only prints a results message but we won t see that unless we set InfoACE to a level of at least 2 see 1 9 3 gap gt SetInfoACELevel 2 Calling ACEStats with arguments fgens defines
182. tart ACERedo is really intended for the case where additional relators and or subgroup generators have been introduced the current table which may be incomplete or exhibit a finite index is still valid However the new data may allow the enumeration to complete or cause a collapse to a smaller index In some cases ACERedo may not be possible and an error will be raised in this case quit the break loop and try ACEStart which will discard the current table and re start the enumeration 6 3 Interactive ACE Process Utility Functions and Interruption of an Interactive ACE Process ACEProcessIndex i F ACEProcessIndex F With argument i which must be a positive integer ACEProcessIndex returns 2 if it corresponds to an active interactive process or raises an error With no arguments it returns the default active interactive process or returns fail and emits a warning message to Info at InfoACE or InfoWarning level 1 Note Essentially an interactive ACE process i is active if ACEData io i is bound i e we still have some data telling us about it Also see 6 1 1 note ACEProcessIndices Eri returns the list of integer indices of all active interactive ACE processes see 6 3 1 for the meaning of active F js IsACEProcessAlive i F IsACEProcessAlive F return true if the GAP iostream of the ith or default interactive ACE process started by ACEStart is alive i e can still be written to or false
183. te table However the resulting subgroup need not yet be the normal closure of H and in fact we know that it is not So we continue with another call to the function ACEConjugatesForSubgroupNormalClosure gap gt ACEConjugatesForSubgroupNormalClosure i add b 2 xa b 5 b a b 2 gap gt ACEStats i index 2 Now we have the index that we expected Another call to the function ACEConjugatesForSubgroupNor malClosure should not yield any more conjugates We ensure that this is indeed the case and then display the resulting list of subgroup generators gap gt ACEConjugatesForSubgroupNormalClosure i add I ACEConjugatesForSubgroupNormalClosure All traceable conjugates in subgp gap gt ACESubgroupGenerators i a b73 b a b72 b 1 a b74 b 2 a b75 6 8 Primitive ACE Read Write Functions For those familiar with the workings of the ACE standalone we provide primitive read write tools to com municate directly with an interactive ACE process started via ACEStart possibly with argument 0 but this is not essential For the most part it is up to the user to translate the output strings from ACE into a form useful in GAP However after the group generators relators and subgroup generators have been set in the ACE process via ACEWrite invocations of any of ACEGroupGenerators see 6 5 1 ACERelators see 6 5 2 ACESubgroupGenerators see 6 5 3 or ACEParameters see 6 5 10 will establish the corresponding
184. tedly add random coset representatives to the subgroup and redo the enumeration If the table becomes too small the attempt is aborted the original subgroup generators restored and another attempt made If an attempt succeeds then the new set of subgroup generators is retained Guru Notes A coset number can have many different coset representatives Consider running standard before rc to canonicise the table and hence the coset representatives INTERACTIVELY use ACERandomCoincidences see 6 7 8 1 gt 4e 98 Appendix D Other ACE Options D 3 Mode Options mode Prints the possible enumeration modes Shortest abbreviation mo Prints the possible enumeration modes i e which of continu redo or start are possible see D 3 4 D 3 3 and D 3 2 INTERACTIVELY use ACEModes see 6 2 1 begin start Start an enumeration Shortest abbreviation of begin is beg Any existing information in the table is cleared and the enumeration starts from coset 1 i e the subgroup Normally when a non interactive ACE interface function is called the option start see D 3 2 is quietly inserted after all the options provided by the user to initiate a coset enumeration however this is not done if the user herself supplies either the begin or start option INTERACTIVELY use ACEStart see 6 1 1 check redo Redo an extant enumeration using the current parameters As opposed to start see D 3 2 which clears an existing coset
185. ter 5 and possibly modify some of the options by selecting from the options in this chapter It s not illegal to select more than one strategy but it s not sensible as mentioned above the later one prevails 4 6 Interpretation of ACE Options Options may be given a value by an assignment to the name such as time val or be passed without assigning a value in which case GAP treats the option as boolean and sets the option to the value true which is then interpreted by the ACE interface functions Technically speaking the ACE binary itself does not have boolean options though it does have some options which are declared by passing without a value e g the hard strategy option and others that are boolean in the C sense taking on just the values 0 or 1 The behaviour of the ACE interface functions ACECosetTableFromGensAndRels ACEStats ACECosetTable or ACEStart is essentially to restore as much as is possible a behaviour that mimics the ACE standalone a false value is always translated to 0 and true may be translated to any of no value 0 or 1 Any option passed with an assigned value val other than false or true is passed with the value val to the ACE binary Since this may appear confusing let s consider some examples The hard strategy option see 5 1 4 should be passed without a value which in turn is passed to the ACE binary without a value However the ACE interface function cannot distinguish the option hard being pass
186. th false If useboth true SetACEOptions see 6 5 8 is applied to the ith interactive ACE process with each ACEData ioli field for each field options or parameters that is bound and in useList in the order implied by useList If useboth false SetACEOptions is applied with ACEData io i field for only the first field that is bound in useList The current value of the echo option is also preserved no matter what values the user chooses for the use and useboth options Notes Do not use general ACE options with ACEResurrectProcess they will only be superseded by those options recovered from ACEData io i options and or ACEData io i parameters Instead call SetACEOptions first or afterwards When called prior to ACEResurrectProcess SetACEOptions will emit a warning that the stream is dead despite this the ACEData io z options will be updated ACEResurrectProcess does not invoke an ACE mode see Section 6 2 This leaves the user free to use SetACEOptions which does invoke an ACE mode to further modify options afterwards ToACEGroupGenerators fgens F This function produces from a GAP list fgens of free group generators the ACE directive string required by the group see D 2 1 option The group option may be used to define the equivalent of fgens in an ACE process ToACEWords fgens words F This function produces from a GAP list words in free group generators fgens a string that represents those wor
187. th a non existent example name The following ACE examples are available in each case for a subgroup H of a group G the cosets of H in G are enumerated Example G H strategy A5 A_5 Id default A5 C5 A_5 C_5 default C5 fel0 C_5 Id felsch 0 F27 purec F 2 7 C_29 Id purec F27 fel0 F 2 7 C_29 Id felsch 0 F27 feli F 2 7 C_29 Id felsch 1 M12 h1t M_12 Matthieu group Id hlt M12 fel1 M_12 Matthieu group Id felsch 1 SL219 hard SL 2 19 IG H 180 hard perf602p5 PerfectGroup 60 2 5 2 G H 480 default 2p17 fel1 IGI 2717 Id felsch 1 2p17 felia IGI 2717 IG Hl 1 felsch 1 2p17 2p3 feli G 2 17 IG H 2 3 felsch 1 2p17 2p14 feli G 2 17 IG H 2 14 felsch 1 2p17 id fel1 IGI 2717 Id felsch 1 2p18 fel1 IGI 2718 IG H 2 felsch 1 big feli IGI 2718 3 IG H 6 felsch 1 big hard IGI 2718 3 IG HI 6 hard Notes 1 The example first argument of ACEExample is a string each example above is in double quotes to remind you to include them 2 By default ACEExample applies ACEStats to the chosen example You may alter the ACE function used by calling ACEExample with a 2nd argument choose from ACECosetTableFromGensAndRels or equival ently ACECosetTable or ACEStart e g ACEExample A5 ACEStart 3 You may call ACEExample with additional ACE options entered after a colon in the usual way for options e g
188. the coset number its order modulo the subgroup and a representative for each coset number satisfying the criteria of the search Note You may wish to compact ACE s coset table first either explicitly via ACERecover see 6 7 1 or implicitly via any function call that invokes ACE s compaction routine see 6 7 1 note 19 gt ACEOrder i suborder F gt ACEOrder suborder F for the ith or default interactive ACE process started by ACEStart search for coset number s whose coset representatives have order modulo the subgroup a multiple of suborder When suborder is a positive integer ACEOrder returns just one record with fields coset order and rep which are respectively the coset number its order modulo the subgroup and a representative for the first coset number satisfying the criteria of the search or fail if there is no such coset number The value of suborder may also be a negative integer in which case ACEOrder i suborder is equivalent to ACEOrders i suborder suborder or suborder may be zero in which case ACEOrder i O is equivalent to ACEOrders i Note You may wish to compact ACE s coset table first either explicitly via ACERecover see 6 7 1 or implicitly via any function call that invokes ACE s compaction routine see 6 7 1 note 20 gt ACECosetOrderFromRepresentative i cosetrep F gt ACECosetOrderFromRepresentative cosetrep F for the ith or default interactive ACE process
189. the final note in particular and try to recover as much as possible of the previous state from saved values of the process s arguments and parameter options The possible options here are use and useboth which are described in detail below The arguments of the ith interactive ACE process are stored in ACEData io i args a record with fields fgens rels and sgens which are the GAP group generators relators and subgroup generators respectively see Section 1 8 Option information is saved in ACEData io i options when a user uses an interactive ACE interface function with options or uses SetACEQOptions see 6 5 8 Option information is saved in ACEData io i parameters if ACEParameters see 6 5 10 is used to extract from ACE the current values of the ACE parameter options this is generally less reliable unless one of the general ACE modes see Section 6 2 has been run previously By default ACEResurrectProcess recovers parameter option information from ACEData io i options if it is bound or from ACEData io 7 parameters if it is bound otherwise The ACEData io z options record however is first filtered for parameter and strategy options see Sections 4 12 1 and 4 9 and the echo option see 4 11 12 To alter this behaviour the user is provided two options use useList useList may contain one or both of options and parameters By default use options parameters useboth A boolean option By default usebo
190. the record optionsRec is used to update the current options of the ith or default process started by ACEStart Note that since optionsRec is a record each field must have an assigned value in particular no value ACE options should be assigned the value true see Section 4 6 Please don t mix these 10 gt 11 gt 12 gt vvvvvvy Section 5 Interactive Query Functions and an Option Setting Function 53 two forms of SetACEOptions with the previous two forms i e do not pass both a record argument and options since this will lead to options appearing in the wrong order if you want to do this make two separate calls to SetACEOptions e g let s say you have a process like that started by gap gt ACEExample A5 ACEStart then the following demonstrates both usages of SetACEOptions gap gt SetACEQptions rec echo 2 gap gt SetACEQOptions hlt Each of the three commands above generates output for brevity it has not been included Notes When ACECosetTableFromGensAndRels enters a break loop see 1 2 1 local versions of the second form of each of DisplayACEOptions and SetACEOptions become available Even though the names are similar and their function is analogous they are in fact different functions ACEParameters i F ACEParameters F return a record of the current values of the ACE Parameter Options see 4 12 1 of the ith or default process started by ACEStart according to ACE Please note that s
191. these messages The value of table i e the GAP coset table immediately follows the last ACE message I line but both the coset table from ACE and the GAP coset table have been abbreviated A slightly modified version of this example which includes the echo option is available on line via table ACEExample perf602p5 You may wish to peruse the notes in the ACEExample index first however by executing ACEExample Note that the final table output here is lenlex standardised the case since GAP 4 3 with GAP 4 2 the final table was semilenlex standardised gap gt SetInfoACELevel 3 So we can see the progress messages gap gt G PerfectGroup 275 60 2 See previous example gap gt Example where ACE is made the gap gt Standard Coset Enumerator gap gt fgens FreeGeneratorsOfFpGroup G gap gt table ACECosetTableFromGensAndRels gt arguments gt fgens RelatorsOfFpGroup G fgens 1 gt options gt mendelsohn max 800 mess 500 I ACE 3 001 Sun Sep 30 22 10 10 2001 HI SSsSsssssssss sss ssssssssssssssssssssssss I Host information 1 name rigel I I ACE 3 001 Run Parameters I Group Name G I Group Generators abstuvd I Group Relators s 2 t 2 u 2 v 2 d 2 aad b 3 st 2 I uv 2 su 2 sv 2 tu 2 tv 2 Asau Atav Auas Avat Bvbu I dAda dBdb ds 2 dt 2 du 2 dv 2 Bubvu Bsbdvt Btbvuts 1
192. this format A valid set of generators is the minimum information necessary before ACE will attempt an enumeration Guru Notes The columns of the coset table are allocated in the same order as the generators are listed insofar as this is possible given that the first two columns must be a generator inverse pair or a pair of involutions The ordering of the columns can in some cases affect the definition sequence of cosets and impact the statistics of an enumeration relators relators Defines the group relators relators must be a string or list of strings that the ACE binary can interpret as words in the group generators Shortest abbreviation rel The group relators should normally be input as one of the arguments of an ACE interface function but this option may occasionally be useful with interactive processes see D 2 1 If wordList is an empty list the group is free To convert a GAP list rels of relators in the free group generators fgens into a form suitable for the relators option use the construction ToACEWords fgens rels see 6 3 6 generators subgens Defines the subgroup generators subgens must be a string or list of strings that the ACE binary can interpret as words in the group generators Shortest abbreviation gen The subgroup generators should normally be input as one of the arguments of an ACE interface function but this option may occasionally be useful with interactive processes see D 2 1 By default t
193. to get the group generators The run ended with 12 active see Section 3 5 coset numbers a 12 after defining a total number of 15 coset numbers t 15 the definitions occurred at the steps with progress messages tagged by AD coset 1 application definition and SG subgroup generator phase and the 13 tagged by RD R style definition So there must have been 3 coincidences observe that there were 3 progress messages with a CC tag See Appendix A We can dump out the statistics accumulated during the run using ACEDumpStatistics see 6 5 24 which Infos the ACE output of the statistics see D 5 10 at InfoACE level 1 90 Appendix C Finer Points with Examples gap gt ACEDumpStatistics 1 ACE 3 001 Level 0 Statistics I cdcoinc 0 rdcoinc 2 apcoinc 0 rlcoinc 0 clcoinc 0 1 xcoinc 2 xcolsi2 4 qcoinc 3 1 xsavei2 0 si2dup 0 si2new 0 1 xcrep 6 crepred 0 crepwrk 0 xcomp 0 compwrk 0 I xsaved 0 sdmax 0 sdoflow 0 I xapply 1 apdedn 1 apdefn 1 I rildedn 0 cldedn 0 I xrdefn 1 rddedn 5 rddefn 13 rdfill 0 I xcdefn 0 cddproc 0 cdddedn 0 cddedn 0 1 cdgap 0 cdidefn 0 cdidedn 0 cdpdl 0 cdpof 0 1 cdpdead 0 cdpdefn 0 cddefn 0 1 Hosa Se a Ses The statistic qcoinc 3 states what we had already observed namely that there were three coincidences Of these two were primary coincidences rdcoinc 2 Since t 15 there were fourteen non trivial coset number definitions one was during the application of coset 1 to the subgrou
194. tor orderings the 2 bit respectively where 1 means active and 0 means inactive See below for an example The aep option first performs a priming run using the options as they stand In particular the asis and messages options are honoured It then turns asis on and messages off i e sets messages to 0 and generates and tests the requested equivalent presentations The maximum and minimum values attained by m the maximum number of coset numbers defined at any stage and t the total number of coset numbers defined are tracked and each time a new record is found the relators used and the summary result line is printed See Appendix A for a discussion of the statistics m and t To observe these messages either set the InfoLevel of InfoACE to 3 or non interactively you can peruse the ACE output file see 4 11 8 Normally when a non interactive ACE interface function is called the option start see D 3 2 is quietly inserted after all the options provided by the user to initiate a coset enumeration Since the aep option invokes an enumeration the quiet insertion of the start option is neither needed nor done when a non interactive ACE interface function is called with the aep option The order in which the equivalent presentations are generated and tested has no particular significance but note that the presentation as given after the initial priming run is the last presentation to be generated and tested so
195. trategies see Hav91 It will also be necessary to understand some further basic features of the implementation and the corre sponding terminology which we will explain in the sequel Section 1 Enumeration Style 19 3 1 Enumeration Style The first main decision for any coset enumeration is in which sequence to make definitions When a new coset number has to be defined in ACE there are basically three possible methods to choose from One may fill the next empty entry in the coset table by scanning from the left top of the coset table towards the right bottom that is in order row by row This is called C style definition for Coset Table Based definition of coset numbers In fact a procedure needs to follow a method like this to some extent for the proofs that coset enumeration eventually terminates in the case of finite index see Neu82 For an R style definition for Relator Based definition the order in which coset numbers are defined is explicitly prescribed by the order in which rows of the subgroup generator tables and the relator tables are filled by making definitions One may choose definitions from a Preferred Definition Stack In this stack possibilities for definition of coset numbers are stored that will close a certain row of a relator table Using these preferred definitions is sometimes also referred to as a minimal gaps strategy The idea of using these is that by closing a row in a relator table t
196. ts the InfoACE level to the default value 1 Currently information from ACE is directed to Info at four InfoACE levels 1 2 3 and 4 The command gap gt SetInfoACELevel 2 enables the display of the results line of an enumeration from ACE whereas gap gt SetInfoACELevel 3 enables the display of all of the output from ACE including ACE s banner containing the host machine information in particular the progress messages emitted by ACE when the messages option see 4 18 1 is set to a non zero value will be displayed via Info Finally gap gt SetInfoACELevel 4 enables the display of all the input directed to ACE behind a ToACE gt prompt so you can distinguish it from other output The InfoACE level of 4 is really for gurus who are familiar with the ACE standalone 1 gt Section 11 Changes from earlier versions 15 1 10 Acknowledgements Large parts of this manual in particular the description of the options for running ACE are directly copied from the respective descriptions in the manual Ram99 for the standalone version of ACE by Colin Ramsay Most of the examples in the examples directory and accessed via the ACEExample function are direct translations of Colin Ramsay s test in files in the src directory Many thanks to Joachim Neubiiser who not only provided one of the early manual drafts and hence a template for the style of the manual and conceptual hooks for the design of the Package code
197. u atav auas avat Bvbu Bsbvt 1 Bubvu Btbvuts ab 75 I Subgroup Name H I Subgroup Generators a b I Wo 1000000 Max 50 Mess 10 Ti 1 Ho 1 Loop 0 I As 0 Path 0 Row 1 Mend 0 No 21 Look 0 Com 10 I C 0 R 0 Fi 11 PMod 3 PSiz 256 DMod 4 DSiz 1000 1 o oon I SG a 1 r 1 h 1 n 2 1 1 c 0 00 m 1 t 1 I RD a 11 r 1 h 1 n 12 1 2 c 0 00 m 11 t 11 I RD a 21 r 2 h 1 n 22 1 2 c 0 00 m 21 t 21 I CC a 29 r 4 h 1 n 31 1 2 c 0 00 d 0 I CC a 19 r 4 h 1 n 31 1 2 c 0 00 d 0 I CC a 19 r 6 h 1 n 36 1 2 c 0 00 d 0 I INDEX 16 a 16 r 36 h 1 n 36 1 3 c 0 00 m 30 t 35 I CO a 16 r 17 h 1 n 17 c 0 00 1 coset b B a s t u v I Sa etal 1 1 1 1 1 2 3 4 5 1 2 11 14 4 1 6 8 9 1 3 13 15 5 6 1 10 11 I 4 T 5 2 8 10 1 1 5 4 7 3 9 11 7 1 1 6 8 10 7 3 2 12 14 1 7 5 4 6 15 16 5 4 1 8 10 6 8 4 12 2 15 I 9 16 12 10 5 14 15 2 I 10 6 8 9 12 4 3 16 I 11 14 2 11 14 5 16 3 I 12 9 16 15 10 8 6 13 1 13 15 3 13 16 15 14 12 1 14 2 11 16 11 9 13 6 I 15 3 13 12 7 13 9 8 1 16 12 9 14 13 7 11 10 A5 2 74 67 68 Appendix B Examples B 2 Example of Using ACECoset TableFromGensAndRels The following example calls ACE for up to 800 coset numbers max 800 using Mendelsohn style relator processing mendelsohn and sets progress messages to be printed every 500 iterations messages 500 we do SetInfoACELevel 3 so that we may see
198. unction is a no argument function it s there purely to pass options which of course are listed behind a colon with record components syntax Let s continue the Fibonacci example above redoing the last command but with the option max 2 see 4 17 6 so that the coset enumeration has only two coset numbers to play with and hence is bound to fail to complete putting us in a break loop gap gt ACECosetTable fgens rels c max 2 Error no coset table the ACE coset enumeration failed with the result OVERFLOW a 2 r 1 h 1 n 3 1 5 c 0 00 m 2 t 2 called from lt function gt lt arguments gt called from read eval loop Entering break read eval print loop try relaxing any restrictive options e g try the hard strategy or increasing workspace type strategy options for info on strategies type options for ACE for info on options type DisplayACEOptions to see current ACE options type SetACEOptions lt optioni gt lt valuel gt to set lt optioni gt to lt valuel gt etc i e pass options after the in the usual way and then type return to continue Otherwise type quit to quit to outer loop brk gt SetACEOptions max 0 brk gt return ga Fas Es rr a aso gm Ces ea ei ee a Rea Dn pe al Bae el eral ete em ee Pat Te Pts Bots dd PR Observe how the lines after the Entering break read eval print loop announc
199. uring an enumeration and so only provides the odd numbered strategies of Sims ACE s numbering coincides with that of Sims With care it is often possible to duplicate the statistics given in Sim94 for his odd numbered strategies and it is also possible using the interactive facilities to approximate his even numbered strategies Examples and a more detailed exposition of the Sims strategies are given in Section C 2 vvvvvvvy Functions for Using ACE Interactively The user will probably benefit most from interactive use of ACE by setting the InfoLevel of InfoACE to at least 3 see 1 9 3 particularly if she uses the messages option with a non zero value Have you read the various options warnings yet If not please take the time to read Section 1 7 which directs you to various important sections of Chapter 4 We describe in this chapter the functions that manipulate and initiate interactive ACE processes An interactive ACE process is initiated by ACEStart and terminated via ACEQuit these functions are de scribed in Section 6 1 ACEStart also has forms that manipulate an already started interactive ACE process ACEStart always returns a positive integer i which identifies the interactive ACE process that was initiated or manipulated Most functions there is one ACEStart exception that manipulate an already started interactive ACE process have a form where the first argument is the integer 7 returned by the initiating ACEStart
200. valid value e g gap gt KnownACEOptions compaction 3 O0 100 indicates that the option compaction may be abbreviated to com and the known valid values are in the integer range 0 to 100 and gap gt KnownACEOptions ct 2 lt Operation IS_INT gt indicates that there is essentially no abbreviation of ct since its shortest abbreviation is of length 2 and a value of ct is known to be valid if IsInt returns true for that value For user convenience we provide the function 2 gt ACEOptionData optname F which for a string optname representing an ACE option or a guess of one returns a record with the following fields name optname unchanged known true if optname is a valid mixed case abbreviation of a known ACE option and false otherwise fullname the lower case unabbreviated form of optname if the known field is set true or optname in all lower case otherwise synonyms a list of known ACE options synonymous with optname in lowercase unabbreviated form if the known field is set true or a list containing just optname in all lower case otherwise abbrev the shortest lowercase abbreviation of optname if the known field is set true or optname in all lower case otherwise For more on synonyms of ACE options see 4 10 1 3 4 gt 5 gt 6 gt 1 gt 1 gt Section 10 ACE Option Synonyms 29 The function ACEOptionData provides the user with all the query facility she should ever need
201. ve ACE process Finally if ACEIgnoreUnknownDefault false see 4 11 2 there will be situations where an ACE interface function needs to be told explicitly to ignore options passed down recursively to it from calling functions For this purpose we have provided the options aceignore see 4 11 9 and aceignoreunknown see 4 11 10 4 3 Abbreviations and mixed case for ACE Options Except for limitations imposed by GAP e g clashes with GAP keywords and blank spaces not allowed in keywords the options of the ACE interface are the same as for the binary so for example the options can appear in upper or lower case or indeed mixed case and most may be abbreviated Below we only list the options in all lower case and in their longest form where abbreviation is possible we give the shortest abbreviation in the option s description e g for the mendelsohn option we state that its shortest abbreviation is mend which means mende mendel etc and indeed Mend and MeND are all valid abbreviations of that option Some options have synonyms e g cfactor is an alternative for ct The complete list of ACE options known to the ACE interface functions their abbreviations and the values that they are known to take may be gleaned from the KnownACEOptions record see Section 4 8 Options for the ACE interface functions ACECosetTableFromGensAndRels ACECosetTable ACEStats and ACEStart see Chapter 6 comprise the few non ACE binary options silent acei
202. was built with the statistics package which it is by default Use ACEBinaryVersion see 6 5 25 to check for the inclusion of the statistics package See the enum c source file for the meaning of the variables ACEBinaryVersion i F ACEBinaryVersion F for the ith or default process started by ACEStart print via Info at InfoACE level 1 version details of the ACE binary you are currently running including what compiler flags were set when the executable was built and also returns the version number of the binary as a string Essentially the information obtained is what is obtained via ACE s options option see D 5 5 and the returned value is what is stored in ACEData version see 1 8 1 A typical output illustrating the default build is gap gt ACEBinaryVersion I ACE Binary Version 3 001 I ACE 3 001 executable built 1 Mon Aug 20 20 10 07 CEST 2001 I Level O options 1 statistics package on 1 coinc processing messages on 1 dedn processing messages on I Level 1 options 1 workspace multipliers decimal I Level 2 options 1 host info on 3 001 Notes The ACE binary s banner may also appear in the output if it has not already appeared Unlike other ACE interface functions the information obtained via ACEBinaryVersion is absolutely independent 1 gt Section 7 Steering ACE Interactively 57 of any enumeration For this reason we make it permissible to run ACEBinaryVersio
203. x standard table with GAP 4 2 it was a semilenlex standard table gap gt ACECosetTable Interactive version of ACECosetTableFromGensAndRels I CO a 12 r 13 h 1 n 13 c 0 00 1 coset b B a I to 1 1 3 2 2 1 2 1 3 1 1 3 2 1 4 1 4 8 5 3 1 5 4 8 6 1 6 9 7 5 1 7 6 9 8 1 8 5 4 7 I 9 7 6 10 1 10 12 11 9 I 11 10 12 12 I 12 11 10 11 2 1 4 3 7 8 5 6 10 9 12 11 2 1 4 3 7 8 5 6 10 9 12 11 3 1 2 5 6 4 8 9 7 11 12 10 2 3 1 6 4 5 9 7 8 12 10 11 gap gt To terminate the interactive process we do gap gt ACEQuit 1 Again we could have omitted the 1 gap gt If we had more than one interactive process we could have gap gt terminated them all in one go with gap gt ACEQuitAll B 4 Fun with ACEExample First let s see the ACEExample index obtained with no argument with index as argument or with a non existent example as argument Section 4 Fun with ACEExample 71 gap gt ACEExample 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 I 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 I 1 1 1 1 1 gap gt ACEExample Index Table of Contents This table of possible examples is displayed when calling ACEExample with no arguments or with the argument index meant in the sense of list or wi
204. xample example filename F ACEPrintResearchExample example filename output filename F print the essential contents of the file example filename in the res examples directory to the terminal or with two arguments to the file output filename example filename and output filename should be strings ACEPrintResearchExample is provided to make it easy for users to copy and edit the examples for their own purposes 1 7 General Warnings regarding the Use of Options Firstly let us mention and we will remind you later that an ACE strategy is merely a special option of ACE that sets a number of the options described in Chapter 4 all at once The strategy options are discussed in their own chapter Chapter 5 In Section 4 1 we describe the two means provided by GAP by which ACE options may be passed In Section 4 2 we discuss how options left over from previous calculations can upset subsequent calculations and hence to clear the decks in such circumstances why we have provided FlushOptionsStack see 4 2 1 However removing OptionsStack options does not remove the options previously passed to an interactive ACE process Section 4 2 discusses that too Note that the ACE package treatment of options is an enhancement over the general way GAP treats options Firstly the ACE binary allows abbreviations and mixed case of options and so the ACE package does also as much as is possible see 4 3 Secondly since ACE s opt
205. y 7 1 one alternately applies ACEStandardCosetNumbering and ACEContinue progressively increasing the value of max by some value mazstep The general algorithm is provided by the ACEEvenSims function following gap gt ACEEvenSims function fgens rels sgens i maxstart maxstep gt local j gt j ACEStart fgens rels sgens sims i max maxstart gt while ACEStats j index 0 do gt ACEStandardCosetNumbering j gt ACEContinue j max ACEParameters j max maxstep gt od gt return ACEStats j gt end It turns out that one can duplicate the Sims strategy 4 statistics in Table 5 5 3 of Sim94 with i 3 so that i 1 4 mazstart 14 and mazstep 50 gap gt ACEEvenSims r s t r t r 2 1 s r s 2 1 t s t 2 1 gt 3 14 50 rec index 1 cputime 0 cputimeUnits 10 2 seconds activecosets 1 maxcosets 393 totcosets 393 Setting mazstep 60 and leaving the other parameters the same also gives Sims statistics but mazstart 64 with mazstep 80 does better gap gt ACEEvenSims r s t r t r 2 1 s r s 2 1 t s t 2 1 gt 3 64 80 rec index 1 cputime 0 cputimeUnits 10 2 seconds activecosets 1 maxcosets 352 totcosets 352 Even though the lenlex standardisation steps in the above examples produce a significant improvement over the sims 3 statistics this does not happen u
206. ze or no of non redundant deductions retained with DS tag c no of redundant deductions discarded with DS tag Now that we have discussed the various meanings of the statistics it s time to discuss the various types of progress and results messages possible First we describe progress messages Section 2 Results Messages 65 A 1 Progress Messages A progress message and its tag indicates the function just completed by the enumerator In the following table the possible message tags appear in the first column In the action column a y indicates the function is aggregated and counted Every time this count reaches the value of messages a message line is printed and the count is zeroed Those tags flagged with a y are only present if the appropriate option was included when the ACE binary was compiled a default compilation includes the appropriate options so normally read y as y Tags with an n in the action column indicate the function is not counted and cause a message line to be output every time they occur They also cause the action count to be reset tag action meaning AD y coset 1 application definition SG RS phase RD y R style definition RF y row filling definition CG y immediate gap filling definition CC y coincidence processed DD y deduction processed CP y preferred list gap filling definition CD y C style definition Lx n lookahead performed type x co n table compacted co n compactio

ACE - Gap

Contents

Download Pdf Manuals

Related Search

Related Contents