CIRCA Report 2000-2002

GAP Development Report
CIRCA Staff
CIRCA students
Grants
Reseach visits
Lectures
Visitors
Conferences
Publications

---

The Centre for Interdisciplinary Research in Computational Algebra was set up by the University in 2000, to support ongoing interdisciplinary research, following the split of the former School of Mathematical and Computational Sciences into the School of Mathematics and Statistics and the School of Computer Science. The Centre incorporated ongoing projects around algorithms for finitely-presented groups and semigroups, the development and maintenance of the GAP (Groups, Algorithms and Programming) system, the History of Mathematics Website and others.

These projects have continued very successfully, leading to publications, completed PhD studentships and software releases, as detailed elsewhere in this report. Additionally, the Centre has obtained funding for, and pursued successfully, initiatives such as hosting the International Symposium on Symbolic and Algebraic Computation (ISSAC) in 2000, developing the use of GAP in undergraduate teaching, providing specialized GAP development and support for researchers in Newcastle, and hosting research visitors from all over the world.

In 2002, the Centre has finally obtained our long sort central site of operations, enabling us to base most of our research students and visitors and some staff in a common area within the Mathematical Institute, and finally giving us a visible presence in the University. This has been a most successful move, and is already leading to more informal contacts and a clearer identity for the Centre as a focus for our research. We look forward to continued expansion in our new surroundings.

Steve Linton
Director
December 2002

GAP Development Report 2000-2002

GAP development has continued throughout these two years on a widely distributed basis. Developers regularly contribute to the system from the UK, Germany, the US, the Netherlands, the Ukraine and elsewhere. Development is coordinated from St Andrews, using a wide variety of electronic tools, including mailing lists, Web sites and the CVS version control system. Occasional meetings of some or all developers “in the flesh” take place as opportunities permit.
User support is also delivered electronically, via mailing lists operated from St Andrews. We estimate that there are over 1000 sites world-wide using GAP.

GAP Releases

Version 4.2 was released in March 2000, with the following new features:

• A much extended and improved library of small groups now includes all groups of order <= 2000, except those of order 1024, as well as those of orders 5⁵ and 7⁴, those whose order factorises in at most 3 primes and those of order qⁿ * p for a prime-power qⁿ dividing 2⁸, 3⁶, 5⁵ or 7⁴ and an arbitrary prime p different to q.
• Associated IdGroup routines to identify a given group of any of these orders (except 512 and 1536) with the corresponding library entry.
• The primitive groups library has been made more independent of the rest of GAP by listing explicit generators for the groups. In the process some errors were corrected, and some additional checks have been performed.
• An enhanced library of character tables.
• New (and often much faster) infrastructure for orbit computation, based on a general “dictionary” abstraction.
• There is 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.
• A prototype implementation of Luks’ algorithms for computation with solvable matrix groups, currently restricted to the nilpotent case, and associated infrastructure, including an abstraction for general subgroup chains.
• Bidirectional streams, allowing an external process to be started and then controlled “interactively” by GAP.
• Changes in the behaviour of vectors over small finite fields – the system is now less eager to convert these automatically into compressed form, since this can result in vectors being compressed over too small a field.
• Numerous bug fixes and performance improvements.
  Release of version 4.3 was delayed while some technical and design issues were resolved and it was finally released early in 2002 with a large number of new features including:
• many new algorithms and new mathematical functionality, including
  – Dixon’s algorithm for constructing representations
  – Schur multiplier and Schur cover for permutation groups are available
  – linear groups over rings Z/mZ are available
  – the MeatAxe has been extended
  – new methods for polycyclic and almost crystallographic groups
  – improved handling of finitely presented groups
  – improved handling of permutation groups and their homomorphisms
• performance enhancements in many areas, including
  – faster arithmetic for matrices and matrix groups over finite fields
  – faster methods for large degree permutation groups
  – faster solvable quotient and Knuth-Bendix methods
  – various improvements in the GAP kernel
