We compare the work actually accomplished and the objectives set out in the work programme by dividing these objectives into six categories and commenting on each. The first four categories A - D refer to scientific achievements of the project, category E refers to the organisational aspects which have been developed through the operation of the network while the final category F refers to the training and mobility aspects which our network has contributed in the Community. Many achievements were innovations which it had not been possible to foresee when the work programme was written. In a number of cases the direction of the work was changed because of new results which had not been previously anticipated. The depth and breadth of the results obtained mean it is impossible to do more than indicate some of them in this report. Wide cooperation between the teams and other European mathematicians made these achievements possible.

GAP provides:

Mathematical capabilities accessible through:

- a large library of functions, containing implementations of various algebraic algorithms.
- separate packages of additional functions for specialized purposes which can be used like library functions,
- data libraries containing large classes of various algebraic objects that are accessible by using GAP commands.

A programming language, also called GAP, which is interpreted and can be compiled. It can be used interactively at the keyboard or to write programs to be saved and then executed. Such programs can easily be modified and rerun. The language features:

- Pascal-like control structures,
- automatic memory management including garbage collection,
- streams,
- flexible list and record data types,
- built-in data types for key algebraic objects,
- automatic method selection building on a mechanism for automatically choosing the highest ranked method for a certain operation, depending on the current state of all its arguments, so that GAP objects representing mathematical objects may gain knowledge about themselves during their lifetime resulting in better methods being chosen later on.

An interactive environment that supports in particular:

- line editing e.g. tab completion,
- break loops for debugging,
- further debugging and profiling facilities for GAP programs,
- online help (i.e. online access to the manuals).

Structure of GAP

GAP has a kernel written in C. It implements

- the GAP language,
- an interactive environment for developing and using GAP programs,
- memory management, and
- fast versions of time critical operations for various data types.

All the rest of the library of functions is written in the GAP language. Packages are mainly written in the GAP language, but some also involve standalones. Some packages provide links to other systems.

The system development almost exactly followed that planned in the work programme.

A1. GAP4.

During the last three years in parallel to the development of mathematical methods and their implementation in the framework of GAP3, a very innovative step of system design has been taken with development of GAP4.

For many of the main computational problems different computing methods have been found that often depend on the way a group is given or on already available knowledge about the group under investigation. While still allowing the GAP user access to all methods we aimed to introduce in GAP4 a mechanism to allow the system make a good choice.

Instead of having a dichotomy of structures implemented in the kernel and structures that are modelled in the GAP library using records we aimed to have in GAP4 less distinction to make it easier to model new mathematical structures first at the level of the GAP language and then to transfer time-critical functions to the kernel.

We also aimed to produce new methods for storage management and other kernel functions in GAP4 to improve the efficiency of the system. The writing of a compiler for the GAP language was another aim to give the user high flexibility in keeping code in GAP source while experimenting with ideas while at the same time compiling time-critical functions.

An alpha release of GAP4 incorporating all the above features is now available to all the teams of our project and some others. A beta release will be made publicly available in May 1997 and, at the same time, we will make the compiler for GAP4 generally available.

A2. Share Packages.

One of the ways that different teams have collaborated in this project has been in producing share packages for GAP. They are not part of the main GAP library of functions but are distributed with GAP under their authors' names. These packages are the end result of mathematical investigations which have produced new mathematical methods, new algorithms and sometimes extremely innovative ideas. These mathematical investigations involve a much larger group of mathematicians within our network than the authors of the packages themselves. Some of the algorithm development which has gone into these packages is discussed in Section B.

Below is a list of the packages produced during the three years of collaboration on the HCM project. We give the authors of the packages and a brief description of the topic. Fuller details are available on the WWW.

A2.1. XGAP, an X windows version of GAP and a Windows 3.11/95 version of XGAP, by Frank Celler and Susanne Keitemeier,

A2.2. ANU Soluble Quotient Algorithm, soluble quotient algorithm for finitely presented groups, by Alice C. Niemeyer.

A2.3. Smash, matrix groups over finite fields, by Derek Holt, Charles Leedham-Green, Eamonn O'Brien, Sarah Rees.

A2.4. Vector Enumeration, linear Todd-Coxeter method, by Steve Linton.

A2.5. Cohomology, cohomological calculations for finite groups, by Derek Holt.

A2.6. GUAVA, coding theory, by J Simonis, Reinald Baart, Jasper Cramwinckel, Eric Minkes, Erik Roijackers.

A2.7. Double Coset Enumerator, variant of the ordinary coset enumeration, by Steve Linton.

A2.8. KBMAG, Knuth-Bendix on monoids and automatic groups, by Derek Holt.

