Summary

Groups

• Finite Groups: A number of algorithms that perform non-constructive and constructive black-box recognition are available for the first time. These include non-constructive recognition of simple groups; non-constructive recognition of classical groups in their natural representation; constructive recognition of linear groups using the Kantor-Seress algorithm; constructive recognition of the alternating/symmetric group using either Bratus-Pak or Beals et al. A datatype and operations for black box groups have been added to support the implementation of group recognition algorithms.

• Finite Groups: The database of maximal subgroups and automorphism groups for almost simple groups has been extended. This database is being constructed firstly, by determining all maximals generically for each classical family in each dimension and, secondly, by storing a description of the maximals for a particular group in the case of exceptional groups and sporadic simple groups. The following groups are included for the first time: L(2, q), L(3, q), L(4, q), L(5, p), (q a prime power), L(d, 2) for d$\le$14, U(6, 2), U(3, 9) Sp(8, 2), Sp(6, 3), O(7, 3), O⁺(8, 2), O^-(8, 2), O⁺(10, 2), O^-(10, 2), G₂(4), G₂(5), ³D₄(2), ²F₄(2)', Sz(32), McL, He, Co₃, Co₂, and Fi₂₂. The expansion of the maximal subgroups database automatically expands the range of applicability of other key group structure functions such as subgroups, low index subgroups, automorphism groups, character tables and representations.

• Finite Groups: Much of the information in the online Atlas of Simple Groups maintained by Robert Wilson at Birmingham is now available as a Magma database. In particular, the list of ordinary and modular representations is available.

• Permutation Groups: A number of major improvements to the fundamental algorithms for permutation groups have been made. In the case of many hard examples, these changes will significantly reduce the execution time. Of particular note, the computation of a BSGS in a permutation group will often be much faster in harder cases. Other major speed-ups affect the computation of conjugacy classes of elements and subgroups.

• Braid Groups: In 2003, Volker Gebhardt developed a much faster test for conjugacy of elements in a braid group by replacing the earlier notion of super summit set by a much more powerful invariant, the ultra summit set. Functions for computing ultra summit sets are now included in Magma and both conjugacy testing and conjugacy search now use ultra summit sets instead of super summit sets. While super summit sets in general cannot be computed for products of more than 4 simple elements in a braid group on 8 strings, tests show that ultra summit sets can be computed successfully for elements constructed as product of 1000 random simple elements in a braid group on 100 strings.

• Automorphisms/Isomorphisms: It is now possible to determine isomorphism of two finite groups where either can be a permutation group, matrix group or pc-group. For example, it is possible to test whether a matrix group is isomorphic to a permutation group.

• Finitely Presented Groups: A Magma database comprising the fundamental groups of the 10,986 small-volume closed hyperbolic manifolds in the Hodgson-Weeks census has been included.

Basic Rings

• Multivariate Polynomial Rings: Factorization of bivariate polynomials over all supported rings is now accomplished by a new algorithm which extends van Hoeij's knapsack ideas for Z[x] to solve the combination problem for GF(q)[x, y]. The new algorithm runs in polynomial time and performs extremely well in practice. General multivariate factorization has been rewritten from scratch and is now reduced to this new bivariate algorithm. Most of the algorithms for multivariate GCD and resultant computation have also been rewritten from scratch. In particular, a faster interpolation algorithm is used for resultants, and there are several new heuristics.

Commutative Algebra

• Ideal Theory and Gröbner Bases: A new highly optimized implementation of the Faugère F4 algorithm for computing Gröbner bases (GBs) over fields is included in V2.11. The algorithm uses sparse linear algebra and has specialized vector representations for all types of finite fields, and an asympotically-fast modular algorithm for the rationals. Special techniques are used for systems over GF(2). The Cyclic-7 grevlex GB takes 2.2 seconds on an Athlon 2800+ XP PC and the Cyclic-9 grevlex GB over Q takes 7.5 days on a 750MHz Sunfire v880 (one sequential processor, 11GB memory used). See http://magma.maths.usyd.edu.au/users/allan/gb/.

• Ideal Theory: The integral closure of the quotient algebra of an ideal in its total ring of fractions can now be computed using a normalisation algorithm included for the first time in V2.11. For ideals in rank 2 polynomial rings, a maximal order in the corresponding function field is computed. For higher rank rings, a general algorithm of de Jong is used. The latter algorithm is often very slow and we plan further improvements. Noether normalisation is also available. Functions for obtaining the equidimensional decomposition of ideals with no embedded primary components have also been added.

Extensions of Rings

• Algebraic Function Fields: A new representation of function fields has been implemented (a non-simple extension). In this representation a field may be extended by adjoining roots of several different polynomials simultaneously rather than by making a succession of relative extensions. The extension field is a one-step extension of the base field and in certain circumstances may allow much more efficient computation than would be the case with the corresponding relative extension. Fields in this new representation have almost all the functionality of the other representations.

• p-adic Rings and Fields: The speed of many operations related to point counting has been greatly improved. In particular, type 1 and 2 Gaussian Normal Bases have been implemented, which give an essentially free Frobenius action without sacrificing multiplication speed.

Algebras

• Finitely-presented Associative Algebras: The first non-trivial implementation of these structures has been achieved by extending (where applicable) part of the commutative algebra machinery to noncommutative data structures and algorithms. Non-commutative versions of both the Buchberger and the F4 algorithms are provided for computing a noncommutative Gröbner basis of an ideal (if the algorithm should terminate). Consequently, this algorithm may be used to solve the word problem, construct a matrix representation or, if the algebra is finite dimensional, construct an isomorphic structure constant algebra.

Representation Theory

• Representations of Finite Groups: An implementation of the Dixon algorithm for finding the irreducible representation affording a given character of a finite group has been coded by Derek Holt. Techniques for finding a field of minimal degree which realises a given representation have also been developed.
• Representations of Symmetric Groups: The Symmetrica package is used to provide efficient methods for computing individual characters or character values for the alternating and symmetric groups. Integral, seminormal and orthogonal representations of the symmetric group may also be constructed.

Lie Theory

• Lie Groups: It is now possible to construct the highest weight representations and the adjoint representation for groups of Lie type. Functions are provided to determine the centre and also to decompose automorphisms (following Carter).
• Lie Algebras: Very efficient machinery has been developed for constructing a Gröbner basis for a finitely presented Lie algebra L by Willem de Graaf and Allan Steel. The GB reduction algorithm used is Magma's generic F4 algorithm. At present, if the algebra L is finite dimensional, the GB can be used to construct a Lie algebra defined by structure constants. Alternatively, the GB may be used to construct a nilpotent quotient of L to a designated class.

Differential Rings

• Differential Rings and Fields: Machinery has been implemented for defining and working with these structures. The types are based on the existing algebraic function field and affine algebra types. Notable features include the calculation of the differential constant field, extensions of differential rings and fields, and the formation of quotient rings and field of fractions.

• Differential Operator Rings: Rings of differential operators can be created over any differential ring or field in such a way that an operator can be applied to elements of the underlying ring or field. Features include the calculation of properties of a place at an operator, the determination of the singular points of an operator, the calculation of the indicial polynomial of an operator and the calculation of all rational solutions of linear differential equations having the forms L(y) = 0 and L(y) = g.

Algebraic Geometry

• Schemes: Machinery for projecting projective schemes isomorphically into lower dimensional linear subspaces has been implemented. This is applied in a new function which gives a birational embedding of a plane curve as a non-singular projective scheme in 2- or 3-space. The projection of a canonical genus 5 curve over Q from projective 4-space to 3-space, takes 2 milliseconds on a 750 MHz machine.

• Hilbert Series and Polarised Varieties: Magma V2.11 contains a database of 24,099 K3 surfaces that, in a well-defined sense, includes a sketch of all possible examples. As the K3 methods work in many other contexts, tools for calculating subcanonical curves, Fano 3-folds and Calabi-Yau 3-folds are also included. The basic method is to assemble a lot of data, feed it into the Riemann-Roch formula to get a Hilbert series, and then attempt to describe a plausible variety with that Hilbert series.

Arithmetic Geometry

• Conics: A new algorithm due to Denis Simon that allows for efficient parametrisation of non-diagonal conics over Q with factorizable discriminant has been implemented. The implementation automatically chooses the best strategy to parametrise a given conic and allows the efficient parametrisation of a much larger class of conics over Q than was previously possible.

• Elliptic Curves: The basic machinery for curves over number fields has been considerably expanded. V2.11 includes code written by John Cremona implementing Tate's algorithm for computing local minimal models and Martine Girard's code for determining the heights of a point on an elliptic curve defined over a number field or a function field. Also available is a Magma database of 136, 924, 520 elliptic curves over Q with conductors up to 10⁸ constructed by William Stein and Mark Watkins.

• Elliptic Curves: Analytic methods for elliptic curves over Q have been implemented by Mark Watkins. One can now compute the order of vanishing and special values of the L-function of an elliptic curve. This allows full determination of the data involved in the BSD conjecture for curves over Q. One can also determine the modular degree of an elliptic curve as well as the set of curves isogenous to a given rational elliptic curve. The Heegner point method for the determination of generators of elliptic curves of rank 1 over Q has been implemented by Mark Watkins and Tom Womack.

• Elliptic Curves: p-adic canonical lift-based techniques for counting points on elliptic curves over finite fields of characteristic 2 are now included in Magma. When Type I and II GNB's exist, a fast adaptation of the quasi-quadratic algorithm of Lercier and Lubicz by Michael Harrison is used. This mainly applies for fields of size up to about 2¹⁰⁰⁰ which include those of cryptographic interest. It combines the good features of Lercier/Lubicz with those of the MSST algorithm. A sample time for a field of size 2¹⁶² is 0.04 seconds on a 2.1 GHz Athalon. When Type I or II GNB's do not exist, the usual MSST algorithm or, for larger fields, a recursive version by Harley is employed.

