Parallel Algorithms for Group Isomorphism via Code Equivalence

We will first recall the following notation [46]. Let $\mathscr{H}(𝒜,ℰ)$ be the class of coprime extensions $H⋉N$, where $N$ is Abelian and $H$ is elementary Abelian.

There has been considerable work on polynomial-time isomorphism tests for coprime [36, 46, 8, 28, 14] and tame extensions [29]. In [46], polynomial-time isomorphism tests were given for coprime extensions $H⋉N$ where (i) $H$ was $O(1)$-generated and $N$ was Abelian, and (ii) $\mathscr{H}(𝒜,ℰ)$. The parallel complexity for isomorphism testing of coprime extensions was first investigated by Grochow and Levet [28], who showed that some constant-dimensional Weisfeiler–Leman (WL) algorithm identifies, in $O(1)$-rounds, all coprime extensions $H⋉N$, where $N$ is Abelian and $H$ is $O(1)$-generated. Consequently, they obtained that the isomorphism problem for this family belongs to L. In his thesis, Brachter [14] showed that the more general class of groups with Abelian Sylow towers has WL-dimension $O(\log \log n)$. Consequently, Brachter’s work yields $n^{O(\log \log n)}$-time bounds for isomorphism testing of this class. It remains open whether even the class $\mathscr{H}(𝒜,ℰ)$ has bounded Weisfeiler–Leman dimension. Prior to this paper, it was open whether isomorphism testing of groups in $\mathscr{H}(𝒜,ℰ)$ was in NC.

The polynomial-time isomorphism test for $\mathscr{H}(𝒜,ℰ)$ [46] crucially leveraged small (size $O(\log |G|)$) instances of Linear Code Equivalence (CodeEq). Thus, in order to obtain our parallel bounds, we will establish the following.

In establishing the bound of ${(2+o(1))}^m$-time for CodeEq, Babai reduces to isomorphism testing of graphs with $O(m)$ vertices [6]. When $m\in O(\log n)$, applying Babai’s quasipolynomial GI procedure [4] would only yield bounds of $m^{O({\log }^{2}m)}={(\log n)}^{O({(\log \log n)}^2)}$ runtime, which is not sufficient to obtain bounds of NC. Instead, we utilize Luks’ group-theoretic method [40] to handle these small graphs. While Luks’ claims of polynomial-time isomorphism testing are for graphs of bounded valence, the graphs we will consider need not satisfy this condition. However, our graphs are small, having only $O(\log n)$ many vertices. Thus, we bring to bear a standard suite of NC algorithms for permutation groups [3, 43]. As the group $G$ is specified by its multiplication table and our graphs have $O(\log n)=O(\log |G|)$ many vertices, we can implement solutions for each subroutine of [3, 43] using an AC circuit of depth $\mathrm{poly}(\log \log n)$ and size $\mathrm{poly}(n)$. Grochow, Johnson, and Levet [26] introduced the notation ${\text{FOLL}}^{O(1)}$ to refer to the class of languages decidable by uniform AC circuits of depth $\mathrm{poly}(\log \log n)$ and size $\mathrm{poly}(n)$. We combine this suite of ${\text{FOLL}}^{O(1)}$permutation group algorithms, as well as the ${\text{FOLL}}^{O(1)}$procedure for small instances of Coset Intersection (CosetInt) from [26].

We now turn to our second main result. Recall that the solvable radical is the unique maximal solvable normal subgroup of $G$. We will denote the solvable radical of $G$ as $\text{Rad}(G)$. Here, we will consider central-radical groups, which are precisely those groups where the solvable radical $\text{Rad}(G)=Z(G)$.

This improves upon the previous polynomial-time bounds due to Grochow and Qiao [30].

