Permutation group algorithms.

*(English)*Zbl 1028.20002
Cambridge Tracts in Mathematics. 152. Cambridge: Cambridge University Press. ix, 264 p. (2003).

This monograph gives a thorough overview of the current knowledge on computing with permutation groups.

Previous books have been of notably smaller scope. Apart from the fact that they represented the state of the art in a rapidly evolving sub-discipline of 15 years ago or more, they considered the subject either from a purely theoretical view such as C. M. Hoffmann [Group-theoretic algorithms and graph isomorphism. Springer (1982; Zbl 0487.68055)] or practical view such as G. Butler [Fundamental algorithms for permutation groups. Springer (1991; Zbl 0785.20001)].

The algorithms in this book in contrast combine theoretical and practical aspects to mutual benefit, a development which has been substantially promoted by the author’s work.

Much of the material covered has never before appeared in book form; some even has never been formally published, but only existed in the form of lecture notes and manuscript copies.

Algorithms often are not only given in their original form, but also implementation remarks are added. Many of the methods also have been implemented in the computer algebra systems GAP and Magma, and this book supplies a description to much of the underlying mathematics for these systems.

Chapter 1 gives an introduction into notation and terminology, both for permutation groups and algorithm analysis.

Chapter 2 studies black-box groups (that is one only considers the elementary operations that make up a group, but not the actual type of elements); in particular it examines random elements (see F. Celler et al. [Commun. Algebra 23, No. 13, 4931-4948 (1995; Zbl 0836.20094)]) and random subproducts (see L. Babai et al. [SIAM J. Comput. 26, No. 5, 1310-1342 (1997; Zbl 0885.68090)]).

Chapter 3 gives a short overview of what calculations in a group are known to be doable in polynomial time (cf. the survey by W. M. Kantor and E. M. Luks [Proc. 22nd ACM Symposium Theory Computing, 1990, 524-534 (1993)]), of “nearly linear time” algorithms for permutation groups (whose study the later chapters flesh out), and of problems currently only solvable by backtrack (see the work of B. D. McKay [Congr. Numerantium 30, 45-87 (1981; Zbl 0521.05061)] and J. S. Leon [J. Symb. Comput. 12, No. 4/5, 533-583 (1991; Zbl 0807.20001)]). It gives a good overview to a reader who is solely interested in the question of complexity classes and does not want to examine the concrete algorithms.

The core topic of the book starts in Chapter 4 which describes the ideas and data structures of the Schreier-Sims algorithm of C. C. Sims [Comput. Probl. abstract Algebra, Proc. Conf. Oxford 1967, 169-183 (1970; Zbl 0215.10002)] as well as randomization methods that can be used to reduce the complexity in a Monte-Carlo setting.

Algorithms that build immediately on a stabilizer chain are studied in Chapter 5: Point stabilizers, homomorphisms between permutation groups, the possibility to describe elements only by their base image (thus reducing storage requirements), base change and blocks of imprimitivity are covered.

Chapter 6 describes a whole battery of efficient algorithms that use a stabilizer chain data structure. Building on algorithms for the intersection with a normal closure and for centralizer in the symmetric group methods for the centralizer of a normal subgroup and core of a subnormal subgroup are given. These in turn lead to an algorithm for the composition series and chief series which first reduce to the case of primitive action and then uses the O’Nan-Scott theorem (given originally by L. L. Scott [Finite groups, Santa Cruz Conf. 1979, Proc. Symp. Pure Math. 37, 319-331 (1980; Zbl 0458.20039)], a complete version is given by M. W. Liebeck et al. [J. Aust. Math. Soc., Ser. A 44, No. 3, 389-396 (1988; Zbl 0647.20005)]) to reduce the subnormal factors. A further product are algorithms for solvable radical and \(p\)-core that also produce a small-degree permutation representation of the factor group. Together, this pool of algorithms has been fundamental for recent algorithms for more complicated structures such as subgroups (J. J. Cannon et al. [J. Symb. Comput. 31, No. 1-2, 149-161 (2001; Zbl 0984.20002)]) or conjugacy classes (A. Hulpke [Math. Comput. 69, No. 232, 1633-1651 (2000; Zbl 0962.20001)]); an outline of such algorithms is given at the end of Chapter 9.