• extensions to the data libraries, including
  – transitive permutation groups up to degree 30
  – irreducible maximal finite integral matrix groups up to degree 31
  – character tables
• improvements of various interfaces, including
  – help system
  – kernel hooks
  – packages

We are currently working on version 4.4, with a view to a release in spring 2003, and plan to maintain a roughly annual schedule, thereafter.

GAP Packages

As well as the “core” system, GAP now comes with a wide range of add-on packages. A flexible interface allows easy inclusion of new packages, each of which has its own documentation. New versions of packages can be released, downloaded and installed, independently of releases of GAP. In version 4.3, some feature of the core system have actually been moved into packages to allow greater flexibility in updates. A great deal of cutting-edge development now takes place in packages.
We operate a refereeing system for packages, intended both to provide quality assurance for the user, and recognition for the authors. In version 4.3, the list of packages stands as follows:

Packages that were formerly part of the system

• ctbllib – character table library
• tomlib – library of tables of marks
  both maintained by T. Breuer

Refereed packages

• GRAPE,
  constructing and analysing graphs, finite geometries,
  by Leonard Soicher,
• cohomolo,
  computing Schur multipliers, first and second cohomologies and extensions
  by Derek F. Holt,
• LAG,
  Lie algebras of group algebras,
  by Richard Rossmanith, communicated by Andrea Caranti (Povo (Trento)), March 1999
• FactInt,
  integer factorization,
  by Stefan Kohl, communicated by Mike Atkinson (St Andrews), July 1999
• ParGAP (previously known as ParGAP/MPI),
  parallel GAP: Communication between a master GAP and several slave GAP’s on other machines (UNIX only),
  by Gene Cooperman, communicated by Steve Linton (St Andrews), July 1999
• XGAP,
  XGAP for GAP4 – a graphical user interface (UNIX only),
  by Frank Celler and Max Neunhsffer, communicated by Gerhard Hiss (Aachen), July 1999
• GrpConst,
  construction of all groups of a given order,
  by Hans Ulrich Besche and Bettina Eick, communicated by Charles Wright (Eugene), July 1999
• FPLSA,
  interface to a fast external Lie Todd-Coxeter program,
  by Vladimir Gerdt and Vladimir Kornyak, communicated by Steve Linton (St Andrews), July 1999
• EDIM,
  elementary divisors of integral matrices,
  by Frank Lybeck, communicated by Mike Atkinson (St Andrews), August 1999
• Cryst,
  computing with affine crystallographic groups,
  by Bettina Eick, Franz Gshler and Werner Nickel, communicated by Herbert Pahlings (Aachen), February 2000
• CrystCat,
  a catalog of crystallographic groups of dimensions 2, 3, and 4,
  by Volkmar Felsch and Franz Gshler communicated by Herbert Pahlings (Aachen), February 2000
• Carat,
  interface to Carat,
  by Franz Gshler communicated by Herbert Pahlings (Aachen), February 2000
• ITC,
  interactive Todd-Coxeter (UNIX only)
  by Volkmar Felsch, Ludger Hippe and Joachim Neubyser communicated by Edmund F. Robertson (St Andrews), March 2000
• AutPGrp,
  automorphism group of a p-group
  by Bettina Eick and Eamonn O’Brien, communicated by Derek F. Holt (Warwick), September 2000
• CRISP,
  computing with radicals, injectors Schunck classes and projectors of finite solvable groups
  by Burkhard Höfling, communicated by Joachim Neubyser (Aachen), December 2000
• FORMAT,
  computing with formations of finite solvable groups
  by Bettina Eick and Charles Wright, communicated by Joachim Neubyser (Aachen), December 2000
• ACLIB,
  almost crystallographic groups library
  by Karel Dekimpe and Bettina Eick, communicated by Gerhard Hiss (Aachen), February 2001
