1 Preface

Sections

Welcome to GAP. This preface serves not only to introduce this manual, ``the GAP Tutorial'', but also as an introduction to the system as a whole, and in particular to version 4 release 3 (or GAP 4.3 for short).

GAP stands for Groups, Algorithms and Programming. The name was chosen to reflect the aim of the system, which is introduced in this tutorial manual. Since that choice, the system has become somewhat broader, and you will also find information about algorithms and programming for other algebraic structures, such as semigroups and algebras.

There are four further manuals in addition to this one: the ``Reference Manual'' containing detailed documentation of the mathematical functionality of GAP; ``Extending GAP'' containing some tutorial material on various aspects of GAP programming; ``Programming in GAP 4'' containing detailed documentation of various aspects of the system of interest mainly to programmers; and ``New Features for Developers'' containing details of some newly introduced features which we may wish to change in a future release and so do not want to include in the main reference manual. Some of the functionality of the system and a number of contributed extensions are provided as ``GAP packages'' and each of these has its own manual. This preface, however, serves as an introduction to the whole system.

Subsequent sections of this preface explain the structure of the system and the arrangements for the attribution of credit for authorship and maintenance of the system; acknowledge those who have made particular contributions to this and previous releases and outline the changes from earlier versions.

1.1 The GAP System

GAP is a free, open and extensible software package for computation in discrete abstract algebra. The terms ``free'' and ``open'' describe the conditions under which the system is distributed -- in brief, it is free of charge (except possibly for the immediate costs of delivering it to you), you are free to pass it on within certain limits, and all of the workings of the system are open for you to examine and change. Details of these conditions can be found in Copyright.

The system is ``extensible'' in that you can write your own programs in the GAP language, and use them in just the same way as the programs which form part of the system (the ``library''). Indeed, we actively support the contribution, refereeing and distribution of extensions to the system, in the form of ``GAP packages''. Further details of this can be found in chapter GAP Packages in the Reference Manual, and on our World Wide Web site.

Development of GAP began at Lehrstuhl D für Mathematik, RWTH-Aachen, under the leadership of Prof. Joachim Neubüser in 1985. Version 2.4 was released in 1988 and version 3.1 in 1992. The final full release of GAP 3, version 3.4, was made in 1994. In 1997, Prof. Neubüser retired, and overall coordination of GAP development, now very much an international effort, was transferred to St Andrews. A complete internal redesign and almost complete rewrite of the system, which was already in progress in Aachen, was completed and following five, increasingly usable, beta-test releases, version 4.1, released July 1999, was the first version of the rewritten system to be released without any restriction for general use. Version 4.2 followed in spring 2000 and, this version, GAP 4.3 is being released in May 2002.

More information on the motivation and development of GAP to date, can be found on our Web pages in a section entitled ``Release history and Prefaces''.

For those readers who have used an earlier version of GAP, an overview of the changes from GAP 4.2, and a brief summary of changes from GAP3 is given in section Changes from Earlier Versions below.

The system that you are getting now consists of a ``core system'' and a number of packages. The core system consists of four main parts.

A kernel, written in C, which provides the user with
- automatic dynamic storage management, which the user needn't bother about in his programming;
- 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;
- an interpreter for the GAP language, an untyped imperative programming language with functions as first class objects and some extra built-in data types such as permutations and finite field elements. The language supports a form of object-oriented programming, similar to that supported by languages like C++ and Java but with some important differences.
- a small set of system functions allowing the GAP programmer to handle files and execute external programs in a uniform way, regardless of the particular operating system in use.
- a set of programming tools for testing, debugging, and timing algorithms.
- a ``read-eval-view'' style user interface.

A much larger library of GAP functions that implement algebraic and other algorithms. Since this is written entirely in the GAP language, 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 own use and eventually for the benefit of all GAP users.

A library of group theoretical data which contains various libraries of groups, including the library of small groups (containing all groups of order at most 2000, except those of order 1024) and others. Large libraries of ordinary and Brauer character tables and Tables of Marks are included as packages.

The documentation. This is available as on-line help, as printable files in various formats and as HTML for viewing with a Web browser.

Also included with the core system are some test files and a few small utilities which we hope you will find useful.

