Release Notes V2.5 (July 7, 1999)

This screen provides a terse summary of the new features installed in Magma for release version V2.5 (July 7, 1999).

Summary

The kbmag package of Derek Holt has been installed. This has as its basis a powerful Knuth-Bendix algorithm for monoids. Using this as a foundation, three new categories have been installed: MonRWS -- monoids defined by finite confluent rewrite systems; GrpRWS -- groups defined by finite confluent rewrite systems; and GrpATC -- short-lex automatic groups.

The Plesken soluble quotient algorithm has been implemented in Magma by Herbert Brueckner. This is the first implementation capable of computing soluble quotients without the user needing to supply any information about the quotient.

The ordinary irreducible representations of a finite soluble group may now be constructed. Previously, only the modular irreducible representations were available.

A basic module for Coxeter groups implemented by Don Taylor has been installed.

General algebraic function fields are available for the first time. These facilities are provided by the KANT group. A general function field is a finite degree extension of a rational function field K(x). In Magma V2.5, the field K may be taken to be either a finite field, Q or a number field. Operations supported include the arithmetic of algebraic functions, genus, maximal orders, arithmetic of fractional ideals, fundamental unit computation (global function fields) and subfields.

The first stage of a general package for working with plane curves is included in V2.5. Its main features are flexible tools for translating between affine and projective curves, the calculation of geometric genus of any plane curve and the explicit manipulation of divisors on cubics in Weierstrass form.

Also forming part of the algebraic geometry machinery is a module for working with schemes defined by polynomial equations in affine or projective space. Such tools include Groebner basis computation, dimension and image of maps, and linear algebra calculations formalized as linear systems on projective space. Maps between spaces may also be constructed and studied.

Magma V2.5 contains an efficient implementation of the Schoof-Elkies-Atkin algorithm with Lercier's extension to base fields of characteristic 2. Calculations are performed in the smallest field over which the curve is defined, and the result is lifted to the original field.

Removals and Changes

The function ElementaryDivisors has been fixed to include any ones which are in the Smith normal form of the input matrix (so the length of the result is now always the rank of the input matrix).

Descriptions of the functions LargestClique and LargestIndependentSet have been removed from the Magma Handbook. The functions will be removed from Magma in a subsequent release.

Language and System Features [HB 1--5]

New features:

New functions GetMemoryUsage, GetMaximumMemoryUsage and ResetMaximumMemoryUsage for obtaining information about Magma's memory usage.

New function Getuid() to return the user ID of the current Magma process (calls the system function getuid() in Unix).

The expression +specfile may now be placed in a package specification file instead of a filename to indicate that all files in the named specification file specfile should be recursively attached.

The help system browser now allows the command grep to search the full text of the help information for a given substring.

Semigroups

Monoids Defined by Rewrite Systems (New) [HB 17]

A new category comprising monoids with confluent rewriting systems (RWS monoids) has been introduced. The major algorithm provided is the Knuth-Bendix procedure as implemented in Derek Holt's kbmag package.

Construction of an RWS monoid from an fp-monoid using the Knuth-Bendix procedure. Orderings supported include: RT-recursive, recursive, ShortLex, WT-ShortLex and Wreath.

Test a rewrite system for confluence

Reduction of a word to normal form

Operations on words: Product, exponentiation, equality

Test for a monoid being finite

Enumeration of elements

Groups

Finitely Presented Groups [HB 20]

New features:

The Plesken soluble quotient algorithm has been implemented for Magma by Herbert Br\"uckner. This is the first implementation that will compute soluble quotients without having the user supply information about the quotient. It is capable of constructing very large finite quotients and also of detecting infinite soluble quotients.

Groups Defined by Rewrite Systems (New) [HB 21]

This is a category of finitely presented groups where the relations are interpreted as rewrite rules. If the group is defined by a confluent system of rewrite rules then we have a normal form for its elements and hence a solution to the word problem. A group belonging to this category is typically constructed by applying the Knuth-Bendix procedure. As in the case of monoids, Magma uses the Knuth-Bendix developed by Derek Holt as part of his package kbmag.

Construction of an RWS group from an fp-group using the Knuth-Bendix procedure. Orderings supported include: RT-recursive, recursive, ShortLex, WT-ShortLex and Wreath

Test a rewrite system for confluence

Reduction of a word to normal form

Operations on words: Product, exponentiation, inverse, equality

Enumeration of elements

Test for a group being finite

Automatic Groups (New) [HB 22]

