<p><span class="math-container">$p$</span>-groups of class 2 and exponent <span class="math-container">$p$</span> are widely believed to be the hardest case of Group Isomorphism (<span class="math-container">$p &gt; 2$</span>). (For <span class="math-container">$p=2$</span>, we need to consider exponent 4, since all groups of exponent 2 are abelian - easy exercise for the reader.) Although there is as yet no reduction from general GpIso to this class of groups (though see point 0.5 below), there are several reasons for this belief. Let me outline some of them here.</p>

<p>0) Practical experience (see papers by Newman, Eick, O'Brien, Holt, Cannon, Wilson, ... which give the algorithms that are implemented in GAP and MAGMA).</p>

<p>0.5) [EDIT: added 8/7/19] Reductions. When such <span class="math-container">$p$</span>-groups are given by generating sets of matrices over <span class="math-container">$\mathbb{F}_p$</span>, the problem is <span class="math-container">$\mathsf{TI}$</span>-complete [<a href="https://arxiv.org/abs/1907.00309" rel="nofollow noreferrer">G.-Qiao '19</a>]. Also (cf. point (4) below), isomorphism of <span class="math-container">$p$</span>-groups of exponent <span class="math-container">$p$</span> and class <span class="math-container">$c &lt; p$</span> reduces in poly time to isomorphism of <span class="math-container">$p$</span>-groups of exponent <span class="math-container">$p$</span> and class 2 (ibid.).</p>

<p>1) Structure (reduce to solvable, then to <span class="math-container">$p$</span>-group). Every finite group contains a unique maximal solvable normal subgroup, called the solvable radical, denoted <span class="math-container">$Rad(G)$</span>. <span class="math-container">$G/Rad(G)$</span> contains no abelian normal subgroups, and isomorphism of such groups can be handled efficiently in practice (<a href="http://dx.doi.org/10.1016/S0747-7171(02)00133-5" rel="nofollow noreferrer">Cannon-Holt J. Symb. Comput. 2003</a>) and in theory (<a href="http://dx.doi.org/10.1007/978-3-642-31594-7_5" rel="nofollow noreferrer">Babai-Codenotti-Qiao ICALP 2012</a>). Even for groups where <span class="math-container">$Rad(G)$</span> is abelian, some of these can be handled in <span class="math-container">$n^{O(\log \log n)}$</span> time (<a href="https://doi.org/10.1137/15M1009767" rel="nofollow noreferrer">G-Qiao CCC '14, SICOMP '17</a>) - so, not quite polynomial, but much closer than <span class="math-container">$n^{\log n}$</span>. The main obstacle thus appears to be solvable (normal sub)groups. Now, within solvable groups, there is a lot of structure - starting with the fact that every solvable group is a <a href="https://en.wikipedia.org/wiki/Zappa%E2%80%93Sz%C3%A9p_product" rel="nofollow noreferrer">knit product</a> of its Sylow <span class="math-container">$p$</span>-subgroups - and it seems the hardest cases are <span class="math-container">$p$</span>-groups.</p>

<p>2) Counting. The number of groups of order <span class="math-container">$n$</span> is <span class="math-container">$\leq n^{(\frac{2}{27} + o(1))\mu(n)^2}$</span>, where <span class="math-container">$\mu(n)$</span> is the largest exponent of any prime dividing <span class="math-container">$n$</span> (<a href="https://doi.org/10.2307/2946623" rel="nofollow noreferrer">Pyber 1993</a>). The number of <span class="math-container">$p$</span>-groups of order <span class="math-container">$n=p^m$</span> is at least <span class="math-container">$p^{(\frac{2}{27} + o(1))m^2}$</span> (<a href="https://doi.org/10.1112/plms/s3-10.1.24" rel="nofollow noreferrer">Higman 1960</a>). So you see that the coefficient of the leading terms in the exponents match. In this sense "most" groups are <span class="math-container">$p$</span>-groups (even of class 2 and exponent <span class="math-container">$p$</span>). There is a long-standing conjecture which says that "most" in the preceding weak sense can be strengthened to say that proportion of groups of order <span class="math-container">$\leq n$</span> which are <span class="math-container">$p$</span>-groups tends to 1 as <span class="math-container">$n \to \infty$</span>.</p>