GAP packages are self-contained extensions to the core system. A package contains GAP code and its own documentation and may also contain data files or external programs to which the GAP code provides an interface. These packages may be loaded into GAP using the RequirePackage command, and both the package and its documentation are then available just as if they were parts of the core system. Some packages may be loaded automatically, when GAP is started, if they are present. Some packages, because they depend on external programs, may only be available on the operating systems where those programs are available (usually UNIX). You should note that, while the packages included with this release are the most recent versions ready for release at this time, new packages and new versions may be released at any time and can be easily installed in your copy of GAP.

With GAP 4.3, there are two packages (the library of ordinary and Brauer character tables, and the library of tables of marks) which contain functionality developed from parts of the GAP 4.2 core system. These have been moved into packages for ease of maintenance and to allow new versions to be released independently of new releases of the core system. The library of small groups should also be regarded as a package, although it does not currently use the standard RequirePackage mechanism. Other packages (included in separate archives for download) contain functionality which has never been part of the core system.

1.2 Authorship and Maintenance

Previous versions of GAP have simply included the increasingly long list of all of the authors of the system with no indication as to who contributed what. In GAP 4.3 we have introduced a new concept: modules, to allow us to report the authorship of the system in more detail. A module is a part of GAP which provides identifiable functionality and has reasonably clean interfaces with the rest of the system (usually it consists of separate files). Each module has its own lists of authors and maintainers, which are not necessarily the same. A preliminary list of modules and their attributions appears in this manual. Note that we are still in the process of identifying modules within the system, so large parts of the system do not yet fall into any module. Since also we all collaborate closely in designing, developing and debugging the system, it should not be assumed that the list of modules in this manual represents all of everyone's contribution, or that it lists everyone who made any contribution at all to each module.

All GAP packages are also considered to be modules and have their own authors and maintainers. It should however be noted that some packages provide interfaces between GAP and an external program, a copy of which is included for convenience, and that, in these cases, we do not claim that the module authors or maintainers wrote, or maintain, this external program. Similarly, some modules and packages include large data libraries that may have been computed by many people. We try to make clear in each case what credit is attributable to whom.

We have, for some time, operated a refereeing system for contributed packages, both to ensure the quality of the software we distribute, and to provide recognition for the authors. We now consider this to be a refereeing system for modules, and we would note, in particular that, although it does not use the standard package interface, the library of small groups has been refereed and accepted on exactly the same basis as the accepted packages.

We also include with this distribution, in a separate archive, a number of packages which have not (yet) gone through our refereeing process. Some may be accepted in the future, in other cases the authors have chosen not to submit them. More information can be found on our World Wide Web site, see section Further Information about GAP.

1.3 Acknowledgements

Very many people have worked on, and contributed to, GAP over the years since its inception. On our Web site you will find the prefaces to the previous releases, each of which acknowledges people who have made special contributions to that release. Even so, it is appropriate to mention here Joachim Neubüser whose vision of a free, open and extensible system for computational algebra inspired GAP in the first place, and Martin Schönert, who was the technical architect of GAP 3 and GAP 4.

In the two years since the release of version 4.2, GAP development has become a more and more widely distributed operation, and increasingly dependent on hard voluntary work by developers not solely or mainly employed to work on GAP, nevertheless, the development process has remained constructive and friendly, even when wrangling over difficult technical decisions, or sensitive questions of attribution and credit and I must express my huge gratitude to everyone involved for this.

The list of modules which appears in this manual now gives a partial idea of the contributions of different people, but I should like to mention some people who have made important contributions to the development process over the last two years that do not show up there: Alexander Hulpke has remained a tower of strength, with unparalleled oversight of many parts of the library, despite now having a teaching post; Thomas Breuer continues to develop many areas of the system, and to play a vital role in clarifying our underlying concepts, despite now working in industry; Frank Lübeck and Max Neunhöffer have brought much fresh insight to bear on the design of crucial parts of the system, and also done a lot of the ensuing work; Greg Gamble and Volkmar Felsch have both brought enormous persistence to correcting very many details of the documentation, improving error messages and generally polishing the system; and very many others have contributed ideas, insight and hard work to produce this release. Senior colleagues, especially Joachim Neubüser, Edmund Robertson, and Charlie Wright, continue to provide encouragement support and constructive criticism.

1.4 Changes from Earlier Versions

The main changes between GAP 4.2 and GAP 4.3 are:

Potentially Incompatible Changes

