arXiv:1609.08253v1 [cs.CC] 27 Sep 2016

On the Group and Color Isomorphism Problems
François Le Gall

David J. Rosenbaum

Graduate School of Informatics
Kyoto University
Email: legall@i.kyoto-u.ac.jp

The University of Tokyo
Department of Computer Science
Email: djr7c4@gmail.com

September 27, 2016

Abstract
In this paper, we prove results on the relationship between the complexity of the group and
color isomorphism problems. The difficulty of color isomorphism problems is known to be closely
linked to the the composition factors of the permutation group involved. Previous works are
primarily concerned with applying color isomorphism to bounded degree graph isomorphism,
and have therefore focused on the alternating composition factors, since those are the bottleneck
in the case of graph isomorphism.
We consider the color isomorphism problem with composition factors restricted to those
other than the alternating group, show that group isomorphism reduces in nO(log log n) time to
this problem, and, conversely, that a special case of this color isomorphism problem reduces to
a slight generalization of group isomorphism. We then sharpen our results by identifying the
projective special linear group as the main obstacle to faster algorithms for group isomorphism
and prove that the aforementioned reduction from group isomorphism to color isomorphism in
fact produces only cyclic and projective special linear factors. Our results demonstrate that,
just as the alternating group was a barrier to faster algorithms for graph isomorphism for
three decades, the projective special linear group is an obstacle to faster algorithms for group
isomorphism.

1

Introduction

The complexity of isomorphism testing problems is worthy of study both because they are fundamental computational questions and also because many of them are not known to be in P, but
nevertheless appear to be easier than the NP-complete problems. The most heavily studied of
these is the graph isomorphism problem. It is strongly suspected that graph isomorphism is not
NP-complete both because this would imply the collapse of the polynomial hierarchy [4, 10, 15, 14]
and also because there are subexponential time algorithms [24, 8, 7, 2] for testing isomorphism of
2
general graphs, which is much better than the 2O(n ) time complexity that we would expect based
on the exponential-time hypothesis [19]. √
For more than three decades, the 2O( n log n) time bound from [24, 8, 7] was the best known for
testing isomorphism of general graphs in the worst case. This result is based on (a) reducing testing
isomorphism
of a pair of arbitrary graphs to testing isomorphism of many pairs of graphs of degree
p
n/ log n using Zemlyachenko’s lemma (cf. [3]), and (b) reducing [24, 8, 7] testing isomorphism of
graphs of degree at most d to another problem known as the color automorphism problem [24, 8, 7].
In this problem, we are given a set X of size n and a coset σΓ where Γ is a subgroup of the
symmetric group on X and σ is a permutation of X. We are also given a function f : X → [n]
that specifies the color of each element of X. The problem is to compute all π ∈ σΓ such that
f (πx) = f (x) for all x ∈ X. It is important to note that the set of all such π forms a subcoset
of σΓ [24], so the solution can be represented compactly as a coset representative along with the
generators of a subgroup of Γ. In this paper, we consider a slight generalization of the color
automorphism problem in which there are two functions f1 and f2 .
Definition 1.1. In the color isomorphism problem, we are given a set X of size n and a coset σΓ
containing permutations of X and two functions f1 : X → [n] and f2 : X → [n]. The goal is to find
all π ∈ σΓ such that f2 (πx) = f1 (x) for all x ∈ X.
Note that we can recover the color automorphism problem by stipulating that f1 = f2 .
The complexity of the color isomorphism problem is strongly dependent on the non-Abelian
composition factors (which we define later) of the group Γ: if every non-Abelian composition factor
of Γ is isomorphic to a subgroup of the symmetric group on d elements, then any color isomorphism
O(d/ log d) time [8, 7]1 . The barrier to improving the
problem on a subcoset σΓ can be solved in n√
nO(d/ log d) time bound, and hence also the 2O( n log n) time bound for graph isomorphism, depends
only on the composition factors that are isomorphic to alternating groups [7]. All other composition
factors can be handled simply by brute force in nO(log n) time by a result of Pyber [28].
In a recent paper [2], Babai overcame the obstacle of the alternating composition factors with
2+O(1)
n) time. This is
an algorithm that solves the graph and color isomorphism problems in 2O(log
almost an exponential speedup. However, the statement of this result does not allow us to obtain
speedups for other types of composition factors since — as mentioned above — they can be dealt
with exhaustively in nO(log n) time.
In this work, we study the complexity of color isomorphism problems involving composition
factors other than the alternating group. We accomplish this by comparing this class of color
isomorphism problems to the group isomorphism problem — a fundamental problem in computational group theory that has been well studied and has seen a surge of activity in the last few
1

In these previous papers, color automorphism and string canonization were the problems that were considered.
However, the techniques in these papers can easily be adapted to solve color isomorphism within the same bounds.

1

years [23, 33, 35, 1, 20, 21, 29, 5, 13, 9, 6, 22, 16, 27, 17]. As we will show, group isomorphism depends only on the cyclic and projective special linear composition factors, so we focus our attention
on color isomorphism problems with cyclic and projective special linear composition factors. Our
first result shows that, just as the alternating group was a barrier to placing graph isomorphism in
quasi-polynomial time for more than thirty years, the projective special linear group is a barrier to
faster algorithms for group isomorphism. Before we can present our reduction, we need to introduce
some notation. Let CI denote the class of all color isomorphism problems and let CI∗ be all color
isomorphism problems with cyclic and projective special linear composition factors. We denote the
group isomorphism problem by GrI.
Theorem 1.2. GrI is Turing reducible to CI∗ in nO(log log n) time.
It is important to note that this result is trivial when CI∗ is replaced with CI. The main difficulty
here is to restrict the non-Abelian composition factors to the projective special linear group.
Our proof is based a holomorph trick suggested by Babai (personal communication), a new
notation for dealing with iterated wreath products, structural results on automorphisms of finite2
Abelian groups (which we prove using [18]) and the algorithm of [5]. The holomorph trick can also
be replaced by the framework introduced by Luks’ in his recent paper [25] that shows how to test
isomorphism of composition series in polynomial time. We discuss the relationship between our
work and Babai’s holomorph trick in more detail in Subsection 2.2.
Our next result is the simple (but to our knowledge previously unknown) observation3 that the
color isomorphism problem is equivalent to a slight generalization of graph isomorphism. The main
reasons for mentioning this result are to make the relationship between general graph isomorphism
and color isomorphism explicit and also to motivate one of our later results in this paper. Let GI∗
be the problem of computing all isomorphisms between two graphs X and Y that are contained in
a specified subcoset σΓ that maps the vertices of X to the vertices of Y .
Theorem 1.3. CI and GI∗ are equivalent under polynomial-time many-one reductions.
Next, we explore the question of how much more difficult CI∗ is compared to GrI. To do this,
we introduce a slight generalization of group isomorphism and show that a special case of CI∗ can
be reduced to it. To this end, we define GrI∗ to be the problem of computing all isomorphisms
from a group G to a group H that are contained within a coset σΓ that maps the elements of Γ
to H analogously to GI∗ for graphs. It seems unlikely that GrI∗ is much harder than GrI; currently,
the fastest worst-case algorithms for both problems run in nO(log n) time. Before we can define the
special case BI of CI∗ that we will reduce to GrI∗ , we need to introduce some additional terminology.
Definition 1.4. Let f : B × B → A be a bilinear map defined on Abelian groups (regarded as
Z-modules). Then an isometry is a map α ∈ Aut(B) such that f (x, y) = f (βx, βy) for all x, y ∈ B.
It is easy to see that the isometries of a bilinear map form a group. Now we can define the
problem BI.
Definition 1.5. Let A and B be Abelian groups and let f : B × B → A be a bilinear map given
as a table of the values f (x, y) for all x, y ∈ B. Then BI is the problem of computing the isometry
group of f .
2
3

All of the groups that we deal with in this paper are finite and we shall omit the adjective finite from now on.
The proof of this result is straightforward. However, for the sake of completeness, we give a proof in Appendix A.

2

This redundancy in the representation of f is similar in spirit to the Cayley table representation
used in group isomorphism. Another reason to use this redundant representation is that it means
that BI corresponds to a color isomorphism problem involving an action of Aut(B) on the Abelian
group B × B × A. Since the composition factors of Aut(B) are either cyclic or projective special
linear, this implies that BI is a special case of CI∗ .
Versions of this problem in which the bilinear map is specified compactly as a matrix and A and
B are vector spaces have been studied. Brooksbank and Wilson showed [11] that for bilinear maps
that are Hermitian, one can compute the isometry group in polynomial time. Hermitian matrices
generalize the symmetric and skew-symmetric matrices, but there are many matrices that are not
hermitian.
Our next result shows that BI is polynomial-time many-one reducible to GrI∗ .
Theorem 1.6. BI is polynomial-time many-one reducible to GrI∗ .
Previously, Grochow and Qiao studied [16, 17] a generalization of the reverse direction of this
reduction and used it to prove several interesting results. Our result complements theirs, and, to
our knowledge, is the first reduction to (a slight generalization of) group isomorphism.
Our proof is based on using cohomology to construct a group Gf from the bilinear map f that
contains A as a normal subgroup. We then compute a certain subgroup of the automorphism group
of Gf by solving a problem in GrI∗ . We show that every automorphism φ in this subgroup defines
a map ϕφ : Gf /A → A and prove that φ gives rise to an isometry of f precisely when ϕφ is a
homomorphism. By further restricting the subcoset in the instance of GrI∗ above, we can ensure
that every element of the resulting subgroup of automorphisms gives rise to a homomorphism and
that every isometry can be obtained from an automorphism in this subgroup.
Additionally, BI is likely to be equivalent to GrI. The reason is as follows. The hard case of
GrI is conjectured to be testing isomorphism of nilpotent groups of class 2 (NGrI). Theorem 1.6 in
fact reduces to NGrI∗ , where NGrI∗ is defined analogously to GrI∗ . Moreover, one can show that
NGrI reduces to the problem of computing all α ∈ Aut(A), β ∈ Aut(B) and b ∈ B such that
f (x, y) = αf (βx, βy) + b for all x, y ∈ B where A, B are abelian groups, B is a known subgroup of
the group of bilinear maps from B × B to A and f : B × B → A is bilinear. One can then recover
BI as a special case by setting α = 1 and b = 0. This only removes cyclic composition factors from
the resulting corresponding color isomorphism problem.

2

Background

In this section, we introduce some of the basic group theoretic concepts used later in the paper.
We also discuss related results on testing isomorphism of composition series.

2.1

Group theory background

A subnormal series of a group G is a chain of subgroups G1 = 1 ⊳ G2 ⊳ · · · ⊳ Gk = G where each
subgroup is normal in the next and 1 denotes the trivial subgroup. The factor groups of this
series are the groups Gi+1 /Gi . For a group G, let [G, G] be the subgroup of G generated by the
commutators [g1 , g2 ] = g1 g2 g1−1 g2−1 where g1 , g2 ∈ G. One series that will be of interest is the
derived series G(k) ⊳ · · · ⊳ G(0) = G. Here, G(0) = G and each G(i+1) = [G(i) , G(i) ] and k is the
smallest natural number such that G(k+1) = G(k) . It need not be the case that G(k) = 1. If this
holds, then G is a solvable group.
3

If a subnormal series is maximal so that no more intermediate subgroup can be inserted that
are distinct from the subgroups already in the series, then it is called a composition series. The
factor groups of a composition series are called composition factors and are simple groups. That is,
each of their normal subgroups is either the whole group or is trivial. One can equivalently define
a composition series as a subnormal series in which all the factor groups are simple. In a solvable
group, all of the composition factors are cyclic so that there are no non-Abelian composition factors.
Much of the motivation for this work is based on a simple group called the projective special
linear group. To obtain this group, one starts with the general linear group GLd (F) of all invertible
matrices over the field F. By restricting to the subgroup of matrices with determinant 1, we obtain
the special linear group SLd (F). The projective linear group is then defined to be the quotient of
SLd (F) mod the subgroup consisting of multiples of the identity matrix by roots of unity. Dealing
with the projective linear group is about as difficult as dealing with the general linear group since
its non-Abelian composition factors consist of a single copy of the projective special linear group.
The holomorph Hol(G) of a group G is a semidirect product of G with its automorphism group.
An element (g, φ) ∈ Hol(G) acts on each element x ∈ G by (g, φ)(x) = g · φ(x). The product of
two elements (g1 , φ1 ), (g2 , φ2 ) ∈ Hol(G) is (g1 , φ1 ) · (g2 , φ2 ) = (g1 φ1 (g2 ), φ1 φ2 ). The wreath product
G ≀ H of two permutation groups G and H that act on the sets Y and X is a semidirect product
of the groups GH and H. Here, GH means a direct product of |H| copies of G; each copy of G
is indexed by a different element of H. Each element of the wreath product G ≀ H corresponds
to a pair (g, h) where g ∈ GH is a vector indexed by the elements of H. Then (g, h) acts on an
element x, y ∈ X × Y by (g, h)(x, y) = (ghy x, hy). Intuitively, a wreath product corresponds to a
group of automorphisms of a full rooted tree of depth 2. The children of the root correspond to
the elements of Y while their children correspond to elements of X × Y . The element h indicates
how the children of the root should be permuted and the vector g of elements of G indexed by H
indicates how the children of each child of the root should be permuted after the children of the
root are permuted. In particular, if T is a rooted tree of depth 2 where all nodes at depth 1 have
degree d1 and all nodes at depth d2 , then Aut(T ) = Sd2 ≀ Sd1 .
In this section, we shall be concerned with iterated wreath products of the form G1 ≀ · · · ≀ Gk
of groups Gi which each acts on a set Xi . The iterated wreath product G1 ≀ · · · ≀ Gk acts on
X1 × · · · × Xk by recursively applying the definition of a wreath product. If one imagines a rooted
tree where the first level consists of the elements of Xk and the ith level consists of the elements of
Xk−i+1 × · · · × Xk , then G1 ≀ · · · ≀ Gk is a group of automorphisms of this rooted tree. The group
Gk determines how the children of the root are permuted and there is a copy of each Gk−i+1 for all
(xk−i+1 , . . . , xk ) ∈ Xk−i+1 ×· · ·×X1 that determines how its children are permuted. If one considers
the full rooted tree of depth k where every node in the ith level has degree di , then its automorphism
group is the iterated wreath product Sdk ≀ · · · ≀ Sd1 . This notation quickly becomes cumbersome
to deal with as the number of groups k increases. We address this problem by introducing a new
notation for wreath products that is much more convenient for our purposes in Section 3.

2.2

Previous work on composition series isomorphism

Our techniques rely on recent ideas by Luks [25] and Babai (personal communication) on composition series isomorphism. We say that two series S and S ′ for groups G and H are isomorphic if there
is an isomorphism from G to H that maps each subgroup in S to the corresponding subgroup in

4

S ′ . Babai showed (personal communication) that if φ is an isomorphism between subnormal series4
S and S ′ for groups G and H, then φ ∈ Hol(F0 ) ≀ · · · ≀ Hol(Fk ) where F0 , . . . , Fk are the factors of
the isomorphic subnormal series S and S ′ . If G and H are solvable, then so is each Hol(Fi ); this
implies that Hol(F0 ) ≀ · · · ≀ Hol(Fk ) is also solvable. Since Hol(F0 ) ≀ · · · ≀ Hol(Fk ) can be given as a
permutation group with 2(k +1) generators and color isomorphism problems on solvable groups can
be handled in polynomial time [26, 8], this implies that testing isomorphism of composition series
of solvable groups is in polynomial time since Hol(F0 ) ≀ · · · ≀ Hol(Fk ) does not have any non-Abelian
composition for solvable groups.
The solvable radical Rad(G) of a group G is its unique maximal solvable normal subgroup.
Babai (personal communication) further proved that one can decide isomorphism of subnormal
series of arbitrary groups in nO(log log n) time by using the algorithm of [5] assuming that they have
the form 1 ⊳ G1 ⊳ · · · ⊳ Gk ⊳ Rad(G) ⊳ Gk+1 ⊳ · · · ⊳ Gm = G. Using different but related ideas,
Luks’ went further and showed [25] that testing isomorphism of arbitrary composition series can
be done in polynomial time. In an upcoming paper (cf. [25]), Luks’ plans to build this into the
stronger result that canonical forms of composition series can be computed in polynomial time.
Let p be the smallest prime divisor of the group. Since every group has at most n(1/2) logp n+O(1)
composition series, this method can be combined with the bidirectional collision detection methods
introduced by the second author [31] (which provide a deterministic square-root speedup) to solve
group isomorphism in n(1/4) logp n+O(1) time.
In this work, we apply Babai’s holomorph trick and his idea to a different series that we call the
radical derived series 5 (which we shall define shortly). Unlike the classes of composition series and
subnormal series, this series has the property that there is only one way to construct it for a given
group. Consequently, if S and S ′ denote the radical derived series for the groups G and H, then
G and H are isomorphic if and only if S and S ′ are isomorphic. The advantage of this approach is
that it allows us to avoid the n(1/4) logp n factor in the runtime above. The difficulty of the group
isomorphism problem is instead handled by allowing projective special linear composition factors
in the resulting color isomorphism problem. The radical derived series is defined as follows.
Definition 2.1. Let G be a group. Then the radical derived series of G is
Rad(G)(m) = 1 ⊳ Rad(G)(m−1) ⊳ · · · ⊳ Rad(G)(0) = Rad(G) ⊳ G
Here, Rad(G)(i) denotes the ith subgroup in the derived series of Rad(G) starting with Rad(G).
Because the iterated wreath products that arise in this reduction are quite complicated and
difficult to handle, we also introduce a new notation for describing elements of iterated wreath
products which makes our proofs much easier. It is our hope that our notation will prove useful in
future work in this area. Our proof also requires us to prove a result on the composition factors
of the automorphism groups of Abelian groups. We accomplish this by using the framework for
dealing with automorphisms of Abelian groups given in [18].

3

Reducing group isomorphism to color isomorphism

In this section, we prove that group isomorphism reduces to the color isomorphism problem with
cyclic and projective special linear composition factors.
4
Only the case of composition series is relevant in this paper; however, Babai’s result applies more generally to
arbitrary subnormal series.
5
A similar series with elementary Abelian factors appears in [12].

5

The first step is to identify the elements of G and H. Clearly, this does not solve the isomorphism
problem since the resulting groups can have different multiplication rules and the identification does
not necessarily yield an isomorphism. We accomplish this using the following definitions.
Definition 3.1. Let G be a group, let Gm = 1 ⊳ · · · ⊳ G0 = G be its radical derived series and let
Fi = Gm−i /Gm−i+1 and choose an arbitrary lift ℓi : Fi → Gi for each 1 ≤ i ≤ m. Then for each
g ∈ G, there exists a unique (x1 , . . . , xm ) ∈ F1 ×c · · · ×c Fm such that g = ℓm (x0 ) · · · ℓ1 (xm−1 ).
Let ℓ : F1 ×c · · · ×c Fm → G denote this bijection. Then we define Ĝ to be the group on the set
F1 ×c · · · ×c Fm whose multiplication rule is induced by G under the bijection ℓ.
Here, we distinguish between Cartesian products (denoted by ×c ) which operate on sets and
direct products (denoted by ×) which operate on groups. Therefore, F1 ×c · · · ×c Fm is the subset of
Ĝ that corresponds to (Ĝ)(i) . We use ×c instead of × in order to avoid suggesting that F1 ×c · · ·×c Fm
is a direct product of the groups F1 , . . . , Fm . This would be very misleading since (Ĝ)(i) can be
non-Abelian.
Our next step is to identify the factor groups in the radical derived series for the groups G and H.
Let us say
Ś that the canonical representation of an Abelian group A is the unique group of the form
C(A) = ki=1 Zepii that is isomorphic to A where p1 < · · · < pk are primes and each ei is a natural
number. This takes care of the Abelian factors in the radical derived series. However, we also need
a way to identify the factor groups G/Rad(G) and H/Rad(H). These are non-Abelian groups that
do not have any normal Abelian subgroups. We identify them by using the algorithm of [5] which
can enumerate all the isomorphisms between two groups of order n that do not have any normal
Abelian subgroups in nO(log log n) time. To do this, we first define C(G/Rad(G)) = G/Rad(G); we
then define C(H/Rad(H)) = G/Rad(G). The later identification is performed in nO(log log n) time
using [5]. Note that our definition of C on non-Abelian groups depends on whether we are given G
or H and is thus specific to our problem instance.
Definition 3.2. Let G be a group, let Gm = 1 ⊳ · · · ⊳ G0 = G be its radical derived series and let
Fi = Gm−i /Gm−i+1 . For each Fi , let F̃i = C(Fi ) and choose an arbitrary isomorphism ϕi : Fi → F̃i .
This defines a bijection ϕ : F1 ×c · · · ×c Fm → F̃1 ×c · · · ×c F̃m . We let G̃ be the group on the set
F1 ×c · · · ×c F̃m whose multiplication rule is induced by the group Ĝ under the bijection ϕ : Ĝ → G̃.
Note that ϕ ◦ ℓ−1 : G → G̃ is an isomorphism from G to G̃. A key fact that we shall need
about G̃ is that its derived subgroups correspond to iteratively removing factors from the product
C(F1 ) ×c · · · ×c C(Fm ) as we move down the series. This is stated in the following proposition. The
proof follows easily from the definitions.
Proposition 3.3. Let G be a group, let Gm = 1 ⊳ · · · ⊳ G0 = G be its radical derived series and let
Fi = Gm−i /Gm−i+1 . Then (G̃)(i) = C(F1 ) ×c · · · ×c C(Fm−i ).
The next lemma allows us to treat isomorphisms between groups as members of a wreath
product.
Lemma 3.4. Let G and H be groups and suppose that φ : G̃ → H̃ is an isomorphism. Let
Gm = 1 ⊳ · · · ⊳ G0 = G and Hm = 1 ⊳ · · · ⊳ H0 = H be the radical derived series for G and H and
let F̃i = C(Gm−i /Gm−i+1 ) = C(Hm−i /Hm−i+1 ). Then φ ∈ Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m ).
Before we can present the proof, we need a better way of dealing with iterated wreath products
since using the standard wreath product definition recursively quickly becomes very cumbersome.
6

Without better notation, our proof would be extremely tedious. We accomplish this by defining a
wreath product as a indexes set of elements that satisfies certain conditions.
Definition 3.5. Consider the iterated wreath product G1 ≀ · · · ≀ Gk of groups Gi which each acts on
a set Xi . Let πxi+1,...,xk ∈ Gi for each xi+1 , . . . , xk ∈ Xi+1 × · · · × Xk and each 1 ≤ i ≤ k. Then
this set of elements defines the permutation π(x1 , . . . , xk ) = (πx2 ,...,xk (x1 ), . . . , πxk (xk−1 ), π() (xk )).
Note that in the above definition, π() ∈ Gk denotes the case where i = k + 1 so that the
list of subscripts is empty. It is easy to show that the functions π from Definition 3.5 are indeed
permutations and are precisely the elements of the iterated wreath product G1 ≀ · · · ≀ Gk .
Lemma 3.6. Consider the iterated wreath product G1 ≀ · · · ≀ Gk of groups Gi which each acts on a
set Xi . Then every π defined by Definition 3.5 is a permutation contained in G1 ≀· · · ≀Gk . Moreover,
every element of G1 ≀ · · · ≀ Gk can be expressed in the form of Definition 3.5.
Now, we are ready to prove Lemma 3.4. Because our proof deals with many subsequences
of vectors, we introduce a shorthand. If a ∈ A1 × · · · × Ak , then ai,j denotes the subsequence
(ai , . . . , aj ).
Proof. For each 1 ≤ i ≤ m, let φi = φ

Fi

: F̃i → F̃i be the automorphism of F̃i induced by φ. Define

φ̃xi+1,m = (fi (xi+1,m ), φi ) ∈ Hol(F̃i )
for each x ∈ F1 ×c · · · ×c Fm and 1 ≤ i ≤ m where the fi+1 : Fi+1 ×c · · · ×c Fm → Fi are functions
that are to be determined in the course of the proof. Whatever we later choose these functions to
be, note that by Definition 3.5 and Lemma 3.6, it defines a permutation φ̃ ∈ Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m ).
Our aim is to choose them so that φ = φ̃.
We accomplish this by induction on i. Our goal is to show that
φ(1i , xi+1,m ) = φ̃(1i , xi+1,m )

(1)

i times

z }| {
for all 0 ≤ i ≤ m where
is a shorthand for 1, . . . , 1.
We start with the basis case i = m. This corresponds to the claim that
1i

φ(1m ) = φ̃(1m )
which is equivalent to asserting that
1m = (f1 (1m−1 ), . . . , fm−1 (1), fm )
Since we can choose the fi functions as desired, we simply define (f1 (1m−1 ), . . . , fm−1 (1), fm ) = 1m .
This proves the basis case, so we now proceed to the inductive case.
Assume that (1) holds for some 1 ≤ i ≤ m; we will show that it holds for i − 1 as well. By
Proposition 3.3, (1i−1 , xi , 1m−i ) ∈ (G̃)(m−i) so
φ(1i−1 , xi,m ) = φ(1i−1 , xi , 1m−i )φ(1i , xi+1,m )
Now, again because φ(1i−1 , xi , 1m−i ) ∈ (G̃)(m−i) , we have φ(1i−1 , xi , 1m−i ) = (ai−1 (xi ), φi (xi ), 1m−i )
for some ai−1 (xi ) ∈ F̃1 ×c · · · ×c F̃i−1 . Thus, by the inductive hypothesis
φ(1i−1 , xi,m ) = (ai−1 (xi ), φi (xi ), 1m−i ) · φ̃(1i , xi+1,m )
7

(2)

By Definition 3.5 and noting that fm = 1 from the basis case, we see that φ̃(1i , xi+1,m ) is equal to
(f1 (1i−1 , xi+1,m ), . . . , fi (xi+1,m ), fi+1 (xi+2,m )φi (xi+1 ), . . . , fm−1 (xm )φi (xm−1 ), φm (xm ))
By applying Proposition 3.3, we see that this is equal to
(f1 (1i−1 , xi+1,m ), . . . , fi (xi+1,m ), 1m−i )

(3)

i

· (1 , fi+1 (xi+2,m )φi (xi+1 ), . . . , fm−1 (xm )φi (xm−1 ), φm (xm ))
By replacing φ̃(1i , xi+1,m ) in (2) with (3), we see that
φ(1i−1 , xi,m ) = (ai−1 (xi ), φi (xi ), 1m−i )
· (f1 (1i−1 , xi+1,m ), . . . , fi (xi+1,m ), 1m−i )
· (1i , fi+1 (xi+2,m )φi (xi+1 ), . . . , fm−1 (xm )φi (xm−1 ), φm (xm ))
Now F̃i is Abelian for i < m and fi = 1 for i = m. Thus, φi (xi )fi (xi+1,m ) = fi (xi+1,m )φi (xi ), so
φ(1i−1 , xi,m ) = (bi−1 (B), fi (xi+1,m )φi (xi ), 1m−i )
· (1i , fi+1 (xi+2,m )φi (xi+1 ), . . . , fm−1 (xm )φi (xm−1 ), φm (xm ))
= (bi−1 (B), fi (xi+1,m )φi (xi ), . . . , fm−1 (xm )φi (xm−1 ), φm (xm ))
where B = (xi , f1 (1i−1 , xi+1,m ), . . . , fi (xi+1,m )) indicates the values on which bi−1 (B) depends6 .
If i = 1, then bi−1 (B) = b0 (B) = () and we have φ(1i−1 , xi,m ) = φ̃(1i−1 , xi,m ) as desired. Also,
if xi = 1, then φ(1i−1 , xi,m ) = φ̃(1i−1 , xi,m ) by the inductive hypothesis. Therefore, we may assume
that i ≥ 2 and xi 6= 1. Then by Definition 3.5 we have
φ̃(1i−1 , xi,m ) = (f1 (1i−2 , xi,m ), . . . , fi−1 (xi,m ), fi (xi+1,m )φi (xi ), . . . , fm−1 (xm )φm−1 (xm−1 ), φm (xm ))
so to show that φ(1i−1 , xi,m ) = φ̃(1i−1 , xi,m ), we need to choose (f1 (1i−2 , xi,m ), . . . , fi−1 (xi,m )) =
bi−1 (B).
Now, we just need to argue that all the assignments that we make at each step are independent.
Let us say that the weight of a vector y is d − k where d is the length of y and k is the smallest
index such that yk 6= 1. Then, the ith step of the induction assigns values to the functions fj with
j < i on arguments of weight exactly m − i + 1. It follows that the assignments made at each step
are independent which proves that (1) holds for i − 1. By induction, we conclude that the functions
fi can be chosen so that φ = φ̃.
Before we can prove Theorem 1.2, we need a lemma about the structure of automorphisms of
Abelian groups.
Lemma 3.7. Let A be an Abelian group. Then every composition factor of Aut(A) is either cyclic
or projective special linear.
To prove this lemma, we need to introduce a few definitions and results on the theory of
automorphisms of Abelian groups. These were first studied by Ranum [30]; however, we follow the
more modern treatment by Hillar and Rhea [18] since it is more convenient. Since the group of
automorphisms of a direct product of groups of relatively prime order is the direct product of the
automorphisms of each group, it suffices to consider Abelian p-groups. First, we characterize the
endomorphisms of Abelian p-groups.
6

There is no need to include φi (xi ) in addition to xi since φ is fixed and therefore so is φi .

8

Ś
Definition 3.8 ([30], cf. [18]). Let A = di=1 Zepi be a Abelian p-group where e1 < · · · < ed . Define
n
o
R(A) = (mij ) ∈ Zd×d pei −ej divides aij for all 1 ≤ j ≤ i ≤ d
One can show that R(A) is a ring [30] (cf. [18]). The endomorphisms End(A) of A then arise
via a homomorphism defined on R(A).
Śd
ei
Theorem 3.9 ([18]). Let A =
i=1 Zp be a Abelian p-group where e1 < · · · < ed and define
ψ : R(A) → End(A) by
ψ(M )(π(a)) = π(M a)
where π : Zd → A is the projection that maps each a ∈ Zd to (a1 + Zep1 , . . . , ad + Zepd ). Then ψ is a
surjective homomorphism.
We also need another result that relates the endomorphisms to automorphisms.
Śd
ei
Theorem 3.10 ([30], cf. [18]). Let A =
i=1 Zp be an Abelian p-group where e1 < · · · < ed .
Then ψ(M ) is an automorphism if and only if ψ(M ) mod p ∈ GLd (p) (where the modulo division
is performed entrywise).
Now, we are ready to prove Lemma 3.7.
Proof of Lemma 3.7. Since the automorphism group of A is the direct product of the automorphism
groups
Ś of its Sylow subgroups, it suffices to prove this for the case where A is a p-group. Let
A = di=1 Zepi be a Abelian p-group where e1 < · · · < ed and let us define ρ : End(A) → Zd×d
by
p
ρ(ψ(M )) = ψ(M ) mod p for each ψ(M ) ∈ End(A). Observe that ρ is a ring homomorphism.
By Definition 3.8 and Theorem 3.9, the image of of ρ is
n
o
Im ρ = (mij ) ∈ Zd×d
m
=
0
if
1
≤
j
≤
i
≤
d
and
e
=
6
e
ij
i
j
p
In other words, the image of ρ consists of block-upper triangular matrices in Zd×d
where the blocks
p
consist of those (i, j) such that ei = ej . Let Bk denote the set of indexes (i, j) in the kth block
on the main diagonal of these matrices where 1 ≤ k ≤ ℓ. Since the determinant of a block-upper
triangular matrix is equal to the product of the determinants of the blocks, we see that ρ[Aut(A)]
consists of those matrices in Im ρ where the blocks on the diagonal are invertible. Thus,



ρ[Aut(A)] = (mij ) ∈ Im ρ det (mij )Bk 6= 0 for each k
where (mij )Bk denotes the submatrix of (mij ) on the block Bk .
We now shift our attention to σ = ρ Aut(A) : Aut(A) → ρ[Aut(A)] which we interpret as a
surjective homomorphism between multiplicative groups. Since Aut(A)/ ker σ ∼
= Im σ, to find the
composition factors of Aut(A), it suffices to show that the composition factors of the kernel and
image of ρ are either cyclic or projective special linear. Now, Im σ = ρ[Aut(A)].
To find its composition factors, we define another homomorphism θ : Im σ → GLd (p) where dk is
the dimension of the kth block Bk . Then we define θ(M ) = diag(M1 , . . . , Mℓ ) where Mk = (mij )Bk
is the submatrix on the block Bk in M . Now, Im θ = GLd1 (p) × · · · × GLdℓ (p) and the composition
factors of general linear groups are cyclic and projective special linear. The kernel of θ is a p-group
and therefore has cyclic composition factors. It follows that Im σ has only cyclic and projective
special linear composition factors.
9

All the remains is to determine the composition factors of ker σ. However, ker σ is also a pgroup, so its composition factors are all cyclic. It follows that the composition factors of Aut(A)
are cyclic and projective special linear.
Theorem 1.2. GrI is Turing reducible to CI∗ in nO(log log n) time.
Proof. Let Gm = 1 ⊳ · · · ⊳ G0 = G and Hm = 1 ⊳ · · · ⊳ H0 = H be the radical derived series for two
groups G and H and let F̃i = C(Gm−i /Gm−i+1 ) = C(Hm−i /Hm−i+1 ). We will first compute the
isomorphisms Iso(G̃, H̃) from G̃ to H̃ and then use this to find the isomorphisms Iso(G, H) from G
to H. If G and H are isomorphic, then Lemma 3.4 tells us that Iso(G̃, H̃) ⊆ Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m ).
Now, by the definition of the holomorph and Lemma 3.7, the composition factors of Hol(F̃i ) are
either cyclic or projective special linear for 1 ≤ i < m. Therefore, the composition factors of the

F̃m
normal subgroup Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m−1 )
are all either cyclic or projective special linear. (As

F̃m
before, Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m−1 )
denotes a direct product of copies of Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m−1 )
indexed by F̃m .) Since F̃m can be non-Abelian, Hol(F̃m ) can have other composition factors which
we must somehow eliminate if we are to place GrI in CI∗ .
We accomplish this using the results of [5], which show that a group of order n that does not have
any Abelian normal subgroups has at most nO(log log n) automorphisms and that all of them can be
O(log log|F̃m |)
≤ nO(log log n)
enumerated within the same bound. This implies that Aut(F̃m ) ≤ F̃m
where n = |G| = |H| and that we can enumerate Aut(F̃m ) within the same bound. Consequently,
we can also enumerate Hol(F̃m ) in nO(log log n) time.
Therefore, we can transform our instance of GrI into nO(log log n) instances of CI∗ as follows. For

F̃m
each (fm , φm ) ∈ Hol(F̃m ), we consider the coset Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m−1 )
·(fm , φm ). Note that
Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m ) =


F̃m
Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m−1 )
· (fm , φm )

[
(fm ,φm )∈Hol(F̃m )

so it suffices to find the isomorphisms from G̃ to H̃ that are contained in each such coset and

F̃m
accumulate the results. For each Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m−1 )
· (fm , φm ), we define a color iso
F̃m
morphism problem where we extend Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m−1 )
· (fm , φm ) to act on the set

3
X = F̃1 ×c · · · ×c F̃m . Recalling that F̃1 ×c · · · ×c F̃m is the underlying set of both G̃ and H̃,
we solve the instance of CI∗ n
that arises when we o
let f1 :nX → [n3 ] and f2 : Xo→ [n3 ] be the indicator functions on the subsets (x, y, xy) x, y ∈ G̃ and (x, y, xy) x, y ∈ H̃ of X. This yields all

F̃m
isomorphisms from G̃ to H̃ that are contained in the coset Hol(F̃1 ) ≀ · · · ≀ Hol(F̃m−1 )
· (fm , φm ).
By taking the union of all of the isomorphisms found, we obtain Iso(G̃, H̃) in nO(log log n) time.
All that remains is to show how to compute Iso(G, H) from Iso(G̃, H̃). Since it was computed
from nO(log log n) cosets, the description of Iso(G̃, H̃) may use up to nO(log log n) generators. For
convenience, we reduce this to O(log2 n) generators in polynomial time using standard permutation
group algorithms (cf. [34]). Using Definitions 3.1 and 3.2, we can define isomorphisms α : G → G̃
and β : H → H̃. Then Iso(G, H) = β −1 Iso(G̃, H̃)α.
10

4

Reducing color isomorphism to a generalization of group isomorphism

