Release Notes V2.3 (January 30, 1998)

This screen provides a terse summary of the new features installed in Magma for release version V2.3 (January 30, 1998).

Summary

• A new powerful algorithm for computing normal subgroups in a permutation group has been implemented (Cannon-Souvignier algorithm) and an algorithm for computing the socle of a general permutation group has been implemented.
• The database of all transitive permutation groups of degree up to 22 constructed by Alexander Hulpke has been included.
• Given a matrix group over an infinite ring, it is now rigorously checked whether the group is finite before any structural computation is performed. Functions are now provided to test whether orders of matrices or matrix groups are infinite.
• The LLL algorithm has been significantly improved in speed (more than twice as fast than V2.2 for many examples). The exact integral method of de Weger is now available. The LLL function has many new parameters.
• A major new module for computing with lattices has been implemented. Features include: construction of standard and special lattices; minimum, kissing number, enumeration of short and close vectors, successive minima; LLL reduction, pair reduction, Seysen reduction; automorphism groups and isometry testing; G-lattices: invariant forms, endomorphisms and sublattices.
• A new module for computing with Lie algebras has been implemented, based on the ELIAS package of Willem de Graaf.
• New advanced algorithms for matrices have been implemented: a new Hermite form algorithm which yields a near-optimal transformation matrix based on the LLL algorithm, and new modular algorithms for computing nullspaces and inverses of matrices over Z and Q.

Function Removals and Changes

• The function CentralizingFieldAlgebra has been removed. (The function EndomorphismAlgebra should now be used.)
• The function DimensionOfCentralizingAlgebra has been removed. (The expression Dimension(EndomorphismAlgebra(M)) should now be used.)

Language and System Features [HB 1--5]

• The line editor has been modified to get round an annoying bug in X windows on Suns and other machines when large amounts of text are pasted in. The editor will now keep the terminal in raw mode after the return key is pressed (it used to switch the terminal back to cooked mode) so that if many lines are pasted in, many raw/cooked switches will not occur. If Magma then does a computation for more than a second, the terminal will be switched back to cooked mode.
• New procedure ClearVerbose to clear all the verbose flags (set their levels to zero).
• New procedure SetIgnoreSpaces to allow control of whether the line editor should ignore spaces when searching backwards or forwards.

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

• The pQuotient function has been upgraded so that its second return argument (the map from the fp-group onto the p-group) allows the computation of both images and preimages. Previously this map did not permit the calculation of preimages.
• The Tietze transformation code has been modified so that groups defined by coset tables are handled properly (function Simplify and others).
• An error in the function CosetAction which sometimes caused the homomorphism to incorrectly compute images has been fixed.
• The code processing the parameter SubgroupRelations for the function ToddCoxeter (and related functions) has been changed so that it now handles all positive values correctly.
• A serious error which caused the function CompositionSeries for soluble groups to frequently crash has been fixed.

Permutation Groups [HB 20]

• A new algorithm for computing normal subgroups in a permutation group has been implemented (Cannon-Souvignier algorithm). This algorithm is based on the use of an elementary abelian series and is far more powerful than the algorithm that it replaces. The relevant functions are MinimalNormalSubgroups and NormalSubgroups.
• An algorithm for computing the socle of a general permutation group has been implemented. Previously, the function Socle was restricted to primitive groups.
• The new conjugacy class algorithm for elements first installed in V2.2 has been further improved through the use of orbit-reduction techniques. In certain examples of groups having non-trivial Fitting subgroup, the computation time has been drastically reduced.
• The database of all transitive permutation groups of degree up to 22 constructed by Alexander Hulpke has been included. This incorporates the earlier database of Greg Butler and John McKay containing all transitive groups of degree up to 15. The database is accessed by the new function TransitiveGroup.
• A bug that sometimes arose when applying the inverse word map for permutation groups has been fixed.
• The function EARNS that computes the elementary abelian regular normal subgroup of a primitive permutation group was recently discovered to return on very rare occasions the trivial group when in fact there was a non-trivial EARNS. This has now been fixed.

