3 Groups

3.1.1 Construction

• Permutation representations for classical groups, e.g. PGL(n,q), PSp(n,q), PSU(n,q²), P Ω(n,q)

• Construction of standard groups, e.g., S_n, A_n.

• Construction of wreath products with both types of action

• Random generation of elements (Product-replacement algorithm),

3.1.2 Base and Strong Generating Set

• Sims-Schreier algorithm for constructing a base and strong generating set (BSGS)

• Random Schreier algorithm for constructing a BSGS (Monte Carlo algorithm)

• Todd-Coxeter Schreier algorithm for constructing a BSGS

• Sims variation of Schreier method for soluble groups

• Fast construction of BSGS when group order is known

• Brownie-Cannon-Sims algorithm for verifying a BSGS

The key concept for representing a permutation group is that of a base and strong generating set (BSGS). Given a BSGS for a group, its order may be deduced immediately. Brownie, Cannon and Sims (1991) showed that it is practical, in some cases at least, to construct a BSGS for short-base groups having degree up to ten million. For example, starting with six permutations of degree 8 835 156, generating the Lyons simple group, it takes Magma 5.0 hours to provably determine the order of the group they generate.

The ability to construct a BSGS, coupled with the use of algorithms that make heavy use of the classification theorem for finite simple groups, allow the determination of a great deal of structural information, such as composition factors, for short base groups of degree up to at least ten million.

3.1.3 Elementary Properties

The functions listed in this section require a BSGS to be computed.

• Order

• Exponent

• Whether abelian, nilpotent, soluble, etc.

• Whether perfect, simple, etc.

3.1.4 Conjugacy Classes

The conjugacy classes of elements of a group G are found using a lifting algorithm which first finds the classes of the trivial Fitting quotient of G (algorithm of D. Holt) and then lifts these classes through the layers of an elementary abelian series for G. For example, all classes in the group 2¹².(SL₂(4) ≀ S₃) of degree 4096 and order 5,308,416,000 are computed in 4 seconds.

• Testing a pair of elements for conjugacy

• Conjugacy classes of elements (lifting algorithm)

• Power map

• Class map, i.e. return the number of the class to which a given element belongs

• Class matrix

3.1.5 Subgroup Constructions

• Construction of subgroups, quotient groups

• Normal closure, core of a subgroup

• Normalizer, centralizer

• Testing subgroups for conjugacy

• Intersection of subgroups

• Sylow p-subgroup (reduction algorithm)

3.1.6 Actions

• Stabilizer of a point, set of points, sequence of points

• Stabilizer of an ordered partition, conjugacy of partitions

• Orbits on points, sets of points, and sequences of points

• Homomorphisms induced by actions on orbits

• Systems of imprimitivity (Schönert-Seress algorithm)

• Homomorphisms induced by actions systems of imprimitivity

• Induced actions on G-sets

• Action properties: Semiregular, regular, transitive, primitive, Frobenius

• Permutation representation on the cosets of a subgroup

• Fast tests for the alternating/symmetric group

3.1.7 Analysis of a Primitive Group

• Elementary abelian regular normal subgroup (EARNS)

• Action of an affine primitive group on its EARNS

• Construction of the socle of a non-affine group via the O'Nan-Scott theorem

• Action of a primitive group on its socle

• Permutation representation of G/N, where G is a primitive group and N is its socle

• O'Nan-Scott decomposition of a primitive group

• Identification of a 2-transitive group

The Magma group has developed efficient methods for obtaining the O'Nan-Scott decomposition of a primitive group. The elementary abelian regular normal subgroup of an affine primitive group is constructed by a polynomial-time algorithm based on ideas published by P. Neumann (1986). For example, Magma finds the EARNS of AGL(10,3) which has degree 59,049 and order 17046196453240220939126401085378073952125928970649600 in 1.49 seconds. The construction of the socle and the analysis of a non-affine primitive group is performed by algorithms based on ideas of Cannon, Holt and Kantor. A 2-transitive group is identified as an abstract group using an algorithm published by Cameron and Cannon.

3.1.8 Normal Structure

• Derived subgroup, derived series, soluble residual

• Lower central series, nilpotent residual