In this section, we show that the problem of computing the isometry group of a bilinear map can be
reduced to a generalization of group isomorphism in polynomial time. The first step is to construct
a group whose structure depends on the bilinear map.
Definition 4.1. Let f : B → A × A be a bilinear map. Then we define Gf to be the group on the
set B × A with the operation (b1 , a1 ) · (b2 , a2 ) = (b1 b2 , a1 a2 f (b1 , b2 )).
The fact that Gf is a group follows easily from the assumption that f is bilinear. Readers
familiar with group cohomology theory will note that this is also a consequence of a construction
from group cohomology involving factor sets (cf. [32]). Moreover, since A ≤ Z(G), Gf /Z(Gf ) is
isomorphic to a subgroup of the Abelian group B, so it follows that Gf is nilpotent of class at most
2.
Proposition 4.2. Gf is a nilpotent group of class at most 2.
Let b ∈ B. It is convenient to define ℓ(b) = (b, 0). We can then write ℓ(b)a for (b, a).
Our next step is to show that every isometry of f gives rise to an automorphism of Gf .
Lemma 4.3. Let β : B → B be an isometry of a bilinear map f : B × B → A. Then the map
φ : Gf → Gf defined by φ(ℓ(b)a) = ℓ(βb)a is an automorphism of Gf .
Proof. Let ℓ(b1 )a1 , ℓ(b2 )a2 ∈ Gf . Then
φ((ℓ(b1 )a1 )(ℓ(b2 )a2 )) = φ(ℓ(b1 b2 )f (b1 , b2 )a1 a2 )
= ℓ(β(b1 b2 ))f (b1 , b2 )a1 a2
= ℓ(β(b1 ))ℓ(β(b2 ))f (βb1 , βb2 )−1 f (b1 , b2 )a1 a2
= ℓ(β(b1 ))a1 ℓ(β(b2 ))a2
= φ(ℓ(b1 )a1 )φ(ℓ(b2 )a2 )
which completes the proof.
We also need to show that certain types of automorphisms of Gf yield isometries of f . Our
first step towards this goal is to prove the following characterization of which automorphisms of
Gf that fix A induce isometries. For convenience, we identify B with Gf /A via b 7→ ℓ(b)A. An
automorphism φ of Gf can then induces an automorphism β = φ B of B by taking images of the
cosets ℓ(b)A.
Lemma 4.4. Let f : B × B → A be a bilinear map and let φ ∈ Aut(Gf ) such that φ[A] = A. Let
β = φ B : B → B and define ℓφ = φℓβ −1 : B → Gf and ϕφ : B → A by ϕφ (b) = ℓ(b)ℓφ (b)−1 . Then
ϕφ ∈ Hom(B, A) if and only if f (b1 , b2 ) = f (β −1 b1 , β −1 b2 ) for all b1 , b2 ∈ B.

11

Proof. Let b1 , b2 ∈ B. Then

−1
ϕφ (b1 b2 ) = ℓ(b1 b2 ) φℓ(β −1 (b1 b2 ))
 
−1
= ℓ(b1 )ℓ(b2 )f (b1 , b2 )−1 φ ℓ(β −1 b1 )ℓ(β −1 b2 )f (β −1 b1 , β −1 b2 )−1
= ℓ(b1 )ℓ(b2 )ℓφ (b2 )−1 ℓφ (b1 )−1 f (b1 , b2 )−1 f (β −1 b1 , β −1 b2 )

= ℓ(b1 )ℓφ (b1 )−1 ϕφ (b2 )f (b1 , b2 )−1 f (β −1 b1 , β −1 b2 )
= ϕφ (b1 )ϕφ (b2 )f (b1 , b2 )−1 f (β −1 b1 , β −1 b2 )
Now, ϕφ is a homomorphism if and only if ϕφ (b1 b2 ) = ϕφ (b1 )ϕφ (b2 ) for all b1 , b2 ∈ B. By the above
calculation, this holds if and only if f (b1 , b2 )−1 f (β −1 b1 , β −1 b2 ) = 1 for all b1 , b2 ∈ B.
Next, we show that every automorphism of Gf that fixes the sets A and ℓ[B] induces an isometry
of f .
Lemma 4.5. Let f : B × B → A be a bilinear map and let φ ∈ Aut(Gf ) such that φ[A] = A and
φ[ℓ[B]] = ℓ[B]. Then β = φ B : B → B is an isometry of f .
Proof. Let b ∈ B. Then φℓ(b) ∈ φ[ℓ(b)A] = ℓ(βb)A. Since this holds for all b ∈ B, we have
φℓ(β −1 b) ∈ ℓ(b)A. Since φ[ℓ[B]] = ℓ[B], we see that in fact, φℓ(β −1 b) = ℓ(b). Hence, ϕφ = 1, which
is a homomorphism. Lemma 4.4 then implies that β is an isometry of f .
We are now ready to reduce BI to GrI∗ .
Theorem 1.6. BI is polynomial-time many-one reducible to GrI∗ .
Proof. Let f : B × B → A be an instance of BI and construct the group Gf . The order of this
group is |A| |B|, which is polynomial in the size of our instance of BI by Definition 1.5. We wish
to compute the subgroup Aut(Gf )A,ℓ[B] of Aut(Gf ) that maps A to A and ℓ[B] to ℓ[B]. This is
a subgroup of Sym(B) × Sym(A) that acts on Gf by (π, σ)(ℓ(b)a) = ℓ(πb)σa. Therefore, we can
compute Aut(Gf )A,ℓ[B] of Aut(Gf ) by solving a GrI∗ problem for the group Sym(B) × Sym(A).
By Lemma 4.5, for each φ ∈ Aut(Gf )A,ℓ[B] , β = φ B is an isometry of f . Moreover, by
Lemma 4.3, for every isometry β : B → B of f , there is an automorphism φ ∈ Aut(Gf )A,ℓ[B]
such that β = φ B . It follows that we can compute the isometry group of f from Aut(Gf )A,ℓ[B] in
polynomial time. Therefore, BI is many-one reducible to GrI∗ in polynomial time.

Acknowledgements
We thank Laci Babai for discussing his Holomorph idea with us. FLG is supported by the Grant-inAid for Young Scientists (A) No. 16H05853 and the Grant-in-Aid for Scientific Research (A) No. 16H01705
of the Japan Society for the Promotion of Science, and the Grant-in-Aid for Scientific Research on
Innovative Areas No. 24106009 of the Ministry of Education, Culture, Sports, Science and Technology in Japan. DJR was funded by a Japan Society for the Promotion of Science Postdoctoral
Fellowship No. PE15020.

12

Equivalence of CI and GI∗

A

