Algorithms for Group Isomorphism via Group Extensions and Cohomology

摘要

The isomorphism problem for groups given by their multiplication tables (GPI) has long been known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. Thus, at present it is crucial to understand groups with abelian normal subgroups to develop n^o(log n)-time algorithms. Towards this goal we advocate a strategy via the extension theory of groups, which describes how a normal subgroup N is related to G/N via G. This strategy "splits" GPI into two sub problems: one regarding group actions on other groups, and one regarding group co homology. The solution of these problems is essentially necessary and sufficient to solve GPI. Most previous works naturally align with this strategy, and it thus helps explain in a unified way the recent polynomial-time algorithms for other group classes. In particular, most prior results in the multiplication table model focus on the group action aspect, despite the general necessity of co homology, for example for p-groups of class 2-believed to be the hardest case of GPI. To make progress on the group co homology aspect of GPI, we consider central-radical groups, proposed in Babai et al. (SODA 2011): the class of groups such that G mod its center has no abelian normal subgroups. Recall that Babai et al. (ICALP 2012) consider the class of groups G such that G itself has no abelian normal subgroups. Following the above strategy, we solve GPI in n^O(log log n) time for central-radical groups, and in polynomial time for several prominent subclasses of central-radical groups. We also solve GPI in n^O(log log n)-time for groups whose solvable normal subgroups are elementary abelian but not necessarily central. As far as we are aware, this is the first time that a nontrivial algorithm with worst-case guarantees has tackled both aspects of GPI-actions a- d cohomology-simultaneously. Prior to this work, only n^O(log n)-time algorithms were known, even for groups with a central radical of constant size, such as Z(G) = Z_2. To develop these algorithms we utilize several mathematical results on the detailed structure of cohomology classes, as well as algorithmic results for code equivalence, coset intersection and cyclicity testing of modules over finite-dimensional associative algebras. We also suggest several promising directions for future work.