This category corresponds to short-lex automatic groups. A group is represented by four automata: first and second word-difference machines, a word-acceptor, and a multiplier. These automata are constructed using the Knuth-Bendix procedure. This category is implemented by Derek Holt's package kbmag.

Construction of an automatic group from an fp-group using the Knuth-Bendix procedure.

Reduction of a word to normal form

Product, exponentiation, inverse, equality of elements

Enumeration of words without repetition

Test for a group being finite

Growth function for a group

Finite Soluble Groups [HB 25]

New features:

Several functions are provided for constructing a polycyclic presentation for the maximal finite soluble quotient of an fp-group (Plesken-Brueckner algorithm)

The function IrreducibleRepresentations will compute the irreducible representations over a finite field, Q, or a cyclotomic number field.

The function AbsolutelyIrreducibleRepresentations will compute the ordinary or modular absolutely irreducible representations.

Bug fixes:

An error in the function NormalSubgroups where some normal subgroups were missed has been fixed.

An error that showed up in rare situations in the subgroup echelonization code has been fixed. This would sometimes cause errors in the determination of conjugacy classes.

Coxeter Groups (New) [HB 28]

Finite Coxeter groups are implemented as a subclass of permutation groups so that they inherit all the operations for permutation groups as well as having many specialized functions. This module was implemented by Don Taylor. Frank Luebeck and the Chevie team provided helpful assistance.

Cartan matrix corresponding to a given Dynkin diagram

Construction of a Coxeter group from a root system or Cartan matrix

Dynkin diagram of a Cartan matrix or Coxeter group

Root system for a Coxeter group

Element as a reduced word in the standard generators

Element of maximal length

Unique long (short) root of greatest height

Short root of maximal height

Reflections in Coxeter group

Reflection subgroup

Reduced representatives for cosets of the reflection subgroup

Actions on roots and co-roots

Coxeter group as a real reflection group

Groups of Lie Type (New) [HB 28]

Killing form of the Cartan algebra associated with a given Weyl group

Root elements

Fundamental roots and their negatives of a simple Lie algebra of given type and rank

Lie algebra of a Chevalley group as a structure constant algebra

Adjoint action

Graph automorphism of a Coxeter group

Degree of a representation with specified weight

The BN-pair for a group of Lie type

Rings

General Rings [HB 30]

New features:

Mutation operators ^:= and /:= (when dividing by a unit) now work for all ring elements.

Finite Fields [HB 34]

Bug fixes:

A bug in the iterator for certain finite field representations has been fixed (it sometimes produced duplicate elements).

Univariate Polynomial Rings [HB 35]

New features:

New function InverseMod/Modinv for univariate polynomials to return the inverse of one polynomial modulo another.

Coercion for rational function fields has been improved to avoid undesirable behaviour in various cases.

Functions have been provided for creating polynomials belonging to the standard families of orthogonal polynomials. Included are Chebyshev polynomials of the first and second kind, Hermite polynomials, Legendre polynomials, Laguerre polynomials and Gegenbauer polynomials.

Functions have been provided to construct instances of the Dickson polynomials of the first and second kind.

Multivariate Polynomial Rings [HB 36]

New features:

The computation of the variety of an ideal over a (moderately small) finite field is now performed even when the dimension of the ideal is greater than zero.

Computation of the (trivial) variety of the full polynomial ring is now allowed, and VarietySizeOverAlgebraicClosure now returns zero for the full polynomial ring.

SetVerbose("Groebner", 2); will now cause all new computed polynomials to be printed fully in the Buchberger algorithm.

Bug fixes:

A bug in multivariate factorization over the integer ring has been fixed.

Error checking is now performed in NormalForm when a bad set or sequence is passed as the second argument.

Rational Function Fields, [HB 42]

New features:

Coercion for rational function fields has been improved to avoid undesirable behaviour in various cases.

Global Function Fields and their Orders (New) [HB 43]

An algebraic function field is a finite degree extension of a rational function field K(x). In Magma V2.5, the field K may be taken to be either a finite field, Q or a number field. An extension of K(x), where K is finite field, is called a global function field. The development of this module is a joint project with the KANT group. Work is under way on developing algorithms for computing the divisor class group.

Construction of a function field as an extension of K(x)

Arithmetic with elements

Trace and norm of an element

Exact constant field

Genus

Finite and infinite equation orders

Discriminant (of an order)

Maximal order (finite or infinite)

Construction of integral and fractional ideals

Ideal arithmetic: sum, product, quotient, gcd, lcm