There have been many adjustments to the arithmetic of lists (including matrices and vectors). These include performance enhancements in many areas, and also extended, and more precisely documented, rules for the results of arithmetic operations applied to lists, including rules for the mutability of the results. The main visible consequences of this are that a lot of operations that previously gave errors now give results, but, in a few unusual cases, the mutability status, or even the value, of the results may be different. More specifically:

*
The scope of the arithmetic operations is extended to some objects for which it is currently undefined, or unimplemented.

*
The mutability of the results of unary arithmetic operations such as unary -, multiplication by zero, and raising to the power 0 or -1, applied to immutable lists has changed. See section Arithmetic for Lists for details.

*
The behaviour under multiplication of lists of nesting depth three or more is changed.

Finitely-presented monoids have been added to the system as objects in their own right. Dividing a free monoid by a list of relations now produced a finitely-presented monoid, whereas previously it produced a finitely-presented semigroup.

A number of documented functions which have been renamed, or whose functionality is now unnecessary or better achieved in other ways have been declared ``obsolescent'' and will be removed in GAP 4.4. These functions have been moved to the file obsolete.g in the GAP library. Perhaps the best known of these functions are the permutation group functions with the old Operation names (such as OperationHomomorphism. These all have replacements like ActionHomomorphism with Action names.

These changes are, in some respects, departures from our policy of maintaining upwards compatibility of documented functions between releases. In the first case, we felt that the old behaviour was sufficiently inconsistent, illogical, and impossible to document that we had no alternative but to change it. In the second case the change was necessary to introduce new functionality. The planned and phased removal of a few unnecessary functions or symonyms is needed to avoid becoming buried in ``legacy'' interfaces, but we remain committed to our policy of maintaining upwards compatibility whenever sensibly possible.

Changes to Mathematical Functionality

The performance of several routines has been substantially improved (e.g. File I/O, large degree permutation groups, finite field matrices, matrix groups, double cosets, permutation group homomorphisms, Solvable quotient, Knuth-Bendix)
Many bugs have been fixed. This release thus incorporates the contents of all the bugfixes which were released for GAP 4.2. It also fixes a number of bugs discovered since the last bugfix.
The functionality for finitely presented groups has been improved, including the addition of effective support for homomorphisms for finitely presented groups.
Routines for the calculation of the Schur multiplier and a Schur Cover of finite permutation groups are now available.
An implementation of Dixon's method for computing ordinary representations of groups has been added.
The methods for decomposing a group element as a word in given generators and for computing a presentation of a given group have been substantially enhanced.
More general methods to form group products are available.
Generators for orthogonal groups of odd dimension in characteristic 2 have been added.
Methods for NrConjugacyClasses have been added for many classical groups.
Errors in the (theoretical) classification of irreducible solvable matrix groups have been resolved.
A special representation for univariate rational functions was added.
Straight line program elements have been added.
The built-in MeatAxe now can treat the so-called ``bad case'' well.
The list of Conway polynomials for finite fields has been extended.

Changes to the Data Libraries

The library of transitive permutation groups has been extended from degree 23 to degree 31.
The library of irreducible maximal finite integral matrix groups has been extended from degree 24 to degree 31.
The library of character tables and the library of tables of marks have been moved into packages for easier maintenance and upgrade. Some new tables have been added.

Changes to the System

Limitations on the length of integers and strings that can be read into GAP have been removed, integers can also be read in in hexadecimal format.
The ability to read and write binary strings has been added.
A filename starting with a tilde now refers by default to the home directory.
The online help interface has been greatly improved. Further help viewers have been added (in particular viewers for dvi and pdf files).
The Windows installation has been simplified for the case where you are installing GAP in its standard location.
Utilities for editing GAP files with vim or emacs are provided.
The -K option can be used to limit the amount of workspace used.
New interfaces allow more control of the user interface, for instance colouring the gap> prompt, or modifying break loop behaviour.
A continue statement has been added to the GAP language, analagous to that in C
Numerous unreliable or potentially confusing C constructions reported by various C compilers have been removed. The system now compiles with few or no warnings on all the compilers we could test.

The most important changes between GAP 4.1 and GAP 4.2 were:

A much extended and improved library of small groups as well as associated IdGroup routines.
The primitive groups library has been made more independent of the rest of GAP, some errors were corrected.
New (and often much faster) infrastructure for orbit computation, based on a general ``dictionary'' abstraction.
New functionality for dealing with representations of algebras, and in particular for semisimple Lie algebras.
New functionality for binary relations on arbitrary sets, magmas and semigroups.
Bidirectional streams, allowing an external process to be started and then controlled ``interactively'' by GAP
A prototype implementation of algorithms using general subgroup chains.
Changes in the behaviour of vectors over small finite fields.
A fifth book ``New features for Developers'' has been added to the GAP manual.
Numerous bug fixes and performance improvements

The changes between the final release of GAP 3 (version 3.4.4) and GAP 4 are wide-ranging. The general philosophy of the changes is two-fold. Firstly, many assumptions in the design of GAP 3 revealed its authors' primary interest in group theory, and indeed in finite group theory. Although much of the GAP 4 library is concerned with groups, the basic design now allows extension to other algebraic structures, as witnessed by the inclusion of substantial bodies of algorithms for computation with semigroups and Lie algebras. Secondly, as the scale of the system, and the number of people using and contributing to it has grown, some aspects of the underlying system have proved to be restricting, and these have been improved as part of comprehensive re-engineering of the system. This has included the new method selection system, which underpins the library, and a new, much more flexible, GAP package interface.

Details of these changes can be found in chapter Migrating to GAP 4 of this manual. It is perhaps worth mentioning a few points here.

Firstly, much remains unchanged, from the perspective of the mathematical user:

The syntax of that part of the GAP language that most users need for investigating mathematical problems.
The great majority of function names.
Data libraries and the access to them.

A number of visible aspects have changed:

Some function names that need finer specifications now that there are more structures available in GAP.
The access to information already obtained about a mathematical structure. In GAP 3 such information about a group could be looked up by directly inspecting the group record, whereas in GAP 4 functions must be used to access such information.

Behind the scenes, much has changed:

A new kernel, with improvements in memory management and in the language interpreter, as well as new features such as saving of workspaces and the possibility of compilation of GAP code into C.
A new structure to the library, based upon a new type and method selection system, which is able to support a broader range of algebraic computation and to make the structure of the library simpler and more modular.
New and faster algorithms in many mathematical areas.
Data structures and algorithms for new mathematical objects, such as algebras and semigroups.
A new and more flexible structure for the GAP installation and documentation, which means, for example, that a GAP package and its documentation can be installed and be fully usable without any changes to the GAP system.

A very few features of GAP 3 are not yet available in GAP 4.

Not all of the GAP 3 packages have yet been converted for use with GAP 4 (although several new packages are available only in GAP 4).
The Galois group determination algorithms which were implemented in the GAP 3 library are not present in GAP 4.
The algorithms for the factorization of polynomials over algebraic number fields which were implemented in the GAP 3 library are not present in GAP 4.
The library of crystallographic groups which was present in GAP 3 is now part of a GAP 4 package crystcat.

1.5 Further Information about GAP

Information about GAP is best obtained from the GAP Web pages that you find on:

http://www.gap-system.org

and its mirrors at:

http://www.math.rwth-aachen.de/~GAP and

http://www.ccs.neu.edu/mirrors/GAP

Further mirrors may be announced from time to time. There you will find, amongst other things

directions to the FTP sites from which you can download the current GAP distribution, any bugfixes, all accepted GAP packages, and a selection of other contributions.
the GAP manual and an archive of the gap-forum mailing list, formatted for reading with a Web browser, and indexed for searching.
information about GAP developers, and about the email addresses available for comment, discussion and support.

I would particularly ask you to note five things:

Any bugfixes which may have been made since this release.
The GAP Forum -- an email discussion forum for comments, discussions or questions about GAP. You must subscribe to the list before you can post to it, see the Web page for details.
The email address gap-trouble@dcs.st-and.ac.uk to which you are asked to send any questions or bug reports which do not seem likely to be of interest to the whole GAP Forum. Section If Things Go Wrong in the Reference Manual tells you what to include in a bug report.
The email address gap@dcs.st-and.ac.uk to which we ask you send a brief message when you install GAP.
The correct form of citation of GAP, which we ask you use whenever you publish scientific results obtained using GAP.

It finally remains for me to wish you all pleasure and success in using GAP, and to invite your constructive comment and criticism.

St Andrews May 2002 Steve Linton

[Top] [Up] [Next] [Index]

GAP 4 manual
May 2002