Announcement of the MAGMA System for Computational Algebra Introduction ------------ Magma is a radically new software system for computational algebra, number theory and geometry. It provides a mathematically rigorous environment for computing with algebraic structures (groups, rings, fields, modules, algebras), geometric structures and combinatorial structures. A novel feature of the system lies in its emphasis on *structural* computation. By this is meant the ability to perform operations such as finding a "standard basis", testing membership, determining global properties etc for an algebraic structure, which may be finite or infinite. Magma was launched at a conference held at Queen Mary and Westfield College, London, August 23 -- 27, 1993. As distribution will commence late in November, 1993, this document is intended to provide some general information. Two companion documents, "Summary of categories and their operators in Magma", and "Examples of Magma calculations and programs" are available upon request. Types ----- The system design adapts ideas from Object-Oriented programming where the OO classes are derived from notions in Universal Algebra and Category Theory. The primary concept is that of a *magma* (a set with a law of composition). Thus, types correspond to magmas; a collection of magmas sharing a common representation form a category (e.g. the category of permutation groups); a collection of categories satisfying the same set of identical relations form a variety (e.g. the variety of groups). In particular, + The variety operations -- substructure, homomorphic image, and Cartesian product are available as uniform constructors across all categories. + Functors may be used to move between categories. Every object created in Magma, is either a magma or is defined in terms of one or more magmas. This approach provides the user with precise control over the operations that may be performed on an object x since these are completely determined by the magma to which x belongs. The aggregate data types are sets (finite and infinite), sequences (finite and infinite), Cartesian products, tuples, and mappings. A feature of the language is the provision of powerful set and sequence constructors based on the use of predicates. The Language ----------- The main features of the user language are: + Imperative language with standard imperative-style statements and procedures + The language contains an essentially functional subset providing standard features such as closures, higher-order functions, and partial evaluation + Dynamic typing + The general aggregate data types correspond to the fundamental concepts of algebra: set, sequence, mapping, magma + Universal structure constructors provide a general mechanism for constructing magmas + Simple but powerful notation for constructing sets and sequences in a natural mathematical style + Set and sequence operations are implemented with a strong emphasis on efficiency + Coercion between magmas (including automatic coercion) + User-defined OO classes will be available in 1994 The Kernel Magmas ----------------- The efficiency of Magma's implementations of fundamental algorithms is designed to be similar to that achieved by specialist programs. This is achieved by having optimized implementations of a large number of fundamental algebraic algorithms encoded as part of the C kernel of the system. To avoid having to re-implement many highly complex algorithms, an internal *software bus* allows the integration of C code written independently at the cost of a modest amount of effort. Consequently, many key Magma functions are implemented by highly optimized programs written by the experts in the appropriate areas. The major categories of magma currently supported in the kernel include: + Semigroups: Finitely presented semigroups + Groups: Finitely presented groups, finite abstract groups, permutation groups, soluble groups and matrix groups + Rings: Ring of integers, order in a number field; + Fields: Galois fields, rational field, number fields, function fields, real field, complex field + Algebras: Finitely presented algebras, polynomial algebras, matrix algebras, power series algebras, group algebras (in preparation) + Modules: R-modules (with scalar or matrix action); Hom(M, N), where M and N are R-modules; K[G]-modules; lattices + Geometric structures: Elliptic curves (in preparation) + Incidence structures: Graphs, codes, finite geometries (in preparation) Features of the Mathematical Function Library --------------------------------------------- The library of intrinsic functions contains implementations of approximately 2000 algebraic and geometric algorithms. Highlights include: + Fast machinery for polynomial algebra, particularly for the factorization of univariate polynomials over GF(q) and Z. Magma supports calculation with ideals in rings. Groebner basis algorithms for both commutative and non-commutative polynomial rings will be installed in the near future. + A package for finite fields that uses distinct representations for fields GF(q), where q is small, prime fields GF(p), where p may be multiple precision, and GF(p^n), where p is small but n is large (e.g. p=2, n=1000). + The KANT system developed by Michael's Pohst's group for constructive algebraic number theory. This package includes facilities for calculating integral bases, ideal class groups and systems of fundamental units for fields of degree in excess of 20. + A new generation of permutation group algorithms that enables users to routinely perform computations, such as computing a chief series, in short base groups having degree up to at least a million. Backtrack searches are conducted using Jeff Leon's new package. + New algorithms and programs for most of the critical processes for finitely presented groups. Included among these is George Havas's new Todd-Coxeter procedure and Sims' new backtrack-based low index subgroups algorithm. + Extensive machinery for computing with modules and their homomorphisms. This includes highly optimized code for modules over finite fields and over the ring of integers. + A graph theory module containing many functions for determining graph invariants as well as Brendan McKay's graph automorphism program (nauty). + A coding theory package including many constructions for linear codes together with machinery for determining important invariants such as the minimum weight, the weight enumerator and the automorphism group. Data Bases ---------- A subsequent release of the system will include an integrated data-base facility to support the use of large mathematical data bases. The data base will contain such things as all quadratic fields having discriminant less than a million, all vertex-transitive graphs having up to 24 vertices, all 2-groups having order dividing 256, etc. The Environment --------------- + Interactive line editing + History system with recall and editing of previous lines + A hierarchical on-line help facility + Ability to save and restore user workspaces + Environment variables for configuring style of output, etc. + Verbose options for built-in functions + Logging of output, input/output with external files, etc. + A socket mechanism for communicating with other processes (in preparation) Documentation ------------- There are three main components of the documentation: + J. Cannon and C. Playoust: An Introduction to MAGMA, 250 pages; + W. Bosma and J. Cannon: The MAGMA Handbook, 600 pages; + On-line help. The Magma Introduction does not assume any previous knowledge of programming languages or computer algebra and provides a gentle introduction to the system. It is particularly suitable for undergraduate use. The Magma Handbook provides complete documentation for every language and environmental feature. An on-line help system provides a variety of levels of information. In particular, it provides access to the Handbook descriptions of all function and operators. Cayley and Magma ---------------- Magma has been developed by the Computational Algebra Group at the University of Sydney with funding provided by the Australian Research Council. Between 1975 and 1985, this group produced the Cayley system for group theory and related areas. Some 18 years of field experience with Cayley provided a starting point for the design of Magma. However, Magma is designed as a general algebra system in contrast to the more limited objectives of Cayley. In addition to providing a vast expansion in its coverage of algebra, Magma currently contains approximately 90 per cent of the facilities of Cayley and the remainder will be installed over the next few months. Distribution of Magma will commence in November 1993 with the public release of Magma V1. At that time distribution of Cayley will cease. While Cayley and Magma are not compatible, a translator has been written to assist in the conversion of Cayley code to Magma code. All Cayley sites with a license current on or after 1 January, 1993 will be automatically upgraded to Magma. Platforms --------- The initial release of Magma will be available for the following processors: SUN 4, SUN 10 under SUNOS 4.x and Solaris 2 DECstation under Ultrix DEC Alpha under Ultrix (Available in 1994) IBM RS6000 under AIX HP9000/700 series under HP-UX Apollo M680x0 based machines, DN10000 386/486 PC (Available first quarter 1994) Macintosh running A/UX 2.01 or higher (Available in 1994) It is planned to make available a low-cost student version for 386/486 PCs. Implementations for other UNIX-based machines will depend upon demand. Ordering Information -------------------- For more information, or to order the system, contact The Secretary Computational Algebra Group School of Mathematics University of Sydney NSW 2006 Australia Email: magma@maths.su.oz.au Telephone: +61 2 692 3338 Fax: +61 2 692 4534 ================= ================= Summary of Categories and Operators in Magma The kernel of Magma contains machinery for representing and computing with the fundamental families of algebraic structures. Much of the power of the system derives from the inclusion of a large number of sophisticated algorithms for group theory, ring theory, module theory, representation theory, number theory and finite geometry. The categories and operators implemented in the kernel of the system are summarized below. ------------------------------------------------------------------------------- CATEGORIES OF RING AND ALGEBRA:- + Ring of integers + Order of a number field + Matrix rings + Polynomial rings + Power series rings + Group rings (In preparation) + Ring of generalized characters of a finite group + Finitely presented algebras OPERATIONS FOR A GENERAL RING:- - Arithmetic with elements - Construction of ideals and subrings - Membership of ideals and subrings (Not supported in all types of ring) - Arithmetic with ideals - Formation of quotient rings (Not supported in all types of ring) ADDITIONAL OPERATIONS FOR PARTICULAR CATEGORIES:- The Ring of Integers -------------------- - Infinite precision arithmetic - Arithmetic functions: Jacobi symbol, Euler phi function etc - Combinatorial functions: partitions, Stirling numbers etc - Primality testing (Miller-Rabin, Lucas-Lehmer tests) - Primality proofs, primality certificates - Generation of primes - Elementary factorization techniques: Trial division, Fermat, Shanks, Pollard rho, Pollard p-1 - Advanced factorization techniques: Elliptic curve method (A Lenstra) Matrix Rings ------------ - Determinant - Tensor product - Echelon form, reduced echelon form (Over a field) - Dimension of a subring (Over a field) - Frobenius and Jordan normal form (Over a field) - Minimal and characteristic polynomials (Over a field) - Hermite and Smith normal form (Over an Euclidean domain) Polynomial Rings ---------------- - Resultant - Discriminant - Greatest common divisors - Factorization (Over GF(q) and Z) - Groebner basis of an ideal (Over a field) Ring of Generalized Characters of a Finite Group ------------------------------------------------ - Table of ordinary characters (Dixon-Schneider algorithm) - Definition of class functions - Arithmetic on class functions - Construction of permutation characters - Induction and restriction of a character - Action of a group on the characters of a normal subgroup - Decomposition of characters Finitely Presented Algebras --------------------------- - Construction of an fp-algebra K[S], where S is a fp-semigroup, fp-monoid or fp-group - Construction of a matrix representation (S Linton's program) -------------------------------------------------------------------------------- CATEGORIES OF FIELD:- + Finite fields + Rational field + Rational function fields + Algebraic number fields + p-adic fields + Real and complex fields OPERATIONS FOR A GENERAL FIELD:- - Arithmetic, trace, norm - Square root, n-th root, logarithm - Construction of subfields - Construction of extensions - Embedding of subfields - Minimal polynomial - Field as a vector space over a subfield ADDITIONAL OPERATIONS FOR PARTICULAR CATEGORIES:- Number Fields: Finite Extensions of the Rational Field Q -------------------------------------------------------- A sophisticated package known as KANT2 and developed jointly with Michael Pohst's group in Dusseldorf is included in the system. This module enables users to calculate integral bases, fundamental units and ideal class groups in extensions of the rational field having degree up to 20 or 30. - Discriminant - Integral basis (Round 2 and round 4 algorithms) - Fundamental units (Relation method) - Ideal class group (Relation method) - Solution of norm equations - Special methods for quadratic fields - Special methods for cyclotomic fields The Real Field and the Complex Field ------------------------------------ Magma contains an implementation of Richard Brent's MP package for multiple precision floating point arithmetic. This permits the user to compute with real or complex numbers to any specified precision. - Arithmetic - Constants: Pi, Euler's constant, Catalan's constant - Elementary transcendental functions: log, exp, sin, cos, tan, arcsin,arccos, arctan, sinh, cosh, tanh etc. - Special functions: Bessel functions, Dawson's integral, error function, complementary error function, exponential integral, logarithmic integral, Riemann-zeta function. -------------------------------------------------------------------------------- CATEGORIES OF FINITELY PRESENTED GROUPS AND GENERALIZATIONS:- + Finitely presented semigroups + Finitely presented monoids + Finitely presented groups OPERATIONS FOR A GENERAL FP-STRUCTURE:- - Arithmetic with elements - Construction of substructures and quotient structures - Coset enumeration (Todd-Coxeter algorithm) ADDITIONAL OPERATIONS FOR PARTICULAR CATEGORIES:- Finitely Presented Groups ------------------------- - Construction of coset spaces (Todd-Coxeter algorithm) - Permutation representation on the cosets of a subgroup - Calculation with subgroups of finite index (normalizer, normal closure, intersection, core etc) - Low index subgroups (Sims backtrack algorithm) - Subgroup presentations (Reidemeister-Schreier rewriting) - Presentation simplification (Tietze transformations) - Abelian quotient - Nilpotent quotient ------------------------------------------------------------------------------- CATEGORIES OF FINITE GROUP:- + (Small) Finite groups defined by a presentation + p-groups + Soluble groups + Permutation groups + Matrix groups OPERATIONS FOR A GENERAL FINITE GROUP:- - Order of the group - Representation of subgroups, quotient groups - Permutation representation on the cosets of a subgroup - Normalizer, centralizer, normal closure, core of a subgroup - Testing elements and subgroups for conjugacy - Intersection of subgroups, Sylow p-subgroup, centre, derived subgroup - Derived-, upper central-, lower central-, p-central-, Jennings-series - Conjugacy classes - Normal subgroup lattice - Character table - Darstellungsgruppe (small groups) ADDITIONAL OPERATIONS FOR PARTICULAR CATEGORIES:- p-groups -------- Algorithms designed for finite p-groups assume that the group is defined by means of a power-commutator presentation. - Construction of the p-quotient of a finitely presented group (E O'Brien's pq program) - Construction of split extensions and wreath products - Maximal subgroups, Frattini subgroup - Omega series, agemo series - Isomorphism - Automorphism group - Classification of p-groups (E O'Brien's p-group generation program) Soluble Groups -------------- Algorithms designed for finite soluble groups assume that the group is defined by means of a power-commutator presentation. The soluble group machinery is capable of working with groups having composition length at least one hundred in the case of small primes. - Construction of a pc-presentation for a p-group given as a fp group, a permutation group or a matrix group - Construction of split extensions and wreath products - Hall pi-subgroups, Sylow basis, complement basis - System normalizer, relative system normalizer - Fitting subgroup, Carter subgroup - Elementary abelian series, chief series - Maximal subgroups, Frattini subgroup - System of double coset representatives for a pair of subgroups Permutation Groups ------------------ Most algorithms for computing structural information about permutation groups represent the group in terms of a base and strong generating set. Magma is capable of computing a base and strong generating set and hence basic structural information for groups of degree up to 1,000,000. More detailed computations can be performed in groups having degree up to 100,000. Those constructions that rely on backtrack searching utilize Jeff Leon's new partition-based algorithms. - Construction of permutation representations for classical groups: Eg PGL(n,q), PSp(n,q), PSU(n,q^2), etc - Construction of wreath products with both types of action - Induced actions on G-sets - Orbits on points, sets of points, and sequences of points - Systems of imprimitivity - Base and strong generating set (Sims-Schreier algorithms) - Stabilizer of a point, set of points, sequence of points, partition - Homomorphisms induced by actions on orbits and systems of imprimitivity - Elementary abelian regular normal subgroup of a primitive group - Socle - O'Nan-Scott decomposition of a primitive group - Composition series, composition factors - Sylow p-subgroup (By reduction to a simple group) - Schur multiplier (D Holt's package) - First and second cohomology groups (D Holt's package) - Group extensions (D Holt's package) Finite Matrix Groups over a Field; Finite Matrix Groups over the Integers ------------------------------------------------------------------------- - Generators for classical groups GL(n,q), U(n,q), Sp(n,q), Sz(q) - Stabilizer of a vector, subspace - Homomorphisms induced by actions on point and line orbits -------------------------------------------------------------------------------- CATEGORIES OF MODULE:- + Modules of n-tuples over a ring or algebra with scalar action + Modules of n-tuples over a ring or algebra with matrix action + Bimodule of linear transformations + K[G]-modules + Inner product spaces + Lattices + Finitely presented algebras OPERATIONS FOR A GENERAL MODULE:- - Arithmetic - Direct sum, tensor product, symmetric square, exterior square - Construction of submodules and quotient modules (Modules over an ED) - Union and intersection of submodules (Modules over an ED) - Membership of a submodule (Modules over an ED) ADDITIONAL OPERATIONS FOR PARTICULAR CATEGORIES:- Bimodules of Linear Transformations ----------------------------------- - Image, kernel, cokernel - Row and column operations - Echelon form (Over a field) - Elementary divisors (Over an ED) - Hermite and Smith canonical forms (Over an ED) - Solution of systems of linear equations Lattices -------- - Discriminant - LLL-reduced lattice basis - Shortest vector - Successive minima K[G]-modules, K a finite field, G a finite group ------------------------------------------------ Magma includes a range of powerful functions based on the Holt-Rees Meataxe and the Schneider endomorphism algorithm for studying modular representations. The Magma Meataxe is capable of splitting modules of dimension 20,000 in the case of small fields. - Construction of a permutation module - Submodules and quotient modules - Submodules generated by a set of vectors (Spinning algorithm) - Tensor product, induction and restriction of modules - Splitting a reducible module (Holt-Rees Meataxe) - Test a module for irreducibility, absolute irreducibility - Isomorphism of modules - Composition series and composition factors of a module - Socle series of a module - Endomorphism ring of a module - Construction of Hom(U, V), where U and V are KG-modules - Test a module for indecomposability - Vertices and sources -------------------------------------------------------------------------------- CATEGORIES OF INCIDENCE STRUCTURE:- + Graphs + Linear Codes + Designs (To come) OPERATIONS:- Graphs ------ A graph may be directed or undirected. A future release will allow coloured and weighted graphs. - Operations: union, join, product, contraction, switching etc - Standard graphs: complete, complete bipartite, kcube - Properties: connected, regular, eulerian, hamiltonian, planar - Diameter, girth, circumference - Cut-vertices, maximal independent sets, cliques - Chromatic number, chromatic index, chromatic polynomial - Graphs from groups: Cayley graph, orbital graph - Automorphism group (B. McKay's algorithm), canonical labelling - Test pairs of graphs for isomorphism - Group actions on a graph: Orbits and stabilizers of vertex and edge sequences - Symmetry properties: vertex transitive, edge transitive, k-arc transitive, distance transitive, distance regular - Intersection numbers of a distance regular graph Error-Correcting Codes ---------------------- - Construction of linear and non-linear codes - Modifying a code: extend, expurgate, lengthen, shorten, etc - Construction of basic codes: Hamming, Reed-Muller, Golay - Construction of general cyclic codes - Construction of BCH, Alternant, Goppa, QR codes - Minimum weight, weight distribution - Coset weight distribution - Syndrome decoding, BCH decoding. - Automorphism group - Group actions on a code ================= ================= Magma Computational Algebra Group, University of Sydney john@maths.su.oz.au (John Cannon) Recent advances in Computational Algebra have strongly emphasized the growing inter-dependence between the various branches of the field. Thus, the new Holt-Rees technique for splitting KG-modules makes heavy use of factorization of polynomials over finite fields. Bosma and H.W. Lenstra Jr have recently used the Groebner basis technique for polynomial rings to determine minimal systems of addition laws for elliptic curves. The Leedham-Green algorithm for computing the order of a matrix over GF(q) depends upon the ability to factor integers of the form p^n - 1. Up until the present, advanced algorithms for the various branches of algebra, geometry and number theory have tended to be implemented in packages designed for a very specific area: E.g. CAYLEY, COCOA, KANT, Macaulay, Pari, SAC, SIMATH. In order to provide mathematicians with the ability to write programs which may utilize the algorithmic machinery from these diverse fields, the Computational Algebra Group at Sydney University has designed a new system, known as MAGMA which provides a *unified enviroment* for efficient computation in the principal structures of modern algebra viz. groups, rings, fields and modules. This system extends the ideas of *structural computation*, successfully developed for group theory over the past two decades in the CAYLEY system, to algebra generally. MAGMA has a functional-style programming language in which the principal data types are sets, sequences, structures (magmas) and mappings. The kernel contains efficient implementations of many of the principal algorithms in Module Theory, Ring Theory, Group Theory, Algebraic Number Theory and Algebraic Combinatorics. This system is designed to support computation in algebra, number theory, geometry and algebraic combinatorics. The system has an advanced functional programming language with many novel features designed for concise and efficient specification of algebraic algorithms. The system has coded into its kernel the fundamental algorithms for ring theory (polynomial rings, matrix rings, integer rings), field theory (general algebraic number fields -- KANT2, finite fields, real and complex fields), module theory, group theory (fp groups, permutation groups, soluble groups and matrix groups) and algebraic combinatorics (coding theory and graph theory). The flavour of the language may be gained from the following sample of code partially implementing polynomial factorization over Z. ------------------------------------------------------------------------------- function SquarefreeFactorization(apoly) P := Parent(apoly); p := Characteristic(CoefficientRing(P)); deriv := Derivative(apoly,1); if IsZero(deriv) then /* apoly = u(x^p) = u(x)^p */ acoeffs := Coefficients(apoly); u := &+[acoeffs[i]*x^((i-1) div p) : i in [1 .. #acoeffs]]; v := $$(u); return &cat[v:i in [1 .. p]]; end if; g := Gcd(apoly, deriv); if IsOne(g) then return [apoly]; else return $$(g) cat $$(apoly div g); end if; end function; function Qmatrix (apoly) P := Parent(apoly); n := Degree(apoly); CField := CoefficientRing(P); // GF(p^d) p:=Characteristic(CField); d:= Degree(CField); q:=p^d; Q := quo

; cseq := [Coefficients(Q!1)]; //x^0 xq := x^q; xqk := xq; for k in [1 .. n-1] do cseq := cseq cat [Coefficients(xqk)]; xqk := xqk*xq; // Multiply in Q end for; // A sequence of sequences qseq := // Just pad each row out with zeros return MatrixRing(CField, n) ! qseq; end function; function Hensel(f, g1, h1, k) Rp := Parent(g1); // Zp[x] p := Modulus(CoefficientRing(Rp)); Zx := FreeRing(Integers(), ["x"]); g := g1; h := h1; pi := p; one, grecip, hrecip := Xgcd(g1, h1); for i in [2 .. k] do pim1 := pi; pi := pi*p; Zpi := FreeRing(Integers(pi), ["x"]); Zpi1 := FreeRing(Integers(pi*p), ["y"]); Disc:=Zpi1!(Zx!(Zpi!f-Zpi!g*Zpi!h)/pim1); gcorr:=Rp!(Disc*Zpi1!hrecip) mod g1; hcorr:=Rp!(Disc*Zpi1!grecip) mod h1; g := Zpi!g + pim1 * Zpi!gcorr; h := Zpi!h + pim1 * Zpi!hcorr; end for; return [g,h]; end function;