Discrete Mathematics and Theoretical Computer Science

TITLE: "GROUPS AND COMPUTATION"

EDITORS: Larry Finkelstein, William M. Kantor

Published by the American Mathematical Society

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

The Workshop "Groups and Computation" took place at DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science on the campus of Rutgers University, on October 7-10, 1991. The Workshop explored and fostered the interplay of a number of research areas:

- Symbolic algebra and computer algebra, which have developed algorithms for group-theoretic computation and have built large integrated software packages (such as Cayley and GAP).
- Theoretical computer science, which has studied the complexity of computation with groups.
- Group theory, which has provided new tools for understanding the structure of groups, many of which involve the classification and properties of finite simple groups.
- Applications of group computation within mathematics and computer science, which have dealt with such diverse subjects as simple groups, combinatorial search, networks and the analysis of data.

The scientific program consisted of invited lectures and short research announcements, as well as informal discussions and software demonstrations. The four extended length talks (by C. C. Sims, J. Neubuser, E. M. Luks and L. Babai) laid out part of the groundwork for discussions of relationships between implementation and complexity questions; this was continued in further talks and in informal settings. The present Proceedings, which contain most, but not all, of the talks given at the Workshop, are dominated by papers amplifying these relationships. However, there were further subjects discussed in the Workshop and represented here: parallel algorithms for groups, computation in associative algebras, asymptotic behavior of permutation groups, studying finite groups using infinite reflection groups, combinatorial searching, computing with representations (including applications to statistics), and Cayley graphs as models for interconnection networks. Some of these subjects naturally led to practical computational questions. In fact, the difficulty encountered in attemping to separate or pigeon-hole the papers in this volume is indicative of the fact that there are no clear dividing lines between practical and theoretical aspects of the subject of the Workshop, nor between the needs of users and those more interested in the algorithms themselves.

It was our belief that a full discussion of implementation experiences would lead to a deeper understanding of the mathematical issues that underlie group computations, leading both to new algorithms and to improvements of existing ones. In order to provide some background for this, software provided by the participants was available during the entire Workshop; it was discussed in a number of talks, and one evening was devoted to informal software presentations. In addition, there was a panel discussion whose theme was "Problems whose current algorithmic solutions are, in practice, too time- or space-consuming." The panelists were selected for their broad experience in building software for group computation; the discussions provided insight into implementation problems and goals.

We are grateful for the assistance of our co-organizers, Daniel Gorenstein and Charles Sims. The possibility of arranging a Workshop arose accidentally during lunch with Danny, a mere thirteen months before the Workshop took place. His encouragement and enthusiasm helped us to overcome many of the usual difficulties encountered when organizing an international workshop. We also thank the staff at DIMACS for their efforts in helping the Workshop to function smoothly. Donna Harmon and Christine Thivierge of the American Mathematical Society provided invaluable assistance in the production of these Proceedings. Finally, we thank DIMACS, the National Science Foundation, the National Security Agency and Rutgers University for their financial support of the Workshop.

Foreword xi Preface xiii Workshop Program xv Participants xvii Computing Composition Series in Primitive Groups Laszlo Babai, Eugene M. Luks, and Akos Seress 1 Computing Blocks of Imprimitivity for Small-Base Groups in Nearly Linear Time 17 Robert Beals Fast Fourier Transforms for Symmetric Groups Michael Clausen and Ulrich Baum 27 From Hyperbolic Reflections to Finite Groups J. H. Conway 41 Combinatorial Tools for Computational Group Theory Gene Cooperman and Larry Finkelstein 53 Efficient Computation of Isotypic Projections for the Symmetric Group 87 Persi Diaconis and Daniel Rockmore Constructing Representations of Finite Groups John D. Dixon 105 A Graphics System for Displaying Finite Quotients of Finitely Presented Groups 113 Derek F. Holt and Sarah Rees Random Remarks on Permutation Group Algorithms William M. Kantor 127 Application of Group Theory to Combinatorial Searches Clement W. H. Lam 133 Permutation Groups and Polynomial-Time Computation Eugene M. Luks 139 Parallel Computation of Sylow Subgroups in Solvable Groups Peter D. Mark 177 Computation with Matrix Groups over Finite Fields Cheryl E. Praeger 189 Asymptotic Results for Permutation Groups Laszlo Pyber 197 Computations in Associative Algebras Lajos Ronyai 221 Cayley Graphs and Direct-Product Graphs Arnold L. Rosenberg 245 Group Membership for Groups with Primitive Orbits Namita Sarawagi, Gene Cooperman, and 253 Larry Finkelstein PERM: A Program Computing Strong Generating Sets Akos Seress and Ivan Weisz 269 Complexity Issues in Infinite Group Theory Charles C. Sims 277 GRAPE: A System for Computing with Graphs and Groups Leonard H. Soicher 287 Implications of Parallel Architectures for Permutation Group Computations 293 Bryant W. York

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.