• AtlasRep,
  atlas of group representations
  by Robert Wilson, Richard A. Parker, John Bray and Thomas Breuer, communicated by Herbert Pahlings (Aachen), April 2001
• ACE,
  advanced coset enumerator
  by George Havas, Colin Ramsay, Alexander Hulpke and Greg Gamble, communicated by Joachim Neubyser (Aachen), April 2001
• SmallGroups,
  small groups library
  by Hans Ulrich Besche, Bettina Eick and Eamonn O’Brien communicated by Mike F. Newman (Canberra), June 2001
• ANUPQ,
  ANU p-quotient,
  by Eamonn O’Brien, Werner Nickel and Greg Gamble, communicated by Charles Wright (Eugene), April 2002
• XMod,
  crossed modules and cat1-groups,
  by Chris Wensley and Murat Alp, originally communicated for GAP 3 by Derek F. Holt (Warwick), December 1996.

Other Packages

• Polycyclic,
  computation with polycyclic groups,
  by Bettina Eick (beick@tu-bs.de) and Werner Nickel (nickel@mathematik.tu-darmstadt.de), April 2000
• unipot
  computation with elements of unipotent subgroups of Chevalley groups,
  by Sergei Haller (Sergei.Haller@math.uni-giessen.de) May 2000 (updated to version 1.1, July 2000)
• OpenMath, README
  OpenMath phrasebook for GAP 4, (UNIX only) Version 1r0
  by Andrew Solomon (andrew@illywhacker.net) August 2000
• KBMAG,
  Knuth-Bendix for monoids and groups
  by Derek F. Holt April 2002
• quagroup, README
  computing in quantized enveloping algebras of finite-dimensional semisimple Lie algebras, Version 1r0, (for GAP 4r3 and higher)
  by Willem de Graaf May 2002
• GUAVA,
  coding theory
  by R. Baart, J. Cramwinckel, E. Minkes, E. Roijackers, Lea Ruscio 2002
• gapdoc,
  alternative GAP package documentation tools
  by F. Lübeck and M. Neunhoeffer

CIRCA Staff

Steve A Linton
Edmund F Robertson
Colin M Campbell
John J O’Connor
Nik Ruskuc

CIRCA Students

Ph.D.

Andrew Cutting (1996-2000), Todd-Coxeter methods for inverse monoids.
Robert Wainwright (1996-2001), Finding “small” matrices P, Q such that PDQ = S.
Robert M Thomson (1998-2001), Finiteness conditions of wreath products of semigroups and related properties of diagonal acts.
Isabel M Araujo (1998-2001), Presentations for semigroup constructions and related computational methods.
Luís Descalço (1999-2002), Automatic semigroups: constructions and subsemigroups.
James D Mitchell (1999-2002), Extremal problems in combinatorial semigroup theory.
Max Murphy (1999-2002), Restricted permutations, antichains, atomic classes and stack sorting.
Peter P Campbell (1999-2003), Efficiency and Fibonacci length in group presentations.
Erzsi Dombi (2001-)
Nelson Silva (2001-)
Maja Waldhausen (2001-)
Catarina Carvalho (2002-)
Elizabeth Kimber (2002-)
Alan Cain (2002-)
Peter Gallagher (2002-)
Robert Gray (2002-)
Dale Sutherland (2002-)

M.Sc.

Catarina Carvalho (2001-2002), Presentations of semigroups and inverse semigroups.
Katrin Gehles (2001-2002), Ordinary characters of finite special linear groups.
Elizabeth Kimber (2001-2002), Some cyclically presented groups.
C-H Wu (2002-)

Grants