Key motivation for isomorphism testing of central-radical groups comes from the following series of characteristic subgroups, known as the Babai–Beals filtration [5]: $1\le \text{Rad}(G)\le {\text{Soc}}^{\ast }(G)\le \text{PKer}(G)\le G.$ We will now explain the terms on this chain. Let $\pi :G\to G/\text{Rad}(G)$ be the natural projection map. ${\text{Soc}}^{\ast }(G)$ is the preimage of the socle¹¹1The socle of a group $H$ is the direct product of the minimal normal subgroups of $H$. $\text{Soc}(G/\text{Rad}(G))$, under $\pi$. The group ${\text{Soc}}^{\ast }(G)/\text{Rad}(G)=\text{Soc}(G/\text{Rad}(G))$ is the direct product of non-Abelian simple groups $T_1,\mathrm{\dots },T_k$. The conjugation action of $G$ on $\text{Soc}(G/\text{Rad}(G))$ induces a permutation action $\phi$ on $T_1,\mathrm{\dots },T_k$. Now $\text{PKer}(G):=\text{Ker}(\phi )$. Note that Thm. 3(a) considers precisely those groups where $\text{Rad}(G)=Z(G)$ is elementary Abelian, and $G={\text{Soc}}^{\ast }(G)$. While these assumptions might feel restrictive, Grochow and Qiao essentially leveraged the full weight of [30] in order to obtain a polynomial-time isomorphism test, combining deep mathematical insights (group cohomology) with demanding algorithmic techniques (see under Methods, below).

The class of Fitting-free groups consists precisely of those groups $G$ where $\text{Rad}(G)$ is trivial. There has been considerable work on isomorphism testing of Fitting-free groups. In the Cayley table model, it took a series of two papers [6, 7] to obtain a polynomial-time isomorphism test, and this bound was only recently improved this bound from P to ${\text{AC}}^3$ [26]. Fitting-free groups have also received significant attention, from the perspective of the Weisfeiler–Leman algorithm [15, 14, 28, 27, 26].

In light of the efficient isomorphism tests for Fitting-free groups [6, 7, 26], the next step is to consider groups where $\text{Rad}(G)$ is non-trivial. In [6], the authors posed the problem of handling isomorphism for central-radical groups. Grochow and Qiao [30] exhibited an $n^{O(\log \log n)}$-time algorithm to decide isomorphism of arbitrary central-radical groups, as well as groups where $\text{Rad}(G)$ was elementary Abelian (not necessarily central). For additional complexity-theoretic work on isomorphism testing for groups where $\text{Rad}(G)$ is non-trivial, see [29, 16, 37, 14].

We will now outline the key ideas and techniques involved in proving Thm. 3. As a conceptual starting point, let us first consider the setting of direct products. The Remak–Krull–Schmidt theorem provides that two direct products $G=G_1\times \mathrm{\cdots }\times G_k$ and $H=H_1\times \mathrm{\cdots }\times H_{\mathrm{\ell }}$ are isomorpic if and only if $k=\mathrm{\ell }$, and for some permutation $\sigma \in \text{Sym}(k)$, $G_i\cong H_{\sigma (i)}$ for all $i\in [k]$. Grochow and Qiao established that for the groups in Thm. 3, an analogous result holds [30, Lem. 7.4] (recalled as Lem. 27).

Let $G_1,G_2$ be two groups under consideration in Thm. 3. For $i=1,2$, write $G_i/\text{Rad}(G_i)={\prod }_{j=1}^k{T}_{i,j}$. Let ${\pi }_i:G_i\to G_i/\text{Rad}(G_i)$ be the natural projection map. Rather than considering the isomorphism type of the $T_{i,j}$, we will need to consider the isomorphism type of each ${\pi }_i^{-1}(T_{i,j})$. It is then necessary to determine whether there exists a permutation $\sigma \in \text{Sym}(k)$ such that ${\pi }_1^{-1}(T_{1,j})$ and ${\pi }_2^{-1}(T_{2,\sigma (j)})$ are isomorphic. However, there is an additional complication, in that we require a single isomorphism $\alpha :Z(G_1)\cong Z(G_2)$, such that for all $j\in [k]$, $\alpha$ can be extended to an isomorphism of ${\pi }_1^{-1}(T_{1,j})$ and ${\pi }_2^{-1}(T_{2,\sigma (j)})$. Grochow and Qiao handled this step using small (size $O(\log |G|)$) instances of CodeEq and CosetInt. In these places, we will use our parallel implementation for CodeEq (Thm. 2), as well as the ${\text{FOLL}}^{O(1)}$procedure for small instances of CosetInt from [26].