We now give the proof of Theorem 1.3.
Theorem 1.3. CI and GI∗ are equivalent under polynomial-time many-one reductions.
Proof. We start with the reduction from GI∗ to CI . Let X and Y be graphs and suppose that we
wish to find an isomorphism from X to Y in a subcoset σΓ the maps the vertices of X to those of
Y . The reduction is immediate once we extend each σπ ∈ σΓ to map7 X × X to Y × Y and define
colors according to the graphs X and Y .
The reduction from CI to GI∗ is slightly more complicated. Let σΓ be a subcoset of permutations
acting on a set X and let f1 : X → [n] and f2 : X → [n] be as in Definition 1.1. We define graphs
Xi for i ∈ {1, 2} as follows. The vertices of Xi consist of the vertices of X as well as certain gadgets
that encode the colors. For each distinct fi (x) ∈ fi [X], we add a vertex labelled fi (x) and create a
copy Kfi (x) of the complete graph on fi (x)+2 colors. We add an edge from the vertex fi (x) to every
vertex in Kfi (x) . Finally, we connect every vertex x′ 6= x ∈ X such that fi (x′ ) = fi (x) to the vertex
fi (x). Since complete subgraphs of size 3 or larger appear only as the gadgets Kfi (x) ⊎ {fi (x)},
it is easy to see that the graph isomorphisms from X1 to X2 correspond precisely to the color
isomorphisms of the set X. This completes the reduction.

7

For the purposes of the color isomorphism problem, we regard each σπ as a permutation of X ⊎ Y .

13

References
[1] V. Arvind and J. Toran. Solvable group isomorphism is (almost) in NP ∩ coNP. In 19th Annual
IEEE Conference on Computational Complexity, pages 91–103, 2003.
[2] L. Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of
the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 684–697, 2016,
1512.03547.
[3] L. Babai. Moderately exponential bound for graph isomorphism. In Proceedings of the 1981
International FCT-Conference on Fundamentals of Computation Theory, pages 34–50, 1981.
[4] L. Babai. Trading group theory for randomness. In Proceedings of the Seventeenth Annual
ACM Symposium on the Theory of Computing, pages 421–429, 1985.
[5] L. Babai, P. Codenotti, J. A. Grochow, and Y. Qiao. Code equivalence and group isomorphism.
In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 1395–1408, 2011.
[6] L. Babai, P. Codenotti, and Y. Qiao. Polynomial-time isomorphism test for groups with no
abelian normal subgroups (extended abstract). In 39th International Colloquium on Automata,
Languages and Programming, pages 51–62, 2012.
[7] L. Babai, W. M. Kantor, and E. M. Luks. Computational complexity and the classification
of finite simple groups. In Proceedings of the 24th Annual Symposium on Foundations of
Computer Science, pages 162–171, 1983.
[8] L. Babai and E. M. Luks. Canonical labeling of graphs. In Proceedings of the Fifteenth Annual
ACM Symposium on Theory of Computing, pages 171–183, 1983.
[9] L. Babai and Y. Qiao. Polynomial-time isomorphism test for groups with abelian Sylow towers.
In 29th International Symposium on Theoretical Aspects of Computer Science, pages 453–464,
2012.
[10] R. B. Boppana, J. Håstad, and S. Zachos. Does coNP have short interactive proofs? Information Processing Letters, 25(2):127–132, 1987.
[11] P. Brooksbank and J. Wilson. Computing isometry groups of hermitian maps. Transactions
of the American Mathematical Society, 364(4):1975–1996, 2012.
[12] J. J. Cannon and D. F. Holt. Automorphism group computation and isomorphism testing in
finite groups. Journal of Symbolic Computation, 35(3):241–267, 2003.
[13] P. Codenotti. Testing Isomorphism of Combinatorial and Algebraic Structures. PhD thesis,
University of Chicago, 2011.
[14] O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or
all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):690–728,
1991.

14

[15] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof
systems. SIAM Journal on computing, 18(1):186–208, 1989.
[16] J. Grochow and Y. Qiao. Algorithms for group isomorphism via group extensions and cohomology. In Proceedings of the 29th IEEE Conference on Computational Complexity, pages
110–119, 2014, 1309.1776.
[17] J. A. Grochow and Y. Qiao. Polynomial-time isomorphism test of groups that are tame
extensions. In The 26th International Symposium on Algorithms and Computation, pages
578–589, 2015, 1507.01917.
[18] C. J. Hillar and D. L. Rhea. Automorphisms of finite abelian groups. The American Mathematical Monthly, 114(10):917–923, 2007, math/0605185.
[19] R. Impagliazzo and R. Paturi. Complexity of k-SAT. In Proceedings of the Fourteenth Annual
IEEE Conference on Computational Complexity, pages 237–240, 1999.
[20] T. Kavitha. Linear time algorithms for Abelian group isomorphism and related problems.
Journal of Computer and System Sciences, 73(6):986–996, 2007.
[21] F. Le Gall. Efficient isomorphism testing for a class of group extensions. In 26th International
Symposium on Theoretical Aspects of Computer Science, pages 625–636, 2009, 0812.2298.
[22] M. Lewis and J. Wilson. Isomorphism in expanding families of indistinguishable groups.
Groups-Complexity-Cryptology, 4(1):73–110, 2012.
[23] R. Lipton, L. Snyder, and Y. Zalcstein. The Complexity of Word and Isomorphism Problems
for Finite Groups. Defense Technical Information Center, 1977.
[24] E. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal
of Computer and System Sciences, 25(1):42–65, 1982.
[25] E. M. Luks. Group isomorphism with fixed subnormal chains. 2015, 1511.00151.
[26] P. P. Pálfy. A polynomial bound for the orders of primitive solvable groups. Journal of Algebra,
77(1):127–137, 1982.
[27] P. Papakonstantinou. The depth irreducibility hypothesis. Electronic Colloquium on Computational Complexity, 2014. TR14-124.
[28] L. Pyber. Asymptotic results for permutation groups. In Workshop on Groups and Computation, 1991.
[29] Y. Qiao, J. Sarma, and B. Tang. On isomorphism testing of groups with normal Hall subgroups.
In 28th International Symposium on Theoretical Aspects of Computer Science, pages 567–578,
2011.
[30] 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.

15

[31] D. J. Rosenbaum. Bidirectional collision detection and faster deterministic isomorphism testing. April 2013, 1304.3935. Submitted to Theoretical Computer Science.
[32] J. Rotman. An Introduction to the Theory of Groups. Graduate Texts in Mathematics.
Springer, 1995.
[33] C. Savage. An O(n2 ) algorithm for Abelian group isomorphism. Computer Studies Program,
North Carolina State University, 1980.
[34] Á. Seress. Permutation Group Algorithms. Cambridge Tracts in Mathematics. Cambridge
University Press, 2003.
[35] N. Vikas. An O(n) algorithm for Abelian p-group isomorphism and an O(n log n) algorithm
for Abelian group isomorphism. Journal of Computer and System Sciences, 53(1):1–9, 1996.

16

