Authors George Glauberman, {\L}ukasz Grabowski,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 11 (15), 2015, pp. 395–401
www.theoryofcomputing.org
NOTE
Groups with Identical k-Profiles
George Glauberman Łukasz Grabowski
Received June 16, 2013; Revised November 30, 2015; Published December 23, 2015
p
Abstract: We show that for 1 ≤ k ≤ 2 log3 n − (5/2), the multiset of isomorphism types
of k-generated subgroups does not determine a group of order at most n. This answers a
question raised by Tim Gowers in connection with the Group Isomorphism problem.
ACM Classification: F.2.2
AMS Classification: 68Q17, 20D15, 20F69, 68Q25
Key words and phrases: group theory, nilpotent groups, p-groups, group isomorphism problem, algo-
rithms, lower bounds, k-generated group, k-profile of groups
1 Introduction
We say that a group is k-generated if it has a set of at most k generators. Let Gk be the set of isomorphism
types1 of all k-generated finite groups. Let G be a finite group. Following Gowers [3], we say that the
k-profile of G is the function fG : Gk → N defined by letting fG (H) be the number of subgroups of G
isomorphic to H (H ∈ Gk ).
Tim Gowers raised the question [3], for which k does the k-profile determine a group of order n ?
Such a k yields a simple isomorphism test2 in time nO(k) for groups of order n given by their Cayley
tables (see Section 3).
1 Two groups belong to the same isomorphism type if and only if they are isomorphic.
2 Regarding the significance of the Group Isomorphism problem to the Graph Isomorphism problem we refer the reader to
Section 13 of [1] and especially to footnote 9 in that section.
© 2015 George Glauberman and Łukasz Grabowski
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2015.v011a015
G EORGE G LAUBERMAN AND Ł UKASZ G RABOWSKI
Theorem 1.1. If p is an odd prime, k and n are positive integers, and
p
1 ≤ k ≤ 2 log n/ log p − (5/2) ,
then there exist nonisomorphic p-groups of order at most n with identical k-profiles.
Remark
p 1.2. In particular, setting p = 3, we see that if k and n are positive integers such that 1 ≤ k ≤
2 log3 n − (5/2), then there exist nonisomorphic groups of order at most n with identical k-profiles.
Our examples are p-groups of class 2 and exponent p.
Theorem 1.3. For any odd prime p and positive integer k there exist nonisomorphic p-groups of class 2,
exponent p, and order pN , where N = (k + 2)(k + 3)/2, with identical k-profiles.
2 The proof
Recall that a nilpotent group G is of class 2 if G0 ≤ Z(G), where G0 denotes the commutator subgroup
G0 = [G, G] and Z(G) denotes the center of G. For an odd prime p, a relatively free p-group P of class 2
and exponent p with m generators can be obtained from a free group with m generators by factoring out
all elements u p and all commutators [[u, v], w].
Fact 2.1. For real numbers m and k such that m ≥ k + 2, we have
m(m − 1)/2 ≥ 1 + mk − (k2 + k)/2 .
Proof. Let x = m − k − 2, so x ≥ 0 and we wish to show that f (x) ≥ 0 where
f (x) = (k + 2 + x)(k + 1 + x) − 2(k + 2 + x)k + k2 + k − 2 .
But then f (x) = x2 + 3x ≥ 0, as desired.
Fact 2.2. For an odd prime p and a positive integer k we have
2
(pk − 1)(pk − p) · · · (pk − pk−1 ) > (1/2)pk .
Proof.
∏k−1 k i
i=0 (p − p )
k ∞
1 1 1 1
2 = ∏ 1 − j
> 1 − ∑ pj = 1− p−1 ≥ 2 .
pk j=1 p j=1
Hypothesis 2.3.
(i) p is an odd prime,
(ii) m is a positive integer, and
(iii) P is a relatively free group with m generators, class two, and exponent p.
T HEORY OF C OMPUTING, Volume 11 (15), 2015, pp. 395–401 396
G ROUPS WITH I DENTICAL k-P ROFILES
Lemma 2.4. Assume Hypothesis 2.3. Suppose k is a positive integer such that m ≥ k + 2. Then there
exists an element of P0 that does not lie in Q0 for any k-generated subgroup Q of P.
Note. This is false for k = 2 and m = k + 1 = 3.
Proof. In this situation, P0 = Z(P), |P/P0 | = pm , and |P0 | = pm(m−1)/2 .
We claim that for every k-generated subgroup Q of P, there exists a k-generated subgroup R of P such
that R0 ≥ Q0 and |R/(R ∩ P0 )| = pk .
Indeed, let Q be a k-generated subgroup of P and pi = |Q/(Q ∩ P0 )| = |QP0 /P0 |. Let s1 , . . . , si be
elements of Q such that Q ∩ P0 together with s1 , . . . , si generate Q. Let S = hs1 , . . . , si i. Then i ≤ k. If
i = k, let R = S. If i < k then there exist elements si+1 , . . . , sk such that |RP0 /P0 | = pk for R = hs1 , . . . , sk i.
In both cases, |RP0 /P0 | = pk , |R0 | = pk(k−1)/2 , Q = S(Q ∩ P0 ) ≤ SP0 ≤ RP0 , and Q0 ≤ (RP0 )0 = R0 . This
proves the claim.
The number of distinct subgroups of the form RP0 is the same as the number of k-dimensional
subspaces of an m-dimensional vector space over the prime field F p . Call this number N(m, k). Then
(pm − 1)(pm − p) . . . (pm − pk−1 )
N(m, k) = . (1)
(pk − 1)(pk − p) . . . (pk − pk−1 )
Clearly, the numerator of N(m, k) is less than pmk . By Fact 2.2, the denominator is greater than
2 2 2
(1/2)pk . Therefore, N(m, k) < 2pmk−k . Since p ≥ 3, we have N(m, k) < pmk−k +1 .
Now we count the elements of P0 that lie in Q0 for some k-generated subgroup Q of P. Each such
element lies in (RP0 )0 for some subgroup RP0 as above. So we obtain the upper bound
pk(k−1)/2 N(m, k) < pe+1 (2)
for e = (k2 − k)/2 + mk − k2 = mk − (k2 + k)/2.
We saw above that |P0 | = pm(m−1)/2 . Fact 2.1 shows that
m(m − 1)/2 ≥ e + 1 .
This gives the desired conclusion.
Lemma 2.5. Assume Hypothesis 2.3 for a group P1 in place of P. Let d be a positive integer such that
m ≥ d + 2. Let P2 = hwi be a cyclic group of order p and P = P1 × P2 . Then there exists an element v of
P10 such that
(a) |hv, wi| = p2 ,
(b) P/hvi is not isomorphic to P/hwi, and
(c) for every d-generated subgroup Q of P we have Q0 ∩ hv, wi = 1.
Proof. By Lemma 2.4, P10 has an element v that does not lie in Q0 for any d-generated subgroup Q of P.
Then (a) is obvious. We obtain (b) because
(P/hvi)0 = P10 /hvi and (P/hwi)0 ∼
= P10 . (3)
T HEORY OF C OMPUTING, Volume 11 (15), 2015, pp. 395–401 397
G EORGE G LAUBERMAN AND Ł UKASZ G RABOWSKI
To obtain (c), let s1 , . . . , sd be d elements of P. Set R = hs1 , . . . , sd i. Then there exist unique elements
u1 , . . . , ud of P1 such that u−1 0 0
i si ∈ hwi for each i, and R = Q where Q = hu1 , . . . , ud i. By the choice of v,
0 0 0
we see that v 6∈ R . As R ≤ P1 , we have R ∩ hv, wi = 1.
Lemma 2.6. Assume the hypothesis and notation of Lemma 2.5. Then there exists a bijection between
the set of all d-generated subgroups of P/hvi and the set of all d-generated subgroups of P/hwi such that
corresponding subgroups are isomorphic.
Proof. Consider a d-generated subgroup Q of P/hvi. Then Q = Q∗ /hvi for a subgroup Q∗ of P that
contains v, and Q∗ = hQ0 , vi for some d-generated subgroup Q0 of P. Let Q∗∗ = hQ∗ , wi = hQ0 , v, wi.
Recall that v and w are in Z(P). So
(Q∗∗ )0 = (Q∗ )0 = (Q0 )0 . (4)
By Lemma 2.5 we infer (Q∗∗ )0 ∩ hv, wi = 1.
For a d-generated subgroup R of P/hwi, we obtain analogous subgroups R∗ , R0 , R∗∗ of P. Note that
Q and R uniquely determine Q∗∗ and R∗∗ .
Now consider the family of all subgroups S of P such that
(i) v and w are in S, and
(ii) S = hS0 , v, wi for some d-generated subgroup S0 of S.
The analysis above shows that to prove Lemma 2.6, it suffices to obtain, for each subgroup S as above, a
bijection between
• the set of all d-generated subgroups Q of P/hvi for which Q∗∗ = S and
• the set of all d-generated subgroups R of P/hwi for which R∗∗ = S
such that corresponding subgroups Q and R are isomorphic.
For each subgroup S, we have S0 ∩ hv, wi = S00 ∩ hv, wi = 1 by Lemma 2.5.
Since P has exponent p and S/S0 is abelian, there exists a complement S1 /S0 to hS0 , v, wi/S0 in S/S0 .
Since S0 , v, and w are central, we have S = S1 × hv, wi. Therefore, there exists a unique automorphism of
S that induces the identity on S1 and switches v and w. This establishes the desired bijection.
Proof of Theorem 1.3. The result is contained in Lemma 2.6. Let m = k + 2. Then
|P| = p1+m(m+1)/2 = p1+(k+2)(k+3)/2 .
The groups P/hvi and P/hwi have order |P|/p.
p
Proof of Theorem 1.1. The condition k ≤ 2 log n/ log p − (5/2) means
2
n ≥ p(k+(5/2)) /2 > p(k+2)(k+3)/2 = pN .
By Theorem 1.3, there exist nonisomorphic groups of order pN with identical k-profiles.
T HEORY OF C OMPUTING, Volume 11 (15), 2015, pp. 395–401 398
G ROUPS WITH I DENTICAL k-P ROFILES
Remark 2.7. We comment on the case k = 1. It is obvious that p-groups of exponent p of equal order
have the same 1-profile. In particular, for every odd prime p there exist nonisomorphic p-groups of order
p3 with the same 1-profile. Moreover, for all primes p there exists a nonabelian group of order p4 with a
cyclic subgroup of order p3 called M4 (p), which has the same 1-profile as the direct product of a cyclic
group of order p3 and the cyclic group of order p. (For the definition of M4 (p) see the classification
of p-groups with a cyclic subgroup of index p in [2, pp. 192–193].) In particular, M4 (2) has order 16,
improving Remark 1.2 for k = 1.
3 The isomorphism test
We describe the isomorphism test based on k-profiles suggested by Gowers [3].
Proposition 3.1. Let k, n be positive integers and suppose the groups of order n are determined, up to
isomorphism, by their k-profiles. Then isomorphism of two groups of order n, given by their Cayley tables,
can be decided in time n2k+O(1) .
Proof. Let G, H be two groups of order n. By our assumption, G and H are isomorphic if and only if
their k-profiles agree, so we only need to show how to compare the k-profiles of the two groups. This can
be done by computing the following equivalence relation on the disjoint union X := Gk ∪ ˙ H k . We say that
two k-tuples (x1 , . . . , xk ) ∈ X and (y1 , . . . , yk ) ∈ X are equivalent if the correspondence xi 7→ yi extends to
an isomorphism of the subgroups generated by these k-tuples. This can be checked in polynomial time
per instance, so n2k+O(1) total time. Now the k-profiles of G and H agree if and only if each equivalence
class is evenly divided between Gk and H k .
Remark 3.2. While our result shows that the comparison of k-profiles alone will not solve the Group
Isomorphism problem in polynomial time, it does not rule out a role for this algorithm in improving the
state of the art in this area. Indeed, Group Isomorphism is not currently known to be testable in time
no(log n) (cf. [4, 6, 5, 7]). Therefore, if our p
bound on k is not very far from being tight, say the result stated
in Remark 1.2 would fail if we replace 2 log3 n by O((log n)0.99 ), this would mean progress on the
complexity of the Group Isomorphism problem.
Acknowledgments
The first author wishes to thank Youming Qiao for bringing this problem to his attention and László Babai
for suggestions that strengthened the main results. The second author thanks Nikolai Nikolov for helpful
conversations and EPSRC for financial support.
References
[1] L ÁSZLÓ BABAI: Graph isomorphism in quasipolynomial time. Technical report, 2015.
[arXiv:1512.03547] 395
[2] DANIEL G ORENSTEIN: Finite Groups. AMS Chelsea Publ., 1980. 2nd ed. 399
T HEORY OF C OMPUTING, Volume 11 (15), 2015, pp. 395–401 399
G EORGE G LAUBERMAN AND Ł UKASZ G RABOWSKI
[3] T IM 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: Novem-
ber 12, 2011. http://rjlipton.wordpress.com/2011/11/07/the-group-isomorphism-problem-a-possible-
polymath-problem/. 395, 399
[4] E UGENE M. L UKS: Group isomorphism with fixed subnormal chains. Technical report, 2015.
[arXiv:1511.00151] 399
[5] DAVID ROSENBAUM: Bidirectional collision detection and faster algorithms for isomorphism
problems. Technical report, 2013. [arXiv:1304.3935] 399
[6] DAVID ROSENBAUM: Breaking the nlog n barrier for solvable-group isomorphism. In
Proc. 24th ACM–SIAM Symp. Discrete Algorithms (SODA’13), pp. 1054–1073, 2013.
[doi:10.1137/1.9781611973105.76, arXiv:1205.0642] 399
[7] DAVID ROSENBAUM AND FABIAN WAGNER: Breaking the generator-enumeration bound for
p-group isomorphism. Theoret. Comput. Sci., pp. 16–25, 2015. [doi:10.1016/j.tcs.2015.05.036,
arXiv:1312.1755] 399
AUTHORS
George Glauberman
Professor
University of Chicago
gg math uchicago edu
http://www.math.uchicago.edu/~gg/
Łukasz Grabowski
Research associate
University of Warwick
graboluk gmail com
http://homepages.warwick.ac.uk/~masmbh/
ABOUT THE AUTHORS
G EORGE G LAUBERMAN received his Ph. D. in 1965 from the University of Wisconsin–
Madison under the supervision of Richard H. Bruck, with additional help from Helmut
Wielandt and John Thompson. His work has been in the theory of finite groups, especially
their local analysis. He is also an avid baseball fan (the famed Jewish pitcher Sandy
Koufax is one of his heroes) and played catcher on the Math–Stat graduate student
softball team 1996–2010, wearing a replica of Jackie Robinson’s uniform. Since retiring
from softball because of an injury, his hobby has been to learn about fusion systems.
T HEORY OF C OMPUTING, Volume 11 (15), 2015, pp. 395–401 400
G ROUPS WITH I DENTICAL k-P ROFILES
Ł UKASZ G RABOWSKI graduated from the University of Göttingen in 2011 under the
supervision of Andreas Thom and Thomas Schick. He is currently a research associate
at the University of Warwick, working in combinatorics and group theory. His aim for
this year is to be a little bit like Stephen Curry.
T HEORY OF C OMPUTING, Volume 11 (15), 2015, pp. 395–401 401