<p>3) Universality (/wildness). Giving a classification of <span class="math-container">$p$</span>-groups would imply a classification of all modular representations of any finite group (or even Artinian algebra) in characteristic <span class="math-container">$p$</span> (<a href="https://mathscinet.ams.org/mathscinet-getitem?mr=491938" rel="nofollow noreferrer">Sergeichuk 1977</a>). </p>

<p>4) Flexibility. Why <span class="math-container">$p$</span>-groups of class 2 and not higher class? (Note that <span class="math-container">$p$</span>-groups of nearly-maximal class, so-called "small coclass", have essentially been classified, <a href="https://doi.org/10.1112/blms/bdn007" rel="nofollow noreferrer">Eick &amp; Leedham-Green 2006</a>, see also some of the answers <a href="https://mathoverflow.net/q/207668/38434">here</a>.) To any <span class="math-container">$p$</span>-group one can associate a graded Lie ring, where bracket in the Lie ring corresponds to commutator in the group. Associativity in the group implies the Jacobi identity for the bracket, thus giving rise to a genuine Lie ring. However, note that when the group is class 2, the Jacobi identity is trivially satisfied (all its terms are automatically 0), so this puts no additional constraints on the structure. It basically just corresponds to an arbitrary skew-symmetric bilinear map. For <span class="math-container">$p$</span>-groups of exponent <span class="math-container">$p$</span>, <a href="https://arxiv.org/abs/1907.00309" rel="nofollow noreferrer">there is even a reduction</a> from class <span class="math-container">$c &lt; p$</span> to class 2.</p>

CC BY-SA 4.0
2019-05-13T09:19:59.760Z
Can you edit-in the definition of class 2? The Wikipedia page on $p$-groups only mentions nilpotency class, is that the same notion of class that you have in mind?
Vincent
CC BY-SA 4.0
2019-05-13T13:17:48.793Z
Yes, nilpotency class.
Joshua Grochow
CC BY-SA 4.0
2019-05-14T07:33:30.883Z
Thanks for the clarification!
Vincent
CC BY-SA 4.0
2019-03-19T20:00:37.043Z
2019-08-07T21:15:22.557Z
2019-08-07T21:15:22.557Z
Joshua Grochow
<p>Two groups <span class="math-container">$(G,\cdot)$</span> and <span class="math-container">$(H, \times)$</span> are said to be isomorphic iff there exists a homomorphism from <span class="math-container">$G$</span> to <span class="math-container">$H$</span> which is bijective. The group isomorphism problem is as follows: given two groups, check whether they are isomorphic or not. There are different ways to input a group, the two mostly used are by a Cayley table and by a generating set. Here I am assuming input groups are given by their Cayley table.  More formally:</p>

<p><span class="math-container">$\textbf{Group Isomorphism Problem}$</span></p>

<p><span class="math-container">$\textbf{Input : }$</span> Two groups <span class="math-container">$(G,\cdot)$</span> and <span class="math-container">$(H,\times)$</span>.</p>

<p><span class="math-container">$\textbf{Decide : } $</span> Is <span class="math-container">$G \cong H$</span>?</p>

<p>Let us assume that <span class="math-container">$n = |G| = |H|$</span></p>

<p>Group Isomorphism problem when input groups are given by Cayley table is not known to be in <span class="math-container">$\textbf{P}$</span> in general. Although there are group classes like the abelian group class for which the problem is known to be in polynomial time, groups which are the extension of an abelian group, simple groups etc. Even for nilpotent class two groups, no algorithm better than brute force is known.</p>

<p>A brute force algorithm for group isomorphism is given by Tarjan, which is as follows. Let <span class="math-container">$G$</span> and <span class="math-container">$H$</span> are two input groups, and let <span class="math-container">$S$</span> be a generating set of the group <span class="math-container">$G$</span>. It is a well-known fact that every finite group admits a generating set of <span class="math-container">$\mathcal{O}(\log n)$</span> size and which can be found in polynomial time. The number of images of the generating set <span class="math-container">$S$</span> in the homomorphism from <span class="math-container">$G$</span> to <span class="math-container">$H$</span> is <span class="math-container">$n^{\log n}$</span> many. Now, check whether each possible homomorphism is bijective or not. The overall runtime will be <span class="math-container">$n^{\log n + \mathcal{O}(1)}$</span>.</p>

