Algorithms for Finite Group Epimorphism Testing

We consider groups with finitely many elements. The order of group $G$ is the number of elements in a group $G$, denoted by $|G|$. The order of an element $g\in G$, denoted as $\text{ord}(g)$, is the smallest positive integer $m$ such that $g^m=1$. The exponent of $G$ is the smallest positive integer $m$ such that $g^m=1$ for all $g\in G$. Let $H$ be a subgroup of $G$, if for all $a\in G$, $a^{-1}Ha=H$ then we say that $H$ is a normal subgroup of $G$ (denoted by $H⊲G$). A normal Hall subgroup $N$ is a normal subgroup of $G$ with $\gcd (|N|,|G/N|)=1$. For any subgroup $H$ and any normal subgroup $K$ of $G$ we denote the subgroup $\{hk|h\in H,k\in K\}=\{kh|h\in H,k\in K\}$ by $HK$.

Let $N$ be a normal subgroup of $G$. We say that $G$ is semidirect product of $N$ by a subgroup $H$ of $G$, denoted as $G=N⋊H$ if $G=NH$ and $N\cap H=1$. Since $N⊲G$, this gives rise to a homomorphism $\tau :H\to \mathrm{Aut}(N)$ by $h\to {\chi }_h$, where ${\chi }_h:N\to N$ by $n\to h^{-1}nh$. In this case, we write $G=N{⋊}_{\tau }H$. We say $N$ is a normal subgroup of this decomposition and $H$ the complement of $N$ in $G$. Conversely, given two groups $N$ and $H$ and a homomorphism $\tau :H\to \mathrm{Aut}(N)$, we can define a group $G:=\{(n,h)\mid n\in N,h\in H\}$ with the product operation, $(n_1,h_1)(n_2,h_2)=(n_1{\chi }_{h_1}(n_2),h_1{h}_2)$, for all $(n_1,h_1),(n_2,h_2)\in G$. This gives a construction of the outer semidirect product $G=N{⋊}_{\tau }H$. For a normal Hall subgroup $N$ of $G$, the Schur–Zassenhaus theorem guarentees that a complement subgroup $H\le G$ such that $\gcd (|H|,|N|)=1$ and $G=N{⋊}_{\tau }H$ exists. Furthermore, if $H$ and $K$ are complements of $N$, then $H$ and $K$ are conjugate (see, e.g., [37]).

A minimal normal subgroup of $G$ is a normal subgroup $N⊴G$ with no nontrivial subgroups that are also normal in $G$; equivalently, if $M⊴G$ and $M\le N$, then $M\in \{1,N\}$. A standard exercise is that every minimal normal subgroup of a finite group is a direct power $T^n$ of some finite simple group $T$. The socle of a group $G$, denoted $\mathrm{Soc}(G)$ is the (characteristic) subgroup generated by all minimal normal subgroups of $G$. The socle series of $G$ is defined by ${\mathrm{Soc}}^1(G):=\mathrm{Soc}(G)$ and ${\mathrm{Soc}}^i(G)$ is the unique subgroup of $G$ such that ${\mathrm{Soc}}^i(G)/{\mathrm{Soc}}^{i-1}(G)=\mathrm{Soc}(G/{\mathrm{Soc}}^{i-1}(G))$.

A normal series in $G$ is a series $1=N_0\le N_1\le N_2\le \mathrm{\cdots }\le N_k=G$ such that $N_i⊴G$ for all $i$. A chief series is a normal series that cannot be further refined (a so-called “maximal” normal series). Equivalently, a chief series is a normal series such that $N_i/N_{i-1}$ is a minimal normal subgroup of $G/N_{i-1}$ for all $i$. If $N_{\ast }$ is a chief series, then the factor groups $N_i/N_{i-1}$ are called chief factors of $G$. Each chief factor is of the form $T^n$ for some simple group $T$ and some integer $n$, and the multiset of isomorphism types of chief factors is well-defined for $G$, independent of the chief series (see e.g., [24, Theorem 8.4.4]).

