Release Notes V2.10 (April 2003)

This screen provides a terse summary of the new features installed in Magma for release version V2.10 (April 2003). For more details, see the full release notes in the files relv210.dvi or relv210.ps, or see the full release notes at the top page of the HTML version of the Help system.

Groups

Permutation Groups: The performance of the Schreier--Todd-Coxeter--Sims algorithm for computing the order of a permutation group has been greatly improved in a number of important contexts. A new algorithm for chief series (developed by Bill Unger) provides greatly improved performance. The database of primitive permutation groups has been extended from degree 50 to degree 999.

Finite Groups: A new algorithm developed by Holt and Cannon that determines the maximal subgroups of any finite group using a knowledge of the maximal subgroups of its simple composition factors is included for the first time.

Finite Groups: The maximal subgroup machinery is now able to access the maximal subgroups and automorphism groups of a greatly expanded set of simple groups. These include HS and L(6,2), Alt(d); (d<1000), L(2,p), L(2,p^2), L(2,p^3), L(3,p), L(3,8), L(3,9), S(4,p), and U(3,p) (p prime). This greatly extends the range of those algorithms used for determining subgroups and automorphism groups. Fast algorithms for computing all subgroups having index less than some specified (moderate) bound in permutation and pc-groups have been implemented.

Finite Matrix Groups: It is now possible to compute automorphism groups and determine isomorphism of any finite matrix group for which it is possible to to compute a BSGS. A revised version of the package for performing Aschbacher analysis has been provided by Eamonn O'Brien.

Group Cohomology: A new module for computing the cohomology of a permutation group or pc-group developed by Derek Holt is included. This module also provides machinery for constructing extensions of G-modules and general abelian groups by general finite groups. It will be extended to include finite matrix groups shortly.

Finitely Presented Groups: A highly tuned version of the Holt algorithm for computing equivalence classes of homomorphisms from a finitely presented group to a permutation group has been developed. This has been successful in constructing epimorphisms onto groups of order up to 10^9.

Braid Groups: Asymptotically fast algorithms have been implemented for group operations, lattice operations, normal form computations and for computing the super summit set and the set of positive conjugates of an element. This work has as its goal the implementation of a new fast algorithm due to Volker Gebhardt for solving the conjugacy problem.

Groups and Monoids Defined by Rewrite Systems: A new version of the KBMAG package of Derek Holt has been installed. The new installation provides code for the construction of confluent presentations for finitely presented groups and monoids as well as short-lex automatic groups. This machinery is an enormous improvement over the previous KBMAG installation in Magma, particularly in the case of determining the automatic structure of a group.

Commutative Algebra

Polynomial Rings and Affine Algebras: A new algorithm by Allan Steel (to be published) solves a suite of fundamental problems associated with arbitrary algebraic function fields. These fields may be constructed as chains of algebraic extensions (using polynomial quotient rings, affine algebras, or standard algebraic function fields) and transcendental extensions (using rational function fields). The fields may have any characteristic and the algebraic extensions may be inseparable (which can happen in small characteristic). The problems now solved include decomposition of multivariate ideals and factorization of polynomials over such fields.

Extensions of Rings

Algebraic Function Fields: Conversion of arbitrary finite extensions of univariate function fields to simple extensions is possible, thus any field can be converted into the representation suited best for any given application.

Algebraic Function Fields: The machinery for relative extensions of function fields has been extended so that essentially all intrinsics now apply to both absolute extensions and relative extensions. In particular, divisor theory is supported in the relative case.

Algebraic Function Fields: Magma 2.10 includes an experimental release of a module for class field theory of global functions fields. In particular, it is possible to determine defining equations for arbitrary Abelian extensions.

Function Fields: The computation of GCDs of polynomials over function fields has also been greatly improved through use of a new modular algorithm. Factorization of polynomials over arbitrary algebraic function fields of any characteristic is now fully supported.

p-adic Rings and Fields: The module for p-adic rings (and fields) and their extensions has been completely rewritten in Magma 2.10, resulting in greatly improved performance that is highly competitive for cryptographic applications. Furthermore, the new ``Round 4'' algorithm of Pauli for factoring polynomials over local fields is included.

Representation Theory

Modular Representations: A package is provided which attempts to construct all (absolutely) irreducible representations of a finite group over a given finite field. For soluble groups the Brueckner adaptation of the Glasby--Howlett method is used. For non--soluble groups the irreducibles are obtained by chopping up representations using the Meataxe.

Lie Theory

Lie Theory: The entire module has been heavily revised and greatly expanded. Only a few highlights are noted here.

