Authors James B. Wilson,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25
www.theoryofcomputing.org
The Threshold for Subgroup Profiles to
Agree is Logarithmic
James B. Wilson∗
Received December 20, 2016; Revised October 19, 2019; Published December 21, 2019
Abstract: For primes p > 2 and e > 3 there are at least pe−3 /e groups of order p2e+2 that
have equal multisets of isomorphism types of proper subgroups and proper quotient groups,
isomorphic character tables, and power maps. This obstructs recent speculation concerning
a path towards efficient isomorphism tests for general finite groups. These groups have a
special-purpose deterministic polynomial-time isomorphism test.
ACM Classification: F.2.2
AMS Classification: 68Q17, 20D15, 20F69, 68Q25
Key words and phrases: group isomorphism, profiles, p-groups
1 Introduction
The problem G RAPH I SO asks if two graphs of order n are isomorphic. A recent breakthrough by Babai
c
has reduced the complexity of G RAPH I SO to nO((log n) ) for some c ≥ 1 [1]. An obstacle to improving this
bound is the problem G ROUP I SO, which asks if two finite groups given by their multiplication tables are
isomorphic. As implied by work of Hedrlín-Pultr [16] and shown also by Miller [23], G ROUP I SO ≤P
G RAPH I SO. Amongst the many problems that reduce to G RAPH I SO, G ROUP I SO generates attention.
See [12] for a list of many of the key algorithms over the years. As a complexity problem, G ROUP I SO
is interesting in part because its worst-case analysis is largely unchanged from what we obtain by a
brute-force algorithm. Specifically, by comparing minimal generating sets one can decide isomorphism
against a group G of order n in time nd(G)+O(1) where d(G) denotes the minimum size of a generating
set of a group G. By Lagrange’s theorem d(G) ≤ log2 n which gives a bound on the complexity of
∗ This research was supported in part by NSF grant DMS 1620454.
© 2019 James B. Wilson
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2019.v015a019
JAMES B. W ILSON
G ROUP I SO of nlog2 n+O(1) . Rosenbaum explored variations of such algorithms that lowered the bound to
n0.5 log2 n+O(1) [27].
A stronger bound on d(G) clarifies the cases of group isomorphism that are most concerning. Using
the prime factorization n = pe11 · · · pes s , we define the following parameter:
µ(pe11 · · · pes s ) = max{e1 , . . . , es }. (1.1)
Guralnick [15] proved that d(G) ≤ µ(n) + 1. As n → ∞, the number of integers n for which µ(n) ≤ c
tends to 1/ζ (c + 1)—the reciprocal of the zeta function (see, e. g., [30]). So for 99% of group orders n,
group isomorphism is solved in time polynomial in n; see [11, 10] for an exploration of the complexity of
group isomorphism based on the prime factorization of n.
The above suggests that to locate worst-case complexity of group isomorphism we should consider
groups of order n = p` , p prime, which are known as p-groups. Indeed, families of p-groups exist which
when given to present-day group isomorphism tests, e. g., those in [12], require nO(log p n) operations. In
light of these difficulties, and the reductions by Pultr–Hedrlín and Miller, the complexity of p-group
isomorphism appears to be a real obstacle to the improvement of graph isomorphism.
Recent speculation by Gowers [14] (see, e. g., Babai [1, p. 693]) posed the possibility of using a
portion of the subgroups of a finite group to determine isomorphism types of finite groups. Isomorphism
tests have been successfully using such ideas as heuristics for some time; see, e. g., fingerprinting in
[12]. Yet, proving efficiency based on these heuristics has been obstructed by 90-year-old examples by
Rottlaender and others, that show that subgroup lattices do not characterize groups up to isomorphism
[28].
In [14] Gowers introduced a threshold criterion based on the following. We say that a group is
d-generated if d(G) ≤ d. The d-subgroup profile of a group G is the multiset of isomorphism types of
d-generated subgroups of G. Define κ(G) as the minimum d such that the d-profile of G determines the
isomorphism type of G, and finally define
κ(n) = max{κ(G) | n = |G|}.
Evidently κ(G) ≤ d(G) and so κ(n) ≤ µ(n) + 1. Comparing κ(n)-profiles of groups of order n decides
isomorphism in time n2κ(n)+O(1) . Gowers asked for
√ examples where κ(n) ∈ / O(1). Glauberman and
`
Grabowski [13] gave instances to show κ(p ) ∈ Ω( `). We prove
Theorem 1.2. For a prime p > 2, κ(p` ) ∈ Θ(`). In particular, isomorphism testing of p-groups by
comparing subgroup profiles requires nΘ(log p n) time in the worst case.
To prove Theorem 1.2 we begin with primes p > 2 and e > 3 then set q = pe . Let Fq be a finite field
of order q and define the Heisenberg group over Fq as
1 α γ
H = H(Fq ) = 1 β α, β , γ ∈ Fq . (1.3)
1
Our interest is in the quotients of H, which we collect according to their orders.
Hgp,e = {G | ∃N C H(F pe ), |H(F pe ) : N| = p2e+g and G ∼
= H(F pe )/N}. (1.4)
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 2
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
We shall see the groups in Hgp,e with −2e ≤ g ≤ 0 are all elementary abelian and so they are isomorphic
to Z2e+g
p . When g = 1 the groups are nonabelian but each is what P. Hall called extraspecial of exponent
p and they are pairwise isomorphic (Theorem 4.9). However for 1 < g ≤ e we see increasing diversity.
Our focus is on g = 2.
Theorem 1.5. H2p,e has at least pe−3 /e isomorphism classes; yet, the groups in H2p,e have equal multisets
of isomorphism types of proper subgroups, and also of proper quotient groups.
The groups in H2p,e are an extreme illustration of the difficulty to capture group isomorphism by a list
of invariants. In Section 6.1 we list numerous other similarities including character tables, conjugacy
classes, and at times automorphism groups.
Despite these observations, the following class of groups has an efficient solution to the membership
and isomorphism problems.
[ [
Hp = Hge,p . (1.6)
e 1≤g≤e
For computation a group G can be given by numerous methods, most commonly, by permutations,
matrices, or polycyclic presentations; see [29]. The complexity of operations in these models differs,
so we adopt the black-box group model—as introduced by Babai–Szemerédi, see [29, Chapter 2]. We
further assume an oracle for group orders. This means we can access compactly encoded generators for
the group G, we can compute all group operations, and we can compute |G|, but we model these tasks as
requiring only constant time. In prior work with Lewis, the author proved the following.
Theorem 1.7 ([21]). Fix a prime p. For groups given as a black-box with an order oracle, there are
deterministic polynomial-time algorithms that
(a) given a group G, decides if G ∈ H p ; and
(b) given groups G, Ḡ ∈ H p , decides if G ∼
= Ḡ.
All permutation groups and their quotients have deterministic polynomial-time algorithms for the
necessary black-box group oracles and to find a group’s order, see [29, Chapter 3]. Since the rows of
the multiplication table of a group G are a faithful permutation representation of G, we consider the
multiplication table model as the special case of regular permutation groups. In the context of matrix
groups G we assume p is bounded. In that case work of Luks implies that we can decide in polynomial
time if G is a p-group and if so to compute |G| [22]. So in both these models we can replace “black-box
polynomial time” with simply “polynomial time.” The computational complexity of groups given by
polycyclic presentations is nuanced, but in general polynomial-time algorithms for the necessary oracles
are not known, see [19, Section 4], [20]. Even so the reports of practical performance with polycyclic
groups (e. g., [29, Section 7.2]) suggest they are equally useful input models.
The algorithms of [21] have a complexity of O(p + e2ω log2 p), where 2 ≤ ω < 3 is the exponent
of matrix multiplication, see [31, Chapter 12]. In the special case of groups in H2p,e , Brooksbank,
Maglione, and the author give an O(p3 + eω log2 p)-time algorithm [7]. Note that it takes Ω(e2 log2 p)
bits to input the groups in H2p,e by any of the standard methods, including matrices, presentations, or
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 3
JAMES B. W ILSON
permutations. These algorithms have been implemented in the computer algebra system Magma [5]
and decide isomorphism for groups as large as n = 5256 in about an hour on a general-purpose personal
computer [7, Figure 1.1]. The algorithms in [7] further give a complete invariant for the groups in H2p,e ,
which is a homogeneous polynomial of degree e in F p [x, y]. This implies that the number of isomorphism
classes in H2p,e is at most pe ; see [7, Proposition 9.2].
Some of the steps in the proof of Theorem 1.5 can be extracted as special cases of results in [21, 8, 7].
However, there is an increased need to provide an introduction into the methods in those works. We have
made this exposition largely self-contained and we rely as much as possible on proofs based in linear
algebra as found in [18].
Preliminaries
General claims about groups can be found in [25]. We assume all groups in this note are finite. The
Frattini subgroup Φ(G) is the intersection of the maximal subgroups of G. The exponent of a group G is
the least positive integer m such that for every g ∈ G, gm = 1. The commutator subgroup G0 is the smallest
normal subgroup whose quotient is abelian, equivalently the subgroup generated by the commutators
[x, y] = x−1 xy = x−1 y−1 xy. Z(G) denotes the center of G. We write G p = hx p | x ∈ Gi. As in [7], we
borrow terminology from Lie theory and say the genus of a group G of nilpotence class 2 and exponent p
is
p-genus(G) = log p |G| − d(G). (1.8)
We will critically involve the following fact found in [25, p. 140].
Theorem 1.9 (Burnside Basis Theorem). For a p-group G, Φ(G) = G0 G p and G/Φ(G) ∼
d(G)
= Zp .
We will make frequent use of the fact that Zdp is both an abelian group and a natural F p -vector space.
In this work all rings, algebras, and modules are unital (have a unit element), and subrings use the same
unit as the superring. For emphasis we write A ≤ B for subsets which also are substructures such as
subgroups and subalgebras. Finally we write GLd (Fq ) for the group of invertible linear automorphisms
on Fdq , and SLd (Fq ) for the subgroup of transformations with determinant 1.
2 A formula for subgroup profiles
We prove a formula that, under some hypotheses, calculates the subgroup profiles in p-groups. This
allows us to construct groups that produce the same profile without need to directly compare the groups.
Theorem 2.1. Let G be a p-group in which Aut(G) acts transitively on maximal subgroups and such that
for a maximal subgroup M of G, d(G) = 1 + d(M). Then for every J < G, the size of J(J) = {K < G |
K∼= J} is
1+d(M)
p1+d(M) − 1
∑ K≤M K∼
= J and |M : KΦ(M)| = p f −1 .
f =1 pf −1
Hence the profile map J 7→ |J(J)| depends only on the isomorphism type of a maximal subgroup of G.
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 4
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
While the hypothesis of Theorem 2.1 is restrictive, in Proposition 5.1 we demonstrate that the
automorphism groups of groups G ∈ Hgp,e each contain SL2 (F pe ) acting transitively on the maximal
subgroups of G, just as SL2 (F pe ) acts transitively on F p -hyperplanes of F2e ∼
p = G/Φ(G). Having targeted
this particular action may help expose the reason we chose Heisenberg groups H(F pe ) at the start. Similar
constructions can be fashioned for example from the symplectic group Sp2m (F p2e ) and other linear
subgroups.
Lemma 2.2. Let G be a p-group G with a maximal subgroup M having d(G) = 1 + d(M). Then
Φ(G) = Φ(M).
Proof. Using the Burnside Basis Theorem on G and on M we calculate
|G : Φ(G)| · |Φ(G)| pd(G) |Φ(G)| |Φ(G)|
1= = 1+d(M) = .
|G : M| · |M : Φ(M)| · |Φ(M)| p |Φ(M)| |Φ(M)|
As Φ(M) = M 0 M p ≤ G0 G p = Φ(G), we find that Φ(M) = Φ(G).
Proof of Theorem 2.1. Fix J < G. We use an Aut(G)-invariant partition
d(G)
J(J) = J(J, f ), J(J, f ) = K ∈ J(J) |G : KΦ(G)| = p f .
[
f =1
Let M be the set of maximal subgroups of G and fix M ∈ M with d(G) = 1 + d(M).
Fix f and define a bipartite graph between the two sets J(J, f ) and M, such that (K, X) ∈ J(J, f ) × M
is an edge if, and only if, K ≤ X. The action of Aut(G) on this graph permutes the vertices of M
transitively. In particular, the degree of every vertex X ∈ M is the same as the degree of M. Apply
Lemma 2.2 to conclude that Φ(G) = Φ(M). Thus, for every K ≤ M, KΦ(G) = KΦ(M) and so
deg M = K ≤ M K ∼ = J, |G : KΦ(G)| = p f
= K≤M K∼ = J, |M : KΦ(M)| = p f −1 .
Next we compute the degree of K ∈ J(J, f ), i. e., the size of the set
{X ∈ M | K ≤ X} = {X ∈ M | KΦ(G) ≤ X}.
Since G/Φ(G) ∼
d(G)
= Z p and |G : KΦ(G)| = p f it follows that
(G/Φ(G))/(KΦ(G)/Φ(G)) ∼
= Z pf .
In particular the number of maximal subgroups of G containing K equals the number of hyperplanes in
an f -dimensional F p -vector space.
At this point we count the number of edges in our graph in two ways.
pd(G) − 1 pf −1
deg M = ∑ deg X = ∑ deg K = |J(J, f )| .
p−1 X∈M K∈J(J, f )
p−1
Thus |J(J, f )| = deg M · (p1+d(M) − 1)/(p f − 1). The theorem follows.
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 5
JAMES B. W ILSON
3 Making p-groups with matrices
We are interested in quotients of groups of (3 × 3)-matrices, but it will be easier to discuss properties of a
larger class of groups. For that we use a general constructions of p-groups that has roots in studies of
Brahana and Baer [6, 2]. Throughout this section F = F p is the field of coefficients.
Fix a set {T1 , . . . , Tg } of (r × c)-matrices. Here and throughout empty blocks in matrices are presumed
to be 0 and > denotes the transpose. Define
1 u w
> · · · T v>
Ir T1 v g
for u ∈ Fr , v ∈ Fc and w ∈ Fg .
M(u, v, w) := (3.1)
Ig
We abbreviate u ∗ v = (uT1 v> , . . . , uTg v> ) and witness multiplication of these matrices behaves as follows.
M(u, v, w)M(u0 , v0 , w0 ) = M(u + u0 , v + v0 , w + w0 + u ∗ v0 ) ,
[M(u, v, w), M(u0 , v0 , w0 )] = M(0, 0, u ∗ v0 − u0 ∗ v) ,
i i
M(u, v, w) = M iu, iv, iw + u∗v .
2
From these we fashion the following group of matrices.
B(T1 , . . . , Tg ) = {M(u, v, w) | u ∈ Fr , v ∈ Fc , w ∈ Fg }. (3.2)
Proposition 3.3. Assuming B = B(T1 , . . . , Tg ) the following hold.
(i) B0 ≤ {M(0, 0, w) | w ∈ Fgp } with equality whenever hu ∗ v | u ∈ Fr , v ∈ Fc i = Fg .
(ii) Z(B) ≥ {M(0, 0, w) | w ∈ Fgp } with equality if i Null(Ti ) = 0, where Null(Ti ) = {u | uTi = 0}.
T
(iii) If p > 2, then M(u, v, w) p = 1; hence, Φ(B) = B0 and dimhT1 , . . . , Tg i is the genus of B.
> r+c+g .
i Null(Ti ) = 0, then |B| = p
T
(iv) If
3 2
Notice if r, s, g ≈ n/3 then there are pn /27+Θ(n ) distinct tuples T∗ = (T1 , . . . , Tg ). Yet d(B(T∗ )) ∈ O(n)
2 3 2
so the number of isomorphism classes is bounded by pO(n ) . As a result these groups comprise pn /27+Θ(n )
pairwise distinct isomorphism types of groups of order pn . Sims has shown the total number of groups of
3 2.5
order pn is p2n /27+O(n ) [4, Chapters 4 & 5]. So despite its humble appearance, this family is extremely
complex.
As our fields F pe are finite, there exists an ω ∈ F pe such that F pe = F p (ω). Hence, {1, ω, . . . , ω e−1 }
(k)
is a basis for F pe as an F p -vector space. Define t(ω)i j ∈ F p as the structure constants so that
e−1
(k)
ω i · ω j = ∑ t(ω)i j ω k .
k=0
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 6
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
(k)
Also let Tk ∈ Me (F p ) be such that [Tk+1 ](i+1)( j+1) = t(ω)i j .
Example 3.4. If F pe = F p (ω) then H(Fq ) ∼
= B(T1 , . . . , Te ).
In the next section we shall prove the following theorem.
Theorem 3.5. For primes p and e, G ∈ H2p,e if, and only if, there are invertible (e × e)-matrices (T1 , T2 )
such that G ∼
= B(T1 , T2 ) where T1−1 T2 has an irreducible minimal polynomial of degree e.
3.1 Subgroups by row, column, and matrix elimination
One way to explore the subgroups of the groups B(T1 , . . . , Tg ) is to restrict the range of values of u or v in
the formula given in (3.2). For instance, suppose we restrict the coordinate ui = 0. The result is that the
values in the i-th row of each matrix T1 , . . . , Tg can be ignored within that subgroup. Hence the subgroup
we get is isomorphic to the group we obtain by first removing the i-th row of each matrix in {T1 , . . . , Tg }
and then using the construction of (3.2) to create a group on these smaller matrices. Removing one row
produces a maximal subgroup, two rows a subgroup of index p2 , and so on. A similar idea applies to
columns. Reversing the process and inserting rows or columns creates subgroup embeddings.
Restricting values of w in (3.2) may result in a subset that is not closed under multiplication. A way
to avoid that concern is to eliminate entries wi only once the corresponding matrix Ti = 0.
Example 3.6. To build an embedding of Brahana groups, e. g., H(F3 ) into H(F9 ), we may add matrices
to our list of matrices, or add to the rows and columns of the matrices we posses. In this example we let
a0 a1
F9 = a0 , a1 ∈ F3 .
−a1 a0
We display the concatenations as partitioned matrices.
H(F3 ) ∼
= B([1]) ,→ B([1], [0])
,→ B([1|0], [0|1])
1 0 0 1 ∼
,→ B , = H(F9 ).
0 1 −1 0
Using this process in reverse (removing rows, columns, or matrices) lets us explore many of the
subgroups of Brahana groups. We emphasize that this approach is not guaranteed to explore every
subgroup.
In light of Theorem 2.1 we build a family of groups each having a maximal subgroup of a fixed
isomorphism type. As in [18, p. 70], for a polynomial a(t) = a0t 0 + · · · + ae−1t e−1 + t e ∈ F p [t], the
companion matrix will be
0 1
.. ..
C(a(t)) = . .
.
0 1
a0 · · · ae−1
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 7
JAMES B. W ILSON
Lemma 3.7. For a polynomial a(t) of degree e, the group G = B(Ie ,C(a(t))) has a maximal subgroup M
whose isomorphism type depends only on p, e, and d(G) = 1 + d(M).
Proof. We delete the last row of Ie and C(a(t)) to obtain
e e
z }| {
z }| {
1 0 0 1
. . . . .. ..
M = B , ,→
. . . .
1 0 0 1
1 0 0 1
.. .. .. ..
. . , . .
B = G.
1 0 0 1
0 ··· 1 a0 · · · ae−1
Evidently pd(M) = |M : Φ(M)| = p2e−1 = pd(G)−1 .
3.2 Quotient groups by linear combinations
Next we will want some quotient groups of B(T1 , . . . , Tg ). One can see in (3.2) that for each subset
{i1 , . . . , is } ⊆ {1, . . . , g}, there is a natural surjection B(T1 , . . . , Tg ) → B(Ti1 , . . . , Tis ) and that is indeed a
group homomorphism. This is an analogue to the way we created subgroups in the previous section.
Along with reducing the number of matrices we can take linear combinations. Given scalars
(a1 , . . . , ag ) there is an epimorphism from B(T1 , . . . , Tg ) to B(a1 T1 + · · · + ag Tg ). More generally given a
(g0 × g)-matrix A, there is an epimorphism
!
g g
B(T1 , . . . , Tg ) 7→ B ∑ A1 j Tj , . . . , ∑ Ag0 j Tj .
j=1 j=1
3.3 Notable isomorphisms
There are also direct ways to create groups isomorphic to B(T1 , . . . , Tg ). For example, for invertible
matrices X ∈ Mr (F p ) and Y ∈ Mc (F p ),
B(T1 , . . . , Tg ) ∼
= B(XT1Y > , . . . , XTgY > ).
We may also permute the order of the matrices. In particular we can always insist the first matrix have
largest rank and that it be expressed in the form
Ia 0
0 0
through Gaussian elimination. Thus the groups B(T1 ) can be classified up to isomorphism by the rank of
T1 .
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 8
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
More generally, for each i, j ∈ {1, . . . , g}, and s ∈ F×
p,
B(T1 , . . . , Tg ) ∼
= B(T1 , . . . , Ti + sT j , . . . , Tg ) ∼
= B(T1 , . . . , sTi , . . . , Tg ).
Thus, if {T10 , . . . , Tg0 } is another basis for hT1 , . . . , Tg i, then B(T1 , . . . , Tg ) ∼
= B(T10 , . . . , Tg0 ). There can be
further isomorphisms between these groups, but these will suffice for our present discussion.
Using these observations we can make even more complex embeddings.
Lemma 3.8. For every a(t), b(t) ∈ F p [t] with deg b(t) =: f < e := deg a(t), there is an embedding
B(I f ,C(b(t))) into B(Ie ,C(a(t))).
We emphasize that b(t) has no relation to a(t) other than having lower degree. So there is no algebraic
reason to guess the possible embedding of B(I f ,C(b(t))) into B(Ie ,C(a(t))). Manipulating matrices
demonstrates how this is done.
Proof. Fix b0 , . . . , be−2 ∈ F p .
1
1 0 . 1 0
.. ..
..
.. ..
= . , (3.9)
. . .
1
1 0 1 0
b0 . . . be−2 1
1
0 1 . 0 1
.. ..
..
.. ..
= . (3.10)
. . . .
1
0 1 b0 . . . be−2 1
b0 . . . be−2 1
Thus, setting b(t) = b0t 0 +· · ·+be−2t e−2 +t e−1 , we obtain the following embedding. For the isomorphism
we are using the identity B(T1Y > , T2Y > ) ∼
= B(T1 , T2 ) following the calculation of (3.9) and (3.10).
1 0 0 0 1 0
. . . . .. .. .. .
B(Ie−1 ,C(b(t))) ,→ B . . , . ..
. .
1 0 b0 . . . be−2 1
1 0 0 1
= B . . . . . . , . . . . . .
∼
1 0 0 1
,→ B(Ie ,C(a(t))).
Remark 3.1. In light of Theorem 3.5, Lemma 3.8 shows that the groups in H2p,e each have pΩ(e)
isomorphism types of proper subgroups.
Proposition 3.11. Given (e × e)-matrices (T1 , . . . , Tg ) where T1 is invertible, there are polynomials
a1 (t)| · · · |am (t) of polynomials in F p [t], and matrices T̃3 , . . . , T̃g such that
B(T1 , . . . , Tg ) = B(Ie ,C(a1 (t)) ⊕ · · · ⊕C(am (t)), T̃3 , . . . , T̃g ).
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 9
JAMES B. W ILSON
Proof. Use the Frobenius Normal Form [18, p. 93] to find a divisor chain a1 (t)| · · · |am (t) and an invertible
matrix X such that
X −1 (T1−1 T2 )X = C(a1 (t)) ⊕ · · · ⊕C(am (t)).
Hence,
B(T1 , T2 , . . . , Tg ) ∼
= B(Ie , T1−1 T2 , . . . , T1−1 Tg )
∼
= B(Ie ,C(a1 (t)) ⊕ · · · ⊕C(am (t)), . . . , X −1 T −1 Tg X).
1
So for 3 ≤ i ≤ g, set T̃i = X −1 T1−1 T2 X.
4 Isomorphisms between quotients of Heisenberg groups
We have so far created many groups and demonstrated ways to construct varied subgroups and quotients.
Our effort now shifts back to Heisenberg groups and in particular we will tackle the question of isomor-
phisms and automorphisms within H2p,e . Our main results in this section are proofs of Theorem 3.5 and
the following result.
Theorem 4.1. Every isomorphism between nonabelian quotients of H of genus g > 1 lifts to an automor-
phism of H.
This is a special case of [21, Theorem 4.4]. We give a self-contained and largely matrix-based proof.
4.1 The role of commutation
A first principle in the theory of nilpotent groups is to treat groups like algebras by invoking commutation
[x, y] = x−1 xy = x−1 y−1 xy as a skew-commutative multiplication. This very nearly distributes over the
usual product, in the following way.
[xy, z] = [x, z]y [y, z], [x, yz] = [x, z][x, y]z . (4.2)
With q = pe and H = H(Fq ), commutation takes the following form.
1 α0 γ0 1 0 αβ 0 − α 0 β
1 α γ
1 β, 1 β 0 = 1 0 . (4.3)
1 1 1
This shows the following two groups are abelian.
1 0 γ
H 0 = [H, H] = 1 0 γ ∈ Fq , H/H 0 ∼
= {(α, β ) | α, β ∈ Fm
q }.
1
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 10
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
Evidently there are isomorphisms
ι : H/H 0 → hF2q , +i and ι̂ : H 0 → hFq , +i. (4.4)
None of these isomorphisms is natural in the category of groups. In particular neither H/H 0 nor H 0 is an
obvious Fq -vector space as scalar multiplication is not part of the operations of a group.
Normal subgroups are characterized as follows.
Lemma 4.5. For h ∈ H − H 0 , [h, H] = H 0 ; thus, if N is normal in H then either H 0 ≤ N or N ≤ H 0 .
4.2 Quotients of H
To inspect the quotients of H we use a method to “linearize” a nilpotent group which is in some sense the
reversal of the constructions we gave in Section 3. Early versions of this approach were described by
Brahana and Baer [2, 6].
Since elements in H 0 = [H, H] commute with the whole group, the identities (4.2) imply that commuta-
tion factors through H/H 0 × H/H 0 → H 0 and thereby affords a biadditive map [, ]+ : hF2q , +i × hF2q , +i →
hFq , +i,
0 0 0 0 0 1
[(α, β ), (α , β )]+ = αβ − α β = (α, β ) (α 0 , β 0 )> . (4.6)
−1 0
To distinguish between the various roles of [, ] we let [, ] denote group commutation and [, ]+ the biadditive
mapping that commutation produces.
Remark 4.1. The expression in (4.6) is misleading. While αβ 0 and α 0 β are defined in Fq , our codomain
is technically the elementary abelian group hFq , +i and the specific identification depends on the perhaps
arbitrary choice of maps (ι, ι̂) of (4.4). Within isomorphism testing such small intuitive leaps can hide
challenging computations and on a theoretical level it remains to be justified that the maps (ι, ι̂)—which
are not Fq -linear, nevertheless preserve the geometric properties of an Fq -bilinear form. A more precise
formulation of (4.6) capable of addressing these concerns is given below in (4.8).
Now Lemma 4.5 shows that for N < H 0 , (H/N)0 = H 0 /N. So the commutation of the quotient H/N
will accordingly afford a new biadditive map
H/N π
[, ]+ : hF2q , +i × hF2q , +i → hFq , +i → Zgp
where π is given as the homomorphism hFq , +i ∼ = H 0 → H 0 /N ∼
g
= Z p . The genus of H/N is the value g.
Let us look closely at the case of genus g = 1. Fix π : hFq , +i → Z p . Choose a basis {α1 , . . . , αe } for
hFq , +i as an F p -vector space and such that π(αi ) = 1 if i = 1 and 0 otherwise. Define
Ti j = π([(αi , 0), (0, α j )]) = π(αi α j ).
Observe
Ti j = π(αi α j ) = π(α j αi ) = T ji . (4.7)
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 11
JAMES B. W ILSON
So T = T > . Regarded as a map of F p -vector spaces we see
0
H/N 0 T α
[(α, β ), (α , β 0 )]+ = α
0
β .
−T 0 β0
H/N
As we vary H/N amongst groups of arbitrary genus 1 ≤ g ≤ e we describe [, ]+ = [, ]+ by a list of
linearly independent invertible symmetric matrices T1 , . . . , Tg ∈ Me (F p ) such that
0 T1 α 0 0 Tg α 0
0 0
[(α, β ), (α , β )]+ = α β ,..., α β . (4.8)
−T1 0 β 0 −Tg 0 β 0
This demonstrates the following correspondence.
Theorem 4.9 (Brahana correspondence). A group H/N whose commutation is described by linearly
independent invertible symmetric matrices (T1 , . . . , Tg ) where H/N ∼
= B(T1 , . . . , Tg ). In particular all
quotients H/N of genus 1 are isomorphic.
Proof. The (T1 , . . . , Tg ) are described above. Recall M(u, v, w) from (3.1). The required isomorphism
B(T1 , . . . , Tg ) → H/N is as follows.
1 ι −1 (u) ι̂ −1 (w)
M(u, v, w) 7→ 1 ι −1 (v) mod N.
1
If g = 1 then H/N ∼
= B(T1 ) ∼
= B(Ie ).
Corollary 4.10. The groups in H2p,e have equal multisets of isomorphism types of proper quotient groups.
Proof. Fix N ≤ H 0 with |H : N| = p2e+2 . As p2e+2 = |H : H 0 | · |H 0 : N| = p2e |H 0 : N| we find that
|H 0 : N| = p2 , and so H/N has genus 2. As in Lemma 4.5, if N < K ≤ H and K/N is normal in H/N, then
K < H 0 or H 0 ≤ K. If H 0 ≤ K then (H/N)/(K/N) ∼ = H/K ∼
f
= Z p where p f = |H : K|. This does not depend
on the choice of N. The number of choices for K is the number of subgroups in Z2e p of index f , which
again does not depend on N. Otherwise N < K < H 0 and so |H 0 : K| = p. Thus (H/N)/(K/N) ∼ = H/K
has genus 1. So by Theorem 4.9 its isomorphism type is fixed and independent of N. Finally, H /N ∼
0
= Z2p
0
so there are exactly p + 1 choices of K with N < K < H . This is independent of N.
4.3 Distributive products
Throughout this section F = F p and q = pe . To prove Theorem 4.1 we need a brief detour to discuss
distributive products. Take a subset S ⊆ Mr (F) × Mc (F). Note that we do not require that S be a subring
or have any algebraic structure, though often S is a generating set for some interesting algebraic structure;
see Remark 4.2. Recall > denotes transpose. Define
Fr ⊗S Fc := {X ∈ Mr×c (F) | ∀(L, R) ∈ S, L> X = XR}. (4.11)
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 12
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
We further develop Fr ⊗S Fc into a distributive product. First Mr×c (F) = (Fr ⊗S Fc ) ⊕ K(S) where
K(S) := hL> X − XR | X ∈ Mr×c (F), (L, R) ∈ Si. (4.12)
The map πS from Mr×s (F) onto Fr ⊗S Fc with kernel K(S) lets us define a distributive tensor product
⊗ = ⊗S : Fr × Fc → Fr ⊗S Fc , u ⊗ v = πS (u> v).
Notice for (L, R) ∈ S, πS (L> X) = πS (XR) and so we find
(uL) ⊗ v = πS (L> (u> v)) = πS ((u> v)R) = u ⊗ (vR).
Example 4.13. Let C ∈ Me (F) such that K = {∑i aiCi | ai ∈ F} ≤ Me (F p ) is a field of order pe , e. g.,
take C to be the companion matrix of an irreducible polynomial of degree e. Then consider the following
set of operators in M2e (F) × M2e (F).
>
Ie 0 C 0 0 Ie 0 −Ie
S= , , , .
0 C 0 Ie Ie 0 −Ie 0
By solving the system of linear equations of (4.11) we find
2e 2e 0 α 0 Ie
F ⊗S F = α ∈ K = SpanK .
−α > 0 −Ie 0
In particular F2e ∼ 2 2e 2e ∼ 2 2
p = K and F p ⊗ F p = K, and ⊗S : K × K → K is the same as the mapping in (4.6).
Turning now to a general distributive product ◦ : Fr × Fc → Fg , we can ask if ◦ is related to ⊗S . We
do so by comparing codomains, specifically we define
⊗S → ◦ :≡ (∃τ : Fr ⊗S Fc → Fg )(u ◦ v = τ(u ⊗S v)). (4.14)
We say ◦ factors through ⊗S ; see [8, (2.4)].
4.4 Adjoint algebras of distributive products
Section 4.3 imagined we possessed a set S of operators from which we craft a product. However our
circumstance is reversed. We have distributive products [, ]+ arising from groups G ∈ Hgp,e , and these
products have no associated operators. Even so, we have seen hints, e. g., (4.8), that when we identify G
with a quotient of H(Fq ), then the operators Fq seem applicable to the analysis of [, ]+ . We cannot expect
to recover something arbitrary like Fq from [, ]+ , rather we must set our sights on some form of universal
operators for [, ]+ , as those will persist independent of representation. We turn to a device introduced in
[32] known as the adjoint algebra of a product.
Definition 4.15. Fix a distributive product ◦ : Fr × Fc → Fg . An adjoint pair (L, R) ∈ Mr (F) × Ms (F)
satisfies the following for each u ∈ Fr and each v ∈ Fc
(uL) ◦ v = u ◦ (vR).
The adjoint algebra Adj(◦) is the set of all adjoint pairs of ◦.
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 13
JAMES B. W ILSON
As the name suggests, Adj(◦) is an algebra, i. e., an F-vector space with an F-bilinear associative
unital multiplication. However, the multiplication is not coordinatewise but requires a twist as follows
(L1 , R1 )(L2 , R2 ) = (L1 L2 , R2 R1 ). (4.16)
The composition in the second component is also referred to as op-multiplication. This makes Adj(◦) a
subring of what is commonly denoted M2e (F) × M2e (F)op . Indeed Adj(◦) is a unital subalgebra—all our
rings, modules and algebras to follow are unital. Given structure constants for ◦, such as those given in
(4.8) for the products [, ]+ , then we can compute a basis for Adj(◦).
As intended, Adj(◦) is a universal set of operators in the following sense. Recall (4.14).
Theorem 4.17 (Adjoint-tensor Galois correspondence [8, Theorem 2.11]). Fix a distributive product
◦ : Fr × Fc → Fgp and S ⊆ Mr (F) × Ms (F). Then
S ⊆ Adj(◦) ⇐⇒ ⊗S → ◦.
In particular we obtain two closure operations: S ⊆ Adj(⊗S ) and ⊗Adj(◦) → ◦. Furthermore
Adj(◦) = Adj(⊗Adj(◦) ), ⊗S = ⊗Adj(⊗S ) .
Notice if A is subalgebra of Mr (F) × Ms (F)op generated as an algebra by a set S, then
Fr ⊗Adj(⊗S ) Fc ⊆ Fr ⊗A Fc ⊆ Fr ⊗S Fc = Fr ⊗Adj(⊗S ) Fc .
That is, Fr ⊗S Fc = Fr ⊗A Fc = Fr ⊗Adj(⊗S ) Fc . In this way one sees there is no advantage to assuming at
the start that we have an algebra over which we tensor.
Remark 4.2. Historically Whitney introduced tensor products as requiring rings, and that assumption
has been carried into the literature, for example [17, Section IV.5]. We have demonstrated that the ring
assumption has no actual role in defining tensor products and it is often a barrier to calculations. Indeed,
even if we intend to tensor over a ring A, it is often the case that A is a proper subring of Adj(⊗A ). So
to insist on a fixed ring A is arbitrary. It would be enough to regard the image of A as a set and appeal
to Adj(⊗A ) for any necessary ring theory. The main point is Fr ⊗S Fc = Fr ⊗Adj(⊗S ) Fc and the left-hand
side is a more flexible construction.
There are two optional assumptions we have made for simplicity but which may be removed. The first
is to use matrices instead of constructing U ⊗S V as a quotient of some infinite abelian group. Secondly,
it would be enough to consider functions S → Mr (F) × Mc (F) instead of subsets.
One helpful observation is the ability to identify extension of scalars without prior assumptions.
Lemma 4.18. Let K ≤ Me (F) be a subalgebra. If ◦ : K r × K c → K g is biadditive and furthermore
satisfies
(∀α ∈ K) (αu) ◦ v = α(u ◦ v) = u ◦ (αv),
u ◦ K c = 0 only if u = 0, and K r ◦ v = 0 only if v = 0; then for every (L, R) ∈ Adj(◦),
(αu)L = α(uL), (αv)R = α(vR).
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 14
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
Proof. The proof is a so-called “three pile shuffle” of the operators:
((αu)L) ◦ v = (αu) ◦ (uR) = α(u ◦ (vR)) = α((uL) ◦ v) = (α(uL)) ◦ v.
As this is for each v and ((αu)L − α(uL)) ◦ K c = 0, we get that (αu)L = α(uL). Do likewise with R.
Example 4.19. Let F pe = F p (ω) and C = C(ω) be the matrix of left multiplication matrix of by ω on
hF pe , +i ∼
= Fep . For H = H(F pe ), [, ]H ∼ i
+ as defined in (4.3) with N = 1, and F pe = K = {∑i aiC | ai ∈ F} ≤
Me (F), we calculate that
α β δ −β
H
Adj([, ]+ ) = , α, β , γ, δ ∈ K ∼= M2 (Fq ).
γ δ −γ α
Furthermore, hF pe , +i ∼
= hF2pe , +i ⊗Adj([,]H+ ) hF2pe , +i.
Proof. Consider the matrices (T1 , . . . , Te ) of (4.3). Notice from their definition that for each α ∈ K
αTi = [(α, 0), (0, 1)]+ = [(0, 1), (α, 0)]−1
+ = Ti α. (4.20)
In particular CTi = TiC for each i. Hence, S from Example 4.13 is contained in Adj([, ]H
+ ). So, by the
Adjoint-Tensor Galois Correspondence (Theorem 4.17),
⊗S → ⊗Adj([,]H+ ) .
That means there is a τ : K ∼
= F2e 2e 0
p ⊗S F p → hFq , +i = H which is surjective because of Proposition 3.3(i).
By dimensions this is an (F p -linear) isomorphism. In particular Adj([, ]H
+ ) = Adj(⊗S ). From Exam-
2 2
ple 4.13, ⊗S : K × K → K satisfies the hypothesis of Lemma 4.18 so Adj(⊗S ) ⊆ M2 (K) × M2 (K).
Furthermore, letting
0 1
J= ,
−1 0
and (L, R) ∈ Adj(⊗S ), L> J = JR so R = J −1 L> J. Therefore, Adj(⊗S ) = {(L, J −1 L> J) | L ∈ M2 (K)}.
4.5 Adjoint algebras of Heisenberg group commutation
Now we refocus on the goal of Theorem 4.1.
Lemma 4.21. Fix a unital F p -subalgebra K ≤ Me (F p ) where K is a field of order pe . If A ≤ Me (F p ) is
a unital F p -subalgebra containing K, and e prime, then A = K or Me (F p ).
Proof. Let V = Fep be the natural (left) module for Me (F p ). So V is also an A-module and an F-vector
space. Note that V is 1-dimensional as a K-vector space. As K ≤ A, it follows that for every 0 6= v ∈ V ,
V = Kv = Av. So V is a simple A-module; hence, A is faithfully represented on a simple module V , that
is A is primitive. By the Wedderburn-Artin theorem, A is therefore isomorphic to M f (∆) for a finite
division ring ∆ [17, p. 421]. By the Dickson-Wedderburn theorem ∆ ∼ = F ps for some s [17, p. 462]. Lastly,
e = dimF p V = s dimF ps V = f s. As e is prime either f = 1 and A = K, or else f = e and s = 1 which
makes A = Me (F p ).
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 15
JAMES B. W ILSON
Lemma 4.22. If H/N has genus g > 1 then Adj([, ]H ∼ H/N
+ ) = Adj([, ]+ ) = M2 (Fq ).
Proof. We start by observing some necessary adjoints. By the adjoint-tensor Galois correspondence,
H/N op
Adj([, ]H
+ ) ≤ Adj([, ]+ ). Now we claim this is an equality (as subalgebras of M2e (F p ) × M2e (F p ) ).
We know that the commutation in H/N is given by a set {T1 , . . . , Tg } of linearly independent invertible
H/N
symmetric matrices (4.7). So the linear equations to solve to describe Adj([, ]+ ) are the following. For
each 1 ≤ i ≤ g,
>
L11 L12 0 Ti 0 Ti R11 R12
= .
L21 L22 −Ti 0 −Ti 0 R21 R22
For i = 1 we get
−1 >
R11 R12 0 T1 L11 L12 0 T1
= .
R21 R22 −T1 0 L21 L22 −T1 0
Now i = 2 ≤ g adds the further constraints Li j (T1−1 T2 ) = (T1−1 T2 )Li j . (Here we take advantage of the
assumption that the Ti are symmetric but this condition can be relaxed at the expense of a more complex
formula at this stage.)
Now consider the subalgebra C(T1−1 T2 ) = {L ∈ Me (F p ) | LT1−1 T2 = T1−1 T2 L}. Then
( −1 > ! )
H/N L11 L12 0 T1 L11 L12 0 T1
Adj([, ]+ ) ≤ , Li j ∈ C(T1−1 T2 )
L21 L22 −T1 0 L21 L22 −T1 0
∼
= M2 (C(T1−1 T2 ).
H/N
By restricting to the first components of Adj([, ]H + ) ≤ Adj([, ]+ ), and invoking Example 4.19, we obtain
M2 (K) ≤ M2 (C(T1 T2 )) and by first restricting to the upper right block we have K ≤ C(T1−1 T2 ) ≤
−1
Me (F p ). If C(T1−1 T2 ) = Me (F p ) then T1−1 T2 commutes with every matrix and thus T1−1 T2 is a scalar
matrix. However, T2 and T1 are linearly independent. So T1−1 T2 cannot be scalar. As a result C(T1−1 T2 ) 6=
Me (F p ). By Lemma 4.21, C(T1−1 T2 ) = K. That is,
H/N α β δ −β
Adj([, ]+ ) ≤ , α, β , γ, δ ∈ Fq = Adj([, ]H
+ ).
γ δ −γ α
H/N
So indeed Adj([, ]H
+ ) = Adj([, ]+ ).
Proof Theorem 3.5. Fix G ∈ H2p,e . By Theorem 4.9 we know there are linearly independent symmetric
invertible matrices (T1 , T2 ) such that G ∼
= B(T1 , T2 ) ∼
= B(Ie , T1−1 T2 ). Let a(t) be the minimal polynomial
of this new T1 T2 . As T1 is independent of T2 , we know that T1−1 T2 cannot be a scalar matrix and so a(t)
−1
has degree at least 2. We need to show deg a(t) = e.
Now let C(T1−1 T2 ) = {L ∈ Me (F p ) | LT1−1 T2 = T1−1 T2 L}. Following the calculation of the adjoint
ring above we know that
Adj([, ]+ ) ∼
H/N
= M2 (C(T1−1 T2 )).
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 16
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
Thus, if B(T1 , T2 ) is a quotient of H then C(T1−1 T2 ) ∼= Fq . Since F p [t]/(a(t)) ∼
= F p [T1−1 T2 ] ≤ C(T1−1 T2 ) it
−1
follows that F p [T1 T2 ] is a subfield of Fq . As a(t) has degree greater than 1 and Fq has no intermediate
fields, it follows that F p [T1−1 T2 ] = Fq . Thus a(t) is an irreducible polynomial of degree e.
Conversely if T2 is conjugate to C(a(t)) then
H/N ∼
Adj [, ]+ = M2 (Fq ) ∼ = Adj([, ]H+ ).
By the Adjoint-Tensor Galois correspondence, the commutation in B(Ie , T1−1 T2 ) factors through the tensor
product over Adj([, ]H
+ ). By Example 4.19 that tensor is also the commutation of H. So B(T1 , T2 ) is a
quotient of H.
Remark 4.3. At this point we can sketch the concepts behind the algorithms in Theorem 1.7(a), which
we recall serve to recognize when a group G, given as a black-box group, is a quotient of a Heisenberg
group. A key step is to construct the ring Adj([, ]G
+ ) and recognize if it isomorphic to M2 (F pe ) for some
e. If so then the commutation in G naturally factors through the tensor over M2 (F pe ) which we saw in
Example 4.19 gives us the commutation of H(F pe ). See [7, 21] for details.
4.6 Automorphisms of Heisenberg groups
Now we need to consider the automorphisms of H, assuming p > 2. Each automorphism is described by
three constituents:
1. a homomorphism τ : hF2q , +i → hFq , +i,
α β
2. an invertible matrix over Fq , and
γ δ
3. a field automorphism α 7→ ᾱ of Fq .
The corresponding automorphism is as follows.
1 α0 γ0 1 α 0 α + β 0 γ (αδ − β γ)γ 0 + τ(α 0 , β 0 )
1 β 0 7→ 1 α 0β + β 0δ . (4.23)
1 1
Theorem 4.24. Every automorphism of H has the form of (4.23).
Our proof will follow the one give in [21, Proposition 2.9 & Theorem 4.1]. The automorphisms
arising from (1), with parts (2) and (3) the identity, form the subgroup of so-called central automorphisms.
We include them for completeness but remark that they do not influence our proofs to follow.
Remark 4.4. Statements in the literature about the automorphism groups of the of Heisenberg groups
based on symplectic geometry can be misunderstood. Most claims concern F p , Z, R and C, and in the
latter cases considers only smooth automorphisms. As we cautioned in Remark 4.1, in the case of Fq ,
[, ]+ : hF2q , +i × hF2q , +i → hFq , +i is Fq -bilinear but [, ] : H/H 0 × H/H 0 → H 0 is only biadditive. So only
the cases of Z and F p are immediate by standard geometric methods. One must recover the missing ring
structure of the coefficients before appealing to geometric reasoning.
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 17
JAMES B. W ILSON
We saw in Example 4.19 that the commutation of Heisenberg groups is actually a special type of
distributive product, a tensor product. This means instead of acting on a biadditive map we can act on a
ring Adj([, ]+ ) ∼
= M2 (Fq ).
Theorem 4.25 (Skolem-Noether [18, p. 237]). The ring automorphisms of M2 (Fq ) are Y 7→ X −1Ȳ X
where X is an invertible 2 × 2 matrix and α → ᾱ is a field automorphism of Fq applied to each entry of
X.
Proof. First the automorphism φ will send αI2 7→ ᾱI2 which gives us the field automorphism σ . Re-
−1
placing φ with φ (Y σ ) we now have an Fq -linear automorphism. That function maps the minimal right
ideal nh i o
α β
0 0
: α, β ∈ F q
to another minimal right ideal, either
nh i o nh i o
0 0 γ δ
γ δ : γ, δ ∈ F q or νγ νδ
: γ, δ ∈ Fq ,
for some ν ∈ Fq . Each of these is a 2-dimensional vector space over Fq so that transformation can be
given by an invertible square matrix X.
Lemma 4.26. There is an epimorphism Aut(H) → Aut(M2 (Fq )). The kernel consists of the central
automorphisms of H.
Proof. Let φ : H → H be an automorphism. Since φ ([h, k]) = [φ (h), φ (k)], φ factors through F2e ∼
p =
H/H 0 → H/H 0 ∼ = F2e
p . So we let X be the matrix representing that transformation. Also we let X̂ be the
matrix describing the restriction of φ to Fep ∼
= H0 → H0 ∼
= Fep . Notice (X, X̂) satisfy
[(α, β )X, (α 0 , β 0 )X]+ = [(α, β ), (α 0 , β 0 )]+ X̂.
Now take (L, R) ∈ Adj([, ]+ ). It follows that
[(α, β )X −1 LX, (α 0 , β 0 )]+ = [(α, β )X −1 L, (α 0 , β 0 )X −1 ]+ X̂
= [(α, β ), (α 0 , β 0 )X −1 RX]+ .
In this way Aut(H) acts on Adj([, ]+ ) ∼= M2 (Fq ). We saw that commutation in Aut(H) is the same as
the tensor product with Adj([, ]+ ) (Example 4.19). So every automorphism of Adj([, ]+ ) determines an
automorphism of H. If (X, X̂) is the identity pair then φ is a central automorphism by definition.
Proof of Theorem 4.1. In the Brahana correspondence (Theorem 4.9) we saw that every nonabelian
H/N
quotient H/N is determined up to isomorphism by the matrices (T1 , . . . , Tg ) which also define [, ]+ . Fix
an isomorphism φ : H/N1 → H/N2 . Since (H/Ni )/(H/Ni )0 ∼ = H/H 0 ∼ = hF2q , +i, we see φ determines a
matrix
A B
X= ∈ M2e (F p ).
C D
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 18
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
Using the isomorphism τ : hFq , +i → hF2q , +i ⊗M2 (Fq ) hF2q , +i described in Example 4.19, we define
Γ : H → H as follows. If c ∈ hFq , +i and cτ = ∑i (ai , bi ) ⊗ (xi , yi ), then define
1 a c 1 aA + bC ∑i (ai , bi )X ⊗ (xi , yi )X
1 b 7→ 1 aB + bD .
1 1
From our proof of Lemma 4.26 we notice Γ is an automorphism of H if, and only if, X −1 Adj([, ]+ )X =
Adj([, ]+ ). Since φ is an isomorphism H/N1 → H/N2 we know that
H/N H/N
X −1 Adj [, ]+ 1 X = Adj [, ]+ 2 .
H/N
By Lemma 4.22 we know Adj ([, ]+ ) = Adj [, ]+ i . So Γ ∈ Aut(H) and Γ(N1 ) = N2 and induces φ .
Corollary 4.27. The set H2e+2
p,e has at least p
e−3 /e isomorphism types.
Proof. The number of subgroups N < H 0 of index p2 is the number of subspaces of codimension 2 in an
F p -vector space H 0 ∼
= Fep . That number is
(pe − 1)(pe − p)
.
(p2 − 1)(p − 1)
Meanwhile the action by Aut(H) on H 0 has order e(pe − 1); see (4.23). So the number of orbits is at least
pe−3 /e. By Theorem 4.1 these orbits are in bijection with isomorphism types so the result follows.
Remark 4.5. The proof of Theorem 4.1 and the analysis in Corollary 4.27 mimics how we efficiently
test isomorphism of quotients of Heisenberg groups as announced in Theorem 1.7(b). We transform the
question into one of asking if two F p -subspaces of F pe are in the same orbit under F×
pe o Gal(F pe ). As
×
discovered by Rónyai (see [21, Lemma 4.8]), the orbits under F pe can be decided by solving a system of
linear equations. The remaining action by Gal(F pe ) has small orbits.
5 Proof of Theorem 1.5
In Corollary 4.27 we used the fact that the representation of Aut(H) on H 0 induces the group F× pe o
Gal(F pe ). Now we use the fact that the kernel of that representation induces the group SL(2, F pe ) on
H/H 0 .
Proposition 5.1. For every N ≤ H 0 , Aut(H/N) acts transitively on the maximal subgroups of H/N.
We need a few observations, compare [25, p. 135 & 140].
Lemma 5.2. In a group G, for a normal subgroup N contained in Φ(G) (including N = 1), Φ(G/N) =
Φ(G)/N and the maximal subgroups of G are in bijection with those in G/N and with those in G/Φ(G).
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 19
JAMES B. W ILSON
Lemma 5.3. For a p-group G, there is a bijection between the maximal subgroups of G and the projective
d(G) d(G)
points in (F p )> —the dual space of F p . In particular Aut(G) acts transitively on its maximal
d(G)
subgroups if, and only if, the induced action of Aut(G) on (F p )> is transitive on projective points.
d(G)
Proof. By the Burnside basis theorem there is an isomorphism τ : G/Φ(G) → F p . Since each max-
imal subgroup M of G contains Φ(G), M/Φ(G) is maximal in G/Φ(G) and so W = τ(M/Φ(G)) is a
d(G)
hyperplane. In particular W is identified with {φ ∈ (F p )> | W φ = 0} as a projective point in W > .
Lemma 5.4. The natural action of SL2 (F pe ) on the dual space (F2pe )> (i. e., the action on column-vectors)
is transitive on non-zero vectors, and therefore also on projective points.
Proof. We show (1, 0) can reach both (α, β ) and (0, α), provided α 6= 0, using determinant 1 matrix.
0 −α −1
α 0 1 α 1 0
−1 = = .
β α 0 β α 0 0 α
Proof of Proposition 5.1. Fix N C H such that |H : N| = p2e+2 . Because N ≤ Φ(H), by Lemma 5.2, the
maximal subgroups of H are in bijection of those of H/N. Following Proposition 3.3 we know H 0 = Φ(H)
and (H/N)/Φ(H/N) ∼ = H/Φ(H) ∼ = F2e
p .
Notice from Theorem 4.24 that there is a subgroup
CAut(H) (H 0 ) = {φ ∈ Aut(H) | (H 0 )φ = 1H 0 }.
As N < H 0 , there is a homomorphism
ρ : CAut(H) (H 0 ) → Aut(H/N).
Furthermore, ρ faithfully embeds the automorphisms of H induced by matrices
α β
γ δ
with determinant 1, as described in Theorem 4.24. In particular there is a representation of
SL2 (F pe ) → Aut(H/N)
with the natural action on F2pe ∼
= (H/N)/Φ(H/N). By Lemma 5.4, this action is transitive on projective
points. By Lemma 5.3 it follows that Aut(H/N) acts transitively on the maximal subgroups of H/N.
Proof of Theorem 1.5. Corollaries 4.27 & 4.10 establish that the set H2e+2
p,e has at least p
e−3 /e isomor-
phism types and that these groups all have the same multiset of isomorphism types of proper quotient
groups. Finally, Proposition 5.1 and Lemma 3.7 allow us to invoke Theorem 2.1 to conclude the proof.
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 20
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
6 Closing remarks
6.1 Further comparisons of the groups H/N
The groups in H2p,e are an extreme illustration of the difficulty to capture isomorphism by a list of
invariants. Along with equivalent profiles we summarize the following further similarities.
Each G ∈ H2 has G0 = Z(G) = Φ(G) ∼
p,e = Z2 . Also the groups have isomorphic lattices of normal
p
subgroups. They have exponent p and the same multiset of conjugacy class sizes (Lemma 4.5).
Next we remark that for any fixed g ≤ e, the groups in Hgp,e have isomorphic character tables [21,
Section 6.2]. (See [25, p. 232] for definitions and basic implications of character tables.) In fact a
stronger property holds. Observe that character table columns are indexed by conjugacy classes of a
group. Because (g−1 xg)m = g−1 xm g we can speak of the m-th power map as as function on conjugacy
classes of G. An often strong isomorphism invariant of groups is to consider character table isomorphisms
that also preserve all powers on the conjugacy classes. For instance, the examples of Rottlaender have
isomorphic character tables as well but they are distinguished when in addition we add the power-map
constraint. For a p-group it suffices to consider the p-th powers. Brauer asked if non-isomorphic groups
could have an isomorphism of character tables that also preserves the powers of conjugacy classes of the
group. Dade [9] provided examples using groups of order p7 , class 3 and exponent p. Our examples are
of class 2, and they also answer Brauer’s question providing an infinite family with character tables as
large as possible amongst groups of exponent p. See Nenciu [24] for examples with composite exponent.
The groups in Hgp,e are directly and centrally indecomposable and with the same algebraic type
of indecomposability (an invariant introduced in [32, Theorem 4.41] and [33, Theorem 8], that links
indecomposability to isomorphism types of local commutative rings and local Jordan algebras). These
features are explored in [21, Section 5].
Finally we argue that automorphisms often agree, though we cannot guarantee that they always agree.
By Theorem 4.1 we have that for G ∈ H2p,e ,
Aut(G) ,→ ΓL2 (F pe ) n M2e×2 (F p ), ΓL2 (F pe ) = Gal(F pe /F p ) n GL2 (F pe ).
Then in our proof of Proposition 5.1 we observed
CAut(G) (G0 ) := SL2 (F pe ) n M2e×2 (F p ) ,→ Aut(G).
This means the number of choices for Aut(G) can be bounded by counting the subgroups of
ΓL2 (F pe )/SL2 (F pe ) ∼
= Ze n Z(pe −1)/2 .
Furthermore, CAut(G) (G0 ) is the kernel of the induced representation Aut(G) → GL2 (F p ) given by the
action on G0 ∼
= Z2p . In particular, Aut(G)/CAut(G) (G0 ) embeds into both the subgroups of Ze n Z(pe −1)/2
and GL2 (F pe ). This limits the order of Aut(G)/CAut(G) (G0 ) to divisors of
` = gcd (p(p − 1)(p + 1), e(pe − 1)/2) ∈ O(p3 ).
Whenever e - `, then it follows that the `-subgroups of Ze n Z(pe −1)/2 lie in Z(pe −1)/2 and are thus unique.
So the total number of choices for Aut(G) as subgroups of ΓL2 (F pe ) is at most the number of subgroups
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 21
JAMES B. W ILSON
of a cyclic group of order `, which is O(log `) ⊆ O(log p). By Theorem 1.5 we know H2e+2
p,e have at
least pe−3 /e distinct isomorphism types and only O(log p) choices for automorphisms. So equivalent
automorphism groups, as subgroups of Aut(H), are common.
For example when p = 3 and e = 7 then ` = 1. So for each G ∈ H2·7+2
3,7 ,
Aut(G) = SL2 (F37 ) n M2e×2 (F p )
as a subgroup of Aut(H(F37 )). Meanwhile there are at least 19 isomorphism types in H2·7+2
3,7 .
6.2 Complete invariants
Pivoting to methods that do give information, Barnes and Wall [3] show that the subgroup lattice of a
nilpotent group of class 2 and exponent p determines the isomorphism type of the group (which corrects
an errant remark of the author). Yet, the groups in Hgp,e have maximum sized lattices with |G|Θ(log |G|)
subgroups, chains of length log p |G| and antichains of length |G|Θ(log p |G|) . Presently we have no tools to
compare such large lattices.
Since standard isomorphism invariants are proving unhelpful we suggest one non-standard but
effective tool. The idea of a polynomial invariant was suggested to the author by Rónyai [26]. The
following version was defined in [7].
For groups G ∼= B(T1 , T2 ) in H2p,e , we define the generalized Pfaffian as
Pf(T1 , T2 ) = det(x1 T1 + x2 T2 ) ∈ F p [x1 , x2 ]. (6.1)
As B(T1 , T2 ) ∼
= B(I2 ,C(a(t)), the generalized Pfaffian can in fact be computed efficiently as the homog-
enization of a(t). The lex-least representative of the orbit of the generalized Pfaffian under the action
by GL2 (F p ) is a defining invariant as proved in [7]. (Note that that work deals with a far more general
problem.)
Sketch of Proof of Theorem 1.7. The recognition of the class H p begins by using a suite of now standard
algorithms to determine if a group G is a p-group of nilpotence class 2 and exponent p. That work
depends on many algorithms, notably by Sims and Luks; see [29].
The next stage constructs the commutator map [, ]G + for G and solves a system of linear equations
G
to compute the adjoint algebra Adj([, ]+ ). Using results of Rónyai, Ivanyos, Brooksbank-Luks, and the
author we constructively recognize Adj([, ]G + ) together with its op-composition structure; see [21, 8].
Following Theorem 3.5 (and more general versions) this leads to a constructive recognition of the
quotients of Heisenberg groups. The solution of the system of linear equations to compute Adj([, ]G +)
dominates the calculation and takes O(e2ω log2 p) bit operations.
Having recognized quotients of Heisenberg groups we turn to their isomorphism problem. The first
method of [21] builds on Remark 4.5 which shows how to set up a relatively small search problem with
in the Galois group of F pe . In each step of the search we solve a system of linear equations to decide if
there is an isomorphism. This leads to an O(e2ω log2 p)-time isomorphism test.
For the faster variation we must solve the system of linear equations without a quadratic blow-up. For
adjoints this is done in work of Brooksbank and the author. We avoid the later linear algebra problem that
arises in the search question by using (6.1). We compute the lex-least representative under the action of
GL2 (F p ). This leads to a complexity of O(p3 + eω log p). See [7] for details and references.
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 22
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
Acknowledgment
Thanks to Laci Babai & Gene Luks who asked me about profiles and offered useful comments on this
article, to Bill Kantor for extensive feedback on this article, and to the referees for catching blunders and
improving the exposition.
References
[1] L ÁSZLÓ BABAI: Graph isomorphism in quasipolynomial time [extended abstract]. In Proc. 48th
STOC, pp. 684–697. ACM Press, 2016. [doi:10.1145/2897518.2897542, arXiv:1512.03547] 1, 2
[2] R EINHOLD BAER: Groups with abelian central quotient group. Trans. Amer. Math. Soc., 44(3):357–
386, 1938. [doi:10.2307/1989886] 6, 11
[3] D ONALD W. BARNES AND G ORDON E. WALL: On normaliser preserving lattice iso-
morphisms between nilpotent groups. J. Austral. Math. Soc., 4(4):454–469, 1964.
[doi:10.1017/S1446788700025295] 22
[4] S IMON R. B LACKBURN , P ETER M. N EUMANN , AND G EETHA V ENKATARAMAN: Enumera-
tion of finite groups. Volume 173 of Cambridge Tracts in Math. Cambridge Univ. Press, 2007.
[doi:10.1017/CBO9780511542756] 6
[5] W IEB B OSMA , J OHN C ANNON , AND C ATHERINE P LAYOUST: The Magma algebra system I: The
user language. J. Symbolic Comput., 24(3–4):235–265, 1997. [doi:10.1006/jsco.1996.0125] 4
[6] H. R. B RAHANA: Metabelian groups and trilinear forms. Duke Math. J., 1(2):185–197, 1935.
[doi:10.1215/S0012-7094-35-00117-X] 6, 11
[7] P ETER A. B ROOKSBANK , J OSHUA M AGLIONE , AND JAMES B. W ILSON: A fast isomor-
phism test for groups whose Lie algebra has genus 2. J. Algebra, 473:545–590, 2017.
[doi:10.1016/j.jalgebra.2016.12.007] 3, 4, 17, 22
[8] P ETER A. B ROOKSBANK AND JAMES B. W ILSON: Groups acting on tensor products. J. Pure
Appl. Algebra, 218(3):405–416, 2014. [doi:10.1016/j.jpaa.2013.06.011, arXiv:1210.0827] 4, 13, 14,
22
[9] E VERETT C. DADE: Answer to a question of R. Brauer. J. Algebra, 1(1):1–4, 1964.
[doi:10.1016/0021-8693(64)90002-X] 21
[10] H EIKO D IETRICH AND JAMES B. W ILSON: Polynomial-time isomorphism testing of groups of
most finite orders, 2018. [arXiv:1806.08872] 2
[11] H EIKO D IETRICH AND JAMES B. W ILSON: Isomorphism testing of groups of cube-free order. J.
Algebra, 545:174–197, 2020. [doi:10.1016/j.jalgebra.2019.02.008, arXiv:1810.03467] 2
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 23
JAMES B. W ILSON
[12] B ETTINA E ICK , C HARLES R. L EEDHAM -G REEN , AND E AMONN A. O’B RIEN: Construct-
ing automorphism groups of p-groups. Communications in Algebra, 30(5):2271–2295, 2002.
[doi:10.1081/AGB-120003468] 1, 2
[13] G EORGE G LAUBERMAN AND Ł UKASZ G RABOWSKI: Groups with identical k-profiles. Theory of
Computing, 11(15):395–401, 2015. [doi:10.4086/toc.2015.v011a015] 2
[14] W. T IMOTHY G OWERS: Comment on Dick Lipton’s blog entry: The Group Isomorphism Problem:
A possible polymath problem? Blog entry started November 7, 2011. Comment cited: November
12, 2011. https://rjlipton.wordpress.com/2011/11/07/the-group-isomorphism-problem-a-possible-
polymath-problem. 2
[15] ROBERT M. G URALNICK: On the number of generators of a finite group. Archiv der Mathematik,
53(6):521–523, 1989. [doi:10.1007/BF01199809] 2
[16] Z DEN ĚK H EDRLÍN AND A LEŠ P ULTR: On full embeddings of categories of algebras. Illinois J.
Math., 10(3):392–406, 1966. [doi:10.1215/ijm/1256054991] 1
[17] T HOMAS W. H UNGERFORD: Algebra. Springer, 1980. [doi:10.1007/978-1-4612-6101-8] 14, 15
[18] NATHAN JACOBSON: Lectures in Abstract Algebra II. Linear Algebra. Springer, 1953.
[doi:10.1007/978-1-4684-7053-6] 4, 7, 10, 18
[19] C HARLES R. L EEDHAM -G REEN AND L EONARD H. S OICHER: Collection from the left and other
strategies. J. Symb. Comput., 9(5–6):665–675, 1990. [doi:10.1016/S0747-7171(08)80081-8] 3
[20] C HARLES R. L EEDHAM -G REEN AND L EONARD H. S OICHER: Symbolic collection using Deep
Thought. LMS J. Comput. Math., 1:9–24, 1998. [doi:10.1112/S1461157000000127] 3
[21] M ARK L. L EWIS AND JAMES B. W ILSON: Isomorphism in expanding families of indistinguish-
able groups. Groups Complexity Cryptology, 4(1):73–110, 2012. [doi:10.1515/gcc-2012-0008,
arXiv:1010.5466] 3, 4, 10, 17, 19, 21, 22
[22] E UGENE M. L UKS: Computing in solvable matrix groups. In Proc. 33rd FOCS, pp. 111–120. IEEE
Comp. Soc., 1992. [doi:10.1109/SFCS.1992.267813] 3
[23] G ARY L. M ILLER: Graph isomorphism, general remarks. J. Comput. System Sci., 18(2):128–142,
1979. Preliminary version in STOC’77. [doi:10.1016/0022-0000(79)90043-6] 1
[24] A DRIANA N ENCIU: Brauer t-tuples. J. Algebra, 322(2):410–428, 2009.
[doi:10.1016/j.jalgebra.2009.04.019] 21
[25] D EREK J. S. ROBINSON: A Course in the Theory of Groups. Springer, 1996. [doi:10.1007/978-1-
4419-8594-1] 4, 19, 21
[26] L AJOS R ÓNYAI: Private communication, 2011. 22
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 24
T HE T HRESHOLD FOR S UBGROUP P ROFILES TO AGREE IS L OGARITHMIC
[27] DAVID J. ROSENBAUM: Breaking the nlog n barrier for solvable-group isomorphism. In Proc. 24th
Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1054–1073. ACM Press, 2013.
[doi:10.1137/1.9781611973105.76, arXiv:1205.0642] 2
[28] A DA ROTTLAENDER: Nachweis der Existenz nicht-isomorpher Gruppen von gleicher Situation der
Untergruppen. Mathematische Zeitschrift, 28(1):641–653, 1928. [doi:10.1007/BF01181188] 2
[29] Á KOS S ERESS: Permutation Group Algorithms. Cambridge Univ. Press, 2003.
[doi:10.1017/CBO9780511546549] 3, 22
[30] H AROLD M. S TARK: On the asymptotic density of the k-free integers. Proc. Amer. Math. Soc.,
17(5):1211–1214, 1966. Available on JSTOR. 2
[31] J OACHIM VON ZUR G ATHEN AND J ÜRGEN G ERHARD: Modern Computer Algebra. Cambridge
Univ. Press, 1999. [doi:10.1017/CBO9781139856065] 3
[32] JAMES B. W ILSON: Decomposing p-groups via Jordan algebras. J. Algebra, 322(8):2642–2679,
2009. [doi:10.1016/j.jalgebra.2009.07.029, arXiv:0711.0201] 13, 21
[33] JAMES B. W ILSON: Existence, algorithms, and asymptotics of direct product decompositions, I.
Groups Complexity Cryptology, 4(1):33–72, 2012. [doi:10.1515/gcc-2012-0007] 21
AUTHOR
James B. Wilson
Associate professor
Department of Mathematics
Colorado State University
Fort Collins, Colorado, USA
James Wilson ColoState Edu
https://wwww.math.colostate.edu/~jwilson/
ABOUT THE AUTHOR
JAMES B. W ILSON graduated with his Ph. D. in Mathematics from the University of Oregon
in 2008 where he studied with Bill Kantor (advisor), Gene Luks, and Charley Wright.
Before this he spent nearly four years with the Intel Architecture Labs and still enjoys
questions from industry. As a sophomore he asked an innocent question about group
isomorphism to Professor F. Rudy Beyl, who kindly delayed a response and instead gave
him a copy of a lovely paper by Ada Rottlaender to find the answer himself. This sparked
the author’s now decades-long obsession with isomorphism in algebra and its complexity.
T HEORY OF C OMPUTING, Volume 15 (19), 2019, pp. 1–25 25