Chapter 7 describes a special method due to C. C. Sims [J. Symb. Comput. 9, No. 5/6, 699-705 (1990; Zbl 0701.20001)] for the computation of a stabilizer chain in a solvable permutation group, together with a polycyclic generating system. Such a generator set (see R. Laue et al. [Computational group theory, Proc. Symp., Durham/Engl. 1982, 105-135 (1984; Zbl 0547.20012)]) is the basis for many efficient algorithms for solvable groups that reduce the problem via the chief factors inductively to linear algebra over a finite field. As examples a method for Sylow subgroups (a special case of P. Morje [Workshop on groups and computation, June 7-10, 1995, New Brunswick, NJ, USA. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 28, 257-272 (1997; Zbl 0878.20005)]) for solvable groups, and for conjugacy classes (following M. Mecky and J. Neubüser [Bull. Aust. Math. Soc. 40, No. 2, 281-292 (1989; Zbl 0683.20001)]) are given.

The problem of verifying a probabilistically computed stabilizer chain (and thus make the probabilistic algorithms guarantee a correct result at the cost of repeating a failed calculation) is the topic of Chapter 8. The Schreier-Todd-Coxeter-Sims algorithm of J. S. Leon [Math. Comput. 35, 941-974 (1980; Zbl 0444.20001)] and the strong generation test of C. C. Sims [previously unpublished] are given. While these tests do not have the nearly-linear time complexity of the randomized stabilizer chain calculation, this is resolved by the following algorithm of W. M. Kantor and Á. Seress [Groups St. Andrews 1997 in Bath. Selected papers of the international conference, Bath, UK, July 26-August 9, 1997. Vol. 2. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 261, 436-446 (1999; Zbl 0932.20006)].

Once “short” presentations (i.e. polylogarithmic in the order) are known for all classes of simple groups (Reviewers remark: At the time of writing this is known for all simple groups apart from the Ree groups) and these groups could be recognized constructively (for example see the review article by C. R. Leedham-Green [Groups and computation III. Walter de Gruyter. Ohio State Univ. Math. Res. Inst. Publ. 8, 229-247 (2001; Zbl 1052.20034)]) in an efficient way, one can compute first a composition series and then verify correctness of the composition factors. A variant of this algorithm is used to produce a presentation of a permutation group as done in the algorithms of J. J. Cannon [Discrete Math. 5, 105-129 (1973; Zbl 0272.20030)] and V. Gebhard [J. Algebra 233, No. 2, 526-542 (2000; Zbl 1007.20033)].

Chapter 9 deals with backtrack algorithms for the computation of centralizers, normalizers, and conjugacy tests in permutation groups. Both the traditional method described by G. Butler [J. Algorithms 4, 163-175 (1983; Zbl 0552.20004)] and the partition backtrack of McKay and Leon are described. While the conjugacy problem is not treated in complete detail, the description of the partition backtrack is the most accessible one this reviewer has so far encountered.

Chapter 10 finally deals with large base groups. These are essentially wreath products of symmetric or alternating groups and one method to deal with such groups is to recognize symmetric/alternating groups from the cycle structure of elements as suggested by E. T. Parker and P. J. Nicolai [Math. Tables Aids Comput 12, 38-43 (1958)] and J. H. Davenport and G. C. Smith [J. Pure Appl. Algebra 153, No. 1, 17-25 (2000; Zbl 0960.11053)]. A description of the author’s recent work on constructive recognition of such groups [Trans. Am. Math. Soc. 355, No. 5, 2097-2113 (2003; Zbl 1022.20004)] follows.

The book closes with a useful bibliography of about 150 items.

Each chapter comes with exercises, which vary from straightforward to demanding, those which refer to research papers might be taken better as an extended reference to the paper, than a bona-fide exercise for a student.

While the book does not require prerequisites beyond a standard algebra course, it is clearly a research monograph and might not be a book to hand a beginning graduate student for self-study.

This is in part due to the fact that nontrivial examples on permutation group algorithms very quickly reach a size that makes them infeasible for a printed medium.

A reader who wants to understand the algorithms might want to keep a sheet of paper (or a system such as GAP) at hand to follow theoretical descriptions in an explicit example.

Some illustrations of concepts, or partial lattices of subgroups might have aided understanding. This is in particular true for the two algorithms which are probably most interesting for a person who is interested in permutation calculations from a purely practical point of view, namely stabilizer chain and partition backtrack.

These few desiderata however cannot hide the fact that this is a book with an immense wealth of information which collects a large part of computational group theory for the first time in book form.

The book will be an invaluable tool for anyone who is interested in permutation groups, computational group theory or the broader area of computations involving symmetries and deserves a space on the shelf of any researcher in these areas.

