Rewriting systems for finite groups
Edgar E. Enochs, Jack Schmidt · 2008
Rewriting systems are useful for finite groups. A computational problem arose while studying finite perfect groups, and rewriting systems provided an effective data type for machine calculation with these groups. This dissertation consists of roughly three parts: (1) common data types cannot efficiently represent solutions to this problem, while rewriting systems can, (2) previous algorithms work quite well for this computational problem, and (3) efficient rewriting systems exist for all finite groups. Explicitly: (1) While polycyclic presentations and rewriting systems require space polynomial in n to represent the finite quotients of order pn of a fixed (virtually) pro-p-group of finite coclass, the degree of a permutation representation or of a matrix representation over some field with finitely many roots of unity both grow exponentially in n. (2) The algorithm of Anick, Squier, and Groves can compute cohomology for large finite groups such as an extension of Alt(7) of order greater than 1030 with 2-coclass equal to zero. (3) All but finitely many finite groups have a complete rewriting system where the number of rules squared is less than the group order. KEYWORDS: Rewriting systems, group cohomology, computational group theory, finite groups, perfect groups