MAGMA Computational Algebra System

Home    Download    Help    FAQ    Calculator    Book    About

Magma
•	How to get it
•	Download
•	Online Demo
Resources
•	Online Help
•	Discovering Mathematics with Magma
•	Citations
•	How to cite Magma
•	Links
•	Contact us

Summary

The Integers

• Primality Proving:
  • The original version of the Elliptic Curve Primality Prover (ECPP) of F. Morain has been upgraded. In particular, it now uses Morain's 1998 tables of Weber polynomials which enable the primality of much larger integers to be established.

Finite Fields

• Arithmetic
  • Extension fields are now defined by sparse lexicographically minimal polynomials when possible (and when Conway polynomials are not available), leading to big speedups of arithmetic in moderate to high degree extension fields. Databases of such polynomials have been constructed for characteristic 2 up to degree 120, 000; for characteristic 3 up to 50, 000; for characteristics 5 and 7 up to degree 20, 000; and for characteristics p, 11$\le$p$\le$101, up to degrees at least 1, 500.

  • A new packed representation for finite fields of characteristic 3 has been introduced giving large speedups for fields of higher degree, in particular. In addition, a fast irreducibility test for polynomials over GF(3) has been devised. This algorithm can run 10 times faster in the case of sparse polynomials. Factoring a polynomial over GF(3¹⁰³) is now 10 to 15 times faster than for V2.13. (The speed-up comes from the more efficient field arithmetic alone, not improvements in factorization.)

  • Fast Frobenius maps, based on linear algebra.

• Factorisation
  • The Magma implementation of the Berlekamp algorithm now uses a sparse matrix datastructure when the polynomial is sparse leading to less memory usage and reduced execution times, particularly over GF(2). Sparse polynomials of degree 100, 000 over GF(2) can be factored in a few seconds.

  • For polynomials whose coefficients lie in a subfield, factorisation and root finding have been sped up enormously.

• Isomorphism/Embedding
  • Magma now uses an algorithm due to Eric Rains for constructing isomorphisms between fields and embedding subfields in larger fields. For example, embedding GF(2¹⁰⁰⁰) in GF(2²⁰⁰⁰) now takes 0.3 seconds, compared to 20 minutes with V2.13.

• Norm/Trace/Hilbert90
  • A new deterministic algorithm to solve norm equations in finite fields of relative degree 2 has been added. It is usually faster than the randomised standard algorithm.

  • A fast deterministic algorithm for Hilbert-90 equations over finite fields has been added. Given a finite field F of order q and an element a $\in$ F, the Hilbert 90 equation x^qx^-1 = a can be solved for x in some extension of F. This is the fundamental result in the Galois cohomology of finite fields.

Polynomial Rings

• Arithmetic
  • Multiplication of polynomials over finite fields of characteristic 2 has been greatly improved. For polynomials over GF(2) this is achieved through use of the Cantor algorithm which has better complexity than the Karatsuba algorithm. For polynomials over high degree fields GF(2ⁿ), n > 1, the Kronecker segmentation expansion method is now used. Multiplication of degree 1000 polynomials over GF(2¹⁰⁰⁰) is now about 10 times faster than in V2.13 on 64-bit processors.

  • The multivariate GCD algorithm has been extended to take advantage of the important case in which the quotient of one of the inputs by the GCD is a low-degree polynomial.

• Factorisation
  • Coppersmith's method for finding small roots of univariate polynomials modulo an integer has been implemented. This implementation uses the new fpLLL package of Damien Stehlé.

  • Factorisation of univariate polynomials over small finite fields has been completely overhauled, leading to very significant speedups. This is particularly significant for fields of characteristic 2 and for very sparse polynomials over small fields of any characteristic.

  • Separate to the previous item, testing irreducibility of polynomials over finite fields has been greatly improved through use of a sieving method.

  • In V2.14, for the first time factorisation of polynomials over a class of power series rings is supported. This was achieved by extending S. Pauli's p-adic factorisation method, which is actually an algorithm for the factorisation of polynomials over local fields.

Linear Algebra

• Matrix Arithmetic
  • Matrix multiplication has been greatly improved in the case that one of the input matrices is sparse and the other dense.

  • The multiplication of matrices over prime finite fields has been optimised by precomputing the inverse of the modulus.

  • The code for the multiplication of matrices over GF(2) now uses Intel SSE2 instructions when supported.

• Linear Algebra over Finite Fields
  • General speed-ups have been achieved for linear algebra over finite fields of characteristic 2.

• Linear Algebra over Euclidean Rings
  • The calculation of the Smith normal form and the determinant of a dense matrix defined over an euclidean ring has been significantly improved through replacing the Havas-Holt-Rees algorithm formerly used by an asymptotically-fast recursive echelonisation algorithm.

Lattices and Quadratic Forms

• Lattices
  • Simon's variant of LLL reduction for indefinite forms has been efficiently implemented in Magma as part of a new package of Damien Stehlé, and works readily in dimensions greater than 100.

  • The automorphism group and theta series of a lattice is now stored and can be asserted via attributes.

  • A new function ThetaSeriesLimited(L, n) takes a time limit and returns the contribution to the first n coefficients of the theta series of a lattice L found by lattice enumeration within the specified CPU time.

• Quadratic Forms
  • Given a quadratic form F in an arbitrary number of variables, Mark Watkins has used Denis Simon's ideas as the basis of an algorithm for finding a large (totally) isotropic subspace of F. The subspace found is frequently maximal isotropic.

Global Arithmetic Fields

• Number Fields
  • The fast algorithm of Bosma and Stevenhagen for computing the 2-part of the ideal class group of a quadratic field has been implemented.

  • It is now possible to compute the integral closure of more general rings, such as the closure of Z[x] (instead of the more customary Q(x)). This is an example of recognising the existence of non-trivial valuations in the base field. Applications of this technique arise in areas such as inverse Galois theory (over Q) and the computation of minimal models for schemes.

  • The unit group of a suborder is canonically a subgroup of the full unit group of the maximal order, typically having very large index. In V2.14 we include code that implements a very efficient approach to computing this subgroup.

  • A new algorithm of C. Fieker and W. de Graaf has been implemented which finds the Z-lattice of all dependencies that exist between the roots of a polynomial or even a set of arbitrary algebraic integers.

  • A routine is provided for finding a simple representative modulo nth powers of a number field element.

• Galois Theory
  • Prior to this release, the calculation of Galois groups of polynomials defined over number fields has been limited to polynomials of degree at most 23. In this release, the new Fieker-Klüners algorithm has been extended so as to apply to polynomials defined over absolute extensions of Q. This allows the computation of Galois groups for polynomials of arbitrary large degrees (at least in theory) defined over number fields.

  • In a previous release, machinery was provided for the computation of arbitrary subfields of the normal closure based on the use of the Galois correspondence. In V2.14, the techniques are extended to allow computation of towers of relative extensions of number fields corresponding to descending chains of subgroups. This has applications to such problems as the solvability of equations by radicals and the computation of splitting fields.

  • One of the most celebrated results in mathematics states that an equation is soluble by means of radicals if and only if its Galois group is soluble. A constructive version of this theorem has been installed in Magma. More precisely, given a polynomial over Q with solvable Galois group, we find a representation of its roots in a radical tower.

  • Given a polynomial f over the integers, code has been developed which exploits Magma's ability to find Galois groups in order to efficiently compute the splitting field of f (and representations of its roots).

• Class Field Theory
  • Drinfeld modules of rank 1 may be viewed as realising the CM-theory for global function fields. In particular, they can be used to find explicit defining equations for abelian extensions. In V2.14 a new algorithm is included that is capable of finding explicit algebraic descriptions of images under this Drinfeld module for arbitrary fields (in principle). Previous methods applied only to elliptic or hyperelliptic curves.

  • A celebrated theorem in class field theory due to Grunwald and Wang asserts the existence of a global (cyclic) field with given local degrees. Theoretical applications arise, for example, in the theory of algebras where the theorem guarantees the existence of a minimal degree splitting field satisfying given local conditions. A constructive version of the theorem has been implemented: given (finitely many) local degrees, it produces a cyclic number field interpolating the given local data.

• Galois Cohomology
  • It is important to be able to recognise whether an element of the second cohomology group of the Galois group of a number field acting on the multiplicative group is trivial (ie. an element of the first cohomology group). (It can be thought of as a generalisation of a norm equation.) Applications occur in the theory of central simple algebras (the relative Brauer group of a field) and in representation theory. In V2.14 a new algorithm of C. Fieker determines whether a given 2-cochain is trivial, and if so, finds a corresponding 1-cochain.

Local Arithmetic Fields

• Unramified Fields
  • The Frobenius map (GaloisImage) for unramified extensions of Q_p with default bases has been rewritten for increased speed.

  • An implementation of an algorithm of Harley for efficient Teichmüller lifts in unramified extensions of Q_p has been added.

Algebras

• Matrix Algebras
  • A very efficient algorithm for computing the unit group and Jacobson radical of a matrix algebra defined over a finite field has been developed and implemented by P. Brooksbank and E. O'Brien.

• Quaternion Algebras
  • For definite quaternion algebras over number fields, the conjugacy classes of maximal orders, and the 2-sided ideal class group of a maximal order can now be computed. A much faster routine for determining unit groups of orders is provided. An alternative algorithm for the left or right ideal classes, that makes use of the other new features, has also been implemented. This machinery was developed by Markus Kirschmer.

• Reductive Lie Algebras
  • The construction of twisted reductive Lie algebras is now supported. This makes it possible allows us to construct a wider range of Lie algebras over non-algebraically closed fields. For example, over a real field, this allows the construction of the unitary Lie algebra.

  • It is now possible to compute standard bases for reductive Lie algebras over finite fields.

• Nilpotent Lie Algebras
  • A database of all nilpotent Lie algebras of dimension up to 6 over fields of odd characteristic has been implemented by Willem de Graaf. Given any such algebra it is possible to identify it in the database.

• Algebras over Euclidean rings
  • One may now create arbitrary quotients of finite dimensional algebras given in terms of structure constants which are defined over euclidean rings (including rings with zero divisors, such as residue class rings). The quotient algebras may have both free and torsion parts. Only free algebras and their subalgebras over such rings were previously supported.

  • As a consequence of the previous item, Lie rings (that is, Lie algebras over defined over an euclidean ring, usually Z) are now supported. In particular, it is possible to compute a basis and multiplication table for finitely presented Lie rings having finite dimension. The implementation handles both homogeneous and nonhomogeneous relations. A variant of the algorithm is provided which can find nilpotent quotients of finitely presented Lie rings. This implementation was undertaken by W. de Graaf.

Finite Groups

• Arithmetic
  • A variation of the Product Replacement Algorithm for generating random elements of a group due to H. Bäärnhielm and C. Leedham-Green has been installed. The new algorithm, known as Prospector, is designed so as to minimise the length of the words.

  • The evaluation of straight line programs (SLPs) in a group has been revised following ideas of H. Bäärnhielm to retain fewer intermediate results in memory during the evaluation. This can greatly reduce memory use, for example, when evaluating homomorphisms. The new scheme is particularly effective when evaluating SLPs produced by the product replacement algorithm.

• Monte-Carlo Structure Algorithms
  • A number of Monte-Carlo algorithms for investigating the structure of large groups have been implemented by E. O'Brien and others. Perhaps the most important of these algorithms is an implementation of the well-known algorithm of J. Bray for computing the centraliser of an involution.

• Maximal Subgroups
  • The maximal subgroups of the classical groups of dimension not exceeding 12 have been determined by J. Bray, D. Holt and C. Roney-Dougal and the corresponding Magma code has been written by D. Holt and C. Roney-Dougal. The maximal subgroups are given in the natural representation of the given classical group.

  • The maximal subgroups of the twisted groups ²B₂(q) (more commonly known as the Suzuki groups Sz(q)) and the maximal subgroups of the twisted exceptional groups ²G₂(q) (small Ree groups) have been determined by Henrik Bäärnhielm whose Magma implementation is included in V2.14. Again, the maximal subgroups are produced in the natural matrix representation.

• Sylow Subgroups
  • The Sylow subgroups of the family of exceptional groups ²F₄(q) (large Ree groups) have been determined by Henrik Bäärnhielm and his Magma implementation is released in V2.14. The Sylow subgroups of the families Sz(q) and ²G₂(q) were released in V2.13. The Sylow subgroups are produced in the natural matrix representation.

  • The Sylow subgroups of the classical groups were already included in V2.13.

• Conjugacy Classes
  • Machinery for computing with element conjugacy in the linear, unitary and symplectic families of classical groups has been implemented by S. Haller and S. Murray. In particular, functions are provided for determining representatives of each class, calculating the corresponding centralisers, determining the class in which an arbitary element lies and constructive conjugation of elements in the respective groups.

  • The conjugacy classes of elements for the simple groups of Suzuki have been implemented by H. Bäärnhielm.

• Constructive Recognition
  • It is now possible to to perform constructive recognition on both the large and small Ree groups (that is, ²F₄(q) and ²G₂(q) ) in various matrix representations using a package developed by Hendrik Bäärnhielm.

  • Constructive recognition of U₃(q) and U₄(q) has been implemented by Peter Brooksbank.

