V2.10-1 (14 October 1996)

Here is a terse summary of the new features installed in Magma for version V2.10 since June 21, 1996. See the release notes for version V1.30 for all new features introduced into Magma in 1995.

Summary

A new Tietze program for simplifying presentations of finitely-presented groups

A new category for groups whose elements are represented by straight-line programs: Blackbox groups

A new algorithm for computing conjugacy classes in permutation groups

Major expansion of the Groebner basis machinery including the addition of a Hilbert series-driven Buchberger algorithm

Introduction of gradings for polynomial rings

Invariant rings of finite groups

Modules over the ring K[x_1, ..., x_n]

An extensive revision of the graph theory module to bring its semantics into line with the other incidence structure categories. Graphs may now have labelled vertices and edges. Directed graphs may have loops.

A faster collineation group algorithm for projective planes

A major expansion of the coding theory module to include bounds, many new code constructions, decoding, automorphism groups over GF(p) (prime p) and GF(4), and much else

Extensive revision of the way in which the automorphism group of an incidence structure acts on the structure

Documentation

Handbook: Four new chapters; many other chapters have extensive changes and additions

An Introduction to Magma: Extensive revision/updating of almost all chapters

Language and System Features [HB 1--4]

printf statement for formatted printing now has field widths [HB 3.3]

-b option to suppress banner and other information at startup and exit [HB 4.1]

Function StringToInteger now allows base 36 (was 35) and lower-case characters in the input string [HB 3.2]

Aggregate Data Types [HB 7]

Function IsDisjoint, to test whether two sets are disjoint

General Groups [HB 15]

New function IsTrivial

New function IdentityHomomorphism

Finitely Presented Groups and Soluble Groups [HB 16, 19]

Function AbelianQuotientInvariants automatically computes a coset table when possible

New fast presentation simplification package due to Havas and Lian installed

Function pQuotient now returns the homomorphism in addition to the p-quotient

Automorphisms for StandardPresentation/GeneratepGroups may be supplied as homomorphisms.

A number of bugs related to performing operations on subgroups represented by coset tables have been fixed

Numerous bugs caused by the old Tietze package have now been fixed with the installation of the new Havas-Lian package

Function ToddCoxeter was modified so as to accept trivial defining relations and subgroup generators

Bug in function Coincidence fixed

GeneratepGroup bug fixed (if pCovering group)

Function AutomorphismGroup modified so as to incorporate inner automorphisms

Bug in function StandardPresentation when applied to abelian groups fixed

A large number of leaks in functions pQuotient, StandardPresentation and GeneratepGroups removed

Blackbox Groups (New Category) [HB 17]

Blackbox groups may be viewed as finitely presented groups in which words are represented as ``straight-line'' programs. They allow very fast evaluation of long words in permutation and matrix groups where the words are defined inductively.

Construction

Arithmetic with straight-line programs

Homomorphism from a blackbox group onto an arbitrary group