Still, we will need an additional ingredient. In order to determine the isomorphism types of the ${\pi }_i^{-1}(T_{i,j})$ ($i=1,2$; $j\in [k]$), Grochow and Qiao utilized [30, Thm. 6.1]. Note that [30, Thm. 6.1] is quite powerful. Grochow and Qiao obtained one of their main results [30, Thm. A/Cor. 6.2] as a corollary: a bound of $n^{O(\log \log n)}$-time for isomorphism testing of central-radical groups, as well as the same bound for computing the coset of isomorphisms when $\text{Rad}(G_i)=Z(G_i)$ was elementary Abelian. We will parallelize [30, Thm. 6.1]; for readability, we refer to Thm. 22, rather than stating the exact theorem here. As a byproduct, we obtain the following complexity-theoretic improvement in isomorphism testing of arbitrary central-radical groups.

We proceed for $m-1\in O(\log n)$ times iterations. At each iteration, we compute generators for the corresponding kernel ($ℛ$) and use Prop. 14 to compute generators for the corresponding image ($𝒮$). The result now follows. $◀$

The remainder of this section will be devoted to the proof of Prop. 14. Let $\mathrm{\Delta }(X)$ be the maximum degree of $X$. Let $A\subseteq 2^{V(X_r)}\setminus \{\mathrm{\varnothing }\}$ contain those subsets of size at most $\mathrm{\Delta }$. Define $f:V(X_{r+1})\setminus V(X_r)\to A$ by: $f(v):=\{w\in V(X_r):vw\in E(X)\}.$ Luks [40] previously established that $\sigma \in {\text{Aut}}_e(X_r)$ is in $\text{Im}({\pi }_r)$ if and only if, for each $0\le s\le m-1$, $\sigma$ stabilizes the set of fathers of $s$-tuples: $A_s:=\{a\in A:|f^{-1}(a)|=s\},$ as well as the set $A^{\prime }$ of new edges. Color $A$ accordingly with $2m$ colors (see e.g., [40, p. 49]). We need to now find the automorphisms in $G={\text{Aut}}_e(X_r)$ acting on $A$, that preserve the edge colors. We now recall some notions from Luks [40]. Let $A$ be a colored set, with coloring $\chi$. Let $B\subseteq A$ and $K\le \text{Sym}(A)$. The set of permutations in $K$ that preserve the colors in $B$ is: ${𝒞}_B(K):=\{\sigma \in K:\text{for all }b\in B,\chi (\sigma (b))=\chi (b)\}.$ Observe that: ${𝒞}_B(K\cup K^{\prime })={𝒞}_B(K)\cup {𝒞}_B(K^{\prime }),$ and ${𝒞}_{B\cup B^{\prime }}(K)={𝒞}_B(K)\cap {𝒞}_{B^{\prime }}(K).$ Note that if ${𝒞}_B(\sigma B)$ is non-empty, then it is a left-coset of the subgroup ${𝒞}_B(G)\le K$ [40, Lem. 2.4]. We now turn to solving the Color Automorphism problem. For $k\in \mathbb{N}$, let ${\mathrm{\Gamma }}_k$ be the class of groups $G$ where all the non-Abelian composition factors of $G$ are subgroups of $\text{Sym}(k)$.

The Color Automorphism takes as input generators for a subgroup $G\le \text{Sym}(A)$ with $G\in {\mathrm{\Gamma }}_k$, a $G$-stable subset $B$, and $\sigma \in \text{Sym}(A)$. The solution is ${𝒞}_B(\sigma G)$. We will consider the Color Automorphism problem in the case when $k=m\in O(\log n)$. In order to solve the Color Automorphism problem, we proceed via a divide-and-conquer procedure. We have the following cases in the recursion:

The recursion bottoms out when $|B|=1$. In this case, we compute the Pointwise Stabilizer of ${𝒞}_{B^{{\sigma }^{-1}}}(G)$ in ${\text{FOLL}}^{O(1)}$using Lem. 10(d). Now $\sigma {𝒞}_{B^{{\sigma }^{-1}}}(G)={𝒞}_B(\sigma G)$.

Suppose that $B$ is the disjoint union of $G$-stable subsets $Z_1,\mathrm{\dots },Z_k$. We use Lem. 10(g) to, in ${\text{FOLL}}^{O(1)}$, break $B$ up into orbits $Z_1,\mathrm{\dots },Z_k$. We now have that: ${𝒞}_B(\sigma G)={\bigcap }_{i=1}^k{𝒞}_{Z_i}(\sigma G).$ We may thus compute each ${𝒞}_{Z_i}(\sigma G)$ in parallel. As $G$ acts transitively on each $Z_i$, the recursive calls for ${𝒞}_{Z_i}(\sigma G)$ fall under Cases 1 or 3. In order to compute the intersection, we use a binary tree circuit of depth $O(\log k)\le O(\log |X|)\le O(\log \log n)$. At each node of the binary tree, we utilize the ${\text{FOLL}}^{O(1)}$ algorithm for CosetInt (Lem. 10h). Thus, the total non-recursive work in this case is ${\text{FOLL}}^{O(1)}$.

