[Next] [Prev] [_____] [Left] [Up] [Index] [Root] 
Release Notes V2.3 (January 30, 1998)


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.

    

    • 

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