Previous books have been of notably smaller scope. Apart from the fact that they represented the state of the art in a rapidly evolving sub-discipline of 15 years ago or more, they considered the subject either from a purely theoretical view such as C. M. Hoffmann [Group-theoretic algorithms and graph isomorphism. Springer (1982; Zbl 0487.68055)] or practical view such as G. Butler [Fundamental algorithms for permutation groups. Springer (1991; Zbl 0785.20001)].

The algorithms in this book in contrast combine theoretical and practical aspects to mutual benefit, a development which has been substantially promoted by the author’s work.

Much of the material covered has never before appeared in book form; some even has never been formally published, but only existed in the form of lecture notes and manuscript copies.

Algorithms often are not only given in their original form, but also implementation remarks are added. Many of the methods also have been implemented in the computer algebra systems GAP and Magma, and this book supplies a description to much of the underlying mathematics for these systems.

Chapter 1 gives an introduction into notation and terminology, both for permutation groups and algorithm analysis.

Chapter 2 studies black-box groups (that is one only considers the elementary operations that make up a group, but not the actual type of elements); in particular it examines random elements (see F. Celler et al. [Commun. Algebra 23, No. 13, 4931-4948 (1995; Zbl 0836.20094)]) and random subproducts (see L. Babai et al. [SIAM J. Comput. 26, No. 5, 1310-1342 (1997; Zbl 0885.68090)]).

Chapter 3 gives a short overview of what calculations in a group are known to be doable in polynomial time (cf. the survey by W. M. Kantor and E. M. Luks [Proc. 22nd ACM Symposium Theory Computing, 1990, 524-534 (1993)]), of “nearly linear time” algorithms for permutation groups (whose study the later chapters flesh out), and of problems currently only solvable by backtrack (see the work of B. D. McKay [Congr. Numerantium 30, 45-87 (1981; Zbl 0521.05061)] and J. S. Leon [J. Symb. Comput. 12, No. 4/5, 533-583 (1991; Zbl 0807.20001)]). It gives a good overview to a reader who is solely interested in the question of complexity classes and does not want to examine the concrete algorithms.

The core topic of the book starts in Chapter 4 which describes the ideas and data structures of the Schreier-Sims algorithm of C. C. Sims [Comput. Probl. abstract Algebra, Proc. Conf. Oxford 1967, 169-183 (1970; Zbl 0215.10002)] as well as randomization methods that can be used to reduce the complexity in a Monte-Carlo setting.

Algorithms that build immediately on a stabilizer chain are studied in Chapter 5: Point stabilizers, homomorphisms between permutation groups, the possibility to describe elements only by their base image (thus reducing storage requirements), base change and blocks of imprimitivity are covered.

Chapter 6 describes a whole battery of efficient algorithms that use a stabilizer chain data structure. Building on algorithms for the intersection with a normal closure and for centralizer in the symmetric group methods for the centralizer of a normal subgroup and core of a subnormal subgroup are given. These in turn lead to an algorithm for the composition series and chief series which first reduce to the case of primitive action and then uses the O’Nan-Scott theorem (given originally by L. L. Scott [Finite groups, Santa Cruz Conf. 1979, Proc. Symp. Pure Math. 37, 319-331 (1980; Zbl 0458.20039)], a complete version is given by M. W. Liebeck et al. [J. Aust. Math. Soc., Ser. A 44, No. 3, 389-396 (1988; Zbl 0647.20005)]) to reduce the subnormal factors. A further product are algorithms for solvable radical and \(p\)-core that also produce a small-degree permutation representation of the factor group. Together, this pool of algorithms has been fundamental for recent algorithms for more complicated structures such as subgroups (J. J. Cannon et al. [J. Symb. Comput. 31, No. 1-2, 149-161 (2001; Zbl 0984.20002)]) or conjugacy classes (A. Hulpke [Math. Comput. 69, No. 232, 1633-1651 (2000; Zbl 0962.20001)]); an outline of such algorithms is given at the end of Chapter 9.

Chapter 7 describes a special method due to C. C. Sims [J. Symb. Comput. 9, No. 5/6, 699-705 (1990; Zbl 0701.20001)] for the computation of a stabilizer chain in a solvable permutation group, together with a polycyclic generating system. Such a generator set (see R. Laue et al. [Computational group theory, Proc. Symp., Durham/Engl. 1982, 105-135 (1984; Zbl 0547.20012)]) is the basis for many efficient algorithms for solvable groups that reduce the problem via the chief factors inductively to linear algebra over a finite field. As examples a method for Sylow subgroups (a special case of P. Morje [Workshop on groups and computation, June 7-10, 1995, New Brunswick, NJ, USA. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 28, 257-272 (1997; Zbl 0878.20005)]) for solvable groups, and for conjugacy classes (following M. Mecky and J. Neubüser [Bull. Aust. Math. Soc. 40, No. 2, 281-292 (1989; Zbl 0683.20001)]) are given.