The socle series can be refined to a chief series by taking the minimal normal subgroups $M_1,\mathrm{\dots },M_k$ of $G/{\mathrm{Soc}}^i(G)$, taking their pre-images ${\widehat{M}}_1,\mathrm{\dots },{\widehat{M}}_k$ in $G$, and then inserting them in between ${\mathrm{Soc}}^i(G)$ and ${\mathrm{Soc}}^{i+1}(G)$ in any order, viz. ${\mathrm{Soc}}^i(G)⊴{\mathrm{Soc}}^i(G)M_1⊴{\mathrm{Soc}}^i(G)M_1{M}_2⊴\mathrm{\cdots }⊴{\mathrm{Soc}}^i(G)M_1{M}_2\mathrm{\cdots }{M}_{k-1}⊴{\mathrm{Soc}}^{i+1}(G)$. We say $G$ has socle length $\mathrm{\ell }$ if $\mathrm{\ell }$ is the least integer such that $G={\mathrm{Soc}}^{\mathrm{\ell }}(G)$.

Let $𝔽$ be a field. A $d$-dimensional linear subspace $C\subseteq {𝔽}^n$ is called a linear code of dimension $d$. A generating matrix of a linear code $C$, of dimension $d$, is a $d\times n$ matrix with row vectors being a basis of $C$. We will also use $C$ to denote the generating matrix of a linear code $C$.

Let $V$ be a vector space of dimension $d$ over $𝔽$. A representation of a group $G$ is a homomorphism $\tau :G\to \mathrm{GL}(d,𝔽)$. A subspace $W$ of $V$ is called $G$-invariant if for all $g\in G$ and $w\in W$, we have ${\tau }_g(w)\in W$. A representation $\tau :G\to \mathrm{GL}(d,𝔽)$ is called irreducible if the only $G$-invariant subspaces of $V$ are $0$ and $V$.

Let $V$ and $W$ be two finite-dimensional vector spaces over a field $𝔽$ of dimension $d$ and $d^{\prime }$, respectively. We say that two representations $\tau :G\to \mathrm{GL}(d,𝔽)$ and $\gamma :G\to \mathrm{GL}(d^{\prime },𝔽)$ are equivalent if there is an invertible linear map $f:V\to W$ such that $f\circ {\tau }_g={\gamma }_g\circ f$ for all $g\in G$.

Let $N$ be an elementary abelian $p$-group and let $G=N{⋊}_{\tau }H$ be a group, where $\tau :H\to \mathrm{Aut}(N)$ is an action of $H$ on $N$. Since $N$ is an elementary abelian $p$-group, $N\cong {\mathbb{Z}}_p^d$, and $\mathrm{Aut}(N)=\mathrm{GL}(d,{𝔽}_p)$. Then the homomorphism $\tau$ can be seen as a representation of $H$ given by $\tau :H\to \mathrm{Aut}(N)=\mathrm{GL}(d,{𝔽}_p)$.

We say that matrix $A_{d\times n}$ of rank $d$ is in standard form if $A=[I_d|A^{\prime }]$, i.e., the first $d$ columns of $A$ form the identity matrix. We can perform row operations on $A$ followed by a permutation of the columns to transform $A$ to a standard form, i.e., we can find $B$ and $B^{\prime }$ such that $BA{B}^{\prime }$ is in standard form.

Let $R$ be a ring and $M,N$ be $R$-modules. A map $\varphi :M\to N$ is an $R$-module homomorphism if $\varphi (\alpha x+y)=\alpha \varphi (x)+\varphi (y)$ for all $x,y\in M$ and $\alpha \in R$. A module $M$ is indecomposable if $M=M_1\oplus M_2$ implies $M_1=0$ or $M_2=0$.

Let $G$ be a group. A (left) $G$-module is an abelian group $A$ on which $G$ acts by additive maps on the left, i.e., a left $G$-module consists of an abelian group $A$ together with a left group action $\tau :G\times A\to A$ such that $g\cdot (a_1+a_2)=g\cdot a_1+g\cdot a_2$, for all $a_1,a_2\in A$ and $g\in G$. Similarly, we can define right $G$-module. Unless explicitly mentioned otherwise the term “$G$-module” will always mean “left $G$-module”. We refer reader to [45, 13] for more details on group modules.