Random generation of elements (Cellar, Leedham-Green, Murray, Niemeyer, O'Brien algorithm)

Abelian Groups [HB 18]

Function FPGroup extended to construct a GrpFP representation of an abelian group

Bug in function CosetTableToRepresentation fixed

Permutation Groups [HB 20]

G-set mechanism generalized and additional permutation group functions generalized to work for G-sets (e.g., IsConjugate)

Extension algorithm for function Classes installed

Conjugacy classes for symmetric/alternating groups now written down directly

Direct product of permutation groups now returns sequences of inclusion and projection maps

Better strategy for evaluating function IsSolvable

Order filter on subgroup classes functions improved

G-set changes (in particular, semantics of GSet(G, SetIndx) changed).

Automorphism groups of combinatorial structures are now given on the support {1 .. n}. The automorphism group now acts on the structure via the G-set mechanism

Parameter names for function ClassMap changed

Limit of 10000 elements for function Class(G, x) removed

Bug in function OrbitImage fixed

Matrix Groups [HB 21]

Base point selection strategy revised

Constructions provided for the orthogonal groups and the exceptional family G_2(q).

Construction of semi-linear groups

Tests for irreducibility, absolute irreducibility, semi-linearity

Homomorphism induced by action of a reducible group on a G-invariant submodule and its quotient module

Image of a tuple bug fixed

Characters of Finite Groups [HB 22]

Function ClassFunctionSpace is now synonomous with and preferred to function CharacterRing

Characters can be constructed as elt<R | ... : Character := true>

Function CoefficientField for a character ring

Functions OrthogonalComponents/SymplecticComponents for writing down (orthogonal/symplectic) components of the tensor powers of a character

New irreducible characters are automatically inserted into a central list of irreducibles

Function RemoveIrreducibles removes known irreducibles from a list of characters

Function ReduceCharacters reduces the norms of a list of characters by computing differences

Function KnownIrreducibles

Coercion of a scalar into a class function generalized

Magma printing of cyclotomic field elements

A bug in character subtraction where it may miscompute the characterness type of the class function has been fixed

Integer Ring [HB 23]

Kronecker Symbol (KroneckerSymbol)

Determination of whether an integer is square free (IsSquareFree)

Sum of divisors of a positive integer (SumOfDivisors)

Number of divisors of a positive integer (NumberOfDivisors)

Negative (non-zero) factorization records

New functions for factorization records: IsSquareFree, MoebiusMu, SquareFree, NumberOfDivisors, SumOfDivisors

Multivariate Polynomial Rings [HB 29]

Construction of graded polynomial rings with specific weights on the variables (relevant functions are PolynomialRing, VariableWeights, WeightedDegree, IsHomogeneous, HilbertSeries) [HB 29.20]

Hilbert-driven Buchberger algorithm to efficiently compute the Groebner basis of a homogeneous ideal when the Hilbert series is known (function HilbertGroebnerBasis) [HB 29.22]

Multivariate GCD over Z and Q improved

Groebner basis computation over function fields significantly improved.

Function ProbableRadicalDecomposition to compute a probabilistic prime decomposition of the radical of an ideal

Function GroebnerBasisUnreduced to compute an unreduced Groebner basis

Function EasyIdeal to access ``easy''-order ideal of a given ideal

Parameters for the function GroebnerBasis

Invariant Rings of Finite Groups (New Category) [HB 30]

Magma contains a powerful new module for computing with invariant rings of finite groups. Many of the algorithms are based on the work of Gregor Kemper (IWR, Universitaet Heidelberg). Given a matrix or permutation group G, one can construct the invariant ring R of G over the ground field K and then determine many structual properties of R. Magma allows computation in invariant rings over ground fields of arbitrary characteristic. Of particular interest is the modular case; i.e., the case where the characteristic of the ground field divides the order of the group - Magma incorporates powerful algorithms to handle this case also.

Invariant ring structure of a finite matrix or permutation group

Efficient construction of independent homogeneous invariants of an invariant ring for a specific degree (function InvariantsOfDegree)

Advanced storage and lookup techniques for the Reynolds operator (function ReynoldsOperator)

Computation of Molien series (function MolienSeries)

Efficient construction of primary invariants of near-optimal degrees (function PrimaryInvariants)

Efficient construction of secondary invariants (function SecondaryInvariants)

Efficient construction of fundamental invariants (function FundamentalInvariants)

Representation of an invariant ring R as a graded module over the algebra generated by the primary invariants and construction of the explicit isomorphism (function Module)

Multiple verbosity levels

Hilbert series of an invariant ring (function InvariantRing)

Determination of whether an invariant ring is Cohen-Macaulay (function IsCohenMacaulay)

Algebraic Number Fields [HB 33, 35]

Memory leaks in class group computation fixed

Function IsMaximal for an order of a quadratic field

Function IsEquationOrder for an order of a quadratic field

Function IsIntegral for an ANF element now uses the maximal order, not the equation order

Order printing no longer leaves an extra blank line

Extension of an order by an element works now

Function FactorBasis for an ANF

Function RelationMatrix for an ANF

Function MinkowskiBound for maximal orders

Extension ext<O | 1> for an order O returns O, rather than a transformation of it by the identity

Modules Hom(U, V) [HB 42]

Explicit construction of Hom(H_1, H_2) for homomorphism modules H_1 and H_2 with left or right matrix action

Construction of the reduced module of a homomorphism module whose elements are with respect to the bases of the domain and codomain (not just the generic bases of these)

Modules over K[x_1, ..., x_n] (New Category) [HB 43]

A new category for modules over multivariate polynomial rings has been installed. Many of the module operations are translated into ideal operations, where the Groebner basis machinery may be applied, by adding a column field to each monomial. This method is much more efficient than introducing new variables to represent the columns since the number of columns does not affect the total number of variables.

Construction of modules with TOP (``term over position'') or POT (``position over term'') module orders

Construction of graded modules with weights on the columns (determining homogeneity)

Construction of submodules and quotient modules

Access, Arithmetic, Predicates, etc. on module elements

Construction of Groebner bases of modules

Construction of minimal bases of homogeneous modules (function MinimalBasis)

Sum and quotient of submodules

Computation of the hilbert series of (the quotients of) homogeneous modules

Construction of syzygy modules (functions SyzygyModule and MinimalSyzygyModule)

Finitely presented Algebras [HB 45]

Bug fix in the Linton vector enumerator

Elliptic Curves [HB 46]

Mutation assignments P +:= Q and P *:= n now work properly

New functions NaiveHeight(P) and CanonicalHeight(P)

New function IsPoint(S, E)

Elliptic curve isomorphism maps now allow preimages

Most functions which used to require integral curves will now accept rational curves instead - the exceptions are functions dealing with the heights of points

Memory leaks fixed (curves will actually be deleted now)

Enumerative Combinatorics [HB 47]

Function Bernoulli has been changed to BernoulliNumber (although Bernoulli will remain for a while for backwards compatibility), and the function now returns a FldRatElt rather than the FldPrElt it used to

Function Binomial(n, r) now works for all integers n, r

New functions BernoulliPolynomial(n), HarmonicNumber(n), EulerianNumber(n, r)

New functions Subsets(S), Multisets(S, k), Subsequences(S, k)

New functions NumberOfPermutations(n, r), Permutations(S, k), Permutations(S)

Graphs [HB 48]

The graph constructor now has the use of the support

Functions Support(G) (graph G) and Support(V) (vertex set V)

Digraphs may now have loops in their edge specifications

G.i no longer works for graphs

Category names for Graph edges and vertices (and sets thereof) have been changed to GrphVert, GrphVertSet, GrphEdge, and GrphEdgeSet

Functions V.i and E.i now return the i-th vertex and edge respectively

All functions which used to return a graph only now also return the vertex and edge sets

Function Index(v) for vertex v

Loops in digraphs are represented in the incidence matrix by a column with precisely one non-zero element, which may be either 1 or -1; when returned, this element will be -1

Switch is now not allowed for digraphs (avoids problems about loops)

Vertex, edge and graph printing has been changed to use the support, or the standard support if Minimal print level is specified

New function StandardGraph(G)

New function ChangeSupport(G, I) and procedure ChangeSupport(~G, I)

Function AutomorphismGroup now returns a permutation group on the standard support and the edge and vertex G-sets

Graphs may now have vertex and edge labels

For convenience, there are now many functions to mutate graphs by referring to their vertices as integers; this avoids having to use the vertex and edge sets

Function EdgeGroup now returns the appropriate G-set and the support of the group G is the standard support

Incidence Structures and Designs [HB 49]

Functions IncidenceStructure(G) (graph G) and IncidenceStructure(I) (incidence structure I) now also return point and line sets

Function D.i no longer works for designs

Function AutomorphismGroup now returns the automorphism group on the standard support. Action on the design is obtained through the use of G-sets.

Function BlockGroup now returns the appropriate G-set and the support of the group G is the standard support

Finite Planes [HB 50]

Functions Eltseq and Coordinates now work for points and lines

Function PointGraph for a plane

Functions AffinePlane(P, l), AffinePlane(I), and ProjectiveEmbedding(A) now return point and line sets as well

Category names ProjPl and AffPl changed to PlaneProj and PlaneAff respectively

Function CollineationGroup now returns the collineation group on the standard support. Action on the design is obtained through the use of G-sets

New optimized algorithm for computing collineation groups of projective planes

Function LineGroup now returns the appropriate G-set and the support of the group G is the standard support

Error-correcting Codes [HB 51]

The coding theory module has been considerably expanded. Many new functions have been added for constructions of standard codes, bounds associated with codes, and decoding. Permutation group actions on codes have been extended to allow monomial actions on non-binary codes.

New standard linear code construction functions (SimplexCode)

New simple linear code construction functions (EvenWeightCode, etc.)

New standard cyclic code construction functions (CyclicCode given roots)

New standard alternant code construction functions (ChienChoyCode, FireCode, GabidulinCode, GeneralizedSrivastavaCode, ReedSolomonCode, SrivastavaCode)

New functions ConcatenatedCode and JustensenCodes for the construction of concatenated and Justensen codes

Function AllInformationSets to compute all information sets of a code

Functions CheckPolynomial, GeneratorPolynomial, and Idempotent for a cyclic code

Function LeeWeight

New Predicates to test properties of codes (IsMaximumDistanceSeparable, IsNearlyPerfect, IsPerfect, IsProjective, IsSelfDual, IsWeaklySelfDual)

Function MinimumDistance as synomym for MinimumWeight for linear codes

Function Decode for decoding of received vectors

Functions GilbertVarshamovBound, EliasAsymptoticBound, etc. for upper and lower bounds associated with codes

Functions BKABdsInfoRate, BKBdsCardLargestCode, etc. for best known asymptotic bounds

Functions MattsonSolomonTransform, InverseMattsonSolomonTransform to compute Mattson-Solomon transforms

Functions KrawchoukPolynomial, KrawchoukTransform, and InverseKrawchouk to compute Krawchouk polynomials

New permutation and monomial actions of permutation groups on codes

Improved automorphism group functions (new version of J. Leon's PARTITION package)

Calculation of automorphism groups and testing equivalence extended to codes over GF(p) (prime p) and GF(4)

Function PermutationGroup to compute the permutation automorphism group of a non-binary code

Function AutomorphismSubgroup to compute a subgroup of the full automorphism group of a code

Function AutomorphismGroupStabilizer to compute the subgroup of the full automorphism group of a code which stabilizes a specified number of initial base points

Function IsEquivalent to test equivalence of codes for codes over GF(p) (prime p) and GF(4)

Function Aut to construct power structure of all automorphism maps