| From: DECWRL::"[email protected]" "Site Administration" 31-MAR-1992 21:29:28.32
To: being::edp
CC:
Subj: Re: Cayley inquiry
The Cayley System for Discrete Algebraic and Combinatorial Computation
Announcement of Version 3.8
Introduction
------------
The Cayley system for discrete algebra and combinatorial theory is designed
to solve hard problems in related areas of algebra, number theory and finite
geometry.
Cayley is not simply an alternative to other Computer Algebra systems. It
supports computation in important new areas of algebra (eg group theory,
modules) which are not included in the standard systems. Moreover, its design
is based on a computational model arising from the structural principles of
modern abstract algebra.
Cayley enables users to define and to compute in structures such as finite
and infinite groups, rings, fields and modules. Features include:
(*) User definition of the particular algebraic structures needed to solve a
problem. Each object arising in the course of the computation is then
defined in terms of these structures;
(*) Fast computation in important classes of algebraic structures;
(*) Correspondence of the user language data types to the central concepts
of modern algebra: algebraic structures, algebraic elements, sets,
sequences, and mappings;
(*) Over a thousand built-in functions capable of determining deep
structural properties of groups, rings and modules; and
(*) Data bases containing many useful examples of structures (mainly groups
at present) are available which further enhance the knowledge-base of the
system.
Approximately 250 institutions spread over 35 countries have installed the
system and it has found wide application to problems arising in many branches
of mathematical research including group theory, representation theory,
topology, knot theory, finite geometry, number theory, combinatorial theory and
graph theory. Further, the system has successfully solved problems arising in
application areas such as complexity theory, coding theory, data encryption,
communication network design, discrete fourier transforms, mathematical
crystallography and solid state physics. Cayley has been cited in approximately
600 papers and theses.
Standard Mathematical Structures Available in Version 3.8
---------------------------------------------------------
The kernel of the system contains machinery for representing and computing
with the fundamental types of algebraic structures. Much of the power of the
system derives from the inclusion of a large number of sophisticated algorithms
for group theory, representation theory, number theory, commutative algebra,
and finite geometry.
The structures and facilities implemented in version 3.8 (distributed fourth
quarter 1991) are summarized below.
(a) GROUPS
------
(a1) Finitely Presented Groups - Computing with Presentations
--------------------------------------------------------
This module is concerned with deducing properties of fp groups directly from
finite presentations.
- Word operations
- Coset enumeration (Todd-Coxeter algorithm)
- Low index subgroups
- Permutation representation on the cosets of a subgroup
- Subgroup presentations (Reidemeister-Schreier rewriting)
- Presentation simplification (Tietze transformations)
- Abelian quotient, nilpotent quotient
(a2) Finitely Presented Groups - Structure of a Finite Group
-------------------------------------------------------
Given a finitely presented group that is known to be finite, Cayley will
attempt to construct its Cayley graph using the Todd-Coxeter algorithm. If
successful, the Cayley graph provides a basis for efficient computation
with elements.
- Order of the group
- Representation of subgroups, quotient groups
- Permutation representation on the cosets of a subgroup
- Normalizer, centralizer, normal closure, core of a subgroup
- Intersection of subgroups, Sylow p-subgroup, centre, derived subgroup
- Derived-, upper central-, lower central-, p-central-, Jennings-series
- Conjugacy classes, normal subgroup lattice, subgroup lattice
- Darstellungsgruppe (small groups)
- Character table, automorphism group
(a3) Finite Soluble Groups
---------------------
Algorithms designed for finite soluble assume that the group is defined
by means of a power-commutator presentation. The process of commutator
collection may then be used to compute element products.
- As for (a2), plus
- Construction of a pc-presentation for a soluble group given as a
fp group, a permutation group or a matrix group
- Construction of split extensions and wreath products
- Frattini subgroup, minimal subgroups, maximal subgroups (p-groups)
- Hall pi-subgroups, Sylow basis, complement basis
- System normalizer, relative system normalizer
- Fitting subgroup, Carter subgroup
- Elementary abelian series, chief series
- Omega series, agemo series (p-groups)
The soluble group machinery is capable of working with groups having
composition length at least one hundred in the case of small primes.
(a4) Permutation Groups
------------------
Most algorithms for computing structural information about permutation groups
represent the group in terms of a base and strong generating set. Cayley is
capable of computing a base and strong generating set and hence basic
structural information for groups of degree up to 500,000. More detailed
computations can be performed in groups having degree up to 10,000.
- As for (a2), plus
- Construction of permutation representations for classical groups:
Eg PGL(n,q), PSp(n,q), PSU(n,q^2), etc
- Construction of wreath products with both types of action
- Orbits on points, sets of points, and sequences of points
- Systems of imprimitivity
- Base and strong generating set (Sims-Schreier algorithms)
- Stabilizer of a point, set of points, sequence of points
- Homomorphisms induced by actions on orbits and systems of imprimitivity
- Elementary abelian regular normal subgroup of a primitive group
- Socle of a primitive group, composition factors
(a5) Matrix Groups over Finite Fields and the Integers
-------------------------------------------------
- As for (a2), plus
- Generators for classical groups GL(n,q), U(n,q), Sp(n,q), Sz(q)
- Stabilizer of a vector, subspace
- Homomorphisms induced by actions on point and line orbits
(a6) Ordinary Representations of Finite Groups
-----------------------------------------
- Table of ordinary characters (Dixon-Schneider algorithm)
- Definition of class functions
- Arithmetic on class functions
- Construction of permutation characters
- Induction and restriction of a character
- Action of a group on the characters of a normal subgroup
- Decomposition of characters
(a7) Modular Representations of Finite Groups
---------------------------------------
See the section on KG-modules
(a8) Cohomology of Groups
--------------------
Cayley includes a module for computing cohomology of permutation groups
developed by Derek Holt of Warwick University.
- Schur multiplier
- First and second cohomology groups
- Group extensions
(b) FIELDS
(b1) Finite Fields
-------------
The current finite field module is designed for very efficient computation
in fields having up to a million elements. Efficiency is achieved by utilizing
a table of Zech logarithms to optimize the arithmetic operations.
- Arithmetic, trace, norm
- Square root, n-th root, logarithm
- Construction of extensions, embedding of subfields
- Minimal polynomial, primitive polynomial
- Finite field as a vector space over a subfield
(b2) Rational Field Q, Cyclotomic Fields, Quadratic Extensions of Q
--------------------------------------------------------------
- Arithmetic
- Integral basis
- Minimal polynomial
- Discriminant, norm and trace
- Embedding of subfields
(b3) The Real Field and the Complex Field
------------------------------------
Cayley contains an implementation of Richard Brent's MP package for multiple
precision floating point arithmetic. This permits the user to compute with
real or complex numbers to any specified precision.
- Arithmetic
- Constants: Pi, Euler's constant, Catalan's constant
- Elementary transcendental functions: log, exp, sin, cos, tan,
arcsin,arccos, arctan, sinh, cosh, tanh etc.
- Special functions: Bessel functions, Dawson's integral, error function,
complementary error function, exponential integral,
logarithmic integral, Riemann-zeta function.
(c) RINGS
(c1) The Ring of Integers
--------------------
The integer module contains a recent version of Arjen Lenstra's implementation
of the elliptic curve method for integer factorization.
- Infinite precision arithmetic
- Arithmetic functions: Jacobi symbol, Euler phi function etc
- Combinatorial functions eg partitions, Stirling numbers etc
- Primality testing (Miller-Rabin, Lucas-Lehmer tests)
- Primality proofs, primality certificates
- Generation of primes
- Factorization tools: Trial division, Fermat, Shanks, Pollard rho,
Pollard p-1, elliptic curve
(c2) The Residue Class Ring Z/Zm
---------------------------
- Arithmetic
- Properties of the group of units
(c3) Matrix Rings over an Euclidean Domain D
---------------------------------------
- Arithmetic
- Tensor product, skew tensor product
- Echelon form, reduced echelon form (D a field)
- Hermite and Smith normal forms
- Frobenius and Jordan normal forms (D a field)
- Minimal and characteristic polynomials
- Solution of systems of linear equations
(d) MODULES
(d1) Modules of n-tuples over an Euclidean Domain
--------------------------------------------
- Arithmetic
- Submodules and quotient modules
- Union and intersection of submodules
- Hermite basis for a submodule, membership of a submodule
- Invariant factors
- Minimal G-invariant submodule, where G is a group acting on the
module.
- LLL-reduced lattice basis for a Z-module
(d2) KG-modules, K a finite field, G a finite group
----------------------------------------------
Cayley includes a range of powerful functions developed by Gerhard Schneider
in Essen for computing with modular representations.
- Arithmetic
- Construction of a permutation module
- Submodules and quotient modules
- Submodules generated by a set of vectors (Spinning algorithm)
- Tensor product, induction and restriction of modules
- Splitting a reducible module (Parker Meataxe)
- Test a module for irreducibility, absolute irreducibility
- Test modules for equivalence
- Composition series and composition factors of a module
- Endomorphism ring of a module
- Construction of Hom(U, V), where U and V are KG-modules
- Test a module for indecomposability
- Vertices and sources
(E) INCIDENCE STRUCTURES
(e1) Graphs
------
A graph may be directed or undirected. A future release will allow
coloured and weighted graphs.
- Operations: union, join, product, contraction, switching etc
- Standard graphs: complete, complete bipartite, kcube
- Properties: connected, regular, eulerian, hamiltonian, planar
- Diameter, girth, circumference
- Cut-vertices, maximal independent sets, cliques
- Chromatic number, chromatic index, chromatic polynomial
- Graphs from groups: Cayley graph, orbital graph
- Automorphism group (B. McKay's algorithm), canonical labelling
- Test pairs of graphs for isomorphism
- Group actions on a graph: Orbits and stabilizers of vertex and
edge sequences
- Symmetry properties: vertex transitive, edge transitive,
k-arc transitive, distance transitive, distance regular
- Intersection numbers of a distance regular graph
A Simple Example
----------------
The output displayed below was produced by a simple Cayley run which first
constructs generators for the wreath product (under product action) of the
groups PGL(2,7) and Sym(5) (producing a group of degree 32768 and order
513,898,834,821,120) and then determines the isomorphism type of each of its
composition factors.
SUN/UNIX CAYLEY V3.8-188 Tue May 29 1990 10:33:40 STORAGE 16000000
>"Create generators for the groups PGL(2, 7) and S5."
>PGL27 = Projective General(2, 7);
>S5 = Symmetric( 5 );
>"Create generators for their wreath product G."
>G = pwreath(PGL27, S5);
>print degree( G );
32768
>print order( G );
513898834821120
"Now compute and print the composition factors."
>print composition factors( G );
COMPOSITION FACTORS OF GROUP K
------------------------------
G
| Cyclic(2)
*
| Cyclic(2)
*
| Alternating(5)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| A(1, 7) = L(2, 7)
*
| A(1, 7) = L(2, 7)
*
| A(1, 7) = L(2, 7)
*
| A(1, 7) = L(2, 7)
*
| A(1, 7) = L(2, 7)
1
END OF RUN.
The Data Bases
--------------
The use of mathematical data bases is an integral part of the system. The
following databases, built by various workers, are currently distributed with
the Cayley system:
- Simple groups of order less than a million (Campbell & Robertson)
- Permutation representations of sporadic simple groups
- Matrix representations (over GF(q)) of sporadic simple groups (Parker)
- Perfect groups of order less than a million (Holt & Plesken)
- Two-groups of order dividing 256 (O'Brien)
- Primitive groups of degree not exceeding 50 (Sims)
- Transitive groups of degree up to 15 (Royle)
- All groups of order up to 100 (Neubueser & Laue)
The Programming Language
------------------------
The system is provided with a high-level user programming language which
is intended to provide a natural vehicle for the specification of computations
with algebraic structures.
(*) The language is designed around the concepts of algebraic structure,
algebraic element, set, sequence and mapping.
(*) Constructors are provided which enable the user to define an instance
of one of the standard algebraic structures in a natural way.
(*) The use of a set/mapping notation enables the user to specify a
great range of constructions and computations in a concise and elegant
manner.
A more advanced user language is currently under construction. Among other
features, this language will permit users to implement new types of algebraic
structures.
Applications
------------
An estimated 600 papers and theses cite some application of Cayley (a list
containing some 250 of these citations may be obtained from the Computational
Algebra Group). We list a few examples of published applications.
(*) Group Theory
- A new construction for the Rudvalis simple group (Delgado & Weiss)
- Subgroup structure of M_12 (Buekenhout & Rees)
- Maximal subgroups of He and G(2,4) (Butler)
- Classification of the minimal 2-groups which act uniserially in
dimension 8 and having class less than 8 (Leedham-Green & McKay)
- Determination of groups of order 128 and 256 (Newman & O'Brien)
- Classification of all transitive groups of degree up to 12 (Royle)
(*) Representation theory
- Character tables of Sylow normalizers of the sporadic simple groups
(Ostermann)
- Vertices and sources of the 2-modular representations of the Mathieu
groups (Schneider)
- Group of units in a modular group ring (Sandling)
(*) Lattices
- Maximal finite irreducible subgroups of GL(n, Z), n ge 5 (Plesken)
- Constructing lattices with prescribed minimum (Plesken & Pohst)
(*) Ring Theory
- Verbal embeddings of rings in groups (Fournelle & Weston)
(*) Topology
- A computer search for homology 3-spheres (Dunwoody)
- Classification of hyperbolic manifolds from regular polyhedra
(Richardson & Rubinstein)
(*) Combinatorial Theory
- Classification of vertex transitive graphs on 24 points (Praeger & Royle)
- Analysis of the groups of perfect shuffles (Morrison)
- Construction of designs by partitioning sets (Sharry & Street)
(*) Finite Geometry
- Construction of affine planes (Assmus & Key)
- Geometries of the groups PSL(2, q) (Cruyce)
- Collineation groups of spreads of PG(3, q) (Volcheck)
(*) Differential Equations
- Existence of Liouvillian solutions of third order homogeneous
linear differential equations (Ulmer)
- Construction of symmetry adapted bases for the solution of 3-dimensional
partial differential equations (Ungricht)
(*) Discrete Fourier Transforms
- Construction of discrete Fourier transforms on abelian groups and
p-groups (Clausen)
Implementations
---------------
Cayley comprises approximately 350,000 lines of C. The system is distributed
only in binary form. An interface is provided to enable users to link their own
code with the Cayley system and then to call it directly from within the Cayley
language.
As of January 1992, versions of Cayley are available for the following
processors:
SUN 3, SUN 4
Apollo M680x0 based models, DN10000
DECstation
VAX/VMS
Macintosh running A/UX 2.01 or higher
IBM RS 6000 series
IBM RT
IBM PS/2 Models running AIX
IBM 30xx, 43xx under VM/CMS
Convex
Ordering Information
--------------------
Cayley is distributed on a subscription basis: a site acquires a licence
for a period (typically three years) and over that period is provided with
upgrades and new releases. At the present time the system is evolving
rapidly and a major new release is put out each year. The subscription price
varies according to processor type and whether the licencee is a university,
government, or industrial organization. As an illustration, the university
price for a version running on a SUN 4 fileserver together with its clients is
currently $US2000. A discount is available in certain cases for single
workstation versions.
For more information, or to order the system, contact
The Secretary
Computational Algebra Group
School of Mathematics
University of Sydney
NSW 2006
Australia
Email: [email protected]
Telephone: +61 2 692 3338
Fax: +61 2 692 4534
References
----------
W. Bosma and J.J. Cannon, A Handbook of Cayley Functions and Operators,
School of Mathematics, University of Sydney, October, 1991, 243 pages.
J.J. Cannon, Software tools for group theory, Proceedings of the
AMS Symposium on Pure Mathematics, 37 (1980), 495--502.
J.J. Cannon, An introduction to the group theory language Cayley, in
Computational Group Theory, edited by M.D. Atkinson, Academic Press,
London, 1984, 145--183.
J.J. Cannon, A Language for Group Theory, School of Mathematics,
University of Sydney, 1982, 1984, 1987, 300 pages.
J.J. Cannon, A computational toolkit for finite permutation groups,
in Proceedings of the Rutgers Group Theory Year, 1983--1984,
M. Aschbacher et al (eds), Cambridge University Press, New York, 1984, 1--18.
J.J. Cannon, The group theory system Cayley, to appear in
J. Symbolic Computation.
D.F. Holt, The CAYLEY group theory system,
Notices Amer. Math. Soc., 35 (1988), 1135--1140.
M.F. Newman and E.A. O'Brien,
A CAYLEY library for the groups of order dividing 128,
in Group Theory (Singapore, 1987), Walter de Gruyter,
Berlin, New York, (1989), 437--442.
G.J.A. Schneider, Computing with endomorphism rings of modular
representations, J. Symbolic Computation, 9, 5/6 (1990).
---------------
% ====== Internet headers and postmarks (see DECWRL::GATEWAY.DOC) ======
% Received: by enet-gw.pa.dec.com; id AA03508; Tue, 31 Mar 92 18:28:08 -0800
% Received: from galois.maths.su.oz.au by adder.maths.su.oz.au with SMTP (5.61++/11.2 to SMTP)id AA10715; Wed, 1 Apr 92 12:27:18 +1000
% Date: Wed, 1 Apr 92 12:27:13 EST
% From: [email protected] (Site Administration)
% Message-Id: <9204010227.AA08903@galois>
% Received: by galois (4.1/10.3 to SMTP)id AA08903; Wed, 1 Apr 92 12:27:13 EST
% To: being::edp
% Subject: Re: Cayley inquiry
|