Date: Thu, 3 Jul 1997 13:25:20 +1000 From: magma@maths.usyd.edu.au (Magma Computer Algebra System) To: hwloidl@risc.uni-linz.ac.at Subject: Announcement of MAGMA V2.2 --------------- | MAGMA V2.2 | --------------- Magma V1 was released in December 1993. Since then it has undergone enormous expansion and many original modules have been rewritten. This document gives a terse summary of the scope and capabilities of the current release V2.2 (some information is included about the the October, 1997 release (V2.3)). Timing data refers to Magma running on a SUN Ultra 2 with a 200 MHz processor. The Magma home page http://www.maths.usyd.edu.au:8000/comp/magma/Overview.html provides a much more detailed listing of facilities together with examples. ------------ | PHILOSOPHY | ------------ Magma is a Computer Algebra system designed specifically for computation in all branches of algebra, number theory and geometry (and for other areas that are heavily algebraic in nature). Features of its philosophy include: ALGEBRAIC DESIGN PHILOSOPHY: The design principles underpinning both the user language and system architecture are based on ideas from universal algebra and category theory. The language attempts to approximate as closely as possible, the usual mathematical modes of thought and notation. In particular, the principal constructs in the user language are set, (algebraic) structure and morphism. UNIVERSALITY: In-depth coverage of all the major branches of algebra, number theory, algebraic geometry and finite incidence geometry. INTEGRATION: The facilities for each area are designed in a similar manner using generic constructors wherever possible. The uniform design makes it a simple matter to program calculations that span different classes of mathematical structures or which involve the interaction of structures. PERFORMANCE: The intention is that Magma provide the best possible performance both in terms of the algorithms used and their implementation. The design philosophy permits the kernel implementor to choose optimal data structures at the machine level. Most of major algorithms currently installed in the Magma kernel are state-of-the-art and give performance similar to, or better than, specialized programs. ------------------ | SUMMARY OF AREAS | ------------------ The mathematical structures implemented in the Magma kernel may be loosely grouped into eight areas: * Semigroups, monoids, automata, rewriting systems. * Groups: Finitely-presented groups, fg abelian groups, black-box groups, permutation groups, matrix groups, soluble groups. * Commutative rings: Ring of integers, polynomial rings, power series rings, orders, valuation rings, rings of group invariants. * Fields: Finite fields, number fields, function fields, local fields, fields of Laurent series, real and complex fields. * Modules: Vector spaces, R-modules over fields, R-modules over EDs, R-modules over K[x_1, ..., x_n], K[G]-modules, Hom(M, N), lattices. * Algebras: General finite-dimensional (fd) algebras, fd associative algebras, fd Lie algebras, matrix algebras, group algebras, finitely-presented associative algebras. * Algebraic geometry: Elliptic curves, curves of genus greater than 1, algebraic varieties. * Combinatorics: Counting theory, directed and undirected graphs, incidence structures, designs, planes, codes. -------------- | GROUP THEORY | -------------- ________________________________________________________________________ Finitely-presented groups Automatic groups Abelian groups Blackbox groups Soluble groups Permutation groups Matrix groups Representations Cohomology ________________________________________________________________________ FINITELY-PRESENTED GROUPS: A key component is the Todd-Coxeter procedure for enumerating cosets developed by George Havas. Built on top of this is machinery for computing properties of subgroups of finite index. The standard quotient constructions (abelian quotient, p-quotient and soluble quotient) are provided. Eamonn O'Brien's p-group generation package is also included. A particularly efficient search for low index subgroups (due to Sims) allows the user to look for large subgroups. Subgroup rewriting is included and the new Tietze simplification program of Havas and Lian provides fast simplification of presentations. The KBMAG program developed by Derek Holt will provide support for automatic groups in V2.3. SOLUBLE GROUPS: Given a (finite) soluble group defined by means of a polycyclic presentation, a large family of algorithms designed to take advantage of this representation is provided. These include the finding of characteristic subgroups, the computation of structural information specific to soluble groups (e.g., Hall subgroups, Sylow basis), and the determination of maximal subgroups, normal subgroups, and all conjugacy classes of subgroups. For example, the maximal subgroups of the Burnside group B(2, 6) of order 2^28 3^25, may be found in 115 seconds. In the particular case of p-groups, specialized techniques are often employed. In particular, the O'Brien algorithm for computing automorphism groups and testing isomorphism of p-groups are available. Automorphism groups of soluble groups will be available in the near future. PERMUTATION GROUPS: A permutation action may be defined on any finite set using a G-set mechanism. A huge range of permutation group algorithms (some 300) are incoporated -- many of them developed specifically for Magma. The key to structural computation in large permutation groups is the use of a base and strong generating set (BSGS). A range of techniques is provided for finding a BSGS, including the Brownie-Cannon-Sims verification procedure (applicable to degrees in excess of a million). Backtrack searches are performed using Jeff Leon's PERM package. For analyzing the structure of large permutation groups, reduction algorithms are often employed. In particular, tools are provided to decompose a primitive group according to the O'Nan-Scott theorem. For example, using a reduction algorithm, the Sylow 2-subgroup of the wreath product of AGL(7, 3) with A5 (a group of degree 10,935 and order 1.30 x 10^134) is found in 1,035 seconds. A new family of algorithms has been developed for computing conjugacy classes of elements, normal subgroups and all subgroups; it takes 2285 seconds to compute the 15,124 classes of subgroups of 2^6 A8 (of order 1,290,240). MATRIX GROUPS: For finite groups of moderate degree and order, where an orbit of length less than a few million can be found, BSGS techniques are used. Structural information such as characteristic subgroups, local subgroups, and conjugacy classes may then be computed. For groups of large degree over finite fields, the specialized machinery developed by Cellar, Holt, Leedham-Green, O'Brien, Pye and others will become available in V2.3. The Magma implementation of the Niemeyer-Praeger algorithm is capable of recognizing classical groups having degrees up to 10,000. For example, SL(10000, 2) is recognized in 30,500 seconds. REPRESENTATIONS AND COHOMOLOGY: A carefully tuned Dixon-Schneider algorithm is employed for finding character tables. Extensive support is provided for computing with KG-modules, including algorithms for composition series, submodule lattice (if K is a finite field), testing equivalence, endomorphism ring and testing indecomposability. In the case where K is a small finite field, composition series may be found for modules of dimension up to 20,000, while (in V2.3), if K is the rational field, composition series may be found for dimensions up to 500-600. The first and second cohomology groups, together with all extensions of a module by a group, may be computed in the case of a permutation group. ------------------- | COMMUTATIVE RINGS | ------------------- ________________________________________________________________________ Ring of integers Polynomial rings Rings of invariants Orders of fields Valuation rings Power series rings ________________________________________________________________________ INTEGERS: A new fast integer arithmetic package was released in V2.2. Among many highlights, it employs the Karatsuba algorithm for products, an exact divide function and the Weber accelerated GCD algorithm. Assembler macros are used for critical operations. Integer multiplication is 25-40% faster than GNU gmp: the multiplication of two 10,000 bit integers takes 0.005 seconds. Integer factorization is performed using versions of the ECM and MPQS algorithms developed by Arjen Lenstra. An 80-digit integer that is the product of two 40-digit primes may be factored in about 10 hours. Francois Morain's ECPP program is used for proving primality, taking about 800 seconds to prove a 200-digit integer prime. UNIVARIATE POLYNOMIALS: An extensive module for computing in polynomial rings over commutative rings is provided, and includes very fast imple- mentations of factorization algorithms over finite fields, integers and p-adics. Algorithms are also provided for factorization over number fields and function fields. Magma factors the first challenge polynomial of Zimmermann (degree 156, 78 digit coefficients over Z) in 6 seconds. (See http://www.loria.fr/~zimmerma/mupad). MULTIVARIATE POLYNOMIALS: Included are algorithms for GCDs and factor- ization over F_q, Z, Q, number fields and rational function fields (over F_q and Q); factorization over F_q, Z and rational function fields (over F_q and Q). A comprehensive Groebner basis (GB) package is provided which, in addition to a very fast implementation of the standard GB algorithm includes both a Groebner Walk and a Hilbert-driven GB algorithm. All the standard constructions associated with ideals: variety, radical, dimension, primary decomposition and Hilbert series are provided. Sample timings of the Magma GB include: - Katsura-5 problem (lex order) -- 4.5 seconds; - Cyclic 6-th roots problem (grevlex order) -- 2.5 seconds; - Cyclic 7-th roots problem (grevlex order) -- 1200 seconds. All examples are from the POSSO test suite (posso@dm.unipi.it). INVARIANT RINGS: A module for constructing both characteristic 0 and modular invariants of finite groups has been developed by Gregor Kemper and Allan Steel. This includes a new algorithm for computing primary invariants that guarantees the degrees of the invariants constructed are optimal (with respect to their product and then sum). Both primary and secondary invariants are available and many properties of the invariant ring may be computed. The optimal primary invariants (degrees 3, 5, 8 and 12) for the 4-dimensional representation of the alternating group A_5 over GF(2) are found in 1.5 seconds. -------- | FIELDS | -------- ________________________________________________________________________ Rational field Finite fields Number fields Quadratic fields Cyclotomic fields Function fields Real & complex fields Local fields Laurent series fields ________________________________________________________________________ FINITE FIELDS: Finite field arithmetic is optimized through use of specialized representations for fields GF(p^n), depending upon the characteristic p and exponent n. Of particular note, is the ability to efficiently solve the compatibility problem for embedded subfields. In particular, if a field extension if constructed in two different ways, a compatible embedding in an appropriate overfield is constructed. NUMBER FIELDS: Facilities for general number fields are provided by the KANT package. The core consists of machinery for performing arithmetic with arbitrary orders and their ideals. The major capabilities include facilities to determine the maximal order (round 2 and 4 algorithms), class group, unit group and Galois group (up to degree 12). A very fast algorithm is available for determining subfields. Algorithms for solving norm equations, relative norm equations, Thue equations and unit equations are included. The extension of Q by a root of x^9 - 57*x^6 + 165*x^3 - 6859 is shown to have class group Z/3Z and unit group Z/2Z + Z + Z + Z + Z in 143 seconds. The Galois group (of order 18) is found in 1 second. QUADRATIC FIELDS: Magma contains special code for quadratic fields, based on code from the PARI package. In particular, a subexponential algorithm for computing the class number is used. Binary quadratic forms with the usual reduction and composition operations provide a convenient means of computing in class groups. FUNCTION FIELDS: Fields of rational functions are available in V2.2. The first release of the KANT facility for global function fields (i.e., finite degree extensions of F_q(x)) will appear in V2.3. A fundamental operation is the construction of the integral closures (maximal orders) of F_q[x] and the valuation ring at the infinite place. Reduced integral bases may be found using a reduction algorithm of Pohst and Schoernig. Ideals of orders may be defined and a complete set of arithmetic operations on these ideals are implemented. In particular, the factorization of an ideal may be obtained. Important invariants of a field such as its genus may be found. Finally, independent and fundamental units may be constructed. COMPLEX FIELD: Real and complex arithmetic is provided by the PARI package. This package includes a huge number of functions of interest to number theorists including logarithmic and polylogarithmic functions, elliptic and modular functions, Gamma and Bessel functions and, the Riemann zeta-function. Xavier Gourdon's implementation of the Schoenhage splitting circle method for computing the roots of an exact polynomial to a specified precision is included. As an example, Magma takes 930 seconds to determine the zeros of the degree 100 Laguerre polynomial to an accuracy of 100 decimal digits. LOCAL FIELDS: p-adic rings and fields are available in V2.2. General finite extensions of p-adic rings (fields) will appear in V2.3. Apart from arithmetic, the facilities include Hensel lifting, automorphisms, factorization of polynomials and linear algebra over local fields. ---------------------- | MODULES AND LATTICES | ---------------------- ________________________________________________________________________ R-modules K[G]-modules Hom modules Lattices ________________________________________________________________________ MODULES: An R-module M is viewed as a collection of n-tuples with the action given by n x n matrices. Calculation with submodules requires M to be defined over either a field, an euclidean domain or a polynomial ring over a field. In the case of modules M and N defined over either F_q or a number field, Magma can find composition series, composition factors, Jacobson radical, socle series, End(M) and Hom(M, N). For example, taking the simple group of Rudvalis and considering its permutation module P of degree 4,600 over F_2, Magma determines the irreducible constituents of P in 720 seconds. If the base ring is restricted to a finite field, maximal and minimal submodules, and indeed the complete submodule lattice may be found. HOM MODULES: Given R-modules M and N, the set of all homomorphisms from M to N, Hom(M, N), may be created as a module. In particular, rectangular matrices are regarded as elements of an appropriate Hom module. In addition to module-type operations, Hom modules support canonical forms and morphism-type operations: image, kernel, cokernel etc. In the case of Z-modules, the Hermite Normal Form and Smith Normal Form algorithms of Havas have been implemented. Given a 1081 x 2657 integer matrix corresponding to the abelianization of a certain finitely presented group, Magma computes its elementary divisors, [2, 2, 2, 2, 102, 37842], in 82 seconds. MODULES OVER K[x_1, ..., x_n]: Let R denote the ring K[x_1, ..., x_n], where K is a field. Since R is not a PID, Groebner basis techniques are employed to construct standard basis for submodules. This allows all the usual submodule operations to be realized. Functions are provided for computing syzygy modules and free resolutions. For homogeneous modules, it is possible to find minimal bases and Hilbert series. LATTICES: A powerful family of LLL algorithms based on the FP-LLL algorithms of Schnorr and Euchner are included. Different variants on the main algorithm are provided to achieve optimization across a wide range of situations with particular attention being given to Z-lattices. Notable algorithms include enumeration of shortest vectors, automorphism groups and isomorphism testing. Given the 24-dimensional Leech lattice, Magma enumerates the 98,280 (normalized) shortest vectors in 6.8 seconds and finds its automorphism group in 175 seconds. The LLL algorithm can find difficult Z-linear dependencies among the rows of matrices having dimensions well over 500. ---------- | ALGEBRAS | ---------- ________________________________________________________________________ Finite dimensional algebras Finite dimensional associative algebras Matrix algebras Group algebras Lie algebras (V2.3) Finitely presented associative algebras ________________________________________________________________________ STRUCTURE CONSTANT ALGEBRAS: A general finite dimensional algebra may be defined by taking a free module over a field or Euclidean Domain (ED) and giving a rule for multiplying basis elements (SC algebra). Subagebras as well as left, right and two-sided ideals may be defined. The standard arithmetic operations with ideals (membership, sum, intersection, product etc) are available. In the case of an algebra defined over a field $K$, quotient algebras, composition series, the composition factors and the Jacobson radical may be constructed. If, in addition, $K$ is finite the maximal and minimal left (right, two-sided) ideals, etc., may also be found. ASSOCIATIVE ALGEBRAS: If a SC algebra is associative, additional operations are available. These include centre, commutator ideal, centralizer, idealizer, left and right annihilators, and the construction of matrix representations. MATRIX ALGEBRAS: While a matrix algebra may be defined over any ring R, most non-trivial computations require R to be an ED. If R is a field, a new fast algorithm due to Allan Steel is used to construct the various matrix canonical forms: Jordan, generalized Jordan, rational, primary rational etc, while if R is an ED, recent algorithms of Havas and others are used to compute characteristic polynomials and the Hermite and Smith normal forms. Given a 100 x 100 matrix over Z with random one-digit entries, Magma finds its Smith form in 40 seconds and its characteristic polynomial in 270 seconds. The order of a unit over a finite field is found using the very efficient algorithm of Leedham-Green. All of the operations listed for associative algebras also apply to matrix algebras. GROUP ALGEBRAS: Given a finite group of moderate order, its algebra over a field or ED may be created. In addition to the standard operations for SC associative algebras, specialized operations such as computing the augmentation ideal are provided for group algebras. FINITELY-PRESENTED ASSOCIATIVE ALGEBRAS: Given an algebra over a field, a Todd-Coxeter procedure is used to construct matrix representations of (finite dimensional) quotient algebras (Linton vector enumerator). ----------------- | ELLIPTIC CURVES | ----------------- ________________________________________________________________________ Elliptic curves over a field or Z ________________________________________________________________________ ELLIPTIC CURVES: Elliptic curves may be defined over any field or Z. Standard models are provided together with heights and invariants. For curves with integer coefficients, invariants such as conductor, regulator, and local information (Tate's algorithm) are available. For curves over Q, the Mordell-Weil rank and group is computed using code based on John Cremona's MWRANK program. Magma takes 280 seconds to determine that the curve y^2 + x*y = x^3 - 215*x + 1192 has group Z_2 x Z x Z, and 100 seconds to determine that the curve y^2 = x^3 + 36861504658225*x^2 + 1807580157674409809510400*x has rank 13. ---------------------- | INCIDENCE STRUCTURES | ---------------------- ________________________________________________________________________ Enumerative combinatorics Graphs Incidence structures Near-linear spaces Linear spaces t-designs Projective planes Affine planes Linear codes ________________________________________________________________________ GRAPHS: Graphs may be directed or undirected. In addition, their vertices and/or their edges may be labelled. Algorithms are implemented for all the standard constructions and properties. Brendan McKay's automorphism program (nauty) is used for computing automorphism groups and for testing pairs of graphs for isomorphism. In accordance with the Magma philosophy, a graph may be studied under the action of an automorphism group. Using the G-set mechanism, an automorphism group can be made to act on any appropriate set of configurations. INCIDENCE STRUCTURES: General incidence structures provide a universe in which families of incidence structures satisfying stronger conditions (linear spaces, t-designs, etc) reside. Tools are provided for constructing designs from difference sets, Hadamard matrices, codes and other designs. The standard families of difference sets are incorporated. A major feature is the ability to compute automorphism groups and to test pairs of incidence structures for isomorphism. FINITE PLANES: Although finite planes correspond to particular families of designs, separate categories are provided for both projective and affine planes in order to exploit the rich structure possessed by these objects. Apart from elementary invariants, a reasonably fast method is available for testing whether a plane is desarguesian. Among special configurations of interest, a search procedure for k-arcs is provided. A specialized algorithm developed by Jeff Leon is used to compute the collineation group of a projective plane while the affine case is handled by the incidence structure method. The collineation group (order 2^3 3^8) of a ``random'' projective plane of order 81 supplied by Gordon Royle was found in 1,202 seconds. As with graphs and designs, the G-set mechanism gives the action of the collineation group on any appropriate set. LINEAR CODES: Currently, the coding theory module is designed for linear codes over finite fields though this will be extended to linear codes over finite rings in the near future. A very large number of constructions are supported together with the determination of all the standard invariants. Carefully crafted algorithms are provided for computing the minimum weight and weight enumerator. For example, computation of the minimum weight (15) of a [79, 40, 15] quadratic-residue code takes 23 seconds; computation of the weight distribution of the [64, 22, 16] Reed-Muller code (r = 2, m = 6) takes 2.9 seconds. Automorphism groups may be computed over any field GF(p), p a prime, and GF(4), again using Leon's PERM package. Finally, some standard decoding techniques are supported. ________________________________________________________________________ MAGMA HOMEPAGE: The reader is referred to the Magma home page for a more detailed listing of facilities together with numerous examples. http://www.maths.usyd.edu.au:8000/comp/magma/Overview.html GETTING MAGMA: For more information, or to order the system, contact: Email: magma@maths.su.oz.au Telephone: +61 2 9351 3338 Fax: +61 2 9351 4534 Smail: Magma Group, Mathematics, University of Sydney, NSW 2006, Australia --------------------------------------------------------------------------Hans-Wolfgang Loidl <hwloidl@dcs.glasgow.ac.uk> Last modified: Wed Jul 9 02:08:46 1997 Stardate: [-31]9605.23