A2.9. Specht, decomposition numbers of Hecke algebras of the symmetric groups and $q$-Schur algebras, by Andrew Mathas, communicated by Herbert Pahlings.

A2.10. AutAG, automorphism groups of finite solvable groups, by Michael Smith, communicated by Charles Wright.

A2.11. XMod, crossed modules and cat1-groups, by Chris Wensley and Murat Alp, communicated by Derek Holt.

A3. Other systems and interaction between systems.

A3.1. Implementation of a graphics surface for GAP.

The XGAP package above provides a graphics interface with X windows and more recently with Windows 95. It was developed in a cooperative effort with expertise from Newcastle and Warwick on Quotpic being used.

A3.2. Extending the GAP-based system GRAPE.

Two new versions of GRAPE (versions 2.2 and 2.3) have been released during the course of the project. The latest version includes programs for classifying partial linear spaces and for determining cliques of a given weight in a vertex-weighted G-graph. These programs have already been put to use to produce new results on partial linear spaces and on experimental designs.

A3.3. Exchange of data between GAP and LIE.

The original plan just to link the existing LIE package to GAP has been superseded by a much more far reaching project to develop in GAP 4 (whose new facilities, created by the Aachen team were prompted not to the least by the necessities of this Eindhoven based project) a system that will be able to handle Lie algebras given either by a presentation, or by generating matrices, or through structure constants. This will then invoke the LIE system for further structural information on classical Lie algebras. This project is close to completion anmd will be released with GAP 4. This LieGAP project is linked to another innovative project of the Eindhoven team namely the ACELA project to develop an 'interactive book on Lie Algebras. See also B11.

A3.4. Quotpic.

Quotpic was developed steadily throughout the project. Features implemented include recognising whether an extension of $M/N$ by $G/M$ splits when $M/N$ is elementary abelian, and $G$ is a finitely presented group with normal subgroups $N < M < G$. This particular calculation is not easy to carry out using other systems. It was used, for example, to answer some specific queries of this nature by J N Bray, a student of R. Curtis in Birmingham. Quotpic now includes a graphics interface to the Plesken soluble quotient algorithm as implemented by H. Bruckner in Aachen B, which is in many ways the most natural and satisfactory interface.

A3.5. SYMMETRICA, MOLGRAPH and DISCRETA.

The systems SYMMETRICA and MOLGRAPH were further developed by the Bayreuth team. The use of SYMMETRICA is of great interest to workers in algebraic combinatorics research in France, Germany, Italy and Austria. Cooperation with these researchers played an important role in the development of SYMMETRICA. A new system DISCRETA, which is devoted to the construction of various structures using a prominent range group theoretic algorithms, was developed. Applications are devoted to Mathematical Chemistry, where especially double coset algorithms are at the heart of the system. Techniques used in the mathematical modelling of chemical information apply the group theoretic routines to mass spectroscopy.

B1. Matrix groups.

Much was accomplished on the matrix group problem in a cooperative effort involving four teams. All Aschbacher classes except the "symplectic $p$-group case" can now be recognised, there are constructive recognition algorithms for classical groups, and a package has been written in GAP for many aspects of matrix group recognition. The "matrix" package now includes routines for recognising classical groups (more details from Celler or Leedham-Green), an improved Meataxe that works for large fields, the "smash" procedure for recognising certain decompositions of matrix groups with respect to a normal subgroup (e.g. imprimitive actions, tensor product actions and actions over an extension field), and a procedure for recognising imprimitive matrix groups.

B2. Nearly linear and partition backtrack methods for permutation groups.

The Nearly Linear library represents the strongest influence that complexity theory has had so far on practical algorithm development. There is no loss of reliability using these probabilistic methods either by fast verification or by turning Monte Carlo methods into Las Vegas methods. Methods were developed in permutation groups for composition series, identification of composition factors, centre, centraliser of normal subgroups, $p$-core, maximal soluble normal subgroups etc. Backtrack methods were improved, in particular a new partition backtrack methods for determination of normalisers by cooperation from Aachen D with QMW.

B3. Developing algorithms for finitely presented groups.

In this area a number of methods have been developed which involve a large number of different mathematicians and influences from a number of different areas of mathematics:

B3.1. The NQ (nilpotent quotient for possibly infinite factors) involves integral methods such as LLL. (Aachen, St Andrews, Trento).

B3.2. Niemeyer SQ (soluble quotient). Involves the Module Enumerator developed at St Andrews.

B3.3. Plesken SQ (soluble quotient). Involves modular representation
theory. See A4.4. above. (Aachen, Warwick, Newcastle).

