In this chapter we will give a brief description of the mathematical
notions used in the algorithms implemented in the ANU pq
program
that are made accessible from GAP through this package. For proofs
and details we will point to relevant places in the published
literature. Also we will try to give some explanation of terminology
that may help to use the ``lowlevel'' interactive functions described
in Section Lowlevel Interactive ANUPQ Functions based on menu items of the pq program. However, users who intend to use these functions
are strongly advised to acquire a thorough understanding of the
algorithms from the quoted literature. There is little or no checking
done in these functions and naive use may result in incorrect results.
pc Presentations and Consistency
For details, see e.g. NNN98.
Every finite pgroup G has a presentation of the form:

This is called a powercommutator presentation (or pc presentation or pcp) of G, generators from such a presentation will be referred to as pc generators. In terms of such pc generators every element of G can be written in a ``normal form'' a_{1}^{e1}... a_{n}^{en} with 0 £ e_{i} < p. Moreover any given product of the generators can be brought into such a normal form using the defining relations in the above presentation as rewrite rules. Any such process is called collection. For the discussion of various collection methods see LGS90 and VL90a.
Every pgroup of order p^{n} has such a pcp on n generators and conversely every such presentation defines a pgroup. However a pgroup defined by a pcp on n generators can be of smaller order p^{m} with m < n. A pcp on n generators that does in fact define a pgroup of order p^{n} is called consistent in this manual, in line with most of the literature on the algorithms occurring here. A consistent pcp determines a confluent rewriting system (see IsConfluent of the GAP Reference Manual) for the group it defines and for this reason often (in particular in the GAP Reference Manual) such a pcp presentation is also called confluent.
Consistency of a pcp is tantamount to the fact that for any given word in the generators any two collections will yield the same normal form.
Consistency of a pcp can be checked by a finite set of consistency
conditions, demanding that collection of the left hand side and of
the right hand side of certain equations, starting with subproducts
indicated by bracketing, will result in the same normal form. There
are 3 types of such equations (that will be referred to in the
manual):

Exponentp Central Series and Weighted pc Presentations
For details, see NNN98.
The (descending or lower) (exponent)pcentral series of an
arbitrary group G is defined by

pq
 and related algorithms, the pclass is
often referred to simply by class.
Let the pgroup G have a consistent pcp as above. Then the
subgroups

