Summary

Documentation

• Handbook: There are 18 new chapters in the Handbook.

• Handbook: The Handbook now includes bibliographies for each chapter, and some information concerning the algorithms used has been provided for a selection of the functions.

• Help System: A new help system has been developed by Claus Fieker. The system is html-based and allows the user to quickly access any Handbook entry via the usual help request from within Magma. To access the new help system, the following line should be placed in the user's startup file:
  SetHelpUseExternalBrowser(true);

Groups

• Permutation Groups: An algorithm for determining the maximal subgroups of a permutation group is provided. This is applicable to any group for which the non-abelian composition factors either have order less than $1.6 \times 10^7$ or have a permutation representation of degree less than 32.

• Permutation Groups: The machinery for finding all conjugacy classes of subgroups has been extended to a much larger class of groups. In particular, the former limitation that the trivial Fitting quotient have order less than 216,000 has been removed. Variations are provided to find all conjugacy classes of subgroups satisfying some condition.

• Permutation Groups: The maximal subgroup algorithm is used as the basis for an algorithm for determining all subgroups whose index is less than some given bound. This is much more efficient than finding all subgroups and selecting those which satisfy the index condition.

• Permutation Groups: A new algorithm for finding the automorphism group of a permutation group is also included. A variation may be used to determine whether two permutation groups are isomorphic.

• Matrix Groups: New algorithms for computing the conjugacy classes of elements and the maximal normal p-subgroup in a finite matrix group have been installed.

• Matrix Groups: Several functions for analysing the action of a matrix group over a finite field on subspaces of the underlying natural vector space have been introduced. These functions are designed to handle situations where the orbits may be large.

• Finitely Presented Groups: Much of the basic infrastructure for finitely presented groups has been redesigned, yielding improved performance and greatly increased applicability of key functions for fp-groups.

• Finitely Presented Groups: New versions of the algorithms for coset enumeration, simplification of presentations by Tietze transformations, Reidemeister-Schreier rewriting and computation of p-quotients have been installed. An interactive coset enumeration facility is now available.

• Finitely Presented Groups: The function Order for finitely presented groups has been revised and now uses a much more sophisticated strategy for determining the order of a (finite) group or for proving that the group is infinite.

• Polycyclic Groups: The functionality of the new category of polycyclic groups introduced in V2.7 has been greatly increased. In particular, algorithms have been implemented that compute the following: a normal series where the factors are either elementary abelian p-groups or free abelian groups; the Fitting subgroup; the Fitting series, the upper central series; the centre. For the case of nilpotent groups, functions that compute normalizers and centralizers have been installed.

• p-Groups: New implementations by Eamonn O'Brien of an algorithm for computing the automorphism group of a p-group and also an algorithm for generating p-groups have been installed. The new p-group generation implementation overcomes problems associated with file handling that affected the previous implementation.

• Generic Abelian Groups: A new category has been created for generic (finite) abelian groups. The creation of a generic abelian group is a new feature which allows the user to create an abelian group over any domain given that an identity and a group operation have been defined. Features include finding the order of an element, determining a presentation from generators, and computing the discrete logarithm of an element.

• Subgroups of PSL(2, R): A package for working with congruence subgroups of PSL(2, R) has been developed by Helena Verrill. The package includes graphics facilities which allow the user to produce pictures of fundamental domains.

• Databases: Several new databases of groups have been created, e.g. for perfect groups, almost simple groups, rational maximal finite matrix groups and finite quaternionic matrix groups.

Groups of Lie Type

• Root Datum: A data type has been introduced for root datum of groups of Lie type.

• Coxeter Groups: The module for Coxeter groups has been considerably expanded.

• Lie Groups: A data type has been introduced for groups of Lie type. The basic group operations have been implemented over any field.

Basic Rings

• Integers: An experimental implementation of the number field sieve (NFS) for factoring large integers is now available.

• Integers: The Factor database maintained by Richard Brent has been updated. It now contains 221,188 factors f of integers $a^n \pm 1$, where a < 10000, n < 10000, and f > 10⁹.