Matrix Groups [HB 21]

• Given a matrix group over an infinite ring, it is now rigorously checked whether the group is finite before any structural computation (e.g., determination of order) is performed.
• New function IsFinite to determine whether a matrix group is finite.
• New function HasFiniteOrder to determine whether a matrix has finite order.
• The function creating unitary groups has been extended so as to create 1-dimensional unitary groups.
• An error has been corrected in the generators of the matrix group 2G2(q).
• In the library matgps, correct generators have been installed for a 27-dimensional representation of the triple cover of Fi_(22) (name fi22f4).

Characters of Finite Groups [HB 22]

• An obscure bug in the Dixon-Schneider character table algorithm that caused it to crash in certain very complicated examples has been fixed.

Integer Ring [HB 24]

• New functions Infinity and MinusInfinity and associated operations to allow symbolic positive and negative infinities.
• New function IsPrimePower to test whether an integer is a prime power.
• The function Divisors now gives an error if the number of divisors is not moderately small.
• New function Valuation.
• Function KroneckerSymbol fixed (did not handle negative arguments properly).
• Two errors in the ECPP primality proving code have been corrected (fixes supplied by F. Morain).

Residue Class Rings [HB 25]

• Creation function IntegerRing may now be given a factorization sequence to specify the modulus.
• New function FactoredModulus to return the factorization of the modulus of a residue class ring.

Univariate Polynomial Rings [HB 28]

• New function IsSeparable to determine whether an irreducible polynomial over a field is separable.

Multivariate Polynomial Rings [HB 29]

• The function EliminationIdeal now allows the same parameters as the procedure Groebner.
• Function Homogenization for homogenization of ideals.
• Multivariate GCD over Z and Q (GCD-HEU) improved further.
• The functions for quotient rings (affine algebras) have been expanded.
• New procedure MarkGroebner to mark the current basis of an ideal to be the (unique) Gr"obner basis of the ideal.

Algebraic Number Fields [HB 33--35]

• A bug which sometimes returned incorrect results for the trace of an element belonging to a quadratic field or the order of a quadratic field has been fixed.
• The function NumberField now tests its polynomial argument for being irreducible. A number of crashes have been reported which resulted from using a reducible polynomial when defining a number field.
• It is now possible to cast a rational integer element x of a quadratic order into the integers using Integers()!x (just as always has been the case for a general number field).
• The function ClassNumber applied to a quadratic field or order now calculates the order of the class group by default. This replaces Shanks' heuristic method in the imaginary case (which can return incorrect results) and the L-series computation in the real case (which is slow). This behaviour can be overridden using the optional parameter Al.

Real and Complex Fields [HB 36]

• Various bugs in the function Roots which computes the complex roots of a polynomial have been fixed.

Vector Spaces and R-spaces [HB 40]

• R-spaces over the residue class rings Z_m have been significantly improved and all matrix functions involving them have been reviewed.

Modules Hom(U, V) [HB 42]

• A new algorithm for the function HermiteForm has been implemented which is much more powerful and fast than previous algorithms and also yields a near-optimal transformation matrix based on the LLL algorithm.
• Very powerful new modular algorithms for computing nullspaces and inverses of matrices over Z and Q have been implemented. Using these algorithms, nullspaces or inverses of matrices of degrees around 1000, say, can be now computed for the first time.
• The function SmithForm may now be applied to matrices over fields (even though the result is trivial).
• Many algorithms for matrices over Q have been improved by developing fraction-free versions which work completely over Z.

Lattices (New Category) [HB 44]

Lattices: Introduction

A lattice in Magma is a Z-module contained in R^n with some additional structure, in particular an inner product. The basic information for a lattice is a basis, given by a sequence of vectors in R^n, and an inner product (cdot,cdot) given by a positive definite matrix M such that (v,w) = v M w^tr.

Central to the lattice machinery in Magma is a highly optimized LLL algorithm. The LLL algorithm takes a basis of a lattice and returns a new basis of the lattice which is em LLL-reduced which usually means that the vectors of the new basis have small norms. The Magma LLL algorithm is based on the FP-LLL algorithm of Schnorr and Euchner and the de Weger integral algorithm but includes various optimizations, with particular attention to different kinds of input matrices.

