PREFACE

The algebra system Magma is designed to provide a software environment for computing with the structures which arise in algebra, geometry, number theory and (algebraic) combinatorics. Magma enables users to define and to compute with structures such as finite and infinite groups, rings, fields, modules, graphs and designs. Novel features of the system include:

• Explicit definition of the algebraic structures needed to solve a problem. Each object subsequently arising in the course of the computation is then defined in terms of these structures.

• Simultaneous definition of many different structures. This reflects the fact that much sophisticated algebraic computation does not happen in isolation but rather involves working in a range of different structures.

• The ability to perform structural computation with many types of algebraic structure. For example, given generators for a permutation group, Magma can name its composition factors.

• Automatic maintenance of relationships between structures, such as the relationship of being a substructure, or the relationship of being a quotient structure.

• An emphasis on fast computation in important classes of algebraic structures.

• Correspondence of the user language data types to the central concepts of modern algebra: algebraic structures, algebraic elements, sets, sequences, and mappings.

• Over a thousand built-in functions and operators designed to determine deep structural properties of groups, rings and modules.

• The availability of Magma databases containing many useful examples of structures (currently, mainly groups). For example, included in these data bases are all groups having order less than 100, and the Sims list of all primitive groups having degree less than 50.

Algebraic structures are first classified by variety, that is, a class of structures having the same set of defining operators and satisfying a common set of axioms. Thus, the collection of all rings forms a variety. Within a variety, structures are partitioned into classes. Informally, a family of algebraic structures forms a class if its members all share a common representation. All varieties possess the abstract class of structures (finitely presented structures). However, classes based on a concrete representation are as least as important in most varieties. For example, within the variety of rings, the family of polynomial rings constitutes the abstract class, while the family of matrix rings constitutes a concrete class.

In the mid 1970's, the computer algebra system Cayley was conceived, primarily as a group theory package. However, a great deal of the infrastructure originally developed to support group theoretic computation is equally applicable to other branches of algebra. Further, the study of groups involves working with many other types of algebraic structure. As a consequence, over the past six years the system has been significantly expanded to include fields, matrix rings, polynomial rings, modules and other types of structure. In parallel with these mathematical developments, a new user programming language based on the principles outlined above has been designed. The new system Magma comprises the new language and the expanded range of mathematical facilities. This book is a draft of what is intended to be the reference manual for Magma.

As remarked before, this manual is a draft for a comprehensive guide to Magma. Although we have compiled this guide with great care, it is possible that the semantics of some facilities have not been described adequately. We regret any inconvenience that this may cause, and we would be most grateful for any comments and suggestions for improvement. We would like to thank users for numerous helpful suggestions for improvement and for pointing out misprints in previous versions.

Sydney, January 1998

ACKNOWLEDGEMENTS

The Magma system has benefited enormously from contributions made by many members of the mathematical community. We list below those persons and research groups who have given the project substantial assistance either by allowing us to adapt their software for inclusion within Magma or through general advice and criticism. We wish to express our gratitude both to the people listed here and to all those others who participated in some aspect of the Magma development.

• A facility for computing with arbitrary but fixed precision reals was based on Richard Brent's (ANU) FORTRAN package MP. Richard also provided his database of 180, 000 factorizations of integers of the form p^n +- 1, together with his intelligent factorization code FACTOR.