EPSRC: “GAP Development and Support” (1996-2000) Rated alpha 5/excellent.
INTAS (2000-2003).
LMS: ISSAC 2000.
EMS: ISSAC 2000.
EPSRC MathFIT: “Constraint Programming, Search and Symmetry” (2001- ).
NETCA – UK network in Computer Algebra: St Andrews, Bath, QMU, London, NAG
Ltd, UKC (2001- ).
LMS: Visit of Sinisa Crvenkovic (Novi Sad University) (August-September 2002).
LMS: Groups St Andrews 2001.
EMS: Groups St Andrews 2001.
EPSRC: “Computational Algebra for Commodity Parallel Machines” (2002- ).
LMS: Visit of Alexander Konovalov (Zaporozhye State University) (August-September 2002).
EPSRC: Support for Preparation of a Proposal for a European Network of Excellence in Symbolic Computation (ENESCO).

Research Visits

2000

CMC: RWTH Aachen, Germany; Galway, Ireland; Lincoln, Nebraska, USA; Pusan, Korea.
EFR: Galway, Ireland; Lincoln, Nebraska, USA; RWTH Aachen, Germany.
NR: Dunedin, New Zealand.
SAL: Queen Mary University, London; City University New York; Northeastern
University, Boston; RWTH Aachen, Germany; Birmingham

2001

CMC: Coimbra, Portugal; Trento, Italy; RWTH Aachen, Germany.
EFR: RWTH Aachen, Germany; Oberwolfach, Germany.
NR: Leicester; Evora, Portugal; Dunedin, New Zealand.
SAL: Leicester; Oberwolfach, Germany; Birmingham; RWTH-Aachen, Germany; Sienna, Italy.

2002

CC: Centre of Algebra, Lisbon, Portugal.
CMC: Galway, Ireland; Centre of Algebra, Lisbon, Portugal; RWTH Aachen, Germany.
ED: Porto.
MM: Cambridge; Essex.
JDBM: Essex.
EFR: Centre of Algebra, Lisbon, Portugal; RWTH Aachen, Germany.
SAL: Newcastle; Brussels; RWTH Aachen, Germany.
NS: Centre of Algebra, Lisbon, Portugal.

Lectures

2000

CMC: ‘Third International Colloquium on Words, Languages and Combinatorics’, Kyoto Sangyo University Japan; ‘Germany-Korea Mathematics Workshop on Algebra and Topology’, Pusan National University, Korea.
EFR: Automata, semigroups and groups, EPSRC Regional Meeting, Edinburgh. 
NR: ‘International Conference on Geometrical and Combinatorial Methods in Group Theory and Semigroup Theory’, Lincoln, Nebraska; ‘Third International Colloquium on Words, Languages and Combinatorics’, Kyoto, Japan; ‘Workshop on Algebraic Systems, Formal Languages and Computations’, Kyoto, Japan.

2001

CMC: ‘Groups Galway’, Galway, Ireland.
EFR: ‘Groups Galway’, Galway, Ireland.
NR: Leicester; ‘Thematic Term on Semigroups, Algorithms and Languages’, Coimbra, Portugal.
SAL: Symmetry Breaking in the Alien Tiles Puzzle, Calculemus 2001, Sienna.

2002

CMC: ‘Tenth International Conference on Fibonacci Numbers and Applications’, Northern Arizona Universty, Flagstaff.
LD: Workshop on Semigroups and Languages, Centre of Algebra, Lisbon, Portugal.
JDBM: Workshop on Semigroups and Languages, Centre of Algebra, Lisbon, Portugal.
EFR: ‘Groups Galway’, Galway, Ireland.
NR: Joint AMS-UMI Meeting, Pisa, Italy; Worksop on Semigroups, Automata and Formal Languages, Crema, Italy; Workshop on Semigroups and Languages, Centre of Algebra, Lisbon, Portugal.

Visitors

2000

Craig A Struble (Virginia, USA)
Derek F Holt (Warwick)
Ben Hopson (Oxford)
Eamonn A O’Brien (Auckland, New Zealand)
Friedrich Otto (Kassel, Germany)
Michael Hoffmann (Leicester)
Peter M Higgins (Essex)
Richard M Thomas (Leicester)
Robert F Morse (Evansville, USA)
Scott H Murray (Chicago, USA)
Vitor H Fernandes (Lisbon, Portugal)
Walter Ledermann

