Algorithms for group isomorphism via
group extensions and cohomology ∗
Joshua A. Grochow

†

Youming Qiao

‡

arXiv:1309.1776v2 [cs.DS] 11 Apr 2017

April 12, 2017

Abstract
The isomorphism problem for finite groups of order n (GpI) has long been known to be
solvable in nlog n+O(1) time, but only recently were polynomial-time algorithms designed for
several interesting group classes. Inspired by recent progress, we revisit the strategy for GpI
via the extension theory of groups.
The extension theory describes how a normal subgroup N is related to G/N via G, and
this naturally leads to a divide-and-conquer strategy that “splits” GpI into two subproblems:
one regarding group actions on other groups, and one regarding group cohomology. When the
normal subgroup N is abelian, this strategy is well-known. Our first contribution is to extend
this strategy to handle the case when N is not necessarily abelian. This allows us to provide a
unified explanation of all recent polynomial-time algorithms for special group classes.
Guided by this strategy, to make further progress on 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. This class is a natural extension of the group class considered by
Babai et al. (ICALP 2012), namely those groups with no abelian normal subgroups. Following the above strategy, we solve GpI in nO(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 nO(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 there have been worstcase guarantees on a no(log n) -time algorithm that tackles both aspects of GpI—actions and
cohomology—simultaneously.
Prior to this work, the best proven upper bounds on algorithms for groups with central
radicals were nO(log n) , even for groups with a central radical of constant size, such as Rad(G) =
Z(G) = Z2 . To develop our new 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.

∗

The introduction may serve as an extended abstract: Section 1.3 contains an informal exposition of Section 2,
Section 3 and Section 4; Section 1.4 gives a brief overview of Section 5, Section 6 and Section 7. An extended abstract
based on the introduction appeared as [GQ14].
†
Department of Computer Science, University of Colorado, Boulder and the Santa Fe Institute.
joshua.grochow@cs.colorado.edu
‡
Centre for Quantum Software and Information, University of Technology Sydney. youming.qiao@uts.edu.au

i

Contents
1 Introduction
1.1 Main results . . . . . . . . . . . . . . . . . . . . .
1.2 Motivation for the classes of groups considered .
1.3 A strategy via group extensions and cohomology
1.4 Overview of our algorithms . . . . . . . . . . . .
1.5 Organization of the paper . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

1
3
5
6
9
11

2 Preliminaries on abelian cohomology
11
2.1 Pseudo-congruent extensions versus isomorphic total groups . . . . . . . . . . . . . . 13
3 Nonabelian cohomology and its applications
14
3.1 Application to extensions with trivial outer action . . . . . . . . . . . . . . . . . . . 19
4 The
4.1
4.2
4.3

strategy
22
A recipe for group isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Some recent results from the point of view of the main lemma . . . . . . . . . . . . . 23
Necessity of pseudo-congruence and cohomology . . . . . . . . . . . . . . . . . . . . 26

5 Preliminaries for the algorithms

27

6 When enumerating Aut(Q) is allowed
29
6.1 For central extensions of general abelian groups (Theorem A) . . . . . . . . . . . . . 29
6.2 For general extensions of elementary abelian groups (Theorem B) . . . . . . . . . . . 36
7 When Aut(Q) is too big
7.1 Preparations from cohomology .
7.2 Warm-up result . . . . . . . . . .
7.3 Proof of Theorem C . . . . . . .
7.4 Towards the general abelian case

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

38
39
40
41
44

8 Future directions
47
8.1 Abelian radical . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
8.2 The Babai–Beals filtration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
8.3 The Cannon–Holt strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
A A gentle introduction to group extensions and cohomology

55

B Generalized Fitting subgroups of groups with central radical

64

C Relationship with results on practical algorithms

65

ii

1

Introduction

The group isomorphism problem (GpI) is to determine whether two finite groups are isomorphic.
For groups of order n, the easy nlog n+O(1) -time algorithm [FN70, Mil78]1 for the general case of GpI
has barely seen any asymptotic improvement over the past four decades; it was improved recently to
n1/4 log n+O(1) by Rosenbaum [Ros13a] (see [GR16, Sec. 2.2]), but even the extensive body of work
on practical algorithms led by Eick, Holt, Leedham-Green and O’Brien (e. g., [BEO02, ELGO02,
BE99, CH03])—resulting in most of the functional algorithms in use today—was recently found
[Wil14] to only improve the constant in the exponent, still resulting in a nΘ(log n) -time algorithm
for the general case. The past few years have witnessed a resurgence of activity on worst-case
guaranteed algorithms for this problem [LG09, BCGQ11, QST11, Wag11, LW12, BQ12, BCQ12,
Ros13b, Ros13a, BMW15, GQ15].
Before introducing these works and our results, we recall why group isomorphism is an intriguing problem from the complexity-theoretic perspective, even when the groups are given by their
multiplication tables. (See Remark 1.1 below.) We call this version of the problem CayleyGpI. As
CayleyGpI reduces to Graph Isomorphism (GraphI) (see, e. g., the book [KST93]), CayleyGpI
currently has an intermediate status: It is not NP-complete unless PH collapses [BHZ87, BM88],
and is not known to be in P. In addition to its intrinsic interest, resolving the exact complexity of
GpI is a tantalizing question. Further, there is a surprising connection between CayleyGpI and
the Geometric Complexity Theory program (see, e. g., [Mul11] and references therein): Techniques
from CayleyGpI were used to solve cases of Lie Algebra Isomorphism that have applications
in Geometric Complexity Theory [Gro12].
In a survey article [Bab95] in 1995, after enumerating several isomorphism-type problems including GraphI and GpI, Babai expressed the belief that CayleyGpI might be the only one
expected to be in P. Indeed, in many ways CayleyGpI seems easier than GraphI: There is a
simple nlog n+O(1) -time algorithm for GpI, whereas the best known algorithm for GraphI takes
c
time 2(log n) for some c ≥ 3 [Bab16] and is quite complicated.2 There is a polynomial-time reduction from CayleyGpI to GraphI, yet there is provably no AC0 reduction in the opposite direction
[CTW10]. The reduction CayleyGpI ≤ GraphI means that CayleyGpI stands as an obstacle to
putting GraphI into P; in light of the recent quasi-polynomial-time algorithm for GraphI [Bab16],
this obstacle has become much more salient (the previous best algorithm for GraphI was so far
from quasi-polynomial that there were clearly obstacles to be overcome before CayleyGpI became
a serious obstacle, but many of those obstacles have now been overcome). Further, GraphI is
as hard as its counting version, whereas no such counting-to-decision reduction is known for GpI.
Finally, whereas the smallest standard complexity class known to contain GraphI is NP ∩ coAM,
Arvind and Torán [AT11] showed that CayleyGpI for solvable groups is in NP ∩ coNP under a
plausible assumption, weaker than that needed to show GraphI ∈ coNP (recall that a group is
solvable if all its composition factors are abelian, or equivalently if the derived series G0 = G,
Gi+1 = [Gi , Gi ] terminates in the identity).
Despite this situation and considerable attention to GpI, prior to 2009 the actual developments
towards algorithms with worst-case guaranteed running time polynomial in |G| essentially stopped
at abelian groups, although there have been impressive practical advances (see, e. g., the theses
1

2

Miller [Mil78] attributes this algorithm to Tarjan.
time of writing, the paper [Bab16] is still under peer review. The previous-best algorithm took time
(see [BL83]), and was also quite complicated.

2
At the
√
O( n log n)

1

[Smi94, How12] and references therein for nice overviews). Isomorphism of abelian groups has long
been known to be solvable in polynomial time [Sav80, Ili85, Vik96, Kav07]. The next natural group
class after abelian groups—class 2 nilpotent groups, whose quotient by their center is abelian—
turns out to be formidable (see [GZ91, LW12, BMW15] for efficient algorithms in some restricted
cases).
Beginning in 2009 there were several advances on worst-case guaranteed algorithms, starting
with Le Gall [LG09]. In [BCQ12], following [BCGQ11], Babai et al. developed a polynomial-time algorithm for groups with no abelian normal subgroups. This suggests the presence of abelian normal
subgroups as a bottleneck. With this in mind, Babai and Qiao [BQ12] developed a polynomial-time
algorithm for a special class of non-nilpotent solvable groups, building on [LG09, QST11]; this was
recently extended by the present authors to the so-called groups of tame extensions [GQ15]. In
[LW12], Lewis and Wilson made intriguing progress on p-groups: They gave a polynomial-time
algorithm for quotients of generalized Heisenberg groups, a decently large subclass of p-groups of
class 2. Rosenbaum’s recent works [Ros13b, Ros13a] (some of them building on ideas of Wagner
[Wag11]) lead to an n1/4 log n+O(1) -time algorithm for GpI (see [GR16, Sec. 2.2]). To summarize,
at present it is crucial to understand indecomposable groups with abelian normal subgroups to
develop no(log n) -time algorithms.
Given these developments, we are at an interesting crossroads: First, as several nontrivial algorithms with worst-case guarantees have recently been developed (or worst-case guarantees proven
for previously known algorithms), it is reasonable to reflect back to see if there is some common
pattern or structure to these results. Second, of course, we should continue to improve the state
of the art by developing more no(log n) -time algorithms for special group classes. Finally, class 2
nilpotent groups seem to remain the bottleneck, but despite heuristic evidence, it is still desirable
to formalize a reduction from the general case to this seeming bottleneck.
In this paper we contribute to all three of the preceding aspects. Our contributions are twofold:
(1) we show how a general strategy for group isomorphism from the mathematics literature can be
used to bound the worst-case complexity; and (2) using that strategy, we develop an nO(log log n) time algorithm for a group class proposed in [BCGQ11], and polynomial-time algorithms for some
prominent subclasses thereof. The worst-case analysis of this strategy also helps to explain in a
unified way the recent successes on other group classes [LG09, QST11, BQ12, BCGQ11, BCQ12,
LW12, GQ15], which can be viewed as adding class-specific tactics to the general strategy. We also
explain how these results may help to reduce general GpI to the class 2 nilpotent case.
Remark 1.1 (On efficient implementation versus computational complexity). There are naturally
two audiences for this paper, who might view it quite differently: (A) computational complexity
theorists / algorithms theory researchers, and (B) computational group theorists. To some in the
latter group, much of the content of this paper is surely well-known, and to them perhaps not even
worth writing down at this point in history. To them, we would like to highlight our results on nonabelian cohomology (Section 3) and the use of Guralnick–Kantor–Kassabov–Lubotzky [GKKL07],
which we believe may be new even in light of the large body of work in that community. We
would also like to point out that the remainder of the paper will likely seem new to computational
complexity theorists, despite seeming trivial to computational group theorists. As so often happens
when ideas from one area B (in this case, classical and computational group theory) are imported
to another area A (computational complexity), area B may view the results as trivial while area A
may view them as a nontrivial advance. However, while much of this paper is targeted at computational complexity theorists and so has this flavor, we believe that some of the results (as mentioned
2

above) will be new to both communities.
As discussed above, there are good reasons (e. g., related to GraphI) to be interested in the
getting the asymptotic complexity of GpI down to polynomial in the order of the group, independently of its (ir)relevance to practical implementation. Combined with the fact that all of the
practical algorithms put together still leave the worst-case bound at |G|Θ(log |G|) [Wil14], we thus
state our runtime bounds as a function of n = |G|. Nonetheless, our algorithms are fairly agnostic
to the method of input, and in particular do not depend on the input being a Cayley table. That is,
when the runtime of an algorithm is at least quadratic in the order of the group, even if the group
is input as a black box, the algorithm may first enumerate the entire multiplication table, and then
proceed from there.
Except in a few cases, we do not bother to estimate multiplicative constants, nor even constant
exponents, in most of our algorithms. The current inability to get a general algorithm with run-time
|G|o(log |G|) [Wil14] suggests that this is a potentially deep research topic, and getting algorithms
with guaranteed run-time |G|O(1) can be seen as a first step in understanding the difficulties involved
(not to mention its complexity-theoretic interest). Furthermore, there is non-trivial precedent for
synergistic interaction between worst-case analyses and practical algorithms, as reflected in, e. g.,
A. Seress’s pioneering implementations in GAP [GG13] of theoretically-proven fast algorithms for
permutation groups (see, e. g., [Ser03]). Therefore, although we do not deal with issues of practical
algorithms in this paper, it is our sincere hope that this great tradition will continue in future work.

1.1

Main results

The classes of groups we consider are natural extensions of the class of groups considered in
[BCGQ11, BCQ12], and are additionally motivated by the Babai–Beals filtration [BB99] (resurrecting certain ideas that go back to Fitting [Fit33]), and the Cannon–Holt approach to group
isomorphism in the practical setting [CH03]. We go into the details of the Babai–Beals filtration and
the Cannon–Holt approach in Section 8. Here we merely give enough of a flavor to help motivate
the classes of groups we consider.
Important in both the Babai–Beals filtration and the Cannon–Holt approach is the solvable
radical. The solvable radical Rad(G) of a group G is the unique maximum solvable normal subgroup of G. Note that the center Z(G), as an abelian normal subgroup, is contained in Rad(G).
G/ Rad(G) contains no solvable normal subgroups, side-stepping the currently intractable obstacle
of solvable groups. Babai et al. [BCQ12] give a polynomial-time algorithm for isomorphism of
groups with no solvable normal subgroups (equivalently, no abelian normal subgroups); following
them, we call such groups “semisimple.”
We mainly consider the class of groups whose solvable radical coincides with its center, that is,
Rad(G) = Z(G); in Section 6.2 we also consider groups whose solvable radical is abelian, but need
not be contained in the center. The former class, which we refer to as groups with central radicals
or central-radical groups for short, is a natural extension of the class of semisimple groups and a
natural stepping stone towards general groups (see Figure 1 below). Note that for such groups the
solvable radical is necessarily abelian. Besides the motivations mentioned above, central-radical
groups also cover a class of groups that is well-studied in finite group theory (see Appendix B). In
the theory of Lie groups, central-radical groups correspond to the well-studied and important class
of reductive Lie groups, which are important throughout mathematics and physics, often because
of their nice representation-theoretic properties.
We use the strategy outlined in Section 1.3 below to achieve the following results. For groups
3

with central radicals, we give an nO(log log n) -time algorithm in general, and for several subclasses
of groups with central radicals we give polynomial-time algorithms. We also give similarly efficient
algorithms for groups with elementary abelian, but not necessarily central, radicals. Prior to this
work, the best proven upper bounds on algorithms for groups with central radicals were nO(log n) ,
even for groups with a central radical of constant size, such as Rad(G) = Z(G) = Z2 .
Recall that for any groups G and H, the set of isomorphisms between them is either empty
or a coset of the automorphism group Aut(G) in the group of permutations of the disjoint union
∼
=
G t H. We say that the coset of isomorphisms can be found if one isomorphism G → H and a
generating set for Aut(G) can be found. Finding the full coset of isomorphisms—rather than just
deciding GpI or finding a single isomorphism—is often useful in recursively building algorithms for
larger group classes from those for smaller classes.
Theorem A (=Corollary 6.2). Isomorphism of central-radical groups of order n can be decided
in time nc log log n+O(1) , for c = 1/ log2 (60) ≈ 0.169. Furthermore, if the radical is elementary
abelian, the coset of isomorphisms can be found in the same time bound.
The algorithm in the above theorem in fact runs in polynomial time when the order or structure
of the semisimple quotient G/ Rad(G) is bounded as follows. Recall that a normal subgroup of G is
minimal if it is nontrivial and does not contain any smaller normal subgroups of G. The number of
minimal normal subgroups of G/ Rad(G) is always at most log60 n; if it happens to be just slightly
smaller, then we have:
Corollary 6.3. Let G and H be central-radical groups of order n. If G/ Rad(G) has O( logloglogn n )
minimal normal subgroups, isomorphism between G and H can be decided in poly(n) time. Furthermore, if the radical is elementary abelian, the coset of isomorphisms can be found in the same
time bound.
In particular, this includes groups G satisfying |G/ Rad(G)| ≤ nO(1/ log log n) , but also many
groups where G/ Rad(G) is much larger. Both of these theorems are in fact corollaries of our more
general Theorem 6.1 together with previous results on semisimple groups [BCGQ11], but we defer
the statement of Theorem 6.1 until Section 6, as the above results make its significance clearer.
For groups with elementary abelian radicals—even if they are not central—we get the same
conclusions. This requires us to simultaneously solve Action Compatibility and Cohomology Class Isomorphism. We combine the above techniques with a novel reduction to known
representation-theoretic algorithms [CIK97] to get:
Theorem B (=Corollaries 6.12 and 6.13). Isomorphism of groups of order n with elementary
abelian radicals can be decided, and the coset of isomorphisms found, in time nc log log n+O(1) , for
c = 1/ log2 (60) ≈ 0.169.
If furthermore G/ Rad(G) has O( logloglogn n ) normal subgroups, isomorphism can be decided, and
the coset of isomorphisms found, in poly(n) time.
We then consider central-radical groups with G/ Rad(G) a direct product of nonabelian simple
groups. Although this may seem restrictive, this class of groups is quite natural. In group theory,
this class is closely related to the generalized Fitting subgroups (see, e. g., [Suz86, Ch. 6, §6]
and [Asc00, Ch. 11], as well as Appendix B). Also, within central-radical groups, this class has
two characterizations: (1) the last two of the four levels of the Babai–Beals filtration are trivial
(see Section 8.2); or (2) those groups that are equal to their generalized Fitting subgroup (see
4

Appendix B). Our next result gives polynomial-time algorithms for this group class, which includes,
Θ(log n)
Θ(log n)
for example, central extensions of Zp
by Ak
, which do not satisfy the conditions of the
results above.
Theorem C (=7.1). Isomorphism between two groups G1 , G2 with central, elementary abelian
radicals can be decided, and the coset of isomorphisms found, in poly(|Gi |) time if either:
1. G1 / Rad(G1 ) is a direct product of simple groups; or
2. G1 / Rad(G1 ) is a direct product of perfect groups, each of order O(1).
More importantly, we believe the techniques that go into proving this theorem are worth noting:
we rely on a detailed analysis of the structure of the cohomology classes specific to this group class
(see Section 7.1, and the use of the powerful results of [GKKL07]) to allow for the application
of known algorithmic techniques, including singly-exponential-time algorithms for Linear Code
Equivalence [Bab10] (see [BCGQ11, Thm. 7.1]) and Coset Intersection [Bab83, Luk99] (see
also [Bab08, BKL83]).

1.2

Motivation for the classes of groups considered

Aside from the motivations already mentioned above, Figure 1 gives the general idea of where this
paper fits in the picture of a larger approach towards putting GpI into P. The figure is neither
complete nor 100% accurate in terms of the landscape of groups and algorithms for GpI, but is
more or less correct for algorithms with worst-case guarantees at a large scale.

Figure 1: Some progress on group isomorphism. The arrow on the left indicates that the techniques
for abelian groups hit a wall before class 2 nilpotent groups. The arrow on the right indicates the
recent progress at the “opposite end of the spectrum,” including this paper and prospects for future
progress.
While central-radical groups may seem to be only a slight extension of semisimple groups, they
in fact differ significantly from previous classes of groups with no(log n) -time isomorphism algorithms.
In particular, most previous no(log n) -time algorithms for GpI of special group classes only consider
one of the two main aspects of GpI, namely actions (in Section 4.2, we briefly indicate how actions
are used in [LG09, QST11, BQ12, BCGQ11, BCQ12]). On the other hand, to work with groups
with central radicals, we need to focus on the other main aspect of the problem, namely cohomology
(see Section 1.3).
Our results also suggest one more step towards a formal reduction from the general case to
nilpotent groups of class 2. In particular, in Proposition 3.13 and Remark 3.14, we show that
5

for groups G where the action of G on Rad(G) by conjugation is essentially trivial (technically:
the action is by inner automorphisms of Rad(G)) and Aut(Z(Rad(G))) is small, GpI reduces to
isomorphism of central-radical groups and isomorphism of solvable groups, separately. Thus, if
isomorphism of central-radical groups could be decided in polynomial time, then GpI for this class
of groups would reduce to GpI for solvable groups. Note that central-radical groups arise here
naturally, by considering cases in which the relationship between G/ Rad(G) and Rad(G) is simple.
This is just one example of how we believe our ideas point towards a possible reduction from the
general case to nilpotent groups; some other ideas in this paper may also be useful in this regard
(see Section 8.3).

1.3

A strategy via group extensions and cohomology

In this paper we use the theory of group extensions (which we describe briefly in this section,
and in more detail in Section 2, and give expository preliminaries in Appendix A; for textbook
treatments, see, e. g., [Rob96, Chapter 11] and [Rot94, Chapter 7]) to show that the group isomorphism problem “splits” into two subproblems—one coming from actions of groups on other
groups (Action Compatibility), and the other coming from group extensions and cohomology
(Cohomology Class Isomorphism), which we explain below. We note that Besche and Eick
have proposed this splitting in a slightly different setting, under the name “strong isomorphism”
[BE99]. In the abstract theory of finite groups this splitting is standard material; the contribution
here is the observation that this standard material can be used to prove worst-case algorithmic
guarantees and that doing so is useful and even formally necessary to resolve the complexity of
GpI. We also extend this approach to the setting where the normal subgroup can be non-abelian.
For the converse direction, we observe that special cases of these subproblems reduce to GpI under
polynomial-time reductions (Section 4.3). We summarize these results in:
Facts 4.1, 4.3, and Lemmas 2.3, 3.7 (“Splitting” GpI into actions and cohomology).
• For coprime extensions Action Compatibility ≡pm GpI.
• For p-groups of class 2, when p > 2, Cohomology Class Isomorphism ≡pm GpI.
• GpI for groups with a normal subgroup from one class of groups N and a quotient from a
class of groups Q reduces to solving GpI in N , solving it in Q, and simultaneously solving
Action Compatibility and Cohomology Class Isomorphism.
A “simultaneous solution” to these two problems is possible because they have the same space of
potential solutions, namely certain automorphisms of certain groups; a simultaneous solution is an
automorphism that is simultaneously a solution for both problems. See Section 1.4 and Lemma 2.3
for more details.
Most previous complexity-theoretic results on GpI have focused on some combination of algorithmic techniques and Action Compatibility. In this paper, for the first time from the
worst-case complexity perspective, we make progress on Cohomology Class Isomorphism.
We now explain this “splitting” and the problems mentioned above informally. Consider the
following natural strategy for testing whether G is isomorphic to H. If G is simple, then isomorphism can be tested in polynomial time as G is generated by at most two elements (Fact 5.1). If G
is not simple, then it has some normal subgroup N G, and we may try to use a divide-and-conquer
strategy by first solving the isomorphism problem for N and G/N . However, even if we find M  H
6

such that N ∼
= M and G/N ∼
= H/M , this is typically not sufficient to conclude that G ∼
= H: e. g.,
Z4 and Z2 × Z2 both have Z2 as a normal subgroup, with corresponding quotient Z2 . We must then
understand how the groups N and G/N “glue” back together to get G. G is called an extension of
N by G/N (some authors use the opposite order of terminology); given N and Q, understanding
the collection of groups G which are extensions of N by Q—that is, where N  G and G/N ∼
= Q—is
known as the extension problem. The extension problem is considered quite difficult in general,
but the theory of group cohomology exactly captures this problem and provides useful tools for its
study, including connections with other cohomology theories such as in algebraic topology. One of
the main technical achievements of the present paper is to make some aspects of group cohomology
effective in the setting of worst-case complexity.
When N is abelian the extension theory is conceptually easier and technically cleaner. Coincidentally, due to the polynomial-time algorithm for semisimple groups [BCQ12], abelian normal
subgroups are exactly the subject of interest at present. So for the rest of this subsection, we assume N is abelian; the theory for the general case is similar but more complicated, and is covered
in Section 3.
The extensions of N by Q are governed by two pieces of data: (1) an action of Q on N and (2)
a cohomology class. We explain each of these in turn.
The action. If G is an extension of N by Q, then N  G, so G acts on N by conjugation, giving
a homomorphism θ0 : G → Aut(N ). As we have assumed N is abelian, N lies in the kernel of θ0 ,
so the conjugation action of G on N induces an action θ of G/N ∼
= Q on N . Two such actions are
compatible if they become equal after applying some element of Aut(N ) × Aut(Q), giving rise to
the first problem:
Definition 1.2 (Action Compatibility). Given two actions ϕi : Q → Aut(N ) of a group Q
on a group N —specified by giving, for each q ∈ Q, ϕi (q) as a permutation on the set N —decide
whether the actions are compatible, that is, whether there is an element of Aut(N ) × Aut(Q) whose
application to ϕ1 makes it equal to ϕ2 .
The cohomology class. Informally speaking, the simplest examples of extensions are when Q
can be “lifted” to a subgroup of G that is compatible with the isomorphism G/N ∼
= Q (the extension
is said to be split). However, it is possible to have an extension G of N by Q in which this cannot
happen. For example, consider the additive group of real numbers R, and its normal subgroup
2πZ. (There are similar examples in finite groups, but we believe this example has more intuitive
appeal. For readers familiar with group extensions, the goal here is to exhibit a nonsplit extension;
Z2  Z4 is a familiar example.) The quotient R/2πZ is isomorphic to the “circle group” S 1 of unit
complex numbers under multiplication, yet S 1 is not even a subgroup of R, let alone “liftable to
R.” Contrast with the group G = 2πZ × S 1 , which also has 2πZ  G and G/2πZ ∼
= S 1 , yet S 1 is
a subgroup of G. Note that as both R and G are abelian the conjugation action of R or G on any
normal subgroup is trivial. So the actions cannot explain the fact that S 1 is not a subgroup of R;
instead, it is group cohomology that exactly captures this phenomenon.
Specifically, if G is an extension of N by Q, the failure of Q to be “liftable” to G (a split
extension) is measured by a cohomology class as follows. Consider any function s : Q → G such
that s(q) is in the coset of N corresponding to q under the identification G/N ∼
= Q. Q is “liftable”
if and only if there is some such s which is also a group homomorphism. The failure of any given

7

s to be a homomorphism is measured by the function
fs (q, p) := s(q)s(p)s(qp)−1 .
Then s is a homomorphism if and only if fs (q, p) = 1 for all p, q ∈ Q. The cohomology class
corresponding to G, viewed as an extension of N by Q, is then the set {fs |s : Q → G as above}. Two
cohomology classes are isomorphic if they become equal after applying some element of Aut(N ) ×
Aut(Q), giving rise to the second problem:
Definition 1.3 (Cohomology Class Isomorphism). Given two functions fi : Q × Q → N as
above, decide whether there is an element α of Aut(N ) × Aut(Q) whose application to f1 makes
[f1α ] = [f2 ].
Towards a formal strategy. Let us now see how the action and cohomology class just introduced
can be used in isomorphism testing. We refer to the pair (θ, f ) of the corresponding action and (a
representative of) a cohomology class as the extension data of the extension. Suppose we are given
two groups G1 and G2 . We cleverly choose some N1  G1 and N2  G2 , and (somehow we are lucky
to find that) N1 ∼
= N2 and G1 /N1 ∼
= G2 /N2 . Viewing Gi as extensions of Ni by Gi /Ni , we extract
the action θi and cohomology classes fi , for i = 1, 2. If there is a simultaneous solution (one single
(α, β) ∈ Aut(N ) × Aut(G/N )) to Action Compatibility for θ1 , θ2 and Cohomology Class
Isomorphism for f1 , f2 , we say the extension data are pseudo-congruent.3
Definition 1.4 (Extension Data Pseudo-congruence). Given two extension data (θi , fi ) for
extensions of N by Q—that is, θi : Q → Aut(N ) and fi : Q × Q → N —decide whether they are
pseudo-congruent (see preceding paragraph).
If the extension data are pseudo-congruent, then G1 ∼
= G2 and we are done. However, it is
possible that G1 ∼
= G2 but the extension data are not pseudo-congruent (we thank Naik [Nai10] for
providing Example A.12). The difficulty is that G may contain two normal subgroups M, M 0  G
such that M ∼
= M 0 and G/M ∼
= G/M 0 , but no automorphism of G sends M to M 0 . To resolve
this problem, the Main Lemma 2.3 shows that it is enough to take N1 and N2 to be the center or
the radical, or more generally any characteristic subgroups that are preserved under isomorphisms.
(We note that in Besche and Eick [BE99], they get around the pitfall by introducing the related
concept of “strong isomorphism,” which is more natural for their purpose, namely the construction
of finite groups.)
Now we state the Main Lemma informally. Let us remark that, since in this section we mostly
discuss the case of abelian normal subgroups, the Main Lemma is presented in the abelian case here,
which is well-known (see e.g. [HEO05, Sec. 2.7.4]). We shall develop a general Main Lemma 3.7
(including the case of non-abelian normal subgroups) in Section 3.
Lemma (Main Lemma 2.3, abelian case, informal). Given two groups G1 and G2 , let Ai be the
abelian characteristic subgroup of Gi of a given type (e. g., the center), θi the action of Gi /Ai on
3

We take this terminology from Naik [Nai12], who gives a different definition of pseudo-congruence of extensions
that is more standard from the group-theoretic point of view, but less well-adapted to the computational setting. We
give the other definition and show that the two are formally equivalent in §A.4.1. Robinson [Rob96] uses the term
“isomorphism” for this notion; we prefer “pseudo-congruence” to avoid confusion with the several other notions of
isomorphism floating around. Theoretical investigations of some aspects of this concept can be found in Robinson
[Rob82, Sec. 4].

8

Ai , and fi the cohomology class of the extension of Ai by Gi /Ai given by Gi . Suppose A1 ∼
= A2
∼
(identified as A) and G1 /A1 = G2 /A2 (identified as Q).
Then G1 ∼
= G2 if and only if θ1 ≡ θ2 , and f1 ≡ f2 up to the action of Aut(A) × Aut(Q).
As evidence of the usefulness of the Main Lemma beyond this paper, we note that the polynomialtime algorithms for a special class of solvable groups in [LG09, QST11, BQ12] follow this strategy:
they use a theorem of Taunt [Tau55] to reduce isomorphism testing to a problem about linear
representations of finite groups (see Problem 1 in [QST11]), and solve that problem with additional
tactics. In retrospect, Taunt’s Theorem is a special case of the Main Lemma, and Problem 1 in
[QST11] is essentially Action Compatibility. Taunt’s Theorem applies regardless whether the
normal subgroup N is abelian or not, though the works [LG09, QST11, BQ12] only used the case
when N is abelian. The general Main Lemma 3.7 additionally covers and extends the nonabelian
case of Taunt’s Theorem.
Similarly, in retrospect the polynomial-time algorithm for semisimple groups [BCGQ11, BCQ12]
can be viewed as taking advantage of the nonabelian Main Lemma 3.7. We cover these examples
in more detail in Section 4.2.
Due to the structure of the group classes considered in [LG09, QST11, BQ12], Cohomology
Class Isomorphism does not appear in these works. On the other hand, for p-groups of class
2—currently believed the bottleneck—Cohomology Class Isomorphism is well-known to be
necessary (see Fact 4.3). We thus turn to study the Cohomology Class Isomorphism problem
in the following. As far as we know, this is the first time group cohomology has been used to get
worst-case bounds for GpI.
1.3.1

The general Main Lemma

As mentioned, the Main Lemma in the abelian case is well-known, and one contribution of this paper
is to extend it to the case when the normal subgroup can be non-abelian. The extension theory in
the non-abelian case is classical; a nice introduction can be found in Suzuki’s book [Suz82, Section
2.7]. In this paper, we shall adapt this theory explicitly to the setting of isomorphism testing. The
general strategy is the same as the abelian case, but several technical details need to be taken care
of. Consider the extension N ,→ G  Q where N need not be abelian. An obvious difference with
the abelian case is that the conjugation action of G on N no longer induces an action of Q on N ,
so one needs to consider the homomorphism Q → Aut(N )/Inn(N ) instead. As another example,
it is important to note is that the set of 2-cocycles is no longer a group, let alone an abelian group.
Due to all these complications, a careful treatment is needed for the formulation and the proof for
the general Main Lemma 3.7, and we refer the interested readers to Section 3.

1.4

Overview of our algorithms

Here we give an overview of the structure of our algorithms, as well as some of the more salient
details. We first consider the case when the solvable radical is abelian, to see how the strategy in
the above section is applied. We then focus on central-radical groups to outline some key steps in
the algorithms.
Given groups G1 , G2 , we first compute their solvable radicals Ai = Rad(Gi ) and the corresponding semisimple quotients Qi = Gi / Rad(Gi ). Then apply the algorithm from [Kav07] to A1 and
A2 , and the algorithm from [BCQ12] to Q1 and Q2 . If either of them returns non-isomorphic, then
G1 ∼
6 G2 . If both algorithms return isomorphic, they also yield isomorphisms. Thus, without loss
=
9

of generality, for i = 1, 2, we use A to denote Rad(Gi ) and Q to denote Gi / Rad(Gi ), identifying
Gi as an extension of A by Q.
Next, we compute the corresponding actions θ1 , θ2 and representatives f1 , f2 of the corresponding cohomology classes. As mentioned in Section 1.3, G1 and G2 are isomorphic if and only if
there is an element of Aut(A) × Aut(Q) which simultaneously turns θ1 into θ2 , and [f1 ] into [f2 ]
(as cohomology classes).
For groups with elementary abelian radicals (Theorem B = Corollaries 6.12 and 6.13)
Babai et al. [BCGQ11] showed that all automorphisms of a semisimple group can be enumerated
in time nO(log log n) . So if nO(log log n) time is allowed, we can use that algorithm to enumerate
(α,β)
all β ∈ Aut(Q). Then for each such β, search for some α ∈ Aut(A) such that θ1 = θ2 ,
(α,β)
and [f1 ] = [f2
]. When A ∼
= Zkp is elementary abelian, this task can be reduced to Module
Cyclicity Testing over finite-dimensional algebras, in almost the same way as the reduction
from Module Isomorphism to Module Cyclicity Testing [CIK97]. Here we only mention
that the algebra is U = {γ ∈ M (k, p) | ∀q ∈ Q, γθ2 (q) = θ2 (q)γ, and ∃a ∈ Zp , [γf2 ] = [af2 ]} and we
consider the U -module V = {α ∈ M (k, p) | ∀q ∈ Q, αθ1 (q) = θ2 (q)α, and ∃a ∈ Zp , [αf1 ] = [af2 ]}.
What is left is to verify that V is a cyclic U -module if and only if there exists some desired
α ∈ GL(k, p). See Section 6.2 for the details.
For general central-radical groups (Theorem A = Corollary 6.2). For groups with central
radicals, A = Z(Gi ), so the actions θi are trivial, and we only need to solve Cohomology Class
Isomorphism. As before, since nO(log log n) time is allowed, we can use the algorithm of Babai et
al. [BCGQ11] to enumerate all β ∈ Aut(Q). Then for each such β, we need to search for some
(α,β)
α ∈ Aut(A) such that [f1 ] = [f2
]. We solve this problem using linear algebra over abelian
groups, as follows. To ease the exposition let us assume A = Zkp . Then we shall view any map
f : Q × Q → A as a k × |Q|2 -size matrix over Zp , with Aut(A) acting on the rows, Aut(Q)
inducing an action on the columns. The main difficulty at this point has to do with identifying
which cohomology class f is in, in a way that is Aut(A)-invariant. Viewing f as a Zp -linear vector
(of dimension k × |Q|2 ), by Proposition 6.10 we can compute a projection π in this vector space
such that π(f ) identifies the cohomology class of f —that is, π(f ) = π(f 0 ) if and only if f and
f 0 are in the same cohomology class—and such that π commutes with every α ∈ Aut(A) (i. e.,
(id,β)
π is Aut(A)-invariant). With fixed β, this allows us to compute π(f1 ) and π(f2
), and then
2
determine whether, as k × |Q| -size matrices, their row spans are the same, which is a standard
task in linear algebra. For central-radical groups with elementary abelian radicals, this approach
allows us to compute the coset of isomorphisms. We also give an alternative proof (Section 6.1.1)
that allows us to decide isomorphism for general central-radical groups (where the radical need not
be elementary abelian), but the alternative approach does not yield the coset of isomorphisms.
For central-radical groups with G/ Rad(G)
a direct product of nonabelian simple groups
Q
(Theorem C=7.1). In this case Q = i∈[`] Ti , Ti nonabelian simple. To ease the exposition let
us assume Ti ’s are all mutually isomorphic to some T , and A = Zkp . For a function f : Q × Q → A,
a key fact is that the cohomology class of f is completely determined by the restrictions of f to the
direct factors Ti (Lemma 7.4). Several group-theoretic facts lead to this cohomological proposition,
including: (1) the direct product decomposition of Q into nonabelian simple factors is unique (not

10

just up to isomorphism); (2) if Ui is the preimage of Ti under the projection G → G/Z(G), then
ui uj = uj ui whenever ui ∈ Ui , uj ∈ Uj , and i 6= j ([Suz86, Chapter 6, Proposition 6.5], see
Proposition 7.3). Another useful fact is the well-known description of Aut(Q) as Aut(T ) o S` .
Instead of considering f : Q × Q → A, we can thus consider fi : Ti ×
PTi → A,2 i ∈ [`]; and
2
instead of working with a k × |Q| -size matrix, we can work with a k × ( i∈[`] |Ti | )-size matrix.
Q
P
2
This difference between |Q|2 = i∈[`] |Ti |2 and
i∈[`] |Ti | leads to major savings. When T is
a nonabelian simple group, we use the powerful theorem of Guralnick, Kantor, Kassabov, and
Lubotzky [GKKL07] (reproduced as Theorem 5.3 below); when T is more generally only centerless
and perfect, we restrict our attention to the setting where |T | = O(1). In either case, we combine
algorithms for Linear Code Equivalence and Coset Intersection. We need several technical
ingredients (including Lemma 7.5) to make the above procedure work though. As in the previous
setting, we give two proofs, one of which handles the general abelian case, and the other of which
allows us to compute the coset of isomorphisms in the elementary abelian case.

1.5

Organization of the paper

In Section 2 we collect basic concepts from extension theory. Appendix A contains a gentle introduction to extensions and cohomology, designed to be digestible without first preparing one’s
gut with half of a textbook. In Section 3 we prove our (nonabelian) Main Lemma. We develop
our strategy in Section 4, which uses the Main Lemma to expand the ideas in Section 1.3 into a
formal framework. Section 5 contains preliminaries and previous algorithmic results to prepare for
the algorithms for central-radical groups. In Section 6 we describe the nO(log log n) -time algorithm
for general central-radical groups (Theorem A=Corollary 6.2); this is also the algorithm for Corollary 6.3. We also give the algorithms for groups with elementary abelian radicals that need not be
central (Theorem B). In Section 7, we prove Theorem C, giving the polynomial-time algorithms for
central-radical groups with G/ Rad(G) a direct product of nonabelian simple groups (or centerless
perfect groups of constant size). Finally, Section 8 contains future directions, some of which are
motivated by the Cannon–Holt approach and the Babai–Beals filtration.
For any of our results which currently depend on an abelian group being elementary abelian,
we discuss what obstacles towards this generalization we know how to overcome, and which remain
to be overcome: see the end of Section 6.1.2, Section 7.4, and Section 8.

2

Preliminaries on abelian cohomology

The material in this section is standard group theory; for group theorists, this section serves
primarily to fix notation. For computer scientists, we provide a gentle introduction to this material,
with motivation and proofs, in Appendix A.
General notations. For n ∈ N, [n] = {1, . . . , n}. In this paper, all groups are finite. We use
id to denote the identity element, or the group of order 1. For a group G, |G| denotes the order
of G. We write H ≤ G if H is a subgroup of G. The (right) coset of H in G containing g ∈ G
is Hg = {hg | h ∈ H}. Given two groups G1 and G2 , Iso(G1 , G2 ) denotes the set of G1 → G2
isomorphisms. Aut(G) = Iso(G, G) is the group of automorphisms of G. The set Iso(G1 , G2 ) is
either empty or a coset of Aut(G1 ). For g ∈ G, conjugation by g is the automorphism θg : G → G
defined by θg (x) := gxg −1 . For g ∈ G, the maps θg are the inner automorphisms of G, and they
11

form a subgroup Inn(G) ≤ Aut(G). A subgroup N ≤ G is normal if it is invariant under all inner
automorphisms, and we write N  G. N ≤ G is a characteristic subgroup of G if it is invariant
under all automorphisms of G. Z(G) denotes the center of G. For K, L ≤ G, [K, L] denotes the
subgroup generated by all elements of the form [x, y] := xyx−1 y −1 , x ∈ K and y ∈ L. [G, G] is
called the commutator subgroup of G.
Group extension data. Given a finite group G and an abelian normal subgroup A  G, when
π
ι
we consider G as an extension of A by Q := G/A, we denote this by A ,→ G  Q, where ι
is an injective homomorphism and π a surjective homomorphism, such that Ker(π) = Im(ι). In
this paper, we mostly use the “inner” perspective, by identifying A with its image ι(A)  G. We
sometimes refer to G as the “total group” of the extension.
When A ≤ Z(G), the action of G on A by conjugation induces an action of Q on A by
conjugation, which is the action associated to the extension A ,→ G  Q.
As A is abelian, we write the group operation in A additively, despite the fact that when
considering general elements of G we write the group operation in G multiplicatively (this mixed
notation is fairly standard in this setting). Even though A is a subgroup of G, we tend to only use
these notations in separate contexts and it should not cause confusion.
Let π : G → G/A ∼
= Q be the natural projection; then any function s : Q → G such that
π(s(q)) = q for all q ∈ Q is called a section of π. Any such section s gives rise to a function
fs : Q × Q → A defined by fs (p, q) := s(p)s(q)s(pq)−1 (by applying π, it is readily verified that
the image of fs is in fact contained in A). We are free to choose s(1) = idG , and then fs (1, q) =
fs (q, 1) = 0 for all q ∈ Q. Such f are called normalized. In the following all sections are normalized
unless stated otherwise.
The fact that the group operation in G is associative implies that for all p, q, r ∈ Q,
fs (p, q) + fs (pq, r) = θp (fs (q, r)) + fs (p, qr)

(the 2-cocycle identity).

Any function f : Q × Q → A is called a 2-cochain; any 2-cochain satisfying the 2-cocycle identity
with respect to θ is a 2-cocycle (with respect to θ). Given any homomorphism θ : Q → Aut(A),
every 2-cocycle with respect to θ arises as fs for some section s of some extension A ,→ G  Q
with action θ.
Given a function u : Q → A, the 2-coboundary associated to u is the function bu : Q × Q → A
defined by bu (p, q) := u(p) + θp (u(q)) − u(pq). Any two 2-cocycles associated to the same extension
differ by a coboundary.
The 2-cochains form an abelian group C 2 (Q, A) defined by pointwise addition: (f + g)(p, q) :=
f (p, q) + g(p, q). It is readily visible that the 2-cocycle identity is Z-linear, and hence the 2-cocycles
form a subgroup of the 2-cochains, denoted by Z 2 (Q, A, θ). It is similarly verified that the 2coboundaries form a subgroup of the 2-cocycles, denoted B 2 (Q, A, θ).
A 2-cohomology class is a coset of B 2 (Q, A, θ) in Z 2 (Q, A, θ), and any element of this coset is a
representative of the cohomology class. If f ∈ Z 2 (Q, A, θ), we denote the corresponding cohomology
class by [f ]. The group of 2-cohomology classes is denoted H 2 (Q, A, θ) := Z 2 (Q, A, θ)/B 2 (Q, A, θ).
By the above discussion, each extension A ,→ G  Q determines a single cohomology class [f ] ∈
H 2 (Q, A, θ).
We thus arrive at one of the central notions in this paper:
Definition 2.1. For A an abelian group and Q any group, a pair (θ, f ) of an action θ : Q → Aut(A)
and a 2-cocycle f : Q × Q → A, f ∈ Z 2 (Q, A, θ) is extension data. Two extension data for the pair
12

(Q, A) are equivalent if they have the exact same action and if the two 2-cocycles are cohomologous
(differ by a coboundary).
Given an extension A ,→ G  Q, the extension data associated to this extension are the action
θ as defined above, and any 2-cocycle fs for any section s : Q → G. Note that extension data
are non-unique, as we may choose any representative of the corresponding 2-cohomology class.
Furthermore, if the action is trivial then this extension is called central. If the 2-cohomology class
is trivial then this extension is called split; in this case G is a semi-direct product of A by P for
some subgroup P .

2.1

Pseudo-congruent extensions versus isomorphic total groups

Recall that a characteristic subgroup is a subgroup invariant under all automorphisms. The analogous notion for isomorphisms (rather than automorphisms) is a function S that assigns to each
group G a subgroup S(G) ≤ G such that any isomorphism ϕ : G1 → G2 restricts to an isomorphism
ϕ|S(G1 ) : S(G1 ) → S(G2 ). We call such a function a characteristic subgroup function. Note that if
G1 = G2 , this says that S(G1 ) is sent to itself by every automorphism of G1 , that is, S(G1 ) is a
characteristic subgroup of G1 . Most natural characteristic subgroups encountered are characteristic
subgroup functions, for example the center Z(G), the commutator subgroup [G, G], or the radical
Rad(G).
Definition 2.2. Let A be an abelian group and Q any group, and let (θ1 , f1 ) and (θ2 , f2 ) be
two extension data for A-by-Q. Then the extension data are pseudo-congruent 4 if there exists
(α, β) ∈ Aut(A) × Aut(Q), such that
(α,β)

θ1 (q)(a) = α−1 (θ2 (β(q))(α(a))) =: θ2

(q)(a),

(1)

for all q ∈ Q, a ∈ A, and
f1 (p, q) = α−1 (f2 (β(p), β(q))) + bu (p, q)

(2)

for all p, q ∈ Q, and for some 2-coboundary bu . In this case we write (θ1 , f1 ) ∼
= (θ2 , f2 ).
Lemma 2.3 (See, e. g., [HEO05, Sec. 2.7.4]). Let S be a characteristic subgroup function. Given
two finite groups G1 and G2 , suppose S(G1 ) and S(G2 ) are abelian. Then G1 ∼
= G2 if and only if
both of the following conditions hold:
1. S(G1 ) ∼
= S(G2 ) (which we denote by A) and G1 /S(G1 ) ∼
= G2 /S(G2 ) (which we denote by Q);
2. (θ1 , f1 ) ∼
= (θ2 , f2 ), where (θi , fi ) is the extension data of the extensions A ,→ Gi  Q.
For a detailed proof that doesn’t require reading half a textbook on group theory first, see
Appendix A. In the next section we generalize this to the case where the normal subgroup need
not be abelian.
4

See Footnote 3 on page 8.

13

3

Nonabelian cohomology and its applications

Here we consider extensions N ,→ G  Q where N need not be abelian, i. e., the general case.
We show that Lemma 2.3 extends to the case when N comes from a characteristic subgroup
function—not necessarily abelian—showing the usefulness of the extension theory perspective in
its full generality. The results of this section may be of independent interest and of further use in
the future, but in this paper will only be needed for the applications in this section and the next
(namely, to show how the results of [BCQ12] can be viewed in the same cohomological light as
Lemma 2.3, and to reduce the case where G acts by inner automorphisms on its radical to natural
sub-problems). Suzuki’s book [Suz82, Section 2.7] contains a nice introduction to the extension
theory in the nonabelian case, while our contribution here is to adapt this theory explicitly to
the setting of isomorphism testing. While some of the basics here are already laid out in Suzuki
[Suz82]—so the first part of this section can be viewed as a review to fix notation—here we consider
how the extension theory with nonabelian kernels can be used to understand isomorphism of the
total groups, which was only considered in a very special case there (reproduced as Theorem 3.15
below).
The action. The first difference to notice when N is non-abelian is that the conjugation map
θ0 : G → Aut(N ), defined by θ0 (g) = cg where cg (n) = gng −1 , no longer contains N in its kernel,
and hence no longer descends to a map Q → Aut(N ). However, the action of N on itself by
conjugation is by inner automorphisms (by definition) so that we do get a well-defined map G/N →
Aut(N )/Inn(N ), that is, Q → Out(N ). For ease of reference, we give a name to such maps:
Definition 3.1. An outer action of a group Q on a group N is a group homomorphism Q →
Out(N ) = Aut(N )/Inn(N ).
In computations, rather than represent an outer automorphism as a coset of Inn(N ) in Aut(N ),
we simply give it by a representative automorphism, and must remember when we may need to
multiply by an arbitrary element of Inn(N ). Throughout this section we use T to denote an action
rather than θ, to remind the reader that the essential object here is the outer action represented
by T , despite the fact that we work directly with actions T : Q → Aut(N ).
Correspondingly, in the setting of general N , the problem Action Compatibility must
be generalized to Outer Action Compatibility, which is defined as follows. Two actions
T1 , T2 : Q → Aut(N ) are said to be “outer equivalent” if there is a function t0 : Q → Inn(N )
and an automorphism α ∈ Aut(N ) such that T1 (q) = α−1 ◦ t0 (q) ◦ T2 (q) ◦ α for all q ∈ Q.
Definition 3.2 (Outer Action Compatibility). Given two actions T1 , T2 : Q → Aut(N ), decide
whether there an element β ∈ Aut(Q) such that T1 and T2 ◦ β are outer equivalent, that is, whether
there exists (β, α, t0 ) ∈ Aut(Q) × (Aut(N ) n Inn(N )Q ) such that T1 (q) = α−1 ◦ t0 (β(q)) ◦ T2 (β(q)) ◦ α
for all q ∈ Q.
Although this formulation of Outer Action Compatibility is more complicated than if we
had represented an outer automorphism as a full coset θInn(N ), it will be useful when we formulate
Extension Data Pseudo-congruence below.
Note that when N is abelian there are no inner automorphisms, so Out(N ) = Aut(N ), the
only choice for t0 above is trivial, and Outer Action Compatibility then becomes Action
Compatibility.
14

Remark 3.3. We note that, unlike the case of N abelian, when N is nonabelian it is possible that
some outer actions θ : Q → Out(N ) may not be induced by any extension of N by Q. When there
is such an extension, the outer action θ is called extendable. Eilenberg and Mac Lane [EM47b,
Sec. 7–9] characterize which outer actions are extendable in terms of the third cohomology group
H 3 (Q, Z(N )). As our interest is primarily in GpI, whenever it matters (e. g., in the definition of
Outer Action Compatibility) we happily restrict our attention to extendable outer actions.
The characterization in terms of cohomology with coefficients in Z(N ) allows one to use linear
algebra over the abelian group Z(N ) to test in polynomial time whether a given outer action
is extendable. In particular, the outer action is extendable if and only if an associated third
cohomology class vanishes, i. e., is a 3-coboundary. A basis for B 3 (Q, Z(N )) can be computed
analogously to that in Proposition 6.5, by enumerating over a natural basis of the 2-cochains
C 2 (Q, Z(N )) (which has dimension |Q|2 ) and applying the coboundary operator. Then we just
have to compute the 3-cocycle corresponding to the given outer action, and check that it lies in the
linear subspace spanned by (subgroup generated by) the 3-coboundaries. Note that we may treat
3-cochains as k × |Q|3 matrices, analogous to how we treat 2-cochains.
The cohomology class. As in the case of N abelian, when N is nonabelian, one may still choose
a set-theoretic section s : Q → G and get a 2-cocycle fs : Q × Q → N . This section s gives an action
(not just outer action) Ts : Q → Aut(N ) by conjugation, namely Ts (q)(n) = s(q)ns(q)−1 . Starting
from associativity in G, one may then work out, as in the abelian case, the 2-cocycle condition:
fs (q1 , q2 )fs (q1 q2 , q3 ) = Ts (q1 )(fs (q2 , q3 ))fs (q1 , q2 q3 )

(the nonabelian 2-cocycle identity).

However, this condition depends not just on the action Ts and the 2-cochain fs , but also on some
relationship between Ts and fs (in this case, that they come from the same section s). We would
much prefer a condition that does not depend on the ambient extension group G. To get this
condition, note that the action satisfies Ts (q1 )Ts (q2 ) = cfs (q1 ,q2 ) Ts (q1 q2 ), where cn : N → N denotes
the inner automorphism given by conjugation by n ∈ N : cn (m) = nmn−1 . This leads us to the
definition of extension data for general N :
Definition 3.4 (Extension data for general Q, N ). Let Q and N be groups. We say that a pair
(T, f ) of an action T : Q → Aut(N ) and a function f : Q × Q → N is extension data if, for all
qi ∈ Q,
T (q1 )T (q2 ) = cf (q1 ,q2 ) T (q1 q2 )
(3)
and
f (q1 , q2 )f (q1 q2 , q3 ) = T (q1 ) (f (q2 , q3 )) f (q1 , q2 q3 ).

(4)

In this case, we refer to f as a 2-cocycle with respect to the action T .
Note that condition (3) very nearly determines f : it determines f (q1 , q2 ) up to an element of
Z(N ). In particular, when Z(N ) = 1 condition (3) actually does determine f completely, a fact we
will take advantage of when discussing the polynomial-time algorithm for groups with no abelian
normal subgroups [BCQ12] (see also Theorem 3.15).
Another difference in the case of N nonabelian is that, although we might denote the set of
2-cocycles by Z 2 (Q, N, T ), this set will not in general be a group in any natural way, let alone an
abelian group. (Also note that it depends on the action T , whereas we know that the action is not
intrinsic to the extension but only the corresponding outer action is.) However, the quotient of two
15

2-cocycles with respect to the same action T will land in the center Z(N ), allowing us to reduce part
of the question back to the case of N abelian. To see this, let f1 , f2 be two 2-cocycles with respect
to an action T : Q → Aut(N ), and consider conjugating by their quotient f1 (q1 , q2 )f2 (q1 , q2 )−1 :
cf1 (q1 ,q2 )f2 (q1 ,q2 )−1 = T (q1 )T (q2 )T (q1 q2 )−1 T (q1 q2 )T (q2 )−1 T (q1 ) = idN .
As the center Z(N ) consists exactly of those n ∈ N such that cn = idN , we find that the quotient
f1 (q1 , q2 )f2 (q1 , q2 )−1 lies in Z(N ). So although there isn’t really a cohomology group “H 2 (Q, N, T ),”
we can often nonetheless reduce to questions about cohomology classes in H 2 (Q, Z(N ), T |Z(N ) ).
Everything up to this point in this section has been classical (although it has not been leveraged
much for algorithms).
Equivalence. As in the case of N abelian, two extensions N ,→ Gi  Q are said to be equivalent
if there is an isomorphism γ : G1 → G2 such that γ induces the identity map on both N and Q.
However, since Z 2 (Q, N, T ) is no longer a group and B 2 (Q, N, T ) no longer its subgroup, the notion
of equivalent extensions doesn’t translate so easily to a notion of equivalence for extension data.
Hence we derive this condition more or less from scratch. That is, we derive what it means for
two extension data to be equivalent by analyzing how two extension data coming from the same
extension may differ, when a different choice of section s : Q → G is made.
Fix an extension N ,→ G  Q and two sections s1 , s2 : Q → G. Let t(q) := s1 (q)s2 (q)−1 ; as
the si are both sections, s1 (q) and s2 (q) are in the same coset of N , so that t(q) ∈ N for all q ∈ Q.
Then the actions T1 = θs1 and T2 = θs2 differ by the inner automorphism ct(q) : T1 (q) = ct(q) ◦ T2 (q).
Recall that we set fi (q, r) := si (q)si (r)si (qr)−1 for q, r ∈ Q. Then we have that
f1 (q, r) = s1 (q)s1 (r)s1 (qr)−1
= t(q)s2 (q)t(r)s2 (r)s2 (qr)−1 t(qr)−1
= t(q)T2 (q)(t(r))s2 (q)s2 (r)s2 (qr)−1 t(qr)−1
= t(q)T2 (q)(t(r))f2 (q, r)t(qr)−1
= t(q)T2 (q)(t(r))cf2 (q,r) (t(qr)−1 )f2 (q, r) =: f2t,T2 (q, r)
For future reference, we denote this final expression by f2t,T2 (q, r).
Definition 3.5. Two extension data (Ti , fi ) are equivalent if there is a map t : Q → N such that
T1 (q) = ct(q) ◦ T2 (q) for all q ∈ Q, and f1 = f2t,T2 .
There are several aspects of this definition to take note of:
• By definition, two extension data can be equivalent only if T1 (q) and T2 (q) represent the same
outer automorphism of N , in accord with our discussion above.
• When N is abelian, this definition agrees with the previous definition of equivalent extensions.
For, in this case, ct(q) = idN and the condition f1 = f2t,T2 exactly says that f1 and f2 differ
by the 2-coboundary bt defined by t.
• T1 = T2 if and only if s1 (q) and s2 (q) differ by an element of the center Z(N ), that is, t is a
map Q → Z(N ). In this case, let T = T1 = T2 ; then (T, f1 ) and (T, f2 ) are equivalent if and
only if f1 and f2 differ by the coboundary bt ∈ B 2 (Q, Z(N ), T ). Again, this will be relevant
for our discussion below of the polynomial-time algorithm for semisimple groups [BCQ12].
16

Pseudo-congruence. As before, pseudo-congruence is defined as “equivalence up to the action
of Aut(N ) × Aut(Q):”
Definition 3.6 (Pseudo-congruence of extension data for general Q, N ). Let Q and N be two
groups. Two extension data (Ti , fi ) ∈ (Q → Aut(N ), Q × Q → N ) are pseudo-congruent if there
(α,β) (α,β)
exist (α, β) ∈ Aut(N ) × Aut(Q) such that (T1 , f1 ) and (T2
, f2
) are equivalent.
In more detail, the extension data are pseudo-congruent if there exists (α, β) ∈ Aut(N )×Aut(Q)
and t : Q → N such that, for all q ∈ Q and all n ∈ N :

and

T1 (q)(n) = (α−1 ◦ ct(β(q)) ◦ T2 (β(q)) ◦ α)(n)

(5)

h
i
(α,β,t,T2 )
f1 (q1 , q2 ) = α−1 f2t,T2 (β(q1 ), β(q2 )) =: f2
(q1 , q2 ).

(6)

The problem Extension Data Pseudo-congruence is to decide, given two extension data
(Ti , fi ), whether they are pseudo-congruent.
Lemma 3.7 (Main Lemma5 ). Let S be a characteristic subgroup function. Given two finite (or
Lie, see Remark 3.8) groups G1 and G2 , G1 ∼
= G2 if and only if both of the following conditions
hold:
1. S(G1 ) ∼
= S(G2 ) (which we denote by N ) and G1 /S(G1 ) ∼
= G2 /S(G2 ) (which we denote by
Q);
2. (T1 , f1 ) ∼
= (T2 , f2 ), where (Ti , fi ) is the extension data of the extensions N ,→ Gi  Q.
Proof. First suppose that γ : G1 → G2 is an isomorphism. Since S is a characteristic subgroup
function, γ restricts to an isomorphism between the copy S(G1 ) of N in G1 and the copy S(G2 )
of N in G2 , i. e., an automorphism α ∈ Aut(N ). Consequently, γ induces an automorphism
β := γ ∈ Aut(Q). After twisting by these automorphisms, the discussion preceding Definition 3.5
shows that the extension data become equivalent.
Conversely, suppose (T1 , f1 ) ∼
= (T2 , f2 ), via (α, β, t) ∈ Aut(N ) × Aut(Q) × (Q → N ). As in
the abelian case we have a standard reconstruction procedure; we construct groups Hi from (Ti , fi )
such that Hi ∼
= Gi , and then we show how the pseudo-congruence of the extension data easily yields
an isomorphism H1 ∼
= H2 .
The underlying set of Hi will be N × Q, with multiplication defined by
(n, p) ◦Hi (m, q) = (n · Ti (p)(m) · fi (p, q), pq).
Note that this is the same as in the abelian case, just being careful about the order. Here we have
started using dots “·” to denote multiplication, as the expressions below get somewhat complicated
and this helps to keep things clear. Let si : Q → Gi denote the sections used to construct the
5

Although the statement of the Main Lemma may not surprise experts, and follows from standard constructions
in group cohomology, we have been unable to find a reference for it, and it seems not widely-known even amongst
mathematicians, despite the abelian case being very well-known. As an example of our Main Lemma not being
well-known, we point out that the main theorem of a 2003 paper [Häm03] in L’Enseignment Mathématique, whose
proof takes approximately 7 pages there even assuming knowledge of group cohomology, is a short corollary of our
Main Lemma, as shown in Remark 3.8. In that paper, it is even asked whether there are larger classes of groups for
which its main theorem holds [Häm03, Remark 4.2]; our Main Lemma gives quite a general answer to this question.

17

extension data (Ti , fi ). Then it is readily verified that the map (n, q) 7→ nsi (q) gives an isomorphism
∼
=
Hi → Gi .
Finally, we claim that the map ϕ(n, p) := (α(n) · t(β(p)), β(p)) is an isomorphism from H1 to
H2 . The main fact to check is that this is even a homomorphism. Consider (n, p) and (m, q) ∈ H1 .
On the one hand, we have
ϕ((n, p) ◦H1 (m, q)) = ϕ(n · T1 (p)(m) · f1 (p, q), pq)
= (α(n · T1 (p)(m) · f1 (p, q)) · t(β(pq)), β(pq))
= (α(n) · α(T1 (p)(m)) · α(f1 (p, q)) · t(β(pq)), β(pq))
On the other hand, we have (here we’ll sometimes use square brackets [] to denote application of
an automorphism to help keep all the parentheses straight):
ϕ(n, p) ◦H2 ϕ(m, q) = (α(n) · t(β(p)), β(p)) ◦H2 (α(m) · t(β(q)), β(q))
= (α(n) · t(β(p)) · T2 (β(p)) [α(m) · t(β(q))] · f2 (β(p), β(q)), β(p)β(q))
= (α(n) · t(β(p)) · T2 (β(p))[α(m)] · T2 (β(p))[t(β(q))] · f2 (β(p), β(q)), β(pq))
= (α(n) · (ct(β(p)) ◦ T2 (β(p)))[α(m)] · t(β(p)) · T2 (β(p))[t(β(q))] · f2 (β(p), β(q)),
β(pq))
Let’s work through these two expressions bit by bit. We can dispense easily with the second
coordinate, as β(pq) = β(p)β(q) since β ∈ Aut(Q). Both of the first coordinates begin with α(n).
Next we have α(T1 (p)(m)) on the one hand and (ct(β(p)) ◦ T2 (β(p)))[α(m)] on the other. From the
definition of pseudo-congruence, we have that T1 (p)(m) = α−1 (ct(β(p) ◦ T2 (β(p)))[α(m)]. Applying
α to both sides of this equation we see that these two terms are equal.
The remainder of the first coordinate is then α(f1 (p, q)) · t(β(pq)) in the first case. From the
definition of pseudo-congruence we have:
α(f1 (p, q))t(β(pq)) = f2t,T2 (β(p), β(q)) · t(β(pq))
= t(β(p)) · T2 (β(p))[t(β(q))] · f2 (β(p), β(q)) · t(β(pq))−1 · t(β(pq))
= t(β(p)) · T2 (β(p))[t(β(q))] · f2 (β(p), β(q)),
which is exactly the remainder of the first coordinate in the second case, as desired. Hence ϕ is a
homomorphism.
Finally, it suffices to show that ϕ is injective, for as |H1 | = |N ||Q| = |H2 |, it will then follow
that ϕ is bijective and hence an isomorphism. Consider the kernel of ϕ: ϕ(n, p) = (1, 1). As the
second coordinate is 1, we have β(p) = 1 and hence p = 1. As the first coordinate is 1, we have
α(n)t(β(p)) = α(n) = 1, so we also have n = 1. (In the first equality we use the fact that t(1) = 1,
which follows from Ti (1Q ) = idN .) Hence ϕ is injective, and thus an isomorphism.
Remark 3.8 (The Main Lemma for Lie groups). Lemma 3.7 also extends to the case of Lie groups,
allowing us to show that the main theorem of Hämmerli [Häm03] follows from our Main Lemma
as a quick corollary, as well as giving a very general answer to a question he posed. The main
theorem of Hämmerli [Häm03] is essentially the special case of our Main Lemma in which the
characteristic subgroup is taken to be the connected component of the identity. Hämmerli asked
[Häm03, Remark 4.2] whether his main theorem extended to other classes of groups; our Main
Lemma extends it greatly, and shows that the result has very little to do with Lie groups per se.
18

To see that our Main Lemma extends to Lie groups, note that the only place we used finiteness
in the proof of the Main Lemma 3.7 is in the final paragraph, to get surjectivity from injectivity. In
the case of Lie groups, we also note that the map in the above proof is continuously differentiable
(even smooth). The rest of the argument is essentially dimension-counting, but we give it here
for completeness. First, because the homomorphism is differentiable, it descends to a map of Lie
algebras, and injectivity of the map implies injectivity of the corresponding map of Lie algebras. As
the Lie algebras are, in particular, finite-dimensional vector spaces of the same dimension, injectivity
and linearity imply surjectivity, so we have an isomorphism of Lie algebras. For a Lie group G,
let G(0) denote the connected component of the identity of G. Continuity of the homomorphism
and the fact that it induces an isomorphism of Lie algebras implies that it induces an isomorphism
(0)
(0)
of H1 ∼
= H2 . As G/G(0) is a finite group for any Lie group G, injectivity and continuity
(0)
(0)
together imply that we have an isomorphism of the component groups H1 /H1 ∼
= H2 /H2 . As the
map we started with was an injective homomorphism that induces an isomorphism of the identity
components and of the component groups, it is an isomorphism.


3.1

Application to extensions with trivial outer action

We did not define Cohomology Class Isomorphism for general N and then proceed to pseudocongruence, as in the abelian case, because it turns out that when the outer action is trivial,
Cohomology Class Isomorphism for action-trivial extensions of N by Q reduces to Cohomology Class Isomorphism for extensions of Z(N ) by Q. To prove this we use one additional
concept, that of a central product. Although this notion generalizes to an arbitrary number of
factors, we only need the two-factor case:
Definition 3.9 (Central decomposition; see, e. g., [Wil09a]). A pair {G1 , G2 } of subgroups of a
finite group G is a central decomposition of G if G is generated by G1 and G2 (G = hG1 , G2 i) and
G1 and G2 commute ([G1 , G2 ] = 1).
π

Lemma 3.10. Let N ,→ G  Q be an extension of N by Q which induces the trivial outer action
θ(q) = idN Inn(N ) for all q ∈ Q. Then there is a subgroup H of G such that H ∩ N = Z(N ),
π(H) = Q, and {N, H} is a central decomposition of G. We denote this subgroup H by G|Z(N ) .
Proof. There is a section s : Q → G such that cs(q) = idN for all q ∈ Q. Let f (p, q) = fs (p, q) =
s(p)s(q)s(pq)−1 be the 2-cocycle corresponding to s. As cs(q) = idN for all q ∈ Q, we also have
that cf (p,q) = idN for all p, q ∈ Q. As f (p, q) ∈ N , this implies that f (p, q) ∈ Z(N ). Hence f is a
2-cocycle in H 2 (Q, Z(N )) (for the trivial action of Q on Z(N )). Let H be the subgroup generated
by Z(N ) and s(Q). Since f (p, q) ∈ Z(N ) for all p, q ∈ Q, it follows that every element of H can be
represented uniquely in the form zs(q) for z ∈ Z(N ), q ∈ Q.
From the uniqueness of the representation zs(q), it follows immediately that H ∩ N = Z(N ).
Since H included s(q) for all q ∈ Q, it follows that π(H) = Q. Finally, to see that [H, N ] = 1,
consider zs(q)n(zs(q))−1 n−1 = zs(q)ns(q)−1 z −1 n−1 . Since cs(q) = idN , this equals znz −1 n−1 , but
since z ∈ Z(N ), the latter is trivial.
The preceding lemma nearly allows us to reduce group isomorphism when the outer action of
G on Rad(G) is trivial to isomorphism of a pair of central radical groups and a pair of solvable
groups. However, up to this point we have brushed over the fact that central products are not
uniquely determined by their factors. In a central decomposition {G1 , G2 }, as in a direct product
19

decomposition, it is true that both Gi are normal subgroups. Unlike a direct decomposition,
however, G1 ∩ G2 need not be trivial. To make the discussion a little clearer, we introduce a
standard alternative viewpoint on central decompositions:
Definition 3.11 (Central product; see, e. g., [Asc00, (11.1)]). Given two groups H1 , H2 and an
isomorphism ϕ : Y1 → Y2 between two subgroups Yi ≤ Z(Hi ) of their centers, the quotient of
H1 × H2 by {(y −1 , ϕ(y)) : y ∈ Y1 } is the central product of H1 and H2 along ϕ, denoted H1 ×ϕ H2 .
Central products and central decompositions are essentially equivalent. More specifically, if
{G1 , G2 } is a central decomposition of G, then if we let Yi = G1 ∩ G2 ≤ Gi for i = 1, 2, and define
ϕ : Y1 → Y2 to be the map induced by the identity map on G1 ∩ G2 (thinking of both G1 and G2
as subgroups of G), then we see that G is the central product of G1 and G2 along ϕ. Conversely, if
H = H1 ×ϕ H2 is a central product, then every element of H can be written (not uniquely!) as the
equivalence class of (h1 , h2 ) in the quotient H1 ×ϕ H2 , for some h1 ∈ H1 , h2 ∈ H2 . Let us denote
this equivalence class by (h1 , h2 ). Then it is readily verified that G1 = {(h1 , 1) : h1 ∈ H1 } is a
subgroup of H isomorphic to H1 , that G2 = {(1, h2 ) : h2 ∈ H2 } is a subgroup of H isomorphic to
H2 , and that {G1 , G2 } is a central decomposition of H.
When dealing with isomorphisms between central products, the fact that G1 ∩ G2 is nontrivial
becomes a source of difficulty, as in the following lemma. Although this lemma applies in a more
general situation, we state it for the situation we are most interested in.
Lemma 3.12. Let A be a solvable group and B a central-radical group. Suppose that ϕ1 , ϕ2 are
two isomorphisms Z(A) → Z(B). Then A ×ϕ1 B is isomorphic to A ×ϕ2 B if and only if there are
automorphisms α ∈ Aut(A) and β ∈ Aut(B) such that ϕ1 = β −1 ◦ ϕ2 ◦ α.
Proof. Let Gi denote A ×ϕi B, and let Zi denote the copy of Z(A) ∼
= Z(B) in Gi for i = 1, 2. Every
element of Gi can be written—not necessarily uniquely—as ab with A ∈ A and b ∈ B; ab = 1 in
Gi if and only if a ∈ Z(A), b ∈ Z(B), and ϕi (a) = b−1 .
First, suppose there are α ∈ Aut(A) and β ∈ Aut(B) such that ϕ1 = β −1 ◦ ϕ2 ◦ α. Then we
claim that the map sending ab ∈ G1 to α(a)β(b) ∈ G2 is both well-defined and an isomorphism. To
see that it is well-defined note that if ab = 1 in G1 , then ϕ1 (a) = b−1 ∈ Z(G1 ). By assumption, we
then have β −1 (ϕ2 (α(a))) = b−1 , or equivalently ϕ2 (α(a)) = β(b)−1 , which means that α(a)β(b) = 1
in G2 . From this, one concludes that if ab = a0 b0 then α(a)β(b) = α(a0 )β(b0 ); it is then easily verified
that this map is in fact a homomorphism. Since these are finite groups, injectivity then suffices to
show it is an isomorphism; injectivity follows using the preceding argument run in reverse.
For the reverse direction, we will need to use the following fact. Let πi : A × B → A ×ϕi B
be the natural quotient map. Then we claim that πi (1 × Z(B)) = Z(Gi ). It is easy to see that
πi (1 × Z(B)) ≤ Z(Gi ). For the reverse inclusion, suppose z ∈ Z(Gi ). Then z must commute
with both πi (1 × B), and since πi maps 1 × B isomorphically onto its image, this means that
z ∈ πi (1 × Z(B)).
Now, suppose there is an isomorphism γ : G1 → G2 . Note that, as A is a solvable normal
subgroup of Gi and Gi /A ∼
= B/Z(B) is semisimple, A must be equal to Rad(Gi ). In particular, since
the radical is a characteristic subgroup function, γ(A) = A and thus α := γ|A is an automorphism
of A.
Next we show that γ sends B to B, thus inducing an automorphism of B. Note that Gi /Z(Gi ) ∼
=
(A/Z(A)) × (B/Z(B)). Since the center is a characteristic subgroup function, γ induces an isomorphism G1 /Z(G1 ) → G2 /Z(G2 ), that is, an automorphism of (A/Z(A)) × (B/Z(B)). Since A
20

is solvable and B/Z(B) is semisimple, γ thus induces an automorphism of B/Z(B) as well. Since
γ(Z(B)) = γ(Z(G1 )) = Z(G2 ) = Z(B) ≤ B, by a counting argument γ must send B to B. Thus γ
induces β ∈ Aut(B).
Thus, by construction, for a ∈ A and b ∈ B, γ(a) = α(a) and γ(b) = β(b). Since γ is
a homomorphism, it follows that γ(ab) = α(a)β(b) for all a ∈ A and all b ∈ B. To see that
ϕ1 = β −1 ◦ ϕ2 ◦ α, one uses the same calculation as in the first direction.
The Central Amalgam Problem is: given two automorphisms ϕi ∈ Aut(Z), i = 1, 2, of an
abelian group Z, two black-box groups G, H (think of these as Aut(A) and Aut(B) in the preceding
lemma), and actions of G and H on Z—given by specifying the matrix actions of generating sets
of G and H—decide whether there exists α ∈ G and β ∈ H such that ϕ1 = β −1 ◦ ϕ2 ◦ α.
Proposition 3.13. Let S be a polynomial-time computable characteristic subgroup function. Suppose that G1 , G2 are two groups for which the induced outer action of Gi /S(Gi ) on S(Gi ) by
conjugation is trivial (equivalently: the induced action is by inner automorphisms of S(Gi )). Then
the group isomorphism problem for (G1 , G2 ) reduces in polynomial time to finding a generating set
for Aut(S(Gi )) and Aut(Gi |Z(S(Gi )) ) and solving the Central Amalgam Problem.
In particular, group isomorphism for groups for which the outer action of G/ Rad(G) on Rad(G)
is trivial reduces in nO(log log n) -time to finding generating sets of the automorphism group of solvable
groups and solving the Central Amalgam Problem.
Remark 3.14. When |Aut(Z(Rad(G))| is bounded by poly(|G|), the Central Amalgam Problem can be solved in poly(|G|) time by standard permutation group algorithms. Note that the
class of solvable groups S whose centers have automorphisms groups of polynomial size may seem
restrictive, but is in fact quite rich. In particular, it includes solvable groups whose centers are
abelian groups with arbitrarily many factors, as long as each prime appears in a bounded number
of factors, and also includes all centerless solvable groups (itself quite a nontrivial class of groups).
Proof. We show how to construct a central decomposition as in Lemma 3.10 in polynomial time.
Let N = S(G) and Q = G/N . By assumption, the subset N = S(G) can be identified in poly(|G|)
time. Next, choose any section s : Q → G. It may be that some s(q) acts non-trivially on N via
conjugation. However, by the assumption that the outer action is trivial, cs(q) must be some inner
automorphism of N , say cn(q) for some n(q) ∈ N . To find this n(q), we may search through N
exhaustively in at most O(|N |2 ) ≤ O(|G|2 ) time: essentially |N | steps to check the action of a given
n on N by conjugation, and there are |N | possible n’s to check. Then let s0 (q) = s(q)n(q)−1 ; as
n(q) ∈ N , s0 is another section, and by construction cs0 (q) = idN for all N . Finally, let f (p, q) =
s0 (p)s0 (q)s0 (pq)−1 . Computing all the values of f takes essentially O(|Q|2 ) ≤ O(|G|2 ) time, and then
we construct G|Z(S(G)) as the subgroup of G generated by s(Q) and Z(N ) in poly(|G|) time.
Extensions of centerless groups. We have already mentioned a few useful properties of extensions of centerless groups, that is, when Z(N ) = 1. One that is implicit in what we have already
said is that every outer action Q → Out(N ) is extendable, that is, it is induced from some extension
of N by Q. These properties culminate in the following very useful theorem:
Theorem 3.15 (see, e. g., [Suz82, Thm. 2.7.11]). Let N be a centerless group, Q any group, and
G an extension of N by Q. Then G is determined up to isomorphism by the induced outer action
of Q on N .
21

Furthermore, every such extension is equivalent to a subgroup Γ ≤ Q × Aut(N ) satisfying
Γ ∩ Aut(N ) = Inn(N ) and πQ (Γ) = Q, where πQ : Q × Aut(N ) → Q is the projection onto the first
factor.
In particular, if S is a characteristic subgroup function computable in polynomial time, and C
is a class of groups for which S(G) is centerless for every G ∈ C, then isomorphism of groups in
C reduces to isomorphism of groups of the type G/S(G) for G ∈ C, groups of the type S(G) for
G ∈ C, and Outer Action Compatibility.

4

The strategy

Suppose we are given two groups G1 and G2 from some class of groups C. Our Main Lemma 3.7
suggests (and indeed was motivated by) a divide-and-conquer strategy to test isomorphism (Section 4.1). This strategy highlights important structural features of GpI, which we show are formally
necessary in Section 4.3. It naturally suggests new group classes for which polynomial-time isomorphism tests might be within reach, and also suggests a priori many group classes for which
polynomial-time algorithms have previously been achieved.
However, before we proceed, let us emphasize that the extension viewpoint only helps with a
conceptual understanding of these previous works. Given this viewpoint, to tackle each group class
may still require novel mathematical ideas and technically demanding algorithms. The extension
viewpoint is mostly used to set the stage for applications of such mathematical and algorithmic
techniques. In other words, instead of looking at a table encoding an abstract group, an application
of the Main Lemma usually transfers us to a more concrete setting where we need to solve problems
about, e. g., bilinear maps and permutation groups. We also stress that not all recent progress on
GpI can be captured from this extension viewpoint, e. g., [Wil13, GR16].

4.1

A recipe for group isomorphism

1. Choose wisely a polynomial-time computable characteristic subgroup function S. Note that if
S(G) is always abelian, then the technically simpler abelian Main Lemma 2.3 can be applied.
2. Test whether S(G1 ) ∼
= S(G2 ) (which we henceforth refer to as N ) and G1 /S(G1 ) ∼
= G2 /S(G2 )
(which we refer to as Q). If either of these fails, then G1 6∼
G
.
= 2
3. Extract the extension data (Ti , fi ) from the extension N ,→ Gi  Q for i = 1, 2 by picking
arbitrary sections s : Q → Gi and computing the action and cohomology class.
4. Test pseudo-congruence of the two extension data. That is, find (α, β) ∈ Aut(N ) × Aut(Q),
(α,β)
(α,β) t,T2
and a function t : Q → N such that T1 (q) = ct(q) ◦ T2
(q) and f1 = (f2
) . If the
abelian Main Lemma 2.3 applies, then t is unnecessary.
Some general remarks are due for each of these steps:
1. A seemingly obvious requirement would be that S(G) should not be trivial for any G ∈ C.
However, even if this is not the case, it may be fruitful to consider separately the class of
groups for which S(G) is trivial. For example, semisimple groups arise this way, as those
groups for which Rad(G) is trivial.
22

2. Due to the nature of the divide and conquer strategy, S(G) and G/S(G) should be from
group classes with known efficient isomorphism tests. Alternatively, if, say, S(G) is not from
such a class, it may be possible to use this strategy to reduce isomorphism of groups in C to
isomorphism of groups of the form S(G) for G ∈ C (or similarly for G/S(G)).
3. This step is easy (poly(|G|) time). Based on the group class C the extension data will hopefully
turn out to have nice mathematical structure; indeed, looking for this nice mathematical
structure is a nice heuristic that can help motivate and suggest various choices for C.
4. This pseudo-congruence test is the main bottleneck. Choosing S so that this step can take
advantage of known cohomological results may be helpful. For example, if S(G) ≤ Z(G) then
Extension Data Pseudo-congruence simplifies to Cohomology Class Isomorphism;
at the opposite end of the spectrum, if G = S(G) o (G/S(G)) then Extension Data
Pseudo-congruence simplifies to Action Compatibility. As another example, if S(G)
is centerless, one may take advantage of Theorem 3.15, as in the case of semisimple groups
(see below).

4.2

Some recent results from the point of view of the main lemma

As mentioned in the introduction, there have been some recent polynomial-time algorithms for
several group classes: semisimple groups [BCGQ11, BCQ12], generalized Heisenberg groups [LW12],
groups with abelian Sylow towers [BQ12], and (in this paper) no(log n) -time algorithms for centralradical groups. The experts would easily see how the perspective of group extension helps to open a
venue of attack to devise efficient algorithms for these group classes. However, for readers who have
not seen such a connection, the definitions of these group classes may at first seem obscure, and
it is not a priori clear why we should have found efficient algorithms for these particular classes
of groups, as opposed to others. We believe that the viewpoint of extensions and cohomology,
especially in light of the Main Lemma, gives a unifying perspective to these works which helps to
explain the progress on these group classes, thereby easing certain readers’ understanding of these
previous works.
In the following, we first summarize some basic information about these works, and then explain
in detail how previous works on GpI fit into the general strategy described as above.

23

References

Group class

[BCGQ11, BCQ12]

Semisimple groups

[LW12]

Quotients of generalized Heisenberg
groups
Groups with abelian
Sylow towers

Center

This work

Central-radical
groups

Solvable radical

Follow-up work [GQ15]

Groups with “tame”
radicals

Any “tame” abelian

[LG09, QST11, BQ12]

Characteristic
group function
Socle6

Normal
groups

Hall

sub-

sub-

Extension type
Extension of a centerless group
Special type of central extensions of Zkp
by Z`p
Split extension of A
by Q with (|A|, |Q|) =
1
(Central) Extension
of abelian groups by
semisimple groups
Tame extension of A
by Q

Semisimple groups (groups with no abelian normal subgroups). In the polynomial-time
algorithm for semisimple groups [BCQ12] we take S = Soc, i. e., N = Soc(G), which is a polynomialtime characteristic subgroup function. Hence the general Main Lemma 3.7 applies and isomorphism
of semisimple groups reduces to Extension Data Pseudo-congruence. When G is semisimple,
its socle is a direct product of nonabelian simple groups, so Z(N ) = 1. N being centerless simplifies
some of the results in the previous section, as captured in Theorem 3.15, which corresponds to the
key lemma in [BCGQ11] (Lemma 3.1 therein), and leads to the problems considered by Babai et al.
[BCGQ11, BCQ12]. In particular, note that in the definition of pseudo-congruence for nonabelian
N , after twisting by (α, β) ∈ Aut(N ) × Aut(Q) to make the actions T1 , T2 become equivalent
as outer actions, the condition on the 2-cocycles is simply that they differ by a 2-coboundary in
B 2 (Q, Z(N ), T ). In particular, when N is centerless B 2 (Q, Z(N ), T ) is trivial, so Extension Data
Pseudo-congruence reduces to Outer Action Compatibility.
In the case of semisimple groups, using the structure of these groups, one sees quickly that
Outer Action Compatibility reduces to Twisted Code Equivalence (introduced in [BCQ12]),
where the “twisting” groups correspond to the action of Out(N ) = Out(Soc(G)) in the definition
of Outer Action Compatibility, and the choice of t : Q → N is handled by considering codes
whose codewords correspond to elements of G rather than just elements of Q.
p-groups of class 2 and exponent p, esp. quotients of generalized Heisenberg groups.
For p-groups of class 2 and exponent p with odd p, Baer’s correspondence [Bae38] suggests considering the alternating bilinear maps defined by the commutator bracket: isomorphism of p-groups
corresponds to pseudo-isometry of these bilinear maps. These bilinear maps are 2-cocycles, and
two such cocycles are isomorphic as cohomology classes if and only if the bilinear maps are pseudoisometric, so we see that this is a particular instance of Cohomology Class Isomorphism and
Baer’s correspondence can be viewed as a special case of the abelian Main Lemma 2.3.
The bilinear map viewpoint has been the main stage for the recent progress on testing isomorphism of such p-groups [LW12, BMW15]. For example, in [LW12], Lewis and Wilson [LW12]
studied a decently large class of p-groups—quotients of generalized Heisenberg groups—which are
6

The socle of a group G is the subgroup generated by the union of the minimal normal subgroups of G.

24

indistinguishable to classical invariants but for which they nonetheless present a polynomial-time
isomorphism test. Such groups admit a nice characterization from the bilinear map viewpoint
[LW12, Theorem 3.13], and the polynomial-time isomorphism test for these groups takes advantage
of the special structure of the bilinear maps corresponding to these groups ([LW12, Theorem 4.1]).
We remark that the algorithm in [LW12] works with much more succinct models for representing
groups, including permutation groups and matrix groups, and runs in time polynomial in the input
size, which can be as small as log |G| instead of |G|.
Groups with abelian Sylow towers. Though solving GpI for the obscure-sounding group class
“groups with abelian Sylow towers,” the core of [BQ12] (following [LG09, QST11]) deals with the
case of coprime extensions, namely extension of an abelian A by Q where (|A|, |Q|) = 1. The
Schur–Zassenhaus Theorem guarantees that coprime extensions split, thus reducing Extension
Data Pseudo-congruence to Action Compatibility for such groups. Assuming Aut(Q) is
known (via recursive divide-and-conquer), [BQ12] views the actions of Q on A as linear representations and utilizes the complete reduciblility of these representation by Maschke’s Theorem, which
requires coprimality. The tactic they use is to view the induced action of Aut(Q) on the irreducible
constituents as a permutation group action, and then to develop a parameterized permutation
group algorithm to finally solve Action Compatibility in this case [BQ12].
Tame extensions. In a follow-up work [GQ15], the current authors used the viewpoint of this
paper to generalize the preceding from coprime extensions to so-called “tame” extensions. These
are extensions of Zkp by Q (assuming Aut(Q) is known, e. g., by recursive divide-and-conquer)
where the Sylow p-subgroups of Q are cyclic, or p = 2 and the Sylow 2-subgroups are dihedral,
semi-dihedral, or generalized quaternion. (The case above is when the Sylow p-subgroups of Q are
trivial.)
In fact, the story behind [GQ15] is a perfect example of the utility of explicitly splitting GpI
into Action Compatibility and Cohomology Class Isomorphism. Namely, independently,
one of the current authors had solved Action Compatibility for the tame case, and the other had
solved Cohomology Class Isomorphism for the tame case under the assumption that Action
Compatibility could be solved; when they met in Chicago each was eager to tell the other of their
result, asking if the other “half” of the problem could be solved. The result was nearly immediate
from there.
Central-radical groups. Similarly, by considering cohomology rather than actions we will see
in the following how to handle central-radical groups. An elementary way of manipulating the
2-cohomology classes yields an nO(log log n) -time algorithm for groups with central radicals. For a
subclass of groups with central radicals, a more detailed understanding of 2-cohomology classes
(Lemma 7.4) helps establish the polynomial-time algorithms in Theorem C=7.1. In particular,
singly exponential algorithms for Linear Code Equivalence and for Coset Intersection
enter inevitably in the algorithm for this theorem.
Summary. In summary, although the strategy we propose will rarely solve the problem completely, even for a restricted class of groups, it has the virtue of quickly dispensing with structural
issues to highlight the needed algorithmic tactics.

25

4.3

Necessity of pseudo-congruence and cohomology

Lemma 2.3 suggests studying Extension Data Pseudo-congruence to make progress towards
GpI for groups with abelian normal subgroups. In this section, we shall see that pseudo-congruence
tests for certain classes of extension data are exactly isomorphism tests for certain interesting group
classes. While Lemma 2.3 almost implies so, a pitfall is that in the reconstruction procedure we
need the normal copy of A in H to be the image of a characteristic subgroup function. (In the
setting of Lemma 2.3 the standard reconstruction procedure does return groups Hi with the copy
of A = S(Hi ), but this is because of the assumptions of that lemma.) This leads us to look at some
concrete classes of extension data, for which this property holds.
For split extensions, a well-known example is the case when |A| and |Q| are coprime, as ensured
by the Schur–Zassenhaus Theorem. In this case G is said to be a coprime extension of A by Q, and
A is a normal Hall subgroup in G. Noting that taking a normal Hall subgroup of a specific order
is a characteristic subgroup function, with the standard reconstruction procedure we have:
Fact 4.1. There is a polynomial-time function r which takes any group action θ : G → Aut(B) (for
any groups B, G) to a group r(θ) with the following property. When A is abelian, Q is a group of
order coprime to |A|, and θi : Q → Aut(A) (i = 1, 2) are group actions, then (θ1 , θ2 ) 7→ (r(θ1 ), r(θ2 ))
is a Karp reduction from these instances of Action Compatibility to GpI.
A polynomial-time algorithm for Action Compatibility for the case in Fact 4.1 was given by
Babai and Qiao [BQ12], yielding a polynomial-time time algorithm for “groups with abelian Sylow
towers.”
Remark 4.2. Despite the polynomial-time algorithm for Action Compatibility for coprime
case—which trivially implies there is a Karp reduction to any problem, including GpI—Fact 4.1
remains nontrivial. In particular, recall that given equivalence relations ∼1 on X1 and ∼2 on
X2 , a kernel reduction between them is a function f : X1 → X2 such that x ∼1 y if and only if
f (x) ∼2 f (y) [FG11]. Fact 4.1 states that there is a polynomial-time kernel reduction, which does
not follow automatically from the polynomial-time algorithm for coprime Action Compatibility.
For central extensions, let p 6= 2 be a prime. If A and Q are both abelian, then a Z-bilinear
map f : Q × Q → A is a 2-cocycle, as the cocycle identity follows directly from bilinearity. Note
that the action of Aut(A) × Aut(Q) preserves bilinearity. The following proposition is known
([Bae38, Laz54], see also [War76, Section 5] and [Wil09a]); the standard reconstruction procedure
is altered to make the image of A the commutator subgroup.
Fact 4.3. Given a prime p 6= 2, and finite abelian p-groups A and Q let fi : Q × Q → A be an
alternating bilinear map. Then Cohomology Class Isomorphism for f1 , f2 Karp-reduces to
GpI.
Proof. Given fi for i = 1, 2, alter the standard construction as follows. For a, b ∈ A and q, q 0 ∈ Q,
we define the group Gi with operation ◦ over the set A×Q as (a, q)◦(b, q 0 ) = (a+b+ 21 fi (q, q 0 ), q+q 0 ).
It is known that Gi ’s are p-groups of class 2, the copy of A in Gi is the commutator subgroup, and
f1 ∼
= f2 if and only if G1 ∼
= G2 (see, e. g., [War76, Section 5]).
Finally let us examine groups whose solvable radicals are abelian, a super-class of centralradical groups. When Q is semisimple, the standard reconstruction procedure sends A to the
solvable radical. (A solvable normal subgroup N is the solvable radical if and only if G/N is
26

semisimple.) This hints at the fact that for central-radical groups, group isomorphism is equivalent
to Cohomology Class Isomorphism.
Fact 4.4. Let A be abelian and Q semisimple. For i = 1, 2, let θi : Q → Aut(A) be a homomorphism, and fi : Q × Q → A be a 2-cocycle in Z 2 (Q, A, θi ). Then Extension Data Pseudocongruence for (θ1 , f1 ) and (θ2 , f2 ) Karp-reduces to GpI.

5

Preliminaries for the algorithms

Some general notations are described at the beginning of Section 2.
Further notations and some group-theoretic facts. Given a finite set Ω, Sym(Ω) denotes
the symmetric group consisting of all permutations of Ω. A permutation group acting on Ω is a
subgroup of Sym(Ω). Given π ∈ Sym(Ω) and a ∈ Ω, the image of a under π is denoted by aπ . If
Ω = [n], n ∈ N, we use Sn to denote Sym(Ω), and An ≤ Sn consists of permutations of even signs.
For a vector space V over a field F, the general linear group GL(V ) consists of all non-singular
linear transformations of V . If V = Fnq , q is a prime power, we may write GL(n, q) for GL(V ).
By the Fundamental Theorem of Finite Abelian Groups, a finite abelian group is isomorphic
to a direct product of cyclic groups of prime power orders. Formally, let A be an abelian group,
then there exists a direct product decomposition of A as A = he1 i × he2 i × · · · × hen i, where ei ∈ A
has order piki , such that p1 ≤ p2 ≤ · · · ≤ pn , and if pi = pi+1 , then ki ≤ ki+1 , for all i. This
decomposition is called the primary decomposition of A, and the tuple (e1 , . . . , en ) forms a basis
of A. The elementary abelian groups are those groups of the form Znp for some prime p and any n.
Note that Aut(Znp ) ∼
= GL(n, p).
A group G is simple if |G| > 1 and G has no proper nontrivial normal subgroups. The celebrated
Classification of Finite Simple Groups lists all finite simple groups explicitly [CCN+ 85]. The only
abelian simple groups are the cyclic groups of prime order. We use the following fact, which
(currently) depends on the Classification for its proof:
Fact 5.1 ([Ste62, AG84]). Every nonabelian simple group can be generated by 2 elements.
Let T be a nonabelian simple group, it is easily shown that Aut(T k ) ∼
= Aut(T )oSk where o denotes
the wreath product. If a group G is a direct product of nonabelian simple groups, then this direct
product decomposition is unique, not just up to isomorphism: if G = T1 × · · · × Tk = S1 × · · · × S` ,
Ti , Sj nonabelian simple, then k = ` and ∃σ ∈ Sk , ∀i ∈ [k], Ti = Siσ as subsets of G.
A group G is perfect if G = [G, G], centerless if Z(G) = 1, and (directly) indecomposable if it
cannot be written as a nontrivial direct product. Nonabelian simple groups are perfect, centerless,
and indecomposable, and several properties of nonabelian simple groups generalize to this class.
In particular, if T is a perfect, centerless, indecomposable group then Aut(T k ) ∼
= Aut(T ) o Sk .
Furthermore, if G = T1 × · · · × Tk where each Ti is perfect, centerless, and indecomposable, then
the direct factors of G are uniquely determined as subsets of G (not just up to isomorphism), as in
the case of nonabelian simple groups.
(However, perfect, centerless, indecomposable groups can require many more than two generators, and correspondingly
can have quite large automorphism groups, for example, the group
Q
{(π1 , . . . , πk )|πi ∈ S5 , i∈[k] πi ∈ A5 }.)
The following observation is often useful to upgrade algorithms from merely deciding isomorphism to computing the entire coset of isomorphisms. The reader should have in mind that this
27

observation will typically be applied in settings where the groups X, Y, Z are automorphism groups
of other groups.
ι

π

Observation 5.2. Let X be a subgroup of an extension Y ,→ X  Z. If Y ⊆ ι(Y ) generates
ι(Y ) ∩ X, and Z ⊆ Z generates π(X), and for each z ∈ Z, xz is such that xz ∈ X and π(xz ) = z,
then Y ∪ {xz ∈ X : z ∈ Z} generates X.
Proof. Given x ∈ X, first write z = π(x) as a word in the generators Z, say z = z1 · · · z` , with each
zi ∈ Z. Then y = x · (xz1 · · · xz` )−1 is in X ∩ Ker(π) = X ∩ ι(Y ). Now write y as a word in Y.
In Theorem 7.1(1), we will need the following deep result bounding the size of the second
cohomology of simple groups:
Theorem 5.3 ([GKKL07, Thm. B]). For any finite (quasi7 )simple group G, any field F, and any
F-representation θ : G → GL(V ) (V an F-vector space), dimF H 2 (G, V, θ) ≤ 17.5 dimF V .
Useful algorithms. We shall need some known algorithmic results. Recall that in permutation group algorithms (see [Luk91, Ser03]), a coset P σ ⊆ Sn is represented by a set of generators for P ≤ Sn and a coset representative σ. A particularly relevant problem on permutation
groups is the Coset Intersection problem: given two cosets of subgroups of Sym(A), find
their intersection. GraphI can be Karp-reduced to Coset Intersection [Luk82]. The Coset
Intersection problem for permutation groups of degree n can be solved in quasi-polynomial
(exp((log n)O(1) )) time [Bab16], while a relatively easier singly exponential (exp(O(n))) algorithm
has been obtained by Luks [Luk99]. Algorithms over finite-dimensional algebras have been considered in, e. g., [CIK97, BL08, IKS10]. In particular, over finite fields, polynomial-time algorithms
for Module Isomorphism and Module Cyclicity are first shown in [CIK97].
A linear code of length n is a linear subspace V ≤ Fn , represented by a d × n matrix where
d = dim(V ), and the rows form a linear basis of V . Sn acts on a linear code by permuting the
coordinates (that is the columns of the matrices). Two linear codes V, U ≤ Fn are equivalent if
there exists a permutation σ ∈ Sn such that V σ = U as linear subspaces. Such a σ is called an
equivalence between V and U , and the set of all equivalences, denoted by CodeEq(V, U ) is either
empty or a coset in Sn . This problem is GraphI-hard in general [PR97] while Babai presents a
singly exponential time algorithm:
Theorem 5.4 (Babai, [Bab10], cf. [BCGQ11]). The set of equivalences of two linear codes of
length n (over any field) given by generator matrices can be found in (2 + o(1))n time, assuming
field operations at unit cost.
We will also need the following results of Babai et al. [BCGQ11]:
Theorem 5.5 ([BCGQ11, Thm. 1.1]). All isomorphisms between two semisimple groups Q1 and
Q2 of order n, can be listed in time nc log log n+O(1) , where c = 1/ log(60) ≈ 0.16929.
It is also noted in [BCGQ11] that there exist semisimple groups G of order n with |Aut(G)| ≥
nc log log n , namely G = Ak5 . Hence, for listing all isomorphisms this result is essentially optimal.
The number of minimal normal subgroups of any semisimple group of order n is at most O(log n).
If it happens to be O(log n/ log log n), they show:
7
G is quasisimple if it is perfect, and G/Z(G) is simple. Examples include SLn (Fq ) and GLn (Fq ). We will only
need the case of nonabelian simple groups, but the theorem holds in the generality of quasisimple groups, which
might be useful in the future.

28

Theorem 5.6 ([BCGQ11, Cor. 4.4]). Suppose Q1 and Q2 are semisimple groups of order n with
at most O(log n/ log log n) minimal normal subgroups. Then all isomorphisms between Q1 and Q2
can be listed in polynomial time.
In Section 6 we extend both of these results to algorithms for isomorphism of groups with central
radicals, with the same time bounds as above.
To find the coset of isomorphisms efficiently in Theorem 7.1, beyond just deciding isomorphism
or finding a single isomorphism, we need the following result. Recall that an d × d matrix algebra
over a field F is a linear subspace of d × d matrices over F that is also closed under multiplication of
matrices. The unit group of a (matrix) algebra A is the group consisting of all invertible elements
of A (the group operation being the same as the product in the algebra).
Theorem 5.7 ([BO08, Thm. 2.3] and [Rón91]). Given a linear basis of a d × d matrix algebra A
over a finite field Fq , generators of the unit group of A can be computed in time polynomial in d
and q.
Although the preceding theorem from the original papers is stated as a Las Vegas randomized
algorithm that runs in time polynomial in d and log q, they only need randomization to get an
algorithm whose running time depends polynomially on log q rather than q. Essentially the same
algorithm works deterministically in time polynomial in d and q.
We also mention a useful result for groups in the Cayley table model by Kayal and Nezhmetdinov
[KN09], though it is not strictly required in the following. They show that decomposing a group G
into indecomposable direct factors can be done in polynomial time. Even in the stronger setting of
permutation groups given by generators, Wilson showed [Wil12] that this task can be performed
in polynomial time.

6

When enumerating Aut(Q) is allowed

Our main results in this section are nO(log log n) -time algorithms to test isomorphism of (1) groups
with central radicals (Corollary 6.2) and (2) groups with elementary abelian radicals that need not
be central (Corollary 6.12). In case (1), if the radical is furthermore elementary abelian, we can
compute the coset of isomorphisms in the same time bound. These results follow from our more
general Theorems 6.1 and 6.11, respectively, and a theorem on semisimple groups from [BCGQ11]
(reproduced above as Theorem 5.5).

6.1

For central extensions of general abelian groups (Theorem A)

We first consider the case when both extensions G and H are central.
Theorem 6.1. Let S be a polynomial-time-computable characteristic subgroup function. For two
groups G, H of order n, if S(G) ≤ Z(G) and Aut(G/S(G)) can be listed in time t(n), then isomorphism of G and H can be decided in time t(n)nO(1) .
If, furthermore, S(G) is elementary abelian, then the coset of isomorphisms can be found in the
same time bound.
Before proving Theorem 6.1, let us see how it is applied to groups with central radicals. Combining Theorem 6.1 with Theorem 5.5, respectively Theorem 5.6 we have our first two main results:
29

Corollary 6.2. Isomorphism of central-radical groups of order n can be decided in time nc log log n+O(1) ,
for c = 1/ log2 (60) ≈ 0.169. If, furthermore, the center is elementary abelian, the coset of isomorphisms can be found in the same time bound.
Corollary 6.3. Let G and H be central-radical groups of order n. If G/ Rad(G) has O(log n/ log log n)
minimal normal subgroups, isomorphism between G and H can be decided in poly(n) time. If, furthermore, the center is elementary abelian, the coset of isomorphisms can be found in the same
time bound.
We give two different proofs of Theorem 6.1. The first proof has the advantage of dealing
with cohomology classes in a very direct manner and working for arbitrary central S(G), but the
disadvantage of not making it obvious how to compute the full coset of isomorphisms. For clarity,
we first give this “direct” proof in the elementary abelian case, then in Section 6.1.1 give it for the
general abelian case, and finally in Section 6.1.2 go back to the elementary abelian case to show
how to compute the coset of isomorphisms.
Let us consider how to work with 2-cohomology classes in algorithms. Let G be a central
extension of A = Zkp by Q (thinking of A = S(G) and Q = G/S(G)). As the action is trivial
in central extensions, we drop it from the notation, as in Z 2 (Q, A), B 2 (Q, A) and H 2 (Q, A). By
choosing an arbitrary section, we get a 2-cocycle f : Q × Q → A. Let e1 , . . . , ek be the standard
basis of Zkp . We may view f as a k × |Q|2 -size Zp -matrix, which we denote by Mf . The rows are
indexed by the set [k] and the columns are indexed by Q × Q. For i ∈ [k] and (q, q 0 ) ∈ Q × Q,
Mf [i, (q, q 0 )] is the ith coordinate of f (q, q 0 ) relative to the basis {e1 , . . . , ek }. Note that the actions
of Aut(A) and Aut(Q) commute.
Under the above identification, the set C 2 (Q, A) of 2-cochains is identified with the set of all
k × |Q|2 matrices over Zp . Then Z 2 (Q, A) is not just a subgroup (under matrix addition), but
also a Zp -linear subspace of C 2 (Q, A), and similarly B 2 (Q, A) is a Zp -linear subspace of Z 2 (Q, A).
Aut(A) ∼
= GL(k, p) acts on C 2 (Q, A) by left multiplication, and Aut(Q) acts on C 2 (Q, A) by
permuting the columns according to the diagonal action of Aut(Q) on Q × Q.
Proposition 6.4. A basis of B 2 (Q, Zp ) can be computed in time O(|Q|3 (log |Q| + log p)).
In the larger context of GpI, note that the running time here is O(|G|3 log |G|).
Proof. For q ∈ Q, q 6= id, let uq : Q → Zp be uq (q 0 ) = δ(q, q 0 ) where δ is the Kronecker delta.
Let fq : Q × Q → Zp be the 2-coboundary based on uq . V := {fq | q ∈ Q} then forms a basis of
B 2 (Q, Zp ). There are |Q| basis elements, each of which is constructed by computing its |Q|2 values;
each value can be computed by a constant number of additions in Zp (taking O(log p) steps) and
one table lookup to compute a single product in Q (taking O(log |Q|) steps).
As we identified C 2 (Q, A) as k ×|Q|2 matrices over Zp , let Ei,j , i ∈ [k], j ∈ Q×Q be the k ×|Q|2
matrix with a 1 in the (i, j) position and 0 everywhere else. Then {Ei,j | i ∈ [k], j ∈ Q×Q} is a basis
of C 2 (Q, A). Let Ui be the subspace of C 2 (Q, A), spanned by {Ei,j | j ∈ Q × Q}, corresponding to
matrices whose only nonzero entries are in the i-th row. Then C 2 (Q, A) = ⊕i∈[k] Ui . The following
proposition says that not only does C 2 (Q, A) split as a direct sum over the rows, but B 2 (Q, A)
does as well. It follows directly from the fact that the condition to be a 2-coboundary in B 2 (Q, A)
only depends on the columns (Q × Q) and not on the rows ([k]).
Proposition 6.5. Let V be the basis of B 2 (Q,F
Zp ) constructed in the proof of Proposition 6.4, and
let Vi ≤ C 2 (Q, A) be a copy of V in Ui . Then i∈[k] Vi (disjoint union) is a basis of B 2 (Q, Zkp ).
30

|Q|2

Given two 2-cocycles f1 and f2 , let Mi be the matrix representation of fi , i = 1, 2, and Ri ⊆ Zp
be the set of rows in Mi . Recall that α ∈ GL(k, p) acts on the rows of Mi .

Proposition 6.6. With notation as above, there exists α ∈ GL(k, p) such that f1 and f2α are
cohomologous if and only if hR1 , B 2 (Q, Zp )i = hR2 , B 2 (Q, Zp )i, where h·i denotes the Zp -linear
span.
|Q|2

Proof. Let ri,j ∈ Zp be the jth row in Mi , j ∈ [k], i = 1, 2. Let B denote B 2 (Q, Zp ). Note that
Proposition 6.5 says that B 2 (Q, Zkp ) = B ⊕ B ⊕ · · · ⊕ B (k summands).
α be the jth row in the
(⇒) f1 and f2α are cohomologous if and only if f1 −f2α ∈ B 2 (Q, Zkp ). Let r2,j
α
α
matrix representation of f2 . By Proposition 6.5, for every i ∈ [k], r1,i −r2,i ∈ hVi i = B 2 (Q, Zp ) = B.
α ∈ hR i (note that the linear span of R , i. e., the rowspan of M , is
That is r1,i ∈ hR2 , Bi as r2,j
2
2
2
left unchanged by the action of α). Similarly we have r2,i ∈ hR1 , Bi, ∀i ∈ [k]. This shows
hR1 , Bi = hR2 , Bi.
α be the jth row of f α . Given hR , Bi = hR , Bi, we have
(⇐) For α ∈ GL(k, p), again let r2,j
1
2
2
|Q|2

hR1 , Bi/B and hR2 , Bi/B are the same as subspaces of Zp /B. That means that we can choose
α + B, ∀i ∈ [k]. This gives f − f α ∈ B 2 (Q, A).
α ∈ GL(k, p) such that r1,i + B = r2,i
1
2
Proof of Theorem 6.1 (decision version only) when S(G) is elementary abelian. We list Aut(Q) in
time t(n). For i = 1, 2, choose an arbitrary section of Q in Gi to get a 2-cocycle fi . By the Main
Lemma 2.3, it is necessary and sufficient to test whether there exists an (α, β) ∈ Aut(A) × Aut(Q)
(α,β)
such that f1 and f2
are cohomologous.
(id,β)
. We first use Proposition 6.4 to get a basis V of
For each β ∈ Aut(Q) we get f20 = f2
B 2 (Q, Zp ). Let M1 be the matrix representation of f1 , and M2 for f20 . We now need to determine
whether there exists α such that f1 and f20 are cohomologous. By Proposition 6.6 it is enough to
decide whether the linear span of the rows of f1 with V , and the linear span of the rows of f20
with V , are the same. This is a standard task in linear algebra and can be determined in time
polynomial in |Q| and dimZp |A| = k. Lemma 2.3 implies that G1 ∼
= G2 if and only if the preceding
test succeeds for some β ∈ Aut(Q).
6.1.1

From elementary abelian to general abelian

The proof here follows the same steps as in the elementary abelian case. As each abelian group A
is the direct product of its Sylow p-subgroups Ap , we essentially treat the case of a single Sylow
p-subgroup, that is, when A is an abelian p-group Zpµ1 × · · · × Zpµk (not necessarily elementary).
We begin by extending Propositions 6.4–6.6 to the case of abelian p-groups.
As such groups are no longer just vector spaces over Zp , we must speak of subgroups of A rather
than subspaces, and generating sets rather than Zp -bases. To emphasize the similarities, we use
the terminology “Z-basis” for “irredundant generating set.” Similarly for C 2 (Q, A), Z 2 (Q, A), and
B 2 (Q, A). We represent a 2-cochain f : Q × Q → A by a k × |Q|2 integer matrix, where we consider
the entries in the i-th row modulo pµi , that is, as elements of Zpµi . As before, we use Ui to denote
the subgroup of C 2 (Q, A) consisting of matrices whose only nonzero entries are in the i-th row (in
|Q|2
particular, Ui ∼
= Zpµi ).
For these first two propositions, the proofs are the same as the analogous propositions above
for elementary abelian A.

31

Proposition 6.7. For any µ ≥ 1, a Z-basis of B 2 (Q, Zpµ ) can be computed in time O(|Q|3 (log |Q|+
µ log p)).
Proposition 6.8. Let V (µ) denote the Z-basis of B 2 (Q, Zpµ ) constructed in the proof of Proposi(µ )
(µ )
tion 6.7, and let Vi i ≤ C 2 (Q, A) be a copy of V (µi ) in Ui . Then ti∈[k] Vi i (disjoint union) is a
Z-basis of B 2 (Q, Zpµ1 × · · · × Zpµk ).
Before giving the analog of Proposition 6.6 for general abelian A, we recall the structure of
Aut(A) (see, e. g., the exposition in [HR07]); it is only slightly more complicated than the fact that
Aut(Zkp ) = GL(k, p). First, if Ap is the p-Sylow subgroup of A, then Aut(A) = Aut(Ap1 ×· · · Apd ) =
Aut(Ap1 ) × · · · × Aut(Apd ) where p1 , . . . , pd are the distinct primes dividing |A|. So we reduce to
the case where A is an abelian p-group Zpµ1 × · · · × Zpµk with 1 ≤ µ1 ≤ µ2 ≤ · · · ≤ µk . Think
of elements of A as integer column vectors of length k, where the i-th entry is considered modulo
pµi . As in the elementary abelian case (where µ1 = · · · = µk = 1), an automorphism may replace
each entry with a Z-linear combination of the entries, as follows. For i < j, the i-th coordinate can
contribute to the j-th coordinate by multiplying by pµj −µi —in other words, by using the unique
inclusion Zpµi ,→ Zpµj . In the opposite direction, the j-th coordinate can contribute to the i-th
coordinate by taking the j-th coordinate modulo pµi —in other words, using the natural surjection
Zpµj  Zpµi . (Note that when µi = µj these two operations are the same, corresponding to the
identity map on Zpµi .)
More symbolically, we may consider each element of Aut(A) as an integer k × k matrix α such
that: (1) for i > j, pµj −µi divides the (i, j) entry, (2) the entries in row i are considered modulo
pµi , and (3) α is invertible when taken modulo p.
|Q|2
Finally, consider (row) subgroups R ≤ Zpµi . In accord with the above description of the
|Q|2

automorphisms of A, for µ < µi let R(µ) denote the subgroup of Zpµ
pµ ;

that is given by taking R

|Q|2
subgroup of Zpµ
R(q,µ) denote R(µ)

R(µ)

modulo
for µ > µi , let
denote the
that is given by multiplying every
µ−µ
i
element of R by p
. For any prime q, let
if q = p and the trivial subgroup 0
otherwise.
Now, return to A being an arbitrary abelian group. For a 2-cochain f1 ∈ C 2 (Q, A) with
|Q|2
(p,µ)
|Q|2
corresponding k × |Q|2 matrix M with i-th row R1,i ≤ Zpµi , let R1
denote the subgroup of Zpµ
i

(p,µ)

(p,µ)

generated by all the R1,i ; we write R1

(p,µ)

(p,µ)

= hR1,1 , . . . , R1,k i.

Proposition 6.9. Let A = Zpµ1 × · · · Zpµk be an arbitrary abelian group (the pi are primes, not
1
k
necessarily distinct). With other notation as above, there exists α ∈ Aut(A) such that f1 and f2α
(p ,µ )
(p ,µ )
are cohomologous if and only if hR1 i i , B 2 (Q, Zpµi )i = hR2 i i , B 2 (Q, Zpµi )i for each 1 ≤ i ≤ k,
i
i
where h·i denotes the Z-span (=group generated by).
|Q|2

Proof. Let ri,j ∈ Z

µ

pj j

be the j-th row in Mi , j ∈ [k], i = 1, 2. Let B (p,µ) denote B 2 (Q, Zpµ ). Note

that Proposition 6.5 says that B 2 (Q, Zpµ1 × · · · Zpµk ) = B (p1 ,µ1 ) ⊕ · · · ⊕ B (pk ,µk ) .
1

k

α be the j-th row
(⇒) f1 and f2α are cohomologous if and only if f1 − f2α ∈ B 2 (Q, A). Let r2,j
(p,µi )

α ∈ hV
in the matrix representation of f2α . By Proposition 6.7, for every i ∈ [k], r1,i − r2,i
i

B 2 (Q, Zpµi )
i

=

B (pi ,µi ) .

That is r1,i ∈

(p ,µ )
hR2 i i , B (pi ,µi ) i

(p ,µ )

as

α
r2,j

∈

(p ,µ )
hR2 i i i

i=

(note that the subgroup

generated by of R2 i i is, by definition, left unchanged by the action of α). Similarly we have
(p ,µ )
(p ,µ )
(p ,µ )
r2,i ∈ hR1 i i , B (pi ,µi ) i, ∀i ∈ [k]. This shows hR1 i i , B (pi ,µi ) i = hR2 i i , B (pi ,µi ) i for each i.
32

(pi ,µi )

α be the jth row of f α . Given hR
(⇐) For α ∈ Aut(A), again let r2,j
2
1
(pi ,µi )

for each i, we have hR1

(pi ,µi )

, B (pi ,µi ) i/B (pi ,µi ) and hR2

|Q|2
groups of Zpµi /B (pi ,µi ) . That means that we can choose
i
α + B (pi ,µi ) , ∀i ∈ [k]. This gives f − f α ∈ B 2 (Q, A).
r2,i
1
2

(pi ,µi )

, B (pi ,µi ) i = hR2

, B (pi ,µi ) i

, B (pi ,µi ) i/B (pi ,µi ) are the same as subα ∈ Aut(A) such that r1,i + B (pi ,µi ) =

Finally, we come to the proof of Theorem 6.1 for general abelian A:
Proof of Theorem 6.1 (decision version only) for general abelian S(G). The proof is the same as
for the elementary abelian case, but using Propositions 6.8 and 6.9 instead of Propositions 6.4
and 6.6, respectively. Checking the condition of Proposition 6.9 amounts to solving a system of
equations over the abelian group A (“linear algebra over A”), which can be done in polynomial
time (see, e. g., [GR02]).
6.1.2

Computing the coset of isomorphisms in the elementary abelian case

Here we give an alternative proof of Theorem 6.1 in the elementary abelian case, which also provides the structure needed to compute the full coset of isomorphisms. The proof follows the same
general lines as the proof above, except instead of including a basis of B 2 (Q, A) among the rows
2
g
of an extended matrix M
fj , it uses the following Aut(A)-invariant projection from C (Q, A) to
C 2 (Q, A)/B 2 (Q, A). One might think that this approach could be generalized to the general abelian
case following the idea in the previous section, thereby computing the coset of isomorphisms in that
case as well; see the end of this section for a discussion of the difficulties in using that approach.
Proposition 6.10. For A = Zkp and a group Q, let n = |A| · |Q|. In time O(n2 log n) one can
compute an Aut(A)-invariant complement W of B 2 (Q, A) in C 2 (Q, A), and a Zp -linear projection
π from C 2 (Q, A) to W that commutes with every α ∈ Aut(A).
Proof. Let V0 be the basis of B 2 (Q, Zp ) from Proposition 6.4, and let W0 be a linear complement
to V0 in C 2 (Q, Zp ) (which we can think of as the space of row vectors of length |Q|2 ). For each
row index i ∈ [k], let Ri denote the subgroup of C 2 (Q, A) consisting of those matrices whose only
nonzero entries are in the i-th row, let Bi be the copy of B 2 (Q, Zp ) in Ri , let Wi be the copy of W
in Ri , and let πi : Ri → Wi be the projection of Ri to Wi along Bi . (Here we are identifying each
Ri with C 2 (Q, Zp ) as in Proposition 6.5.) Collectively, the πi ’s define a projection π to ⊕i Wi along
⊕i Bi in ⊕i Ri = C 2 (Q, A).
This π makes it easy to identify the 2-cohomology class of f ∈ Z 2 (Q, A) ≤ C 2 (Q, A): f, g ∈
2
Z (Q, A) are cohomologous if and only if π(f ) = π(g). Furthermore, since we have chosen π to be
“the same” on each row, it follows that for any α ∈ Aut(A), απ = πα—an important fact we shall
need later. Also, the above procedure involves only standard linear algebra tasks, and such π can
be constructed in time O(n2 log n).
To summarize, each α ∈ Aut(A), β ∈ Aut(Q), and the map π : C 2 (Q, A) → C 2 (Q, A)/B 2 (Q, A)
just introduced can be viewed as a linear map on C 2 (Q, A), with α and β nonsingular. We then
note: (1) α and β commute; (2) α and π commute.
Proof of Theorem 6.1 for elementary abelian S(G), with the coset of isomorphisms. We list Aut(Q)
in time t(n). For i = 1, 2, choose an arbitrary section of Q in Gi to get a 2-cocycle fi . Use Proposition 6.10 to get the projection π : C 2 (Q, A) → W for some complement W of B 2 (Q, A) such that
33

W is invariant under α and απ = πα for every α ∈ Aut(A). By the Lemma 2.3, it is necessary and
(α,β)
sufficient to test whether there exists an (α, β) ∈ Aut(A) × Aut(Q) such that π(f1 ) = π(f2
). As
(id,β) (α,id)
every α commutes with both π and β, this condition is equivalent to π(f1 ) = (π(f2
))
. In
other words, we may leave α unspecified until the final step.
(id,β)
For each β ∈ Aut(Q), compute f10 = π(f1 ), and f20 = π(f2
). Note that fi0 are in W ≤
C 2 (Q, A). The goal is then to find α ∈ Aut(A) such that f10 = α−1 (f20 ). f10 = α−1 (f20 ) for some
|Q|2
α ∈ Aut(A) if and only if the row spans of Mf10 and Mf20 are the same in Zp . The latter task
is standard in linear algebra and can be checked in time O(|Q|6 log p). Lemma 2.3 implies that
G1 ∼
= G2 if and only if the preceding test succeeds for some β ∈ Aut(Q).
Computing the coset of isomorphisms. (This is essentially the same procedure as in Smith’s
thesis [Smi94]; we review the procedure here in detail, in order to give a rigorous analysis of its
running time.) Note that Aut(G) maps into Aut(A) × Aut(Q); let ρ denote this homomorphism.
We apply Observation 5.2 twice: once, to split the computation into computing generators of
Im(ρ) ≤ Aut(A) × Aut(Q) and Ker(ρ), and then a second time to split the computation of Im(ρ)
into computing its projections onto Aut(A) and Aut(Q), respectively. We handle this latter step
first.
Let Aut(A) play the role of Y in Observation 5.2 and Aut(Q) play the role of Z. In our
algorithm, we may in fact take Z to be the entirety of the projection of Aut(G) into Aut(Q), since
we enumerate over all automorphisms of Q. To use Observation 5.2, for each automorphism of Q
that admits a compatible automorphism of A, we need one such automorphism of A, which are
easily found as solutions to the linear algebra, as described above.
We then also need a generating set of the automorphisms of A that preserve the cohomology
class f : Q × Q → A, that is, those elements of Aut(A) that send f to itself modulo B 2 (Q, A).
Equivalently, we want the stabilizer of the matrix Mπ(f ) in Aut(A) ∼
= GL(k, p). Since Aut(A) acts
on each column of a 2-cochain independently, this stabilizer is the same as the pointwise stabilizer
of the set of columns of Mπ(f ) . If the columns of Mπ(f ) span A, then this stabilizer is trivial, and
we are done. More generally, let B ≤ A be the Zp -linear span of the columns of Mπ(f ) (although
we won’t need it here, Lemma 7.5 may help the reader’s intuition, which says that, in this case,
there is a complementary subgroup B 0 ≤ A such that A ∼
= B ⊕ B 0 and G ∼
= (G/B 0 ) × B 0 ). Choose
a basis {e1 , . . . , ek } of A such that a prefix of this basis, say {e1 , . . . , edim B } is a basis of B. In this
basis, the stabilizer of Mπ(f ) in GL(k, p) then consists of all block matrices of the form


idB ∗
0 η


,

where η ∈ GL(k − dim B, p) and “∗” indicates any (dim B) × (dim A − dim B) matrix. A generating
set for this subgroup is easily written down directly, taking advantage of a standard generating set
for GL (e. g., elementary matrices). Observation 5.2 then gives us a generating set for Im(ρ) ≤
Aut(A) × Aut(Q).
Finally, we apply Observation 5.2 again, now with Ker(ρ) in the role of Y and Im(ρ) in the
role of Z. We have already computing a generating set Z. For each such generator, we must
compute a lift of it in Aut(G), and then we also need to compute generators for Ker(ρ). The
lifts of Im(ρ) to Aut(G) are easily computed, once we have chosen our section s : Q → G: given
(α, β) ∈ Im(ρ) ≤ Aut(A) × Aut(Q), every element of G is uniquely represented as as(q) for some
34

a ∈ A, q ∈ Q, and then the corresponding automorphism of G acts by sending as(q) to α(a)s(β(q)).
It is readily verified that this is an automorphism of G.
The kernel of ρ consists of those automorphisms of G that fix Q pointwise, and fix A pointwise.
Thus, all they can do is move elements around within their respective cosets of A. That is, any automorphism in Ker(ρ) is determined by a map δ : Q → A such that the automorphism is given by sending as(q) to aδ(q)s(q). Since the automorphism fixes A pointwise, we must have δ(idQ ) = idA . To
see the condition to be a homomorphism, recall that (as(q))(a0 s(q 0 )) = a(s(q)a0 s(q)−1 )fs (q, q 0 )s(qq 0 )
so we must have δ(q)δ(q 0 ) = δ(qq 0 ). These |Q|2 equations are homogeneous linear equations in
|Q| dim A variables over the field Zp ; such linear equations can be solved in polynomial time, yielding a generating set for Ker(ρ). Putting it all together, this yields a generating set for Aut(G).
To see the difficulty in extending this proof to the general abelian case, we first mention an
alternative viewpoint on the preceding proof: The set C 2 (Q, Zkp ), viewed as k × |Q|2 matrices, is
acted on by Aut(A) ∼
= GL(k, p) by left multiplication. Let V ∼
= Zkp be the defining representation
2
of GL(k, p); then C 2 (Q, A) is isomorphic, as an Aut(A)-module, to V ⊕|Q| . Since V is irreducible,
this module is semisimple, so every submodule is a direct summand, and thus every submodule is
of the form V ⊕` for some `. So H 2 (Q, A) is isomorphic to V ⊕` as an Aut(A)-module, and finding
the Aut(A)-stabilizer of a point in V ⊕` amounts to finding the stabilizer of a point in V several
times, which is easily done since V is the defining representation of Aut(A) ∼
= GL(V ).
The difficulty in extending this proof to the general abelian case is that B 2 (Q, A) need not, in
2
general, be a direct summand of Z 2 (Q, A), nor of C 2 (Q, A); in the general case C 2 (Q, A) ∼
= A⊕|Q|
as Aut(A)-modules, but this module is no longer semisimple in general. For example, C 2 (A5 , Z4 ) ∼
=
2
Z60
,
which
contains
many
copies
of
Z
that
are
submodules
but
not
direct
summands.
Note
2
4
that H 2 (A5 , Z4 ) ∼
= Z2 (use the well-known fact that H2 (A5 , Z) ∼
= Z2 , together with the Universal
Coefficient Theorem, e. g., [Hat02, Theorem 3.2], and the fact that H1 (A5 , Z) = 0, since A5 is
perfect). So either Z 2 (A5 , Z4 ) is not a direct summand of C 2 (A5 , Z4 ) or B 2 (A5 , Z4 ) is not a direct
summand of Z 2 (A5 , Z4 ).
Without a direct summand decomposition, the straightforward way to obtain an action of
Aut(A) on H 2 (Q, A) is to realize H 2 (Q, A) explicitly as L
a quotient module. This can be done
quite easily, using the fact that H 2 (Q, Zpµ1 × · · · Zpµk ) ∼
= i∈[k] H 2 (Q, Zpµi ). This even yields an
1

k

i

Aut(A)-invariant projection Z 2 (Q, A) → H 2 (Q, A) (the best we can hope for in the absence of a
direct sum decomposition). But then the difficulty becomes that we do not know the structure of
this quotient module well enough. If it were just the action of Aut(A) on A⊕` for some `, then we
would be very close to done, as one can find the linear subspace of Aut(A) that fixes a point in
A⊕` using Smith normal form, and then all that would be needed is the general abelian analogue
of Theorem 5.7 (see Open Problem 8.2). However, while the group action of Aut(A) on H 2 (Q, A)
looks very similar to the action of Aut(A) on A⊕` for some `, it differs in an important way:
The elements in Aut(A) that would normally induce surjections Zdpµ  Zdpµ0 with µ0 < µ induce
maps H 2 (Q, Zpµ ) → H 2 (Q, Zpµ0 ) which need not be surjections. (The failure to be a surjection
is measured precisely by H 3 (Q, Zpµ−µ0 ).) So in this case, the best we can do naively is to apply
generic algorithms for finding stabilizers in matrix groups, but the current state of the art is not
fast enough for this to run in time poly(|Q|, |A|).

35

6.2

For general extensions of elementary abelian groups (Theorem B)

Theorem 6.11. Let S be a polynomial-time-computable characteristic subgroup function. For two
groups G, H of order n, if S(G) ∼
= Zkp and Aut(G/S(G)) can be listed in time t(n), then isomorphism
of G and H can be decided, and the coset of isomorphisms found, in time t(n)nO(1) .
As before, let us first see how this applies to groups with elementary abelian radicals. Combining
Theorem 6.11 with Theorem 5.5, respectively Theorem 5.6, we have:
Corollary 6.12. Isomorphism of groups of order n with elementary abelian radicals can be decided,
and the coset of isomorphisms found, in time nc log log n+O(1) , for c = 1/ log2 (60) ≈ 0.169.
Corollary 6.13. Let G and H be groups of order n with elementary abelian radicals. If G/ Rad(G)
has O(log n/ log log n) minimal normal subgroups, isomorphism between G and H can be decided,
and the coset of isomorphisms found, in poly(n) time.
The proof of Theorem 6.11 is a reduction to Module Cyclicity, for which a deterministic
polynomial-time algorithm over finite fields is provided by Chistov, Ivanyos and Karpinski [CIK97];
this was recently generalized to finite modules (not necessarily over a field) [CT15], which we use
to decide the case of general abelian radicals, but where the extension by the radical is split (see
Remark 6.14), and we expect to have further uses. Before the reduction it might be helpful to see
this problem in a special case, when the extensions are split.
Proof of Theorem 6.11 for split extensions, a.k.a. Module Isomorphism. Recall that G1 and G2
are extensions of A = Zkp by Q. Furthermore suppose both extensions split. Then to test isomorphism we are left with the Action Compatibility, that is, we extract the actions of Q on A
in Gi as θi : Q → Aut(A) = GL(k, p), and the goal is to find (α, β) ∈ Aut(A) × Aut(Q) such
(α,β)
that θ1 = θ2 . As Aut(Q) is enumerable, we fix a β and all that remains is to test whether
there exists α ∈ GL(k, p) such that ∀q ∈ Q θ1 (q) = α−1 θ2 (q)α. In other words, viewing θi as
linear representations of Q over the field Fp , the problem is to test whether these two representations are equivalent. This can also be formulated as finding a nonsingular matrix α such that
αθ1 (q) = θ2 (q)α, ∀q ∈ Q, namely Module Isomorphism. Over finite fields this problem admits
deterministic polynomial-time algorithms [CIK97, BL08].
Computing the coset of isomorphisms. When A is elementary abelian, we can also find the
full coset of isomorphisms. For this, we need a generating set of the group of units of the matrix
algebra {α ∈ M (k, p) : αθ1 (q) = θ2 (q)α∀q ∈ Q}. First, compute an Fp -linear basis for this algebra
by solving the given equations, which are linear in the entries of α. Next, from this linear basis for
this matrix algebra, use Theorem 5.7 to compute a generating set of the group of units.
Remark 6.14. In the case of split extensions, we can also decide isomorphism even when A is a
general abelian group, not necessarily elementary. For this, we cannot use GL(k, p), but must stick
with the more general group Aut(A); the rest of the above proof for deciding isomorphism goes
through mutatis mutandis, reducing now to Module Isomorphism for finite ZG-modules, rather
than finite(-dimensional) Fp G-modules. Module Isomorphism for finite ZG-modules can also be
solved deterministically in polynomial time [CT15]. For computing the coset of isomorphisms, we
do not yet know how to compute the unit group of a finite Z-algebra (rather than one over a field).
See Open Question 8.2.
36

Now we present the reduction for the general case.
Proof of Theorem 6.11: reduction to Module Cyclicity. As always, we start with the elementary abelian case. Let G1 and G2 be extensions of A = Zkp by Q, and (θi , fi ) the extension data of
(α,β)

A ,→ Gi  Q. It can be verified that if (α, β) satisfies θ1 = θ2 , then (α, β) sends Z 2 (Q, A, θ2 )
to Z 2 (Q, A, θ1 ) and sends B 2 (Q, A, θ2 ) to B 2 (Q, A, θ1 ). As Aut(Q) is enumerable, the problem is
to find α ∈ GL(k, p) such that (1) ∀q ∈ Q, αθ1 (q) = θ2 (q)α; (2) αf1 = f2 as cohomology classes in
Z 2 (Q, A, θ2 ) (that is [αf1 ] = [f2 ]).
This task can be reduced to Module Cyclicity over finite-dimensional algebras, in almost
the same way as the reduction from Module Isomorphism to Module Cyclicity [CIK97].
We include a full proof here for completeness. The basic idea is as follows: just as Iso(G1 , G2 )
is a coset of Aut(G1 ), Hom(G1 , G2 ) is a “coset of”—more precisely, is acted on by—End(G1 ) :=
Hom(G1 , G1 ). If one could find Hom(G1 , G2 ), the problem would be reduced to finding an invertible
element there. The following is the linear-algebraic version of these ideas, in which finding an
invertible element inside a set of not-necessarily-invertible homomorphisms is reduced to Module
Cyclicity, for the analog of Hom(G1 , G2 ) considered as a module over the analog of End(G1 ).
Let M (k, p) be the linear space of k × k matrices over Zp . Consider a linear subspace of
M (k, p), V = {α ∈ M (k, p) | ∀q ∈ Q, αθ1 (q) = θ2 (q)α, and ∃a ∈ Zp , [αf1 ] = [af2 ]}. Also consider
U = {γ ∈ M (k, p) | ∀q ∈ Q, γθ2 (q) = θ2 (q)γ, and ∃a ∈ Zp , [γf2 ] = [af2 ]}. It can be verified that U
is an associative algebra over Zp with identity. Note that we need to allow the possible scalar a in
the definition of U in order for U to be closed under addition. This does not hurt the multiplicative
condition, since αθ2 (q) = θ2 (q)α is not changed if we multiply both sides by a scalar. Once the
scalar is allowed in the definition of U , we must also allow it in the definition of V , in order for V to
be a U -module (see next paragraph). However, if [γf2 ] = [af2 ], then a−1 γ ∈ U and a−1 γ)[f2 ] = [f2 ],
so U essentially consists of endomorphisms of G “up to scale.”
Then V is a left U -module: for α ∈ V , γ ∈ U and q ∈ Q, γαθ1 (q) = γθ2 (q)α = θ2 (q)γα.
To show that [γαf1 ] = [af2 ] is a little subtle, and for this we need to recall the fact that, if
γθ2 (q) = θ2 (q)γ for every q ∈ Q, then γ preserves B 2 (Q, A, θ2 ). That is, αf1 = af2 + g for some
a ∈ Zp and g ∈ B 2 (Q, A, θ2 ), and γαf1 = γ(af2 + g) = aγf2 + γg = a0 f2 + g 0 + g 00 where a0 ∈ Zp ,
aγf2 = a0 f2 + g 0 and γg = g 00 . Now we claim that if V contains invertible elements, then (1) it
is cyclic, and (2) every generator is invertible. To show (1), let α0 ∈ V be invertible, and form
φ : U → V by sending γ → γα0 . Then φ is an U -module isomorphism between U and V , whose
inverse is V → U by α → αα0−1 ; αα0−1 ∈ U again follows from that α and α0 can be shown to send
B 2 (Q, A, θ2 ) to B 2 (Q, A, θ1 ) as a consequence of αθ1 (q) = θ2 (q)α. For (2), if α00 generates V , then
α00 α0−1 generates U as a left U -module, and thus α00 α0−1 is invertible, showing that α00 is invertible.
Finally we note that if some invertible α0 ∈ V sends [f1 ] to [af2 ] for some a ∈ Zp , then a−1 α0 ∈ V
is also invertible and sends [f1 ] to [f2 ].
Given the above reduction, here is an algorithm for the general case: we still represent 2-cocycles
by k × |Q|2 matrices over Zp . We first compute a Zp -basis of B 2 (Q, A, θ2 ) as in Proposition 6.5.
Using these 2-cocycles we can represent V and U as solution spaces of homogeneous linear equations.
Finally we apply the polynomial-time Module Cyclicity algorithm [CIK97], either to get that
V is not cyclic, and thus does not contain invertible elements, or to get a generator α0 ∈ V . In the
latter case we conclude based on whether α0 is invertible or not.

37

Computing the coset of isomorphisms. Any single invertible element of V yields an isomorphism. As in Theorem 6.1, a generating set of automorphisms is determined by (1) its image in
Aut(A) × Aut(Q), and (2) the kernel of the natural map Aut(G) → Aut(A) × Aut(Q). In this case,
(1) is easily determined by a generating set of the group of units of U , and (2) is a generalization
of a homomorphism from Q → A called a “derivation,” which we describe below (see, e. g., [Smi94,
Section 3.3]). In the elementary abelian case, the unit group of U can be computed from a linear
basis for U by Theorem 5.7. All that remains is to compute the derivations Q → A.
Recall that, for a section s : Q → G, every element of G is uniquely represented as as(q)
for some a ∈ A, q ∈ Q. Then we have that (as(q))(a0 s(q 0 )) = a(s(q)a0 s(q)−1 )fs (q, q 0 )s(qq 0 ). An
automorphism that fixes both Q and A pointwise is fully determined by a map δ : Q → A, as in
Theorem 6.1, but now satisfying the more general condition:
δ(q)(s(q)δ(q 0 )s(q)1 ) = δ(qq 0 ).
Such maps δ are called derivations. As conjugation of Q on A is an action by automorphisms, this
amounts to |Q|2 homogeneous linear equations in |Q| dim A variables over the field Zp ; such linear
equations can be solved in polynomial time, yielding a generating set for the kernel of the map
Aut(G) → Aut(A) × Aut(Q). Putting this all together yields a generating set for Aut(G).

7

When Aut(Q) is too big

In this section we present polynomial-time algorithms for certain central-radical groups even when
Aut(Q) cannot be enumerated in polynomial time (unconditionally, simply because its size is superpolynomial). In particular, we present two fixed-parameter polynomial-time algorithms for central
radical groups with G/ Rad(G) a direct product nonabelian simple groups, or a direct product of
small perfect groups:
Theorem 7.1. Isomorphism between two groups G1 , G2 with central, elementary abelian radicals
can be decided, and the coset of isomorphisms found, in poly(|Gi |) time if either:
1. G1 / Rad(G1 ) is a direct product of simple groups; or
2. G1 / Rad(G1 ) is a direct product of perfect groups, each of order O(1).
Theorem 7.1 yields polynomial-time algorithms for the following concrete cases, for example:
(1) covers groups with Rad(G) = Z(G) = Zkp and G/Z(G) ∼
= Akm ; (2) covers the case when
k
k
∼
Rad(G) = Z(G) = Zp and G/Z(G) = (A5 o PSL20 (F7 )) , where the wreath product is taken with
respect to any permutation representation of PSL20 (F7 ).
Remark 7.2. In Theorem 7.1(2) we can relax the O(1) size bound to O(f (n)) to get an algorithm
2
that runs in time nO(f (n) log f (n)) . For f (n) = (log log n)1/2−ε for some fixed ε > 0, Theorem 7.1(2)
becomes no(log log n) -time (really-very-nearly-polynomial time).
We remark that while it’s possible that some of the algorithms in this paper could yield practically efficient implementations by using suitable sub-routines (with or without worst-case guarantees), Theorem 7.1(2) is admittedly not practical: the square of the O(1) bound appears in the
exponent of the runtime of the algorithm, and the smallest centerless, indecomposable perfect group
that isn’t simple—since simple groups are handled by the much more efficient algorithm from the
38

first part of the theorem—has order 960 (the group is a semi-direct product of A5 acting on F42 ; see
[HP89, Section 5.3, Group (4,1)]).
For Theorem 7.1, currently we can only work with elementary abelian groups; an open problem
posed in [BCGQ11, Section 7.7], namely the group code equivalence problem over cyclic groups,
seems to be the only current obstacle for part (2); see Observation 7.8. For part (1), we show in
Lemma 7.9 that the cohomological bound can be extended to the general abelian case; however,
essentially the same obstacle as in Section 6.1.2 still needs to be overcome in this approach.
As remarked before, for Theorem 7.1 we need a more detailed understanding of central extensions in this special group class, including the deep Theorem 5.3 [GKKL07]. We also remind the
reader that singly exponential algorithms for Linear Code Equivalence and Coset Intersection play an important role in Theorem 7.1 (1).

7.1

Preparations from cohomology

Let A be an abelian group, and T1 , . . . , T` be perfect, centerless, directly indecomposable groups
(this includes the case in which the Ti are nonabelian simple; in fact, the reader unfamiliar with
perfect groups will not lose too much by
Q just considering the nonabelian simple case instead). For
an extension A ,→ G  Q with Q = i∈[`] Ti , let Ui be the inverse image of Ti in G under the
natural projection from G to Q. The following proposition adapted from Suzuki [Suz86] is crucial
(see Appendix A.5 for a proof).
Proposition 7.3 (Cf. [Suz86, Chapter 6, Proposition 6.5]). Let notations be as above. For i, j ∈ [`],
i 6= j, [Ui , Uj ] = id. That is, ∀x ∈ Ui , ∀y ∈ Uj , xy = yx.
We now consider the Ui not just as subgroups of G, but as extensions A ,→ Ui  Ti . As
Proposition 7.3 shows that [Ui , Uj ] = id for i 6= j, these extensions determine the extension A ,→
G  Q as follows:
Lemma 7.4. Given two central extensions A ,→ Gj  Q (j = 1, 2) with A = Z(Gj ) and Q =
Q`
i=1 Ti , with the Ti perfect, centerless, and indecomposable, let Uj,i be the inverse image of Ti
under the natural projection Gj → Gj /A. The extensions A ,→ Gj  Q (j = 1, 2) are equivalent if
and only if for each i ∈ [`], the extensions A ,→ Uj,i  Ti (j = 1, 2) are equivalent.
Proof. The only if direction is trivial. For the other direction, for j = 1, 2 and i ∈ [`], let fj,i be
the 2-cocycle of the extension A ,→ Uj,i  Ti induced by some section sj,i : Ti → Ui . By standard
cohomology (see, e. g., Appendix A), as U1,i and U2,i are equivalent extensions forQeach i, f1,i − f2,i
is some 2-coboundary bi ∈ B 2 (Ti , A). To show the equivalence of A ,→ Gj  i∈[`] Ti , we only
need to exhibit two 2-cocycles fj for A
Q,→ Gj  Q that differ by a 2-coboundary.
As Q is decomposed uniquely as i Ti (that is,Q
uniquely as subsets of Q, not just up to isomorphism), we can identify elements in Q as from i Ti without ambiguity. Let (p1 , . . . , p` ) and
(q1 , . . . , q` ) be two elements in Q, pi , qi ∈ Ti for i ∈ [`]. Then define b : Q × Q → A as
X
b((p1 , . . . , p` ), (q1 , . . . , q` )) =
bi (pi , qi ).
(7)
i∈[`]

Using the Z-linearity of the coboundary condition, one can verify that b is a 2-coboundary in
B 2 (Q, A).

39

Recall that the 2-cocycle fj,i is induced by the section sj,i : Ti → Ui . We define a section
sj : Q → Gj , as sj ((p1 , . . . , p` )) = sj,1 (p1 ) . . . sj,` (p` ). Let fj be the 2-cocycle induced by sj , then—
noting that for i1 6= i2 , sj,i1 (pi1 ) and sj,i2 (pi2 ) commute by Proposition 7.3—it can be verified
that
X
fj,i (pi , qi ).
(8)
fj ((p1 , . . . , p` ), (q1 , . . . , q` )) =
i∈[`]

Thus f1 − f2 = b ∈ B 2 (Q, A), finishing the proof.
For convenience, in the following we shall call Uj,i the restriction of Gj to Ti and use Gj |Ti to
denote it. The next lemma concerns the direct product structure of the normal part; its proof is
included in Appendix A.5 for completeness.
Lemma 7.5. Let A0 × A00 ,→ G  Q be a central extension of A0 × A00 by Q. Let pA0 : A0 × A00 →
A0 be the projection onto A0 along A00 . If there is a 2-cocycle f : Q × Q → A0 × A00 such that
pA0 ◦ f : Q × Q → A0 is a 2-coboundary, then G is isomorphic (even equivalent) to the direct product
A0 × (G/A0 ).
Furthermore, A0 can be computed in poly(|G|) time using linear algebra over abelian groups.
Using general algorithms for decomposing direct products [KN09, Wil12], we could compute A0
in polynomial time without the “furthermore.” However, in the setting of Lemma 7.5, we give a
much simpler algorithm to compute A0 using linear algebra over abelian groups.

7.2

Warm-up result

The full proof of Theorem 7.1 requires several ideas. To highlight these ideas separately, we start
by proving a warm-up result that only needs some of these ideas. The following result is the same
as Theorem 7.1, except that instead of requiring that the central radical be elementary abelian, it
requires that |Aut(Rad(G))| ≤ poly(|G|). (Formally, these two conditions are incomparable, but
the condition used here “feels” more stringent.)
Proposition 7.6. Isomorphism between two groups G1 , G2 with central radicals can be decided, and
the coset of isomorphisms found, in poly(|G1 |) time if |Aut(Rad(G1 ))| ≤ poly(|G1 |) and either:
1. G1 / Rad(G1 ) is a direct product of simple groups; or
2. G1 / Rad(G1 ) is a direct product of perfect groups, each of order O(1).
log |R|
As a few examples of when the condition on Aut(Rad(G)) holds, note that Aut(R)
√ ≤ |R|
2
for all groups R, and |Aut(Z`pe )| ∼ pe` , so the condition holds if | Rad(G)| ≤ 2O( log |G|) or if
Rad(G) = Z`pe with e`2 log p ≤ O(log |G|).
Q
Proof. Decompose each Gj (j = 1, 2) as an extension of A by Q = i∈[`] Ti , where each Ti is perfect
and directly indecomposable; each Ti is necessarily centerless because A = Rad(G). Regardless of
whether we are in case (1) or (2), this decomposition is algorithmically straightforward by [BCGQ11,
Proposition 2.1]; although it was stated there only for case (1), the same algorithm works in both
cases, because the direct factors are uniquely determined not only up to isomorphism, but as subsets
of Gj , even in the perfect case.

40

Q
Now we group the Ti according to their isomorphism types, identifying Q = i∈[r] Q`i i , where r
is the number of isomorphism types among the Ti , each Qi is isomorphic to some Ti , and the Qi ’s
are pairwise nonisomorphic. In case (1), this can be done as each Ti is generated by 2 elements,
and in case (2) it canQbe done as each Ti hasQsize O(1) by assumption.
Then Aut(Q) ∼
= i∈[r] Aut(Qi ) o S`i ∼
= i∈[r] (Aut(Qi )`i o S`i ). A diagonal of Aut(Q) is an
Q
element in i∈[r] Aut(Qi )`i . All diagonals are enumerable in polynomial time by the n# generators
Q
Q
technique: In case (1), by Fact 5.1, | i∈[r] Aut(Qi )`i | ≤ ( i∈[r] |Qi |2 )`i ) ≤ |Gj |2 , and in case (2),
Q
Q
| i∈[r] Aut(Qi )`i | ≤ ( i∈[r] |Qi |log |Qi | )`i ) ≤ O(1)O(log |Gj |) = poly(|Gj |).
By Lemma 2.3, G1 and G2 are isomorphic if and only if they are pseudo-congruent extensions of
A by Q. The extensions are pseudo-congruent if and only if there is an element of Aut(A) × Aut(Q)
such that, after twisting by this element, the resulting extensions are equivalent. Once an element
of Aut(A) × Aut(Q) is fixed, by Lemma 7.4, the latter problem is reduced to determining the
equivalence of G1 |Ti and G2 |Ti for each i ∈ [`].
Note that the equivalence type of the extension Gj |Ti can be computed in polynomial time by
Theorem 6.1, as Aut(Ti ) can be listed in polynomial time: In case (1) each Ti is generated by 2
elements, and in case (2) each Ti has size O(1).
Q
Having decomposed Gj as A ,→ Gj  i∈[r] Q`i i , the algorithm then proceeds as follows. For
Q
Q
every α ∈ Aut(A), and every diagonal i∈[`] δi of i∈[`] Aut(Ti ), do the following. Apply α−1
and δi to each restricted extension G2 |Ti . Now compute the equivalence types of G2 |Ti . If the
multisetQof equivalence types coming from G1 |Ti is equal to the multiset of equivalence types from
the (α, i δi )-twisted G2 |Ti , then G1 and G2 are pseudo-congruent as extensions, and the algorithm
reports
Q “isomorphic.” On the other hand, if the equivalence of multisets is not detected for any
(α, i δi ) then the algorithm returns “not isomorphic.”
It is obvious that the above procedure runs in polynomial time in |G1 | and |Aut(A)|. We
remark that if Ti1 ∼
6 Ti2 then G1 |Ti1 and the (α, δi2 )-twisted G2 |Ti2 cannot be equivalent. Thus the
=
multiset of equivalence types distinguishes the isomorphism types of Ti ’s automatically. Finally,
it is enough to compare the multisets because we have full symmetric groups S`i acting on the
isomorphic factors.
To find the coset of isomorphisms, note
Q that the preceding algorithm enumerates over every element of Aut(A) and every diagonal of i∈[`] Aut(Ti ). For each such pair, the algorithm determines
a multiset of equivalence types, so the relevant subgroup of S`i is just a set transporter, which
is easily calculated. Compute the derivations and apply Observation 5.2 twice, as in the proof of
Theorem 6.11.

7.3

Proof of Theorem C

Unlike the warm-up result from the previous section, for Theorem 7.1 we can no longer afford
to enumerate Aut(Rad(G)). Avoiding this enumeration leads us to two distinct, more advanced
methods, each of which may have further applications.
Proof of Theorem 7.1. We start as in theQproof of Proposition 7.6. For Gj , j = 1, 2, decompose
it as an extension of A = Zkp by Q = i∈[`] Ti . Classify Ti ’s according to their isomorphism
Q
Q
types and group them together, identifying Q = i∈[r] Q`i i . Then Aut(Q) ∼
= i∈[r] Aut(Qi ) o S`i ∼
=
Q
Q
`
`
i
i
i∈[r] (Aut(Qi ) o S`i ). A diagonal of Aut(Q) is an element in
i∈[r] Aut(Qi ) . All diagonals
#
generators
are enumerable in polynomial time by the n
technique. By Lemma 2.3, G1 ∼
= G2 if and
41

only if they are pseudo-congruent extensions of A by Q. The extensions are pseudo-congruent if
and only if there is an element of Aut(A) × Aut(Q) such that, after twisting by this element, the
resulting extensions are equivalent. Once an element of Aut(A) × Aut(Q) is fixed, by Lemma 7.4,
the latter problem is reduced to determining the equivalence of G1 |Ti and G2 |Ti for each i ∈ [`].
We will also need an additional consequence of Lemma 7.4. For Gj , j = 1, 2, we say a 2-cocycle
fj : Q × Q → A respects the direct factors if there exist fj,i : Ti × Ti → A, i ∈ [`] such that
2
Equation 8 holds. Let Zprod
(Q, A) denote the set of 2-cocycles respecting the direct factors. The
2
proof of Lemma 7.4 shows that Zprod
(Q, A) 6= ∅. Similarly we can define 2-coboundaries that
2
respect the direct factors Bprod (Q, A) using Equation 7. The difference of two cohomologous 22
2
2
cocycles in Zprod
(Q, A) is automatically in Bprod
(Q, A). We define Cprod
(Q, A) as the 2-cochains
P
2
respecting the direct factors. We may view elements of Cprod (Q, A) as k × i∈[`] |Ti |2 matrices,
whose rows are indexedLby [k] and whose columns are indexed by triples (i; p, q) with p, q ∈ Ti .
2
That is, Cprod
(Q, A) = i∈[`] C 2 (Ti , A).
(1) Note that the equivalence type of the extension Gj |Ti can be computed in polynomial time by
Theorem 6.1, as each Ti is generated by 2 elements, and thus Aut(Ti ) can be listed in polynomial
time. The algorithm then proceeds as follows.
Q
Q
As every β ∈ Aut(Q) can be represented as (δ, σ) ∈ ( i Aut(Qi )`i ) o ( i S`i ), it follows that
2
2
(Q, A)) is an invariant subset in Z 2 (Q, A) (resp., B 2 (Q, A)) under the
(Q, A) (resp., Bprod
Zprod
actions of both Aut(A) and Aut(Q). Using Proposition 6.10, for each i ∈ [`] we get projection
πi : C 2 (Ti , A) → Wi for some Aut(A)-invariant Wi ≤ C 2 (Ti , A) such that C 2 (Ti , A) = B 2 (Ti , A)⊕Wi
and πi commutes with the action of Aut(A).
Theorem 5.3 tells us that dim Wi = dim H 2 (Ti , A) ≤ 17.5 dim A, and the “alternative viewpoint”
at the end of Section 6.1.2 implies that Wi is a direct sum of copies of A. By a judicious choice of
basis, we may thus write elements of Wi as k ×17 matrices, in a way that is still Aut(A)-equivariant.
(This does not imply that the 17.5 in Theorem 5.3 can be replaced by 17 in general, but rather
only in the case when Q acts trivially on A.) From now on, let πi denote the composition of the
previous πi , followed by this mappingQonto k × 17 matrices.
For each choice of diagonal δ ∈ i∈[`] Aut(Ti ), we may choose the complements Wi so that
whenever i, j are such that Ti ∼
= Tj , that Wi and Wj are identified by δ. With this choice, we may
2
(Q, A) → W ≤ M (k, 17`) for
direct sum these πi together to get a homomorphism π = πδ : Cprod
2
2
2
(Q, A)⊕W and π commutes
some Aut(A)-invariant W ≤Q
Cprod (Q, A) such that Cprod (Q, A) = Bprod
with the action of Aut(A) × i S`i . For each diagonal δ, the question then is to decide the existence
Q
(id,δ,id) (α,id,σ)
)
. (Note that although (id, id, σ)
of (α, σ) ∈ Aut(A) × ( i S`i ) such that π(f1 ) = π(f2
does not commute with (id, δ, id), we do have that (α, δ, σ) = (id, δ, id)(α, id, σ), since σ is already
“on the right” of δ, and α and δ do commute.)
Let M1 = Mπ(f1 ) . By Lemma 7.5, without loss of generality we may assume M1 is of rank k.
Otherwise Lemma 7.5 splits a direct factor out of the center as A0 × Gj /A0 (although Lemma 7.5
2
2
is concerned with Z 2 (Q, A) and B 2 (Q, A), it is readily adapted to Zprod
(Q, A) and Bprod
(Q, A)).
By the Remak–Krull–Schmidt theorem, we then reduce to testing isomorphism between G1 /A0 and
0
G2 /A0 , where the desired rank condition holds. Lemma 7.5 allows us toQcompute such
Q A ≤ Z(Gj ).
The algorithm thus proceeds as follows. For every diagonal δ = j∈[`] δj of j Tj , compute
(id,δ,id)

π(f1 ) and π(f2

), and let M1 = Mπ(f1 ) and M2 = Mπ(f (id,δ,id) ) . Thus Mj is the matrix of size
2

k × (17`) corresponding to fj .
42

Q
As the action of Aut(A) on the Mi is by left multiplication, and the action of i∈[`] S`i is
by permuting blocks of columns, we treat the Mi as generator matrices of two Zp -linear codes of
dimension k and length 17`. Compute
the coset of equivalences CodeEq(M1 , M2 ) ⊆ S17` using
Q
Theorem 5.4. On the other hand i S`i induces an action on [17`], permuting blocks of size
Q 17,
and these are the only permutations we want. Thus we intersect CodeEq(M1 , M2 ) with i S`i .
If the intersection is nonempty, the algorithm reports “isomorphic.” On the other hand, if for all
diagonals we get empty intersection, then the algorithm returns “not isomorphic.”
To analyze the running time, the outer loop depending on the diagonals is polynomially related
to n. Both the applications of the Linear Code Equivalence algorithm (Theorem 5.4), and
the singly-exponential time algorithm for Coset Intersection ([Luk99]), take time c17` for some
absolute constant c. Since ` ≤ log |G|, this is poly(|G|) time.
(2) This case proceeds as in the previous case, with minor modifications. Now, to decide isomorphism of the centerless, indecomposable, perfect groups Ti we rely on the assumption that they
have size O(1) (since we do not, otherwise, know good bounds on testing them for isomorphism).
Also, in the absence of an analog of Theorem 5.3 for this class of groups, rather than 17`, we use
the naive bound that dim H 2 (Ti , A) ≤ dim C 2 (Ti , A) = |Ti |2 dim A. Let D ≤ O(1) be the maximum
of the |Ti |; then the singly-exponential algorithms for Linear Code Equivalence and Coset
2
Intersection run in time c`D ≤ c`·O(1) ≤ poly(|G|).
Computing the coset of isomorphisms. The algorithm is essentially the same in both cases
(1) and (2). To findQ
a single isomorphism, whenever δ is a diagonal such that the coset intersection
CodeEq(M1 , M2 ) ∩ i S`i is nonempty, we pick a single element σ of this coset intersection. Apply
(δ, σ) ∈ Aut(Q) to the columns of M2 , and then compute using linear algebra a matrix in Aut(A) ∼
=
GL(k, p) that makes M1 equal to the column-permuted M2 .
To find a generating set for the automorphisms of G1 , we proceed as follows. As in Theorems 6.1
and 6.11, we can compute the homomorphisms Q → A using linear algebra; these constitute the
kernel of the map Aut(G1 ) → Aut(A) × Aut(Q). Next, we compute generators of the image of
Aut(G1 ) in Aut(A)
× Aut(Q).QWe apply Observation 5.2 again,
1 ) as an extension
Q viewing `Aut(G
Q
i , we compute the coset
.
For
each
diagonal
δ
∈
Aut(Q
)
of Aut(A) × i Aut(Qi )`i by Q
S
i
i
i `i
intersection CodeEq(M
,
M
)
∩
S
.
The
union
of
these
coset
intersections
generates the image
1
1
`
i
i
Q
of Aut(G1 ) in i S`i . For each of these generators σ, we know which diagonal δ it came from, and
we can compute an α ∈ Aut(A) such that (α, δ, σ) ∈ Aut(G1 ), Q
as in the preceding paragraph. This
gives us lifts of all the generators of the image of
QAut(G1 ) in i S`i . Finally, we need
Q to compute
generators of the kernel of the map Aut(G1 ) → i S`i , as a subgroup of Aut(A) × i Aut(Qi )`i .
For this, we will apply Observation
5.2 one last time. Let Aut0 (G1 ) denote the subgroup of
Q
Aut(G
)
whose
projection
to
S
is
trivial.
We can determine the projection of Aut0 (G1 ) to
1
`
i
i
Q
`i by enumerating over all diagonals, and including only those diagonals δ for which the
Aut(Q
)
i
i
(id,δ,id)
matrix associated to π(f1 ) and the matrix associated to π(f1
) have the same rowspan. For
each one, we lift it to Aut0 (G1 ) by using linear algebra to find an element of Aut(A) ∼
= GL(k, p)
that makes the two matrices equal. Finally, we need to compute generators of the subgroup of
Aut(A) that fix π(f1 ). This proceeds exactly as in Theorem 6.1.

43

7.4

Towards the general abelian case

In this section we give two results headed in the direction of extending Theorem 7.1 from elementary
abelian central radicals to general central radicals. First, we give an alternative proof of Theorem 7.1
(2), without using Proposition 6.10. Avoiding Proposition 6.10 is key, because it may not have an
analogue for the general abelian case (see the remarks at the end of Section 6.1.2). This alternative
proof also has the advantage that it makes clear how to extend to the general abelian case by using
group code equivalence over cyclic p-groups (Observation 7.8). Then we observe that Theorem 5.3
can be extended from modules over fields to general finite ZG-modules, which we expect to be
useful for proving the general abelian case of Theorem 7.1(1).
Alternative proof of Theorem 7.1(2). As in Section 6, let Mfj denote the matrix representation of
fj with row index set [k] and column index set Q × Q. As fj is completely determined by the direct
2
factors, we can focus on Mfj with column indices from ∪i∈[`] Ti × Ti . Thus for fj ∈ Zprod
(Q, A) the
P
2
size of Mfj becomes k × ( i∈[`] |Ti | ).
g
need the following analogue of Proposition 6.6. Let M
fj denote the matrix with
P We will
2
|T
|
columns,
and
whose
first
rows
are
just
M
.
The
remaining
rows will be the union
i
f
j
i∈[`]
2
of bases for B (Ti , Zp ) for each i (see Proposition 6.4).
Q
g
Proposition 7.7. Suppose that M
fj has full rank for j = 1, 2. Fix some diagonal δ ∈
i Aut(Ti )
Q
0
(id,δ,id)
0
g
g
g
g
and let M
. Then the intersection
CodeEq(M
f1 = M f 1
f1 , M f2 ) ∩
i S`i is non-empty if and
Q
only if there exists (α, σ) ∈ Aut(A) × i S`i such that (α, δ, σ) is an isomorphism of f1 and f2 as
cohomology classes.
g
g
Proof. Let N be the number of rows of M
fj , and let b = N − k be the number of rows of Mfj that
g
were added to M
fj compared to Mfj .
Q
0
g
g
(⇒) Suppose CodeEq(M
f1 , M f2 ) ∩
i S`i is non-empty. Then there is some permutation σ ∈
Q
g (δ,σ) = M
g
g
g
f2 . As the last b rows of Mf1 and Mf2
i S`i and some Λ ∈ GL(N, p) such that ΛMf1
2
have the same rowspan (namely,Q
Bprod (Q, A)) and this rowspan is preserved by all permutations
of the columns (i. e., elements of i S`i ), we may assume without loss of generality that Λ has the
following block form:


α γ
Λ=
.
0 η
In other words, to make the row spans of the bottom b rows equal, it is never necessary to add any
multiples of the top k rows to the bottom b rows, as the bottom b rows already have equal row
spans that are preserved by all relevant permutations, in particular, by σ.


id γ
2
The sub-matrix γ contributes by adding elements of Bprod (Q, A) to Mf1 , so that
M f1
0 η
corresponds to a cocycle that is cohomologous to f1 . Finally, the contribution of the sub-matrix
α is to send f1 to a pseudo-congruent cocycle, since α ∈ Aut(A). Therefore we have shown that
(α, δ, σ) is an isomorphism of the cohomology classes f1 , f2 .
Q
(α,δ,σ)
(⇐) Suppose that
f
is
cohomologous
to
f
for
some
α
∈
Aut(A)
and
σ
∈
S`i . Then
2
1


(δ,σ)
α
γ
g
some matrix Λ0 =
will make the first k rows of Λ0 M
equal to the first k rows
f1
0 id
0 g (δ,σ) and M
g
g
of M
f . The last b rows of Λ Mf
f have the same row span, so there is some η such
2

1

2

44




α γ
that Λ =
makes the two matrices equal. (In fact, η will be a block-permutation matrix,
0 η
which permutes the blocks in the same way that δ permutes the factors.) In particular, this shows
Q
0
g
g
that σ is a code equivalence, and hence that CodeEq(M
f1 , M f2 ) ∩
i S`i is nonempty.
To finish the proof of Theorem 7.1 (2), we proceed as follows. First, find a direct decomposition
of Gj [KN09]. If any direct factor is contained in Z(Gj ), set this direct factor aside. Then by
Lemma 7.5, the matrices Mfj will be full rank, even after modding out by coboundaries. The latter
2
g
fact implies that the rank of M
fj is then the rank of Mfj plus the dimension of Bprod (Q, A), in
g
other words, the matrices M
fj are also of full rank.
f1 , M
f2 ) ⊆ Sm using Theorem 5.4. On
Finally, we Q
compute the coset of equivalences CodeEq(M
the other hand i S`i induces an action Q
on [m], which contains the permutations we want. Thus we
need to intersect CodeEq(M1 , M2 ) with i S`i . By Proposition 7.7, if this intersection is nonempty,
the algorithm returns “isomorphic.” If the intersection is empty for all diagonals δ, the algorithm
returns “non-isomorphic.”
To analyze the running time, the outer loop depending on the diagonals is polynomially related
to n. Both the applications of the Linear Code Equivalence algorithm (Theorem 5.4), and the
2
singly-exponential time algorithm for Coset Intersection ([Luk99]), take time cm ≤ c`D for
some absolute constant c, where D is the maximum size of any of the Ti .
Computing the coset of isomorphisms
As in the
 other proof, the key isQto compute the
Q
image of Aut(G1 ) in Aut(A) × i∈[r] Aut(Qi )`i o S`i . For each diagonal
Q δ ∈ i∈[`] Aut(Ti ), we
compute the coset intersectionQof Proposition 7.7, which is a subcoset of i∈[r] S`i . This subcoset
is given by a single element of i∈[r] S`i together with a generating set for the image of Aut(G1 ) in
Q
i∈[r] S`i . Given the diagonal δ and one of the generators σ of this subcoset, we compute an element
α ∈ Aut(A) such that (α, δ, σ) ∈ Aut(G1 ) following the first half of the proof of Proposition 7.7.
The only part unspecified is how to find Λ (in the notation of that proof); given δ and σ, this Λ is
just an arbitrary element of a linear transporter, which is easily computed.
Finally, we need to compute a generating set for the Aut0 (G1 ) (notation as in the
Q first proof of
this theorem). We compute such a generating set by enumerating all diagonals of Aut(Ti ) and
(id,δ,id)
g
computing generators for the linear stabilizers of the rowspan of the matrix M
.
f
1

Given a group A, a group code of length n over A is a subgroup of An . Note that when A = Zp
is a prime field, group codes are the same as linear codes.
Observation 7.8. If the coset of group code equivalences of length n over cyclic p-groups Zpk can
be found in time 2O(n) with arithmetic operations in Zpk at unit cost, then Theorem 7.1 (2) also
holds when Rad(G) = Z(G) is an arbitrary abelian group.
Proof. Following the definition of R(µ) inQSection
d × n matrix M representing
Q i 6.1.1, for a given
a 2-cochain over an abelian group A = ki=1 `j=1
Zpµi,j , let M (p,µ) denote the subgroup of Znpµ
i

that is generated by the corresponding (possibly scaled/quotiented) rows R(p,µ) . That is, M (p,µ) is
the subgroup that is generated by the following: a) the rows of M that correspond to Zpµ factors
0
of A, b) pµ−µ times the rows of M that correspond to Zpµ0 with µ0 < µ; c) the rows of M that
correspond to Zpµ0 with µ0 > µ, taken modulo pµ . (Rows corresponding to primes q 6= p do not
45

contribute to M (p,µ) .) In extending the argument of Theorem 7.1 (2) to arbitrary central radicals,
it is not difficult to show that the corresponding cocycles are isomorphic if and only if there is a
product-respecting automorphism of Q that is simultaneously a code equivalence for each M (p,µ) .
Thus, to solve this we compute, for each pµ that appears as a factor of Rad(G), the coset of code
equivalences of the M (p,µ) . Intersecting these cosets then yields the desired permutations, and the
rest of the proof proceeds as in the theorem.
Finally, we observe that the cohomological bound of Theorem 7.1 extends from elementary
abelian G-modules to general abelian G-modules. Although we do not yet know how to prove
Theorem 7.1 in the general abelian case, because we do not have the general abelian analogue of
Proposition 6.10, we expect the following to be useful.
There are two possible ways to generalize the notion of “dimension” from G-modules over Fp to
general finite G-modules, both of which are potentially useful for complexity analysis of algorithms
for GpI; our result will cover both simultaneously. The first is the log of the cardinality of a
finite G-module M , which we denote `(M ) := log |M | (with the base of the logarithm unspecified,
as the result will hold in any base); this generalizes dimension in that for any Fp G-module M ,
|M | = pdim M . The second measure is the minimal number of generators, d(M ) (which equals
dimension for Fp -modules), which is also equal to the smallest d such that M is a quotient of the
free abelian group Zd . The measure d(M ) is also closely related to the number of direct factors
appearing in the primary decomposition of M ; more precisely, d(M ) is at most the number of direct
factors in the primary decomposition of M , and at least the number of p-primary direct factors
in the primary decomposition of M , for any prime p. The ratio d(H 2 (G, M ))/d(M ) governs the
number of columns that appear in the matrices representing 2-cohomology classes as in the first
proof of Theorem 7.1(1).
Lemma 7.9. For any quasi-simple finite group G, and any finite ZG-module M , `(H 2 (G, M )) ≤
17.5`(M ) and d(H 2 (G, M )) ≤ 17.5d(M ).
If the value 17.5 in [GKKL07, Theorem B] gets improved to a smaller constant c, then the 17.5
in this lemma also immediately can be replaced by c. (The authors of [GKKL07] state that they
believe that with additional work the 17.5 could be replaced by 2.)
Proof. We give the proof for `(·); the same proof works mutatis mutandis for d(·).
M is a finite abelian group, so the Sylow p-subgroups of M are characteristic subgroups,
and
L
∼
therefore are G-invariant. Let Mp denote the Sylow p-subgroup of M . Then M =
p||M | Mp
2
is a direct sum
L decomposition of ZG-modules. As H is additive in its second factor, we have
H 2 (G, M ) ∼
= p||M | H 2 (G, Mp ). Thus, if we can show the result when M is an abelian p-group,
P
P
we are done, for then we have `(H 2 (G, M )) = p||M | `(H 2 (G, Mp )) ≤ p 17.5`(Mp ) = 17.5`(M ).
So we now assume that M is a finite abelian p-group acted on by G. In any abelian p-group,
the p-th powers form a characteristic subgroup, which we denote pM since we are using additive
notation. So pM is a G-submodule, albeit not in general a direct summand. Since H 2 is a left-exact
covariant functor in its second argument, from the exact sequence 0 → pM ,→ M  M/pM → 0,
we get a left exact sequence
0 → H 2 (G, pM ) ,→ H 2 (G, M ) → H 2 (G, M/pM ),

46

in which the final map need not be a surjection. However, even if it is not a surjection, by bounding
the measures of the first and last term of this sequence, we still get a bound on the measure of the
middle term H 2 (G, M ).
Now, let e be the exponent of M (that is, pe M = 0 but pe−1 M 6= 0). We proceed by induction
on e. For e = 1, M is in fact an Fp G-module, and we have that `(H 2 (G, M )) ≤ 17.5`(M ) by
[GKKL07, Theorem B].
For e > 1, we have that `(H 2 (G, M/pM )) ≤ 17.5`(M/pM ) by [GKKL07, Theorem B], since
M/pM is an Fp G-module. Since the exponent of pM is strictly less than the exponent of M ,
we have, by induction, that `(H 2 (G, pM )) ≤ 17.5`(pM ). Thus we have that `(H 2 (G, M )) ≤
`(H 2 (G, pM )) + `(H 2 (G, M/pM )) ≤ 17.5(`(pM ) + `(M/pM )) = 17.5`(M ).

8

Future directions

In this paper we developed an nO(log log n) -time algorithm to test isomorphism of groups with central radicals, extending the results of [BCQ12] and beginning to resolve an open problem from
[BCGQ11]. We also developed an nO(log log n) -time algorithm for groups with elementary abelian
radical (not necessarily central), and polynomial-time algorithms for several prominent subclasses
of central radical groups. The “difficult” cases—those where we do not yet know how to improve
beyond nO(log log n) —seem to be when the radical Rad(G) and the semisimple quotient G/ Rad(G)
√
are roughly of the same size—say both are of order n—and G/ Rad(G) is complicated (without
this last condition, we handle such groups in Theorem 7.1; see Remark 7.2). Although a polynomialtime algorithm for the general case of central radicals remains open, we propose several directions
for extending our work which we believe may now be within reach.

8.1

Abelian radical

A nearby next step is to extend our results to groups with general abelian radicals (not necessarily
central nor elementary abelian):
Open Problem 8.1. Extend Theorem 6.11 to groups whose solvable radicals Rad(G) are general
abelian. Ultimately, decide isomorphism of groups with abelian radicals in polynomial time.
We note that even with the recent algorithm for Module Cyclicity for arbitrary finite modules (not necessarily over a field) [CT15], it is not immediately clear how to generalize the proof
of Theorem 6.11 to the general abelian case. The issue is in the definition of the algebra U : in
order to be closed under addition, we must allow the cocycles to get scaled arbitrarily. However,
if an element of End(A) scales a cocycle by a non-unit in Zpe , it is unclear how to proceed (since
then we cannot argue that by rescaling the endomorphism by the inverse of the scalar, we get an
automorphism, since the scalar has no inverse).
In both Theorems 6.1 and 6.11, we are currently only able to compute the coset of isomorphisms
in the elementary abelian case. This could be generalized to the abelian case of Theorem 6.1 by
resolving the following:
Open Problem 8.2. Extend Theorem 5.7 ([BO08, Rón91]) from matrix algebras over a field to
finite Z-algebras. That is, given a Z-linear spanning set of a finite algebra over Z, compute a
generating set of the group of units in polynomial time.

47

8.2

The Babai–Beals filtration

The Babai–Beals filtration was defined and used in the context of algorithms for matrix groups
[BB99, BBS09]—where the groups are given by a generating set of matrices, and the goal is algorithms which run in time polynomial in the input size, which can be polylogarithmic in |G|. In the
context of GpI, it has also been used successfully in the polynomial-time algorithm for semisimple
groups [BCGQ11, BCQ12].
The Babai–Beals filtration is the following chain of characteristic subgroups:
1 ≤ Rad(G) ≤ Soc∗ (G) ≤ Pker(G) ≤ G,

(9)

where Rad(G) is the solvable radical of G and Soc∗ (G) is the subgroup such that Soc∗ (G)/ Rad(G) =
Soc(G/ Rad(G)). Note that the socle of the semisimple group G/ Rad(G) is a direct product of
non-abelian simple groups. G then acts on this direct product by, amongst other things, permuting
the factors. The final subgroup in the Babai–Beals filtration, Pker(G), consists of those g ∈ G
which do not permute the direct factors of Soc∗ (G)/ Rad(G).
In Theorem 7.1 we make progress on the case of groups G with central radical which further
satisfy G = Soc∗ (G). It is then natural to consider groups with the next step of the Babai–Beals
filtration, G = Pker(G). As a polynomial-time algorithm for isomorphism of semisimple groups G
satisfying G = Pker(G) [BCGQ11] was significantly simpler than the polynomial-time algorithm
for general semisimple groups [BCQ12], we have hope that the following is achievable:
Open Problem 8.3. Extend Theorem 7.1 to groups with central radical which satisfy G =
Pker(G).

8.3

The Cannon–Holt strategy

Cannon and Holt [CH03] suggest the following strategy for computing Aut(G) for a finite group G,
as well as for isomorphism testing (see also [How12], which contains improvements and new ideas
related to this strategy). They consider the following chain of characteristic subgroups:
1 = Nr  Nr−1  · · ·  N1 = Rad(G)  G,

(10)

where the Ni refine the derived series of Rad(G) and each Ni /Ni+1 is elementary abelian. More
specifically, let R(i) be the terms of the derived series of Rad(G); so R(0) = Rad(G), R(1) =
[Rad(G), Rad(G)], and so on. Then the quotients R(i) /R(i+1) are abelian. From an abelian group
we get a characteristic series as follows: first break the abelian group into abelian p-groups for each
p, taking the primes in ascending order. Within an abelian p-group, we take the subgroup of p-th
powers as the largest characteristic subgroup in the series, and then recurse. These groups are
then lifted from the abelian quotients R(i) /R(i+1) back to subgroups of Rad(G) in the natural way.
The algorithm proceeds by first computing Aut(G/N1 ) = Aut(G/ Rad(G)), and then iteratively
computing Aut(G/Ni+1 ) from Aut(G/Ni ).
This chain is convenient for describing known results in the Cayley table model: the case when
Rad(G) = 1 (equivalently r = 1) corresponds to the semisimple case, which can be solved in
polynomial time [BCQ12]. When G = Rad(G) and r = 2, the case of |N2 | and |N1 /N2 | being
coprime can be solved in polynomial time [BQ12]. When |N2 | and |N1 /N2 | are not coprime, this
includes the notorious case of p-groups of class 2. Finally, the present work considers a special case
of r = 2, namely when Rad(G) = Z(G).
48