<p>Let me first define the center of the group <span class="math-container">$G$</span>:</p>

<p><span class="math-container">$$Z(G) = \{g \in G \mid ag=ga, \forall a \in G\}$$</span></p>

<p><span class="math-container">$Z(G)$</span> denotes the elements of the group <span class="math-container">$G$</span> which commutes with all other elements of the group <span class="math-container">$G$</span>. Groups for which <span class="math-container">$G/Z(G)$</span> ( / used for quotient) is abelian are known as a nilpotent class two groups. To me it appears that nilpotent class two groups are the hardest instances to solve the group isomorphism problem. The meaning of "hardest instances" is: solving that case will allow researchers who work in group theory to solve the isomorphism problem of a large number of groups.</p>

<p>Initially, I thought that simple groups are the hardest instances as they are building blocks of all groups, but later came to know that the isomorphism problem for simple groups is in <span class="math-container">$\textbf{P}$</span>.</p>

<p><strong>Question</strong>:  What is the hardest instance for the group isomorphism problem?</p>

CC BY-SA 4.0
2019-03-19T15:03:44.073Z
Hi, could you consider expanding your question a bit to recap the definition of the group isomorphism problem (what is the input, what is the output) and/or a reference? Could you also consider recapping the definition of the center of a group? Last, could you clarify whether "allow as to solve" ("us"?) is a claim about the existence of a reduction?
Antoine Amarilli 'a3nm'
<ds.algorithms><gr.group-theory>
What is the hardest instance for the group isomorphism problem?
adc
# What is the hardest instance for the group isomorphism problem?

(Asked by: username_0 on 2019-03-18)

Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, check whether they are isomorphic or not. There are different ways to input a group, the two mostly used are by a Cayley table and by a generating set. Here I am assuming input groups are given by their Cayley table. More formally:

$\textbf{Group Isomorphism Problem}$

$\textbf{Input : }$ Two groups $(G,\cdot)$ and $(H,\times)$.

$\textbf{Decide : } $ Is $G \cong H$?

Let us assume that $n = |G| = |H|$

Group Isomorphism problem when input groups are given by Cayley table is not known to be in $\textbf{P}$ in general. Although there are group classes like the abelian group class for which the problem is known to be in polynomial time, groups which are the extension of an abelian group, simple groups etc. Even for nilpotent class two groups, no algorithm better than brute force is known.

A brute force algorithm for group isomorphism is given by Tarjan, which is as follows. Let $G$ and $H$ are two input groups, and let $S$ be a generating set of the group $G$. It is a well-known fact that every finite group admits a generating set of $\mathcal{O}(\log n)$ size and which can be found in polynomial time. The number of images of the generating set $S$ in the homomorphism from $G$ to $H$ is $n^{\log n}$ many. Now, check whether each possible homomorphism is bijective or not. The overall runtime will be $n^{\log n + \mathcal{O}(1)}$.

Let me first define the center of the group $G$:

$$Z(G) = \{g \in G \mid ag=ga, \forall a \in G\}$$

$Z(G)$ denotes the elements of the group $G$ which commutes with all other elements of the group $G$. Groups for which $G/Z(G)$ ( / used for quotient) is abelian are known as a nilpotent class two groups. To me it appears that nilpotent class two groups are the hardest instances to solve the group isomorphism problem. The meaning of "hardest instances" is: solving that case will allow researchers who work in group theory to solve the isomorphism problem of a large number of groups.

Initially, I thought that simple groups are the hardest instances as they are building blocks of all groups, but later came to know that the isomorphism problem for simple groups is in $\textbf{P}$.

**Question**: What is the hardest instance for the group isomorphism problem?

**Tags:** ds.algorithms, gr.group-theory
> **Comments:**
> **username_1**: Hi, could you consider expanding your question a bit to recap the definition of the group isomorphism problem (what is the input, what is the output) and/or a reference? Could you also consider recapping the definition of the center of a group? Last, could you clarify whether "allow as to solve" ("us"?) is a claim about the existence of a reduction?  

---

## 1 answers

### Answer by username_2 on 2019-03-19. Score: 15 | Accepted answer