$(⟹)$ Let $f:G_1\to G_2$ be an epimorphism from $G_1$ to $G_2$ such that $G_1/\ker f\cong G_2$. Let $L=\ker f\cap N_1$ and $K=\ker f\cap H_1$. It is easy to see that $\ker f=L{⋊}_{\tau }K$.

We now show that the action of $K$ on $N_1/L$, given by ${(nL)}^k=kn{k}^{-1}L$ for $k\in K$, $n\in N_1$, is trivial. Since $f(k)=1$ we have $f(kn{k}^{-1})=f(n)$, which implies that $n^{-1}kn{k}^{-1}\in \ker f$. Clearly $n^{-1}kn{k}^{-1}\in N_1$, therefore $n^{-1}kn{k}^{-1}\in L$ and $kn{k}^{-1}L=nL$. Define an action ${\tau }^{\prime }$ of $H_1/K$ on $N_1/L$ given by ${\tau }^{\prime }(hK):=\tau (h)L$. Since $K$ acts on $N_1/L$ trivially, ${\tau }^{\prime }$ is well-defined. Indeed, if $hK=h^{\prime }K$, then $h^{\prime }=hk$ for some $k\in K$. ${\tau }^{\prime }(h^{\prime }K)(nL)=\tau (h^{\prime })(n)L=\tau (hk)(n)L=(\tau (h)\tau (k))(n)L=\tau (h)(\tau (k)(n)L)=\tau (h)(n)L={\tau }^{\prime }(hK)(nL)$.

Consider a map $\pi :\frac{N_1{⋊}_{\tau }{H}_1}{L{⋊}_{\tau }K}\to \frac{N_1}{L}{⋊}_{{\tau }^{\prime }}\frac{H_1}{K}$ defined by $\pi (n_1,h_1)=(n_{1}L,h_{1}K)$. It is easy to see that $\pi$ is an isomorphism. Moreover, $\frac{N_1}{L}{⋊}_{{\tau }^{\prime }}\frac{H_1}{K}\cong N_2{⋊}_{\gamma }{H}_2$, with $|N_1/L|=N_2$ and $|H_1/K|=H_2$. By [41, Theorem 3.3], there exist an isomorphism $\overline{\rho }:N_1/L\to N_2$ and an isomorphism $\overline{\varphi }:H_1/K\to H_2$ such that, $\forall hK\in H_1/K$, $\overline{\rho }\circ {\tau }^{\prime }(hK)=\gamma (\overline{\varphi }(hK))\circ \overline{\rho }$. By lifting $\overline{\varphi },\overline{\rho },{\tau }^{\prime }$ to $\varphi ,\rho$ and $\tau$ respectively, via the canonical epimorphism we obtain $\rho \circ \tau (h)=\gamma (\varphi (h))\circ \rho$.

$(⟸)$ Consider a map $f:G_1\to G_2$ defined by $f(n,h)=(\rho (n),\varphi (h))$. It is clear that $f$ is an epimorphism from $G_1$ to $G_2$. Now, consider

Hence, $f$ is an epimorphism from $G_1$ to $G_2$. $◀$

For each $v\in N$, we compute the $H$-submodule ${⟨v⟩}_H$ of $N$. For each such submodule, we then use the algorithm of Ciocǎnea-Teodorescu [12, Theorem 1.1] to test whether ${⟨v⟩}_H$ appears as a direct summand in a direct sum decomposition of $N$ as an $H$-module, and if so, to find a complement, that is, another $H$-submodule $U\le N$ such that $N={⟨v⟩}_H\oplus U$. As soon as one such direct sum decomposition is found, the algorithm is then called recursively on ${⟨v⟩}_H$ and $U$ to see if they can be further decomposed. Furthermore, if $N$ is decomposable, then there must exist a $v\in N$ such that ${⟨v⟩}_H$ is a direct summand, for $N$ must contain an indecomposable direct summand by induction on its size, and for a prime $p$ dividing $|N|$, by Lemma 9, in this setting, indecomposable $H$-modules are generated by a single element. If no such direct sum decomposition is found, then $N$ is an indecomposable $H$-module, and the recursion stops. $◀$