• Univariate Polynomial Rings: Polynomials over the integers or rationals are now factored by the new algorithm of Mark van Hoeij. The search for the correct combination of modular factors (which has exponential worst-case complexity in the standard Berlekamp-Zassenhaus algorithm) is performed by van Hoeij's algorithm, which efficiently finds the correct combinations by solving a Knapsack problem via the LLL lattice-basis reduction algorithm.

Extensions of Rings

• Galois Rings: Basic facilities for computing with Galois rings have been implemented.

• Number Fields: Algebraic number fields and their orders have been substantially revised in Magma V2.8. A new field type has been created for the field of fractions of an order of a number field. More functionality has been provided for both absolute and relative fields and orders.

• Number Fields: Factorization of univariate polynomials defined over number fields has become enormously more efficient through use of the van Hoeij ideas. It is now possible to factor a degree 15 polynomial over a degree 15 extension of $\mbox{\bf Q}$ in a few seconds.

• Number Fields: Multi-step relative extensions are now fully supported with most operations for absolute extensions generalized for this situation. In particular, factorization and integral closure are now supported for relative extensions.

• Number Fields: Some restrictions on the creation of number fields (orders) have been removed. Thus, it is now possible to create a field or order using a non-monic polynomial. Further, it is possible to construct non-simple and linear extensions.

• Number Fields: Highly efficient arithmetic has been implemented for residue class rings. In addition, the calculation of unit groups of such rings is supported at least for quotients of absolute maximal orders.
• Number Fields: It is now possible to form the completion of a number field at a (finite) prime.

• Number Fields: Code implemented by Claus Fieker computes the p-Selmer group at a list of primes.

• Number Fields: Initial machinery has been provided for class field theory. In particular, a new type for abelian fields has been provided. It is now possible to construct ray class groups and class fields based on them (i.e. in terms of defining equations).

• Number Fields: It is now possible to compute the relative Galois group and relative subfields of a one-step relative extension of $\mbox{\bf Q}$.

• Quadratic Fields: Quadratic fields have been redesigned so that they are now number fields with the addition of some special code implementing fast algorithms peculiar to quadratic fields. Thus, for the first time all number field operations are supported for quadratic fields.

• Cyclotomic Fields: Cyclotomic fields have been redesigned so that they are now number fields with the addition of some special code implementing fast algorithms peculiar to cyclotomic fields. Thus, for the first time all number field operations are supported for cyclotomic fields.
• Function Fields: Machinery for constructing and working with differentials has been introduced. It is possible to compute the space of holomorphic differentials for a given divisor. Other operations include computing the valuation of a differential at a place, computing the residue of a differential at a place of degree 1 and working with higher differentiations.

• Function Fields: A function that determines the sequence of Weierstrass places has been developed. Related functions compute the sequence of global gap numbers of a divisor or the sequence of gap numbers of a divisor at a place of degree 1.

• Function Fields: The divisor class group of a global function field may be computed using an algorithm and implementation due to Florian Heß. This also allows other related information to be determined: e.g., unit group, S-class group, S-units and S-regulator for a finite set of places S.

• Function Fields: Given the elliptic function field E: y² + xy + x³ + ax² + b defined over GF(qⁿ), a function is provided that computes a hyperelliptic function field in the Weil restriction of E over GF(q). This feature is of particular interest to cryptographers.

• Function Fields: A generic algorithm is provided for the factorization of univariate and multivariate polynomials over function fields.

• Function Fields: The Galois group and lattice of subfields may be found for a function field using code implemented by Katharina Geißler.

Commutative Algebra

• Ideal Theory: It is now possible to compute Gröbner bases of ideals of polynomial rings defined over Euclidean rings (including the important case of the ring $\mbox{\bf Z}$). Such Gröbner bases are constructed by an extension of Jean-Charles Faugère's F₄ algorithm which uses sparse linear algebra (algorithm due to Allan Steel). Many of the standard functions provided for ideals in polynomial rings defined over fields are now generalized to ideals in polynomials rings defined over Euclidean rings.

Linear Algebra and Module Theory

• Matrices: Several new advanced algorithms for matrices over $\mbox{\bf Z}$ or $\mbox{\bf Q}$ have been implemented (and more will follow in the future). The new algorithms are for computing determinants, characteristic polynomials and minimal polynomials.

• Modules over Orders: Modules over orders are now supported.

Algebraic Geometry