All timings given below are for a Sun 200Mhz UltraSPARC 2.

Lattices: Construction and Operations

• Creation of a lattice by a given generating matrix or basis matrix together with an optional inner product matrix
• Creation of a lattice by a given Gram matrix
• Construction of lattices from codes
• Construction of lattices from algebraic number fields
• Construction of special lattices, including the root lattices A_n, D_n, E_n; the laminated lattices Lambda_n (including the Barnes-Wall lattice Lambda_16 and the Leech Lattice Lambda_24); the Kappa lattices K_n, etc.
• Creation of and arithmetic with lattice elements
• Inner product, norm, and length of lattice elements with respect to the inner product of the lattice
• Conversion between a lattice element and its coordinates with respect to the basis of a lattice (in both directions)
• Action on lattice elements by matrices
• Creation of sublattices and superlattices, scaling of lattices
• Creation of quotient lattices (abelian group with isomorphism)
• Dual of a lattice, dual quotient of a lattice
• Arithmetic on lattices: sum, intersection, direct sum, tensor product, exterior square, symmetric square
• Conversion between lattices and Z-modules and Q-modules.

  Several interesting lattices are directly accessible inside Magma using standard constructions, e.g., root lattices and preimages of linear codes. For each lattice, a LLL-reduced basis for the lattice is computed and stored internally when necessary and subsequently used for many operations. This gives maximum efficiency for the operations, yet all the operations are presented using the external (``user'') basis of the lattice.

Lattices: Properties

• Rank, determinant, basis, basis matrix, inner product matrix, Gram matrix, centre density, testing for integrality and evenness, index in a superlattice
• Minimum of a lattice (which can also be asserted)
• Kissing number of a lattice
• Theta series of a lattice
• Enumeration of all short vectors of a lattice having norm in a given range
• Enumeration of all shortest vectors of a lattice
• Enumeration of all vectors of a lattice having squared distance from a vector (possibly) outside the lattice in a given range
• Enumeration of all vectors of a lattice closest to a vector (possibly) outside the lattice
• Process to enumerate short or close vectors of a lattice thereby allowing manual looping over short vectors having norm in a given range or close vectors having squared distance in a given range
• Pure lattice of a lattice over Z or Q
• Computation of a neighbour of a lattice with respect to a particular vector
• Construction of a fundamental Voronoi cell of a small-dimensional lattice
• Holes, deep holes and covering radius of a lattice
• Successive minima of a lattice
• Computation of the genus of an integral lattice

  Magma includes a highly optimized algorithm for enumerating all vectors of a lattice of a given norm. This algorithm is used for computing the minimum, the shortest vectors, short vectors in a given range, and vectors close to or closest to a given vector (possibly) outside the lattice. As an example, the 98280 (normalized) shortest vectors of the Leech lattice Lambda_24 are constructed in 6.8 seconds. The genus of the 12-dimensional Coxeter-Todd lattice K_12 is enumerated in 16 seconds and has 16 classes of lattices and mass 4649359/4213820620800 approx 0.000001103359.

Lattices: Reduction

• LLL reduction of lattices, basis matrices and Gram matrices (with numerous parameters)
• Seysen reduction of lattices, basis matrices and Gram matrices (for reducing a lattice and its dual simultaneously)
• Pairwise reduction of lattices, basis matrices and Gram matrices
• Orthogonalization and orthonormalization (Cholesky decomposition) of a lattice
• Testing matrices for positive or negative (semi-)definiteness

  The LLL algorithm can operate on either a basis matrix or a Gram matrix (and will use the Gram method even if given a basis matrix and it is deemed appropriate) and can be controlled by many parameters (delta constant, exact de Weger integral method or Schnorr-Euchner floating point method, step and time limits, selection of methods, etc.). The LLL algorithm can reduce matrices with very large entries as well as matrices having large sizes (e.g., number of rows well over 500).