In practice, some pre-processing can be done beforehand; for example, at the start, $N$ can be split into a direct sum of its Sylow $p$-subgroups for different primes $p$. And within each Sylow $p$-subgroup, if ${⟨v⟩}_H=p{⟨u⟩}_H$ for some $u\in N$, then ${⟨v⟩}_H$ is not a direct summand of $N$ and can be excluded from the above search.

We are now ready to prove Theorem 1.

First we check that $G_2$ is in $\mathrm{Coprime}(\mathrm{Ab},\mathrm{Cyc})$ (otherwise reject). In order to test whether there is an epimorphism between $G_1$ and $G_2$, we first run the algorithm from [34, Theorem 1] on the inputs $G_1$ and $G_2$ to obtain all normal Hall subgroups and their complements. We then select an arbitrary normal Hall subgroup $N_1$ of $G_1$ (respectively, $N_2$ of $G_2$) and its complement $H_1$ (respectively, $H_2$) such that $|N_1|\ge |N_2|$, $|H_1|\ge |H_2|$, $N_1$ and $N_2$ are Abelian, and $H_1$ and $H_2$ are cyclic. All these conditions can be verified in polynomial time for each normal Hall subgroup and all of its complements. If no such pair of normal Hall subgroup and its complement exists, then by Theorem 7, we conclude that there is no epimorphism from $G_1$ to $G_2$. Otherwise, we proceed as follows.

Since every finite cyclic group has a unique subgroup of any given order dividing its order, there exists a unique subgroup $K⊲H_1$ such that $|H_1/K|=|H_2|$. If no such $K$ exists, then the algorithm will reject. Moreover, $K$ can be computed in polynomial time. Let $\tau$ (respectively, $\gamma$) be a conjugation action of $H_1$ on $N_1$ (respectively, $H_2$ on $N_2$). We compute the normal subgroup $L=⟨\{v^{\tau (k)}-v|v\in N_1,k\in K\}⟩⊲N_1$, and determine its order in polynomial time.

If $|N_1/L|=|N_2|$ then there is an epimorphism from $G_1$ to $G_2$ if and only if the groups $N_1/L{⋊}_{\tau }{H}_1/K$ and $N_2{⋊}_{\gamma }{H}_2$ are isomorphic³³3The quotient $H_1/K$ naturally inherits the action $\tau$ since $K$ acts trivially on $N_1/L$ (see, e.g., proof of Theorem 7) (see the proof of Theorem 7). There exists a polynomial-time algorithm to test whether these two groups are isomorphic and, if so, to compute an explicit isomorphism between them by Le Gall [30, Theorem 1.2]. If such an isomorphism exists, we can lift it to an epimorphism from $G_1$ to $G_2$ by composing the canonical epimorphism, $G_1\to N_1/L{⋊}_{\tau }{H}_1/K$, with the computed isomorphism from $N_1/L{⋊}_{\tau }{H}_1/K$ to $G_2$.

Otherwise, we may assume $|N_1/L|>|N_2|$ (for if $|N_2|>|N_1/L|$ then the algorithm can simply return that there is no epimorphism). Since $L⊲N_1$ and $N_1$ is an $H_1$-module, it follows that $L$ and $N_1/L$ both are an $H_1$-module. Let $⨁V_i$ and $⨁U_j$ denote the decomposition of $N_1/L$ and $N_2$ into their indecomposable $H_1$-submodules and $H_2$-submodules, respectively. These decompositions can be computed in polynomial time by Lemma 10. Note that the underlying group of each $V_i$ is ${(\mathbb{Z}/p_i^{k_i}\mathbb{Z})}^{d_i}$, for some $p_i$, and the exponent of $V_i$ divides $p_i^{k_i}$ (see, e.g., [42, 19]). Moreover, the underlying group of the quotient $V_i/p_i{V}_i$ is an elementary Abelian group ${(\mathbb{Z}/p_i\mathbb{Z})}^{d_i}$ [42].