Properties of ideals: Integral, prime, principal

Valuation of an order element or ideal at a prime ideal

Ramification index and residue class degree of a prime ideal

Prime ideal decomposition of a fractional ideal

Construction of places and divisors

Determination of places of degree one in global fields

Determine whether the place at infinity place is tamely ramified

Determination of places lying over a (finite) prime or the infinite place

Arithmetic in the divisor group

Riemann-Roch spaces

Basis reduction for finite orders (Pohst-Schoernig method) in global fields

Independent units, fundamental units, regulator in global fields

Real and Complex Fields [HB 44]

Bug fixes:

The function DedekindEta for real and complex fields has been fixed to give the correct result (which is consistent with the series function).

Formal Series [HB 46]

Bug fixes:

Bug in the function Eisenstein fixed.

Bug in the function Evaluate fixed.

Modules and Lattices

R-Modules [HB 49]

New features:

New function AHom to compute the module of homomorphisms from one module to another which respect the action of the underlying matrix algebra (like GHom but the module need not be a G-module).

Chain Complexes (New) [HB 50]

New features:

Creation of a complex from a list of A-modules

Subcomplexes and quotient complexes

Operations on complexes: Splice, shift, direct sum

Exact extension

Dual of a complex

Homology groups of a complex

Boundary maps

Given two complexes construct the corresponding chain map

Composition of chain maps

Image, kernel and cokernel of a chain map

Predicates for chain maps: Surjection, injection, isomorphism

Injective resolution (for complexes over a basic algebra)

Projective resolution (for complexes over a basic algebra)

Modules Hom(U, V) [HB 51]

Changes:

The function ElementaryDivisors has been fixed to include any ones which are in the Smith normal form of the input matrix (so the length of the result is now always the rank of the input matrix).

Algebras

Matrix Algebras [HB 57]

New features:

New modular algorithm for the multiplication of matrices over large prime finite fields.

Changes:

The function ElementaryDivisors has been changed to include any ones occurring on the diagonal of the Smith normal form of the input matrix (so the length of the result is now always the rank of the input matrix).

Basic Algebras (New) [HB 59]

A basic algebra is a finite dimensional algebra A over a field, all of whose simple modules have dimension one. In the literature such an algebra is known as a ``split'' basic algebra. The type in Magma is optimized for the purposes of doing homological calculations. This module was written by Jon Carlson.

Creation from a sequence of projective modules and a path tree for each module

Creation of the basic algebra corresponding to the group algebra of a p-group over GF(p).

Arithmetic

Extension and restriction of coefficient ring

Tensor product

Opposite algebra

Injective hull

Algebra as a right regular module over itself

Geometry

The algebraic geometry module includes machinery for studying general algebraic varieties and families of special curves (e.g. elliptic curves). The major categories include:

Affine plane curves

Projective plane curves

Newton polygons

Divisor groups of certain plane curves

Schemes

Elliptic curves

Algebraic Curves

Magma V2.5 includes the first stage of a general package for working with plane curves. These are interpreted as being the scheme defined by the vanishing of a polynomial defined on either an affine or projective space. Its main features are flexible tools for translating between affine and projective curves, the calculation of geometric genus of any plane curve and the explicit manipulation of divisors on cubics in Weierstrass form. Many more specialized will be included in future releases.

Plane Curves (New) [HB 62]

Creation of affine and projective curves together with the ambient affine and projective planes

Basic manoeuvres between affine and projective curves: projective closure, affine patches and so on

Basic scheme-type functions: e.g., irreducibility

Specialised data types for distinct classes of curves such as elliptic curves

Linear systems of curves in the projective plane with assigned basepoints

Implicitization of parametric curves

Global invariants of curves, such as genus and dimension

Local Analysis of Curves (New) [HB 62]

Calculation of tangent spaces and cones

Identification of all singularities of a curve, together with the basic analysis

Blowups, including weighted blowups, of points on curves

Local intersections

Divisors and the Riemann-Roch Theorem (New) [HB 62]

The following functions apply to special classes of curves.

Creation of divisors and arithmetic

Compute the divisor of a function on a curve

Determine whether a divisor is principal. If so find a function with the given divisor

Normal forms for divisors

Newton Polygons (New) [HB 64]

Construction of a newton polygon: Compact, infinite or including the origin

Construction of newton polygons from different types of data

Finding faces and vertices

If polygon is derived from a polynomial f, finding restrictions of f to faces

Locating a given point relative to a newton polygon