$p$-groups of class 2 and exponent $p$ are widely believed to be the hardest case of Group Isomorphism ($p > 2$). (For $p=2$, we need to consider exponent 4, since all groups of exponent 2 are abelian - easy exercise for the reader.) Although there is as yet no reduction from general GpIso to this class of groups (though see point 0.5 below), there are several reasons for this belief. Let me outline some of them here.

0) Practical experience (see papers by Newman, Eick, O'Brien, Holt, Cannon, Wilson, ... which give the algorithms that are implemented in GAP and MAGMA).

0.5) [EDIT: added 8/7/19] Reductions. When such $p$-groups are given by generating sets of matrices over $\mathbb{F}\_p$, the problem is $\mathsf{TI}$-complete [[G.-Qiao '19](https://arxiv.org/abs/1907.00309)]. Also (cf. point (4) below), isomorphism of $p$-groups of exponent $p$ and class $c < p$ reduces in poly time to isomorphism of $p$-groups of exponent $p$ and class 2 (ibid.).

1) Structure (reduce to solvable, then to $p$-group). Every finite group contains a unique maximal solvable normal subgroup, called the solvable radical, denoted $Rad(G)$. $G/Rad(G)$ contains no abelian normal subgroups, and isomorphism of such groups can be handled efficiently in practice ([Cannon-Holt J. Symb. Comput. 2003](http://dx.doi.org/10.1016/S0747-7171(02)00133-5)) and in theory ([Babai-Codenotti-Qiao ICALP 2012](http://dx.doi.org/10.1007/978-3-642-31594-7_5)). Even for groups where $Rad(G)$ is abelian, some of these can be handled in $n^{O(\log \log n)}$ time ([G-Qiao CCC '14, SICOMP '17](https://doi.org/10.1137/15M1009767)) - so, not quite polynomial, but much closer than $n^{\log n}$. The main obstacle thus appears to be solvable (normal sub)groups. Now, within solvable groups, there is a lot of structure - starting with the fact that every solvable group is a [knit product](https://en.wikipedia.org/wiki/Zappa%E2%80%93Sz%C3%A9p_product) of its Sylow $p$-subgroups - and it seems the hardest cases are $p$-groups.

2) Counting. The number of groups of order $n$ is $\leq n^{(\frac{2}{27} + o(1))\mu(n)^2}$, where $\mu(n)$ is the largest exponent of any prime dividing $n$ ([Pyber 1993](https://doi.org/10.2307/2946623)). The number of $p$-groups of order $n=p^m$ is at least $p^{(\frac{2}{27} + o(1))m^2}$ ([Higman 1960](https://doi.org/10.1112/plms/s3-10.1.24)). So you see that the coefficient of the leading terms in the exponents match. In this sense "most" groups are $p$-groups (even of class 2 and exponent $p$). There is a long-standing conjecture which says that "most" in the preceding weak sense can be strengthened to say that proportion of groups of order $\leq n$ which are $p$-groups tends to 1 as $n \to \infty$.

3) Universality (/wildness). Giving a classification of $p$-groups would imply a classification of all modular representations of any finite group (or even Artinian algebra) in characteristic $p$ ([Sergeichuk 1977](https://mathscinet.ams.org/mathscinet-getitem?mr=491938)).

4) Flexibility. Why $p$-groups of class 2 and not higher class? (Note that $p$-groups of nearly-maximal class, so-called "small coclass", have essentially been classified, [Eick & Leedham-Green 2006](https://doi.org/10.1112/blms/bdn007), see also some of the answers [here](https://mathoverflow.net/q/207668/38434).) To any $p$-group one can associate a graded Lie ring, where bracket in the Lie ring corresponds to commutator in the group. Associativity in the group implies the Jacobi identity for the bracket, thus giving rise to a genuine Lie ring. However, note that when the group is class 2, the Jacobi identity is trivially satisfied (all its terms are automatically 0), so this puts no additional constraints on the structure. It basically just corresponds to an arbitrary skew-symmetric bilinear map. For $p$-groups of exponent $p$, [there is even a reduction](https://arxiv.org/abs/1907.00309) from class $c < p$ to class 2.

> **Comments:**
> **username_3**: Can you edit-in the definition of class 2? The Wikipedia page on $p$-groups only mentions nilpotency class, is that the same notion of class that you have in mind?  
> **username_2**: Yes, nilpotency class.  
> **username_3**: Thanks for the clarification!  

---