Lattices: Automorphisms

• Automorphism group of a lattice
• Subgroup of the automorphism group of a lattice fixing specified bilinear forms
• Determination of whether two lattices are isometric
• Determination of whether two lattices are isometric in such a way that specified bilinear forms are fixed

  The computation of the automorphism group of a lattice and the testing of lattices for isometry is performed using the AUTO and ISOM programs of Bernd Souvignier. The automorphism group Co_0 of the 24-dimensional Leech lattice Lambda_24 is found in 175 seconds.

Lattices: G-Lattices

• Creation of G-lattices with associated operations
• Invariant lattice of a rational matrix group and the associated action (thus yielding an integral representation of the group)
• Bravais group of a finite rational matrix group
• Invariant sublattices of finite index
• Space of invariant bilinear forms
• Positive definite invariant form of a rational matrix group
• Endomorphism ring
• Centre of the endomorphism ring
• Dimension of the space of invariant bilinear forms, the endomorphism algebra or its centre using a modular algorithm

  The lattice machinery has been developed by Bernd Souvignier and Allan Steel.

Lie Algebras (New Category) [HB 48]

A finite-dimensional Lie algebra L over a field K is presented in terms of a basis for a K-vector space V together with a set of structure constants defining the multiplication of these basis elements.

The major structural machinery for Lie algebras has been implemented for Magma by Willem de Graaf and is based on his ELIAS package originally written in GAP.

Features:

• Creation of Lie algebras in terms of structure constants
• Construction of simple Lie algebras
• Direct sum
• Arithmetic
• Properties of elements: idempotent, unit, zero-divisor, nilpotent
• Trace and minimal polynomial
• Killing form
• Root system of a semisimple Lie algebra with a split Cartan subalgebra
• Adjoint representation of an element; Associated adjoint algebra
• Creation of subalgebras, ideals and quotient algebras
• Ideal arithmetic: Sum, product, powers, intersection
• Centralizer, normalizer
• Centre, commutator ideal, Jacobson radical, nil radical, solvable radical
• Cartan subalgebra, Levi subalgebra
• Series: Derived series, lower central series, upper central series
• Properties of algebras: Abelian, nilpotent, solvable, restricted
• Ideal structure: Maximal (minimal) left, right, two-sided ideals
• Decomposition of a semisimple Lie algebra into a direct sum of simple algebras
• Type of a simple algebra

Matrix Algebras [HB 50]

• New function Centralizer to compute the centralizer of a subalgebra.
• The computation of the order of a matrix over an infinite ring now checks that the matrix has finite order.
• New fast modular algorithm for computing determinants of matrices over Z and Q (proven correct Hadamard bound version and Monte-Carlo version).
• See also the section ``Modules Hom(U, V)'' for other new developments in matrix algorithms.
• A bug associated with expanding a matrix algebra over subfields has been fixed.
• A bug in multiplication of matrices over non-commutative rings has been fixed.

Finitely Presented Algebras [HB 51]

• The quo-constructor has been extended to allow sets and sequences of words to appear on the right hand side of the vertical bar.

• A serious bug in the Magma interface code to Steve Linton's vector enumerator has been corrected. This would sometimes result in incorrect matrices being returned by the function QuotientModule.

Elliptic Curves [HB 52]

• New function Random for an elliptic curve over a finite field.
• The function Order now works for a point of an elliptic curve over a finite field.
• New function QuadraticTwist to compute the quadratic twist of an elliptic curve over a finite field.
• Iteration over the rational points of an elliptic curve over a finite field now possible.
• Bug in local information computation of elliptic curves for large primes dividing the discriminant fixed.

Graphs [HB 54]

• Function RemoveVertices now removes the right vertices.
• Joining graphs together now includes the vertices in the specified order.
• Bug in OrbitalGraph fixed.
• Bug in sub constructor fixed -- it now works.
• An error in the function CayleyGraph which resulted in the graph returned being incorrectly set up has been fixed. The effect of the bug was that functions applied to the group returned by CayleyGraph would crash.