In light of [BCQ12], in the Cayley table model the second step in the Cannon–Holt strategy—
to compute Aut(G/N2 ) from Aut(G/ Rad(G))—is equivalent to the special case of Problem 8.1 in
which Rad(G) is elementary abelian, which we have solved in nO(log log n) time in Theorem 6.11.
However, even before getting polynomial-time algorithms for groups with general abelian radicals (Problem 8.1), it may be possible to give a reduction from the third step of the Cannon–Holt
strategy to listing isomorphisms of two-step solvable groups. This is headed in the direction of a
formal reduction from general group isomorphism to the solvable case. In a related vein, in Proposition 3.13 we showed how isomorphism of groups whose outer action on Rad(G) is trivial reduces
to isomorphism of central-radical groups and isomorphism of solvable groups.
Open Problem 8.4. Extend Theorems 6.1 and 7.1 to groups whose radicals are two-step solvable,
allowing access to an oracle for listing Aut(Rad(G)).

Acknowledgments
The authors thank Nikki Pfarr for producing Figure 1, and Vipul Naik for Example A.12, as well
as several useful discussions early on. We thank James Wilson and several anonymous referees for
numerous helpful comments and suggestions. We also thank I. Ciocǎnea-Teodorescu for sharing and
discussing the preprint [CT15]. J.A.G. was supported by A. Borodin’s NSERC Grant # 482671.
Y. Q. was supported by the Australian Research Council DECRA DE150100720. Both authors
were supported by NSF grant DMS-1620484 during the preparation of the manuscript.