Determining whether a given line supports a face

Determining whether two polygons are the same

Schemes (New) [HB 63]

This module comprises general tools for working with schemes defined by polynomial equations in affine or projective space. Such tools include Groebner basis computation, dimension and image of maps, and linear algebra calculations formalized as linear systems on projective space. Maps between spaces may also be constructed and studied.

Creation of schemes by equations or implicit methods

Basic algebra-theoretic analysis of schemes: reducibility, dimension

Local geometric analysis: singularities, tangent spaces

Construction of maps between spaces

Coordinate manipulation functions, including birational transformations of the projective plane

Calculation of pullbacks of schemes by maps

Tools to enable the calculation of images of schemes by maps

Elliptic Curves [HB 65]

General Elliptic Curves

New features:

New function CremonaReference to look up an elliptic curve over the rationals in the installed Cremona database.

EllipticCurve and EllipticCurves extended to accept identifying strings (e.g. ``101A'') for curves in Cremona database.

Elliptic Curves over Finite Fields

Magma V2.5 contains an efficient implementation of the Schoof-Elkies-Atkin algorithm with Lercier's extension to base fields of characteristic 2. Calculations are performed in the smallest field over which the curve is defined, and the result is lifted to the original field.

New features for elliptic curves over finite fields:

Schoof-Elkies-Atkin algorithm for counting points in the cases of large characteristic and characteristic 2.

Use of Atkin's algorithm (as subset of the Schoof-Elkies-Atkin machinery) for point counting in small odd characteristic.

New functions IsProbablySupersingular, IsSupersingular, and IsOrdinary for elliptic curves over finite fields, replacing IsProvenSupersingular.

New function FactoredOrder for curves and points on curves.

Changes:

Removal of function Lift from documentation. Functionality preserved with BaseChange, BaseExtend, and ChangeRing.

TraceOfFrobenius as synonym for Trace.

Added functions names nTorsionSubgroup and pTorsionSubgroup, synonymous with previous mTorsionSubgroup.

Replacement of IsProvenSupersingular with new functions IsProbablySupersingular, IsSupersingular, and IsOrdinary for elliptic curves over finite fields.

Incidence Structures

Enumerative Combinatorics [HB 66]

New Features:

A variant of the DivisorSigma(i, n) function has been included which allows the user to give n in factored form.

The function RestrictedPartitions has been provided to construct the restricted partitions of an integer n, i.e., the partitions of n such that the parts belong to a designated set.

A variant of the Partitions function has been provided which generates only the partitions having a specified number of parts.

Graphs [HB 67]

A new clique finding algorithm based on the use of recursion and dynamic programming has been implemented. In some circumstances, such at the case of large graphs with high density, this algorithm is more efficient than the existing branch and bound algorithm. The existing clique and independent set functions have been rewritten so to allow users to specify the choice of clique algorithm. We welcome any user feedback regarding the comparative performance of these two algorithms.

New features:

The new function MinimumDominatingSet finds a minimum dominating set of an undirected graph.

The new functions OptimalVertexColouring and OptimalEdgeColouring find one optimal vertex, respectively, one optimal edge colouring, in an undirected graph.

The new function ChromaticPolynomial computes the chromatic polynomial for an undirected graph.

Functions AllCliques and AllIndependentSets find all cliques and independent sets, respectively, of a given size. No choice of algorithm is permitted.

Changes:

The function Clique now has an extra argument allowing the user to specify algorithm which is to be used. If no clique size is given, then Clique returns a maximum clique. If a clique size k is specified, then Clique returns a clique of size exactly k if the dynamic algorithm is chosen, or a maximal clique of size at least k if the branch and bound algorithm is chosen. The same comment applies to the function IndependentSet.

The functions CliqueNumber and IndependenceNumber also admit an extra argument allowing the user to choose the algorithm used.

Descriptions of the functions LargestClique and LargestIndependentSet have been removed from the Magma Handbook. The functions will be removed from Magma in a subsequent release.

Incidence Structures and Designs [HB 68]

Changes:

A new algorithm has been implemented to find a resolution in an incidence structure. The function IsResolvable has an extra argument allowing to choose the algorithm which is to be used. The previously existing algorithm, which is a backtracking algorithm, is always more efficient in the case where the incidence structure is resolvable. It is believed however that the new algorithm, which rests on a clique finding algorithm, performs significantly better when the incidence structure is not resolvable.

New features:

New function AllResolutions which finds all the resolutions in an incidence structure.