Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1028.20002
Seress, Ákos
Permutation group algorithms. (English)
[B] Cambridge Tracts in Mathematics. 152. Cambridge: Cambridge University Press. ix, 264 p. \sterling 47.50; \$ 65.00 (2003). ISBN 0-521-66103-X/hbk

This monograph gives a thorough overview of the current knowledge on computing with permutation groups.\par 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 {\it C. M. Hoffmann} [Group-theoretic algorithms and graph isomorphism. Springer (1982; Zbl 0487.68055)] or practical view such as {\it G. Butler} [Fundamental algorithms for permutation groups. Springer (1991; Zbl 0785.20001)].\par 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.\par 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.\par 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 {\tt GAP} and {\tt Magma}, and this book supplies a description to much of the underlying mathematics for these systems.\par Chapter 1 gives an introduction into notation and terminology, both for permutation groups and algorithm analysis.\par 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 {\it F. Celler} et al. [Commun. Algebra 23, No. 13, 4931-4948 (1995; Zbl 0836.20094)]) and random subproducts (see {\it L. Babai} et al. [SIAM J. Comput. 26, No. 5, 1310-1342 (1997; Zbl 0885.68090)]).\par Chapter 3 gives a short overview of what calculations in a group are known to be doable in polynomial time (cf. the survey by {\it W. M. Kantor} and {\it 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 {\it B. D. McKay} [Congr. Numerantium 30, 45-87 (1981; Zbl 0521.05061)] and {\it 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.\par The core topic of the book starts in Chapter 4 which describes the ideas and data structures of the Schreier-Sims algorithm of {\it 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.\par 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.\par 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 {\it 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 {\it 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 ({\it J. J. Cannon} et al. [J. Symb. Comput. 31, No. 1-2, 149-161 (2001; Zbl 0984.20002)]) or conjugacy classes ({\it 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.\par Chapter 7 describes a special method due to {\it 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 {\it 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 {\it 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 {\it M. Mecky} and {\it J. Neubüser} [Bull. Aust. Math. Soc. 40, No. 2, 281-292 (1989; Zbl 0683.20001)]) are given.\par 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 {\it J. S. Leon} [Math. Comput. 35, 941-974 (1980; Zbl 0444.20001)] and the strong generation test of {\it 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 {\it W. M. Kantor} and {\it Á. 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)].\par 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 {\it 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 {\it J. J. Cannon} [Discrete Math. 5, 105-129 (1973; Zbl 0272.20030)] and {\it V. Gebhard} [J. Algebra 233, No. 2, 526-542 (2000; Zbl 1007.20033)].\par Chapter 9 deals with backtrack algorithms for the computation of centralizers, normalizers, and conjugacy tests in permutation groups. Both the traditional method described by {\it 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.\par 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 {\it E. T. Parker} and {\it P. J. Nicolai} [Math. Tables Aids Comput 12, 38-43 (1958)] and {\it J. H. Davenport} and {\it 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.\par The book closes with a useful bibliography of about 150 items.\par 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.\par 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.\par 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.\par A reader who wants to understand the algorithms might want to keep a sheet of paper (or a system such as {\tt GAP}) at hand to follow theoretical descriptions in an explicit example.\par 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.\par 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.\par 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.
[Alexander Hulpke (Fort Collins)]

MSC 2000:: *20B40 Computational methods (permutation groups)
20-04 Machine computation, programs (group theory)
20-02 Research monographs (group theory)
68W30 Symbolic computation and algebraic computation
68W40 Analysis of algorithms
68Q25 Analysis of algorithms and problem complexity
20F05 Presentations of groups

Keywords: permutation groups; algorithms; computer algebra systems; black-box groups; Schreier-Sims algorithm; composition series; chief series; presentations

Citations: Zbl 0487.68055; Zbl 0785.20001; Zbl 0836.20094; Zbl 0885.68090; Zbl 0521.05061; Zbl 0807.20001; Zbl 0215.10002; Zbl 0458.20039; Zbl 0647.20005; Zbl 0984.20002; Zbl 0962.20001; Zbl 0701.20001; Zbl 0547.20012; Zbl 0878.20005; Zbl 0683.20001; Zbl 0444.20001; Zbl 0932.20006; Zbl 1052.20034; Zbl 0272.20030; Zbl 1007.20033; Zbl 0552.20004; Zbl 0960.11053; Zbl 1022.20004

Cited in: Zbl 1091.20001

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]