The sporadic simple group Monster, denoted by M, acts on the Griess algebra, which is a real vector space of dimension 196,884, equipped with a positive definite scalar product and a bilinear, commutative, and non-associative algebra product. Certain properties of this linear representation of M, together with properties (discovered by Conway and Miyamoto) of idempotents in the Griess algebra that correspond to 2A involutions in M, have been defined by Ivanov as the M-representation of the Monster. This definition enables us to talk about M-representations of arbitrary groups G that are generated by involutions. In general, an M-representation may or may not exist, but if G is isomorphic to a subgroup of the Monster and a representation is isomorphic to the corresponding subalgebra of the Griess algebra then we say that the M-representation is based on an embedding of G in the Monster.

We consider matrix groups, specified by a list of generators, over finite fields. The two most basic questions about such groups are membership in and the order of the group. Even in the case of abelian groups it is not known how to answer these questions without solving hard number theoretic prob-lems (factoring and discrete log); in fact, constructive mem-bership testing in the case of 1 × 1 matrices is precisely the discrete log problem. So the reasonable question is whether these problems are solvable in randomized polynomial time using number theory oracles. Building on 25 years of work, including remarkable recent developments by several groups of authors, we are now able to determine the order of a matrix group over a finite field of odd characteristic, and to perform constructive membership testing in such groups, in randomized polynomial time, using oracles for factoring and discrete log. One of the new ingredients of this result is the following. A group is called semisimple if it has no abelian normal sub-groups. For matrix groups over finite fields, we show that the order of the largest semisimple quotient can be deter-mined in randomized polynomial time (no number theory oracles required and no restriction on parity). As a by-product, we obtain a natural problem that belongs to BPP and is not known to belong either to RP or to coRP. No such problem outside the area of matrix groups appears to be known. The problem is the decision version of the above: Given a list A of nonsingular d × d matrices over a finite field and an integer N, does the group generated by A have a semisimple quotient of order ≥ N? We also make progress in the area of constructive recog-nition of simple groups, with the corollary that for a large class of matrix groups, our algorithms become Las Vegas.

We describe a recursive data structure for the uniform handling of permutation groups and matrix groups. This data structure allows the switching between permutation and matrix representations of segments of the input group, and has wide-ranging applications. It provides a framework to process theoretical algorithms which were considered too complicated for implementation such as the asymptotically fastest algorithms for the basic handling of large-base permutation groups and for Sylow subgroup computations in arbitrary permutation groups. It also facilitates the basic handling of matrix groups. The data structure is general enough for the easy incorporation of any matrix group or permutation group algorithm code; in particular, the library functions of the GAP computer algebra system dealing with permutation groups and matrix groups work with a minimal modification.

We present new algorithms for permutation group manipulation. Our methods result in an improvement of nearly an order of magnitude in the worst-case analysis for the fundamental problems of finding strong generating sets and testing membership. The normal structure of the group is brought into play even for such elementary issues. An essential element is the recognition of large alternating composition factors of the given group and subsequent extension of the permutation domain to display the natural action of these alternating groups. Further new features include a novel fast handling of alternating groups and the sifting of defining relations in order to link these and other analyzed factors with the rest of the group. The analysis of the algorithm depends on the classification of finite simple groups. In a sequel to this paper, using an enhancement of the present method, we shall achieve a further order of magnitude improvement.

The purpose of this note is to describe a new algorithm for finding blocks of imprimitivity for a permutation group G, operating on a domain Ω.

A base of a permutation group G is a subset B of the permutation domain such that only the identity of G fixes B pointwise. The permutation representations of important classes of groups, including all finite simple groups other than the alternating groups, admit O(log n) size bases, where n is the size of the permutation domain. Groups with very small bases dominate the work on permutation groups within computational group theory.

Article Free Access Share on Nearly linear time algorithms for permutation groups with a small base Authors: László Babai Dept. of Comp. Science, University of Chicago, Chicago, Illinois and Dept. of Algebra, Eötvös University, Budapest, Hungary H-1088 Dept. of Comp. Science, University of Chicago, Chicago, Illinois and Dept. of Algebra, Eötvös University, Budapest, Hungary H-1088View Profile , Gene Cooperman College of Comp. Science, Northeastern University, Boston, Mass. College of Comp. Science, Northeastern University, Boston, Mass.View Profile , Larry Finkelstein College of Comp. Science, Northeastern University, Boston, Mass. College of Comp. Science, Northeastern University, Boston, Mass.View Profile , Ákos Seress Dept. of Mathematics, Ohio State University, Columbus, Ohio Dept. of Mathematics, Ohio State University, Columbus, OhioView Profile Authors Info & Claims ISSAC '91: Proceedings of the 1991 international symposium on Symbolic and algebraic computationJune 1991 Pages 200–209https://doi.org/10.1145/120694.120724Online:01 June 1991Publication History 19citation320DownloadsMetricsTotal Citations19Total Downloads320Last 12 Months9Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Fast Monte Carlo algorithms for permutation groups Authors: László Babai Univ. of Chicago, Chicago, IL Univ. of Chicago, Chicago, ILView Profile , Gene Cooperman Northeastern Univ., Boston, MA Northeastern Univ., Boston, MAView Profile , Larry Finkelstein Northeastern Univ., Boston, MA Northeastern Univ., Boston, MAView Profile , Eugene Luks Univ. of Oregon, Eugene Univ. of Oregon, EugeneView Profile , Ákos Seress Ohio State Univ., Columbus Ohio State Univ., ColumbusView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 90–100https://doi.org/10.1145/103418.103435Published:03 January 1991Publication History 14citation519DownloadsMetricsTotal Citations14Total Downloads519Last 12 Months55Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The diameter of a group G with respect to a set S of generators is the maximum over g in G of the length of the shortest word in S union S/sup -1/ representing g. This concept arises in the contexts of efficient communication networks and Rubik's-cube-type puzzles. 'Best' generators are pertinent to networks, whereas 'worst' and 'average' generators seem more adequate models for puzzles. A substantial body of recent work on these subjects by the authors is surveyed. Regarding the 'best' case, it is shown that, although the structure of the group is essentially irrelevant if mod S mod is allowed to exceed (log mod G mod )/sup 1+c/(c>0), it plays a strong role when mod S mod =O(1).>

Novel algorithms for computation in permutation groups are presented. They provide an order-of-magnitude improvement in the worst-case analysis of the basic permutation-group problems, including membership testing and computing the order of the group. For deeper questions about the group, including finding composition factors, an improvement of up to four orders of magnitude is realized. These and other essential investigations are all accomplished in O(n/sup 4/log/sup c/n) time. The approach is distinguished by its recognition and use of the intrinsic structure of the group at hand.>

There are n persons. Each knows a different item of information. They communicate by k-conference calls, i.e., k persons participate in each conversation. Our goal is to give a sequence of calls subject to the fact that everyone hears each gossip exactly once; moreover, the number of calls is as small as possible. Appropriate sequences of conversations do not exist for all n; we give calling schemes for all feasible n’s, with finitely many exceptions, subject to the fact that the number of calls is a linear function of n.

We show that the basic problems of permutation group manipulation admit efficient parallel solutions. Given a permutation group G by a list of generators, we find a set of NC-efficient strong generators in NC. Using this, we show, that the following problems are in NC: membership in G; determining the order of G; finding the center of G; finding a composition series of G along with permutation representations of each composition factor. Moreover, given G, we are able to find the pointwise stabilizer of a set in NC. One consequence is that isomorphism of graphs with bounded multiplicity of eigenvalues is in NC.