Let $\overline{\varphi }:H_1/K\to H_2$ be an isomorphism. All such isomorphisms can be computed in polynomial time, as both $H_1/K$ and $H_2$ are cyclic groups. Fix such an isomorphism $\overline{\varphi }$. For each $i$, the module $V_i$ inherits an $H_2$-module structure via $\overline{\varphi }$, since $K$ acts trivially on $V_i$.

We now construct a bipartite graph ${\mathrm{\Gamma }}_{\overline{\varphi }}$ as follows. The vertex set of ${\mathrm{\Gamma }}_{\overline{\varphi }}$ is the disjoint union of two sets, one containing a vertex labeled $i$ for each $V_i$, and the other containing a vertex labeled $j$ for each $U_j$. There is an edge $(i,j)$ between vertices $i$ and $j$ if and only if there exists $l_{ij}\le k_i$ such that there is an $H_2$-module isomorphism from $V_i/p_i^{l_{ij}}{V}_i$ to $U_j$.

Let ${\rho }_{ij}:V_i/p_i^{l_{ij}}{V}_i\to U_j$ be an $H_2$-module isomorphism. Note that ${(\mathbb{Z}/p_i^{k_i}\mathbb{Z})}^{d_i}$ and ${(\mathbb{Z}/p_i^{k_i^{\prime }}\mathbb{Z})}^{d_j}$ are the underlying groups of $V_i$ and $U_j$, respectively. Additionally, we have ${(\mathbb{Z}/p_i^{l_{ij}}\mathbb{Z})}^{d_i}\cong {(\mathbb{Z}/p_i^{k_i}\mathbb{Z})}^{d_i}/p_i^{l_{ij}}{(\mathbb{Z}/p_i^{k_i}\mathbb{Z})}^{d_i}=V_i/p_i^{l_{ij}}{V}_i\cong U_j={(\mathbb{Z}/p_i^{k_i^{\prime }}\mathbb{Z})}^{d_j}$ implies that $d_i=d_j$ and $k_i^{\prime }=l_{ij}$. Define $f_{ij}:V_i/p_i{V}_i\to U_j/p_i{U}_j$ by $f_{ij}(\text{v}+p_i{V}_i)={\rho }_{ij}(\text{v}mod{p}_i^{l_{ij}}{V}_i)+p_i{U}_j$, where $\text{v}=(v_1,\mathrm{\dots },v_{d_i})\in V_i$ and $V_i/p_i{V}_i\cong {(\mathbb{Z}/p_i\mathbb{Z})}^{d_i}$. It is easy to see that $f_{ij}$ is an epimorphism. Moreover, $f_{ij}({𝐯}^h+p_i{V}_i)={\rho }_{ij}({𝐯}^{h}mod{p}_i^{l_{ij}}{V}_i)+p_i{U}_j={\rho }_{ij}{(\text{v}mod{p}_i^{l_{ij}}{V}_i)}^h+p_i{U}_j=f_{ij}{(𝐯+p_i{V}_i)}^h$, where $h\in H_2$. Therefore, by Schur’s lemma [39, Proposition 4] we have $f_{ij}$ is an $H_2$-module isomorphism.

Next, we have for each $v\in V_i/p_i^{l_{ij}}{V}_i$, there is $v^{\prime }\in V_i$ such that $\text{ord}(v^{\prime })=\text{ord}(v)m_v$ for some positive integer $m_v$. This implies $\text{exponent}(U_j)=\text{exponent}(V_i/p_i^{l_{ij}}{V}_i)=\mathrm{lcm}(\text{ord}(v)|v\in V_i/p_i^{l_{ij}}{V}_i)=\mathrm{lcm}(\text{ord}(v^{\prime })/m_v|v^{\prime }\in V_i)\le \mathrm{lcm}(\text{ord}(v^{\prime })|v^{\prime }\in V_i)=\text{exponent}(V_i)$.