The problem of verifying a probabilistically computed stabilizer chain (and thus make the probabilistic algorithms guarantee a correct result at the cost of repeating a failed calculation) is the topic of Chapter 8. The Schreier-Todd-Coxeter-Sims algorithm of J. S. Leon [Math. Comput. 35, 941-974 (1980; Zbl 0444.20001)] and the strong generation test of C. C. Sims [previously unpublished] are given. While these tests do not have the nearly-linear time complexity of the randomized stabilizer chain calculation, this is resolved by the following algorithm of W. M. Kantor and Á. Seress [Groups St. Andrews 1997 in Bath. Selected papers of the international conference, Bath, UK, July 26-August 9, 1997. Vol. 2. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 261, 436-446 (1999; Zbl 0932.20006)].

Once “short” presentations (i.e. polylogarithmic in the order) are known for all classes of simple groups (Reviewers remark: At the time of writing this is known for all simple groups apart from the Ree groups) and these groups could be recognized constructively (for example see the review article by C. R. Leedham-Green [Groups and computation III. Walter de Gruyter. Ohio State Univ. Math. Res. Inst. Publ. 8, 229-247 (2001; Zbl 1052.20034)]) in an efficient way, one can compute first a composition series and then verify correctness of the composition factors. A variant of this algorithm is used to produce a presentation of a permutation group as done in the algorithms of J. J. Cannon [Discrete Math. 5, 105-129 (1973; Zbl 0272.20030)] and V. Gebhard [J. Algebra 233, No. 2, 526-542 (2000; Zbl 1007.20033)].

Chapter 9 deals with backtrack algorithms for the computation of centralizers, normalizers, and conjugacy tests in permutation groups. Both the traditional method described by G. Butler [J. Algorithms 4, 163-175 (1983; Zbl 0552.20004)] and the partition backtrack of McKay and Leon are described. While the conjugacy problem is not treated in complete detail, the description of the partition backtrack is the most accessible one this reviewer has so far encountered.

Chapter 10 finally deals with large base groups. These are essentially wreath products of symmetric or alternating groups and one method to deal with such groups is to recognize symmetric/alternating groups from the cycle structure of elements as suggested by E. T. Parker and P. J. Nicolai [Math. Tables Aids Comput 12, 38-43 (1958)] and J. H. Davenport and G. C. Smith [J. Pure Appl. Algebra 153, No. 1, 17-25 (2000; Zbl 0960.11053)]. A description of the author’s recent work on constructive recognition of such groups [Trans. Am. Math. Soc. 355, No. 5, 2097-2113 (2003; Zbl 1022.20004)] follows.

The book closes with a useful bibliography of about 150 items.

Each chapter comes with exercises, which vary from straightforward to demanding, those which refer to research papers might be taken better as an extended reference to the paper, than a bona-fide exercise for a student.

While the book does not require prerequisites beyond a standard algebra course, it is clearly a research monograph and might not be a book to hand a beginning graduate student for self-study.

This is in part due to the fact that nontrivial examples on permutation group algorithms very quickly reach a size that makes them infeasible for a printed medium.

A reader who wants to understand the algorithms might want to keep a sheet of paper (or a system such as GAP) at hand to follow theoretical descriptions in an explicit example.

Some illustrations of concepts, or partial lattices of subgroups might have aided understanding. This is in particular true for the two algorithms which are probably most interesting for a person who is interested in permutation calculations from a purely practical point of view, namely stabilizer chain and partition backtrack.

These few desiderata however cannot hide the fact that this is a book with an immense wealth of information which collects a large part of computational group theory for the first time in book form.

The book will be an invaluable tool for anyone who is interested in permutation groups, computational group theory or the broader area of computations involving symmetries and deserves a space on the shelf of any researcher in these areas.

Reviewer: Alexander Hulpke (Fort Collins)

##### MSC:

20B40 | Computational methods (permutation groups) (MSC2010) |

20-04 | Software, source code, etc. for problems pertaining to group theory |

20-02 | Research exposition (monographs, survey articles) pertaining to group theory |

68W30 | Symbolic computation and algebraic computation |

68W40 | Analysis of algorithms |

68Q25 | Analysis of algorithms and problem complexity |

20F05 | Generators, relations, and presentations of groups |