• Databases
  • The Small Groups database has been agumented by code that will enumerate all groups of any square-free order. This code was developed by Bettina Eick and Eamonn O'Brien.

  • The Magma version of the Atlas database of matrix and permutation representations of simple groups and simple groups with decorations has been updated to roughly correspond to the current contents of R. Wilson's Atlas web site. The number of groups contained in the new version of the database is approximately 700 compared to 300 in the previous Magma version.

• Group Cohomology
  • The package has been extended in a number of ways. The more important changes include the calculation of 1-coboundaries and 2-coboundaries, the restriction of cohomology to a subgroup, calculations with corestriction and coboundary maps, and having the extension functions return the projection and injection maps.

Finitely-Presented Groups

• Nilpotent Quotient Algorithm
  • The latest version (2.2) of Werner Nickel's Nilpotent Quotient program has been installed in Magma by Bill Unger and Michael Vaughan-Lee. This version uses combinatorial collection and so is often much faster than the version included in earlier releases of Magma. It also contains expanded functionality including an ability to handle identical relations.

Lie Groups

• General
  • In a major project, A. Cohen, S. Haller and S. Murray have designed and implemented a practical version of Lang's algorithm for connected reductive groups of Lie type. Among various applications this can be used to compute twisted tori.

  • Some conjugation functions for groups of Lie type are provided: Conjugation of a semisimple element into a torus; conjugation of any element into a Borel subgroup.

• Finite Groups of Lie Type
  • A conformal group is the group of matrices that preserve a given bilinear or quadratic form up to a constant. Constructions are provided for the conformal groups corresponding to the forms defining the classical groups.

  • Fast machinery for solving element conjugacy problems in most families of classical groups has been developed. In particular, it is possible to determine (a) a representative element from each conjugacy class, (b) the centraliser of any element in the group, and (c) test any pair of elements for conjugacy. With the exception of (a), the algorithms used are polynomial-time.

Representation Theory

• Characters and Block Theory
  • It is now possible to determine the table of rational characters of a finite group.

  • An algorithm has been implemented for computing the p-blocks of the table of ordinary characters for a finite group. It is also possible to construct the defect group of a p-block.

• Ordinary Representations of Finite Groups
  • A key problem when constructing an ordinary irreducible representation of a group is to determine its Schur index, that is, the degree of a minimal field for the representation taken over the field generated by its character values. The first practical algorithm for this was developed in 2006 by G. Nebe and W. Unger. This version of Magma contains an implementation of the algorithm.

  • The problem of writing a given (absolutely irreducible) representation over as small a field as possible (or over an ``arbitrary'' user defined field) is a key problem in representation theory. A new method due to C. Fieker and based on Galois cohomology has been implemented. This method will find a minimal subfield that affords a given representation. If this field is not ``small enough'' then a constructive version of the Grunwald-Wang theorem is used to find a minimal degree splitting field.

• Representations of Lie Groups
  • An extensive package for computing the combinatorial properties of highest weight representations of a Lie algebra has been written by Dan Roozemond. For example, given two highest weight representations, we can compute the decomposition of their tensor product into highest weight representations. The aim is to provide functionality in Magma equivalent to that in the now defunct LiE package.

Commutative Algebra

• Gröbner Bases
  • The F4 algorithm is now used for computing with ideals having fixed bases. Thus the coordinate matrix for a Gröbner basis is now found much more quickly.

  • A new algorithm, based on Faugere F4 techniques, has been introduced to reduce a sequence of polynomials modulo another sequence of polynomials or an ideal. This is important for the efficient computation of the secondary invariants of a finite group.

  • The memory management in the F4 algorithm has been improved so that less memory is used when there are extremely large ultrasparse matrices; the time is also significantly reduced in such cases.

  • The method used to calculate Gröbner bases over algebraic number fields (including cyclotomic and quadratic fields) has been greatly improved.

• Ideals and Modules
  • The primary decomposition and radical algorithms have been improved by heuristics to quickly determine whether or not the ideal is prime or radical (thus catching common cases quickly).

  • Modules over multivariate polynomial rings have been completely revised. The former embedded and reduced types have been merged into a single type, which supports the features of both previous types. Any sub- or quotient module may be defined in embedded or reduced form, and such modules may be mixed.

  • Full support is provided for gradings and homogeneous modules for the first time.

