From: mhiroshi@tansei.cc.u-tokyo.ac.jp (H. Murakami)
Newsgroups: fj.sci.math,fj.sources.d
Subject: GAP3.1(Patch level 3) introduced.
Date: 5 Oct 92 14:46:55 GMT
Followup-To: fj.sci.math
Distribution: fj
Organization: Hokkaido Univ. However I am subject to tansei for JUNET.

-------------------------------------------------------------------------------
This is public service for the better quality of life.
                         $BJbJbJbJbJbJbJbJbJb(J              $BB<>e(J   $B90(J
PPPPPPPP                   $B3Q(J          $BHt(J
RNBQKBNR                 $B9a7K6d6b6L6b6d7K9a(J   mhiroshi@tansei.cc.u-tokyo.ac.jp

$B%3%s%T%e!<%?!<(J($BM-8B(J)$B72O@MQ%D!<%k(J GAP3.1 $B$N>R2p$G$9(J.

$B%3%s%T%e!<%?!<72O@$ONr;KE*$K$O(J (FORTRAN$B$G:G=i=q$+$l$?(J) CAYLEY
$B$,M-L>$G$9$,(J,$B$=$l$O8=:_M-NA$N%P%$%J%j$N$_G[I[$N>&IJ$H$J$C$F$7(J
$B$^$$$^$7$?(J.

GAP $B$G$I$s$J$3$H$,=PMh$k$+$O(J, $B;f$G(J 700 $B%Z!<%8$b$N%^%K%e%"%k(J
[$BFH$j8@(J:$B$h$/$bL5NA$N%=%U%H$K(J, Knuth$B$N(JTeX$B$N%^%K%e%"%k$b$=$&$@$,(J,
 $B$3$s$J$K=q$1$k$b$N$@$HJr$l$k$[$+$J$$(J.]
$B$K05E]$5$l$k$h$&$K(J, $B$A$g$C$HK;$7$/$b$"$j(J,$B$H$F$b$9$0$K$OGD0.$G$-$^$;$s(J.
[$BFH$j8@(J:$B$=$l$KK\3JE*$J(J $B7W;;72O@$N$O$F$7$b$J$$%P%C%/%0%i%s%I$,$J$$$H(J....]
$B$"$H$G$D$1$?(J, README $B$NCf$N(J, ($B0l;~4|0l@$$rIwsS$7$?(J)$B%k!<%S%C%/%-%e!<%V(J
$B$r$H$C$?NcBj$,$J$+$J$+$*$b$7$m$=$&$G$9(J.

GAP 3.1 + patchlevel 3 $B$O(J $BL5NA$GG[I[$5$l(J, ftp $B$GF~<j$G$-$k$[$+(J,
$BB>?M$KG[$C$F$b$h$$$,(J, PUBLIC DOMAIN $B$G$O$J$$$H$5$l(J, $B>&6H@=IJ$K(J
$BAH$_F~$l$k$3$H$OG'$a$i$l$F$$$^$;$s(J.  $BF~<j$7$?$i(J

        gap@samson.math.rwth-aachen.de

$B$^$G(J, $B;HMQ<T$NL>A0(J, $B=;=jEy$r(J e-mail $B$GAw$k5AL3$,$"$j$^$9(J.

[$BFH$j8@(J:$B$9$k$H3$30$K2?$i$+$NJ}K!$G(J e-mail $B$,Aw$l$J$$$H(J,
 $BJ];}$7$F$O$$$1$J$$$N$G$O$J$$$@$m$&$+(J? $B5?Ld(J??
 $B9qFb$K(J ftp-site $B$r$D$/$k$J$i(J, e-mail $B$NCf7Q%5!<%S%9(J or
 ftp-ident $B$NE>Aw%5!<%S%9$r$7$J$$$H$$$1$J$$$+$bCN$l$J$$(J.??
 ]

$BItJ,E*$K$G$b(J GAP $B$rMQ$$$FF@$i$l$?@.2L$r8x4)(J(publish)$B$9$k$H$-$K$O(J
$B;29MO@J8$r(J reference $B$KMH$2$k$N$HF1MM$K(J, GAP $B$r(J cite $B$9$k$3$H$,(J
$B$N$>$^$l$F$$$^$9(J. ($B$7$+$b$G$-$l$P(J,$B$=$N$h$&$J8x4)J*(J(paper)$B$N>pJs$r(J
$BCN$i$;$FM_$7$$$=$&$G$9(J.)

$B%=!<%9%3!<%IA4It(J, 
        C $B$K$h$k%+!<%M%k(J, 
        GAP $B8@8l$K$h$k%i%$%V%i%j(J,
        LaTeX ($BF|K\8lHG(JLaTeX$B;HMQIT2D(J)$B$K$h$k(J 700 $B%Y!<%8DxEY$N(J $B%^%K%e%"%k(J.
$B$,$"$j$^$9(J.

$B%^%K%e%"%k$O(J $B1Q8lHG(J LaTeX$B$,$J$/$F$b(J dvi $B7A<0$N%U%!%$%k$,$"$k$N$G(J
$B%U%)%s%H$H(J dvi$B$N%W%j%s%?!<%I%i%$%P!<$H%W%j%s%?$,$"$l$P0u:~2DG=$G$9(J.
$B$b$A$m$s(J pre-viewer $B$GFI$`$3$H$b$G$-$k$7(J.

Main memory 4MB, $B$H(J $B%O!<%I%G%#%9%/$,(J GAP $B$N<B9T$KI,MW$@$=$&$G$9(J.
GAP $B%7%9%F%`$NJ];}$K$O(J, 20MB $BDxEY$NNN0h$,(J DISK $B>e$K$$$k$h$&$G$9(J.

$B%=!<%9$K$O(J,$B8=:_%Q%C%A$,(J3$B8D$G$F$$$^$9(J.
$B%^%7%s$K$h$C$F$O(J(endian$B$K$h$j(J), $B:G=i$N#18D$N%Q%C%A$N$_$r$"$F$k$H(J
$B@5>o$KF0:n$7$^$;$s(J.

$B$=$N$[$+(J,
        386      -rw-r--r--  1 ftp        386304 Jun 19 12:01 gapexe.386
        DEC      -rw-r--r--  1 ftp        491520 Apr  9 16:24 gapexe.dec
        NEXT     -rw-r--r--  1 ftp        294912 Apr 23 21:34 gapexe.next
        ATARI ST -rw-r--r--  1 ftp        359915 Apr 13 15:46 gapexe.st
        SUN-3    -rw-r--r--  1 ftp        409600 Apr  9 16:24 gapexe.su3
        SUN-4    -rw-r--r--  1 ftp        450560 Apr  9 16:24 gapexe.su4
$B$J$I$N%3%s%Q%$%k$5$l$?%+!<%M%k$,4{$K$"$k$h$&$G$9(J.
        Apple Macintosh $B$O7W2hCf(J?

UNIX $B$J$i(J, $B4hD%$C$F(J($BBgDq4JC1(J) $B<+J,$G(J Kernel $B$r@8@.$9$k$Y$-$G$9(J.

----------------- $B$"$kF|$N(J ftp $B%5%$%H$N%U%!%$%kFbMF0lMw(J --------------------
total 12399
-rw-r--r--  1 ftp         47130 Sep 28 18:07 README
-rw-r--r--  1 ftp         92160 Apr  9 16:24 compress.tar
-rw-r--r--  1 ftp        887003 Apr  9 16:24 doc3r1.dvi.Z
-rw-r--r--  1 ftp        691219 Apr  9 16:24 doc3r1.tar.Z
-rw-r--r--  1 ftp        538336 Apr  9 16:24 doc3r1.zoo
-rw-r--r--  1 ftp        386304 Jun 19 12:01 gapexe.386
-rw-r--r--  1 ftp        491520 Apr  9 16:24 gapexe.dec
-rw-r--r--  1 ftp        294912 Apr 23 21:34 gapexe.next
-rw-r--r--  1 ftp        359915 Apr 13 15:46 gapexe.st
-rw-r--r--  1 ftp        409600 Apr  9 16:24 gapexe.su3
-rw-r--r--  1 ftp        450560 Apr  9 16:24 gapexe.su4
-rw-r--r--  1 ftp         53263 Apr  9 16:24 grp3r1.tar.Z
-rw-r--r--  1 ftp         33120 Apr  9 16:24 grp3r1.zoo
-rw-r--r--  1 ftp        694359 Apr  9 16:24 lib3r1.tar.Z
-rw-r--r--  1 ftp        497727 Apr  9 16:24 lib3r1.zoo
-rw-r--r--  1 ftp         69827 Apr 30 23:45 patch.tar.Z
-rw-r--r--  1 ftp        611133 Apr  9 16:24 src3r1.tar.Z
-rw-r--r--  1 ftp        425938 Apr  9 16:24 src3r1.zoo
-rw-r--r--  1 ftp       2057721 Apr  9 16:24 tbl3r1.tar.Z
-rw-r--r--  1 ftp       1734332 Apr  9 16:24 tbl3r1.zoo
-rw-r--r--  1 ftp        632756 Apr  9 16:24 two3r1.tar.Z
-rw-r--r--  1 ftp        513829 Apr  9 16:24 two3r1.zoo
-rw-r--r--  1 ftp         45866 Apr 30 23:45 upg3r1p1.dif.Z
-rw-r--r--  1 ftp         56537 Jun  2 12:19 upg3r1p2.dif.Z
-rw-r--r--  1 ftp         12830 Sep 28 18:07 upg3r1p3.dif.Z
-rw-r--r--  1 ftp         12602 Apr  9 16:24 uud.c
-rw-r--r--  1 ftp        238093 Apr  9 16:24 zoo21.tar.Z
-rw-r--r--  1 ftp         67192 Jun  2 12:19 zooexe.386
-rw-r--r--  1 ftp         83275 Apr  9 16:24 zooexe.st

------------------------ ($B>/$78E$$(J)README $B$h$j(J ---------------------------------
Introduction
============

    GAP  is  a  system  for computational  discrete  algebra,  which we  have
    developed  with  particular  emphasis on  computational group theory, but
    which has already proved useful also in  other areas.  The name GAP is an
    acronym for *Groups, Algorithms, and Programming*.  This  (long) document
    announces the availability of GAP version 3 release 1, GAP 3.1 for short.
    It is an *advertisement* for GAP, but not a *commercial*, since  we  give
    GAP away for free.

    This document begins with the section "Announcement", which  contains the
    announcement proper.  The next section "Analyzing Rubik's Cube with  GAP"
    contains  an  extensive example.  This example is  followed by  a general
    discussion  of GAP's  capabilities  in  the section "An Overview of GAP".
    The next sections "How to get GAP" and  "How to install GAP" describe how
    you can get GAP  running on  your  computer.  Then we tell you  about our
    plans  for the future  in  the  section "The Future of  GAP".  The  final
    section "The GAP Forum" introduces the  GAP forum, where interested users
    can discuss GAP related topics by e-mail messages.


Announcement
============
                                                            Il est trop tard,
                                                                  maintenant,
                                                  il sera toujours trop tard.
                                                                Heureusement!
                                                         (A. Camus, La chute)


                 ########            Lehrstuhl D fuer Mathematik
               ###    ####           RWTH Aachen
              ##         ##
             ##          #             #######            #########
            ##                        #      ##          ## #     ##
            ##           #           #       ##             #      ##
            ####        ##           ##       #             #      ##
             #####     ###           ##      ##             ##    ##
               ######### #            #########             #######
                         #                                  #
                        ##           Version 3              #
                       ###           Release 1              #
                      ## #            7 Apr 92              #
                     ##  #
                    ##   #           Johannes Meier, Martin Schoenert
                   ##    #           Alice Niemeyer, Werner Nickel
                  ##     #           Alex Wegner,    Thomas Bischops
                  ###   ##           Juergen Mnich,  Frank Celler
                   ######            Thomas Breuer,  Goetz Pfeiffer
                                     Udo Polis


    Lehrstuhl D f"ur Mathematik,  RWTH Aachen, announces  the availability of
    GAP version 3  release 1,  or GAP   3.1  for  short.   This is  the first
    publicly available  release     of  GAP since   version   2.4, which  was
    distributed since January 1989.


Analyzing Rubik's Cube with GAP
===============================
                                   Ideal Toy Company stated on the package of
                            the original Rubik cube that there were more than
                         three billion possible states the cube could attain.
                            It's analogous to Mac Donald's proudly announcing
                                  that they've sold more than 120 hamburgers.
                                                   (J. A. Paulos, Innumeracy)

    To show you what GAP can do a short example is probably best.  If you are
    not interested in this example skip to the  section "An Overview of GAP".

    For the example we consider the group of transformations of Rubik's magic
    cube.  If we number the faces of this cube as follows

                         +--------------+
                         |  1    2    3 |
                         |  4  top    5 |
                         |  6    7    8 |
          +--------------+--------------+--------------+--------------+
          |  9   10   11 | 17   18   19 | 25   26   27 | 33   34   35 |
          | 12  left  13 | 20 front  21 | 28 right  29 | 36  rear  37 |
          | 14   15   16 | 22   23   24 | 30   31   32 | 38   39   40 |
          +--------------+--------------+--------------+--------------+
                         | 41   42   43 |
                         | 44 bottom 45 |
                         | 46   47   48 |
                         +--------------+

    then the  group is  generated by the following  generators, corresponding
    to the six faces of the cube  (the two  semicolons tell GAP  not to print
    the result, which is identical to the input here).

      gap> cube := Group(
      >   ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19),
      >   ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35),
      >   (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11),
      >   (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24),
      >   (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27),
      >   (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40)
      > );;

    First we want to know the size of this group.

      gap> Size( cube );
      43252003274489856000

    Since this is a little bit unhandy, let us factorize this number.

      gap> Collected( Factors( last ) );
      [ [ 2, 27 ], [ 3, 14 ], [ 5, 3 ], [ 7, 2 ], [ 11, 1 ] ]

    (The result tells us that the size is 2^27 3^14 5^3 7^2 11.)

    Next let us investigate the operation of the group on the 48 points.

      gap> orbits := Orbits( cube, [1..48] );
      [ [ 1, 3, 17, 14, 8, 38, 9, 41, 19, 48, 22, 6, 30, 33, 43, 11, 46,
            40, 24, 27, 25, 35, 16, 32 ],
        [ 2, 5, 12, 7, 36, 10, 47, 4, 28, 45, 34, 13, 29, 44, 20, 42,
            26, 21, 37, 15, 31, 18, 23, 39 ] ]

    The  first orbit contains the points at the corners, the second  those at
    the edges; clearly the group cannot move a point at a corner onto a point
    at an edge.

    So to  investigate the cube group  we first investigate  the operation on
    the corner points.  Note that  the constructed group that describes  this
    operation  will  operate  on the set   [1..24], not  on the  original set
    [1,3,17,14,8,38,9,41,19,48,22,6,30,33,43,11,46,40,24,27,25,35,16,32].

      gap> cube1 := Operation( cube, orbits[1] );
      Group( ( 1, 2, 5,12)( 3, 7,14,21)( 9,16,22,20),
             ( 1, 3, 8,18)( 4, 7,16,23)(11,17,22,12),
             ( 3, 9,19,11)( 5,13, 8,16)(12,21,15,23),
             ( 2, 6,15, 9)( 5,14,10,19)(13,21,20,24),
             ( 1, 4,10,20)( 2, 7,17,24)( 6,14,22,18),
             ( 4,11,13, 6)( 8,15,10,17)(18,23,19,24) )
      gap> Size( cube1 );
      88179840

    Now this group obviously operates transitively, but let us  test  whether
    it is also primitive.

      gap> corners := Blocks( cube1, [1..24] );
      [ [ 1, 7, 22 ], [ 2, 14, 20 ], [ 3, 12, 16 ], [ 4, 17, 18 ],
        [ 5, 9, 21 ], [ 6, 10, 24 ], [ 8, 11, 23 ], [ 13, 15, 19 ] ]

    Those eight  blocks correspond to  the eight corners of  the cube; on the
    one hand the group permutes those and on the  other hand it  permutes the
    three points at each corner cyclically.

    So the obvious thing to do is to  investigate the operation  of the group
    on the eight corners.

      gap> cube1b := Operation( cube1, corners, OnSets );
      Group( (1,2,5,3), (1,3,7,4), (3,5,8,7),
             (2,6,8,5), (1,4,6,2), (4,7,8,6) )
      gap> Size( cube1b );
      40320

    Now a permutation group of degree 8 that has order 40320 must be the full
    symmetric group S(8) on eight points.

    The next thing then  is to investigate  the  kernel  of this operation on
    blocks, i.e.,  the  subgroup of  'cube1'  of those elements that  fix the
    blocks setwise.

      gap> blockhom1 := OperationHomomorphism( cube1, cube1b );;
      gap> Factors( Size( Kernel( blockhom1 ) ) );
      [ 3, 3, 3, 3, 3, 3, 3 ]
      gap> IsElementaryAbelian( Kernel( blockhom1 ) );
      true

    We can  show that the product of  this elementary  abelian group 3^7 with
    the S(8) is semidirect by finding a complement, i.e., a subgroup that has
    trivial intersection with the kernel  and that generates 'cube1' together
    with the kernel.

      gap> cmpl1 := Stabilizer( cube1, [1,2,3,4,5,6,8,13], OnSets );;
      gap> Size( cmpl1 );
      40320
      gap> Size( Intersection( cmpl1, Kernel( blockhom1 ) ) );
      1
      gap> Closure( cmpl1, Kernel( blockhom1 ) ) = cube1;
      true

    There is even a more elegant way to show that 'cmpl1' is a complement.

      gap> IsIsomorphism( OperationHomomorphism( cmpl1, cube1b ) );
      true

    Of course,  theoretically  it is  clear  that 'cmpl1'   must  indeed be a
    complement.

    In  fact we  know that  'cube1' is a  subgroup of index 3 in  the  wreath
    product of a  cyclic 3 with S(8).  This  missing index 3 tells us that we
    do  not have total freedom in turning the  corners.  The  following tests
    show  that whenever we  turn one  corner clockwise we  must  turn another
    corner counterclockwise.

      gap> (1,7,22) in cube1;
      false
      gap> (1,7,22)(2,20,14) in cube1;
      true

    More or less the same things happen when we consider the operation of the
    cube group on the edges.

      gap> cube2 := Operation( cube, orbits[2] );;
      gap> Size( cube2 );
      980995276800
      gap> edges := Blocks( cube2, [1..24] );
      [ [ 1, 11 ], [ 2, 17 ], [ 3, 19 ], [ 4, 22 ], [ 5, 13 ], [ 6, 8 ],
        [ 7, 24 ], [ 9, 18 ], [ 10, 21 ], [ 12, 15 ], [ 14, 20 ], [ 16, 23 ] ]
      gap> cube2b := Operation( cube2, edges, OnSets );;
      gap> Size( cube2b );
      479001600
      gap> blockhom2 := OperationHomomorphism( cube2, cube2b );;
      gap> Factors( Size( Kernel( blockhom2 ) ) );
      [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
      gap> IsElementaryAbelian( Kernel( blockhom2 ) );
      true
      gap> cmpl2 := Stabilizer(cube2,[1,2,3,4,5,6,7,9,10,12,14,16],OnSets);;
      gap> IsIsomorphism( OperationHomomorphism( cmpl2, cube2b ) );
      true

    This time we get a semidirect  product  of a 2^11 with an S(12), namely a
    subgroup of index 2 of the wreath product of a cyclic 2 with S(12).  Here
    the missing index 2 tells us again that we  do not  have total freedom in
    turning the edges.   The following tests show  that whenever  we flip one
    edge we must also flip another edge.

      gap> (1,11) in cube2;
      false
      gap> (1,11)(2,17) in cube2;
      true

    Since 'cube1' and  'cube2' are the groups  describing the actions  on the
    two orbits of 'cube', it is clear  that 'cube'  is a subdirect product of
    those  groups, i.e., a  subgroup of the direct  product.    Comparing the
    sizes  of 'cube1',  'cube2',  and  'cube' we   see that 'cube'  must be a
    subgroup of index 2 in the direct product of those two groups.

      gap> Size( cube );
      43252003274489856000
      gap> Size( cube1 ) * Size( cube2 );
      86504006548979712000

    This final missing index 2 tells us that we cannot operate on corners and
    edges totally independently.  The following  tests show that whenever  we
    exchange a  pair of  corners we must also  exchange a  pair of edges (and
    vice versa).

      gap> (17,19)(11,8)(6,25) in cube;
      false
      gap> (7,28)(18,21) in cube;
      false
      gap> (17,19)(11,8)(6,25)(7,28)(18,21) in cube;
      true

    Finally let us compute the centre of the cube group, i.e.,  the  subgroup
    of those operations that  can be performed  either before  or  after  any
    other operation with the same result.

      gap> Centre( cube );
      Subgroup( cube, [ ( 2,34)( 4,10)( 5,26)( 7,18)(12,37)(13,20)
                        (15,44)(21,28)(23,42)(29,36)(31,45)(39,47) ] )

    We  see that  the centre  contains  one  nontrivial element, namely   the
    operation that flips all 12 edges simultaneously.

    This concludes our  example.  Of course,  GAP  can do much more, and  the
    next section gives an overview   of its capabilities, but   demonstrating
    them all would take too much room.


An Overview of GAP
==================
                                                      Though this be madness,
                                                    yet there is method in't.
                                                     (W. Shakespeare, Hamlet)

    GAP consists of several parts: the kernel, the  library of functions, the
    library of groups and related data, and the documentation.

    The  *kernel* implements an automatic  memory management,  a  PASCAL-like
    programming  language,  also  called  GAP,  with  special  datatypes  for
    computations  in group theory, and an interactive programming environment
    to run programs written in the GAP programming language.

    The automatic  *memory management* allows  programmers  to concentrate on
    implementing the algorithm without  needing  to care about allocation and
    deallocation  of memory.   It   includes   a  garbage   collection   that
    automatically throws away objects that are no longer accessible.

    The GAP programming language supports a number  of datatypes for elements
    of fields.  *Integers* can be  arbitrarily large, and  are implemented in
    such  a  way that operations  with  small   integers are reasonably fast.
    Building on this large-integer  arithmetic GAP supports  *rationals*  and
    elements  from *cyclotomic  fields*.   Also GAP allows  one to  work with
    elements from *finite fields* of size (at present) at most 2^16.

    The special  datatypes  of group elements  are  *permutations* (currently
    operating  on at  most  2^16  points, but we  are  going  to  remove this
    restriction soon), *matrices* over the  rationals, cyclotomic fields, and
    finite fields, *words  in  abstract generators*,  and *words in  solvable
    groups*.

    GAP also contains  a very flexible  *list* datatype.  A list is  simply a
    collection of objects  that allows you to access  the components using an
    integer position.  Lists grow automatically when you add new elements  to
    them.  Lists are used to represent sets,  vectors, and matrices.  A *set*
    is represented   by a  sorted  list without  duplicates.   A   list whose
    elements all lie in a common field  is a *vector*.  A  list of vectors of
    the same length over a common field is a  *matrix*.  Since sets, vectors,
    and matrices are lists, all list operations and functions are applicable.
    You can, for example, find a certain element in a vector with the general
    function  'Position'.   There    are   also   *ranges*,  i.e., lists   of
    consecutive  integers, and  *boolean lists*,  i.e., lists containing only
    'true'  and 'false'.  Vectors, ranges,   and boolean lists  have  special
    internal representations to ensure efficient operations and memory usage.
    For example, a boolean list requires only one bit per element.

    *Records*   in GAP are   similar  to   lists,  except that accessing  the
    components of a record is done using a name instead of an index.  Records
    are used to collect objects of different types,  while lists usually only
    contain elements of one type.  Records are for example  used to represent
    groups and   other  domains; there  is  *no*  group datatype  in  the GAP
    language .  Because of this all information  that GAP knows about a group
    is also accessible to you by simply investigating the record.

    The control structures of GAP are PASCAL-like.  GAP  has *if* statements,
    *while*,  *repeat*,  and  *for* loops.  The for   loop  is  a little  bit
    uncommon in that it always loops over the elements of a  list.  The usual
    semantics can be obtained by looping over the elements of a range.  Using
    those building   blocks you can  write   *functions*.   Functions  can be
    recursive, and are first class objects in the sense that you  can collect
    functions in  lists, pass them as  arguments to other  functions and also
    return them.

    It  is important to  note  that GAP has dynamic  typing instead of static
    typing.  That means that the datatype is a property of the object, not of
    the variable.  This allows you to  write general  functions.  For example
    the generic  function that computes an orbit  can be  used to compute the
    orbit of  an  integer under a permutation group,  the  orbit of a  vector
    under a matrix group, the conjugacy class of  a group element,  and  many
    more.

    The  kernel also implements an *interactive  environment* that allows you
    to use GAP.  This environment supports debugging;  in case of  an error a
    break loop is entered in which you can investigate the problem, and maybe
    correct it  and continue.   You also have online  access  to the  manual,
    though sections  that  contain larger formulas  do not look nice   on the
    screen.

    The *library of  functions*,  simply called   library  in  the following,
    contains implementations  of various group theoretical algorithms written
    in the GAP language.  Because all the group  theoretical functions are in
    this library it is easy for you to look  at  them  to find  out  how they
    work, and change them if they do almost, but not quite, what you want.

    The whole   library is   centered around the   concept  of   domains  and
    categories.  A *domain* is a structured set, e.g., a group is a domain as
    is the ring of Gaussian integers.  Each  domain in GAP  belongs to one or
    more *categories*, which are simply sets of domains, e.g., the set of all
    groups forms a category.  The categories in which a domain lies determine
    the functions that are applicable to this domain and its elements.

    To each  domain belongs a set of  functions,  in a  so called  operations
    record, that are called by dispatchers  like 'Size'.   For example, for a
    permutation group  <G>, '<G>.operations.Size' is a  function implementing
    the Schreier Sims algorithm.  Thus  if  you have any domain  <D>,  simply
    calling 'Size( <D> )' will return the size of the domain <D>, computed by
    an  appropriate function.   Domains *inherit*  such functions from  their
    category,  unless they redefine  them.   For example,  for  a permutation
    group  <G>,  the derived subgroup will  be  computed by the generic group
    function, which computes the normal closure of  the subgroup generated by
    the commutators of the generators.

    Of course the most important category is the category of *groups*.  There
    are  about  100  functions applicable  to  groups.  These include general
    functions  such  as  'Centralizer'  and  'SylowSubgroup', functions  that
    compute series of subgroups such as 'LowerCentralSeries', a function that
    computes the whole lattice of subgroups, functions  that test  predicates
    such  as 'IsSimple',  functions that  are related  to the  operations  of
    groups  such as 'Stabilizer', and many more.  Most of these functions are
    applicable to all  groups,  e.g., permutation groups,  finite  polycyclic
    groups, factor groups, direct products of  arbitrary groups, and even new
    types of groups that you create by simply specifying how the elements are
    multiplied and inverted (actually  it is not quite so simple, but you can
    do it).

    Where  the general  functions that are applicable to  all  groups are not
    efficient enough,  we  have  tried  to  overlay them  by  more  efficient
    functions for special types of groups.  The prime example is the category
    of   *permutation   groups*,    which   overlays   'Size',    'Elements',
    'Centralizer', 'Normalizer', 'SylowSubgroup', and a few more functions by
    functions  that  employ  stabilizer chains  and  backtracking algorithms.
    Also many  of  the  functions  that  deal with operations  of groups  are
    overlayed for permutation groups for the operation of a permutation group
    on integers or lists of integers.

    For   *finitely  presented  groups*   only  some  functions  are  as  yet
    implemented.   They  include  finding  the  index  of a  subgroup  via  a
    Todd-Coxeter coset enumeration,  computing the abelian invariants  of the
    commutator  factor   group,   intersecting  two  subgroups,  finding  the
    normalizer of a subgroup, and  finding all subgroups  of small index.  Of
    course it  is possible  to  go  to a  permutation group operating on  the
    cosets  of a  subgroup and  then  to work  with  this permutation  group.
    Clearly  there  is  still much  to  be  done in  this  area, most notably
    computing presentations for subgroups and simplifying  presentations.  We
    hope to be able to add such functions in the near future.

    For   *finite   polycyclic  groups*   a  special   kind  of  presentation
    corresponding to a  composition  series  is used.   Such  a  presentation
    implies  a  canonical  form  for the  elements  and thus allows efficient
    operations with the elements of such a group.  This  presentation is used
    to make  functions such  as 'Centralizer',  'Normalizer', 'Intersection',
    and  'ConjugacyClasses' very efficient.   GAP's  capabilities for  finite
    polycyclic groups  exceed  those of the computer system SOGOS (which  was
    developed at Lehrstuhl D f"ur Mathematik for the last decade).

    There  is  also  support for  *mappings* and *homomorphisms*.  Since they
    play such a  ubiquitous role in mathematics, it is only natural that they
    should also play an important role  in a system like GAP.   Mappings  and
    homomorphisms  are objects in  their own right in GAP.   You can apply  a
    mapping to an element of its source, multiply mappings (provided that the
    range of the first  is a  subset of  the  source of  the second),  invert
    mappings (even if what you get is  a multi-valued mapping), and perform a
    few more operations.   Important examples are  the  'NaturalHomomorphism'
    onto  a  factor group,  'OperationsHomomorphism'  mapping  a  group  that
    operates  on a set of <n> elements into the symmetric  group on [1..<n>],
    'Embeddings' into  products of groups,  'Projections'  from  products  of
    groups onto the components,  and the  general 'GroupHomomorphismByImages'
    for which you only specify the images of a set of generators.

    The  library contains a  package for handling  character tables of finite
    groups.  This  includes almost  all possibilities of the computer  system
    CAS (which was  developed  at  Lehrstuhl  D  f"ur  Mathematik in the last
    decade), and  many  new functions.  You can  compute character  tables of
    groups, or construct  character  tables  using other  tables, or  do some
    calculations  within  known  character  tables.   You  can, for  example,
    compute a list of candidates for permutation characters.  Of course there
    are  many character tables (at the moment  more than 650 ordinary tables)
    in the data library, including all those in the ATLAS of finite groups.

    For  large integers  we now  also  have a  package for *elementary number
    theory*.  There  are functions in this package to test primality,  factor
    integers of  reasonable  size,  compute the  size phi(<n>)  of the  prime
    residue group modulo an integer <n>, compute roots modulo an integer <n>,
    etc.  Also based on this there  is  a package  to do  calculations in the
    ring of Gaussian integers.

    The library  also includes a package for  *combinatorics*.  This contains
    functions to find all selections of various flavours of the elements of a
    set, e.g., 'Combinations' and 'Tuples', or the number of such selections,
    e.g., 'Binomial'.  Other functions  are related to  partitions of sets or
    integers, e.g., 'PartitionsSet' and 'RestrictedPartitions', or the number
    of   such, e.g., 'NrPartitions'    and  'Bell'.   It  also contains  some
    miscellaneous functions such as 'Fibonacci' and 'Bernoulli'.

    The *data library* at present contains the  primitive permutation  groups
    of degree up to 50 from  C. Sims, the 2-groups of size dividing  256 from
    E. O'Brien and  M. F. Newman, the solvable groups  of size up to 100 from
    M. Hall,  J. K. Senior,  R. Laue,  and  J. Neub"user,  and a  library  of
    character tables including all of the ATLAS.  We plan to extend  the data
    library with more data in the future.


How to get GAP
==============
                                     Ceterum censeo:
                                       Nobody has ever paid a licence fee
                                         for using a proof
                                       that shows Sylow's subgroups to exist.
                                       Nobody should ever pay a licence fee
                                         for using a program
                                       that computes Sylow's subgroups.
                                                               (J. Neub"user)

    GAP  is distributed *free  of  charge*.  You  can obtain it via  'ftp' or
    electronic mail and give it away to your colleagues.  GAP is *not* in the
    public domain, however.  In particular you are not allowed to incorporate
    GAP or parts thereof into a commercial product.

    If you get GAP, we would appreciate it  if you could notify us,  e.g., by
    sending  a  short  e-mail  message  to  'gap@samson.math.rwth-aachen.de',
    containing your  full  name and address,  so that we have a rough idea of
    the number of users.  We also hope that this number will be  large enough
    to convince various  agencies that GAP is a project worthy of (financial)
    support.   If you publish some result that was partly obtained using GAP,
    we would  appreciate  it  if you  would cite GAP,  just as you would cite
    another paper that you  used.  Again  we  would  appreciate if  you could
    inform us about such a paper.

    We  distribute  the *full  source*  for everything, the C  code  for  the
    kernel, the  GAP code for the library, and the LaTeX code for the manual,
    which has at present about 700 pages.  So it should be no problem  to get
    GAP, even if you have a rather uncommon system.  Of course, ports to  non
    UNIX systems may require some work.  We already have a port to  the Atari
    ST.   A port  to IBM PC compatibles with an Intel 80386 or 80486 is under
    way.  We also  hope to provide  a port to the Apple Macintosh in the near
    future.  Note that  about 4  MByte  of main  memory  and  a harddisk  are
    required to run GAP.

    GAP 3.1 can be obtained by anonymous *ftp* from the following servers.

    'samson.math.rwth-aachen.de':
            Lehrstuhl D fur Mathematik, RWTH Aachen, Germany (137.226.152.6).

    'dimacs.rutgers.edu':
            DIMACS, Rutgers, New Brunswick, New Jersey (128.6.75.16).

    'math.ucla.edu':
            Math. Dept., Univ. of California at Los Angeles (128.97.4.254).

    'pell.anu.edu.au':
            Math. Research Section, Australian National Univ. (150.203.15.5).

    'ftp' to the server  *closest* to  you, login as user 'ftp' and give your
    full  e-mail  address  as password.  GAP  is in the  directory 'pub/gap'.
    Remember when you transmit  the files  to set the  file  transfer type to
    *binary image*, otherwise you will only receive unusable  garbage.  Those
    servers will always have the latest version of GAP available.

    GAP can also be obtained via *electronic mail*.  To get  one of the files
    mentioned  below  send a message to 'listserv@samson.math.rwth-aachen.de'
    containing a line  'get GAP <file-name>',  e.g., 'get  GAP src3r1.tar.Z'.
    'listserv' will reply by sending you the file as e-mail message.

    Because most files are  large  binary files they will  be  uuencoded  and
    split into  several parts,  each   at  most 64  kBytes  large.   You  can
    concatenate  the parts  by hand,  removing the mail  header, and then use
    'uudecode' to decode them.  We suggest however that you also get 'uud.c',
    which skips  the  mail headers automatically  and  is also able to fix up
    transmission errors caused by 'EBCDIC' machines.  You can also get single
    parts of a file by sending 'get GAP <file-name> <part-nr>'.

    For users in the United Kingdom with only Janet access, neither 'ftp' nor
    the mail server will work (please do *not*  try to  use the mail server).
    Please contact Derek Holt (e-mail address 'dfh@maths.warwick.ac.uk').  He
    has kindly offered us to distribute GAP in the United Kingdom.

    The 'ftp'  directory and  the 'listserv' archive   contain  the following
    files.  Please check first  which files you  need, to  avoid transferring
    those that you don't need.

    'README':               the file you are currently reading.

    GAP version 3 release 1 itself  comes in several files.   You do not need
    all of those files.  All files are 'compress'-ed 'tar' archives.

    'src3r1.tar.Z':         the *source code* for the GAP  kernel.  You  need
                            this unless you get one of the executables below.
                            This file is about 600 KBytes long.

    'lib3r1.tar.Z':         the *library of functions*.  You need this.  This
                            file is about 700 KBytes long.

    'doc3r1.tar.Z':         the  *documentation*.  Serves  as  LaTeX   source
                            for the printed manual and  online documentation.
                            Contains further installation  information.  This
                            file is about 700 KBytes long.

    'doc3r1.dvi.Z':         the preformatted  documentation.  You  need  this
                            if you do not have a  *big*  TeX.  This  file  is
                            about 900 KByte long.

    'grp3r1.tar.Z':         various *group libraries*.  Contains for  example
                            all primitive permutation  groups  of  degree  at
                            most 50.  This file is about 50 KByte long.

    'two3r1.tar.Z':         the library of *2-group* of  size  at  most  256.
                            This file is about 630 KByte long.

    'tbl3r1.tar.Z':         a library of *character tables* including all  of
                            the ATLAS.  This file is about 2000 KByte long.

    'src3r1.zoo', 'lib3r1.zoo', 'doc3r1.zoo',
    'grp3r1.zoo', 'tbl3r1.zoo', 'two3r1.zoo':
                            'zoo'  archives  containing  *exactly*  the  same
                            files as the 'compress'-ed 'tar' archives  above.
                            The advantage of 'compress'-ed 'tar'  archives is
                            that  'uncompress' and 'tar' are widely available
                            on UNIX systems.  The advantage of 'zoo' archives
                            is  that they are smaller (about  30 percent) and
                            that 'zoo' is more common on PC-s and Atari ST-s.
                            (These files may not be available on all servers)

    We supply executables for some of the more popular machines.  If you have
    one  of those machines it  will be easier for you to get  this executable
    instead  of  compiling  GAP  yourself.   The  following  executables  are
    available (again these files may not be available on all servers)

    'gapexe.st':            executable  for  Atari  ST  (680?0)  running  TOS
                            compiled with the GNU C compiler.  This  file  is
                            about 360 KByte long.

    'gapexe.su3':           executable for SUN 3 (680?0) running SunOS 4.0 or
                            higher compiled with SunOS C.  This file is about
                            410 KByte long.

    'gapexe.su4':           executable for SUN 4 (Sparc) running SunOS 4.0 or
                            higher compiled with SunOS C.  This file is about
                            450 KByte long.

    'gapexe.dec':           executable for  DECstation (MIPS) running  Ultrix
                            4.0 or higher compiled with Ultrix C.  This  file
                            is about 500 KByte long.

    'gapexe.next':          executable  for  the  NeXT (680?0)  running  MACH
                            compiled  with GNU C compiler.  This file fixes a
                            small  problem in  the source, so  you should get
                            this  file   instead  of   compiling  the  source
                            yourself.  This file is about 300 KByte long.

    To incorporate the  latest  changes into  GAP  3.1,  you  also  need  the
    following  *upgrade* files.  Note that all  the above files are  those of
    the base version V3R1.  Thus you *must* apply these upgrades to bring GAP
    to the latest patchlevel.  The upgrade  files are (unified) 'diff' files,
    so the upgrades can  be made automatically with the program 'patch'.  The
    upgrade files contain instructions how this can be done.

    'upg3r1p1.dif.Z':       This file contains the upgrade from base  version
                            (V3R1)  to  version  3  release  1  patchlevel  1
                            (V3R1P1).   In  this  upgrade  nothing  important
                            changed in the kernel,  so you can use the  above
                            executables.  This file is about 45 KBytes long.

    The following support files are also available (and again these files may
    not be available on all servers)

    'compress.tar':         'compress' version 4.1.  You  need  this  program
                            to uncompress  the  compressed  tar  files.  Note
                            however, that almost all UNIX systems  these days
                            already come with an executable 'compress'.  This
                            file is about 90 KByte long.

    'patch.tar.Z':          Larry  Wall's  'patch'  program  version  2.0.2.0
                            (patchlevel 12u4).  This program  can  be used to
                            automatically  apply upgrades.   Note  that older
                            versions  of 'patch' are *not* able to understand
                            the  unified 'diff'  format  used  in the upgrade
                            files.  This file is about 70 KByte long.

    'uud.c':                'uud' version 3.4.  'uud' is much better than the
                            'uudecode' that comes  with  most  UNIX  systems.
                            This file is about 12 KByte long.

    'zoo21.tar.Z':          Rahul Dhesi's  'zoo' archiver  version  2.1.  You
                            need this  to  unpack  the  *zoo-archives*.  Note
                            that the widespread version 2.01 will *not* work.
                            This file is about 250 KByte long.

    'zooexe.st':            Executable of 'zoo' for the Atari ST.  This  file
                            is about 80 KByte long.


How to install GAP
==================

    The file  'install.tex' in 'doc3r1.tar.Z' contains extensive installation
    instructions.  If however, you are one of those  who never  read manuals,
    here is a quick installation guide.

    Make a directory for GAP,  e.g., '~/gap/'  or  '/usr/local/lib/gap/'.

    Unpack the source  archive  'src3r1.tar.Z' into the subdirectory  'src/';
    unpack the library archive  'lib3r1.tar.Z' into the subdirectory  'lib/';
    unpack the documentation    'doc3r1.tar.Z' into the subdirectory  'doc/'.

    If you have obtained the  optional groups and  character tables libraries
    'grp3r1.tar.Z',  'tbl3r1.tar.Z',  and  'two3r1.tar.Z', unpack  them  into
    the subdirectories 'grp/', 'tbl/', and 'two/'.

    Change into 'src/' and execute 'make' to  see a list of possible targets;
    select a target, if in doubt use 'bsd' or 'usg', and make the kernel.

    In an appropriate directory, e.g., '~/bin/' or  '/usr/local/bin/', create
    a shell script that executes the GAP kernel.  This should look like

       exec <gap-directory>/src/gap  -m 4m  -l <gap-directory>/lib/  $*

    The option '-m' specifies the amount  of initial memory; the  option '-l'
    specifies where to find the library, if you get it wrong GAP complains

       gap: hmm, I cannot find 'lib/init.g', maybe use option '-l <libname>'?

    Change into 'doc/' and make the printed manual with the commands

       latex manual;  latex manual;  lp -dvi manual.dvi

    or something similar, according to your local custom for using LaTeX.

    Try something in GAP,  e.g., the following exercises GAP quite a bit

       gap> m11 := Group( (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6) );;
       gap> Number( ConjugacyClasses( m11 ) );

    The result should be 10.


The Future of GAP
=================
                                                 See ye not all these things?
                                                       Verily I say unto you,
                                                 there shall not be left here
                                                      one stone upon another,
                                               that shall not be thrown down.
                                                               (Matthew 24:2)

    Clearly  GAP  will  contain  bugs,  as any  system of  this size,  though
    currently we know none.  Also  there are  things  that we feel are  still
    missing, and that we would like to include into GAP.  We will continue to
    improve and extend GAP.  We will release new versions quite regulary now,
    about three or four upgrades a year are planned.

    We are committed  however,  to staying  upward compatible  from now on in
    future releases.   That means  that  everything  that works now will also
    work in those future releases.   This is different from the quite radical
    step from GAP 2.4 to GAP 3.1, in which almost everything was changed.

    Of course, we have ideas about what we want to have in future versions of
    GAP.   However  we   are  also   looking  forward  to  your  comments  or
    suggestions.


The GAP Forum
=============

    We have also established a  GAP forum, where interested users can discuss
    GAP related topics by e-mail.  In particular this  forum is for questions
    about GAP, general comments, bug  reports, and maybe bug  fixes.  We, the
    developers  of  GAP,  will  read  this  forum  and  answer questions  and
    comments, and distribute bug fixes.  Of course others are also invited to
    answer questions,  etc.  We will also announce future  releases of GAP on
    this forum.   So  in order to be informed about bugs and  their  fixes as
    well as about additions to GAP we recommend that you subscribe to the GAP
    forum.

    To  subscribe send  a  message  to  'listserv@samson.math.rwth-aachen.de'
    containing the line 'subscribe gap-forum <your-name>', where  <your-name>
    should be your  full name, not your e-mail address.   You will receive an
    acknowledgement,  and   from  then  on   all  e-mail  messages  sent   to
    'gap-forum@samson.math.rwth-aachen.de'.

    'listserv@samson.math.rwth-aachen.de'   also   accepts    the   following
    requests:  'help' for a short help on how to use 'listserv', 'unsubscribe
    gap-forum' to unsubscribe again,  'recipients gap-forum' to get a list of
    subscribers, and 'statistics gap-forum' to see  how many  e-mail messages
    each subscriber has sent so far.


If you have further questions or comments do not  hesitate to write to me
'Martin.Schoenert@Math.RWTH-Aachen.DE'.

Thank you for your attention,  Martin.

--
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,  +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany