Math Solutions 1995 October/Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso/pc/mac/discrete/doc/preface.tex

Text File | 1993-05-05 | 17.2 KB | 334 lines

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  preface.tex                 GAP documentation           Joachim Neubueser
%%
%A  @(#)$Id: preface.tex,v 3.6 1993/02/19 10:48:42 gap Exp $
%%
%Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
%%
%%  This file contains the preface of the GAP manual.
%%
%H  $Log: preface.tex,v $
%H  Revision 3.6  1993/02/19  10:48:42  gap
%H  adjustments in line length and spelling
%H
%H  Revision 3.5  1993/02/11  11:20:32  martin
%H  changed for 3.2
%H
%H  Revision 3.4  1992/04/30  12:16:36  martin
%H  changed a few sentences to avoid bold non-roman fonts
%H
%H  Revision 3.3  1992/04/06  09:32:52  martin
%H  fixed a very minor typo
%H
%H  Revision 3.2  1992/03/31  13:04:12  martin
%H  fixed several typos
%H
%H  Revision 3.1  1992/03/31  08:22:32  martin
%H  initial revision under RCS
%H
%%
\catcode`\*=12
\chapter*{Preface}
\catcode`\*=13
\markboth{PREFACE}{PREFACE}

{\GAP} stands for *Groups,  Algorithms  and  Programming*.  The name  was
chosen to reflect the  aim of the  system,  which is  introduced in  this
manual.

Until  well into the  eighties  the  interest  of pure mathematicians  in
computational  group theory  was  stirred  by,  but in  most  cases  also
confined to  the  information  that  was  produced  by  group theoretical
software  for  their special research  problems  --  and  hampered by the
uneasy  feeling  that  one  was   using  black  boxes  of  uncontrollable
reliability.  However the last years have seen a rapid spread of interest
in the understanding, design and even implementation of group theoretical
algorithms.  These are gradually becoming accepted both as standard tools
for a working group theoretician,  like certain  methods of proof, and as
worthwhile  objects of study, like  connections between notions expressed
in theorems.

{\GAP} was  started as  an attempt to meet  this  interest.   Therefore a
primary design goal has  been to give its user full access  to algorithms
and the data  structures used  by them, thus  allowing  critical study as
well as  modification of existing methods.  We also intend to relieve the
user from unwanted technical chores and to assist him in the programming,
thus supporting invention and implementation of new algorithms as well as
experimentation with them.

We have tried  to achieve these goals by a design which in addition makes
{\GAP} easily portable, even to computers such as Atari ST and Amiga, and
at the same  time facilitates the maintenance of {\GAP} with  the limited
resources of an academic environment.

While I had felt for some time rather strongly the wish  for such a truly
*open* system for computational group theory, the concrete idea of {\GAP}
was born when, together with a larger group of students, among whom where
Johannes    Meier,   Alice   Niemeyer,   Werner   Nickel    and    Martin
Sch{\accent127o}nert who eventually wrote  the first version of {\GAP}, I
had  my first contact with  the  Maple system at the  EUROCAL meeting  in
Linz/Austria  in  1985.  Maple demonstrated to  us  the  feasibility of a
strong and efficient computer  algebra system built  from a small kernel,
with an  interpreted library of  routines written  in  a  problem-adapted
language.  The discussion of the plan of a system for computational group
theory  organized  in  a  similar  way  started  in  the  fall  of  1985,
programming only in the second half of  1986.  A first version  of {\GAP}
was operational by  the end  of 1986.  The system was  first presented at
the  Oberwolfach meeting  on  computational  group  theory in  May  1988.
Version  2.4  was  the  first  officially to be  given  away from  Aachen
starting in December 1988.  The strong interest in this version, in spite
of its still rather  small collection  of  group theoretical routines, as
well as constructive criticism  by  many colleagues, confirmed our belief
in the general design principles of the system.   Nevertheless over three
years had gone by until in April 1992 version 3.1 was released, which now
in December 1992 is followed by version 3.2.

A main reason  for this  much time and  the fact  that there had not been
intermediate  releases was  that we have  found it  advisable  to make  a
number of changes to basic data structures until with version 3.1 we hope
to have reached a  state where we can  maintain upward compatibility over
further releases,  which are planned to follow much  more frequently.  Of
course the time has also been  used to  extend  the scope  of the methods
implemented in  {\GAP}.   A rough  guess  puts the size  of  the  program
library of version 3.2 at about twelve times the size of that of  version
2.4, while for version 3.1 the factor was about eight.  In spite of  this
growth there are still gaps in what I would like to see in {\GAP}.

The system that you are getting now consists of four parts\:

\begin{enumerate}

\item
A comparatively  small *kernel*, written in  C, which  provides  the user
with\:

\begin{description}

\item[-] automatic dynamical storage management, which the user needn\'t
         bother about in his programming;
\item[-] a set of time-critical basic functions, e.g.  \"arithmetic\"
         operations for integers, finite fields, permutations and words,
         as well as natural operations for lists and records;
\item[-] an interpreter for the {\GAP} language, which belongs  to  the
         Pascal family, but, while allowing additional types  for  group
         theoretical objects, does not require type declarations;
\item[-] a set  of  programming  tools  for  testing,  debugging,  and
         timing algorithms.

\end{description}

\item

A  much  larger  *library*  of  {\GAP}  functions  that  implement  group
theoretical and other algorithms.  Since this is  written entirely in the
{\GAP}  language, in contrast to the situation in older group theoretical
software,  the  {\GAP} language is both  the main implementation language
and the user language of the system.  Therefore the user can as easily as
the original programmers  investigate and vary algorithms of  the library
and add new ones to it, first for his  own and eventually for the benefit
of all {\GAP}  users.   We hope that  moreover  the  structuring  of  the
library using the concept of *domains* and  the techniques used for their
handling  that  have  been   introduced   into  {\GAP}   3.1  by   Martin
Sch{\accent127o}nert will be further helpful in this respect.

\item

A *library of group theoretical data* which already contains e.g.  a list
of primitive groups of Charles Sims,  a list of the  2-groups of order up
to 256 of Eamonn  O\'Brien  and a  large collection  of character  tables
including all of the Cambridge  *Atlas of  Finite Groups*,  but  which we
hope  to extend further with the  help of colleagues  who have undertaken
larger classifications of groups.

\item

The *documentation*.  This is available as a file that can either be used
for on-line  help or be printed out to form this manual.  Some advice for
using this manual  may  be  helpful.  The first  chapter  *About GAP*  is
really an introduction to the use  of the system,  starting  from scratch
and,  for the  beginning,  assuming  neither  much  knowledge about group
theory  nor much versatility  in  using a computer.   Some of  the  later
sections of chapter 1 assume more, however.  For instance section  "About
Character Tables" *About Character Tables* definitely assumes familiarity
with representation theory of finite groups, while in particular sections
"About the Implementation  of  Domains"  to  "About  Defining  New  Group
Elements" address more  advanced users who  want to extend the  system to
meet their special needs.  The further chapters of the manual give then a
full description of the functions presently available in {\GAP}.

\end{enumerate}

The policy for the further development of {\GAP} is to keep the kernel as
small  as  possible,  extending the set of  basic functions  only by very
selected  ones  that  have  proved  to  be  time-critical  and,  wherever
feasible,  of  general  use.   In  the  interest of  the  possibility  of
exchanging functions written in the  {\GAP} language the kernel has to be
maintained in  a  single  place which  in the foreseeable future  will be
Aachen.  On the other hand we hoped from the beginning that the design of
{\GAP}  would  allow the  library to  grow not only by continued work  in
Aachen  but, as does  any  other  part of  mathematics,  by  exchange  of
contributions  from  many sides.   Both  has in fact  happened.   Notable
extensions from version 3.1 to version  3.2, which were announced as  our
plans in the preface of version 3.1 are the following\:

\begin{description}

\item[-] the removal of the restriction of the  degree  of  permutations,
\item[-] extensions of  the  methods for  for  permutation groups,  e.g.,
         for finding the composition factors,
\item[-] extension of the  methods for  finite  presentations,  e.g.,  by
         reduced   Reidemeister-Schreier,   Modified   Todd-Coxeter,  and
         Tietze methods,
\item[-] further tools  for  getting  character  tables,  e.g.,  by   the
         Dixon-Schneider method  working   from    class   multiplication
         coefficients, and for working with character  tables,  e.g,  for
         finding permutation  characters.   Other  extensions  include  a
         package for univariate polynomials over a coefficient ring.

\end{description}

Version 3.2 is the  first  to provide separate packages in the form  of a
{\GAP} *share library* (see chapter 47 for details). At present there are
three such packages, the ANU p-quotient and p-group generation package by
Eamonn  O\'Brien and Mike Newman,  the  (nonperiodic) Nilpotent  Quotient
program of Werner Nickel, and a package for Weyl groups by Meinolf Geck.

Of course the development of {\GAP} will go on. Of our own plans for this
that  were already  mentioned in  the introduction  to version 3.1  there
remain the  removal  of  the present restriction of  the  size of  finite
fields  and  better  means  of working  with the  output of  the subgroup
lattice program.  Further plans for the near future include still further
additions  to the methods for permutation groups,  the start of a package
of tools for matrix groups,  the provision of graphical output through an
X-window interface and a debugger. Again some of these  plans are already
in  some  state of  implementation, but  just  did not make  it  for  the
deadline that we had set for this release.

There are five other points to make on further policy\:

\begin{description}

\item[-]

When we began work on {\GAP} the typical user that we had in mind was the
one wanting  to implement his own algorithmic ideas.  While we  certainly
hope that we  still  serve such  users well it has become  clear from the
experience  of  the last  years that there  are even  more  users  of two
different  species,  on  the  one  hand  the   established  theoretician,
sometimes with little  experience in the use of computers,  who  wants an
easily understandable  tool, on the  other hand the  student, often quite
familiar with computers,  who  wants to  get assistance in  learning  the
theory  by being able to do nontrivial examples.  We  think  that in fact
{\GAP} can well be used by both, but  we realize that for  each a special
introduction would  be desirable.  We apologize that we have not had  the
time yet to write such, however have learned (through  the {\GAP}  forum)
that in a couple of places work on the development of Laboratory  Manuals
for  the  use   of {\GAP}  alongside   with  standard  Algebra  texts  is
undertaken.

\item[-]

When we began work on {\GAP}, we designed it as a system for doing *group
theory*.  It has already turned out that in fact the design of the system
is general enough, and  some of its functions  are also useful, for doing
work in other  neighbouring areas.  For instance Leonard Soicher has used
{\GAP} to develop  a system GRAPE for working  with graphs.  We certainly
enjoy seeing  this  happen,  but  we want to  emphasize that  our primary
interest is the development  of a group theory system and that we  do not
plan to try to  extend it beyond our  abilities into a  general  computer
algebra system.

\item[-]

Rather we hope to provide  tools for linking {\GAP} to other systems that
represent  years of  work  and experience  in  areas such  as commutative
algebra,  or to  very efficient special purpose stand-alone programs.

\item[-]

We invite  you to further extend {\GAP}.   We  are  willing to  make such
extensions available through the same channels  as {\GAP} in the  form of
the above mentioned *share library*.  Of course,  we will do this only if
the  extension  can  be distributed  free  of charge  like  {\GAP}.   The
copyright for such extensions shall remain with you.

\item[-]

Finally  to answer  an often asked question\:\ The {\GAP} language is  in
principle  designed to  be  compilable.   We  may one day  try  writing a
compiler for it, but this is not yet far enough under  way  to  make  any
promise of prediction.

\end{description}

{\GAP} is given  away under the  conditions that have always  been in use
between  mathematicians, i.e.  in particular *completely  in source*  and
*free  of  charge*.  We  hope  that  the  possibility  offered  by modern
technology of  depositing {\GAP} on a number of  computers  to be fetched
from them by 'ftp', will assist us in this policy.  We want to emphasize,
however, two points.  {\GAP} is  *not* public domain software; we want to
maintain  a *copyright* that  in particular forbids  commercialization of
{\GAP}.  Further we ask that use of {\GAP} be quoted in publications like
the use of any  other mathematical work, and  we would be grateful if  we
could keep track of where {\GAP} is implemented.  Therefore we ask you to
notify us if you have got {\GAP}, e.g., by sending a short e-mail message
to  '[e-mail]'.   The simple reason,  on top of our
curiosity, is that  as anybody  else in  an academic  environment we have
from time to time to prove that we are doing meaningful work.

We  have 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 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.

To       subscribe       send       an      e-mail       message       to
'[e-mail]'  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 '[e-mail]'.

'[e-mail]'   also   accepts   the    following
requests. 'help' for a short help on how to  use 'listserv', 'unsubscribe
gap-forum'  to  unsubscribe,  '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.

The reliability of  large systems  of  computer programs is  a well known
general problem and, although over the past year the  record of {\GAP} in
this respect has not been too  bad, of  course  {\GAP} is not exempt from
this problem.  We therefore feel that it is mandatory  that  we, but also
other users, are warned of bugs that  have been encountered in  {\GAP} or
when doubts have arisen.  We  ask all users of {\GAP} to  use  the {\GAP}
forum for issuing such warnings.

{\GAP} was started as a joint Diplom project of four students whose names
have  already been mentioned.  Since  then  over a  dozen finished Diplom
projects  have  contributed to {\GAP} and further  students are presently
extending the library in the course of their work for  the Diplom as well
as other members  of Lehrstuhl  D  and  colleagues from other institutes.
Their individual contributions to the  programs and  to  the  manual  are
documented in the respective files.  To all of them as well as to all who
have helped proofreading and  improving this  manual I want to express my
thanks for their engagement and enthusiasm as well  as to  many  users of
{\GAP}  who have helped us by  pointing out  deficiencies  and suggesting
improvements.    Very    special   thanks    however    go    to   Martin
Sch{\accent127o}nert.  Not only does {\GAP}  owe many of its basic design
features  to  his  profound  knowledge  of  computer  languages  and  the
techniques for their implementation, but in many  long discussions he has
in the name of future users always been the strongest defender of clarity
of the design against my impatience and the temptation for
\"quick and dirty\" solutions.

As with the previous versions we send this version out hoping for further
feedback of  constructive criticism.   Of  course we ask  to  be notified
about  bugs, but  moreover we  shall appreciate  any  suggestion for  the
improvement of the basic system  as  well  as  of  the algorithms  in the
library.  Most  of all,  however, we hope that in spite of such criticism
you will enjoy working with {\GAP}.

Aachen, January 30.,1993, \hfill Joachim Neub{\accent127u}ser.