• p-core, Fitting subgroup, soluble radical (Unger's polynomial-time algorithm)

• Centre, upper central series

• Elementary abelian series, p-central series

• Socle, socle action

• Chief series, chief factors, composition factors

• Agemo, omega subgroups (of a p-group)

• Minimal normal subgroups

• Maximal normal subgroups

• All normal subgroups

3.1.9 Standard Quotients

• Maximal abelian quotient

• Maximal soluble quotient

• Socle quotient (for primitive and trivial Fitting groups)

• Conjugation action on socle factors (trivial Fitting groups)

• Quotient by an abelian normal subgroup

• Radical quotient

• Presentation on given generators (for groups of moderate order)

• Presentation on strong generators

• Presentation of quotient by a normal subgroup

A variety of methods are used for quotient constructions. Quotients by abelian groups use the algorithm of Luks &Seress (1997). Finitely presented quotients use a combination of the Schreier-Todd-Coxeter-Sims method of Leon (1980) and the presentation implicit in Sims' verification of a BSGS (see Gebhardt (2000)).

3.1.10 Subgroup Structure

• Maximal subgroups

• Frattini subgroup

• Conjugacy classes of complements of a soluble normal subgroup

• Conjugacy classes of subgroups, poset of subgroup classes

• Conjugacy classes of subgroups satisfying a condition: cyclic, elementary abelian, abelian, nilpotent

• Low index subgroups

Magma V2.14 and later contains an implementation of a very powerful algorithm for computing the maximal subgroups of a group G of moderate degree. The algorithm first determines the maximal subgroups of the trivial Fitting quotient of G and then lifts these maximal subgroups down an elementary abelian series. Magma finds the maximal subgroups of the group of Rubik's cube (degree 48, order 43252003274489856000) in 0.42 seconds.

3.1.11 Automorphisms

• Automorphism group

• Test for two permutation groups being isomorphic

The automorphism group of a permutation group G is found using a lifting algorithm which first finds the automorphisms of the trivial Fitting quotient of G by looking up the automorphism groups of any non-cyclic factors in a database. Then these automorphisms are lifted through the layers of an elementary abelian series for G. For example, the automorphism group of the group of Meffert's puzzle (a non-soluble permutation group of degree 30 and order 2⁸ 3¹⁰5) is found in 0.14 seconds. The group has 16 outer automorphisms.

3.1.12 Cohomology and Representations

• Character table

• Irreducible representations (for groups of moderate order)

• KG-module corresponding to an elementary abelian section

• p-part of Schur multiplicator, p-cover

• Dimensions of first and second cohomology groups

• Split and non-split extensions of a group by a module (D. Holt's package)

• Schur indices, rewriting representations over minimal fields

3.1.13 Databases

• Transitive groups up to degree 30 (Butler, Hulpke)

• Primitive groups up to degree 2499 (Sims, Roney-Dougal &Unger, Roney-Dougal)

• Irreducible soluble subgroups of GL(n,p) for pⁿ < 256 (Short)

• Almost simple groups of order less than 1.6×10⁸, plus M₂₄, HS, L₆(2), J₃, McL, Sz(32) stored with their automorphism groups and maximal subgroups

• A collection of permutation representations of some sporadic simple groups

• Representations of ATLAS groups from the Birmingham ATLAS of finite group representations (R. Wilson).

In V2.17 the database of almost simple groups is augmented by the ability to compute automorphism groups and maximal subgroups for alternating groups up to degree 999, families of low degree classical groups (Holt &Roney-Dougal): L_n(q) for 2 ≤ n ≤ 7 and all q, L_n(2) for n ≤ 14, S₄(q), U₃(q) and U₄(q) for all q, and the following groups: U₆(2), S₈(2), S₁₀(2), O^±₈(2), O^±₁₀(2), S₆(3), O₇(3), O^-₈(3), G₂(4), G₂(5), ³D₄(2), ²F₄(2)', Co₂, Co₃, He, Fi₂₂, Suzi, Ru.

3.2.1 Construction

A matrix group is always constructed as a subgroup of the appropriate general linear group, GL(n,R).

• Generators for linear groups: GL(n,R), SL(n,R) where R is a finite field, R = ℤ, or R = ℤ/nℤ.

• Generators for symplectic groups: CSp(n,q), Sp(n,q)

• Generators for unitary groups: CU(n,q), GU(n,q), U(n,q)

• Generators for orthogonal groups: GO(2n + 1,q), SO(2n + 1,q), Ω(2n + 1,q), GO⁺(2n,q), SO⁺(2n,q), Ω⁺(2n,q), GO^-(2n,q), SO^-(2n,q), Ω^-(2n,q)

• Generators for all exceptional families of groups of Lie type

• Direct product, tensor wreath product, tensor power, exterior square

• Construction of semi-linear groups

• Group obtained by applying a homomorphism φ: R→S to the matrix coefficients.

• Group obtained by restricting the matrix coefficients to a subring of R.

3.2.2 Arithmetic with Elements

• Random generation of elements (Product-replacement algorithm)

• Invariants of a matrix: Trace, determinant, minimal and characteristic polynomials, Jordan form, rational canonical form

• Order of a matrix (Leedham-Green algorithm for finite fields)

• Test whether a matrix over a number field has infinite order

3.2.3 Actions

• Tests for irreducibility, absolute irreducibility, semi-linearity

• Test whether a group over a field of characteristic zero has infinite order

• Orbit, stabilizer of a vector or subspace

• Orbit representatives and orbit lengths for the action of a matrix group (defined over a prime field) on the k-dimensional subspaces of the natural vector space

• Estimate the size of the orbit of a given subspace

• Approximation to the stabilizer of a given subspace

• Enumerate number of k-dimensional subspaces fixed under the action of an element of GL(d,q)

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

• Homomorphism induced by action on an orbit of vectors or subspaces

3.2.4 Base and Strong Generating Set

For matrix groups of small degree, we use an analogue of the methods used for permutation groups. We try to find some sequences of objects (subspaces and vectors) in the underlying vector space that defines a stabilizer chain which has the property that the basic orbits are not excessively large. Thus, we have a concept of a base and strong generating set (BSGS) similar to that employed in the case of permutation groups. Once such a BSGS is available, analogues of the permutation group backtrack searches for centralizer, normalizer, etc. may be described.

• Random Schreier algorithm for constructing a BSGS

• Todd-Coxeter Schreier algorithm for constructing a BSGS

• Murray-O'Brien base selection strategy

3.2.5 Elementary Properties

With the exception of the first, all of the functions listed in this section require the group to be finite and a BSGS to be computed.

• Whether finite or infinite (only for groups defined over Z or a number field)

• Order

• Exponent

• Whether abelian, nilpotent, soluble, etc.

• Whether perfect, simple, etc.

3.2.6 Conjugacy Classes

• Testing a pair of elements for conjugacy and finding a conjugating element

• Conjugacy classes of elements (lifting algorithm, classic algorithm)

• Power map

• Class map, i.e. return the number of the class to which a given element belongs

• Class matrix

3.2.7 Subgroup Constructions

• Construction of a subgroup in terms of generators

• Normal closure, core of a subgroup

• Centralizer

• Intersection of subgroups

• Sylow p-subgroup (reduction algorithm)

• Homomorphism induced by action on the cosets of a subgroup

• Computing subgroup normalizers

3.2.8 Normal Structure

• Derived subgroup

• Soluble residual

• Centre, Fitting subgroup

• Derived series, upper central series, lower central series

• Soluble radical, elementary abelian series, p-central series

• Composition series, composition factors, chief series

• Agemo, omega subgroups (of a p-group)

• Jennings series (of a p-group)

3.2.9 Standard Quotients

• Maximal abelian quotient, elementary abelian quotient

• Maximal p-quotient, nilpotent quotient

• Maximal soluble quotient

• Presentation on strong generators

• Quotient by soluble radical

3.2.10 Automorphisms

Holt's algorithm for computing automorphism groups and testing isomorphism may be applied to matrix groups with BSGS.

3.2.11 Cohomology and Representations

The Magma machinery for matrix groups together with fast Gröbner basis techniques (see below) provide a very efficient algorithm for computing a Cohen-Macaulay basis for the ring of invariants together with its syzygies.

• Character table

• KG-module corresponding to an elementary abelian section

• Molien series

• Ring of invariants

3.2.12 Aschbacher Analysis

The basic facilities provided by Magma for computing with matrix groups over finite fields depend upon being able to construct a chain of stabilizers. However, there are many examples of groups of moderately small degree where we cannot find a suitable chain. An on-going international research project seeks to develop algorithms to explore the structure of such groups. The main theoretical underpinning of the project comes from the classification by Aschbacher (1984) of the (maximal) subgroups of GL(d,q) into nine families. Much of the research effort to date has been devoted to designing algorithms to decide whether G belongs to one of the eight families whose members have a normal subgroup preserving a "natural linear structure" (the geometric maximal subgroups); here, we plan to exploit this information to explore G further, ultimately producing a composition series for G.

• Determine whether a group preserves a form modulo scalars.

• The Niemeyer-Prager classical group recognition algorithm as implemented in Magma by Alice Niemeyer and Anthony Pye.

• Determine whether a subgroup G of GL(d,q) acts imprimitively on the underlying vector space. a block system, respectively.

• Test whether a matrix group G acts as a semilinear group of automorphisms on some vector space.

• Test whether a matrix group G preserves a non-trivial tensor product decomposition.

• Test whether a matrix group G is tensor-induced.

• Search for decompositions (corresponding to certain Aschbacher families) with respect to the normal closure of a supplied subgroup.

• The Glasby-Howlett algorithm to decide if the absolutely irreducible group G ≤ GL(d,K) has an equivalent representation over a subfield of K.

• Given a group G of d×d matrices over a finite field E having degree e and a subfield F of E having degree f, write G as a group generated by the matrices of G written as de/f×de/f matrices over F.

• Roney-Dougal's algorithm for determining conjugacy of subgroups of GL(d,q)

In addition, V2.17 of Magma has rotuines to compute all maximal subgroups of Magma's standard copies of the classical groups of dimension < 12 over finite fields. In dimension ≥ 12 this is restricted to computing the geometric maximal subgroups.

3.2.13 Databases of Matrix Groups

• Maximal finite subgroups of GL(n,ℚ) for n up to 31

• The finite absolutely irreducible subgroups of GL_n(D) where D is a definite quaternion algebra whose centre has degree d over ℚ and nd ≤ 10

• Irreducible subgroups of GL(n,p) where p is prime and pⁿ < 2500.

• Representations of ATLAS groups from the Birmingham ATLAS of finite group representations (R. Wilson).

3.4.1 Free Groups

• Construction

• Reduction of a word to normal form

• Product, exponentiation, inverse, equality

3.4.2 Construction

• Construction as a quotient of a free group

• Standard groups: S_n, A_n, dihedral groups, Coxeter groups, braid groups

• Permutation groups, matrix groups, polycyclic groups as fp-groups

• Direct product, free product

• Maximal central extension

3.4.3 Arithmetic on Elements

• Arithmetic (free reduction only on words)

• Substring operations on words

• Definition of and calculation with homomorphisms

3.4.4 Basic Properties

Determining global properties of an fp-group is known to be intrinsically difficult. If it is suspected that a given fp-group is finite, a function is provided that will attempt to determine the order of the group. While this function basically employs coset enumeration, it does so in a fairly sophisticated manner so that it is able to handle groups that are much too large for a coset enumeration of the trivial subgroup to succeed.

3.4.5 Quotients

• Abelian quotient, elementary abelian quotient

• p-quotient

• Process version of p-quotient allowing the user complete control over its execution

• Nilpotent quotient (W. Nickel's algorithm)

• Soluble quotient (Plesken-Brückner algorithm)

• Process version of the soluble quotient allowing the user complete control over its execution

• Natural homomorphism onto any of the above standard quotients

• Equivalence classes of homomorphisms to an arbitrary permutation group with application to perfect quotients

• Process version of search for equivalence classes of homomorphisms allowing the user complete control over its execution

• Kernel of the natural homomorphism onto any standard quotient (provided that the quotient is not too large)

The p-quotient program has been developed over a number of years by George Havas, Mike Newman and Eamonn O'Brien. It has been used to construct p-quotients of composition length several thousand for small primes p. Soluble quotients are computed using Herbert Brückner's implementation of the Plesken algorithm and is capable of constructing soluble quotients having order in excess of a million. Unlike previous algorithms, no information is required other than the fp-group.

The computation of equivalence classes of homomorphisms to a permutation group uses a well known backtrack algorithm. Volker Gebhardt's implementation of this algorithm is capable of determining all classes of homomorphisms from a 2- or 3-generator group to a permutation group of order up to 10⁸ in reasonable time.

3.4.6 Constructing a Subgroup

• Construction of a subgroup in terms of generators

• Construction of a subgroup in terms of a coset table

• Coset enumeration (Todd-Coxeter procedure)

• Process version of coset enumeration allowing the user complete control over its execution

• Schreier generators for a subgroup

• Presentation for a subgroup (Reidemeister-Schreier rewriting)

Coset enumeration is performed using George Havas's ACE version of the Todd-Coxeter procedure. It has the capability of enumerating up to one hundred million cosets on a sufficiently large machine.

3.4.7 Operations on Subgroups of Finite Index

The fp-group package also includes a collection of functions for computing with subgroups of (small) finite index represented by coset tables. Hence the operations in this group assume that the subgroup has finite index and that it is possible to enumerate its cosets.

• Normal closure

• Membership and equality of subgroups

• Core, intersection and normalizer

• All maximal (minimal) overgroups of a subgroup

• Test for conjugacy, maximality, normality

• Schreier system and Schreier coset map

Magma uses Havas' rewriting Todd-Coxeter to write elements of a subgroup as words in the subgroup generators.

3.4.8 Enumeration of Subgroups

Subgroups of small index may be enumerated using the so-called low index subgroups algorithm. The low index algorithm used in Magma is the backtrack method described by Sims in his book Computation in Finitely Presented Groups, CUP, 1993.

• Enumeration of low index subgroups (Sims backtrack algorithm)

• Process version of low index subgroups to return subgroups one at a time

• Enumeration of low index normal subgroups (Holt's homomorphism algorithm)

3.4.9 Simplifying a Presentation

• Automatic simplification of a presentation

• Interactive simplification of a presentation via a Tietze process

• Tietze process: Eliminate specified generators

• Tietze process: Control of substring searching

• Bijection between original and simplified presentations

3.4.10 Actions

• Actions on coset spaces (Todd-Coxeter procedure)

• Actions on vector spaces (Linton vector enumeration)

• Permutation representation on the cosets of a subgroup

3.4.11 Representation Theory

It is frequently useful to construct the G-modules corresponding to the conjugation action of a finitely presented group G on an elementary abelian section. This can be useful when attempting to construct normal subgroups of G.

• Determine the finite primes dividing the order of the abelian quotient of a subgroup A of a fp-group G

• Given subgroups A and B defining an abelian section of G, construct the G-module corresponding to the conjugation action of G on the maximal p-elementary abelian quotient of A/B

• Given a map f from a normal subgroup A of G onto the G-module M corresponding to the conjugation action of G on the maximal p-elementary abelian quotient of an abelian section A/B of G and a submodule N of M, compute the preimage of N under f using a fast pullback method.

3.4.12 Databases of Finitely Presented Groups

• Fundamental groups of small-volume closed hyperbolic 3-manifolds (Dunfield &Thurston, based on Hodgson &Weeks' census of manifolds).

3.7.1 Polycyclic Groups: Construction and Arithmetic

• Construction as a quotient of a free group

• Standard groups as polycyclic groups

• Permutation groups, matrix groups, abelian groups and finite soluble groups as polycyclic groups

• Nilpotent quotient of a finitely presented group (W. Nickel's algorithm)

• Direct products

• Wreath products

• Product, inverse, conjugate, commutator for elements; improved collector, much faster, better complexity

• Element normal form and equality testing

• Element order

• Random element generation

3.7.2 Polycyclic Groups: Basic Invariants

• Test finiteness, group order

• Test for abelian, elementary abelian, cyclic, nilpotent

• Nilpotency class

• Hirsch number

3.7.3 Polycyclic Groups: Subgroup Constructions

• Subgroup and quotient group construction

• Normal closure of a subgroup

• Conjugation of subgroups

• Commutator subgroups

• Test subgroup membership and inclusion

• Test for normal and central subgroups

• Centraliser of elements (in a nilpotent group)

• Normaliser and centraliser of subgroups (nilpotent group)

• Test for conjugacy of elements and subgroups (nilpotent group)

• Intersection of subgroups (nilpotent group)

3.7.4 Polycyclic Groups: Normal Structure

• Normal series with free- or elementary-abelian factors

• Centre, upper central series

• Lower central series, derived subgroup and series

• Fitting subgroup, Fitting series

• G-module construction from action on free- or elementary abelian sections

• Abelian quotient structure

3.8.1 Construction

• Construction of polycyclic presentation for the maximal finite p-quotient of an fp-group (O'Brien's program)

• Construction of polycyclic presentation for the maximal finite soluble quotient of an fp-group (Plesken-Brückner algorithm)

• Construction of a polycyclic presentation for a soluble group given as a permutation group or a matrix group

• Split and non-split extensions, wreath products

• Representation of a soluble group in terms of a SAG-presentation

• The soluble groups contained in the Small Groups Library developed by Besche, Eick and O'Brien. This database contains all groups of order up to 2000, except the groups of order 1024, and a number of infinite series of larger groups.

In 1991, Leedham-Green with Brownie and Cannon developed an echelonization algorithm capable of constructing a form of polycyclic presentation for a finite soluble group which exhibits much of the structure. This polycyclic presentation (known as a SAG-presentation) is given in terms of generators defining a chain of subgroups which refines a nilpotent series for the group. Each nilpotent section exhibits a lower p-central series for each prime p involved. Finally, the quotient of the group by a term of the nilpotent series splits over the layer below.

3.8.2 Conjugacy Classes

• Testing a pair of elements for conjugacy

• Conjugacy classes of elements

• Power map

• Class map, i.e. return the number of the class to which a given element belongs

• Class matrix

• Exponent

3.8.3 Subgroup Constructions

• Construction of subgroups, quotient groups

• Normal closure, core of a subgroup

• Normalizer, centralizer

• Testing subgroups for conjugacy

• Intersection of subgroups

• Permutation representation on the cosets of a subgroup

• System of double coset representatives for a pair of subgroups (Slattery algorithm)

• Sylow p-subgroup

• Hall π-subgroups, Sylow basis, complement basis

• System normalizer, relative system normalizer

Simple variations of the SAG-algorithm may be used to compute normal closures, the lower central series and the derived series. Sylow p-subgroups, Hall π-subgroups, a Sylow basis, and a complement basis may be read directly from the presentation. The availability of such a presentation together with sophisticated module theory machinery allowed us to design fast algorithms for finding the centre and maximal subgroups.

3.8.4 Normal Structure

• Centre, hypercentre, derived subgroup

• Derived series, upper central series, lower central series

• Chief series, composition series

• Elementary abelian series, p-central series

• Fitting subgroup

• Frattini subgroup

• Normal subgroups

3.8.5 Subgroup Structure

• Maximal subgroups

• Conjugacy classes of complements of a normal subgroup

• Conjugacy classes of subgroups, poset of subgroup classes

• Conjugacy classes of subgroups satisfying a condition: Cyclic, elementary abelian, abelian, nilpotent

The availability of an SAG-presentation combined with sophisticated module theory machinery allowed us to design fast a algorithm for finding the maximal subgroups of a soluble group.

3.8.6 Automorphisms and Representations

• Automorphism group of a soluble group (M Smith's algorithm)

• Character table (Dixon-Schneider algorithm)

• Character degrees (Conlon's Algorithm)

• Modular irreducible representations (Glasby-Howlett algorithm)

• Ordinary irreducible representations (Brückner algorithm)

• KG-module corresponding to an elementary abelian section

3.9.1 Construction

• As for finite soluble groups

• Construction of polycyclic presentation for the maximal finite p-quotient of an fp-group (O'Brien algorithm)

• p-group generation (Eamonn O'Brien algorithm)

3.9.2 Normal Structure

• As for finite soluble groups

• Agemo, omega subgroups

• Jennings series of a p-group

3.9.3 Isomorphisms and Automorphism Groups

• Construct a standard presentation for a p-group

• Test two p-groups for isomorphism

• Automorphism group of a p-group (E O'Brien's algorithm)

3.9.4 Character Theory

• Degrees of irreducible characters (Slattery's algorithm)

• Character Table (Conlon's algorithm)

3.13.1 Constructing and Accessing Braid Groups

• Definition of a braid group on n strings.

• Controlling default presentation, print format for elements and element representation used for group operations.

3.13.2 Constructing and Accessing Elements

• Identity element and fundamental element.

• Artin generators and band generators.

• Generation of pseudo random elements.

• Representations of an element as words and as products of simple elements for Artin presentation and band generator presentation.

• Infimum, supremum and canonical length of an element with respect to either presentation.

3.13.3 Normal Forms of Elements

• Left and right normal form with respect to either presentation.

• Left and right mixed canonical form with respect to either presentation.

3.13.4 Arithmetic Operations with Elements

• Product, left and right quotient, left and right conjugate of two elements.

• Inverse of an element.

• Cycling and decycling operation for an element with respect to either presentation.

3.13.5 Boolean Predicates

• Functions determining whether an element is the identity, simple, or a representative of its super summit class (with respect to either presentation), respectively.

• Tests for equality and conjugacy of elements.

• Partial orderings of elements with respect to either presentation.

3.13.6 Lattice Operations

• GCD and LCM with respect to either presentation and either partial ordering.

3.13.7 Conjugates

• Infimum, supremum and canonical length of the super summit class of an element with respect to either presentation.

• Computing a representative of the super summit set of an element with respect to either presentation.

• Computing the set of positive conjugates of an element with respect to either presentation.

• Computing the super summit set of an element with respect to either presentation.

• Process versions of the above algorithms for computing positive conjugates and super summit elements.

3.13.8 Homomorphisms

• Natural symmetric representation.

• Integral and modular Burau representations.

• Construction and evaluation of a homomorphism whose domain or codomain is a braid group.