1 PGRelFind: A GAP Example using ACE

For the perfect simple group S = áfgens | rels ñ with subgroup ásgens ñ where each element of the list sgens is a word in the generators fgens, PGRelFind tries to find a third relator such that together with the two order-defining relators of fgens a presentation on three relators is determined, and if successful returns a record with fields fgens := fgens, rels set to the new 3-relator list found, and sgens := sgens. fgens should be a list of two generators of a free group, say [a, b]; rels should contain words in the generators fgens, the first of which should determine that a is an involution, and the second should determine that b is of order p for some prime p. The subgroup ásgens ñ should ideally be a maximal subgroup of áfgens | rels ñ. It turns out that one only needs to test for relators that are the products of an odd number of bi-syllables of form a b ^k, for some integer k in the range 1,¼,p - 1. We will use the term bi-syllabic length to mean the number of bi-syllables of form a b ^k in such a relator. Furthermore, each relator we test can be assumed to have the prefix (which we subsequently call the head) a b a b a b ^-1 if p is 3, or a b otherwise.

Each relator tested is of form head * middle * tail, where each of head, middle, tail is a word of integral bi-syllabic length. Moreover,

--

head is fixed (as mentioned above);

--

all tails of the opposite parity bi-syllabic length up to a maximum prescribed length are pre-computed (since head is generally of odd bi-syllabic length, tails are generally of even bi-syllabic length); and

--

the bi-syllabic length of the middles is always even, starting from an initial minimum middle length and increasing in steps of granularity + 2, where granularity is defined to be the difference of the maximum and minimum bi-syllabic lengths of a tail (see below).

Since the tails in general are not all of the same length, it is possible when a search is successful that the first relator found is not the shortest. Hence searching continues until a relator of shortest length can be guaranteed.

To provide some user control of the algorithm, PGRelFind has a number of options (entered after the arguments and after a colon in the usual way):

 head := head

Redefines head which by default is a*b*a*b*a/b if the order of b is 3, or a*b otherwise, where a and b are as defined above; head must be a word consisting of a*b^k bi-syllables for integers k.

 Nrandom := nOrFunc

Sets the number of middles to be generated for each length of a middle; nOrFunc may be a non-negative integer or a single-argument function that returns a positive integer.

Each middle may be generated sequentially or randomly. If nOrFunc = 0 then middles are generated sequentially (and hence exhaustively), as they are by default. If nOrFunc is a positive integer then, for each bi-syllabic length of a middle, nOrFunc ``random'' middles are generated. If nOrFunc is a single-argument function then for each bi-syllabic length len of a middle, nOrFunc(len) ``random'' middles are generated.

 ACEworkspace := workspace

Sets the option workspace used by ACE to workspace when running the index check of the large subgroup. If the index is right, ACE is set to use 2*workspace to check the index of the cyclic subgroup áb ñ. By default, workspace is set to 10^6, which is too small for many of the doXXX.g files (see below). Of course, groups for which ACE overflows the workspace are indistinguishable from infinite groups, and one can't easily be sure whether a relator wasn't found because the workspace was too small or because there wasn't one to be found.

 Ntails := Ntails

Sets the approximate number of tails generated to Ntails; it is used to set maxTailLength (described next); Ntails must a positive integer. The default behaviour is given by Ntails = 2048.

 maxTailLength := len

Sets the intended maximum bi-syllabic length of a tail to len; len must be a positive integer.

The default behaviour is given by len = LogInt(Ntails, orderb - 1), where orderb is the order of b. The actual maximum bi-syllabic length of a tail may be set 1 less, in order that it has the same parity as the minimum bi-syllabic length of a tail.

 minMiddleLength := len

Sets the minimum bi-syllabic length of a middle (which, by default is 0) to len; len should be a non-negative even integer.

 maxMiddleLength := len

Sets the intended maximum bi-syllabic length of a middle to len; len should be a positive integer.