References
[AG84]

M. Aschbacher and R. Guralnick. Some applications of the first cohomology group.
Journal of Algebra, 90(2):446–460, 1984.

[Asc00]

M. Aschbacher. Finite group theory, volume 10 of Cambridge Studies in Advanced
Mathematics. Cambridge University Press, Cambridge, second edition, 2000.

[AT11]

Vikraman Arvind and Jacobo Torán. Solvable group isomorphism is (almost) in NP ∩
coNP. TOCT, 2(2):4, 2011.

[Bab83]

László Babai. Permutation groups, coherent configurations, and graph isomorphism,
April 1983. D.Sc. Thesis, Hungarian Academy of Sci. (Hungarian).

[Bab95]

László Babai. Automorphism groups, isomorphism, reconstruction. In R. L. Graham,
M. Grötschel, and L. Lovász, editors, Handbook of combinatorics (vol. 2), pages 1447–
1540. MIT Press, Cambridge, MA, USA, 1995.

[Bab08]

László Babai. Coset intersection in moderately exponential time. Chicago J. Theoret.
Comp. Sci., 2008. To appear.

[Bab10]

László Babai. Equivalence of linear codes, 2010. Unpublished manuscript.

[Bab16]

László Babai. Graph isomorphism in quasipolynomial time. In 48th ACM STOC, page
To appear, 2016. Preprint available as arXiv:1512.03547 [cs.DS].

49

[Bae38]

Reinhold Baer. Groups with abelian central quotient group. Trans. Amer. Math. Soc.,
44:357–386, 1938.

[BB99]

László Babai and Robert Beals. A polynomial-time theory of black-box groups I. In
C. M. Campbell, E. F. Robertson, N. Ruskuc, and G. C. Smith, editors, Groups St
Andrews 1997 in Bath, I, volume 260 of London Math. Soc. Lect. Notes, pages 30–64.
Cambr. U. Press, 1999.

[BBS09]

László Babai, Robert Beals, and Ákos Seress. Polynomial-time theory of matrix groups.
In Proc. 41st ACM STOC, pages 55–64. ACM Press, 2009.

[BCGQ11] László Babai, Paolo Codenotti, Joshua A. Grochow, and Youming Qiao. Code equivalence and group isomorphism. In Proc. 22nd SODA, pages 1395–1408, 2011.
[BCQ12]

László Babai, Paolo Codenotti, and Youming Qiao. Polynomial-time isomorphism test
for groups with no abelian normal subgroups - (extended abstract). In ICALP, pages
51–62, 2012.

[BE99]

Hans Ulrich Besche and Bettina Eick. Construction of finite groups. J. Symb. Comput.,
27(4):387–404, 1999.

[BEO02]

Hans Ulrich Besche, Bettina Eick, and E.A. O’Brien. A millennium project: Constructing small groups. Intern. J. Alg. and Comput, 12:623–644, 2002.

[BHZ87]

Ravi Boppana, Johan Håstad, and Stathis Zachos. Does co-NP have short interactive
proofs? Inform. Process. Lett., 25:27–32, 1987.

[BJP97]

W. Bosma, J. J. Cannon, and C. Playoust. The Magma algebra system I: the user
language. J. Symb. Comput., pages 235–265, 1997.

[BKL83]

László Babai, William M. Kantor, and Eugene M. Luks. Computational complexity
and the classification of finite simple groups. In Proc. 24th IEEE FOCS, pages 162–
171. IEEE Comp. Soc., 1983.

[BL83]

László Babai and Eugene M. Luks. Canonical labeling of graphs. In Proc. 15th ACM
STOC, pages 171–183. ACM Press, 1983.

[BL08]

Peter A. Brooksbank and Eugene M. Luks. Testing isomorphism of modules. Journal
of Algebra, 320(11):4020 – 4029, 2008.

[BM88]

László Babai and Shlomo Moran. Arthur–Merlin games: a randomized proof system,
and a hierarchy of complexity classes. J. Computer and Sys. Sci., 36:254–276, 1988.

[BMW15] Peter A. Brooksbank, Joshua Maglione, and James B. Wilson. A fast isomorphism test
for groups of genus 2. arXiv:1508.03033, 2015.
[BO08]

Peter A. Brooksbank and E. A. O’Brien. Constructing the group preserving a system
of forms. Internat. J. Algebra Comput., 18(2):227–241, 2008.

[BQ12]

László Babai and Youming Qiao. Polynomial-time isomorphism test for groups with
Abelian Sylow towers. In 29th STACS, pages 453 – 464. Springer LNCS 6651, 2012.
50

[BW12]

Peter A. Brooksbank and James B. Wilson. Computing isometry groups of Hermitian
maps. Trans. Amer. Math. Soc., 364:1975–1996, 2012.

[CCN+ 85] John Horton Conway, Robert Turner Curtis, Simon Phillips Norton, Richard A. Parker,
and Robert Arnott Wilson. Atlas of Finite Groups: Maximal Subgroups and Ordinary
Characters for Simple Groups. Oxford University Press, 1985.
[CH03]

John J. Cannon and Derek F. Holt. Automorphism group computation and isomorphism
testing in finite groups. J. Symb. Comput., 35:241–267, March 2003.

[CIK97]

Alexander Chistov, Gábor Ivanyos, and Marek Karpinski. Polynomial time algorithms
for modules over finite dimensional algebras. In Proceedings of the 1997 international
symposium on Symbolic and algebraic computation, ISSAC ’97, pages 68–74, New York,
NY, USA, 1997. ACM.

[CT15]

Iuliana Ciocǎnea-Teodorescu. The module isomorphism problem for finite rings and
related results. arXiv:1512.08365 [math.RA], 2015.

[CTW10]

Arkadev Chattopadhyay, Jacobo Torán, and Fabian Wagner. Graph isomorphism is not
AC0 reducible to group isomorphism. In FSTTCS, pages 317–326, 2010.

[ELGO02] Bettina Eick, C. R. Leedham-Green, and E. A. O’Brien. Constructing automorphism
groups of p-groups. Comm. Algebra, 30(5):2271–2295, 2002.
[EM47a]

Samuel Eilenberg and Saunders MacLane. Cohomology theory in abstract groups. I.
Annals of Mathematics, 48(1):pp. 51–78, 1947.

[EM47b]

Samuel Eilenberg and Saunders MacLane. Cohomology theory in abstract groups. II:
Group extensions with a non-abelian kernel. Annals of Mathematics, 48(2):pp. 326–341,
1947.

[FG11]

Lance Fortnow and Joshua A. Grochow. Complexity classes of equivalence problems
revisited. Inform. and Comput., 209(4):748–763, 2011. Also available as arXiv:0907.4775
[cs.CC].

[Fit33]

H. Fitting. Die theorie der automorphismenringe abelscher gruppen und ihr analogon
bei nicht kommutativen gruppen. Mathematische Annalen, 107:514–542, 1933.

[FN70]

V. Felsch and J. Neubüser. On a programme for the determination of the automorphism
group of a finite group. In Pergamon J. Leech, editor, Computational Problems in
Abstract Algebra (Proceedings of a Conference on Computational Problems in Algebra,
Oxford, 1967), pages 59–60, Oxford, 1970.

[GG13]

The GAP Group. GAP—groups, algorithms, and programming, version 4.6.5, 2013.
http://www.gap-system.org/.

[GKKL07] Robert Guralnick, William M. Kantor, Martin Kassabov, and Alexander Lubotzky.
Presentations of finite simple groups: profinite and cohomological approaches. Groups
Geom. Dyn., 1(4):469–523, 2007. Preprint available as arXiv:0711.2817v1 [math.GR].

51

[GQ14]

Joshua A. Grochow and Youming Qiao. Algorithms for group isomorphism via group extensions and cohomology. In IEEE Conference on Computational Complexity (CCC14),
2014. Also available as arXiv:1309.1776 [cs.DS] and ECCC Technical Report TR13-123.

[GQ15]

Joshua A. Grochow and Youming Qiao. Polynomial-time isomorphism test of groups
that are tame extensions - (extended abstract). In Algorithms and Computation 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015,
Proceedings, pages 578–589, 2015.

[GR02]

Mikael Goldmann and Alexander Russell. The complexity of solving equations over
finite groups. Inf. Comput., 178(1):253–262, October 2002.

[GR16]

François Le Gall and David J. Rosenbaum. On the group and color isomorphism problems. CoRR, abs/1609.08253, 2016.

[Gro12]

Joshua A. Grochow. Matrix isomorphism of matrix Lie algebras. In IEEE Conference
on Computational Complexity, pages 203–213, 2012. Also available as arXiv:1112.2012
and ECCC TR11-168.

[GZ91]

Max Garzon and Yechezkel Zalcstein. On isomorphism testing of a class of 2-nilpotent
groups. J. Comput. System Sci., 42(2):237–248, 1991.

[Häm03]

Jean-François Hämmerli. Some remarks on nonconnected compact Lie groups. Enseign.
Math. (2), 49(1-2):67–84, 2003.

[Hat02]

Allen Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002.

[HEO05]

Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien. Handbook of computational group
theory. Chapman and Hall/CRC, London, 2005.

[How12]

David J. A. Howden. Computing automorphism groups and isomorphism testing in
finite groups. PhD thesis, The University of Warwick, 2012. Available at http://
wrap.warwick.ac.uk/50060/1/WRAP_THESIS_Howden_2012.pdf.

[HP89]

Derek F. Holt and W. Plesken. Perfect groups. Oxford Mathematical Monographs.
Oxford University Press, 1989.

[HR07]

Christopher J. Hillar and Darren L. Rhea. Automorphisms of finite abelian groups.
Amer. Math. Monthly, 114(10):917–923, 2007. Available as arXiv:math/0605185
[math.GR].

[IKS10]

Gábor Ivanyos, Marek Karpinski, and Nitin Saxena. Deterministic polynomial time
algorithms for matrix completion problems. SIAM J. Comput., 39(8):3736–3751, 2010.

[Ili85]

Costas S. Iliopoulos. Computing in general abelian groups is hard. Theoret. Comput.
Sci., 41(1):81–93, 1985.

[IQ16]

Gábor Ivanyos and Youming Qiao. Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing, 2016. Unpublished manuscript.

52

[Isa08]

I.M. Isaacs. Finite group theory. Graduate Studies in Mathematics Series. American
Mathematical Society, 2008.

[Kav07]

Telikepalli Kavitha. Linear time algorithms for Abelian group isomorphism and related
problems. J. Comput. Syst. Sci., 73(6):986–996, 2007.

[KN09]

Neeraj Kayal and Timur Nezhmetdinov. Factoring groups efficiently. In ICALP ’09:
Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pages 585–596. Springer-Verlag, 2009. Also availabe as ECCC Tech Report
TR08-074.

[KST93]

Johannes Köbler, Uwe Schöning, and Jacobo Torán. The graph isomorphism problem:
its structural complexity. Birkhauser Verlag, Basel, Switzerland, Switzerland, 1993.

[Laz54]

M. Lazard. Sur les groupes nilpotents et les anneaux de lie. Gauthier-Villars, 1954.

[LG09]

François Le Gall. Efficient isomorphism testing for a class of group extensions. In Proc.
26th STACS, pages 625–636, 2009.

[Luk82]

Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial
time. J. Comp. Sys. Sci., 25:42–65, 1982.

[Luk91]

Eugene M. Luks. Permutation groups and polynomial-time computation. In Proc.
Workshop on Groups and Computation, DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, 1991.

[Luk99]

Eugene M. Luks. Hypergraph isomorphism and structural equivalence of boolean functions. In Proc. 31st ACM STOC, pages 652–658. ACM Press, 1999.

[LW12]

Mark L. Lewis and James B. Wilson. Isomorphism in expanding families of indistinguishable groups. Groups - Complexity - Cryptology, 4(1):73–110, 2012.

[Mil78]

Gary L. Miller. On the n log n isomorphism technique (a preliminary report). In STOC,
pages 51–58, New York, NY, USA, 1978. ACM.

[Mul11]

Ketan Mulmuley. On P vs. NP and geometric complexity theory. J. ACM, 58(2):5,
2011.

[Nai10]

Vipul Naik. Isomorphic extensions that are not pseudo-congruent. Personal communication, 2010.

[Nai12]

Vipul Naik. Group extension problem. http://groupprops.subwiki.org/wiki/
Group_extension_problem, December 2012.

[O’B94]

E.A. O’Brien. Isomorphism testing for p-groups. Journal of Symbolic Computation,
17(2):133 – 147, 1994.

[PR97]

Erez Petrank and Ron M. Roth. Is code equivalence easy to decide? IEEE Transactions
on Information Theory, 43:1602–1604, 1997.

[QST11]

Youming Qiao, Jayalal M. N. Sarma, and Bangsheng Tang. On isomorphism testing of
groups with normal Hall subgroups. In Proc. 28th STACS, pages 567–578, 2011.
53

[Ran07]

A. Ranum. The group of classes of congruent matrices with application to the group
of isomorphisms of any abelian group. Transactions of the American Mathematical
Society, 8(1):71–91, 1907.

[Rob82]

D.J.S. Robinson. Applications of cohomology to the theory of groups. In Groups – St
Andrews 1981, volume 71 of London Math. Soc. Lect. Notes, pages 46–80. Cambridge
University Press, 1982.

[Rob96]

Derek J.S. Robinson. A Course in the Theory of Groups. Springer, 2nd edition, 1996.

[Rón91]

Lajos Rónyai. Computing the order of centralizers in linear groups. Inform. and Comput., 91(2):172–176, 1991.

[Ros13a]

David Rosenbaum. Bidirectional collision detection and faster algorithms for isomorphism problems. arXiv:1304.3935 [cs.DS], 2013.

[Ros13b]

David Rosenbaum. Breaking the nlog n barrier for solvable-group isomorphism. In Proc.
24nd SODA, 2013.

[Rot94]

J.J. Rotman. An Introduction to the Theory of Groups. Graduate Texts in Mathematics.
Springer, 1994.

[Sav80]

Carla Savage. An O(n2 ) algorithm for Abelian group isomorphism. Technical report,
North Carolina State University, 1980.

[Ser03]

Ákos Seress. Permutation Group Algorithms. Cambridge University Press, 2003.

[Smi94]

Michael J. Smith. Computing automorphisms of finite soluble groups. PhD thesis, Australian National University, 1994. Available at http://www.mathe2.uni-bayreuth.
de/axel/papers/smith:computing_automorphisms_of_finite_soluble_groups.
ps.gz; summary in Bull. Austral. Math. Soc. 53:169–171, 1996.

[Ste62]

Robert Steinberg. Generators for simple groups. Canadian Journal of Mathematics,
14:277–283, 1962.

[Suz82]

M. Suzuki. Group Theory I. Springer, 1982.

[Suz86]

M. Suzuki. Group Theory II. Springer, 1986.

[Tau55]

D. R. Taunt. Remarks on the isomorphism problem in theories of construction of finite
groups. Mathematical Proceedings of the Cambridge Philosophical Society, 51:16–24,
1955.

[Vik96]

Narayan Vikas. An O(n) algorithm for Abelian p-group isomorphism and an O(n log n)
algorithm for abelian group isomorphism. J. Comput. Syst. Sci., 53(1):1–9, 1996.

[Wag11]

Fabian Wagner. On the complexity of group isomorphism. Technical Report TR11-052,
Electronic Colloquium on Computational Complexity (ECCC), 2011.

[War76]

R.B. Warfield. Nilpotent Groups. Number 513 in Lecture Notes in Mathematics; 513.
Springer-Verlag, 1976.
54

[Wil09a]

James B. Wilson. Decomposing p-groups via Jordan algebras. J. Algebra, 322:2642–
2679, 2009.

[Wil09b]

James B. Wilson. Finding central decompositions of p-groups. J. Group Theory, 12:813–
830, 2009.

[Wil12]

James B. Wilson. Existence, algorithms, and asymptotics of direct product decompositions, I. Groups Complex. Cryptol., 4(1):33–72, 2012.

[Wil13]

James B. Wilson. More characteristic subgroups, Lie rings, and isomorphism tests for
p-groups. Journal of Group Theory, 16(6):875–897, 2013.

[Wil14]

James Wilson. 2014 conference on Groups, Computation, and Geometry at Colorado
State University, co-organized by P. Brooksbank, A. Hulpke, T. Penttila, J. Wilson,
and W. Kantor. Personal communication, 2014.

A

A gentle introduction to group extensions and cohomology

In this appendix we present a gentle introduction to group extensions and cohomology from the
viewpoint of isomorphism testing, for readers encountering such notions for the first time. While
this content exists in many textbooks, the typical textbook treatments often require reading several
chapters first; our goal here is to cover the needed material in a self-contained, leisurely and
expository manner.

A.1

An intuitive starting point

Suppose we have a group G with a normal subgroup N , whose quotient G/N we call Q. We write
this as N ,→ G  Q, and refer to G as an extension of N by Q (some authors use the opposite
convention, and call this as an extension of Q by N ). Given N and Q, what additional data
determines G up to isomorphism?
If G is the direct product N × Q, then we essentially need no additional information.
A slightly more complicated kind of extension is captured by the semi-direct product: In a
direct product, G contains subgroups N and Q ∼
= Q such that G = N Q = {nq : n ∈ N, q ∈ Q}
and N ∩ Q = 1, and both N and Q are normal. As a consequence, every element of n commutes
with every element of Q. A semi-direct product is defined similarly, except that Q need no longer
be normal, and consequently the elements of Q need no longer commute with the elements of N .
However, as N is normal, given any q ∈ Q, qN q −1 = N , so the map ϕ : Q → Aut(N ) given by
sending q to the map (n 7→ qnq −1 ) gives an action of Q on N . We denote this semi-direct product
by N oϕ Q. (When the action is trivial, we recover the direct product.) So to specify G from N
and Q, we also need to specify something about this action.
However, consider the two groups Z2 × Z2 and Z4 , both as extensions of Z2 by Z2 . (For Z4 ,
written additively, we have {0, 2} ∼
= Z2  Z4 , with the quotient Z4 /Z2 again being a copy of Z2 .
The quotient map is the parity map.) However, these two extensions are not distinguished by
any action of the quotient on the normal subgroup: In Z2 × Z2 this action is trivial, as always
happens for direct products; in Z4 , since Z4 is abelian, conjugation by any element of Z4 is trivial,
so the action of Q ∼
= Z2 on N ∼
= Z2 is also trivial. If we think of the group elements in both cases
55