• Hyperelliptic Curves: It is now possible to compute 2-Selmer groups of arbitrary hyperelliptic curves with a rational Weierstrass point and 2-Selmer groups and 2-isogeny Selmer groups of elliptic curves. Whenever possible, Selmer groups are represented by S-units in a product representation, which avoids coefficient blowup. Assuming GRH, this allows for computation of Selmer groups in truly subexponential time.

• Hyperelliptic Curves: Magma routines developed by Nils Bruin allow the application of Chabauty methods to determine the rational points on a curve C over Q covering an elliptic curve E over a number field with a known Mordell-Weil group. This allows in many cases the computation of an often sharp bound on the number of rational points on a curve that can be mapped non-trivially into certain special abelian varieties. Unramified 2-covers of hyperelliptic curves fit in this category and application of these methods allows for explicit determination of the set of rational points on hyperelliptic curves in many cases.

• Hyperelliptic Curves: p-adic techniques have been included for fast point-counting on hyperelliptic curves and their Jacobians over GF(pⁿ) for small p. For p odd, Kedlaya's algorithm is used with several high-level efficiencies. For p = 2, the hyperelliptic Mestre/Lercier/Lubicz algorithm has been adapted in a similar fashion to the elliptic case to produce a fast implementation, particularly well suited to genus 2 and 3 curves. The order of the Jacobian of a genus 2 curve over Gf (2⁸⁰) is found in 1.39 seconds on a 2.1 GHz Athalon machine.

• Hyperelliptic Curves: Paul van Wamelen has written a package for computing with the analytic Jacobian of a hyperelliptic curve, that is, with the Jacobian as a complex torus. The analytic Jacobian is constructed in terms of the period matrix of the curve. Mapping of points between the algebraic and analytic Jacobians allows the user to obtain exact algebraic results from inexact analytic computations. The analytic Jacobian can also be used to find maps between different Jacobians including homomorphisms and specialisation such as isomorphisms, isogenies and the endomorphism rings.

• Modular Abelian Varieties: William Stein, who developed the packages for modular symbols and modular forms in Magma, has very recently constructed a major package for modular abelian varieties, which are viewed as explicitly given quotients or subvarieties of modular Jacobians. No explicit defining algebraic equations are used in these algorithms, so computations with abelian varieties of large dimension are feasible. The current machinery provides extensive functionality for computing with such abelian varieties, including functions for enumerating and decomposing modular abelian varieties, isomorphism testing, computing exact endomorphism and homomorphism rings, doing arithmetic with finite subgroups and computing information about torsion subgroups and special values of L-functions and Tamagawa numbers.

Incidence Structures

• Symmetric functions: The Symmetrica package, developed in Bayreuth by Adalbert Kerber and colleagues has been installed in Magma by Axel Kohnert. The package supports five bases: Schur functions, homogenous symmetric functions, elementary symmetric functions, monomial symmetric functions and power sum symmetric functions. A wide range of operations are supported including arithmetic, transition matrices for base change, and plethysm. The Magma version incorporates many improvements devised by Kohnert and timings show that Magma is much faster for these operations than the other two symmetric function packages (ACE and SF).

• Hadamard Matrices: The previous algorithm used for isomorphism testing has been replaced by a much, much faster idea due to Brendan McKay, a new fast automorphism function based on the same idea is available. We have also constructed the first stage of a database of known Hadamard and skew Hadamard matrices of order up to 100.

• Graphs: In addition to vertex labels, the edges of simple graphs may now have either a label, a weight or a capacity. Standard shortest-path algorithms have been implemented for graphs whose edges are weighted.

• Multigraphs: Both directed and undirected multigraphs have been installed. They may have multiple edges and/or loops and are implemented using an adjacency list representation. Vertices and edges can be labelled, and edges can be assigned capacities and/or weights. A large number of standard elementary graph operations have been implemented for multigraphs. The following major algorithms are also available: shortest path, maximal flow, planarity, triconnected (both operations involve linear-time algorithms).

Coding Theory

• Linear Codes over Finite Fields: An improved algorithm for minimum weight calculation has been introduced (M Grassl and G White). The tables of Best Known Linear Codes (BKLCs) over F₂ and F₄ have been updated to reflect the construction of many improved codes. For the first time a BKLC database over F₃ is released (constructed by M Grassl). The database over F₂ goes up to length 256, (100% filled), over F₃ up to length 100 (100% filled) and over F₄ of length up to 100 (over 99% filled).

• Additive Codes over Finite Fields: Given a finite field F and the space of all n-tuples of F, an additive code is a subset of F⁽ⁿ⁾ which is a K-linear subspace for some subfield K $\subseteq$ F. Additive codes are of current interest because of their applications to the construction of quantum error-correcting codes. In a new Magma module, basic constructions and cyclic codes are supported as are the important invariants such as weight distribution and weight enumerators. The Zimmermann minimum weight algorithm has been generalised to additive codes by Grassl and White.