The default behaviour is given by len = 30. The actual maximum bi-syllabic length of a middle is adjusted downwards by the least amount necessary to ensure that the difference of the minimum and maximum bi-syllabic lengths of a middle is divisible by granularity + 2. (Recall that granularity is the difference of the maximum and minimum bi-syllabic lengths of a tail.)

Please note that the relators tested are saved in the lists ALLRELS and newrels (see ALLRELS).

finds, and returns as a list of 2-element lists, generator pairs of elements for the group G of orders orderx and ordery, where orderx and ordery are positive integers.

finds a new presentation, in terms of the generators newgens, for the simple group S = áfgens | rels ñ, with subgroup generated by sgens; fgens should be a pair of free group generators; rels, sgens and newgens should be lists of words in fgens. Furthermore, newgens should be a list of two words, the first of which should be of even order and the second of odd prime order in the group S. The idea is that, by using Tietze transformations, the variables x and y (see x) are assigned to the words of newgens, which make up the new fgens, and rels and sgens are written in terms of the new fgens, TranslatePresentation returns a record with fields fgens, rels and sgens that are the new values of fgens, and rels and sgens, respectively.

does a number of integrity checks and tries to give an accurate diagnosis if something is wrong, returning true if everything is ``OK'' and false otherwise. It is called whenever ACEReadResearchExample is executed and is not intended for direct usage by users.

is initially set to a record with one field filename whenever ACEReadResearchExample is executed and the value set to that field is the name of the file read by ACEReadResearchExample; other fields are set as the need arises. Essentially, it is used as a temporary variable store when ACEReadResearchExample reads a doXXX.g file.

are initially set to null lists. Each time PGRelFind is executed these each ``third'' relator tested is appended to ALLRELS and each relator that is satisfied by the group defined by the fgens and rels arguments of PGRelFind (see PGRelFind) is appended to newrels. The user should normally reset these lists back to null lists between invocations of PGRelFind.

are the free group F and its two generators a and b, used in the presentations described below.

are the free group newF and its two generators x and y; the record field fgens returned by TranslatePresentation is the list [x, y] (see TranslatePresentation).

contain presentations for the perfect simple groups L₂(8), L₂(16), L₃(3), U₃(3), M₁₁, L₂(32), U₃(4), J₁, L₃(5) and PSp₄(4), respectively. Those with names ending in s contain lists of records (the s is meant to suggest ``plural''), and those with no s are just single records, where each record has the following fields:

 source

a citation giving the source from which the presentation was obtained, where CCN85, CMY79 and CR84 indicate CCN85, CMY79 and CR84, respectively;

 rels

the relators of the group in terms of the generators a and b defined above (see a); and

 sgens

the generators of a large (usually maximal) subgroup of the group, in terms of the generators a and b.

is a record whose fields are the names of the presentation variables of M11, and whose values are the variables, e.g. presentations.L2_16 is the same object as L2_16.

1.3 The doXXX.g files

Corresponding to each group for which presentations are supplied there is a doXXX.g file in the ACE package's res-examples directory which can be read and executed via the command ACEReadResearchExample. There is also ACEPrintResearchExample if you only wish to see the essential commands executed by the corresponding ACEReadResearchExample command. Since these two commands are important for us we repeat there descriptions from the ACE package manual here:

perform Read (see Section Read 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> ACEReadResearchExample("pgrelfind.g");

is equivalent to executing:

gap> Read( Filename(DirectoriesPackageLibrary("ace", "res-examples"),
>                   "pgrelfind.g") );

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.

Each doXXX.g file (other than the generic doGrp.g) has a name that is formed by taking one of the fields of presentations, removing any underscore or s, prepending "do" and appending ".g"; also, each requires that you run

gap> ACEReadResearchExample();

first to define the functions described above. If you forget, never mind ... you will be reminded.

In essence, each doXXX.g file (other than the generic doGrp.g) provides a valid TranslatePresentation and PGRelFind command combination using one of the presentations in the presentations record, for a particular group.

The doGrp.g file provides a way of choosing any presentation in the presentations record, not just the particular ones used by the other doXXX.g files.

Many of the outputs are fairly lengthy and you may wish to use LogTo (see LogTo) in order to peruse the output at leisure, later. Also, for many of the larger groups one needs to be able to set ACEworkspace larger than 10^6, but how large? The investigation showing that L₃(5) has deficiency 0 was run on an SGI Origin 2000 with 6.4 Gb of RAM and with ACEworkspace set to 10^8, to find a ``third'' relator of 23 bisyllables. It turns out however that one need only set ACEworkspace := 5 * 10^6 to find that relator ... one can be very knowledgeable in hindsight! In the list below we give values for ACEworkspace that will succeed in finding the shortest ``third'' relator that we found, when the method succeeded. (Of course, PGRelFind runs a lot faster if the workspace given to ACE is kept small.)

Recall ACEReadResearchExample expects a filename (i.e. a string), or no argument; here are the filenames of the doXXX.g provided:

 "doGrp.g"

This allows the user to experiment with any of the groups that have data in the presentations record. The user must supply a value for the following option:

  grp := presField

presField must be the name (i.e. a string) of a field in the presentations record (this selects the group to be investigated); and, possibly one or both of the following options:

  n := n

If presField, above, ends in s then the user must supply a positive integer n for n, which indicates that the nth record of presentations.(presField) is desired.

  newgens := wordlist

wordlist must be a list of two words in the generators a and b which are to be the words used for the newgens argument of TranslatePresentation (see TranslatePresentation for the conditions they must satisfy). If newgens is not supplied, it is assumed that TranslatePresentation is not needed, i.e. that the generators a and b are already an involution and an element of odd prime order, respectively, and that PGRelFind may be immediately applied.

The user may also supply PGRelFind options, though unlike grp and newgens, they will not be directly observable in the output. An example using both sets of options is given below.

 "doL28.g"

This provides a nice small example. You may supply any PGRelFind options you wish, and/or you may use the following option which has been specifically designed to help you get acquainted with the PGRelFind options (only the equivalent of the optex options will be explicitly observable in the output).

  optex := val

val may be an integer or a list of integers in the range 1,¼,8. The output of ACEReadResearchExample(); suggests a combination that is 65 lines long. Most of the possible choices for optex give an output of the order of 100 to 200 lines, which isn't too bad if you have say an xterm window with the capacity to scroll back.

 "doL216.g"

As is the case with the remaining doXXX.g files, there are no options other than those for PGRelFind. It is sufficient to set ACEworkspace := 2 * 10^4.

 "doL33.g"

It is sufficient to set ACEworkspace := 2 * 10^4.

 "doU33.g"

Though U₃(3) is known to have deficiency 0, the TranslatePresentation-PGRelFind method does not appear to be able to demonstrate it.

 "doM11.g"

ACEworkspace needs to be set to at least 6 * 10^6.

 "doL232.g"

It is sufficient to set ACEworkspace := 5 * 10^4.

 "doU34.g"

It is sufficient to set ACEworkspace := 5 * 10^4.

 "doJ1.g"

ACEworkspace needs to be set to at least 5 * 10^6.

 "doL35.g"

ACEworkspace needs to be set to at least 5 * 10^6.

 "doPSp44.g"

We were unable to determine whether PSp₄(4) has deficiency 0, via the TranslatePresentation-PGRelFind method.

1.4 Examples

The following example shows that you can use both the options peculiar to the file doGrp.g and the options of PGRelFind when ACEReadResearchExample is called with argument (filename) "doGrp.g".

gap> ACEReadResearchExample("doGrp.g"                       
>                           : grp := "L2_8", newgens := [a^3*b, a^2*b],
>                             head := x*y*x*y*x*y^-1*x*y*x*y);
# IsACEResExampleOK() sets ACEResExample.grp     from options grp, n
#                          ACEResExample.newgens from option  newgens
gap> ACEResExample.G := TranslatePresentation([a, b],
>                                             ACEResExample.grp.rels,
>                                             ACEResExample.grp.sgens,
>                                             ACEResExample.newgens);
#I  there are 4 generators and 6 relators of total length 45
#I  there are 2 generators and 4 relators of total length 55
rec(
  fgens := [ x, y ],
  rels := [ x^2, y^3, y^-1*x*y^-1*x*y^-1*x*y^-1*x*y^-1*x*y^-1*x*y^-1*x, 
      x*y^-1*x*y*x*y^-1*x*y*x*y^-1*x*y*x*y^-1*x*y*x*y*x*y^-1*x*y*x*y^
        -1*x*y*x*y^-1*x*y*x*y^-1*x*y*x*y ],
  sgens := [ x*y^-1 ] )
gap> ACEResExample.Gn := PGRelFind(ACEResExample.G.fgens,
>                                  ACEResExample.G.rels,
>                                  ACEResExample.G.sgens);
GroupOrder=504 SubgroupIndex=72
#bisyllables in head = 5 head: x*y*x*y*x*y^-1*x*y*x*y
Max #bisyllables in tail = 10 (granularity = 10)
#bisyllables in middle = 0
Candidate relator: x*y*x*y*x*y^-1*x*y*x*y*x*y^-1*x*y^-1*x*y*x*y*x*y*x*y^
-1*x*y^-1*x*y^-1*x*y*x*y^-1
 #bisyllables = 15 (#bisyllables in tail = 10) #words tested: 1
ACEStats:
  index=72 cputime=10 ms maxcosets=98 totcosets=121
Large subgroup index OK
ACEStats for cyclic subgroup:
  index=168 cputime=10 ms maxcosets=170 totcosets=232
Cyclic subgroup index OK
Success! ... new relator: 
   x*y*x*y*x*y^-1*x*y*x*y*x*y^-1*x*y^-1*x*y*x*y*x*y*x*y^-1*x*y^-1*x*y^
-1*x*y*x*y^-1
... continuing (there may be a shorter relator).
Candidate relator: x*y*x*y*x*y^-1*x*y*x*y*x*y^-1*x*y*x*y^-1*x*y^-1*x*y^
-1*x*y*x*y*x*y*x*y^-1*x*y^-1
 #bisyllables = 15 (#bisyllables in tail = 10) #words tested: 1
ACEStats:
  index=72 cputime=10 ms maxcosets=102 totcosets=123
Large subgroup index OK
ACEStats for cyclic subgroup:
  index=168 cputime=0 ms maxcosets=170 totcosets=236
Cyclic subgroup index OK
Success! ... new relator: 
   x*y*x*y*x*y^-1*x*y*x*y*x*y^-1*x*y*x*y^-1*x*y^-1*x*y^-1*x*y*x*y*x*y*x*y^
-1*x*y^-1
... continuing (there may be a shorter relator).
Middles of length 0 exhausted.
Relator found of length 15, is shortest.
rec(
  gens := [ x, y ],
  rels := 
   [ x^2, y^3, x*y*x*y*x*y^-1*x*y*x*y*x*y^-1*x*y*x*y^-1*x*y^-1*x*y^-1*x*y*x*y*\
x*y*x*y^-1*x*y^-1 ],
  sgens := [ x*y^-1 ] )
gap>

The following

gap> ACEReadResearchExample("doGrp.g" : grp := "L3_3s", n := 1);

is essentially equivalent to

gap> ACEReadResearchExample("doL33.g");

Observe that the option n is needed because grp selects a list of records (as indicated by the trailing s of "L3_3s"). Also, observe that the newgens option was not used since we already have a presentation where the generators a and b are an involution and of odd prime order, respectively.

1.5 Authors

Alexander Hulpke
Department of Mathematics, Colorado State University
Weber Building, Fort Collins, CO 80523, USA

Greg Gamble and George Havas
Department of Information Technology and Electrical Engineering
The University of Queensland, St. Lucia 4072, Australia

For email addresses refer to the ACE package banner in the section: Defining the functions we use.

[Up] [Index]