• Schemes: The algebraic geometry types together with their basic functionality have been moved into the kernel. This includes the integration of many of the specialised curve types such as elliptic and hyperelliptic curves. This significantly increases the power of the geometry types, allowing the user to apply the functionality of both a specialised curve type and the general scheme type to a single object. The change also makes available many generic constructors and standard set and sequence operations, which were previously not available for the geometry types.

• Schemes: Maps between schemes have been enhanced with the provision of new constructors and the ability to calculate images and pullbacks available in more circumstances. Maps may now be defined between actual schemes now rather than just between affine or projective spaces.

• Curves: Plane curves have been tied very closely to the function field machinery in Magma. The result is that computations with divisors and their Riemann-Roch spaces can be made entirely in the geometric context. The applications include: gap numbers, canonical embeddings of curves, class group computation over finite fields, constructions of geometric codes from curves and many other standard methods in the geometry of curves.

• Curves: A new facility for computing with plane conic curves has been written. Its major feature is an implementation of a new algorithm by John Cremona (Nottingham) to find points with reduced coordinates on conics defined over the rational numbers. This implementation is very fast, improving on Cremona's initial test timings.

• Elliptic Curves: Elliptic curves are now scheme types and inherit all of the appropriate scheme functionality. In particular, all of the machinery for divisors and differentials now applies to elliptic curves. Subgroup schemes of elliptic curves are now also schemes. John Cremona's database of elliptic curves has been updated to conductor 10,000.

• Hyperelliptic Curves: Machinery for computing the automorphism group of a hyperelliptic curve has been implemented by Michael Stoll. Pierrick Gaudry has implemented a number of methods for counting points on the Jacobian of a hyperelliptic curve. These include the Schoof algorithm for a genus 2 curve. Code for determining Igusa invariants has been provided by Everett Howe while Pierrick Gaudry has implemented an algorithm for constructing a genus 2 curve from the Igusa invariants.

• Modular Curves: A package for modular curves has been developed by David Kohel of the Magma group. A modular curve is defined in terms of standard affine modular equations which are stored in precomputed databases. The possible model types are ``Atkin'', ``Canonical'', and ``Classical''.

• Modular Forms: A package for modular forms developed by William Stein is now included. Facilities include the computation of a basis of modular forms on $\Gamma_1(N)$, the computation of all newforms of given level, and the decomposition into Eisenstein, cuspidal, and new subspaces.

• Brandt Modules: A package for Brandt modules has been developed by David Kohel. Facilities include the construction of a Brandt module on the left ideal class of a definite order in a quaternion algebra over $\mbox{\bf Q}$, the decomposition of a Brandt module under the action of Atkin-Lehner and Hecke operators and the construction of the Eisenstein and cuspidal subspaces.

• K3 Surfaces: A database of K3 surfaces has been added. It contains characteristic data for K3 surfaces embedded in weighted projective spaces in codimension up to 4. The functions used to create the database are also included so that users can extend the database or create similar databases.

• Handbook: All geometric chapters of the Handbook have undergone major revision. Many more examples have been included, some of which are extended calculations which illustrate different parts of the new geometry packages working together.

Incidence Structures

• Graphs: The nauty program due to Brendan McKay for finding automorphisms in graphs has been updated to the latest version (2.0) and its user interface within Magma has been enhanced. This new version of nauty is often much faster than the previous version installed within Magma.

• Graphs: A database of strongly regular graphs due to Brendan McKay et al is now available.

• Graphs: A program for the orderly generation of graphs satisfying a range of conditions, written by Brendan McKay, is now accessible from within Magma.

Coding Theory

• Codes over Fields: Magma V2.8 incorporates a database containing constructions of the best known linear codes over F₂ of length up to 256. The codes of length up to 36 are optimal. The database is complete in the sense that it contains a construction for every set of parameters. Thus the user has access to 33,152 best-known binary codes. Similar databases for other small fields will be added in the near future. The implementation of this database has been a joint project with Markus Grassl.

• Codes over Fields: Functions are provided to construct Algebraic-Geometric codes.

• Codes over Rings: Magma includes facilities for linear codes defined over $\mbox{\bf Z}_4$ for the first time.

Optimization

• Linear Programming: Basic facilities are provided for solving linear programming and integer linear programming problems.