as specified by length-2 binary strings, the difference between the groups is that when adding in
Z4 , one must perform carries, whereas in Z2 × Z2 one does not. Carrying is a simple example of
nontrivial cohomology.
How can we capture this difference formally? Note that in the case of Z4 , there is no choice
of coset representatives of Z2 such that the coset representatives themselves form a subgroup; that
is, there is no subgroup Q as in the discussion of semi-direct product above. It turns out that
measuring the failure of the existence of such a subgroup is precisely what we need to capture the
difference between Z4 and Z2 × Z2 ; as we will see, in this case, this “measure of failure” will turn
out to be described exactly by carrying.
Let N = Z2 , G = Z4 , and Q = G/N = Z2 , and let π : G → Q denote the natural quotient map.
Let s : Q → G denote any choice of coset representatives; that is, π(s(q)) = q for all q ∈ Q. If there
were a subgroup Q as above, then there would be some choice of s so that s is a homomorphism
∼
=
(and, in fact, it is not hard to see that such an s would be an isomorphism Q → Q). So we will
measure the failure of s to be a homomorphism, and then consider this measure over all possible s.
For s to be a homomorphism is to say precisely that s(p)s(q) = s(pq) for all p, q ∈ Q, or
equivalently that s(p)s(q)s(pq)−1 = 1 for all p, q ∈ Q. We will use this expression to measure the
failure of s to be a homomorphism, and say that the failure of s to be a homomorphism is exactly
captured by the function fs (p, q) := s(p)s(q)s(pq)−1 . This function is identically 1 if and only if s
is a homomorphism. Any fs of this form is called a 2-cocycle, and all such 2-cocycles arise in this
fashion. We then define:
Definition A.1 (Provisional definition of a cohomology class). The 2-cohomology class of an
extension N ,→ G  Q is the collection [fs ] := {fs |s : Q → G is a choice of coset representatives}.
Before understanding what this collection is, let us return to our example.
Example A.2. The map π : Z4 → Z2 maps {0, 2} 7→ 0 and {1, 3} →
7 1. So we have four choices
for s : Z2 → Z4 :
(
(
(
(
0 7→ 0
0 7→ 0
0 7→ 2
0 7→ 2
s0
s1
s2
s3
1 7→ 1
1 7→ 3
1 7→ 1
1 7→ 3
We calculate fs0 for exposition, and leave the calculation of the remaining fsi to the reader. Since
we are writing Z4 and Z2 additively, our expression for fs becomes s(p) + s(q) − s(pq).
fs0 (0, 0)
fs0 (0, 1)
fs0 (1, 0)
fs0 (1, 1)

=
=
=
=

s0 (0) + s0 (0) − s0 (0 + 0)
s0 (0) + s0 (1) − s0 (0 + 1)
s0 (1) + s0 (0) − s0 (1 + 0)
s0 (1) + s0 (1) − s0 (1 + 1)

=
=
=
=

s0 (0)
s0 (0)
s0 (0)
1+1−0

=
=
=
=

0
0
0
2

There are two things to note. First, every fs0 (p, q) actually landed in the normal subgroup N =
{0, 2}; as we will see in a moment, this was no accident. Second, fs0 is exactly the carry function:
If we write the values in Z4 in binary, then fs0 (p, q) was 00 except when p = q = 1, when it was 10.
This should help give some intuition for what a cohomology class “really is.” It is easily verified
that none of the fsi are trivial (with image 0), so this extension is not a semi-direct product, as we
already knew.

56

Note that the cohomology class depends not only on G, but also on the choice of N (see
Example A.12), and on the choice of map π : G → Q (see Example A.8). We will give examples
of both of these in the next section, after we’ve developed some more structure on cohomology
classes, which will make the examples clearer. (At first, the reader may find the dependence on
π surprising, since given N , we think of Q as being the same as G/N , for which there is the
natural map g 7→ gN . However, note that for any given map π : G → Q with kernel N , and any
automorphism β ∈ Aut(Q), the map β ◦ π : G → Q is also a homomorphism G → Q with kernel
N , and it is this choice that is relevant.)

A.2

The group structure on cohomology

Defining the cohomology class as {fs |s : Q → G} is a perfectly fine definition, but what is this
collection? It turns out that, when N is abelian, this collection is a coset of a subgroup of some
group, as we now explain. For the remainder of this appendix, N will be abelian, so we will denote
N by A. In A we will use additive notation; although A ≤ G and G need not abelian, this will
turn out not to cause much confusion, and using this notation helps simplify things greatly.
Let C 2 (Q, A) denote the group of all functions (not necessarily homomorphisms) Q × Q → A;
C 2 (Q, A) is an abelian group under pointwise addition: (f + g)(p, q) := f (p, q) + g(p, q). Elements
of C 2 (Q, A) are called “2-cochains of Q with coefficients in A.” First, we show that any fs as
above is in fact a 2-cochain. To show this, we need merely show that fs (p, q) ∈ A for all p, q ∈ Q.
Recalling that A = Ker(π), we apply π : G → Q to fs (p, q):
π(fs (p, q)) = π(s(p)s(q)s(pq)−1 ) = π(s(p))π(s(q))π(s(pq)−1 ) = pq(pq)−1 = idQ ,
so fs (p, q) is indeed in Ker(π) = A. So fs is an element of the abelian group C 2 (Q, A).
However, not every 2-cochain arises in this manner; it turns out that those that do are a
subgroup of C 2 (Q, A). To determine this subgroup, we need to determine the constraint that all fs
as above satisfy. One constraint comes from the fact that multiplication in G is associative; it will
turn out that this one constraint suffices (that is, any 2-cochain satisfying this associativity-like
constraint will be of the form fs for some choice of coset representatives s : Q → G).
To derive this associativity-like constraint, let us write the elements of G in terms of those of A
and Q. Let s : Q → G be a choice of coset representatives; then every element of G can be written
uniquely as as(q) for some a ∈ A, q ∈ Q. Let’s determine what the product in G looks like when
we represent elements of G in this form:
(as(p))(bs(q)) = as(p)b(s(p)−1 s(p))s(q)
= a(s(p)bs(p)−1 )s(p)s(q)
= aθp (b)s(p)s(q)
= aθp (b)s(p)s(q)s(pq)−1 s(pq)
= aθp (b)fs (p, q)s(pq)

In other words, if we use the notation (a, q)s to mean as(q), then we have
(a, p)s · (b, q)s = (a + θp (b) + fs (p, q), pq)s .

57

(11)

Exercise. Using Equation (11), expand out the two expressions ((a, p)s · (b, q)s ) · (c, r)s and (a, p)s ·
((b, q)s · (c, r)s ) (note that the order of parentheses matters for the syntactic form of the final
expressions; don’t just assume associativity!).
Since multiplication in G is associative, the two expressions in the preceding exercise must be
equal. Expanding them out and setting them equal, we find that fs must satisfy the condition:
fs (p, q) + fs (pq, r) = θp (fs (q, r)) + fs (p, qr)

(the 2-cocycle identity).

Reversing the above reasoning, we find that given an action θ : Q → Aut(A), any 2-cochain f : Q ×
Q → A which satisfies the 2-cocycle identity arises as fs for some extension A ,→ G  Q and
some choice of coset representatives s : Q → G. Any 2-cochain f satisfying the 2-cocycle identity
is called a 2-cocycle (with respect to the action θ). Since the 2-cocycle identity is easily seen to
be Z-linear—if f and g are both 2-cocycles, then so is their pointwise sum f + g—the 2-cocycles
form a subgroup of the 2-cochains, which we denote Z 2 (Q, A, θ) (unlike 2-cochains, the 2-cocycle
identity depends on the action θ). Thus each cohomology class (with respect to θ) is a subset of
Z 2 (Q, A, θ)
Finally, let us determine what kind of subset a cohomology class is. Towards this end, suppose
s, t : Q → G are two choices of coset representatives of Q in G. What is the difference between
fs and ft ? As s(q) and t(q) lie in the same coset of A, there is a function u : Q → A such that
s(q) = u(q)t(q) for all q ∈ Q. Then fs (p, q) = ft (p, q) + (u(p) + θp (u(q)) − u(pq)), where θp : A → A
is the automorphism given by conjugation by p ∈ Q. A 2-coboundary is a function of the form
bu (p, q) := u(p) + θp (u(q)) − u(pq) for any function u : Q → A. Hence, if two 2-cocycles come from
the same extension, they differ by a 2-coboundary.
Now, for a 2-coboundary of the form fs − ft , it is clear that it lies in Z 2 (Q, A, θ), since both fs
and ft are elements of this group. More generally, we have:
Exercise. Show that any 2-coboundary satisfies the 2-cocycle identity. Show that if fs is a 2cocycle corresponding to the extension A ,→ G  Q, and bu is any 2-coboundary, then fs + bu is
another 2-cocycle corresponding to the same extension.
Thus, the 2-coboundaries are elements in Z 2 (Q, A, θ). Finally, note that for any two functions
u, v : Q → A, we have bu+v = bu + bv , so the 2-coboundaries in fact form a subgroup of Z 2 (Q, A, θ),
which we denote B 2 (Q, A, θ). Thus, we have finally arrived at:
Definition A.3. A 2-cohomology class is an element of the abelian group Z 2 (Q, A, θ)/B 2 (Q, A, θ).
We denote this quotient group H 2 (Q, A, θ), called the second cohomology group of Q with coefficients in A, relative to the action θ.
We thus arrive at one of the central notions in this paper:
Definition A.4. For A an abelian group and Q any group, a pair (θ, f ) of an action θ : Q → Aut(A)
and a 2-cocycle f : Q × Q → A, f ∈ Z 2 (Q, A, θ) is extension data. Two extension data for the pair
(Q, A) are equivalent if they have the exact same action and if the two 2-cocycles are cohomologous
(differ by a coboundary).
Given an extension A ,→ G  Q, the extension data for this particular extension are the action
θ as defined above, and any 2-cocycle fs for any section s : Q → G. Note that extension data are
non-unique, as we may choose any representative of the corresponding 2-cohomology class.
Two important special cases of extension data (θ, f ) are as follows.
58

f is trivial (as 2-cohomology class). This implies that there exists P ≤ G such that AP = G
and P ∩ A = id, i. e., that G is the semi-direct product A o P . Such P is called a complement
of A in G, and the extension is called a split extension. In this case, an isomorphism test
need only focus on one of the two aspects of GpI: Extension Data Pseudo-congruence
simplifies to Action Compatibility.
θ is trivial. This implies that A ≤ Z(G), and the extension is called central. In this case, an
isomorphism test need only focus on the other aspect of GpI: Extension Data Pseudocongruence simplifies to Cohomology Class Isomorphism.
Remark A.5. It is not difficult to test whether an input satisfies one of the above conditions: it is
trivial to test whether an extension is central. We leave it as an exercise for the interested reader
to devise an algorithm to test whether an extension is split when the normal subgroup is abelian.
See [HEO05, Section 7.6.2] for a practical algorithm for the latter problem.

A.3

Equivalence of extensions and extension data

Now that we see there is a group structure on H 2 (Q, A, θ), we return to give examples of the
dependence on A and π : G → Q. For this, we introduce a standard, slightly different viewpoint on
the notion of “equivalence.”
Definition A.6. Two extensions of A by Q, G1 and G2 , are equivalent if there exists an isomorphism γ : G1 → G2 such that, in the following diagram


A

ι1

/ G1

π1

//Q

π2

//Q

∼
= γ

A



ι2


/ G2

we have γι1 = ι2 and π1 = π2 γ, in which case we say that the diagram commutes. The vertical
double-lines are stretched out, rotated equality signs; that is, they denote the identity map.
It is classical, going back to O. Hölder and O. Schreier, that two extensions have equivalent
extension data (Definition A.4) if and only if the extensions are equivalent according to Definition A.6. The explicit connection with cohomology was developed by Eilenberg and Mac Lane
[EM47b].
Theorem A.7 (See [Rob96, Chapter 11] and Eilenberg–Mac Lane [EM47b]). There is a bijection
between equivalence classes of extensions of A by Q with action θ, and elements of the group
H 2 (Q, A, θ).
Now we give the promised example of the dependence of the cohomology class on the choice of
map π : G → Q. This example also serves a secondary purpose, as an example of two extensions
where G1 ∼
= G2 but the extensions are not equivalent according to the above definition(s).
Example A.8 (Isomorphic groups from non-equivalent extensions). Z9 can be viewed as an extension of Z3 by Z3 in two ways. First, Z3 ,→ Z9 by sending 1 to 3. Then define πi (1) = i for i ∈ [2].
To see that π1 and π2 yield non-equivalent extensions, consider any φ ∈ Aut(Z9 ). Let k = φ(1);
since φ is an automorphism, k is one of {1, 2, 4, 5, 7, 8}. In order for φ to be an equivalence of
59

extensions, it must induce the identity on h3i, implying that 3 = φ(3) = 3φ(1) = 3k mod 9, so
k mod 3 must be 1 mod 3. On the other hand, to be an equivalence of extensions, we must also
have 1 = π1 (1) = π2 (φ(1)) = π2 (k) = 2k mod 3, that is k = 2 mod 3, giving a contradiction.
Given the preceding example, the question then becomes how to leverage cohomology for isomorphism testing (since what we’ll ultimately care about is the isomorphism class of G, and not
merely the equivalence class of any given extension with G as its total group). This is what we
tackle next.

A.4

Main lemma for abelian characteristic subgroups

Recall that a characteristic subgroup is a subgroup invariant under all automorphisms. The analogous notion for isomorphisms (rather than automorphisms) is a function S that assigns to each
group G a subgroup S(G) ≤ G such that any isomorphism ϕ : G1 → G2 restricts to an isomorphism
ϕ|S(G1 ) : S(G1 ) → S(G2 ). We call such a function a characteristic subgroup function. Note that if
G1 = G2 , this says that S(G1 ) is sent to itself by every automorphism of G1 , that is, S(G1 ) is a
characteristic subgroup of G1 . Most natural characteristic subgroups encountered are characteristic
subgroup functions, for example the center Z(G), the commutator subgroup [G, G], or the radical
Rad(G).
Let S denote a fixed characteristic subgroup function, and suppose we are given two groups
G1 , G2 such that S(G1 ) and S(G2 ) are both abelian. To determine how to use cohomology in
isomorphism testing, we first examine the consequences of an isomorphism G1 ∼
= G2 , as an exercise
in reverse engineering. Let γ : G1 → G2 be an isomorphism. By the definition of characteristic
subgroup function, γ(S(G1 )) = S(G2 ), so γ induces γ1 : S(G1 ) → S(G2 ) and γ2 : G1 /S(G1 ) →
G2 /S(G2 ). Using these isomorphisms, we identify A = S(G2 ) = S(G2 )γ1 and Q = G2 /S(G2 ) =
(G2 /S(G2 ))γ2 . Let (θi , fi ) be the extension data of A ,→ Gi  Q, where θi : Q → Aut(A) and
fi ∈ Z 2 (Q, A, θi ). As we have identified A = S(G1 ) = S(G2 ) and Q = G1 /S(G1 ) = G2 /S(G2 ), γ
induces some α ∈ Aut(A) and β ∈ Aut(Q). We write θi,q as the shorthand for θi (q) for i = 1, 2 and
q ∈ Q. It can then be verified that for q ∈ Q and a ∈ A,
(α,β)

θ1,q (a) = α−1 (θ2,β(q) (α(a))) =: θ2
(α,β)

(q)(a),

(12)

(α,β)

and we record this as θ1 = θ2 , where θ2
is defined as above.
(α,β)
It can be similarly verified that [f1 ] = [f2
] as cohomology classes in H 2 (Q, A, θ1 ), where
(α,β)
f2
(p, q) := α−1 (f2 (β(p), β(q))) for all p, q ∈ Q. In other words, we have:
f1 (p, q) = α−1 (f2 (β(p), β(q))) + bu (p, q)

(13)
(α,β)

for some 2-coboundary bu ∈ B 2 (Q, A, θ1 ). Note that Equation 12 ensures f2
is indeed a 2-cocycle
relative to θ1 , i. e., in Z 2 (Q, A, θ1 ). This discussion leads to the following definition:
Definition A.9. Let A be an abelian group and Q any group, and let (θ1 , f1 ) and (θ2 , f2 ) be
two extension data for A-by-Q. Then the extension data are pseudo-congruent 8 if there exists
(α,β)
(α,β)
(α, β) ∈ Aut(A) × Aut(Q), such that θ1 = θ2
and [f1 ] = [f2
], that is, Equations (12) and
(13) hold. In this case we write (θ1 , f1 ) ∼
(θ
,
f
).
= 2 2
8

See Footnote 3 on page 8.

60

Lemma A.10 (Main Lemma, abelian case). Let S be a characteristic subgroup function. Given
two finite groups G1 and G2 , suppose S(G1 ) and S(G2 ) are abelian. Then G1 ∼
= G2 if and only if
both of the following conditions hold:
1. S(G1 ) ∼
= G2 /S(G2 ) (which we denote by Q);
= S(G2 ) (which we denote by A) and G1 /S(G1 ) ∼
2. (θ1 , f1 ) ∼
= (θ2 , f2 ), where (θi , fi ) is the extension data of the extensions A ,→ Gi  Q.
Proof. The above discussion shows the only if direction. For the other direction, suppose we are
given an abelian group A, a group Q, an action θ : Q → Aut(A), and a 2-cocyle f : Q × Q → A,
f ∈ Z 2 (Q, A, θ). We shall need the following procedure of Eilenberg and Mac Lane [EM47b] that
takes A, Q, θ and f as input, and outputs a group H as an extension of A by Q with extension
data (θ, f ). We refer to this as the standard reconstruction procedure. The set of group elements of
H is A × Q. For (a, p), (b, q) ∈ A × Q, the group operation ◦H is defined as
(a, p) ◦H (b, q) = (a + θp (b) + f (p, q), pq).
A simple but tedious calculation verifies that A ,→ H  Q is an extension with extension data
(θ, f ).
Getting back to our problem, from (θ1 , f1 ) ∼
= (θ2 , f2 ), we can choose appropriate sections
(α,β)
si : Q → Gi such that the corresponding 2-cocycles satisfy f1 = f2
in Z 2 (Q, A, θ1 ). Note
(α,β)
(α,β)
that as θ1 = θ2 , f2
∈ Z 2 (Q, A, θ1 ). Now apply the standard reconstruction procedure to
∼
(θi , fi ) to get Hi = Gi (isomorphism follows from Eilenberg and Mac Lane [EM47a]. It is then
straightforward to verify that the bijection γ : H1 → H2 defined by γ((a, p)) = (α(a), β(p)) is in
fact an isomorphism.
A.4.1

Pseudo-congruence of extensions and extension data

As with the the standard concept of equivalence, the standard concept of pseudo-congruence applies
directly to group extensions themselves, rather than extension data as in our definitions. We use our
definitions because the standard definitions seem to presuppose that the total groups are isomorphic,
whereas in our setting the whole goal is to determine whether this is the case. However, we show
in this section that the definitions are in fact equivalent (which is closely related to the Main
Lemma 2.3). We present the standard definition here as it has more intuitive appeal and we believe
it makes some discussions in the paper clearer, for example the proof of Theorem 7.1.
Throughout this section, A denotes an abelian (normal sub-)group. Non-abelian normal subgroups are handled in Section 3.
Definition A.11. Two extensions A ,→ Gi  Q (i = 1, 2) of A by Q are pseudo-congruent if
there is an isomorphism γ : G1 → G2 such that γ(A) = A. In particular, γ induces automorphisms
α ∈ Aut(A) and β ∈ Aut(Q).
Pictorially, G1 and G2 are pseudo-congruent as extensions if there exist α ∈ Aut(A), β ∈ Aut(Q)
and γ ∈ Iso(G1 , G2 ) such that the following diagram commutes:
A



ι1

A

π1

∼
= γ

∼
= α

 


/ G1

ι2



/ G2

61

//Q
∼
= β

π2


//Q

where ιi is the injective homomorphism from A to Gi and πi is the surjective homomorphism from
Gi to Q with Ker(πi ) = Im(ιi ).
It is possible for the total groups G1 and G2 to be isomorphic without the extensions being
pseudo-congruent. The following example was provided by Vipul Naik [Nai10]. This, finally, also
serves as an example of the dependence on the choice of A.
Example A.12 (Isomorphic groups from non-pseudo-congruent extensions). A = Zp2 × Zp × Zp ,
Q = Zp2 × Zp , G = Zp3 × Zp2 × Zp × Zp . In one extension, ι1 (a, b, c) = (pa, 0, b, c) and in the
other ι2 (a, b, c) = (pa, pb, a (mod p), c). To see that there is no automorphism of G sending Im ι1
to Im ι2 —and hence that the two extensions are not pseudo-congruent—note that Im ι1 contains
elements that are p times an element of order p3 in G, but Im ι2 contains no such elements.
Despite the fact that the usual Definition A.11 presupposes that the total groups are isomorphic,
in fact it is equivalent to our Definition A.9. The isomorphism of the total groups follows for free
from pseudo-congruence of the extension data:
Lemma A.13. Definitions A.9 and A.11 are equivalent. In detail: let A ,→ Gi  Q (i = 1, 2)
be extensions of A by Q, and let (θi , fi ) be the corresponding extension data. Then G1 and G2 are
pseudo-congruent as extensions of A by Q if and only if (θ1 , f1 ) ∼
= (θ2 , f2 ).
Proof. Suppose that the extensions are pseudo-congruent (Definition A.11), and let γ ∈ Iso(G1 , G2 ),
(α,β)
α ∈ Aut(A), β ∈ Aut(Q) be as in Definition A.11. It is readily verified that θ1 = θ2
and
(α,β)
[f1 ] = [f2
], that is, that the extension data are pseudo-congruent under Definition A.9.
Conversely, suppose the extension data are pseudo-congruent (Definition A.9). Then the isomorphism γ constructed in the proof of the Main Lemma 2.3 satisfies the conditions of Definition A.11.
A.4.2

Some algorithmic problems arising from special cases of pseudo-congruence

We describe two special cases of pseudo-congruence of extensions, explain the algorithmic problems
corresponding to them, and indicate some of the solutions. The first one was discussed in [Rob82].
Consider the case when a pseudo-congruence γ induces the identity map on Q as follows:
A



ι1

∼
= α

 


A

/ G1

π1

//Q

π2

//Q

∼
= γ

ι2


/ G2

This corresponds to the algorithmic setting when enumerating Aut(Q) is allowed (Section 6), as
after fixing some β ∈ Aut(Q) we are reduced to looking for α such that G1 and G2 are pseudocongruent via (α, β). If the extension is split and A ∼
= Zkp is elementary abelian, this problem
reduces to Module Isomorphism: the action of each q ∈ Q can be expressed as a nonsingular
matrix in GL(k, p). So suppose Q = {q1 , . . . , qs }, and in Gj the conjugation action of Q is written
as {M (j, i) | M (j, i) ∈ GL(k, p)} where M (j, i) denotes the action of qi on A in Gj . The problem
of Action Compatibility then reduces to determining whether there exists T ∈ GL(k, p) such
that T M (1, i) = M (2, i)T for every i ∈ [`]. This is a special case of Module Isomorphism,
which admits deterministic polynomial-time algorithms [CIK97, BL08, IKS10]. At the other extreme, when the extension is central, Theorem 6.1 solves Cohomology Class Isomorphism. At
62

present it is not clear to us how combine these two procedures to solve Extension Data Pseudocongruence as a whole, beyond the elementary abelian case (Theorem 6.11); see Section 8.1 for
a discussion of the difficulties involved.
On the other hand, consider the case in which a pseudo-congruence γ induces the identity map
on A, but not necessarily on Q:


A

ι1

/ G1

π1

∼
= β

∼
= γ

A



ι2



/ G2

//Q

π2


//Q

The isomorphism problem here corresponds to the algorithmic setting when Aut(A) is enumerable, and our goal is to find β such that G1 and G2 are pseudo-congruent. Proposition 7.6 and
Remark 3.14 fall into this setting. Recently, G. Ivanyos and the second author [IQ16] presented a
randomized efficient algorithm to decide whether two alternating bilinear maps over a finite field
of odd characteristic are isometric or not; given the connections between p-groups of class 2 and
exponent p and alternating bilinear maps (cf. [Wil09a, Section 3.4]), this amounts to solving the
problem of finding β as above. That result, and the techniques therein, are inspired by the work
of Brooksbank and Wilson [BW12] who presented an efficient algorithm to compute the isometry
group of a single alternating bilinear map (the automorphism version of the above problem). These
two works [BW12, IQ16] together suggest that we can compute the coset of isometries between two
alternating bilinear maps.

A.5

Some cohomological lemmas

Recall that a group G is perfect if [G, G] = G; as [G, G] is always a normal subgroup, all nonabelian
simple groups are perfect.
Proposition
Q 7.3, restated. Suppose T1 , . . . , T` are perfect groups. Let A be an abelian group,
and Q = i∈[`] Ti . Let G be a group with Z(G) = A and G/Z(G) = Q. Let Ui = ATi be the full
preimage of Ti under the natural map G → G/Z(G). Then for i, j ∈ [`], i 6= j, [Ui , Uj ] = 1.
Proof. Let π : G → G/Z(G) be the natural projection. Note that Q = G/Z(G) and Ti ’s are direct
factors of Q. For i ∈ [`], define Vi to be the smallest normal subgroup of G such that π(Vi ) = Ti .
Then Ui = Vi Z(G), and for i 6= j, [Ui , Uj ] = id if and only if [Vi , Vj ] = id.
As Ti is perfect, π([Vi , Vi ]) = π(Vi ). Because of minimality of Vi , Vi = [Vi , Vi ]. For i 6= j,
Ti ∩ Tj = id, thus [π(Vi ), π(Vj )] = [Ti , Tj ] = id in Q, which implies that [Vi , Vj ] ⊆ Z(G). Now we
have: (1) [[Vi , Vj ], Vj ] ⊆ [Z(G), Vj ] = id; (2) [[Vj , Vi ], Vj ] = id as [Vi , Vj ] = [Vj , Vi ]. Then Hall’s three
subgroup lemma [Suz86, Chapter 4, Proposition 1.9] gives that [[Vj , Vj ], Vi ] = id. Finally noting
that Vj = [Vj , Vj ] we have [Vj , Vi ] = id.
Lemma 7.5, restated. Let A0 × A00 ,→ G  Q be a central extension of A0 × A00 by Q. Let
pA0 : A0 × A00 → A0 be the projection onto A0 along A00 . If there is a 2-cocycle f : Q × Q → A0 × A00
such that pA0 ◦ f : Q × Q → A0 is a 2-coboundary, then G is isomorphic (even equivalent as an
extension of A0 × A00 by Q) to the direct product A0 × (G/A0 ).
Furthermore, given the Cayley table of G, A0 can be computed in polynomial time using linear
algebra over abelian groups.
63

Proof. We prove directly that A0  G, exhibit a complement of A0 in G and show that this complement is normal. At the end we show how to compute A0 using linear algebra.
We may assume without loss of generality that the image of f lies entirely within A00 . For
if not, then we may add the 2-coboundary pA0 ◦ f : Q × Q → A0 ,→ A0 × A00 to f to get an
equivalent 2-cocycle satisfying this condition. Similarly, we may assume that f is normalized so
that f (1, q) = f (q, 1) = 0 for all q ∈ Q.
We construct an extension equivalent to G from the cocycle f in the usual way: the elements
are A0 × A00 × Q as a set, with multiplication given by (writing A0 and A00 additively):
(a1 , a01 , q1 )(a2 , a02 , q2 ) = (a1 + a2 , a01 + a02 + f (q1 , q2 ), q1 q2 )
since the image of f lies entirely in A00 . We also have (a, a0 , q)−1 = (−a, −a0 − f (q, q −1 ), q −1 ).
A0 is normal:
(a, a0 , q)−1 (a0 , 1, 1)(a, a0 , q) = (−a, −a0 − f (q, q −1 ), q −1 )(a0 + a, a0 , q)
0

= (−a + a0 + a, −a − f (q, q

−1

(since f (1, q) = 0)

0

) + a + f (q, q −1 , qq −1 )

= (a0 , 0, idQ ).
A0 has a normal complement: as the image of f lies entirely in A00 , it is readily verified
that elements of the form (0, a0 , q) are closed under product, hence form a subgroup of G which
is isomorphic to G/A0 and intersects A0 only in the identity. Moreover, this subgroup is normal. For consider conjugating one of its elements by an arbitrary element of G: (−a, −a0 −
f (q, q −1 ), q −1 )(0, a00 , q0 )(a, a0 , q). From the multiplication rule above, it is clear that the first coordinate of this product is just the sum of the first coordinates of the three factors—namely,
zero—whatever the second and third coordinates are.
Finally, we show how to compute A0 from the Cayley table for G using linear algebra over
abelian groups. We give the proof in the case that Z(G) = Zkp is elementary abelian; the general
case uses the same ideas as in Section 6.1.1. First compute Z(G) (which is A0 × A00 , but we do not
yet know this decomposition of Z(G), we are only promised it exists) and Q = G/Z(G). Choose
any set-theoretic section s : Q → G and compute the corresponding cocycle f := fs . Let Mf be
the k × |Q|2 Zp -matrix corresponding to f as in Section 6. We may view Mf as a Zp -linear map
. As in Proposition 6.5, we may compute a basis of B 2 (Q, Z(G)) that
from Z(G) = Zkp to ZQ×Q
p
is a direct sum of bases for B 2 (Q, Zp ), one copy for each row of Mf . The maximal A0 satisfying
the conditions of the theorem is then the inverse image of B 2 (Q, Zp ) under this map. Computing
the inverse image of B 2 (Q, Zp ) under the map MfT : Z(G) → ZQ×Q
is then just linear algebra over
p
Zp .

B

Generalized Fitting subgroups of groups with central radical

Definition B.1. A group G is quasisimple if G = [G, G] and G/Z(G) is a nonabelian simple group.
G is m-quasisimple if G = [G, G] and G/Z(G) is a direct product of nonabelian simple groups.
Our m-quasisimple groups are Suzuki’s “semisimple groups” [Suz86, Page 446]; we cannot use
Suzuki’s terminology as we have used “semisimple” for groups with no abelian normal subgroups.
Although central-radical groups G with G/Z(G) a direct product of nonabelian simple groups need
not be m-quasisimple groups (as G need not be perfect), the difference is not much:
64

Proposition B.2 ([Suz86, Ch. 6, corollary to Theorem 6.4]). Let G be a group such that G/Z(G) is
a direct product of nonabelian simple groups. Then G = Z(G)[G, G], and [G, G] is an m-quasisimple
group.
M-quasisimple groups are crucial for defining the generalized Fitting subgroups.
Proposition B.3 ([Suz86]). Let H and K be m-quasisimple normal subgroups of G, then HK is
m-quasisimple.
This motivates the following definition. Recall that the Fitting subgroup F (G) of G is the
maximal nilpotent normal subgroup of G.
Definition B.4. Let G be a group. The layer E(G) of a group G, is the maximal m-quasisimple
normal subgroup of G. The generalized Fitting subgroup F ∗ (G) of G is E(G)F (G).
Proposition B.5. For any group G, if Rad(G) = Z(G), then Soc∗ (G) = F ∗ (G).
Proof. As Rad(G) = Z(G), F (G) = Z(G). Let D = [Soc∗ (G), Soc∗ (G)]. So D is m-quasisimple
and Soc∗ (G) = Z(G)D = F (G)D ([Suz86, Ch. 6, corollary to Theorem 6.4]). Thus D ⊆ E(G) and
Soc∗ (G) ⊆ F ∗ (G).
To show Soc∗ (G) ⊇ F ∗ (G), for the purpose of contradiction, suppose Z(G)D = Soc∗ (G) (
F ∗ (G) = Z(G)E(G). Consider the decomposition of E(G) into quasisimple groups ([Suz86,
Ch. 6, Definition 6.8]) as Q1 · . . . · Qd , where · denotes central product, and Qi is subnormal
in G. Without loss of generality assume Z(G)Q1 6⊆ Z(G)D. As Q1 is subnormal in G, G/Z(G)
necessarily has Q1 Z(G)/Z(G) as a subnormal group, contained in some minimal normal group
N/Z(G)  G/Z(G) ([Isa08, Lemma 9.17]). By assumption, Q1 Z(G)/Z(G) is not contained in
DZ(G)/Z(G) = Soc∗ (G)/Z(G) = Soc(G/Z(G)), so N/Z(G) is a minimal normal subgroup not
contained in Soc(G/Z(G)), contradicting the definition of the socle.

C

Relationship with results on practical algorithms

It is not surprising that, when it comes to the group isomorphism problem, theoretical computer
scientists and computational group theorists often leverage the same underlying structure of the
relevant group classes, even when they consider groups as being input by different kinds of data
structures. Here we discuss the relationship between these two sets of results. A general reference
for CGT is the handbook [HEO05]; algorithms in CGT are often implemented in Magma [BJP97]
and/or GAP [GG13].
One major achievement in CGT, as reflected in the Magma and GAP as well as in [HEO05],
is to implement a huge collection of practical routines to work with groups, when the groups are
represented by generating sets of permutations or matrices, or by poly-cyclic presentations (for
solvable groups). In general, these encodings are of size poly-logarithmic in |G|, so in that context
even a provable worst-case guaranteed running time of O(|G|) is usually impractical. However,
in order to achieve better running times, practically fast methods are often used, even without
guarantees on their running time. In the general setting, the best-known worst-case guarantee
on the running time of these practical algorithms is |G|O(log |G|) , even when the group is given
succinctly [Wil14]. Thus, improving the state of the art on large group classes to anything less
than |G|Θ(log |G|) represents not only an asymptotic, worst-case improvement in the complexity,
but potentially a practical improvement in many cases as well. Note that, although we sometimes
65

phrase results in terms of the Cayley table model, essentially none of our results depend on this; it
just means that running times that depend on |G| are then also being expressed in terms of their
dependence on the input size.
Regarding isomorphism testing algorithms in CGT, besides [CH03] mentioned in Section 8.3,
some notable works include [O’B94, BE99, LW12], and many of the algorithms in this area are
summarized in the theses [Smi94, How12]. Very often isomorphism testing arises as a subroutine in
the construction of all finite groups up to a certain order (up to isomorphism), as in [Tau55, BE99,
BEO02]. Recently, Wilson et al. have produced several results related to isomorphism of p-groups
(sometimes reformulated in the context of Hermitian bilinear maps) in [Wil09a, Wil09b, LW12,
BW12, BMW15], including worst-case guarantees (and sometimes even worst-case guarantees that
are polynomial in the size of the succinct input!). The structure they are uncovering in p-groups is
thus also notable from the complexity perspective, and there is likely more to be discovered in this
direction.
Although the two communities often leverage the same structure that is present in various classes
of groups, the worst-case guarantees often require further structural results on the group classes
considered, in addition to further algorithmic results. For example, Besche and Eick had already
considered the group classes in Le Gall’s work [LG09] (the algorithm in [BE99, Figure 4]), but Le
Gall’s work was the first to prove a polynomial-time upper bound on an isomorphism algorithm for
groups of the form A o Zp with A abelian and p - |A|. A necessary ingredient in Le Gall’s work is a
detailed understanding of automorphism groups of abelian groups traced back to Ranum [Ran07]
(note: the citation here is to 19 07), which was not needed in the practical setting of Besche and
Eick. Another example is the polynomial-time algorithm for semisimple groups [BCQ12], where
a similar situation is described at the end of that paper, comparing it with the practical work of
Cannon and Holt [CH03]. For example, the algorithm in [BCQ12] required bounds on the orders
of the transitive permutation groups other than Sn and An .
Relations to the present work. As mentioned above, our choice to focus on groups with
central radicals is partially motivated by the strategy of Cannon and Holt [CH03]. Another work
of particular relevance is [BE99]. There Besche and Eick considered construction of finite groups,
and proposed three heuristics. To support one heuristic, they proposed the concept of “strong
isomorphism” of groups, which can be viewed as a special case of our Main Lemma 3.7 in their
setting. We use the same structural results to support the approach, but as our goal is worst-case
running time upper bounds of poly(|G|), we have more freedom to handle the 2-cohomology classes
directly, as in Theorem 6.1; we also need Lemma 7.4 and Theorem 5.3 from [GKKL07], which in
turn allows us to apply algorithms for Linear Code Equivalence and Coset Intersection as
in Theorem 7.1. These ingredients are not present in [CH03] nor [BE99], as they were not needed
to get practical algorithms. However, it is nonetheless possible that taking advantage of these
ingredients, in combination with the practically-fast approaches from [CH03, BE99], could lead to
further practical improvements.

66