• Invariant Theory
  • The computation of primary invariants has been improved by the use of Faugere F4 techniques.

  • A new algorithm designed and implemented by G. Kemper for computing the secondary invariants in the non-modular case has been implemented. This algorithm is very much faster than the previous one.

  • Invariant rings of reductive algebraic groups can be computed in Magma for the first time using Derksen's algorithm among others. The Magma code was developed by G. Kemper.

  • Algorithms have been implemented for computing invariant fields (these include Derksen's algorithm). The Magma code was developed by G. Kemper.

Algebraic Geometry

• General Schemes
  • The code for computing images under general maps as been rewritten for increased speed.

  • Basic attributes of schemes (such as non-singularity, irreducibility and the singular subscheme) are now stored to avoid expensive recomputation.

  • For schemes over algebraic function fields, it is now possible to test whether the scheme is locally soluble over a completion of the base field.

• Algebraic Curves
  • A package has been developed which, given an algebraic curve X, and a subgroup G of the automorphism group of X, computes the quotient of X by G as an algebraic curve.

Arithmetic Geometry

• Conics
  • The algorithm by J. Cremona and M. van Hoeij for finding points on plane conics over rational function fields has been installed. (Code was written by John Cremona and David Roberts).

• Elliptic Curves over Finite Fields
  • A canonical lift method has been implemented to provide fast point counting for curves over finite fields in small, odd characteristic. This case was not covered by the fast point counting machinery previously installed in Magma.

  • A much more efficient version of the Weil pairing has been coded while the Tate, Eta and Ate pairings have been implemented for the first time in Magma. In each case Miller's algorithm is used. This project was undertaken by F. Vercauteren.

• Elliptic Curves over the Rationals
  • A new function MordellWeilShaInformation is provided as an easy interface to all the relevant Magma machinery.

  • A new algorithm by Steve Donnelly for computing the Cassels-Tate pairing on the 2-Selmer group of an elliptic curve over Q has been programmed.

  • For curves admitting 2-isogenies, a routine for lifting ``descent via 2-isogenies'' to full 2-descent has been provided.

  • An 8-descent routine is now provided. The algorithm and implemention are by Sebastian Stamminger.

• Elliptic Curves over p-adic Fields
  • Versions of some routines for obtaining local information about elliptic curves over the rationals now work in the case of curves defined directly over p-adic fields. These include computation of conducter, Tamagawa numbers (Tate's algorithm) and minimal models, and also computation of the root number.

• Elliptic Curves over Number Fields
  • Root numbers of a curve over a number field may be efficiently computed, in full generality, using an algorithm of T. Dokchitser and V. Dokchitser. The implementation was undertaken by T. Dokchitser.

• Elliptic Curves over Rational Function Fields
  • Two-descent machinery has been added in characteristic 2: a routine for computing the two-isogeny Selmer groups is provided for non-supersingular curves.

  • A full two-descent routine is available in odd characteristic for curves without 2-torsion, representing the elements of the 2-Selmer group as hyperelliptic curves. A separate routine for descent via 2-isogenies has been contributed by David Roberts.

  • Minimization and point-searching are available for the 2-covering curves (written by David Roberts).

• Hyperelliptic Curves over Finite Fields
  • For curves defined over finite fields of characteristic 2, Kedlaya's algorithm for point counting has been implemented by F. Vercauteren. Around genus 4 the Kedlaya algorithm out-performs the Mestre canonical lift approach currently used.

• Plane Curves over Finite Fields
  • An efficient implementation of Diem's algorithm for computing discrete logarithms for points on the Jacobian of a general plane curve C over GF(q) having small genus was developed by Jasper Scholten. The complexity of this method is O(q^2-2/(d-1)), where d the degree of C.

Modular Arithmetic Geometry

• Modular Curves
  • Code has been developed by Mark Watkins for finding models of modular curves X₀(N) and their quotients by Atkin-Lehner involutions.

• Modular Forms
  • A major revision of the modular forms package is being undertaken. In particular, very considerable improvements to efficiency for the main routines in the package have been achieved (in particular, computation of newforms and of q-expansion bases).

  • Modular forms of weight one are now included in the package. A special feature is the direct computation of those forms associated to dihedral Galois representations. This was adapted from code provided by Kevin Buzzard.

  • Modular forms of half-integral weight are also included in the package. The functionality now available includes q-expansions bases of the spaces, and basic operations.

• Arithmetic Fuchsian Groups
  • A module for working with arithmetic Fuchsian groups has been developed by John Voight. The module provides support for determining basic invariants of a Fuchsian group $\Gamma$ and for computing a fundamental domain for $\Gamma$. Specialised algorithms are provided for triangle groups.

Coding Theory

• Linear Codes over Fields
  • A database of best known linear codes (BLKC) over GF(5), GF(7), GF(8) and GF(9) constructed by M. Grassl, is included in Magma for the first time.

System and Language

• Associative Arrays
  • A new type for associative arrays has been introduced.