The pair of such a weight function and a pcp allowing it, is called a weighted pcp.
pCover, pMultiplicator
For details, see NNN98.
Let d be the minimal number of generators of the pgroup G of pclass c. Then G is isomorphic to a factor group F/R of a free group F of rank d. We denote [F, R] R^{p} by R^{*}. It can be proved (see e.g. OBr90) that the isomorphism type of G^{*} : = F/R^{*} depends only on G. G^{*} is called the pcovering group or pcover of G, and R/R^{*} the pmultiplicator of G. The pmultiplicator is, of course, an elementary abelian pgroup; its minimal number of generators is called the (p)multiplicator rank.
Descendants, Capable, Terminal, Nucleus
For details, see New77 and OBr90.
Let again G be a pgroup of pclass c and d the minimal number of generators of G. A pgroup H is a descendant of G if the minimal number of generators of H is d and H/P_{c}(H) is isomorphic to G. A descendant H of G is an immediate descendant if it has pclass c+1. G is called capable if it has immediate descendants; otherwise it is terminal.
Let G^{*} = F/R^{*} again be the pcover of G. Then the group P_{c}(G^{*}) is called the nucleus of G. Note that P_{c}(G^{*}) is contained in the pmultiplicator R/R^{*}.
It is proved (e.g. in OBr90) that the immediate descendants of G are obtained as factor groups of the pcover by (proper) supplements of the nucleus in the (elementary abelian) pmultiplicator. These are also called allowable.
It is further proved there that every automorphism a of F/R extends to an automorphism a^{*} of the pcover F/R^{*} and that the restriction of a^{*} to the multiplicator R/R^{*} is uniquely determined by a. Each extended automorphism a^{*} induces a permutation of the allowable subgroups. Thus the extended automorphisms determine a group P of permutations on the set A of allowable subgroups (The group P of permutations will appear in the description of some interactive functions). Choosing a representative S from each orbit of P on A, the set of factor groups F/S contains each (isomorphism type of) immediate descendant of G exactly once. For each immediate descendant, the procedure of computing the pcover, extending the automorphisms and computing the orbits on allowable subgroups can be repeated. Iteration of this procedure can in principle be used to determine all descendants of a pgroup.
Laws
Let l(x_{1}, ..., x_{n}) be a word in the free generators x_{1}, ..., x_{n} of a free group of rank n. Then l(x_{1}, ..., x_{n}) = 1 is called a law or identical relation in a group G if l(g_{1}, ..., g_{n}) = 1 for any choice of elements g_{1}, ..., g_{n} in G. In particular, x^{e} = 1 is called an exponent law, [[x,y],[u,v]] = 1 the metabelian law, and [... [[x_{1},x_{2}],x_{2}],..., x_{2}] = 1 an Engel identity.
For details, see HN80, NO96 and VL84. Other descriptions of the algorithm are given in Sims94.
The pq
algorithm successively determines the factor groups of the
groups of the pcentral series of a finitely presented (fp) group
G. If a bound b for the pclass is given, the algorithm will
determine those factor groups up to at most pclass b. If the
pcentral series terminates with a subgroup P_{k}(G) with k < b,
the algorithm will stop with that group. If no such bound is given, it
will try to find the biggest such factor group.
G/P_{1}(G) is the largest elementary abelian pfactor group of G and this can be found from the relation matrix of G using matrix diagonalisation modulo p. So it suffices to explain how G/P_{i+1}(G) is found from G and G/P_{i}(G) for some i ³ 1.
This is done, in principle, in two steps: first the pcover of G_{i} : = G/P_{i}(G) is determined (which depends only on G_{i}, not on G) and then G/P_{i+1}(G) as a factor group of this pcover.
Finding the pcover
A very detailed description of the first step is given in NNN98, from which we just extract some passages in order to point to some terms occurring in this manual.
Let H be a pgroup and p^{d(b)} be the order of H/P_{b}(H). So d : = d(1) is the minimal number of generators of H. A weighted pcp of H will be called labelled if for each generator a_{k}, k > d one relation, having this generator as its right hand side, is marked as definition of this generator.
As described in NNN98, a weighted labelled pcp of a pgroup can be obtained stepping down its pcentral series.
So let us assume that a weighted labelled pcp of G_{i} is given. A straightforward way of of writing down a (not necessarily consistent) pcp for its pcover is to add generators, one for each relation which is not a definition, and modify the right hand side of each such relation by multiplying it on the right by one of the new generators  a different generator for each such relation. Further relations are then added to make the new generators central and of order p. This procedure is called adding tails. A more formal description of it is again given in NNN98.
It is important to realise that the ``new'' generators will generate an elementary abelian group, that is, in additive notation, a vector space over the field of p elements. As said, the pcp of the pcover obtained in this way need not be consistent. Since the pcp of G_{i} was consistent, applying the consistency conditions to the pcp of the pcover, in case the presentation obtained for pcover is not consistent, will produce a set of equations between the new generators, that, written additively, are linear equations over the field of p elements and can hence be used to remove redundant generators until a consistent pcp is obtained.
In reality, to follow this straightforward procedure would be forbiddingly inefficient except for very small examples. There are many ways of a priori reducing the number of ``new generators'' to be introduced, using e.g. the weights attached to the generators, and the main part of NNN98 is devoted to a detailed discussion with proofs of these possibilities.
Imposing the Relations of the fp Group
In order to obtain G/P_{i+1}(G) from the pcp of the pcover of G_{i} = G/P_{i}(G), the defining relations from the original presentation of G must be imposed. Since G_{i} is a homomorphic image of G, these relations again yield relations between the ``new generators'' in the presentation of the pcover of G_{i}.
Imposing Laws
While we have so far only considered the computation of the factor groups of a given fp group by the groups of its descending pcentral series, the pquotient algorithm allows a very important variant of this idea: laws can be prescribed that should be fulfilled by the pfactor groups computed by the algorithm. The key observation here is the fact that at each step down the descending pcentral series it suffices to impose these laws only for a finite number of words. Again for efficiency of the method it is crucial to keep the number of such words small, and much of NO96 and the literature quoted in this paper is devoted to this problem.
In this form, starting with a free group and imposing an exponent law
(also referred to as an exponent check) the pq
program has, in
fact, found its most noted application in the determination of
(restricted) Burnside groups (as reported in e.g. HN80,
NO96 and VL90b).
Via a GAP program using the ``local'' interactive functions of the
pq
program made available through this interface also arbitrary laws
can be imposed via the option Identities
(see option Identities).
For details, see New77 and OBr90.
The pgroup generation algorithm determines the immediate descendants of a given pgroup G up to isomorphism. From what has been explained in Section Basic Notions, it is clear that this amounts to the construction of the pcover, the extension of the automorphisms of G to the pcover and the determination of representatives of the orbits of the action of these automorphisms on the set of supplements of the nucleus in the pmultiplicator.
The main practical problem here is the determination of these
representatives. OBr90 describes methods for this and the pq
program allows choices according to whether space or time limitations
must be met.
Along with the descendants of G, the pq
program also determines
their automorphism groups from that of G (see OBr95), which
is important for an iteration of the process; this has been used by
Eamonn O'Brien, e.g. in the classification of the 2groups that are
now also part of the Small Groups library available through GAP.
A variant of the pgroup generation algorithm is also used to define a standard presentation of a given pgroup. This is done by constructing an isomorphic copy of the given group through a chain of descendants and at each step making a choice of a particular representative for the respective orbit of capable groups. In a fairly delicate process, subgroups of the pmultiplicator are represented by echelonised matrices and a first among the labels for standard matrices is chosen (this is described in detail in OBr94).
Finally, the standard presentation provides a way of testing if two given pgroups are isomorphic: the standard presentations of the groups are computed, for practical purposes compacted and the results compared for being identical, i.e. the groups are isomorphic if and only if their standard presentations are identical.
[Up] [Previous] [Next] [Index]
ANUPQ manual