DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

EDITORS: Larry Finkelstein, William M. Kantor
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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:

An important Workshop theme was the comparison between algorithms that have had effective implementations and recently developed algorithms that have improved worst-case asymptotic times. Many algorithms of these two types depend heavily on properties of simple groups, both for motivation and correctness proofs, while other algorithms have depended more on novel data structures than on group theory.

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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.