B3.4. Polycyclic Quotient. Share package at present being developed. It involves Groebner bases. (St Andrews and other sites).

B4. Knuth Bendix and Automatic Groups.

The KBMAG package (which is a collection of standalone C programs) is available with full functionality as a GAP share library. This process was made easier when it was decided to use GAP format for KBMAG files. KBMAG also provides facilities for manipulating finite state automata, and for computing in automatic groups.

B5. Special AG systems.

A cooperative effort by QMW and Aachen resulted in the implementation of ideas of C. Leedham-Green for use of 'Special AG Systems' by B Eick. There was development of applications of these for the investigation of prefrattini groups, saturated formations and Euler functions of finite soluble groups. A function to compute the subgroup lattice of a solvable group by using the homomorphism principle was implemented.

B6. Automorphism Groups.

Progress here has been particularly innovative. In particular Sims' method to generate subgroups of automorphism groups as permutation groups. A general method is Morpheus which performs a backtrack search through tuples of elements in given classes of a group, modulo inner automorphisms.

The AutAG package (Automorphism Groups of soluble groups based on Special AG), extends the technique used in pQ of lifting automorphisms. The algorithm for the determination of the automorphism group of a $p$-group that was first implemented in the context of the ANU $p$-group construction method has been rewritten for GAP4 very significantly improving its efficiency by using the possibility offered in GAP of foregoing structure analysis of the $p$-group in question.

B7. Representation Theory.

The Burnside tables of marks task was undertaken first in Aachen, then because of movement of staff, also in St Andrews.

Study of tables of marks is strongly going on with Herbert Pahlings and a student of his, Thomas Merkwitz, and is used by Klaus Lux.

Generic Character tables - the CHEVIE system includes, among other new features, support for calculations in Artin-Tits braid groups and in reflection subgroups of Coxeter groups. Cooperation here was between St Andrews, Aachen and other teams.Improved Meataxe techniques were implemented, in particular condensation methods constructing Morita equivalent algebras.

Construction of Morita equivalent algebras for the determination of radical and socle series of PIMs uses both results coded in tables of marks and methods from the meataxe package, thus linking work of Aachen D, Warwick, Newcastle and St Andrews.

B8. Software for combinatorial topology.

New algorithms for fundamental groups and covers of simplicial complexes have been developed by Rees and Soicher for future inclusion in GRAPE.

B9. Developing algorithms for semigroups.

New methods were found and implemented to make a GAP software package for transformation monoids using group actions. A Todd-Coxeter procedure for finitely presented semigroups was also written in the GAP language. Many deep Reidemeister-Schreier type theorems have been discovered for finitely presented semigroups, in particular a study of when substructures are finitely presented has been undertaken. A theory of automatic semigroups was developed and decidability questions concerning semigroups were investigated.

B10. Crystallographic groups.

An expert system for crystallographers to construct and deal with crystallographic space groups up to dimension 6 in a systematic way is nearly complete. Specifically for this J Opgenorth developed algorithms to compute normalisers of finite unimodular groups. He refined these methods and suggested a very nice algorithm to construct generators for normalisers of finite unimodular groups by adjusting Voronoi's algorithm to Bravais manifolds. With this method we are now able to decide effectively when two finite unimodular groups are conjugate, which has always been one of the biggest challenges in the area. An essential part of this decision procedure is Souvignier's automorphism program.

B11. Lie Algebras.

ELIAS: Collaboration of Eindhoven with several other teams developed the implementation handling finite dimensional Lie Algebras.

ACELA: Work on an interactive book on Lie algebras based on Humphrey's text on Lie algebras was continued at Eindhoven throughout the project.

- Space groups up to dimension 4.
- Irreducible maximal finite subgroups of $GL(n,\mathbb{Z})$ up to $n = 24$.
- Plesken/Holt perfect groups.
- Transitive groups up to degree 31.
- Non-affine primitive permutation group up to degree 1000.
- Soluble affine permutation groups up to degree 243.
- Finite groups up to order 1000 omitting 512 and 768.
- Extension of ordinary and modular character table library.
- Library of table of marks.