Coxeter Groups: A new category of Coxeter groups has been implemented. It represents elements as words in the standard Coxeter group presentation. The normal form of an element is found using an efficient new algorithm developed by Robert Howlett.

Reflection Groups: Some basic functions are now provided for creating and identifying reflection groups over an arbitrary field. The functionality for real reflection groups has been expanded.

Group of Lie type: A much faster algorithm is now used for multiplying elements in groups of Lie type. The standard automorphisms of these groups are available (i.e. inner, diagonal, diagram, and field automorphisms).

Lie Group Representations: The highest weight representations of a group of Lie type can be computed---this gives all rational representations over the base field.

Algebraic Geometry

Schemes: Maps between schemes can now be represented with multiple sets of polynomials, which must agree wherever both sets define a valid map. This allows the representation of true morphisms. Additionally, a routine is available that uses Groebner basis techniques to derive extra sets of defining equations, to extend the domain of definition of a map. For maps between smooth curves, this always yields a morphism. A routine is provided that properly tests a map for birationality and finds a birational inverse, if it exists.

Curve Maps: Maps between curves can now be used to pull back functions, differentials and divisors and to push forward functions and divisors.

Projective Varieties (Local solubility): Given a projective variety over Q or over a number field, one can now test if there are any points over the completion of the base field at a finite prime. For plane curves, one can choose to check solubility of the desingularised curve. The system will perform the necessary blowups as necessary. For hyperelliptic curves, local solubility at a finite prime with a sufficiently large residue field of odd characteristic is tested using an algorithm that is independent of the size of the residue field.

Plane Curves: Plane curves and their function fields are now tightly integrated. It is now possible go backwards and forwards between the coordinate rings of a curve and its function field and to construct projective embeddings from functions.

Elliptic Curves: 2-Selmer groups and 2-Isogeny Selmer groups of elliptic curves over number fields can now be computed explicitly and are returned as abstract abelian groups. Maps are provided to represent elements of the Selmer group as elements of etale algebras and to get the corresponding principal homogeneous space, represented as a cover of the elliptic curve.

Elliptic Curves: The Magma V2.9 Cremona database of elliptic curves (up to conductor 10,000) has been replaced in V2.10 by a version that includes all curves having conductor up to 20,000.

Modular Forms: William Stein has supplied a new revision of his packages for modular symbols and modular forms.

Subgroups of PSL(2, R): A new revision of Helena's Verrill's package for subgroups of PSL(2, R) has been installed.

Numerical Graded Rings: The existing K3 database in Magma contains the 391 examples of K3 surfaces in the known lists. The same ideas have now been used to construct much bigger lists of K3 surfaces, that include all possible configurations of input data, (Gavin Brown).

Incidence Structures

Networks: Flow networks have been introduced as a new type. These may have multiple edges and loops. Two flow algorithms have been implemented, the Dinic algorithm and the push-relabel method.

Graphs: Magma V2.10 contains an implementation of the linear-time algorithm of Hopcroft and Tarjan for finding the 3-connected components of a graph. In addition, it is now possible to determine the vertex connectivity and the edge connectivity of a graph. Finally, a maximum matching algorithm has been implemented for bipartite graphs.

Incidence Structures and Designs: A much faster but more space expensive mechanism is provided to test whether a structure is t-balanced.

Finite Projective Planes: A much improved method is used to test whether an incidence structure is a finite projective plane. The impact of the new method is particularly dramatic when attempting to construct planes of large order.

Coding Theory

Linear Codes over Finite Fields: Magma V2.10 contains a database of constructions of best known codes up to length 100 over GF(4). The codes of length up to 18 are optimal. The database is over 98 per cent complete with only 73 of the 5150 codes missing, the first such missing code occurs at length 92. Many of the codes constructed in this database have bounds that are vast improvements on the previously bounds for best codes over GF(4). (Markus Grassl and Greg White).

Linear Codes over Finite Rings: Magma V2.10 supports error- correcting codes over integer residue rings and Galois rings, with specialised functionality for codes over Z_4, the ring of integers modulo 4. The machinery for codes over general finite rings includes basic constructions such as cyclic code and permutation code and the determination of the complete weight enumerator and Hamming weight distribution.

Linear Codes over Z_4: Features include the Gray map and a host of specific constructions including Kerdock, Preparata, Reed--Muller, Goethals codes and more. Optimised code for calculating the Lee and Euclidean weight distributions is included.

[Next][Prev] [Right] [Left] [Up] [Index] [Root]