Conversely, let $f_{ij}:V_i/p_i{V}_i\to U_j/p_i{U}_j$ be an $H_2$-module isomorphism and let $\text{exponent}(U_j)\le \text{exponent}(V_i)$. Let ${(\mathbb{Z}/p_i^{k_i}\mathbb{Z})}^{d_i}$ and ${(\mathbb{Z}/p_i^{k_i^{\prime }}\mathbb{Z})}^{d_j}$ be the underlying groups of $V_i$ and $U_j$, respectively. Since $f_{ij}$ is an isomorphism, we have $d_i=d_j$. Take $l_{ij}=k_i^{\prime }\le k_i$. By [42, Theorem 1.1], if modules $V_i/p_i^{l_{ij}}{V}_i$ and $U_j$ are not isomorphic then so the modules $(V_i/p_i^{l_{ij}}{V}_i)/(p_i{V}_i/p_i^{l_{ij}}{V}_i)$ and $U_j/p_i{U}_j$. This completes the proof of the claim. $\mathrm{⊲}$

First, we see that the graph ${\mathrm{\Gamma }}_{\overline{\varphi }}$ and the isomorphism ${\rho }_{ij}$ can be constructed in deterministic polynomial time. By Claim 11, to test whether there is an $H_2$-module isomorphism from $V_i/p_i^{l_{ij}}{V}_i$ to $U_j$ it is enough to test whether there is an $H_2$-modules isomorphism from $V_i/p_i{V}_i$ to $U_j/p_i{U}_j$, and that $\text{exponent}(U_j)\le \text{exponent}(V_i)$. Since the Cayley tables of the underlying groups of $V_j$ and $U_j$ can be constructed, we can compute $\text{exponent}(U_j)$ and $\text{exponent}(V_i)$ in polynomial time.

Both $V_i/p_i{V}_i$ and $U_j/p_i{U}_j$ are elementary Abelian $p_i$-groups. Let $M_{V_i},M_{U_j}\in \mathrm{GL}({𝔽}_{p_i},d_i)$ be the matrices induced by an action of $H_2$ on $V_i/p_i{V}_i$ and $U_j/p_i{U}_j$ respectively. Testing whether there is an $H_2$-modules isomorphism between these modules is equivalent to testing whether $M_{V_i}$ and $M_{U_j}$ are conjugate in $\mathrm{GL}({𝔽}_{p_i},d_i)$. Since $\mathrm{GL}({𝔽}_p,n)$ is an ${𝔽}_p$-algebra, this conjugacy problem can be solved in deterministic polynomial time as described in [11, Theorem 2]. Moreover, this algorithm also compute a matrix $T$ such that $T^{-1}{M}_{V_i}T=M_{U_j}$, if such a $T$ exists. Then $f_{ij}$ is the corresponding linear map. Moreover, we can compute a module isomorphism ${\rho }_{ij}$ by [12, Corollary 1.2]. Therefore, the graph ${\mathrm{\Gamma }}_{\overline{\varphi }}$ and the isomorphism ${\rho }_{ij}$ can be constructed in deterministic polynomial time.

Next, we compute a maximum matching in ${\mathrm{\Gamma }}_{\overline{\varphi }}$, which can be done in polynomial time. If the matching saturates all the vertices corresponding to the $U_j$’s, i.e., if its size equals the number of indecomposable $H_2$-modules of $N_2$, then the matching defines the epimorphism from $N_1/L$ to $N_2$, say $\overline{\rho }$ (otherwise, we conclude that no epimorphism from $N_1/L$ to $N_2$ exists and hence there is also no epimorphism from $G_1$ to $G_2$). Moreover, since we have computed the homomorphism ${\rho }_{ij}$ corresponding to the matched edges, we can explicitly construct $\overline{\rho }$ in polynomial time. Note that $(\overline{\rho },\overline{\varphi })$ gives an isomorphism from $N_1/L{⋊}_{\tau }{H}_1/K$ to $G_2$ since $\overline{\rho }$ and $\overline{\varphi }$ satisfies Equation 1 by construction. Next, we lift this isomorphism to an epimorphism from $G_1$ to $G_2$ by composing the canonical epimorphism $G_1\to N_1/L{⋊}_{\tau }{H}_1/K$ with the computed isomorphism. $◀$