If $|B|>1$ and $B$ is not the disjoint union of at least two $G$-stable subsets, then we find a minimal $G$-block system in $B$, which we call $\mathrm{\Phi }$. As $|X|\in O(\log n)$, such a block system is ${\text{FOLL}}^{O(1)}$-computable (Lem. 10(f)). Furthermore, by Lem. 10(c), we may compute the kernel $K$ of the $G$-action on $\mathrm{\Phi }$ in ${\text{FOLL}}^{O(1)}$. From [2], we have that $[G:K]\in {(\log n)}^{O(\log \log n)}$. Thus, we may write $G$ as a union of ${(\log n)}^{O(\log \log n)}$ cosets: $G={\bigcup }_{i=1}^{[G:K]}{\tau }_{i}K$, using an AC circuit of depth $O((\log n)\mathrm{poly}(\log \log n))$ and size $\mathrm{poly}(n)$ (Lem. 11). Now the problem breaks up as follows: ${𝒞}_B(\sigma G)={\bigcup }_{i=1}^{[G:K]}{𝒞}_B(\sigma {\tau }_{i}K).$

In parallel, we recursively compute ${𝒞}_B(\sigma {\tau }_{i}K)$ for each $1\le i\le [G:K]$. As $K$ fixes (setwise) each block of $\mathrm{\Phi }$, the computation for each ${𝒞}_B(\sigma {\tau }_{i}K)$ falls under Case 1 or Case 2. We may, in parallel, recursively compute each ${𝒞}_B(\sigma {\tau }_{i}K)$. Each recursive call deals with subsets of size $|B|/\mathrm{\ell }$. When we recombine the cosets, we must take care to ensure that we only have $\text{poly}(n)$ generators. We accomplish this in ${\text{FOLL}}^{O(1)}$using Lem. 10(e). We use a binary tree circuit of depth $\log [G:K]\in O({(\log \log n)}^2)$ to compute ${𝒞}_B(\sigma G)$ from the ${𝒞}_B(\sigma {\tau }_{i}K)$ ($1\le i\le [G:K]$). This yields a circuit of depth $\mathrm{poly}(\log \log n)$ and size $\mathrm{poly}(n)$ to compute ${𝒞}_B(\sigma G)$.

A recursive call at the intransitive case (Case 2) results in either the base case (Case 1) or the transitive case (Case 3). Similarly, a recursive call at the transitive case (Case 3) results in either the base case (Case 1) or the intransitive case (Case 3). The recursive calls in the transitive case reduce the size of the problem by at least $1/2$. Thus, the recursion tree thus has height $O(\log m)=O(\log \log n)$. Each level of the recursion tree is computable using an AC circuit of depth $O((\log n)\mathrm{poly}(\log \log n))$ and size $\mathrm{poly}(n)$. Thus, in total, we require an AC circuit of depth $O((\log n)\mathrm{poly}(\log \log n))$ and size $\mathrm{poly}(n)$, as desired. This completes the proof of Prop. 14.

Babai [6] exhibited an algorithm that tests the equivalence of two linear codes of length $m$ in time ${(2+o(1))}^m$. He accomplished this by reducing to $\left(\genfrac{}{}{0pt}{}{m}{d}\right)$ instances of Graph Isomorphism – precisely, isomorphism testing of $d\times (m-d)$ bipartite graphs with colored edges. A careful analysis shows that Babai’s reduction is computable using an NC circuit of depth $O({\log }^{2}m)$ and size $\mathrm{poly}(m)$. As $m\in O(\log n)$, we obtain that this reduction is ${\text{FOLL}}^{O(1)}$-computable. By Thm. 13, we can decide isomorphism of such graphs using an AC circuit of depth $O(({\log }^{2}n)\cdot \mathrm{poly}(\log \log n))$ and size $\mathrm{poly}(n)$. The result now follows. $◀$