2001

Zwelethemba Mpono (Natal, South Africa)
Friedrich Otto (Kassel, Germany)
George Havas (Queensland, Australia)
Hossein Doostie (Tehran, Iran)
Isabel M Araujo (Evora, Portugal)
Leonard H Soicher (Queen Mary)
P Elizabeth Holmes (Birmingham)
Peter M Higgins (Colchester)
S Crvenkovic (Novi Sad)
Stefan Kohl (Stuttgart, Germany)
Warwick Harvey (Imperial)

2002

Alexander B Konovalov (Zaporozhye State University)
Anton Evseev (Oxford)
Chris J Saker (Essex)
Nick D Gilbert (Edinburgh)
P Elizabeth Holmes (Birmingham)
Richard M Thomas (Leicester)
Sarah E Rees (Newcastle)
Scott H Murray

Conferences

ISSAC 2000
Calculemus 2000
Groups St Andrews 2001

Publications

2000

1. Araujo, I M and Ruskuc, N: On finite presentability of direct products of semigroups, Algebra Colloquium, 7(2000), 83-91.
2. Arthur, R E and Ruskuc, N: Presentations for two extensions of the monoid of order-preserving mappings on a finite chain, Southeast Asian Bulletin of Mathematics, 24 (2000), 1-7.
3. Atkinson, M D, Gilbert, N, Howie, J, Linton, S A and Robertson, E F: Computational and geometric aspects of modern algebra, Cambridge University Press, Cambridge, 2000.
4. Ayik, H, Campbell, C M, O’Connor, J J and Ruskuc, N: On the efficiency of wreath products of groups, Proc. Groups Korea ’98 (eds.Y G Baik, D L Johnson and A C Kim. Walter de Gruyter, Berlin New York 2000), 39-51.
5. Ayik, H, Campbell, C M, O’Connor, J J and Ruskuc, N: On the efficiency of finite simple semigroups, Turkish J. Math. 24 (2000), 129-146.
6. Ayik, H, Campbell, C M, O’Connor, J J and Ruskuc, N: The semigroup efficiency of direct powers of groups, Proc. Internat. Conf. on Semigroups, Braga, Portugal 18-23 June 1999 (eds, Paula Smith, Emilia Giraldes and Paula Martins, World Scientific, Singapore 2000), 19-25.
7. Ayik, H, Campbell, C M, O’Connor, J J. and Ruskuc, N: Minimal presentations and efficiency of semigroups, Semigroup Forum 60 (2000), 231-242.
8. Campbell, C M, Robertson, E F, Ruskuc, N and Thomas, R M: Direct products of automatic semigroups, J. Austral. Math. Soc. Ser. A  69 (2000), 19-24.
9. Crvenkovic, S, Dolinka, I and Ruskuc, N: Notes on the number of operations of finite semigroups, Acta Scientiarum Mathematicarum (Szeged), 66 (2000), 23-31.
10. Doostie, H and Campbell, C M: Fibonacci length of automorphism groups involving Tribonacci numbers, Vietnam J. Math. 28 (2000), 57-66.
11. Ruskuc, N: On finite presentability of monoids and their Schutzenberger groups, Pacific Journal of Mathematics,195 (2000), 487-509.
12. Ruskuc, N: Presentations for monoids, their maximal subgroups, and Schutzenberger groups, Algorithmic Problems in Groups and Semigroups (eds. J.-C. Birget et al.), Birkhauser, Boston (2000), 235-249.

 

2001