- Character table of Hecke Algebra of type E8.
- Counterexample to Pyber conjecture.
- Further verification of Alperin/McKay-, Alperin weight- and Dade conjectures.
- The complete classification of the primitive multiplicity-free permutation representations and the primitive distance-transitive graphs for the sporadic simple groups and their automorphism groups (joint work by Ivanov, Linton, Lux, Saxl, Soicher), in which GAP and GRAPE played major roles.
- Use of the KBMAG package to prove several groups infinite, including the Fibonacci groups F(2,9), F(4,8) and F(9,6) (the last two were previously unknown), and the Heineken group. This last example turned out to be word-hyperbolic with a free subgroup of rank 3.
- A full classification of the irreducible maximal finite rational matrix groups up to degree 31.
- Extended B Gross' notion of an integral model of a rational algebraic group to integral forms over arbitrary number fields.
- Proved the infiniteness of $< x, y, z | x^{2}, y^{2}, z^{2}, (xy)^{2}, (xz)^{3}, (yz)^{7}, (xyz)^{23}>$ by lifting an epimorphism onto $L_{2}(139)$ to an extension of an 276 dimensional lattice by $L_{2}(139)$.
- Cooperation between Aachen, Trento, Warwick and QMW resulted in a study of the theory of $p$-groups of finite width which extends the theory of $p$-groups of finite coclass. They studied on actions of finite groups $G$ of $p$-adic Lie algebras, describing the lattice of $G$-invariant Lie subalgebras and Lie ideals in Lie algebras over $p$-adic integers lying in simple $p$-adic Lie algebras with $G$-action. An investigation of pro-$p$-Sylow subgroups of automorphism groups of semisimple $p$-adic Lie algebras on computers has been completed.
- Cooperation between Aachen B and Eindhoven resulted in a study of the arithmetic of Cayley orders in the context of finite irreducible subgroups of $G_{2}(\mathbb{C})$.

E1. A 'GAP Council' to advise on broad policy issues in the continued development of GAP has been extensively used. This Council acts as an editorial board for external contributions to GAP. See Appendix 1 to the 1995 Annual Report for details.

E2. An electronic GAP Forum, in which the users of the system are informed of new releases of GAP and of additions to it as well as of bug warnings and fixes. This Forum also served for the discussion of problems of general interest and their solutions using GAP, both for members of the network and others. Users with more local problems with GAP could get help from 'gap-trouble'. Answers to such questions, as well as the information in the Forum, were to a large extent provided by the 'GAP Support Group'. Between the Forum and 'gap-trouble' over 1000 requests for help were dealt with during the three years of the project. All these will continue to operate to support GAP.

E3. Some GAP programs produced by members of our network, and some other mathematicians, have been made available to all users of GAP via our ftp servers. These have been maintained in Aachen by Aachen D for most of the time of the HCM project.

A collection of some such programs with brief comments may be seen at (NO LONGER AVAILABLE).

E4. It is within the framework of cooperation, in particular of the HCM partners, that 'GAP headquarters' is moving to the St Andrews team before the retirement of the present chairman of Lehrstuhl D in July 1997 in order to secure the further continuity of the project. Organisational work on this transfer has been continuing during the last year of the project.

Five young researchers have been employed for periods during the project and trained at network sites. Also, as a result of the cooperation during the project, at least three young researchers have now accepted research posts in a different team in the network in a different EU country, financed by other research grants. At least one permanent post has been filled by a researcher who was working at a different network site.

Two members of the St Andrews team visited Athens and helped set up computer software related to the project and gave a series of lectures on using computational techniques. Sessions also took place at Heriot-Watt. These two teams together had 7 publications in 1994, 6 in 1995 and 16 in 1996.

As an example we quote the number of students trained at GAP headquarters Aachen D during the three years of our project. During that time 11 Diplomas and 6 PhDs were granted to students at Aachen for work related to the project. In addition 36 students, working for their degrees, coming from European countries spent a period of time at Aachen being trained in the skills related to GAP development. Of these students, 31 came from European countries other than Germany.

A still higher number of young European scientists, who were already in employment, came to GAP headquarters to receive training in algebraic software development skills.

A workshop 'Writing GAP Packages' was held in Aachen in September 1996. It was aimed at people who have already some experience with programming in GAP and had plans to write a larger package, possibly introducing new mathematical objects. St Andrews ran a course on Training for research in algebra during the summer of 1996 open to all EU students. St Andrews also ran a series of talks on 'An introduction to GAP' during October, November, December 1996.

The following meetings in 1997 are organised by teams in our network and will continue to inform European scientists about the work which was carried out during the project:

GAP in Research, St Andrews, April 6 - 11.

Computational representation Theory, Dagstuhl, May 18 - 23.

Algorithmic Methods for Permutation and Matrix Groups, Aachen, May 25 - 30.

Quotient Methods for Finitely Presented Groups. Trento, June 22 -
27.

Algorithmic Methods for Lie Groups and Algebras, Eindhoven,
September 21 - 26.

Groups St Andrews 1997 in Bath, July 26 - August 9.