• The group headed by Henri Cohen (Bordeaux) made available their excellent Pari system for computational number theory for inclusion in Magma. Pascal Letard of the Pari group visted Sydney for two months in 1994 and recoded large sections of Pari for Magma. The Pari facilities installed in Magma include arithmetic for real and complex fields (the `free' model), approximately 100 special functions for real and complex numbers, power series, p-adic numbers, factorization of polynomials over p-adic fields, binary quadratic forms, quadratic fields and other features.

• The package for multivariate polynomials in early versions of Magma was based on the SAC-2 package of George Collins and Rüdiger Loos. The current Magma function for the factorization of univariate polynomials over the integers owes much to the help and advice of George Collins.

• The Magma facility for elliptic curves over the rational field is heavily based on John Cremona's mwrank package.

• Greg Gamble (UWA) helped refine the concept of a G-set for a permutation group and drafted several sections of the chapter on permutation groups.

• Xavier Gourdon (INRIA, Paris) made available his C implementation of A. Schön-hage's splitting-circle algorithm for the fast computation of the roots of a polynomial to a specified precision. Xavier also assisted with the adaption of his code for the Magma kernel.

• The major structural machinery for Lie algebras has been implemented for Magma by Willem de Graaf and is based on his ELIAS package originally written in GAP.

• Markus Grassl (IAKS, Karlsruhe) has contributed the ConcatenatedCode and JustensenCode constructions, as well as many other suggestions in Coding Theory.

• Charles Leedham-Green (QMW) has worked with the Magma group on the design of a large number of algorithms for soluble groups and local fields during several visits to Sydney.

• The Todd-Coxeter procedure in Magma was designed by George Havas (University of Queensland) and implemented by Jin Xian Lian (also of the University of Queensland). The Magma Smith and Hermite Normal Form code together with the underlying extended gcd algorithms were developed in close cooperation with George Havas and Bohdan Majewski (University of Newcastle). George has also contributed to the design of the machinery for finitely presented groups.

• Cohomology calculations for permutation groups are implemented by a program written by Derek Holt. His program, kbmag, for monoids and automatic groups has also been installed in Magma. Derek has contributed to the design of algorithms in module theory and permutation groups.

• Alexander Hulpke has made available his database of all transitive permutation groups of degree up to 22. This incorporates the earlier database of Greg Butler and John McKay containing all transitive groups of degree up to 15.

• Gregor Kemper (Heidelberg) has contributed all of the major algorithms of the Invariant Theory module of Magma, together with many other helpful suggestions in the area of Commutative Algebra.

• The main integer factorization tools available in Magma are due to A.K. Lenstra (Bellcore) and his collaborators. These include the elliptic curve method and a multiple polynomial quadratic sieve developed by Arjen from his `factoring by email' MPQS during a visit to Sydney in 1995.

• The PERM package developed by Jeff Leon (UIC) for efficient backtrack searching in permutation groups is used for most of the permutation group constructions that employ backtrack search. Jeff's programs for finding automorphism groups of codes, designs and matrices are also used.

• The vector enumeration program of Steve Linton (St. Andrews) provides Magma with the capability of constructing matrix representations for finitely presented associative algebras.

• Automorphism groups and isomorphism testing of graphs is performed by Brendan McKay's program nauty.

• An implementation of the Dixon-Minkwitz algorithm for computing the ordinary irreducible representations of a finite group was developed with Torsten Minkwitz's assistance.

• The p-quotient program, developed by Eamonn O'Brien based on earlier work by George Havas and Mike Newman, provides a key facility for studying p-groups in Magma. Eamonn's extensions of this package for generating p-groups and computing automorphism groups of p-groups are also included in Magma. The corresponding sections of the Handbook were written by Eamonn.

• The primality of integers is proven using the ECPP (Elliptic Curves and Primality Proving) package written by Francois Morain (Ecole Polytechnique and INRIA). The ECPP program in turn uses the BigNum package developed jointly by INRIA and Digital PRL.

• A program developed by Michel Olivier (Bordeaux) is used to compute Galois groups for polynomials having degree less than 12.

• The facilities for general number fields in Magma are provided by the KANT V4 package developed by Michael Pohst and collaborators, originally at Düsseldorf and now at TU, Berlin. This package provides extensive machinery for compuing with maximal orders of number fields and their ideals. Particularly noteworthy are functions for computing the class group, the unit group, systems of fundamental units, and subfields of a number field. Johannes Graf von Schmettow, Max Jüntgen and Mario Daberkow, all from the KANT group, have spent extended periods in Sydney working with the Magma group.

• The Magma implementation of the Dixon-Schneider algorithm for computing the table of ordinary characters of a finite group is based on an earlier version written for Cayley by Gerhard Schneider (Karlsruhe).

• The low index subgroup function is implemented by code that is based on a Pascal program written by Charlie Sims (Rutgers).

• The functions for computing automorphism groups and isometries of lattices are based on the AUTO and ISOM programs of Bernd Souvignier.

• The code to perform the regular expression matching in the regexp intrinsic function comes from the V8 regexp package by Henry Spencer (University of Toronto).