13. Araujo, I M and Ruskuc, N: Finite presentability of Bruck-Reilly extensions of groups, J. Algebra, 242 (2001), 20-30.
14. Araujo, I M, Branco, M J J, Fernandes, V H, Gomes, G M S and Ruskuc, N: On generators and relations for unions of semigroups, Semigroup Forum, 63 (2001), 49-62.
15. Campbell, C M, Robertson, E F, Ruskuc, N and Thomas, R M: Automatic semigroups, Theoret. Comput. Sci.250 (2001), 365-391.
16. Crvenkovic, S, Dolinka, I and Ruskuc N: Finite semigroups with few term operations, J. Pure Appl. Algebra,157 (2001), 205-214.
17. Crvenkovic, S, Dolinka, I and Ruskuc N: The Berman conjecture is true for finite surjective semigroups and their inflations, Semigroup Forum, 62 (2001), 103-114.
18. Otto, F and Ruskuc, N: Confluent monadic string-rewriting systems and automatic structures, J. Autom. Lang. Combinat., 6 (2001), 375-388.
19. Robertson, E F, Ruskuc, N and Thomson, M R: On diagonal acts of monoids, Bull. Austral. Math. Soc. 63 (1) (2001), 167-175.

 

2002

20. Campbell, C M, Havas, G, Hulpke A and Robertson E F: The simple group L₃(5) is efficient, Comm. Alg. 30(2002), 971-975.
21. Campbell, C M, Mitchell J D and Ruskuc, N: Comparing semigroup and monoid presentations for finite monoids, Monatshefte für Mathematik 134 (2002), 287-293.
22. Campbell, C M, Robertson, E F, Ruskuc, N and Thomas, R M: Automatic completely-simple semigroups, Acta Math. Hungar. 96 (2002), 201-215.
23. Campbell, C M, Mitchell J D and Ruskuc, N: On defining groups efficiently without using inverses, Math. Proc. Cambridge Philos. Soc. 133 (2002), 31-36.
24. Campbell, C M, Havas, G, Hulpke, A and Robertson, E F: Efficient simple groups, Comm. Algebra 30 (2002), 4613-4619.
25. Descalo, L and Ruskuc, N: On automatic Rees matrix semigroups. Comm. Algebra 30 (2002), 1207-1226.
26. Hoffmann, M, Thomas, R M and Ruskuc, N: Automatic semigroups with subsemigroups of finite Rees index, Internat. J. Algebra Comput. 12 (2002), 463-476.
27. Linton, S A, Pfeiffer, G, Robertson, E F and Ruskuc, N: Computing transformation semigroups, J. Symbolic Comput. 33 (2002), 145-162.
28. Linton, S A and Sebastiani, R (Eds): Journal of Symbolic Computation, Special Issue on the Integration of Automated Reasoning and Computer Algebra Systems (4) 34 (October 2002).
29. Robertson, E F, Ruskuc, N and Thomson, M R: On finite generation and other finiteness conditions for wreath products of semigroups, Comm. Algebra 30 (2002), 3851-3873.

 

CIRCA Preprints

2002/1
George Havas and Edmund F Robertson, Irreducible cyclic presentations of the trivial group.
2002/2 
Luis Descalco and Nik Ruskuc, Subsemigroups of the bicyclic monoid.
2002/3 
Petra E. Holmes, Stephen A. Linton and Scott H. Murray, Product replacement in the monster.
2002/4 
Colin M. Campbell, George Havas, Alexander Hulpke and Edmund F. Robertson, The simple group L₃(5) is efficient.
2002/5 
Colin M. Campbell, Peter P. Campbell, H. Doostie and Edmund F. Robertson, The Fibonacci length for certain metacyclic groups.  
2002/6 
Colin M. Campbell, Peter P. Campbell, H. Doostie and Edmund F. Robertson, On the Fibonnaci length of powers of dihedral groups. 
2002/7 
Colin M. Campbell, Peter P. Campbell, B. T. K. Hopson and Edmund F. Robertson, On the efficiency of direct powers of PGL(2,p).