Subject: Sun-Symbolic-Math Digest v1n3 Sun-Symbolic-Math Digest Volume 1 : Number 3 Editor: Steve Christensen Today's Topics: Administrative Stuff CAYLEY ------------------------------------------------------------------ Subject: Administrative Stuff Several of you have emailed with a request to make contributed files accessible to people without ftp connections. I am looking into possible mail distribution. When this is set up (in the next few weeks) I will announce it in a mailing. Bitnet connections for this purpose are not yet possible. The number of people on the mailing list has now reached 100 with a number of redistribution centers around the world. I am very pleased with the enthusiasm for this endeavor and hope that you will all contribute as much as possible. Steve Christensen ----------------------------------------------------------------------- Date: Mon, 29 Feb 88 11:33:28 GMT From: James Davenport Subject: CAYLEY John Cannon (the principal author of CAYLEY) has asked me to forward the following description to you. James Davenport The Cayley System for Discrete Algebraic and Combinatorial Structures Greg Butler and John Cannon Department of Computer Science, Department of Pure Mathematics University of Sydney 1. Introduction The Cayley system for discrete algebra and combinatorial theory is designed to solve hard problems in related areas of algebra, number theory and combinat- orial theory. The structures targeted include finite and infinite groups, fields, matrix rings, polynomial rings, modules, associative algebras, finite geometries, finite graphs and linear codes. Primary objectives include the provision of facilities which can (a) perform arithmetic efficiently in a variety of groups, rings and fields, (b) compute deep structural properties of groups and number fields, and (c) study algebraic and combinatorial structures under the action of a group. The Cayley system is quite different to the class of classical algebra systems of which MACSYMA is typical. The differences include:- (*) The user is able to create a large number of different computational domains in which he or she can then proceed to calculate. With the exception of Scratchpad, and a small number of special purpose group theory packages (eg CAS, SOGOS, CAMAC), other computer algebra systems restrict the user to computing within a small number of predefined structures - typically polynomial rings over finite fields, the integers, and rings of real or complex functions. (*) The system is designed to answer questions not only about individual elements of an algebraic structure, but more importantly, to answer questions about the structure as a whole, eg is the structure finite or infinite; list the elements that commute with all the elements of the structure. All existing computer algebra systems are designed to compute with particular elements of a structure (eg a polynomial ring). None of them has the capability of represent- ing entire structures and obtaining global information about such structures. (*) The objects (types) which the system manipulates include the standard objects of modern algebra: algebraic structures, algebraic elements, sets, seq- uences, and mappings. (*) The system currently contains a large amount of mathematical knowledge in the form of algorithmic knowledge (procedures),and knowledge of a large number of critical examples and their properties (data base knowledge) while in the longer term it will additionally contain formal knowledge (definitions, theorems, etc). Such a system has wide application to problems arising in many branches of mathematical research. Such areas include group theory, representation theory, algebraic topology, geometry, number theory, combinatorial theory and graph theory. Further, applications arise in many areas of modern applied mathematics including complexity of algorithms, coding theory, data encryption, communicat- ion network design, mathematical crystallography and solid state physics. 2. Overall Structure of the System The system is designed to perform highy efficient computation in a carefully chosen collection of algebraic and combinatorial structures. The structures are chosen firstly on the basis of utility, and secondly, on the assumption that effective algorithms either exist or can be designed for them. The language permits the user to implement new structures but computation in user-programmed structures can be expected to be considerably less efficient. The system consists of four principal functional components: (1) A very high level programming language that is designed around the basic concepts of modern algebra: structure, set and mapping; (2) A large run-time library containing polished implementations of a wide range of basic algebraic, geometric and combinatorial algorithms; (3) A database containing mathematical knowledge (mainly group theoretic and geometric knowledge); (4) A deduction engine. 3. Computational Domains When the complete system is operational it will support computation in the following types of algebraic and combinatorial structures: (*) Fields finite fields - GF(q) rationals - Q cyclotomic number fields p-adic number fields simple extensions of the rationals (typically low degree) (*) Rings integers - Z integer residue class ring - Zm ring of integers of an algebraic number field matrix rings polynomial rings, R[x,...,z], where R is GF(q), Zm, or Z (*) Associative algebras matrix algebras (*) Modules K-modules, where K is GF(q) Z-modules KG-modules, where K is GF(q) and G is a finite group (*) Monoids finitely presented monoids (*) Groups finitely presented groups finite p-groups finite soluble groups permutation groups matrix groups (*) Group rings group rings over finite fields, residue class rings, and the ring of integers (*) Geometries group geometries projective geometries abstract geometries (*) Graphs undirected graphs directed graphs (*) Block designs (*) Linear Codes The current release of Cayley (V3.6) supports computation in groups, matrix rings, finite fields, and modules. The first release of Cayley Version 4 due out in 1989 will also include polynomial rings, monoids, graphs and codes, while the remaining structures will follow . 4. The Algorithm Knowledge Base The algorithm portion of the knowledge base has the ability to compute detailed information about a very rich class of particular instances of math- ematical structures. Over the past two decades a great deal of work has been done on devising algorithms for group theory, representation theory, number theory, polynomial ring theory, and combinatorial structures. Most of these algorithms are now either included in the Cayley system or are in the process of being implemented. We briefly indicate the nature and type of the algorithms, both already implemented and planned, for the complete system. (*) Fields Arithmetic Discriminant Integral basis Group of units Class group Status: Only finite fields are available in V3. (*) The Ring of Integers Infinite precision arithmetic Primality testing Factorization Congruences Primitive roots Quadratic reciprocity Moebius inversion Status: Infinite precision integer arithmetic is available in V3. (*) Matrix Rings Arithmetic Subring generated by a set Status: Available in V3. (*) Associative algebras Arithmetic Status: To come in V4. (*) Polynomial Rings Arithmetic Gcd Factorization Ideal generated by a set (Groebner basis) Status: Currently being implemented. (*) Modules Arithmetic Submodules and quotient modules Submodule invariant under group action Endomorphism ring Status: Modules over finite fields have been implemented by G. Schneider as part of V3. (*) Monoids Knuth-Bendix algorithms Status: To come in V4. (*) Finitely Presented Groups Word operations Coset enumeration Subgroup presentations (eg Reidemeister-Schreier) Presentation simplification Abelian quotient Nilpotent quotient Generation of p-groups Soluble quotient Structure of small finite finitely-presented groups Status: All are available in V3 except p-group generation and a soluble quotient algorithm. Versions of the Todd-Coxeter and nilpotent quotient algorithms implemented by G. Havas and M. Newman are included. (*) Finite p-groups Order of the group Fast multiplication of elements (collection) Construction of a subgroup Normalizer, centralizer, normal closure of a subgroup Intersection of subgroups Core of a subgroup Centre, derived subgroup, Frattini subgroup, Fitting subgroup Derived series, upper central series, lower central series Conjugacy classes Normal subgroups Automorphism group Isomorphism of two groups Character table Normal subgroup lattice Subgroup lattice (for small groups) Status: All available in V3 except automorphism group and isomorphism testing. The system is capable of computing with groups of order p^50 while some functions are applicable to groups of order up to p^200, for small primes p. The subgroup lattice code used is that developed for a general group by V. Felsch in Aachen. (*) Finite Soluble Groups As for p-groups, plus Hall pi-subgroups Sylow basis Complement basis System normalizer Relative system normalizer Carter subgroup Complements and supplements Status: All are available in V3 except complements and supplements. The current facilities can handle soluble goups having composition length up to 50. (*) Permutation Groups As for p-groups, plus Base and strong generating set Sylow p-subgroup Regularity, transitivity, primitivity Orbits on points, sets, sequences Systems of imprimitivity 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 Status: All are currently available in V3. It is possible to compute a base and strong generating set for a group having degree up to 50,000. More detailed computations can be performed in groups having degree up to 10,000. (*) Matrix Groups over Finite Fields As for p-groups, plus Sylow subgroup Stabilizer of a vector, subspace Homomorphisms induced by actions on point and line orbits Status: Available for matrix groups of small degree in V3. (*) Representation Theory of Groups Table of ordinary characters Construction of KG-modules, K a finite field Induction and restriction of representations Splitting a reducible module Composition series for a KG-module Simple submodules Endomorphism ring of a KG-module Indecomposability Vertices and Sources Status: A good deal of this machinery is avaliable in V3. Much of this machinery has been developed for Cayley by G. Schneider in Essen. It is possible to split modules of dimension up to 1000. (*) Group rings Arithmetic Jenning basis Canonical maps: augmentation, trace, involution Recognize units, idempotents Status: To come in V4. (*) Cohomology of Groups Calculation of first and second cohomology groups Group extensions Status: Cohomology programs written by Derek Holt are to be installed in the fourth quarter of 1988. (*) Graphs Operations Properties: connected, eulerian, hamiltonian, regular, planar Cliques Diameter, circumference, girth Chromatic number, chromatic index, chromatic polynomial Automorphism group Group actions on a graph Status: This module will be installed in the first quarter of 1988. (*) Geometries Define: group geometries, projective geomeries and abstract geometries Test incidence of a pair of objects Orbits, stabilizers under group actions Status: To come in V4. (*) Linear Codes Weights Actions of an automorphism Automorphism group Status: To come in V4. 5. The Knowledge Base As indicated above, the system will ultimately utilize three types of knowledge: procedural knowledge, knowledge of particular examples, and theoretical knowledge (definitions and theorems). We believe that the power of such a system can be greatly enhanced if it has the capability of utilizing an extensive body of knowledge. The examples database will contain a large number of critical examples of groups, geometries and other combinatorial structures. It is possible to identify a body of examples of manageable size which are traditionally used in great variety of studies in group theory, representation theory, and geometry. For example, those finite simple groups having representations of manageable size are used extensively in all kinds of studies. Already a number of databases are present in the Cayley system and others are in preparation by various groups of workers. These include (*) Simple groups of order less than a million (*) Sporadic simple groups having reasonable degree representations (*) Simple groups of Lie type having reasonable degree representations (*) Geometries on which these simple groups act (*) Perfect groups of order less than a million (*) Two-groups of order dividing 256 (*) Primitive groups of degree up to at least 50 (*) Transitive groups of degree up to 15 (*) All groups of order up to 240 A group database would typically contain definitions and properties of groups. For example, we might store the group order, a presentation, character table, modular representations, maximal subgroups, Schur multiplier etc. A novel feature of the data base is that it will have the capability of storing information about infinite families of groups. This can be achieved in those situations where it is possible to provide an algorithm which, given the parameters describing a particular member of some family, will produce, for example, the information for that particular group. For example, while an individual presentation would be stored for each sporadic simple group, in the case of a family, such as the alternating groups, one would employ a procedure to generate a presentation for any particular alternating group. The use of such databases will be seamlessly integrated into the system, so that when the system is asked to solve some problem, it might attempt to solve it directly, or attempt to deduce the answer from information stored in the data base. 6. The Programming Language The system is provided with a high-level user programming language which is intended to provide a natural vehicle for the expression of computations with algebraic and combinatorial structures. A new language is being implement- ed for V4 which has the following capabilities: (*) The language is designed around the concepts of algebraic structure, algebraic element, set, sequence and mapping. (*) It permits the user to specify a broad range of algebraic and combin- atorial structures in a fairly natural manner. (*) 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. (*) The language provides a mechanism whereby a user can make a broad range of assertions about mathematical objects that have been defined earlier. (*) The language will eventually incorporate a query language for the database. (*) The language processor will also eventually include a planner whose task it is to devise an efficient strategy for performing the desired calculation. The executable program synthesized by the planner will utilize both the algor- ithm base and the examples base. The flavour of the V4 language may be obtained by examining the following program for computing the degrees of the characters of a p-group. The algorithm is due to M. Slattery and both the algorithm and the V3 implementation of the algorithm may be found in the Journal of Symbolic Computation 2 (1986), 51-58. function chardegs( G ); "Given a p-group defined by a PNG-presentation, determine the degrees on the characters of G. The character degrees are returned as a sequence whose i-th entry contains the number of characters having degree p^i." p := forder( G )[1]; if abelian( G ) then s := [ order( G ) ]; else x := pelt( centre( G ), p ); s := chardegs( G / < x > ); t := reldegs( G, < x >, p ); s := [ s[i] + (p-1)*t[i] : i in [1..#s] ] cat [ (p-1)*t[i] : i in [#s+1..#t]]; end if; return s; end function; function reldegs( G, N, p ); if abelian( G ) then s := [ index( G, N ) ]; else Q, f := G / N; Z := centre( Q ); M := (< pelt( Z, p ) >)@f; C := centralizer( G, M ); if cyclic( M ) then t := reldegs( C, M, p ); if G eq C then s := [ p*t[i] : i in [1..#t] ]; else s := [ 0 ] cat t; end if; else s := empty; y := rep { x : x in M - N | order(x) eq p }; if G eq C then x := pelt( N, p ); for i := 1 to p do Q, f := G / < y*x^i >; t := reldegs( Q, (M)f, p ); s := [ s[i] + t[i] : i in [1..#s] ] cat [ t[i] : i in [#s+1..#t] ]; end for; else Q, f := C / < y >; t := reldegs( Q, (M)f, p ); s := [ 0 ] cat t; end if; end if; end if; return s; end function; function pelt( H, p ); y := rep { x : x in H | x ne H(id) }; return y^(order(y)/p); end function; 8. Current User Base A version of Cayley primarily restricted to computation with groups has been distributed since 1982. As of January 1988, some 140 institutions in 21 countries have acquired licences to run the system. These institutions include: ANU U of California-Santa Barbara AT&T Bell Laboratories U of Chicago Birmingham U U of Illinois CUNY-Graduate Center U of Manchester Ecole Normale Superieure U of Manitoba ETH, Zuerich U of Michigan Kansas State U U of Minnesota King Saud U-Riyadh U of Pittsburg National U of Singapore U of Texas Olou U-Finland U of Wisconsin-Madison Princeton U U Essen Queen Mary College U Erlangen-Nuernberg Rutgers U U Giessen RWTH Aachen U Karlsruhe Tata Institute-Bombay U Koln Tel Aviv U U Milan U of Arizona U Tuebingen U of California-Berkeley U College Galway U of California-Los Angeles Warwick U 9. Applications Various releases of the current Cayley system have been distributed since 1982. The capabilities of this system are mainly restricted to group theory. Some 200 papers and theses cite some application of Cayley. We list some examples of situations where it has been successfully applied: ALGEBRAIC GRAPH THEORY (*) Presentations for cubic graphs - Biggs. (*) A new construction of the Rudvalis simple group - Delgado and Weiss. (*) Classification of all vertex transitive graphs on 24 points - Praeger and Royle. COMBINATORIAL THEORY (*) Construction of perfect difference sets - Atkinson. (*) Counting with groups and rings - Plesken. (*) Analysis of the groups of perfect shuffles - Morrison. GEOMETRY (*) Geometries of the groups PSL( 2, q) - Cruyce. (*) Recognition of collineation groups of certain projective planes - Lorimer (*) Collineation groups of spreads of PG(3, q) - Volcheck. GRAPH THEORY (*) Construction of a family of regular graphs that are hamiltonian - Berger. GROUP THEORY (*) Subgroup structure of M12 - Buekenhout. (*) Maximal subgroups of He and G(2, 4) - Butler. (*) Analysis of a family of finitely presented finite groups having deficiency zero - Kenne. (*) Classification of the groups associated with the "triangle" chamber system - Koehler and Timmesfeld. (*) Classification of the minimal 2-groups which act uniserially in dimension 8 and having class less than 8 - Leedham-Green and McKay. (*) Determination of groups of order 128 and 256 - Newman and O'Brien. (*) 2-groups data base - Newman and O'Brien. (*) Structure of the Sylow 2-subgroup of M24 - Schoenwaelder. GROUP RINGS (*) Group of units in a modular group ring - Sandling. KNOT THEORY (*) Distinguishing eleven crossing knots - Havas and Kovacs. MATHEMATICAL CRYSTALLOGRAPHY (*) Finite quotient groups of the plane crystallographic groups - Felix. (*) Subgroup structure of 3-dimensional crystal groups - Moody. NUMBER THEORY (*) Computing Galois groups over the rationals - Soicher and McKay. (*) Maximal finite irreducible subgroups of GL(n, Z), n ge 5 - Plesken. (*) Constructing lattices with prescribed minimum - Plesken and Pohst. NUMERICAL ANALYSIS (*) Construction of symmetry adapted bases for the solution of 3-dimensional partial differential equations - Ungricht. PERMUTATION GROUPS (*) 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. (*) Irreducible 3-modules for PSL( 3, 4) - Schneider. (*) Character degrees of p-groups - Slattery. RING THEORY (*) Verbal embeddings of rings in groups - Fournelle and Weston. TOPOLOGY (*) A computer search for homology 3-spheres - Dunwoody. (*) Classification of hyperbolic manifolds from regular polyhedra - Richardson and Rubinstein. (10) Implementations As of January 1988, Cayley has been implemented on the following processors: (*) SUN 3 (*) VAX/VMS (*) VAX/UNIX bsd 4.3 (*) VAX/ULTRIX (*) IBM 30xx, 43xx under VM/CMS (*) IBM RT (*) Masscomp (*) HP9000 series under UNIX (*) AT&T 3B15 (*) Pyramid (*) Cray 2 (planned for summer 1988) (11) Further Information Further information may be obtained by writing to The Secretary Computational Algebra Group Department of Pure Mathematics University of Sydney NSW 2006 Australia REFERENCES J.J. Cannon. The basis of a computer system for modern algebra. SYMSAC'81. Proceedings of the 1981 ACM Symposium on Symbolic and Algebraic Computation, Snowbird, Utah, August, 1981. Assoc. Comp. Mach., New York, 1981, pp.1-5. J.J. Cannon. An introduction to the group theory language Cayley. In Comput- ational Group Theory, edited by M.D. Atkinson, Academic Press, London, 1984, pp.145-183. J.J. Cannon. A Language for Group Theory. Department of Pure Mathematics, University of Sydney, 1982, 1984, 1987. 300 pages. J.J. Cannon. The group theory system Cayley. To appear in the Journal of Symbolic Computation. G. Butler and J.J. Cannon. The design of Cayley - A language for modern algebra. December, 1987. G. Butler and J.J. Cannon. Cayley V4 - The user language. Proceedings of the 1988 International Symposium on Symbolic and Algebraic Computation. Rome, July, 1988. G. Butler and S. Sridhar. Towards a deductive database for the simple groups G, |G| < 10^6. Proceedings of the 1988 International Symposium on Symbolic and Algebraic Computation, Rome, July, 1988. M.F. Newman and E.A. O'Brien. A Cayley library for the groups of order divid- ing 128. Proceedings of the Singapore Group Theory Conference, June, 1987.