\section{Introduction}
\label{sec:introduction}
The \algprobm{Group Isomorphism} problem (\algprobm{GpI}) takes as input two finite groups $G$ and $H$, and asks if there exists an isomorphism $\varphi : G \to H$. When the groups are given by their multiplication (a.k.a. Cayley) tables, it is known that $\algprobm{GpI}$ belongs to $\textsf{NP} \cap \textsf{coAM}$. The generator-enumerator algorithm, attributed to Tarjan in 1978 \cite{MillerTarjan}, has time complexity $n^{\log_{p}(n) + O(1)}$, where $n$ is the order of the group and $p$ is the smallest prime dividing $n$. In more than 40 years, this bound has escaped largely unscathed: Rosenbaum \cite{Rosenbaum2013BidirectionalCD} (see \cite[Sec. 2.2]{GR16}) improved this to $n^{(1/4)\log_p(n) + O(1)}$. And even the impressive body of work on practical algorithms for this problem, led by Eick, Holt, Leedham-Green and O'Brien (e.\,g., \cite{BEO02, ELGO02, BE99, CH03}) still results in an $n^{\Theta(\log n)}$-time algorithm in the general case (see \cite[Page 2]{WilsonSubgroupProfiles}). In the past several years, there have been significant advances on algorithms with worst-case guarantees on the serial runtime for special cases of this problem including Abelian groups \cite{Kavitha, Vikas, Savage}, direct product decompositions \cite{WilsonDirectProductsArxiv, KayalNezhmetdinov}, groups with no Abelian normal subgroups \cite{BCGQ, BCQ}, coprime and tame group extensions \cite{Gal09,QST11,BQ, GQ15}, low-genus $p$-groups and their quotients \cite{LW12,BMWGenus2}, Hamiltonian groups \cite{DasSharma}, and groups of almost all orders \cite{DietrichWilson}.


In addition to the intrinsic interest of this natural problem, a key motivation for the $\algprobm{Group Isomorphism}$ problem is its close relation to the \algprobm{Graph Isomorphism} problem ($\algprobm{GI}$). In the Cayley (verbose) model, $\algprobm{GpI}$ reduces to $\algprobm{GI}$ \cite{ZKT}, 
while $\algprobm{GI}$ reduces to the succinct $\algprobm{GpI}$ problem \cite{Heineken1974TheOO, Mekler} (recently simplified \cite{HeQiao}). In light of Babai's breakthrough result that $\algprobm{GI}$ is quasipolynomial-time solvable \cite{BabaiGraphIso}, $\algprobm{GpI}$ in the Cayley model is a key barrier to improving the complexity of $\algprobm{GI}$. Both verbose $\algprobm{GpI}$ and $\algprobm{GI}$ are considered to be candidate $\textsf{NP}$-intermediate problems, that is, problems that belong to $\textsf{NP}$, but are neither in $\textsf{P}$ nor $\textsf{NP}$-complete \cite{Ladner}. There is considerable evidence suggesting that $\algprobm{GI}$ is not $\textsf{NP}$-complete \cite{Schoning, BuhrmanHomer, ETH, BabaiGraphIso, GILowPP, ArvindKurur}. As verbose $\algprobm{GpI}$ reduces to $\algprobm{GI}$, this evidence also suggests that $\algprobm{GpI}$ is not $\textsf{NP}$-complete. It is also known that $\algprobm{GI}$ is strictly harder than $\algprobm{GpI}$ under $\textsf{AC}^{0}$ reductions \cite{ChattopadhyayToranWagner}. Tor\'an showed that $\algprobm{GI}$ is $\textsf{DET}$-hard \cite{Toran}, which provides that $\algprobm{Parity}$ is $\textsf{AC}^{0}$-reducible to $\algprobm{GI}$. On the other hand, Chattopadhyay, Tor\'an, and Wagner showed that $\algprobm{Parity}$ is not $\textsf{AC}^{0}$-reducible to $\algprobm{GpI}$ \cite{ChattopadhyayToranWagner}. To the best of our knowledge, there is no literature on lower bounds for $\algprobm{GpI}$ in the Cayley table model. 


Despite $\algprobm{GpI}$ in the Cayley table model being strictly easier than $\algprobm{GI}$ under $\textsf{AC}^{0}$-reductions, there are several key approaches in the $\algprobm{GI}$ literature that are noticeably absent from $\algprobm{GpI}$; in particular, parallelization and the individualize-and-refine paradigm. In this paper, using Weisfeiler--Leman for groups \cite{WLGroups} as our main tool, we begin to bring both of these techniques to bear on $\algprobm{GpI}$. 

\noindent \\ \textbf{Main Results.} In this paper, we show that Weisfeiler--Leman serves as a key subroutine in developing efficient parallel isomorphism tests. 


Brachter \& Schweitzer \cite{WLGroups} actually introduced three different versions of WL for groups. While they are equivalent in terms of pebble complexity up to constant factors, their round complexity may differ by up to an additive $O(\log n)$ (see \Thm{WLEquivalence}), and their parallel complexities differ (see Section 2.4). Because of these differences we are careful to specify which version of WL for groups each result uses.

As we are interested in both the Weisfeiler--Leman dimension and the number of rounds, we introduce the following notation.

\begin{definition}
Let $k \geq 2$ and $r \geq 1$ be integers, and let $J \in \{ I, II, III \}$. The $(k, r)$-WL Version $J$ algorithm for groups is obtained by running $k$-WL Version $J$ for $r$ rounds. Here, the initial coloring counts as the first round.
\end{definition}


We first examine coprime extensions of the form $H \ltimes N$, where $N$ is Abelian and $H$ is $O(1)$-generated. Qiao, Sarma, \& Tang \cite{QST11} previously established an upper bound of $\cc{P}$ for isomorphism testing of this family of groups. We improve this bound as follows.

\begin{theorem} \label{ThmMainQST}
Groups of the form $H \ltimes N$, where $N$ is Abelian, $H$ is $O(1)$-generated, and $|H|$ and $|N|$ are coprime are identified by $(O(1), O(1))$-WL Version II. Consequently, isomorphism between a group of the above form and arbitrary groups can be decided in $\textsf{L}$.
\end{theorem}

We next parallelize a result of Brachter \& Schweitzer \cite{BrachterSchweitzerWLLibrary}, who showed that Weisfeiler--Leman can identify direct products in polynomial-time provided it can also identify the indecomposable direct factors in polynomial-time. Specifically, we show:

\begin{theorem} \label{ThmProductCanonicalForm}
For all $G = G_{1} \times \cdots \times G_{d}$ with the $G_i$ directly indecomposable, and all $k \geq 5$, if $(k,O(\log^c n))$-WL Version II identifies each $G_i$ for some $c \geq 1$, then $(k+1, O(\log^{c} n))$-WL identifies $G$.
\end{theorem}

More specifically, we show that for $k \geq 5$ and $r(n) \in \Omega(\log n)$, if a direct product $G$ is not distinguished from some group $H$ by $(k,r)$-WL Version II, then $H$ is a direct product, and there is some direct factor of $H$ that is not distinguished from some direct factor of $G$ by $(k-1,r)$-WL.

Prior to \Thm{ThmProductCanonicalForm}, the best-known upper bound on computing direct product decompositions was $\textsf{P}$ \cite{WilsonDirectProductsArxiv, KayalNezhmetdinov}. While Weisfeiler--Leman does not return explicit direct factors, it can implicitly compute a direct product decomposition in $O(\log n)$ rounds, which is sufficient for parallel isomorphism testing. In light of the parallel WL implementation due to Grohe \& Verbitsky, our result effectively provides that WL can decompose direct products in $\textsf{TC}^{1}$.

We next consider groups without Abelian normal subgroups. Using the individualize-and-refine paradigm, we obtain a new upper bound of $\textsf{quasiAC}^{1}$ for not only deciding isomorphisms, but also listing isomorphisms. While this does not improve upon the upper bound of $\textsf{P}$ for isomorphism testing \cite{BCQ}, this does parallelize the previous bound of $n^{\Theta(\log \log n)}$ runtime for listing isomorphisms \cite{BCGQ}.

\begin{theorem} \label{ThmSemisimpleIntro}
Let $G$ be a group without Abelian normal subgroups, and let $H$ be arbitrary. We can test isomorphism between $G$ and $H$ using an $\textsf{SAC}$ circuit of depth $O(\log n)$ and size $n^{\Theta(\log \log n)}$. Furthermore, all such isomorphisms can be listed in this bound.
\end{theorem}

Given the lack of lower bounds on \algprobm{GpI}, and Grohe \& Verbitsky's parallel WL algorithm, it is natural to wonder whether our parallel bounds could be improved. One natural approach to this is via the \emph{count-free} WL algorithm, which compares the set rather than the multiset of colors at each iteration. We show unconditionally that this algorithm fails to serve as a polynomial-time isomorphism test for even Abelian groups. 

\begin{theorem}
There exists an infinite family $(G_{n}, H_{n})_{n \geq 1}$ where $G_{n} \not \cong H_{n}$ are Abelian groups of the same order and count-free WL requires dimension $\geq \Omega(\log |G_n|)$ to distinguish $G_n$ from $H_n$.
\end{theorem}

While count-free WL is not sufficiently powerful to compare the multiset of colors, it turns out that $O(\log \log n)$-rounds of count-free $O(1)$-WL Version III will distinguish two elements of different orders. Thus, the multiset of colors computed by the count-free $(O(1), O(\log \log n))$-WL Version III for non-isomorphic Abelian groups $G$ and $H$ will be different. We may use $O(\log n)$ non-deterministic bits to guess the color class where $G$ and $H$ have different multiplicities, and then an $\textsf{MAC}^{0}$ circuit to compare said color class. This yields the following.

\begin{theorem} \label{thm:AbelianGpI}
Abelian Group Isomorphism is in $\beta_{1}\textsf{MAC}^{0}(\textsf{FOLL})$.
\end{theorem}

We note that this and \Thm{ThmSemisimpleIntro} illustrate uses of WL for groups as a \emph{subroutine} in isomorphism testing, which is how it is so frequently used in the case of graphs. To the best of our knowledge, the only previous use of WL as a subroutine for \algprobm{GpI} was in \cite{BGLQW}.

\begin{remark}
The previous best upper bounds for isomorphism testing of Abelian groups are linear time \cite{Kavitha, Vikas, Savage} and $\textsf{L} \cap \textsf{TC}^{0}(\textsf{FOLL})$ \cite{ChattopadhyayToranWagner}. As $\beta_{1}\textsf{MAC}^{0}(\textsf{FOLL}) \subseteq \textsf{TC}^{0}(\textsf{FOLL})$, \Thm{thm:AbelianGpI} improves the upper bound for isomorphism testing of Abelian groups.
\end{remark}

\paragraph{Methods.}
We find the comparison of methods at least as interesting as the comparison of complexity.  Here discuss at a high level the methods we use for each of our three main theorems above, and compare them to the methods of their predecessor results.

For \Thm{ThmMainQST}, its predecessor in Qiao--Sarma--Tang \cite{QST11} leveraged a result of Le Gall \cite{Gal09} on testing conjugacy of elements in the automorphism group of an Abelian group. (By further delving into the representation theory of Abelian groups, they were also able to solve the case where $H$ and $N$ are coprime and both are Abelian without any restriction on number of generators; we leave that as an open question in the setting of WL.) Here, we use the pebbling game. Our approach is to first pebble generators for the complement $H$, which fixes an isomorphism of $H$. For groups that decompose as a coprime extension of $H$ and $N$, the isomorphism type is completely determined by the multiplicities of the indecomposable $H$-module direct summands (\Lem{LemTaunt}). So far, this is the same group-theoretic structure leveraged by Qiao, Sarma, and Tang \cite{QST11}. However, we then use the representation-theoretic fact that, since $|N|$ and $|H|$ are coprime, each indecomposable $H$-module is generated by a single element (\Lem{LemThevenaz}); this is crucial in our setting, as it allows Spoiler to pebble that one element in the WL pebbling game. Then, as the isomorphism of $H$ is fixed, we show that any subsequent bijection that Duplicator selects must restrict to $H$-module isomorphisms on each indecomposable $H$-submodule of $N$ that is a direct summand. 

For \Thm{ThmSemisimpleIntro}, solving isomorphism of semisimple groups took a series of two papers \cite{BCGQ, BCQ}. Our result is really only a parallel improvement on the first of these (we leave the second as an open question). In Babai \emph{et al.} \cite{BCGQ}, they used \algprobm{Code Equivalence} techniques to identify semisimple groups where the minimal normal subgroups have a bounded number of non-Abelian simple direct factors, and to identify general semisimple groups in time $n^{O(\log \log n)}$. In contrast, WL---along with individualize-and-refine in the second case---provides a single, combinatorial algorithm that is able to detect the same group-theoretic structures leveraged in previous works to solve isomorphism in these families.

In parallelizing Brachter \& Schweitzer's direct product result in \Thm{ThmProductCanonicalForm}, we use two techniques. The first is simply carefully analyzing the number of rounds used in many of the proofs. In several cases, a careful analysis of the rounds used was not sufficient to get a strong parallel result. In those cases, we use the notion of \emph{rank}, which may be of independent interest and have further uses. 

Given a subset $C$ of group elements, the $C$-rank of $g \in G$ is the minimal word-length over $C$ required to generate $g$. If $C$ is easily identified by Weisfeiler--Leman, then WL can identify $\langle C \rangle$ in $O(\log n)$ rounds. This is made precise (and slightly stronger) with our Rank Lemma:

\begin{lemma}[Rank lemma] 
If $C \subseteq G$ is distinguished by $(k,r)$-WL, then any bijection $f$ chosen by Duplicator must respect $C$-rank, in the sense that $\rk_C(g) = \rk_{f(C)}(f(g))$ for all $g \in G$, or Spoiler can win with $k+1$ pebbles and $\max\{r,\log d + O(1)\}$ rounds, where $d = diam(Cay(\langle C \rangle, C)) \leq |\langle C \rangle| \leq |G|$.
\end{lemma}

One application of our Rank Lemma is that WL identifies verbal subgroups where the words are easily identified. Given a set of words $w_1(x_1, \dotsc, x_n), \dotsc, w_m(\vec{x})$, the corresponding \emph{verbal subgroup} is the subgroup generated by $\{w_i(g_1, \dotsc, g_n) : i=1,\dotsc, m, g_j \in G\}$. One example that we use in our results is the commutator subgroup. If Duplicator chooses a bijection $f : G \to H$ such that $f([x,y])$ is not a commutator word over $H$, then Spoiler pebbles $[x,y] \mapsto f([x,y])$ and wins in two additional rounds. Thus, by our Rank Lemma, if Spoiler does not map the commutator subgroup $[G, G]$ to the commutator subgroup $[H,H]$, then Duplicator wins with $1$ additional pebble and $O(\log n)$ additional rounds.

Brachter \& Schweitzer \cite{BrachterSchweitzerWLLibrary} obtained a similar result about verbal subgroups using different techniques. Namely, they showed that if WL assigns a distinct coloring to certain subsets $S_{1}, \ldots, S_{t}$, then WL assigns a unique coloring to the set of group elements satisfying systems of equations over $S_{1}, \ldots, S_{t}$. They analyzed the WL colorings directly. As a result, it is not clear how to compose their result with the pebble game. For instance, while their result implies that if Duplicator does not map $f([G,G]) = [H,H]$ then Spoiler wins, it is not clear how Spoiler wins nor how quickly Spoiler can win. Our result addresses these latter two points more directly.

\paragraph{Related Work.} There has been considerable work on efficient parallel ($\textsf{NC}$) isomorphism tests for graphs \cite{LindellTreeCanonization, BirgitKoblerMcKenzieToran, KoblerVerbitsky,WagnerBoundedTreewidth, ElberfeldSchweitzer, GroheVerbitsky, GroheKieferPlanar, DattaLimayeNimbhorkarPrajaktaThieraufWagner, datta_et_al:LIPIcs:2009:2314, ARVIND20121}. In contrast with the work on serial runtime complexity, the literature on the space and parallel complexity for $\algprobm{GpI}$ is quite minimal. Around the same time as Tarjan's $n^{\log_{p}(n) + O(1)}$-time algorithm for $\algprobm{GpI}$ \cite{MillerTarjan}, Lipton, Snyder, and Zalcstein showed that $\algprobm{GpI} \in \textsf{SPACE}(\log^{2}(n))$ \cite{LiptonSnyderZalcstein}. This bound has been improved to to $\beta_{2}\textsf{NC}^{2}$ ($\textsf{NC}^{2}$ circuits that receive $O(\log^{2}(n))$ non-deterministic bits as input) \cite{Wolf}, and subsequently to $\beta_{2}\textsf{L} \cap \beta_{2}\textsf{FOLL} \cap \beta_{2}\textsf{SC}^{2}$ \cite{ChattopadhyayToranWagner, TangThesis}. In the case of Abelian groups, Chattopadhyay, Tor\'an, and Wagner showed that $\algprobm{GpI} \in \textsf{L} \cap \textsf{TC}^{0}(\textsf{FOLL})$ \cite{ChattopadhyayToranWagner}. Tang showed that isomorphism testing for groups with a bounded number of generators can also be done in $\textsf{L}$ \cite{TangThesis}. Since composition factors of permutation groups can be identified in $\textsf{NC}$ \cite{BabaiLuksSeress} (see also \cite{BealsCompositionFactors} for a CFSG-free proof), isomorphism testing \emph{between} two permutation groups that are both direct products of simple groups (Abelian or non-Abelian) can be done in $\textsf{NC}$, using the regular representation, though this does not allow one to test isomorphism of such a group against an arbitrary permutation group. Finding direct factors in $\mathsf{NC}$ is a consequence of our \Thm{ThmProductCanonicalForm}. To the best of our knowledge, no other specific family of groups is known to admit an $\textsf{NC}$-computable isomorphism test prior to our paper.

Combinatorial techniques, such as individualization with Weisfeiler--Leman refinement, have also been incredibly successful in $\algprobm{GI}$, yielding efficient isomorphism tests for several families \cite{GroheVerbitsky, KieferPonomarenkoSchweitzer, GroheKieferPlanar, grohe_et_al:LIPIcs:2019:10693, grohe2019canonisation, BabaiWilmes, ChenSunTeng}. Weisfeiler--Leman is also a key subroutine in Babai's quasipolynomial-time isomorphism test \cite{BabaiGraphIso}. Despite the successes of such combinatorial techniques, they are known to be insufficient to place $\algprobm{GI}$ into $\textsf{P}$ \cite{CFI, NeuenSchweitzerIR}. In contrast, the use of combinatorial techinques for $\algprobm{GpI}$ is relatively new \cite{BGLQW, WLGroups, BrachterSchweitzerWLLibrary}, and it is a central open problem as to whether such techniques are sufficient to improve even the long-standing upper-bound of $n^{\Theta(\log n)}$ runtime.


Examining the distinguishing power of the counting logic $\mathcal{C}_{k}$ serves as a measure of descriptive  complexity for groups. In the setting of graphs, the descriptive complexity has been extensively studied, with \cite{GroheBook} serving as a key reference in this area. There has been recent work relating first order logics and groups \cite{FiniteGroupsFOL}, as well as work examining the descriptive complexity of finite abelian groups \cite{DescriptiveComplexityAbelianGroups}. However, the work on the descriptive complexity of groups is scant compared to the algorithmic literature on \algprobm{GpI}. 

Ehrenfeucht--Fra\"iss\'e games \cite{Ehrenfeucht, Fraisse}, also known as pebbling games, serve as another tool in proving the inexpressibility of certain properties in first-order logics. 
Two finite structures are said to be elementary equivalent if they satisfy the same first-order sentences. In such games, we have two players who analyze two given structures. Spoiler seeks to prove the structures are not elementary equivalent, while Duplicator seeks to show that the structures are indeed elementary equivalent. Spoiler begins by selecting an element from one structure, and Duplicator responds by picking a similar element from the other structure. Spoiler wins if and only if the eventual substructures are not isomorphic. 
Pebbling games have served as an important tool in analyzing graph properties like reachability \cite{ajtai_fagin_1990, ARORA199797}, designing parallel algorithms for graph isomorphism \cite{GroheVerbitsky}, and isomorphism testing of random graphs \cite{Rossman2009EhrenfeuchtFrassGO}.  


\section{Preliminaries}

\subsection{Groups}

Unless stated otherwise, all groups are assumed to be finite and represented by their Cayley tables. 
For a group of order $n$, the Cayley table has $n^{2}$ entries, each represented by a binary string of size $\lceil \log_{2}(n) \rceil$. For an element $g$ in the group $G$, we denote the \textit{order} of $g$ as $|g|$. We use $d(G)$ to denote the minimum size of a generating set for the group $G$. 

The \textit{socle} of a group $G$, denoted $\text{Soc}(G)$, is the subgroup generated by the minimal normal subgroups of $G$. If $G$ has no Abelian normal subgroups, then $\text{Soc}(G)$ decomposes as the direct product of non-Abelian simple factors. The \textit{normal closure} of a subset $S \subseteq G$, denoted $\text{ncl}(S)$, is the smallest normal subgroup of $G$ that contains $S$.

We say that a normal subgroup $N \trianglelefteq G$ \textit{splits} in $G$ if there exists a subgroup $H \leq G$ such that $H \cap N = \{1\}$ and $G = HN$. The conjugation action of $H$ on $N$ allows us to express multiplication of $G$ in terms of pairs $(h, n) \in H \times N$. We note that the conjugation action of $H$ on $N$ induces a group homomorphism $\theta : H \to \Aut(N)$ mapping $h \mapsto \theta_{h}$, where $\theta_{h} : N \to N$ sends $\theta_{h}(n) = hnh^{-1}$. So given $(H, N, \theta)$, we may define the group $H \ltimes_{\theta} N$ on the set $\{ (h, n) : h \in H, n \in N \}$ with the product $(h_{1}, n_{1})(h_{2}, n_{2}) = (h_{1}h_{2}, \theta_{h_{2}^{-1}}(n_{1})n_{2})$. We refer to the decomposition $G = H \ltimes_{\theta} N$ as a \textit{semidirect product} demoposition. When the action $\theta$ is understood, we simply write $G = H \ltimes N$. 

We are particularly interested in semidirect products when $N$ is a normal Hall subgroup. To this end, we recall the Schur--Zassenhaus Theorem \cite[(9.1.2)]{Robinson1982}.

\begin{theorem}[Schur--Zassenhaus]
Let $G$ be a finite group of order $n$, and let $N$ be a normal Hall subgroup. Then there exists a complement $H \leq G$, such that $\text{gcd}(|H|, |N|) = 1$ and $G = H \ltimes N$. Furthermore, if $H$ and $K$ are complements of $N$, then $H$ and $K$ are conjugate.
\end{theorem}

We will use the following standard observation a few times:

\begin{fact} \label{FactWordLength}
Let $G = \langle g_1, \dotsc, g_d \rangle$. Then every element of $G$ can be written as a word in the $g_i$ of length at most $|G|$.
\end{fact}

\begin{proof}
Consider the Cayley graph of $G$ with generating set $g_1, \dotsc, g_d$. Words correspond to walks in this graph. We need only consider simple walks---those which never visit any vertex more than once---since if a walk visits a group element $g$ more than once, then the part of that walk starting and ending at $g$ is a word that equals the identity element, so it can be omitted. But the longest simple walk is at most the number of vertices, which is $|G|$.
\end{proof}

\subsection{Weisfeiler--Leman}

We begin by recalling the Weisfeiler--Leman algorithm for graphs, which computes an isomorphism-invariant coloring. Let $\Gamma$ be a graph, and let $k \geq 2$ be an integer. The $k$-dimension Weisfeiler--Leman, or $k$-WL, algorithm begins by constructing an initial coloring $\chi_{0} : V(\Gamma)^{k} \to \mathcal{K}$, where $\mathcal{K}$ is our set of colors, by assigning each $k$-tuple a color based on its isomorphism type. That is, two $k$-tuples $(v_{1}, \ldots, v_{k})$ and $(u_{1}, \ldots, u_{k})$ receive the same color under $\chi_{0}$ iff the map $v_i \mapsto u_i$ (for all $i \in [k]$) is an isomorphism of the induced subgraphs $\Gamma[\{ v_{1}, \ldots, v_{k}\}]$ and $\Gamma[\{u_{1}, \ldots, u_{k}\}]$ and for all $i, j$, $v_i = v_j \Leftrightarrow u_i = u_j$. 

For $r \geq 0$, the coloring computed at the $r$th iteration of Weisfeiler--Leman is refined as follows. For a $k$-tuple $\overline{v} = (v_{1}, \ldots, v_{k})$ and a vertex $x \in V(\Gamma)$, define
\[
\overline{v}(v_{i}/x) = (v_{1}, \ldots, v_{i-1}, x, v_{i+1}, \ldots, v_{k}).
\]

The coloring computed at the $(r+1)$st iteration, denoted $\chi_{r+1}$, stores the color of the given $k$-tuple $\overline{v}$ at the $r$th iteration, as well as the colors under $\chi_{r}$ of the $k$-tuples obtained by substituting a single vertex in $\overline{v}$ for another vertex $x$. We examine this multiset of colors over all such vertices $x$. This is formalized as follows:
\begin{align*}
\chi_{r+1}(\overline{v}) = &( \chi_{r}(\overline{v}), \{\!\!\{ ( \chi_{r}(\overline{v}(v_{1}/x)), \ldots, \chi_{r}(\overline{v}(v_{k}/x) ) \bigr| x \in V(\Gamma) \}\!\!\} ),
\end{align*}
where $\{\!\!\{ \cdot \}\!\!\}$ denotes a multiset.

Note that the coloring $\chi_{r}$ computed at iteration $r$ induces a partition of $V(\Gamma)^{k}$ into color classes. The Weisfeiler--Leman algorithm terminates when this partition is not refined, that is, when the partition induced by $\chi_{r+1}$ is identical to that induced by $\chi_{r}$. The final coloring is referred to as the \textit{stable coloring}, which we denote $\chi_{\infty} := \chi_{r}$.


Brachter \& Schweitzer introduced three variants of WL for groups. WL Versions I and II are both played directly on the Cayley tables, where $k$-tuples of group elements are initially colored. For WL Version I, two $k$-tuples $(g_{1}, \ldots, g_{k})$ and $(h_{1}, \ldots, h_{k})$ receive the same initial color iff (a) for all $i, j, \ell \in [k]$, $g_{i}g_{j} = g_{\ell} \iff h_{i}h_{j} = h_{\ell}$, and (b) for all $i, j \in [k]$, $g_{i} = g_{j} \iff h_{i} = h_{j}$. For WL Version II, $(g_{1}, \ldots, g_{k})$ and $(h_{1}, \ldots, h_{k})$ receive the same initial color iff the map $g_{i} \mapsto h_{i}$ for all $i \in [k]$ extends to an isomorphism of the generated subgroups $\langle g_{1}, \ldots, g_{k} \rangle$ and $\langle h_{1}, \ldots, h_{k} \rangle$. For both WL Versions I and II, refinement is performed in the classical manner as for graphs. Namely, for a given $k$-tuple $\overline{g}$ of group elements,
\begin{align*}
\chi_{r+1}(\overline{g}) = &( \chi_{r}(\overline{g}), \{\!\!\{ ( \chi_{r}(\overline{g}(g_{1}/x)), \ldots, \chi_{r}(\overline{g}(g_{k}/x) ) \bigr| x \in G \}\!\!\} ).
\end{align*}

WL Version III works as follows. Given the Cayley table for a group $G$, we first apply a reduction from $\algprobm{GpI}$ to $\algprobm{GI}$ in the setting of simple, undirected graphs. We then apply the standard $k$-WL for graphs and pull back to a coloring on $G^{k}$. 

Given the Cayley table for a group $G$, we construct the graph $\Gamma_{G}$ as follows. We begin with a set of isolated vertices, corresponding to the elements of $G$. For each pair of elements $(g, h) \in G^{2}$, we add a multiplication gadget $M(g, h)$, which is constructed as follows (see Figure~\ref{MultiplicationGadget}).
\begin{itemize}
\item We add vertices $a_{gh}, b_{gh}, c_{gh}, d_{gh}$.
\item We add the edges:
\[
\{ g, a_{gh}\}, \{ h, b_{gh}\}, \{ b_{gh}, c_{gh}\}, \{c_{gh}, d_{gh} \}, \{ gh, d_{gh}\}.
\]
\end{itemize}

\begin{figure} 
\centering
\includegraphics{Multiplication_Gadget.png}
\caption{\label{MultiplicationGadget} The multiplication gadget that encodes the group multiplication $g \cdot h$ \cite{WLGroups}.}
\end{figure}

Observe that $\Gamma_{G}$ has $\Theta(|G|^{2})$ vertices. By consideration of vertex degrees, we also note that $G$ forms a canonical subset of $V(\Gamma_{G})$. 

\begin{remark} \label{RemarkReduction}
We note that the construction of $\Gamma_{G}$ can be done in $\textsf{AC}^{0}$. We may store $\Gamma_{G}$ as an adjacency matrix. Adding a single edge can be done using an $\textsf{AC}^{0}$ circuit. Each edge can be added independently; and thus, without increasing the depth of the circuit. As $|\Gamma_{G}| \in \Theta(|G|^{2})$, we need only a polynomial number of gates to add the appropriate edges. So $\Gamma_{G}$ can be constructed using an $\textsf{AC}^{0}$ circuit.
\end{remark}



\subsection{Pebbling Game}

We recall the bijective pebble game introduced by \cite{Hella1989, Hella1993} for WL on graphs. This game is often used to show that two graphs $X$ and $Y$ cannot be distinguished by $k$-WL. The game is an Ehrenfeucht--Fra\"iss\'e game (c.f., \cite{Ebbinghaus:1994, Libkin}), with two players: Spoiler and Duplicator. We begin with $k+1$ pairs of pebbles, which are placed beside the graph. Each round proceeds as follows.
\begin{enumerate}
\item Spoiler picks up a pair of pebbles $(p_{i}, p_{i}^{\prime})$. 
\item We check the winning condition, which will be formalized later.
\item Duplicator chooses a bijection $f : V(X) \to V(Y)$.
\item Spoiler places $p_{i}$ on some vertex $v \in V(X)$. Then $p_{i}^{\prime}$ is placed on $f(v)$. 
\end{enumerate} 

Let $v_{1}, \ldots, v_{m}$ be the vertices of $X$ pebbled at the end of step 1, and let $v_{1}^{\prime}, \ldots, v_{m}^{\prime}$ be the corresponding pebbled vertices of $Y$. Spoiler wins precisely if the map $v_{\ell} \mapsto v_{\ell}^{\prime}$ does not extend to an isomorphism of the induced subgraphs $X[\{v_{1}, \ldots, v_{m}\}]$ and $Y[\{v_{1}^{\prime}, \ldots, v_{m}^{\prime}\}]$. Duplicator wins otherwise. Spoiler wins, by definition, at round $0$ if $X$ and $Y$ do not have the same number of vertices. We note that $X$ and $Y$ are not distinguished by the first $r$ rounds of $k$-WL if and only if Duplicator wins the first $r$ rounds of the $(k+1)$-pebble game \cite{Hella1989, Hella1993, CFI}. 

Versions I and II of the pebble game are defined analogously, where Spoiler pebbles group elements on the Cayley tables. Precisely, for groups $G$ and $H$, each round proceeds as follows.
\begin{enumerate}
\item Spoiler picks up a pair of pebbles $(p_{i}, p_{i}^{\prime})$. 
\item We check the winning condition, which will be formalized later.
\item Duplicator chooses a bijection $f : G \to H$.
\item Spoiler places $p_{i}$ on some vertex $g \in G$. Then $p_{i}^{\prime}$ is placed on $f(g)$. 
\end{enumerate} 

Suppose that $(g_{1}, \ldots, g_{\ell}) \mapsto (h_{1}, \ldots, h_{\ell})$ have been pebbled. In Version I, Duplicator wins at the given round if this map satisfies the initial coloring condition of WL Version I: (a) for all $i, j, m \in [\ell]$, $g_{i}g_{j} = g_{m} \iff h_{i}h_{j} = h_{m}$, and (b) for all $i, j \in [\ell]$, $g_{i} = g_{j} \iff h_{i} = h_{j}$. In Version II, Duplicator wins at the given round if the map $(g_{1}, \ldots, g_{\ell}) \mapsto (h_{1}, \ldots, h_{\ell})$ extends to an isomorphism of the generated subgroups $\langle g_{1}, \ldots, g_{\ell} \rangle$ and $\langle h_{1}, \ldots, h_{\ell} \rangle.$ Brachter \& Schweitzer established that for $J \in \{I, II\}$, $(k,r)$-WL Version J is equivalent to version J of the $(k+1)$-pebble, $r$-round pebble game \cite{WLGroups}.

\begin{remark}
In our work, we explicitly control for both pebbles and rounds. In our theorem statements, we state explicitly the number of pebbles on the board. So if Spoiler can win with $k$ pebbles on the board, then we are playing in the $(k+1)$-pebble game. Note that $k$-WL corresponds to $k$-pebbles on the board.
\end{remark}

The pebble game for graphs is the same pebble game used to analyze the $k$-WL Version III algorithms for groups. Note that placing a pebble pair on vertices corresponding to the multiplication gadgets $M(g_{1}, g_{2})$ and $M(h_{1}, h_{2})$ (but not on the vertices corresponding to the group elements) induces a pairing of group elements. Here, we adopt the convention from Brachter \& Schweitzer \cite{WLGroups} in saying that $(g_{1}, g_{2}) \mapsto  (h_{1}, h_{2})$ are \textit{implicitly pebbled} if a pebble is placed on a non-group-element vertex of the multiplication gadget $M(g_1, g_2)$. Pebbling such a vertex is effectively as strong as pebbling two pairs of group elements simultaneously. We note that, unless a non-group element vertex on $M(g_{1}, g_{2})$ is pebbled, Duplicator need not select bijections $f : G \to H$ that map $M(g_{1}, g_{2}) \mapsto M(f(g_{1}), f(g_{2}))$.

Brachter \& Schweitzer showed that Duplicator must respect the multiplication structure of the implicitly pebbled elements, as well as the subgroups induced by the (implicitly) pebbled group elements \cite{WLGroups}: 
\begin{lemma}[{Brachter \& Schweitzer \cite[Lemma~3.10]{WLGroups}}] \label{LemBS}
Fix $m \geq 2$. Consider the $k$-pebble game on graphs $\Gamma_{G}$ and $\Gamma_{H}$. If $k \geq 4$ and one of the following happens:
\begin{enumerate}[label=(\alph*)]
\item Duplicator chooses a bijection on $f : \Gamma_{G} \to \Gamma_{H}$ with $f(G) \neq H$,
\item after choosing a bijection $f : \Gamma_{G} \to \Gamma_{H}$, there is a pebble pair $(p, p^{\prime})$ for which pebble $p$ is on some vertex of $M(g_{1}, g_{2})$ that is not a group element and $p^{\prime}$ is on some vertex of $M(h_{1}, h_{2})$ that is not a group element, but 
\[
(f(g_{1}), f(g_{2}), f(g_{1}g_{2})) \neq (h_{1}, h_{2}, h_{1}h_{2}),
\] 

or 

\item the map induced by the group elements pebbled or implicitly pebbled by $k-2$ pebbles does not extend to an isomorphism between the corresponding generated subgroups,
\end{enumerate}

then Spoiler can win with at most two additional pebbles and $\log_{2}(n) + O(1)$ addditional rounds.
\end{lemma}

In light of \Lem{LemBS}(a), we may simply consider bijections that Duplicator selects on the group elements. That is, we may without loss of generality consider bijections $f : G \to H$. We stress that condition (b) applies only when there is already a pebble on some element of a multiplication gadget. A priori, Duplicator need not select bijections that respect multiplication gadgets. That is, if there is no pebble on a multiplication gadget $M(g_{1}, g_{2})$, then Duplicator need not map $f(M(g_{1}, g_{2})) = M(f(g_{1}), f(g_{2}))$.

We also note that \Lem{LemBS}(c) provides that if Duplicator does not respect the subgroup structure of the (implicitly) pebbled group elements, then Spoiler can quickly win.

\begin{remark}
The original statement of \cite[Lemma~3.10]{WLGroups} did not specify the number of additional rounds. However, we are able to modify the proof of \cite[Lemma~3.10(c)]{WLGroups} to control the number of rounds. We defer the proof to Appendix \ref{CountWLEquivalence}.
\end{remark}

Brachter \& Schweitzer \cite[Theorem~3.9]{WLGroups} also previously showed that WL Version I, II, and III are equivalent up to a factor of $2$ in the dimension, though they did not control for rounds. We strengthen their analysis to explicitly control for rounds.

\begin{theorem} \label{WLEquivalence}
Let $G$ and $H$ be groups of order $n$. Let $k \geq 2, r \geq 1$. We have the following.
\begin{enumerate}[label=(\alph*)]
\item If $(k,r)$-WL Version I distinguishes $G$ and $H$, then $(k,r)$-WL Version II distinguishes $G$ and $H$.

\item If $(k,r)$-WL Version II distinguishes $G$ and $H$, then $(\lceil k/2 \rceil + 2, 3r + O(\log n))$-WL Version III distinguishes $G$ and $H$.

\item If $(k,r)$-WL Version III distinguishes $G$ and $H$, then $(2k+1, 2r)$-WL Version I distinguishes $G$ and $H$.
\end{enumerate}
\end{theorem}

\begin{proof}
See Appendix \ref{CountWLEquivalence}.
\end{proof}

\subsection{Weisfeiler--Leman as a Parallel Algorithm}

Grohe \& Verbitsky \cite{GroheVerbitsky} previously showed that for fixed $k$, the classical $k$-dimensional Weisfeiler--Leman algorithm for graphs can be effectively parallelized. Precisely, each iteration (including the initial coloring) can be implemented using a logspace uniform $\textsf{TC}^{0}$ circuit. As they mention (\cite[Remark~3.4]{GroheVerbitsky}), their implementation works for any first-order structure, including groups. However, because here we have three different versions of WL, we explicitly list out the resulting parallel complexities, which differ slightly between the versions.

\begin{itemize}
\item \textbf{WL Version I:} Let $(g_{1}, \ldots, g_{k})$ and $(h_{1}, \ldots, h_{k})$ be two $k$-tuples of group elements. We may test in $\textsf{AC}^{0}$ whether (a) for all $i, j, m \in [k]$, $g_{i}g_{j} = g_{m} \iff h_{i}h_{j} = h_{m}$, and (b) $g_{i} = g_{j} \iff h_{i} = h_{j}$. So we may decide if two $k$-tuples receive the same initial color in $\textsf{AC}^{0}$. Comparing the multiset of colors at the end of each iteration (including after the initial coloring), as well as the refinement steps, proceed identically as in \cite{GroheVerbitsky}. Thus, for fixed $k$, each iteration of $k$-WL Version I can be implemented using a logspace uniform $\textsf{TC}^{0}$. 

\item \textbf{WL Version II:} Let $(g_{1}, \ldots, g_{k})$ and $(h_{1}, \ldots, h_{k})$ be two $k$-tuples of group elements. We may use the marked isomorphism test of Tang \cite{TangThesis} to test in $\textsf{L}$ whether the map sending $g_{i} \mapsto h_{i}$ for all $i \in [k]$ extends to an isomorphism of the generated subgroups $\langle g_{1}, \ldots, g_{k} \rangle$ and $\langle h_{1}, \ldots, h_{k} \rangle$. So we may decide whether two $k$-tuples receive the same initial color in $\textsf{L}$. Comparing the multiset of colors at the end of each iteration (including after the initial coloring), as well as the refinement steps, proceed identically as in \cite{GroheVerbitsky}. Thus, for fixed $k$, the initial coloring of $k$-WL Version II is $\textsf{L}$-computable, and each refinement step is $\textsf{TC}^{0}$-computable.

\item \textbf{WL Version III:} From Remark \ref{RemarkReduction}, we have that constructing the graph from the Cayley table is $\textsf{AC}^{0}$-computable. We now appeal directly to the parallel WL implementation for graphs due to Grohe \& Verbitsky \cite{GroheVerbitsky}. Thus, each iteration of WL Version III can be implemented with a logspace uniform $\textsf{TC}^{0}$-circuit, and constructing the graph does not impact the complexity.
\end{itemize}


\subsection{Colored Graphs}

Let $k \in \mathbb{N}$, and let $\Gamma$ be a graph. A $k$-\textit{coloring}\footnote{Not to be confused with the usual ``proper $k$-coloring'' of a graph, that is, an assignment of one out of $k$ colors to each vertex such that no two adjacent vertices receive the same color. Despite this terminological overloading, we stick with this terminology for consistency with \cite{BrachterSchweitzerWLLibrary}.} over $\Gamma$ is a map $\gamma : V(\Gamma)^k \to \mathcal{K}$, where $\mathcal{K}$ is our finite set of colors. A $k$-coloring partitions $V(\Gamma)^k$ into color classes. When $k = 1$, we refer to the coloring as an \textit{element coloring}. For another natural number $m < k$, a $k$-coloring $\gamma^{(k)} : V(G)^k \to \mathcal{K}$ induces an $m$-coloring $\gamma^{(m)} : V(G)^k \to \mathcal{K}$ via:
\[
\gamma^{(m)}( (g_1, \ldots, g_m) ) := \gamma^{(k)}( (g_{1}, \ldots, g_{m}, 1, \ldots, 1) ).
\]

\begin{definition}
A \textit{colored graph} is a pair $(\Gamma, \gamma)$, where $\Gamma$ is a graph and $\gamma : V(G) \to \mathcal{K}$ is an element-coloring. We say that two colored graphs $(\Gamma_{1}, \gamma_{1}), (\Gamma_{2}, \gamma_{2})$ are \textit{isomorphic} if there is a graph isomorphism $\varphi : V(\Gamma_{1}) \to V(\Gamma_{2})$ that respects the colorings; that is, $\gamma_{2} \circ \varphi = \gamma_{1}$. We define $\text{Aut}_{\gamma}(\Gamma) = \{ \varphi \in \Aut(\Gamma) : \gamma \circ \varphi = \gamma\}$.	
\end{definition}


For $k \geq 2$, there is a natural analogue of $k$-WL that starts with a colored graph $(\Gamma, \gamma)$. The only difference is in constructing the initial coloring. Two $k$-tuples of vertices $\overline{u} := (u_{1}, \ldots, u_{k})$ and $\overline{v} := (v_{1}, \ldots, v_{k})$ receive the same initial color precisely if the following three conditions hold:
\begin{enumerate}[label=(\alph*)]
\item $\gamma(u_{i}) = \gamma(v_{i})$ for all $i \in [k]$,
\item The map $u_{i} \mapsto v_{i}$ for all $i \in [k]$ is an isomorphism of the induced subgraphs $\Gamma[\overline{u}]$ and $\Gamma[\overline{v}]$, and 
\item For all $i, j \in [k]$, $u_{i} = u_{j} \iff v_{i} = v_{j}$.
\end{enumerate}

The refinement step is performed in the classical way, where the color at round $r+1$ assigned to $\overline{v}$ is given by:
\begin{align*}
\chi_{r+1}(\overline{v}) = &( \chi_{r}(\overline{v}), \{\!\!\{ ( \chi_{r}(\overline{v}(v_{1}/x)), \ldots, \chi_{r}(\overline{v}(v_{k}/x) ) \bigr| x \in V(\Gamma) \}\!\!\} ),
\end{align*}

In the setting of groups, we may define a colored analogue of Weisfeiler--Leman Version III \cite{WLGroups}. Let $G$ be a group, and let $\gamma : G \to \mathcal{K}$ be a coloring. Let $\Gamma_{G}$ be the graph produced from $G$, using the reduction in the classical WL Version III algorithm. We obtain a colored graph $\Gamma_{G}$ by constructing a coloring $\gamma^{\prime} : V(\Gamma_{G}) \to \mathcal{K}$, where $\gamma^{\prime}(g) = \gamma(g)$ for all $g \in G$. We then apply the $k$-WL for colored graphs to $(\Gamma_{G}, \gamma^{\prime})$ and pull back the stable coloring to $G^k$. 

There is an analogous $(k+1)$-pebble game for colored graphs. Let $(X, \gamma_{X}), (Y, \gamma_{Y})$ be colored graphs. Each round proceeds as follows.
\begin{enumerate}
\item Spoiler picks up a pair of pebbles $(p_{i}, p_{i}^{\prime})$. 
\item We check the winning condition, which will be formalized later.
\item Duplicator chooses a bijection $f : V(X) \to V(Y)$.
\item Spoiler places $p_{i}$ on some vertex $v \in V(X)$. Then $p_{i}^{\prime}$ is placed on $f(v)$. 
\end{enumerate} 

Let $v_{1}, \ldots, v_{m}$ be the vertices of $X$ pebbled at the end of step 1, and let $v_{1}^{\prime}, \ldots, v_{m}^{\prime}$ be the corresponding pebbled vertices of $Y$. Spoiler wins precisely if the map $v_{\ell} \mapsto v_{\ell}^{\prime}$ does not extend to a colored isomorphism of the induced subgraphs $X[\{v_{1}, \ldots, v_{m}\}]$ and $Y[\{v_{1}^{\prime}, \ldots, v_{m}^{\prime}\}]$. Duplicator wins otherwise. Spoiler wins, by definition, at round $0$ if there is no color-preserving bijection $\varphi : V(X)^k \to V(Y)^k$ that respects such that $\gamma_{Y} \circ \varphi = \gamma_{X}$. We note that $X$ and $Y$ are not distinguished by the first $r$ rounds of $k$-WL if and only if Duplicator wins the first $r$ rounds of the $(k+1)$-pebble game. The proof is analogous to the case of uncolored graphs \cite{Hella1989, Hella1993, CFI}. We note that the colored pebble game on graphs is the corresponding pebble game for the colored analogue of WL Version III \cite{CFI, ImmermanLander1990, WLGroups}. 

To the best of our knowledge, the notion of colored group isomorphism was first introduced by Le Gall \& Rosenbaum \cite{GR16}. Brachter \& Schweitzer \cite{BrachterSchweitzerWLLibrary} subsequently introduced a notion of a colored group in close analogue to that of a colored graph. 




\section{Weisfeiler--Leman for Coprime Extensions}

In this section, we consider groups that admit a Schur--Zassenhaus decomposition of the form $G = H \ltimes N$, where $N$ is Abelian, and $H$ is $O(1)$-generated and $|H|$ and $|N|$ are coprime. Qiao, Sarma, and Tang \cite{QST11} previously exhibited a polynomial-time isomorphism test for this family of groups, as well as the family where $H$ and $N$ are arbitrary Abelian groups. This was extended by Babai \& Qiao \cite{BQ} to groups where $|H|$ and $|N|$ are coprime, $N$ is Abelian, and $H$ is an arbitrary group given by generators in any class of groups for which isomorphism can be solved efficiently. Among the class of such groups where $H$ is $O(1)$-generated, we are able to improve the parallel complexity to $\cc{L}$ via WL Version II. 

\subsection{Additional preliminaries for groups with Abelian normal Hall subgroup}
Here we recall additional preliminaries needed for our algorithm in the next section. None of the results in this section are new, though in some cases we have rephrased the known results in a form more useful for our analysis.

A \emph{Hall} subgroup of a group $G$ is a subgroup $N$ such that $|N|$ is coprime to $|G/N|$. When a Hall subgroup is normal, we refer to the group as a coprime extension. Coprime extensions are determined entirely by their actions: 

\begin{lemma}[{Taunt \cite{Taunt1955}}]  \label{LemmaSemidirect}
Let $G = H \ltimes_{\theta} N$ and $\hat{G} = \hat{H} \ltimes_{\hat{\theta}} \hat{N}$. If $\alpha : H \to \hat{H}$ and $\beta : N \to \hat{N}$ are isomorphisms such that for all $h \in H$ and all $n \in N$,
\[
\hat{\theta}_{\alpha(h)}(n) = (\beta \circ \theta_{h} \circ \beta^{-1})(n),
\]
then the map $(h, n) \mapsto (\alpha(h), \beta(n))$ is an isomorphism of $G \cong \hat{G}$. Conversely, if $G$ and $\hat{G}$ are isomorphic and $|H|$ and $|N|$ are coprime, then there exists an isomorphism of this form.
\end{lemma}

A $\mathbb{Z} H$-module is an abelian group $N$ together with an action of $H$ on $N$, given by a group homomorphism $\theta\colon H \to \Aut(N)$. Sometimes we colloquially refer to these as ``$H$-modules.'' A \emph{submodule} of an $H$-module $N$ is a subgroup $N' \leq N$ such that the action of $H$ on $N'$ sends $N'$ into itself, and thus the restriction of the action of $H$ to $N'$ gives $N'$ the structure of an $H$-module compatible with that on $N$. Given a subset $S \subseteq N$, the smallest $H$-submodule containing $S$ is denoted $\langle S \rangle_H$, and is referred to as the $H$-submodule \emph{generated by} $S$. An $H$-module generated by a single element is called \emph{cyclic}. Note that a cyclic $H$-module $N$ need not be a cyclic Abelian group.

Two $H$-modules $N,N'$ are isomorphic (as $H$-modules), denoted $N \cong_H N'$, if there is a group isomorphism $\varphi\colon N \to N'$ that is $H$-equivariant, in the sense that $\varphi(\theta(h)(n)) = \theta'(h)(\varphi(n))$ for all $h \in H, n \in N$. An $H$-module $N$ is \emph{decomposable} if $N \cong_H N_1 \oplus N_2$ where $N_1, N_2$ are nonzero $H$-modules (and the direct sum can be thought of as a direct sum of Abelian groups); otherwise $N$ is \emph{indecomposable}. An equivalent characterization of $N$ being decomposable is that there are nonzero $H$-submodules $N_1, N_2$ such that $N = N_1 \oplus N_2$ as Abelian groups (that is, $N$ is generated as a group by $N_1$ and $N_2$, and $N_1 \cap N_2 = 0$). The Remak--Krull--Schmidt Theorem says that every $H$-module decomposes as a direct sum of indecomposable modules, and that the multiset of $H$-module isomorphism types of the indecomposable modules appearing is independent of the choice of decomposition, that is, it depends only on the $H$-module isomorphism type of $N$. We may thus write 
\[
N \cong_H N_1^{\oplus m_1} \oplus N_2^{\oplus m_2} \oplus \dotsb \oplus N_k^{\oplus m_k}
\]
unambiguously, where the $N_i$ are pairwise non-isomorphic indecomposable $H$-modules. When we refer to the multiplicity of an indecomposable $H$-module as a direct summand in $N$, we mean the corresponding $m_i$.\footnote{For readers familiar with (semisimple) representations over fields, we note that the multiplicity is often equivalently defined as $\dim_\mathbb{F} \text{Hom}_{\mathbb{F} H}(N_i, N)$. However, when we allow $N$ to be an Abelian group that is not elementary Abelian, we are working with $(\mathbb{Z}/p^k \mathbb{Z})[H]$-modules, and the characterization in terms of hom sets is more complicated, because one indecomposable module can be a submodule of another, which does not happen with semisimple representations. }

The version of Taunt's Lemma that will be most directly useful for us is:
\begin{lemma} \label{LemTaunt}
Let $G_i = H \ltimes_{\theta_i} N$ for $i=1,2$ be two semi-direct products with $|H|$ coprime to $|N|$. Then $G_1 \cong G_2$ if and only if there is an automorphism $\alpha \in \Aut(H)$ such that each indecomposable $\mathbb{Z} H$-module appears as a direct summand in $(N, \theta_1)$ and in $(N, \theta_2 \circ \alpha)$ with the same multiplicity.
\end{lemma}

The lemma and its proof are standard but we include it for completeness.

\begin{proof}
If there is an automorphism $\alpha \in \Aut(H)$ such that the multiplicity of each indecomposable $\mathbb{Z} H$-module as a direct summand of $(N, \theta_1)$ and $(N, \theta_2 \alpha)$ are the same, then there is a $\mathbb{Z} H$-module isomorphism $\beta \colon (N, \theta_1) \to (N, \theta_2 \circ \alpha)$ (in particular, $\beta$ is an automorphism of $N$ as a group). Then it is readily verified that the map $(h,n) \mapsto (\alpha(h), \beta(n))$ is an isomorphism of the two groups.

Conversely, suppose that $\varphi \colon G_1 \to G_2$ is an isomorphism. Since $|H|$ and $|N|$ are coprime, $N$ is characteristic in $G_i$, so we have $\varphi(N) = N$. And by order considerations $\varphi(H)$ is a complement to $N$ in $G_2$. We have $\theta_1(h)(n) = hnh^{-1}$. Since $\varphi$ is an isomorphism, we have $\varphi(\theta_1(h)(n)) = \varphi(hnh^{-1}) = \varphi(h) \varphi(n) \varphi(h)^{-1} = \theta_2(\varphi(h))(\varphi(n))$. Thus $\theta_1(h)(n) = \varphi^{-1}(\theta_2(\varphi(h))(\varphi(n)))$. So we may let $\alpha = \varphi|_H$, and then we have that $(N,\theta_1)$ is isomorphic to $(N, \theta_2 \circ \varphi|_H)$, where the isomorphism of $H$-modules is given by $\varphi|_N$. The Remak--Krull--Schmidt Theorem then gives the desired equality of multiplicities.
\end{proof}

When $N$ is elementary Abelian the following lemma is not necessary. A $(\mathbb{Z}/p^k \mathbb{Z})[H]$-module is an $\mathbb{Z} H$-module $N$ where the exponent of $N$ (the LCM of the orders of the elements of $N$) divides $p^k$. 

\begin{lemma}[{see, e.\,g., Thev\'{e}naz \cite{Thevenaz}}] \label{LemThevenaz}
Let $H$ be a finite group. If $p$ is coprime to $|H|$, then any indecomposable $(\mathbb{Z}/p^k \mathbb{Z})[H]$-module is generated (as an $H$-module) by a single element.
\end{lemma}

\begin{proof}
Thev\'{e}naz \cite[Cor.~1.2]{Thevenaz} shows that there are cyclic $(\mathbb{Z}/p^k \mathbb{Z})[H]$-modules $M_1, \dotsc, M_n$, each with underlying group of the form $(\mathbb{Z}/p^k \mathbb{Z})^{d_i}$ for some $d_i$,  such that each indecomposable $(\mathbb{Z}/p^k \mathbb{Z})[H]$-module is of the form $M_i / p^j M_i$ for some $i,j$, and for distinct pairs $(i,j)$ we get non-isomorphic modules. 
\end{proof}




\subsection{Coprime Extensions with an $O(1)$-Generated Complement}
Our approach is to first pebble generators for the complement $H$, which fixes an isomorphism of $H$. As the isomorphism of $H$ is then fixed, we show that any subsequent bijection that Duplicator selects must restrict to $H$-module isomorphisms on each indecomposable $H$-submodule of $N$ that is a direct summand. For groups that decompose as a coprime extension of $H$ and $N$, the isomorphism type is completely determined by the multiplicities of the indecomposable $H$-module direct summands (\Lem{LemTaunt}). We then leverage the fact that, in the coprime case, indecomposable $H$-modules are generated by single elements (\Lem{LemThevenaz}), making it easy for Spoiler to pebble.

\begin{lemma} \label{CheckCoprime}
Let $G = H \ltimes N$, where $N$ is Abelian, $H$ is $O(1)$-generated, and $\text{gcd}(|H|, |N|) = 1$. Let $K$ be an arbitrary group of order $|G|$. If $K$ does not decompose as $H \ltimes N$ (for any action), then $(O(1), O(1))$-WL Version II will distinguish $G$ and $K$.
\end{lemma}

\begin{proof}
Let $f : G \to K$ be the bijection that Duplicator selects. As $N \leq G$, as a subset, is uniquely determined by its orders---it is precisely the set of all elements in $G$ whose orders divide $|N|$---we may assume that $K$ has a normal Hall subgroup of size $|N|$. For first, if for some $n \in N$, $|n| \neq |f(n)|$, Spoiler can pebble $n \mapsto f(n)$ and win immediately. By reversing the roles of $K$ and $G$, it follows that $K$ must have precisely $|N|$ elements whose orders divide $|N|$. Second, suppose that those $|N|$ elements do not form a subgroup. Then there are two elements $x,y \in f(N)$ such that $xy \notin f(N)$. At the first round, Spoiler pebbles $a := f^{-1}(x) \mapsto x$. Let $f' : G \to K$ be the bijection Duplicator selects at the next round. As $K$ has precisely $|N|$ elements of order dividing $|N|$, we may assume that $f'(N) = f(N)$ (setwise). Let $b \in N$ s.t. $f'(b) = y$. Spoiler pebbles $b \mapsto y$. Now as $N$ is a group, $ab \in N$. However, as $f(a)f'(b) \not \in f(N)$, $|ab| \neq |f(a)f'(b)|$. So the map $(a, b) \mapsto (x, y)$ does not extend to an isomorphism. Spoiler now wins.

Now we have that $f(N)$ is a subgroup of $K$, and because it is the set of all elements of these orders, it is characteristic and thus normal. Suppose that $f(N) \not \cong N$. We have two cases: either $f(N)$ is not Abelian, or $f(N)$ is Abelian but $N \not \cong f(N)$. Suppose first that $f(N)$ is not Abelian. Let $x \in f(N)$ such that $x \not \in Z(f(N))$, and let $g := f^{-1}(x) \in N$. Spoiler pebbles $g \mapsto x$. Let $f' : G \to K$ be the bijection that Duplicator selects at the next round. We may again assume that $f'(N) = f(N)$ (setwise), or Spoiler wins with two additional pebbles and two additional rounds. Now let $y \in f(N)$ such that $[x,y] \neq 1$. Let $h \in G$ such that $f'(h) = y$. Spoiler pebbles $h \mapsto y$. Now the map $(g, h) \mapsto (x, y)$ does not extend to an isomorphism, so Spoiler wins. Suppose instead that $f(N)$ is Abelian. As Abelian groups are determined by their orders, we have by the discussion in the first paragraph that Spoiler wins with $2$ pebbles and $2$ rounds.

So now suppose that $N \cong f(N) \leq K$ is a normal Abelian Hall subgroup, but that $f(N)$ does not have a complement isomorphic to $H$. We note that if $K$ contains a subgroup $H'$ that is isomorphic to $H$, then by order considerations, $H'$ and $f(N)$ would intersect trivially in $K$ and we would have that $K = H' \cdot f(N)$. That is, $K$ would decompose as $K = H \ltimes f(N)$. So as $f(N)$ does not have a complement in $K$ that is isomorphic to $H$, by assumption we have that $K$ does not contain any subgroup isomorphic to $H$. 
In this case, Spoiler implicitly pebbles the $O(1)$ generators of $H$ in $G$. As $K$ has no subgroup isomorphic to $H$, Spoiler immediately wins after the generators for $H \leq G$ have been pebbled. The result follows.
\end{proof}




\begin{theorem}
Let $G = H \ltimes N$, where $N$ is Abelian, $H$ is $O(1)$-generated, and $\text{gcd}(|H|, |N|) = 1$. We have that $(O(1), O(1))$-WL Version II identifies $G$.
\end{theorem}

\begin{proof}
Let $K \not \cong G$ be an arbitrary group of order $|G|$. By \Lem{CheckCoprime}, we may assume that $K = H \ltimes N$; otherwise, Spoiler wins in at most $2$ rounds. Furthermore, from the proof of \Lem{CheckCoprime}, we may assume that Duplicator selects bijections $f : G \to K$ mapping $N \cong f(N)$ (though $f|_{N}$ need not be an isomorphism), or Spoiler wins with a single round.

Spoiler uses the first $k := d(H)$ rounds to pebble generators $(g_{1}, \ldots, g_{k}) \mapsto (h_{1}, \ldots, h_{k})$ for $H$. As $K = H \ltimes N$, we may assume that the map $(g_{1}, \ldots, g_{k}) \mapsto (h_{1}, \ldots, h_{k})$ induces an isomorphism with a copy of $H \leq K$; otherwise, Spoiler immediately wins. Let $f : G \to K$ be the bijection that Duplicator selects. As $G, K$ are non-isomorphic groups of the form $H \ltimes N$, they differ only in their actions. Now the actions are determined by the multiset of indecomposable $H$-modules in $N$. As $|H|, |N|$ are coprime, we have by \Lem{LemThevenaz} that the indecomposable $H$-modules are cyclic. As $G \not \cong K$, we have by \Lem{LemmaSemidirect} that there exists $n \in N \leq G$ such that $\langle n \rangle_{H}$ is indecomposable, and $\langle n \rangle_{H}$ and $\langle f(n) \rangle_{f(H)}$ are inequivalent $H$-modules. Spoiler now pebbles $n \mapsto f(n)$. Thus, the following map
\[
(g_{1}, \ldots, g_{k}, n) \mapsto (h_{1}, \ldots, h_{k}, f(n))
\]

\noindent does not extend to an isomorphism. So Spoiler wins.
\end{proof}

\begin{remark}
We see that the main places we used coprimality were: (1) that $N$ was characteristic, and (2) that all indecomposable $H$-modules (in particular, those appearing in $N$) were cyclic. 
\end{remark}



\section{A ``rank'' lemma}
\begin{definition} \label{DefRank}
Let $C \subseteq G$ be a subset of a group $G$ that is closed under taking inverses. We define the \emph{C-rank} of $g \in G$, denoted $\rk_C(g)$, as the minimum $m$ such that $g$ can be written as a word of length $m$ in the elements of $C$. If $g$ cannot be so written, we define $\rk_C(g) = \infty$.
\end{definition}

Our definition and results actually extend to subsets that aren't closed under taking inverses, but we won't have any need for that case, and it would only serve to make the wording less clear.

\begin{remark}
Our terminology is closely related to the usage of ``$X$-rank'' in algebra and geometry, which generalizes the notions of matrix rank and tensor rank: if $X \subseteq V$ is a subset of an $\mathbb{F}$-vector space, then the $X$-rank of a point $v \in V$ is the smallest number of elements of $x \in X$ such that $v$ lies in their linear span. If we replace $X$ by the union $\mathbb{F}^* X$ of its nonzero scaled versions (which is unnecessary in the most common case, in which $X$ is the cone over a projective variety), then the $X$-rank in the sense of algebraic geometry would be the $\mathbb{F}X$-rank in our terminology above. For example, matrix rank is $X$-rank inside the space of $n \times m$ matrices under addition, where $X$ is the set of rank-1 matrices (which is already closed under nonzero scaling).
\end{remark}

\begin{lemma}[Rank lemma] \label{LemmaRank}
If $C \subseteq G$ is distinguished by $(k,r)$-WL$_{II}$, then any bijection $f$ chosen by Duplicator must respect $C$-rank, in the sense that $\rk_C(g) = \rk_{f(C)}(f(g))$ for all $g \in G$, or Spoiler can win with $k+1$ pebbles and $\max\{r,\log d + O(1)\}$ rounds, where $d = diam(Cay(\langle C \rangle, C)) \leq |\langle C \rangle| \leq |G|$.
\end{lemma}

Our primary uses of this lemma in this paper are to show that if $C$ is distinguished by $(k,r)$-WL, then $\langle C \rangle$ is distinguished by $(k+O(1), r + \log n)$-WL. However, the preservation of $C$-rank itself, rather than merely the subgroup generated by $C$, seems potentially useful for future applications. In particular, \Lem{LemmaRank} shows that WL can identify verbal subgroups in $O(\log n)$ rounds, provided WL can readily identify each word.

\begin{proof}
Note that since $C$ is detectable by $(k,r)$-WL, there is a set $C' \subseteq H$ such that for any bijection $f$ chosen by Duplcator, $f(C)=C'$, otherwise Spoiler can win with $k$ pebbles in $r$ rounds. We will thus use $\rk(x)$ to denote $\rk_C(x)$ if $x \in G$, and $\rk_{C'}(x)$ if $x \in H$. We proceed by induction on the rank. 

By assumption, rank-1 elements must be sent to rank-1 elements, since $C = \{g \in G: \rk(g)=1\}$, or Spoiler can win with $k$ pebbles in $r$ rounds.

Let $r \geq 1$, and suppose for all $1 \leq j \leq r$, if $\rk(x)=j$, then $\rk(f(x))=\rk(x)$. Suppose $x \in G$ is such that $\rk(x) = r+1$ but $\rk(f(x)) \neq \rk(x)$. Since $f$ is a bijection on elements of smaller rank, the only possibility is $\rk(f(x)) > r+1$. Spoiler begins by pebbling $x \mapsto f(x)$. 

Let $f' : G \to H$ be the bijection that Duplicator selects at the next round. Write $x = x_{1} \cdots x_{r+1}$, where for each $i$, $x_i \in C$. For $1 \leq i \leq j \leq r+1$, write $x[i, \ldots, j] := x_{i} \cdots x_{j}$. We consider the following cases.
\begin{itemize}
\item \textbf{Case 1:} Suppose first that $\rk(y) = \rk(f'(y))$ for all $y \in G$ with $\rk(y) \leq r$. In this case, Spoiler pebbles $x[2, \ldots, r+1] \mapsto f'(x[2, \ldots, r+1])$. Let $f'' : G \to H$ be the bijection that Duplicator selects at the next round. If $\rk(x_{1}) = \rk(f''(x_{1})) = 1$, then $f''(x_{1}) \cdot f'(x[2, \ldots, r+1]) \neq f(x)$, since $\rk(f''(x_1)) = 1$ and $\rk(f'(x[2, \ldots, r+1])) = r$, so their product has rank at most $r+1 < \rk(f(x))$. In this case, Spoiler pebbles $x_{1}$ and wins immediately since $f''$ does not extend to a bijection on the pebbled elements $x_1, x[2,\ldots,r+1]$. 

If instead, $1=\rk(x_{1}) < \rk(f''(x_{1}))$, Spoiler pebbles $x_{1}$ and wins with $k-1$ additional pebbles and $r$ additional rounds by assumption. Note that once $x_{1} \mapsto f''(x_{1})$ has been pebbled, Spoiler can reuse the pebble on $x$. So we only need $k-1$ additional pebbles rather than $k$ pebbles.

\item \textbf{Case 2:} Suppose instead that the hypothesis of Case 1 is not satisfied. Then $\rk(y) \neq \rk(f'(y))$ for some $y \in \langle C \rangle$ with $\rk(y) \leq r$. In the next two rounds, Spoiler pebbles $x[1, \ldots, \lceil (r+1)/2 \rceil]$ and $x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]$. Let $f'' : G \to H$ be the next bijection that Duplicator selects. If
\[
f(x) \neq f''(x[1, \ldots, \lceil (r+1)/2 \rceil]) \cdot f''(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]),
\]

then Spoiler immediately wins. If 
\[
f(x) = f''(x[1, \ldots, \lceil (r+1)/2 \rceil]) \cdot f''(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]),
\]
 
then either
\begin{align*}
&\rk(x[1, \ldots, \lceil (r+1)/2 \rceil]) < \rk(f''(x[1, \ldots, \lceil (r+1)/2 \rceil])) \, \text{ or } \\ 
&\rk(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]) < \rk(f''(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1])), 
\end{align*}
since $\rk(f(x)) > \rk(x) = \rk(x[1, \ldots, \lceil (r+1)/2 \rceil]) + \rk(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1])$. 

Without loss of generality, suppose that $\rk(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]) < \rk(f''(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]))$. As Spoiler has already pebbled $x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1] \mapsto f''(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]).$ We may iterate on this argument at most $\log(r+1) + 1$ times until we hit the case when $\rk(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]) = 1 < \rk(f''(x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]))$. By assumption, every element of $\langle C \rangle$ can be written as a word of length at most $d$ in the elements of $C$, so we have $r \leq d$, and thus only $O(\log d)$ rounds are required. (That $d \leq |\langle C \rangle|$ follows from Fact~\ref{FactWordLength}.)

We claim that the preceding procedure can be implemented with at most $k+2$ pebbles. After Spoiler pebbles $x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]$, they may reuse the pebbles on $x$ and $x[1, \ldots, \lceil (r+1)/2 \rceil]$. We eventually reach a case in which there exists $g \in C$ such that Duplicator maps $g$ to some element outside of $C'$. In this case, Spoiler pebbles $g$, using the pebble on $x$. Now Spoiler uses the pebbles on $x[1, \ldots, \lceil (r+1)/2 \rceil]$, $x[\lceil (r+1)/2 \rceil + 1, \ldots, r+1]$, and $k-2$ additional pebbles to win. In total, Spoiler has used $k+1$ pebbles.  In a similar manner as Case 1, at most $k-1$ additional pebbles are required to identify $C$.
\end{itemize}

Finally, we must handle the case of infinite rank. By symmetry, it suffices to show that Spoiler can win in the case when $\rk(x) = r+1$, but $\rk(f(x)) = \infty$. In this case, the same argument starting from the third paragraph works \textit{mutatis mutandis}, as $\rk(f(x)) = \infty > r + 1$.  
\end{proof}



\section{Direct Products}

Brachter \& Schweitzer previously showed that Weisfeiler--Leman Version II can detect direct product decompositions in polynomial-time. Precisely, they showed that the WL dimension of a group $G$ is at most one more than the WL dimensions of the direct factors of $G$. We strengthen the result to control for rounds, effectively showing that WL Version II can compute direct product decompositions using $O(\log n)$ rounds. 

In this section, we establish the following.
\begin{theorem} \label{ThmProduct}
Let $G = G_{1} \times \cdots \times G_{d}$ be a decomposition into indecomposable direct factors, let $k \geq 5$, and let $r := r(n) \in \Omega(\log n)$. If $G$ and $H$ are not distinguished by $(k, r)$-WL Version II, then there exist direct factors $H_{i} \leq H$ such that $H = H_{1} \times \cdots \times H_{d}$ such that for all $i \in [d]$, $G_{i}$ and $H_{i}$ are not distinguished by $(k-1, r)$-WL Version II.
\end{theorem}

The structure and definitions in this section closely follow those of \cite[Sec.~6]{BrachterSchweitzerWLLibrary} for ease of comparison.

\subsection{Preliminaries}

We begin by introducing some additional preliminaries.

\begin{definition}
Let $G_{1}, G_{2}$ be groups, and let $Z_{i} \leq Z(G_{i})$ be central subgroups. Given an isomorphism $\varphi : Z_{1} \to Z_{2}$, the \textit{central product} of $G_{1}$ and $G_{2}$ with respect to $\varphi$ is:
\[
G_{1} \times_{\varphi} G_{2} = (G_{1} \times G_{2}) / \{ (g, \varphi(g^{-1})) : g \in Z_{1} \}.
\]

A group $G$ is the \textit{(internal) central product} of subgroups $G_{1}, G_{2} \leq G$, provided that $G = G_{1}G_{2}$ and $[G_{1}, G_{2}] = \{1\}$. 
\end{definition}

\begin{remark}
In general, a group may have several inherently different central decompositions. On the other hand, indecomposable direct decompositions are unique in the following sense.
\end{remark}

\begin{lemma}[{See, e.g., \cite[3.8.3]{Robinson1982}}]
Let $G = G_{1} \times \ldots \times G_{m} = H_{1} \times \ldots \times H_{n}$ be two direct decompositions of $G$ into directly indecomposable factors. Then $n = m$, and there exists a permutation $\sigma \in \text{Sym}(n)$ such that for all $i$, $G_{i} \cong H_{\sigma(i)}$ and $G_{i}Z(G) \cong H_{\sigma(i)}Z(G)$.
\end{lemma}


By the preceding lemma, the multiset of subgroups $\{\!\{ G_{i}Z(G) \}\!\}$ is invariant under automorphism. 

\begin{definition}[{\cite[Def.~6.3]{BrachterSchweitzerWLLibrary}}]
We say that a central decomposition $\{H_1, H_2\}$ of $G = H_{1}H_{2}$ is \textit{directly induced} if there exist subgroups $K_{i} \leq H_{i}$ ($i = 1, 2$) such that $G = K_{1} \times K_{2}$ and $H_{i} = K_{i}Z(G)$.
\end{definition}


\begin{lemma}[{\cite[Lemma~6.4]{BrachterSchweitzerWLLibrary}}]
Let $k \geq 4, r \geq 1$. Let $G_{1}, G_{2}, H_{1}, H_{2}$ be groups such $G_{i}$ and $H_{i}$ are not distinguished by $(k, r)$-WL. Then $G_{1} \times G_{2}$ and $H_{1} \times H_{2}$ are not distinguished by $(k, r)$-WL.
\end{lemma}

\begin{remark}
The statement of \cite[Lemma~6.4]{BrachterSchweitzerWLLibrary} does not mention rounds; however, the proof holds when considering rounds.
\end{remark}


\subsection{Abelian and Semi-Abelian Case}

\begin{definition}[{\cite[Def.~6.5]{BrachterSchweitzerWLLibrary}}]
Let $G$ be a group. We say that $x \in G$ \textit{splits} from $G$ if there exists a complement $H \leq G$ such that $G = \langle x \rangle \times H$.
\end{definition}

We recall the following technical lemma \cite[Lemma~6.6]{BrachterSchweitzerWLLibrary} that characterizes the elements that split from an Abelian $p$-group.

\begin{lemma}[{\cite[Lemma~6.6]{BrachterSchweitzerWLLibrary}}]
Let $A$ be a finite Abelian $p$-group, and let $A = A_{1} \times \cdots \times A_{m}$ be an arbitrary cyclic decomposition. Then $a = (a_{1}, \ldots, a_{m}) \in A$ splits from $A$ if and only if there exists some $i \in [m]$ such that $|a| = |a_{i}|$ and $a_{i} \in A_{i} \setminus (A_{i})^{p}$. In particular, $x$ splits from $A$ if and only if there does not exist a $y \in A$ such that $|xy^{p}| < |x|$.
\end{lemma}

We utilize this lemma to show that WL can detect elements that split from $A$.

\begin{lemma} \label{LemmaSylowSplit}
Let $A, B$ be Abelian $p$-groups of order $n$, and let $f : A \to B$ be the bijection Duplicator selects. If $x \in A$ splits from $A$, but $f(x)$ does not split from $B$, then Spoiler can win with $2$ pebbles and $2$ rounds.
\end{lemma}

\begin{proof}
Spoiler begins by pebbling $x \mapsto f(x)$. Let $f' : A \to B$ be the bijection that Duplicator selects at the next round. As $f(x)$ does not split from $B$, there exists $z \in B$ such that $|f(x) \cdot z^{p}| < |f(x)|$. Let $y = (f')^{-1}(z) \in A$. Spoiler pebbles $y \mapsto f'(y) = z$. Now $|xy| \neq |f(x) \cdot z|$. So Spoiler immediately wins.
\end{proof}

\begin{remark}
To characterize when an element splits in a general Abelian group $A$, we begin by considering the decomposition of $A$ into its Sylow subgroups: $A = P_{1} \times \cdots \times P_{m}$. Now $x = (x_{1}, \ldots, x_{m}) \in A$ splits from $A$ if and only if for each $i \in [m]$, $x_{i}$ is either trivial or splits from $P_{i}$. See, e.g., \cite[Lemma~6.8]{BrachterSchweitzerWLLibrary}.
\end{remark}

\begin{lemma} \label{LemmaSplitAbelian}
Let $A, B$ be Abelian groups. Let $A = P_{1} \times \cdots \times P_{m}$ and $B = Q_{1} \times \cdots \times Q_{m}$, where the $P_{i}$ are the Sylow subgroups of $A$ and the $Q_{i}$ are the Sylow subgroups of $B$ (for each $i$, $P_i$ and $Q_i$ are $p_i$-subgroups for the same prime $p_i$). Let $f : A \to B$ be the bijection that Duplicator selects. Let $x = (x_{1}, \ldots, x_{m})$ be the decomposition of $x$, where $x_{i} \in P_{i}$, and let $f(x) = (y_{1}, \ldots, y_{m})$, where $y_{i} \in Q_{i}$. Suppose that Spoiler pebbles $x \mapsto f(x)$. Let $f' : A \to B$ be the bijection that Duplicator selects at the next round.
\begin{enumerate}[label=(\alph*)]
\item If $f'(x_{i}) \neq y_{i}$, then Spoiler can win with $1$ additional pebbles and $1$ additional round.

\item If $x \in A$ splits from $A$, but $f(x)$ does not split from $B$, then Spoiler can win with $2$ pebbles and $2$ rounds.
\end{enumerate}
\end{lemma}

\begin{proof}
We proceed as follows.
\begin{enumerate}[label=(\alph*)]
\item Suppose there exists an $i \in [m]$ such that $f'(x_{i}) \neq y_{i}$. Spoiler pebbles $x_{i} \mapsto f'(x_{i})$. Suppose that $P_{i}, Q_{i}$ are Sylow $p$-subgroups of $A, B$ respectively. As $x_{i} \in P_{i}$, we have that $\langle x \cdot x_{i}^{-1} \rangle$ has order coprime to $p$. However, as $f(x_{i}) \neq y_{i}$, $\langle f(x) \cdot f(x_{i})^{-1} \rangle$ has order divisible by $p$. So $|x \cdot x_{i}^{-1}| \neq |f(x) \cdot f(x_{i})^{-1}|$. Thus, Spoiler wins at the end of this round.

\item We recall that nilpotent groups are direct products of their Sylow subgroups. Furthermore, for a given prime divisor $p$, the Sylow $p$-subgroup of a nilpotent group is unique and contains all the elements whose order is a power of $p$. Thus, each Sylow subgroup of a nilpotent group is characteristic as a set. So now by (a), we may assume that $f'(x_{i}) = y_{i}$. Let $i \in [m]$ such that $x_{i}$ splits from $P_{i}$, but $f'(x_{i}) = y_{i}$ does not split from $Q_{i}$. Spoiler pebbles $x_{i} \mapsto f'(x_{i}) = y_{i}$. Now by \Lem{LemmaSylowSplit}, applied to $x_{i} \mapsto f'(x_{i})$, Spoiler wins with $2$ additional pebbles and $2$ additional rounds.
\end{enumerate}
\end{proof}


We now show that Duplicator must select bijections that preserve both the center and commutator subgroups setwise. Here is our first application of the Rank Lemma~\ref{LemmaRank}, which was not present in \cite{BrachterSchweitzerWLLibrary}. We begin with the following standard definition.

\begin{definition}
For a group $G$ and $g \in G$, the \textit{commutator width} of $g$, denoted $\cw(g)$, is the $\{[g,h] : g,h \in G \}$-rank (see Definition~\ref{DefRank}). The commutator width of $G$, denoted $\cw(G)$, is the maximum commutator width of any element of $[G,G]$.
\end{definition}


\begin{lemma} \label{IdentifyCenterCommutator}
Let $G, H$ be finite groups of order $n$. Let $f : G \to H$ be the bijection that Duplicator selects. 
\begin{enumerate}[label=(\alph*)]
\item If $f(Z(G)) \neq Z(H)$, then Spoiler can win with $2$ pebbles and $2$ rounds.
\item If there exist $x, y \in G$ such that $f([x,y])$ is not a commutator $[h,h']$ for any $h,h' \in H$, then Spoiler can win with $3$ pebbles and $3$ rounds.
\item If there exists $g \in G$ such that $\cw(g) \neq \cw(f(g))$, then Spoiler can win with $4$ pebbles and $O(\log \cw(G)) \leq O(\log n)$ rounds.
\end{enumerate}
\end{lemma}

Brachter \& Schweitzer previously showed that $2$-WL Version II identifies $Z(G)$, and $3$-WL Version II identifies the commutator $[G,G]$ \cite{BrachterSchweitzerWLLibrary}. Here, using our Rank Lemma~\ref{LemmaRank} for commutator width, we obtain that $4$-WL identifies the commutator in $O(\log n)$ rounds.


\begin{proof}[Proof of \Lem{IdentifyCenterCommutator}]
\noindent 
\begin{enumerate}[label=(\alph*)]
\item Let $x \in Z(G)$ such that $f(x) \not \in Z(H)$. Spoiler begins by pebbling $x \mapsto f(x)$. Let $f' : G \to H$ be the bijection that Duplicator selects at the next round. Let $y \in H$ such that $f'(x)$ and $y$ do not commute. Let $a := (f')^{-1}(y) \in G$. Spoiler pebbles $a \mapsto f'(a) = y$ and wins.

\item Spoiler pebbles $[x, y] \mapsto f([x,y])$. At the next two rounds, Spoiler pebbles $x, y$. Regardless of Duplicator's choices, Spoiler wins.

\item Apply the Rank Lemma~\ref{LemmaRank} to the set of commutators. By part (b), this set is identified by $(4,O(\log n))$-WL, so the Rank Lemma gives part (c).
\end{enumerate}
\end{proof}


By \Lem{IdentifyCenterCommutator}, Duplicator must select bijections that preserve the center and commutator subgroups setwise (or Spoiler can win). A priori, these bijections need not restrict to isomorphisms on the center or commutator. We note, however, that we may easily decide whether two groups have isomorphic centers, as the center is Abelian. Precisely, by \cite[Corollary~5.3]{BrachterSchweitzerWLLibrary}, $(2,1)$-WL identifies Abelian groups. Note that we need an extra round to handle the case in which Duplicator maps an element of $Z(G)$ to some element not in $Z(H)$. So $(2,2)$-WL identifies both the set of elements in $Z(G)$ and its isomorphism type.


We now turn to detecting elements that split from arbitrary groups. To this end, we recall the following lemma from \cite{BrachterSchweitzerWLLibrary}.

\begin{lemma}[{\cite[Lemma~6.9]{BrachterSchweitzerWLLibrary}}]
Let $G$ be a finite group and $z \in Z(G)$. Then $z$ splits from $G$ if and only if $z[G,G]$ splits from $G/[G,G]$ and $z \not \in [G, G]$. 
\end{lemma}

We apply this lemma to show that WL can detect the set of elements that split from an arbitrary finite group, improving \cite[Corollary~6.10]{BrachterSchweitzerWLLibrary} to control for rounds:

\begin{lemma}[{Compare rounds cf. \cite[Corollary~6.10]{BrachterSchweitzerWLLibrary}}] \label{LemmaGeneralSplit}
Let $G, H$ be finite groups. Let $f : G \to H$ be the bijection that Duplicator selects. Suppose that $x$ splits from $G$, but $f(x)$ does not split from $H$. Then Spoiler can win with $4$ pebbles and $O(\log n)$ rounds.
\end{lemma}

\begin{proof}
By \Lem{IdentifyCenterCommutator}, we have that if $x \not \in [G, G]$ but $f(x) \in [H, H]$, then Spoiler can win with $4$ pebbles and $O(\log n)$ rounds. So suppose that $x \not \in [G, G]$ and $f(x) \not \in [H, H]$. It suffices to check whether $x[G,G]$ splits from $G/[G,G]$, but $f(x)[H, H]$ does not split from $H/[H,H]$. By \cite[Lemma~4.11]{BrachterSchweitzerWLLibrary}, it suffices to consider the pebble game on $(G/[G,G], H/[H,H])$. To this end, we apply \Lem{LemmaSplitAbelian} to $G/[G,G]$ and $H/[H,H]$. 

As $f([G,G]) = [H,H]$, $f$ induces a bijection $\overline{f} : G/[G, G] \to H/[H,H]$ on the cosets. As $f$ was an arbitrary bijection that preserves $[G, G]$, we may assume WLOG that Duplicator selected $\overline{f}$ in the quotient game on $(G/[G,G], H/[H, H])$. The result now follows.
\end{proof}


We now consider splitting in two special cases.

\begin{lemma}[{\cite[Lemma~6.11]{BrachterSchweitzerWLLibrary}}]
Let $U \leq G$ and $x \in Z(G) \cap U$. If $x$ splits from $G$, then $x$ splits from $U$.
\end{lemma}

\begin{lemma}[{\cite[Lemma~6.12]{BrachterSchweitzerWLLibrary}}] \label{BSLemma612}
Let $G = G_{1} \times G_{2}$, and let $z := (z_{1}, z_{2}) \in Z(G)$ be an element of order $p^{k}$ for some prime $p$. Then $z$ splits from $G$ if and only if there exists an $i \in \{1,2\}$ such that $z_{i}$ splits from $G_{i}$ and $|z_{i}| = |z|$.
\end{lemma}

We now consider the semi-Abelian case. Here our groups are of the form $H \times A$, where $H$ has no Abelian direct factors and $A$ is Abelian.


\begin{theorem} [{Compare rounds cf. \cite[Lemma~6.13]{BrachterSchweitzerWLLibrary}}] 
\label{IdentifyAbelianDirectFactor}
Let $G_{1} = H \times A$, with a maximal Abelian direct factor $A$. Then the isomorphism class of $A$ is identified by $(4, O(1))$-WL Version II. That is, if $(4, O(1))$-WL fails to distinguish $G$ and $\widetilde{G}$, then $\widetilde{G}$ has a maximal Abelian direct factor isomorphic to $A$.
\end{theorem}

\begin{proof}
We adapt the proof of \cite[Lemma~6.13]{BrachterSchweitzerWLLibrary} to control for rounds. Let $\widetilde{G}$ be a group such that $(4, O(1))$-WL fails to distinguish $G$ and $\widetilde{G}$. By \Lem{IdentifyCenterCommutator} and the subsequent discussion, we may assume that $Z(G) \cong Z(\widetilde{G})$ using $(2,2)$-WL Version II. As Abelian groups are direct products of their Sylow subgroups, it follows that $Z(G)$ and $Z(\widetilde{G})$ have isomorphic Sylow subgroups. Write $\widetilde{G} = \widetilde{H} \times \widetilde{A}$, where $\widetilde{A}$ is the maximal Abelian direct factor. As $Z(G) \cong Z(\widetilde{G})$, we write $Z$ for the Sylow $p$-subgroup of $Z(G) \cong Z(\widetilde{G})$. Consider the primary decomposition of $Z$:
\[
Z := Z_{1} \times \ldots \times Z_{m},
\]
where $Z_{i} \cong (\mathbb{Z}/p^{i}\mathbb{Z})^{e_{i}}$, for $e_{i} \geq 0$. For each $i \in [m]$, there exist subgroups $H_{i} \leq Z(H)$ and $A_{i} \leq A$ such that $Z_{i} \cong H_{i} \times A_{i}$. Similarly, there exist $\widetilde{H_{i}} \leq \widetilde{H}$ and $\widetilde{A_{i}} \leq \widetilde{A}$ such that $Z_{i} \cong \widetilde{H_{i}} \times \widetilde{A_{i}}$. As $Z(G) \cong Z(\widetilde{G})$, we have that $H_{i} \times A_{i} \cong \widetilde{H_{i}} \times \widetilde{A_{i}}$. It suffices to show that each $A_{i} \cong \widetilde{A_{i}}$. As $H$ does not have any Abelian direct factors, we have by \cite[Lemma~6.12]{BrachterSchweitzerWLLibrary} (reproduced as \Lem{BSLemma612} above) that a central element $x$ of order $p^{i}$ splits from $G$ if and only if the projection of $x$ onto $A_{i}$, denoted $A_{i}(x)$, has order $p^{i}$. The same holds for $\widetilde{G}$ and the $\widetilde{A_{i}}$ factors. By \Lem{LemmaSplitAbelian}, we may assume that Duplicator selects bijections $f : G \to H$ such that if $x \in Z(G)$ splits from $Z_{i}$, then $f(x)$ splits from $f(Z_{i})$. The result follows.
\end{proof}

We now recall the definition of a component-wise filtration, introduced by Brachter \& Schweitzer \cite{BrachterSchweitzerWLLibrary} to control the non-Abelian part of a direct product.

\begin{definition} [{\cite[Def.~6.14]{BrachterSchweitzerWLLibrary}}]
Let $G = L \times R$, and let $\pi_{L}(U_{i})$ (resp. $\pi_{R}(U_{i})$) be the natural projection map onto $L$ with kernel $R$ (resp., the natural projection onto $R$ with kernel $L$). A \textit{component-wise filtration} of $U \leq G$ with respect to $L$ and $R$ is a chain of subgroups $\{1\} = U_{0} \leq \cdots \leq U_{r} = U$, such that for all $i \in [r]$, we have that $U_{i+1} \leq \pi_{L}(U_{i})$ or $U_{i+1} \leq \pi_{R}(U_{i})$. For $J \in \{I, II, III\}$, the filtration is $k$-WL$_{J}$-detectable, provided all subgroups in the chain are  $k$-WL$_{J}$-detectable.
\end{definition}

Brachter \& Schweitzer previously showed \cite[Lemma~6.15]{BrachterSchweitzerWLLibrary} that there exists a component-wise filtration of $Z(G)$ with respect to $H$ and $A$ that is $4$-WL$_{I}$-detectable. We extend this result to control for rounds. The proof that such a filtration exists is identical to that of \cite[Lemma~6.15]{BrachterSchweitzerWLLibrary}; we get a bound on the rounds using our \Lem{LemmaGeneralSplit}, which is a round-controlled version of their Corollary~6.10. For completeness, we indicated the needed changes here.

\begin{lemma} \label{LemmaFiltration}
Let $G = H \times A$, with maximal Abelian direct factor $A$. The component-wise filtration of $Z(G)$ with respect to $H$ and $A$ from \cite[Lemma~6.15]{BrachterSchweitzerWLLibrary} (reproduced above) is $(4,O(\log n))$-WL$_{II}$-detectable.
\end{lemma}

\begin{proof}[Proof]
Their proof that the filtration is 4-WL detectable uses only two parts: the fact that central $e$-th powers are detectable, and their Corollary~6.10. Using our \Lem{LemmaGeneralSplit} in place of their Corollary~6.10, we get 4 pebbles and $O(\log n)$ rounds, so all that is left to handle is central $e$-th powers. Suppose Duplicator selects a bijection $f : G \to H$ where $g = x^{e}$ for some $x \in Z(G)$ and $f(g)$ is not a central $e$th power. We have already seen that Duplicator must map the center to the center, so we need only handle the condition of being an $e$-th power. At the first round, Spoiler pebbles $g \mapsto f(g)$. At the next round, Spoiler pebbles $x$ and wins. Thus Spoiler can win with 2 pebbles in 2 rounds.
\end{proof}


We now show that in the semi-Abelian case $G = H \times A$, with maximal Abelian direct factor $A$, the WL dimension of $G$ depends on the WL dimension of $H$.

\begin{lemma}[{Compare rounds to \cite[Lemma~6.16]{BrachterSchweitzerWLLibrary}}] \label{SemiAbelianDirectProduct}
Let $G = H \times A$ and $\widetilde{G} = \widetilde{H} \times \widetilde{A}$, where $A$ and $\widetilde{A}$ are maximal Abelian direct factors. Let $k \geq 5$ and $r \in \Omega(\log n)$. If $(k-1, r)$-WL fails to distinguish $G$ and $\widetilde{G}$, then $(k, r)$-WL fails to distinguish $H$ and $\widetilde{H}$.
\end{lemma}

\begin{proof}
By \Thm{IdentifyAbelianDirectFactor}, we may assume that $A \cong \widetilde{A}$. Consider the component-wise filtrations from the proof of \cite[Lemma~6.15]{BrachterSchweitzerWLLibrary}, $\{1\} = U_{0} \leq \cdots \leq U_{r} = Z(G)$ with respect to the decomposition $G = H \times A$ and $\{1\} = \widetilde{U_{0}} \leq \cdots \leq \widetilde{U_{r}} = Z(\widetilde{G})$ with respect to the decomposition $\widetilde{G} = \widetilde{H} \times \widetilde{A}$. 

Let $V_{i}, W_{i}, \widetilde{V_{i}}, \widetilde{W_{i}}$ be as defined in the proof of \cite[Lemma~6.15]{BrachterSchweitzerWLLibrary} and recalled above. We showed in the proof of \Lem{LemmaFiltration} that for any bijection $f : G \to \widetilde{G}$ Duplicator selects, $f(V_{i}) = \widetilde{V_{i}}$ and $f(W_{i}) = \widetilde{W_{i}}$, or Spoiler may win with $4$ pebbles and $O(\log n)$ rounds.

In the proof of \cite[Lemma~6.16]{BrachterSchweitzerWLLibrary}, Brachter \& Schweitzer established that for all $1 \neq x \in Z(H) \times \{1\}$ and all $1 \neq  y \in \{1\} \times A$, $\min\{ i : x \in U_{i} \} \neq \min\{ i : y \in U_{i}\}$. 
Furthermore, by \cite[Lemma~4.14]{BrachterSchweitzerWLLibrary}, we may assume that Duplicator selects bijections at each round that respect the subgroup chains and their respective cosets, without altering the number of rounds (their proof is round-by-round). It follows that whenever $g_{1}g_{2}^{-1} \in Z(H) \times \{1\}$, we have that $f(g_{1})f(g_{2})^{-1} \not \in \{1\} \times A$.

Furthermore, Brachter \& Schweitzer also showed in the proof of \cite[Lemma~6.16]{BrachterSchweitzerWLLibrary} that Duplicator must map $H \times \{1\}$ to a system of representatives modulo $\{1\} \times \widetilde{A}$. Thus, Spoiler can restrict the game to $H \times \{1\}$. Now if $(k,r)$-WL Version II distinguishes $H$ and $\widetilde{H}$, then Spoiler can ultimately reach a configuration $((h_{1}, 1), \ldots, (h_{k-1}, 1)) \mapsto (x_{1}, a_{1}), \ldots, (x_{k-1}, a_{k-1})$ such that the induced configuration over $(G/(\{1\} \times A), \widetilde{G}/(\{1\} \times \widetilde{A}))$ fulfills the winning condition for Spoiler. That is, considered as elements of $G/(\{1\} \times A)$ (resp., $\widetilde{G}/(\{1\} \times \widetilde{A})$), the map $(h_1, \dotsc, h_{k-1}) \mapsto (x_1, \dotsc, x_{k-1})$ does not extend to an isomorphism. This implies that the pebbled map $((h_{1}, 1), \ldots, (h_{k-1}, 1)) \mapsto (x_{1}, a_{1}), \ldots, (x_{k-1}, a_{k-1})$ in the original groups (rather than their quotients) does not extend to an isomorphism. For suppose $f$ is any bijection extending the pebbled map. By the above, without loss of generality, $f$ maps $H \times \{1\}$ to a system of coset representatives of $\{1\} \times \widetilde{A}$, that is, if Duplicator can win, Duplicator can win with such a map. Let $\overline{f}$ be the induced bijection on the quotients $G/(\{1\} \times A) \to \tilde{G} / (\{1\} \times \tilde{A} )$. Since the pebbled map on the quotients does not extend to an isomorphism, there is a word $w$ such that $\overline{f}(w(h_1, \dotsc, h_{k-1})) \neq w(x_1, \dotsc, x_{k-1})$. But then when we consider $f$ restricted to $H \times \{1\}$, we find that $f(w((h_1,1), \dotsc, (h_{k-1},1))) = f( (w(h_1, \dotsc, h_{k-1}), 1) ) \neq (w(x_1, \dotsc, x_{k-1}), w(a_1, \dotsc, a_{k-1}))$, because their $H$ coordinates are different.
\end{proof}

Lem \ref{SemiAbelianDirectProduct} yields the following corollary.

\begin{corollary} \label{cor:DasSharmaGeneralized}
Let $G = H \times A$, where $H$ is identified by $(O(1), O(\log n))$-WL and does not have an Abelian direct factor, and $A$ is Abelian. Then $(O(1), O(\log n))$-WL identifies $G$. In particular, isomorphism testing of $G$ and an arbitrary group $\widetilde{G}$ is in $\textsf{TC}^{1}$.
\end{corollary}

\begin{proof}
By \Lem{SemiAbelianDirectProduct}, as $H$ is identified by $(O(1), O(1))$-WL, we have that $G$ is identified by $(O(1), O(\log n))$-WL. As only $O(1)$ rounds are required, we apply the parallel WL implementation due to Grohe \& Verbitsky \cite{GroheVerbitsky} to obtain the bound of $\textsf{TC}^{1}$ for isomorphism testing. 
\end{proof}

\begin{remark}
Das \& Sharma \cite{DasSharma} previously exhibited a nearly-linear time algorithm for groups of the form $H \times A$, where $H$ has size $O(1)$ and $A$ is Abelian. \Cor{cor:DasSharmaGeneralized} generalizes this to the setting where $H$ is $O(1)$-generated. While \Cor{cor:DasSharmaGeneralized} does not improve the runtime, it does establish a new parallel upper bound for isomorphism testing. 
\end{remark}



\subsection{General Case}

Following the strategy in \cite{BrachterSchweitzerWLLibrary}, we reduce the general case to the semi-Abelian case. Consider a direct decomposition $G = G_{1} \times \ldots \times G_{d}$, where each $G_{i}$ is directly indecomposable. The multiset of subgroups $\{\!\{ G_{i}Z(G) \}\!\}$ is independent of the choice of decomposition. We first show that Weisfeiler--Leman detects $\bigcup_{i} G_{i}Z(G)$. Next, we utilize the fact that the connected components of the non-commuting graph on $G$, restricted to $\bigcup_{i} G_{i}Z(G)$, correspond to the subgroups $G_{i}Z(G)$. 

\begin{definition}
For a group $G$, the \textit{non-commuting graph} $X_{G}$ has vertex set $G$, and an edge $\{g, h\}$ precisely when $[g, h] \neq 1$.
\end{definition}

\begin{proposition}[{\cite[Proposition~2.1]{ABDOLLAHI2006468}}]
If $G$ is non-Abelian, then $X_{G}[G \setminus Z(G)]$ is connected.
\end{proposition}

Our goal now is to first construct a canonical central decomposition of $G$ that is detectable by WL. This decomposition will serve to approximate $\bigcup_{i} G_{i}Z(G)$ from below.

\begin{definition}[{\cite[Definition~6.19]{BrachterSchweitzerWLLibrary}}] \label{MaximalCentralizerDef}
Let $G$ be a finite, non-Abelian group. Let $M_{1}$ be the set of non-central elements $g$ whose centralizers $C_{G}(g)$ have maximal order among all non-central elements. For $i \geq 1$, define $M_{i+1}$ to be the union of $M_i$ and the set of elements $g \in G \setminus \langle M_{i} \rangle$ that have maximal centralizer order $|C_{G}(g)|$ amongst the elements in $G \setminus \langle M_{i} \rangle$. Let $M := M_{\infty}$ be the stable set resulting from this procedure.

Consider the subgraph $X_{G}[M]$, and let $X_{1}, \ldots, X_{m}$ be the connected components. Set $N_{i} := \langle X_{i} \rangle$. We refer to $N_{1}, \ldots, N_{m}$ as the \textit{non-Abelian components} of $G$. 
\end{definition}

Brachter \& Schweitzer previously established the following \cite{BrachterSchweitzerWLLibrary}.

\begin{lemma}[{\cite[Lemma~6.20]{BrachterSchweitzerWLLibrary}}] \label{LemBSCanonicalDecomposition}
In the notation of Definition \ref{MaximalCentralizerDef}, we have the following.
\begin{enumerate}[label=(\alph*)]
\item $M$ is $3$-WL$_{II}$-detectable.
\item $G = N_{1} \cdots N_{m}$ is a central decomposition of $G$. For all $i$, $Z(G) \leq N_{i}$ and $N_{i}$ is non-Abelian. In particular, $M$ generates $G$.

\item If $G = G_{1} \times \ldots \times G_{d}$ is an arbitrary direct decomposition, then for each $i \in [m]$, there exists a unique $j \in [d]$ such that $N_{i} \subseteq G_{j}Z(G)$. Collect all such $i$ for one fixed $j$ in an index set $I_{j}$. Then
\[
N_{j_{1}}N_{j_{2}} \cdots N_{j_{\ell}} = G_{j}Z(G),
\]

where $I_{j} = \{ j_{1}, \ldots, j_{\ell} \}$. 
\end{enumerate}
\end{lemma}

We note that \Lem{LemBSCanonicalDecomposition}(b)-(c) are purely group theoretic statements. For our purposes, it is necessary, however, to adapt \Lem{LemBSCanonicalDecomposition}(a) to control for rounds. This is our second use of our Rank Lemma~\ref{LemmaRank}, this time applied to the set $M_i$ from Definition \ref{MaximalCentralizerDef}.

\begin{lemma} \label{LemBSCanonicalDecompositionA}
Let $G$ and $H$ be finite non-Abelian groups, let $M_{i,G}$ (resp., $M_{i,H}$) denote the sets from Definition \ref{MaximalCentralizerDef} for $G$ (resp., $H$). Let $f : G \to H$ be a bijection that Duplicator selects. If for some $i$, $\rk_{M_{i,G}}(g) \neq \rk_{M_{i,H}}(f(g))$, then Spoiler can win with $3$ pebbles and $O(\log n)$ rounds.
\end{lemma}

\begin{proof}
Let $M_{i, G}, M_{G}$ be the sets in $G$ as in Definition \ref{MaximalCentralizerDef}, and let $M_{i, H}, M_{H}$ be the corresponding sets in $H$. We show that $f(M_{i, G}) = M_{i, H}$ and $f(\langle M_{i,G}\rangle) = \langle M_{i,H} \rangle$. These statements imply that $f(M_{G}) = M_{H}$. The proof proceeds by induction over $i$, and within each $i$, we use the Rank Lemma~\ref{LemmaRank} applied to $M_i$-rank. Note that each $M_i$ is closed under taking inverses, since $C_G(g) = C_G(g^{-1})$. 

We first note that if $|C_{G}(g)| \neq |C_{H}(f(g))|$, then Duplicator may win with $2$ pebbles and $2$ rounds. Without loss of generality, suppose that $|C_{G}(g)| > |C_{H}(f(g))|$. Spoiler pebbles $g \mapsto f(g)$. Let $f' : G \to H$ be the bijection that Duplicator selects at the next round. Now there exists $x \in C_{G}(g)$ such that $f'(x) \not \in C_{H}(f(g))$. Spoiler pebbles $x \mapsto f'(x)$ and wins immediately.

Thus $M_{1,G}$ is identified by $(2,2)$-WL. By the Rank Lemma~\ref{LemmaRank} applied to $M_1$-rank, we get that $f(\langle M_{1,G} \rangle) = \langle M_{1,H} \rangle$ or Spoiler can win with $3$ pebbles in $O(\log n)$ rounds.

As Duplicator must select bijections $f : G \to H$ where $f(\langle M_{1,G} \rangle) = \langle M_{1,H} \rangle$, we may iterate on the above argument replacing $1$ with $i$, to obtain that $f(M_{i,G}) = M_{i,H}$ and $f(\langle M_{i,G} \rangle) = \langle M_{i,H} \rangle$. The result now follows by induction.
\end{proof}

\begin{definition}
Let $G = N_{1} \cdots N_{m}$ be the decomposition into non-Abelian components, and let $G = G_{1} \times \cdots \times G_{d}$ be an arbitrary direct decomposition. We say that $x \in G$ is \textit{full} for $(G_{j_{1}}, \ldots, G_{j_{r}})$, if 
\[
\{ i \in [m] : [x, N_{i}] \neq 1 \} = \bigcup_{\ell=1}^{r} I_{j_{\ell}},
\]

\noindent where the $I_{j_{\ell}}$ are as in \Lem{LemBSCanonicalDecomposition}(c). For all $x \in G$, define $C_{x} := \prod_{[x, N_{i}] = \{1\}} N_{i}$ and $N_{x} = \prod_{[x, N_{i}] \neq \{1\}} N_{i}.$
\end{definition}

We now recall some technical lemmas from \cite{BrachterSchweitzerWLLibrary}.

\begin{remark}[{\cite[Observation~6.22]{BrachterSchweitzerWLLibrary}}]
For an arbitrary collection of indices $J \subseteq [m]$, the group elements $x \in G$ that have $C_{x} = \prod_{i \in J} N_{i}$ are exactly those elements of the form $x = z \prod_{i \in J} n_{i}$ with $z \in Z(G)$ and $n_{i} \in N_{i} \setminus Z(G)$. In particular, full elements exist for every collection of non-Abelian direct factors and any direct decomposition, and they are exactly given by products over non-central elements from the corresponding non-Abelian components.
\end{remark}

\begin{lemma}[{\cite[Lemma~6.23]{BrachterSchweitzerWLLibrary}}] \label{BSLem623}
Let $G$ be non-Abelian, and let $G = G_{1} \times \cdots \times G_{d}$ be an indecompsable direct decomposition. For all $x \in G$, we have a central decomposition $G = C_{x}N_{x}$, with $Z(G) \leq C_{x} \cap N_{x}$. The decomposition is directly induced if and only if $x$ is full for a collection of direct factors of $G$.
\end{lemma}


\begin{lemma}[{Compare rounds cf. \cite[Lemma~6.24]{BrachterSchweitzerWLLibrary}}] \label{ModifiedLem624}
Let $G = G_{1} \times G_{2}$. For $k \geq 4, r \in \Omega(\log n)$, assume that $(k,r)$-WL Version II detects $G_{1}Z(G)$ and $G_{2}Z(G)$. Let $H$ be a group such that $(k,r)$-WL Version II does not distinguish $G$ and $H$. Then for $i \in \{1,2\}$, there exist subgroups $H_{i} \leq H$ such that $H = H_1 \times H_2$ and $(k,r)$-WL does not distinguish $G_{i}Z(G)$ and $H_{i}Z(H)$.
\end{lemma}

\begin{proof}
The proof is largely identical to that of \cite[Lemma~6.24]{BrachterSchweitzerWLLibrary}. We adapt their proof to control for rounds. 

As $(k,r)$-WL detects $G_{1}Z(G)$ and $G_{2}Z(G)$, we have that for any two bijections $f, f' : G \to H$ that $f(G_{i}Z(G)) = f'(G_{i}Z(G))$ for $i \in \{1,2\}$. It follows that there exist subgroups of $\widetilde{H_{i}} \leq H$ such that $f(G_{i}Z(G)) = \widetilde{H_{i}}$. As $Z(G) \leq G_{i}Z(G)$, we have necessarily that $Z(H) \leq \widetilde{H_{i}}$. Consider the decompositions $Z(G) = Z(G_{1}) \times Z(G_{2})$ and $G_{i}Z(G) = G_{i} \times Z(G_{i+1 \mod 2})$. By \Lem{BSLemma612}, we have that if $x$ splits from $Z(G)$, then $x$ also splits from $G_{1}Z(G)$ or $G_{2}Z(G)$. 

Write $\widetilde{H_{i}} = R_{i} \times B_{i}$, where $B_{i}$ is a maximal Abelian direct factor of $\widetilde{H_{i}}$.

\begin{quotation}
\noindent \textbf{Claim 1:} For all choices of $R_{i}, B_{i}$, it holds that $R_{1} \cap R_{2} = \{1\}$. Otherwise, Spoiler can win with $2$ additional pebbles and $2$ additional rounds.

\begin{proof}[Proof of Claim 1]
By assumption, $\widetilde{H_{1}} \cap \widetilde{H_{2}} = Z(H)$. So $R_{1} \cap R_{2} \leq Z(H)$. Suppose to the contrary that there exists $z \in R_{1} \cap Z_{2}$ such that $|z| = p$ for some prime $p$. Then there also exists a central $p$-element $w$ that splits from $Z(H)$ and where $z \in \langle w \rangle$ (for instance, we may take $w$ to be a root of $z^{p^{N}}$, where $N$ is the largest $p$-power order in the Abelian group $Z(H)$). Write $w = (r_{i}, b_{i})$ with respect to the chosen direct decomposition for $\widetilde{H_{i}}$.  As $z \in \langle w \rangle$, we have that $w^{m} = z \in R_{1} \cap R_{2}$. So $w^{m} \neq 1$. Furthermore, we may write $w^{m} = (r_{1}^{m}, 1) = (r_{2}^{m}, 1)$. As $w$ has $p$-power order, we have as well that $|b_{i}| < |r_{i}|$ for each $i \in \{1,2\}$. Now $w$ does not split from $\widetilde{H_{i}}$; otherwise, by \Lem{BSLemma612}, we would have that $r_{i}$ splits from $R_{i}$. However, neither $R_{1}$ nor $R_{2}$ admit Abelian direct factors.

It follows that $w$ splits from $Z(H)$, but not from $\widetilde{H_{1}}$ or $\widetilde{H_{2}}$. Such elements do not exist in $G_{1}Z(G)$ or $G_{2}Z(G)$. Thus, in this case, we have by \Lem{LemmaGeneralSplit} that Spoiler can win with $2$ additional pebbles and $2$ additional rounds.
\end{proof}
\end{quotation}

\noindent We next consider maximal Abelian direct factors $A \leq G$ and $B \leq H$. Write $H = R \times B$. By \Thm{IdentifyAbelianDirectFactor}, we may assume that $A \cong B$. We now argue that $R_{1}$ and $R_{2}$ can be chosen such that $R_{1}R_{2} \cap B = \{1\}$. For $i \in \{1,2\}$, we may write:
\[
\widetilde{H_{i}} = \langle (r_{1}, b_{1}), \ldots, (r_{t}, b_{t}) \rangle \leq R \times B.
\] 

As $B \leq \widetilde{H_{i}}$, we have that:
\[
\widetilde{H_{i}} = \langle (r_{1}, 1), (1, b_{1}), \ldots, (r_{t}, 1), (b_{t}, 1) \rangle = \langle (r_{1}, 1), \ldots, (r_{t}, 1)\rangle \times B.
\]

It follows that we may choose $R_{1}R_{2} \leq R$. By Claim 1, we have that $R_{1} \cap R_{2} = \{1\}$. So $R_{1}R_{2}B = R_{1} \times R_{2} \times B \leq H$. As $(k, r)$-WL fails to distinguish $G$ and $H$, we have necessarily that $|R_{1}| \cdot |R_{2}| \cdot |B| = |H|$. So in fact, $H = R_{1} \times R_{2} \times B$, which we may write as $(R_{1} \times B_{1}) \times (R_{2} \times B_{2})$, where $B_{i} \leq H_{i}$ are chosen such that $B = B_{1} \times B_{2}$ and $B_{i}$ is isomorphic to a maximal Abelian direct factor of $G_{i}$. Furthermore, we have that $R_{i}Z(H) = \widetilde{H_{i}}$, by construction. The result follows.
\end{proof}


\begin{lemma} \label{LemmaPreservesFullness}
Let $G = N_{1} \cdots N_{m}$ and $H = Q_{1} \cdots Q_{m}$ be the decompositions of $G$ and $H$ into non-Abelian components. Let $G = G_{1} \times \ldots \times G_{d}$ be a decomposition into indecomposable direct factors. Let $f : G \to H$ be the bijection that Duplicator selects. Let $k \geq 4, r \in \Omega(\log n)$. If $x \in G$ is full for $(G_{j_{1}}, \ldots, G_{j_{r}})$, but $f(x)$ is not full for a collection $(H_{j_{1}}, \ldots, H_{j_{r}})$ of indecomposable direct factors of $H$, then Spoiler may win with $5$ pebbles and $O(\log n)$ rounds.
\end{lemma}


\begin{proof}
Spoiler begins by pebbling $x \mapsto f(x)$. Let $f' : G \to H$ be the bijection Duplicator selects at the next round. By \Lem{LemBSCanonicalDecompositionA}, we may assume that $f'(N_{x}) = N_{f(x)}$ and $f'(C_{x}) = C_{f(x)}$, or Spoiler wins with $3$ pebbles and $O(\log n)$ rounds. So suppose that $x$ and $f(x)$ are not distinguished by $(k,r)$-WL. Then as the central decomposition $G = C_{x}N_{x}$ is directly induced, we have that by \Lem{ModifiedLem624}, the central decomposition $H = C_{f(x)}N_{f(x)}$ has to be directly induced or Spoiler can win with $4$ pebbles and $O(\log n)$ rounds. So by \Lem{BSLem623}, we have that $f(x)$ is full.

As Duplicator preserves $C_{x}$ and $N_{x}$, we obtain that if $x$ is full for a collection of $r$ direct factors, then so is $f(x)$. 
\end{proof}

\begin{corollary} \label{CorApproximateBelow}
Let $G = G_{1} \times \ldots \times G_{d}$ be a decomposition of $G$ into directly indecomposable factors. Let $H$ be arbitrary. Let $\mathcal{F}_{G}$ be the set of full elements for $G$, and define $\mathcal{F}_{H}$ analogously. If Duplicator does not select a bijection $f : G \to H$ satisfying:
\[
f\left( \bigcup_{g \in \mathcal{F}_{G}} N_{g} \right) = \bigcup_{h \in \mathcal{F}_{H}} N_{h},
\]

then Spoiler can win using $5$ pebbles and $O(\log n)$ rounds.
\end{corollary}

\begin{proof}
By \Lem{LemmaPreservesFullness}, we may assume that $f(\mathcal{F}_{G}) = \mathcal{F}_{H}$ (or Spoiler wins with $4$ pebbles and $O(\log n)$ rounds). Now suppose that for some $g \in G$ that there exists an $x \in N_{g}$ such that $f(x) \not \in N_{h}$ for any $h \in \mathcal{F}_{H}$. Spoiler pebbles $x \mapsto f(x)$. Let $f' : G \to H$ be the bijection Duplicator selects at the next round. Again, we may assume that $f(\mathcal{F}_{G}) = \mathcal{F}_{H}$ (or Spoiler wins). Spoiler now pebbles $g \mapsto f'(g)$. Now on any subsequent bijection, Duplicator cannot map $N_{g} \mapsto N_{f'(g)}$. So by \Lem{LemBSCanonicalDecompositionA}, Spoiler wins with $4$ additional pebbles and $O(\log n)$ rounds.
\end{proof}

\begin{theorem}
Let $k \geq 5, r \in \Omega(\log n)$. Let $G$ be a non-Abelian group, and let $G = G_{1} \times \ldots \times G_{d}$ be a decomposition into indecomposable direct factors. If $(k,r)$-WL Version II fails to distinguish $G$ and $H$, then there exist indecomposable direct factors $H_{i} \leq H$ such that $H = H_{1} \times \ldots \times H_{d}$ and $(k-1,r)$-WL Version II fails to distinguish $G_{i}$ and $H_{i}$ for all $i \in [d]$. Furthermore, $G$ and $H$ have isomorphic maximal Abelian direct factors and $(k,r)$-WL fails to distinguish $G_{i}Z(G)$ from $H_{i}Z(H)$.
\end{theorem}

\begin{proof}
Without loss of generality, we may assume that $H$ is non-Abelian as well. Let $f : G \to H$ be the bijection that Duplicator selects. By \Cor{CorApproximateBelow}, we may assume that Duplicator preserves the full elements (or Spoiler wins with $4$ pebbles and $O(\log n)$ rounds); that is, $f(\mathcal{F}_{G}) = \mathcal{F}_{H}$. It follows that $H$ must admit a decomposition $H = H_{1} \times \ldots \times H_{\ell}$, where the $H_{j}$ factors are directly indecomposable and $\mathcal{F}_{H} = \bigcup_{j} H_{j}Z(H) \subseteq H$, which we again note is indistinguishable from $\mathcal{F}_{G}$. Let $X_{G}$ be the non-commmuting graph of $G$, and let $X_{H}$ be the non-commuting graph of $H$. Recall from \cite[Proposition~2.1]{ABDOLLAHI2006468} that as $G, H$ are non-Abelian, $X_{G}$ and $X_{H}$ are connected.

As different direct factors centralize each other, we obtain that for each non-singleton connected component in $K$ of $X_{G}[\mathcal{F}_{G}]$ that there exists a unique indecomposable direct factor $G_{i}$ such that $K = G_{i}Z(G) \setminus Z(G)$. Thus, $G_{i}Z(G) = \langle K \rangle$. Again by \cite[Proposition~2.1]{ABDOLLAHI2006468}, all such non-Abelian direct factors appear in this way. 

We note that the claims in the preceeding paragraph applies to $H$ as well. So if $(k,r)$-WL Version II does not distinguish $G$ and $H$, there must exist a bijection between the connected components of $X_{G}[\mathcal{F}_{G}]$ and $X_{H}[\mathcal{F}_{H}]$. Namely, we may assume that $G$ and $H$ admit a decomposition into $\ell = d$ directly indecomposable factors, and that these subgroups are indistinguishable by $(k,r)$-WL. In particular, we have a correspondence (after an appropriate reordering of the factors) between $G_{i}Z(H)$ and $H_{i}Z(H)$, where $G_{i}Z(H)$ and $H_{i}Z(H)$ are not distinguished by $(k,r)$-WL. By \Lem{SemiAbelianDirectProduct}, we have that $(k,r)$-WL Version II does not distinguish $G_{i}$ from $H_{i}$. By \Thm{IdentifyAbelianDirectFactor}, $G$ and $H$ must have isomorphic maximal Abelian direct factors. So when $G_{i}, H_{i}$ are Abelian, we even have $G_{i} \cong H_{i}$.
\end{proof}





\section{Weisfeiler--Leman for Semisimple Groups}

In this section, we show that Weisfeiler--Leman can be fruitfully used as a tool to improve the parallel complexity of isomorphism testing of groups with no Abelian normal subgroups, also known as semisimple or Fitting-free groups. The main result of this section is:

\begin{theorem} \label{thm:ListSemisimpleIsomorphisms}
Let $G$ be a semisimple group, and let $H$ be arbitrary. We can test isomorphism between $G$ and $H$ using an $\textsf{SAC}$ circuit of depth $O(\log n)$ and size $n^{\Theta(\log \log n)}$. Furthermore, all such isomorphisms can be listed in this bound.
\end{theorem}

The previous best complexity upper bounds were $\mathsf{P}$ for testing isomorphism \cite{BCQ}, and $\mathsf{DTIME}(n^{O(\log \log n)})$ for listing isomorphisms \cite{BCGQ}.

We start with what we can observe from known results about direct products of simple groups. Brachter \& Schweitzer previously showed that $3$-WL Version II identifies direct products of finite simple groups. A closer analysis of their proofs \cite[Lemmas~5.20 \& 5.21]{BrachterSchweitzerWLLibrary} show that only $O(1)$ rounds are required. Thus, we obtain the following. 

\begin{corollary}[{cf. Brachter \& Schweitzer \cite[Lemmas~5.20 \& 5.21]{BrachterSchweitzerWLLibrary}}]
Isomorphism between a direct product of non-Abelian simple groups and an arbitrary group can be decided in $\mathsf{L}$.
\end{corollary}

Our parallel machinery also immediately lets us extend a similar result to direct products of \emph{almost} simple groups (a group $G$ is almost simple if there is a non-Abelian simple group $S$ such that $\Inn(S) \leq G \leq \Aut(S)$; equivalently, if $\text{Soc}(G)$ is non-Abelian simple).

\begin{corollary}
Isomorphism between a direct product of almost simple groups and an arbitrary group can be decided in $\mathsf{L}$. 
\end{corollary}

\begin{proof}
Because almost simple groups are 3-generated \cite{DVL}, they are identified by $(O(1), O(1))$-WL. By \Thm{ThmProduct}, direct products of almost simple groups are thus identified by $(O(1), O(\log n))$-WL. \Thm{CanonicalFormsComplexityWLII}(b) then gives both parts of the result.
\end{proof}

\subsection{Preliminaries}
We recall some facts about semisimple groups from \cite{BCGQ}. As a semisimple group $G$ has no Abelian normal subgroups, we have that $\text{Soc}(G)$ is the direct product of non-Abelian simple groups.  The conjugation action of $G$ on $\text{Soc}(G)$ permutes the direct factors of $\text{Soc}(G)$. So there exists a faithful permutation representation $\alpha : G \to G^{*} \leq \Aut(\text{Soc}(G))$. $G$ is determined by $\text{Soc}(G)$ and the action $\alpha$. Let $H$ be a semisimple group with the associated action $\beta : H \to \text{Aut}(\text{Soc}(H))$. We have that $G \cong H$ precisely if $\text{Soc}(G) \cong \text{Soc}(H)$ via an isomorphism that makes $\alpha$ equivalent to $\beta$. 

We now introduce the notion of permutational isomorphism, which is our notion of equivalence for $\alpha$ and $\beta$. Let $A$ and $B$ be finite sets, and let $\pi : A \to B$ be a bijection. For $\sigma \in \text{Sym}(A)$, let $\sigma^{\pi} \in \text{Sym}(B)$ be defined by $\sigma^{\pi} := \pi^{-1}\sigma \pi$. For a set $\Sigma \subseteq \text{Sym}(A)$, denote $\Sigma^{\pi} := \{ \sigma^{\pi} : \sigma \in \Sigma\}$. Let $K \leq \text{Sym}(A)$ and $L \leq \text{Sym}(B)$ be permutation groups. A bijection $\pi : A \to B$ is a \textit{permutational isomorphism} $K \to L$ if $K^{\pi} = L$.

The following lemma, applied with $R = \text{Soc}(G)$ and $S = \text{Soc}(H)$, precisely characterizes semisimple groups \cite{BCGQ}.      
 
\begin{lemma}[{\cite[Lemma 3.1]{BCGQ}}] \label{CharacterizeSemisimple}
Let $G$ and $H$ be groups, with $R \triangleleft G$ and $S \triangleleft H$ groups with trivial centralizers. Let $\alpha : G \to G^{*} \leq \Aut(R)$ and $\beta : H \to H^{*} \leq \Aut(S)$ be faithful permutation representations of $G$ and $H$ via the conjugation action on $R$ and $S$, respectively. Let $f : R \to S$ be an isomorphism. Then $f$ extends to an isomorphism $\hat{f} : G \to H$ if and only if $f$ is a permutational isomorphism between $G^{*}$ and $H^{*}$; and if so, $\hat{f} = \alpha f^{*} \beta^{-1}$, where $f^{*} :  G^{*} \to H^{*}$ is the isomorphism induced by $f$.
\end{lemma}

We also need the following standard group-theoretic lemmas. The first provides a key condition for identifying whether a non-Abelian simple group belongs in the socle. Namely, if $S_{1} \cong S_{2}$ are non-Abelian simple groups where $S_{1}$ is in the socle and $S_{2}$ is not in the socle, then the normal closures of $S_{1}$ and $S_{2}$ are non-isomorphic. In particular, the normal closure of $S_{1}$ is a direct product of non-Abelian simple groups, while the normal closure of $S_{2}$ is not a direct product of non-Abelian simple groups. We will apply this condition later when $S_{1}$ is a simple direct factor of $\text{Soc}(G)$; in which case, the normal closure of $S_{1}$ is of the form $S_{1}^{k}$. We include the proofs of these two lemmas for completeness.

\begin{lemma} \label{LemmaSocle}
Let $G$ be a finite semisimple group. A subgroup $S \leq G$ is contained in $\text{Soc}(G)$ if and only if the normal closure of $S$ is a direct product of nonabelian simple groups.
\end{lemma}

\begin{proof}
Let $N$ be the normal closure of $S$. Since the socle is normal in $G$ and $N$ is the smallest normal subgroup containing $S$, we have that $S$ is contained in $\text{Soc}(G)$ if and only if $N$ is. 

Suppose first that $S$ is contained in the socle. Since $\text{Soc}(G)$ is normal and contains $S$, by the definition of $N$ we have that $N \leq \text{Soc}(G)$. As $N$ is a normal subgroup of $G$, contained in $\text{Soc}(G)$, it is a direct product of minimal normal subgroups of $G$, each of which is a direct product of non-Abelian simple groups.

Conversely, suppose $N$ is a direct product of nonabelian simple groups. We proceed by induction on the size of $N$. If $N$ is minimal normal in $G$, then $N$ is contained in the socle by definition. If $N$ is not minimal normal, then it contains a proper subgroup $M \lneq N$ such that $M$ is normal in $G$, hence also $M \unlhd N$. However, as $N$ is a direct product of nonabelian simple groups $T_1, \dotsc, T_k$, the only subgroups of $N$ that are normal in $N$ are direct products of subsets of $\{T_1, \dotsc, T_k\}$, and all such normal subgroups have direct complements. Thus we may write $N = L \times M$ where both $L,M$ are nontrivial, hence strictly smaller than $N$, and both $L$ and $M$ are direct product of nonabelian simple groups. 

We now argue that $L$ must also be normal in $G$. Since conjugating $N$ by $g \in G$ is an automorphism of $N$, we have that $N = g L g^{-1} \times g M g^{-1}$. Since $M$ is normal in $G$, the second factor here is just $M$, so we have $N = gLg^{-1} \times M$. But since the direct complement of $M$ in $N$ is unique (since $N$ is a direct product of \emph{non-Abelian} simple groups), we must have $g L g^{-1} = L$. Thus $L$ is normal in $G$. 

By induction, both $L$ and $M$ are contained in $\text{Soc}(G)$, and thus so is $N$. We conclude since $S \leq N$.
\end{proof}

\begin{corollary} \label{CorSocleFactor}
Let $G$ be a finite semisimple group. A nonabelian simple subgroup $S \leq G$ is a direct factor of $\text{Soc}(G)$ if and only if its normal closure $N = ncl_G(S)$ is isomorphic to $S^k$ for some $k \geq 1$ and $S \unlhd N$.
\end{corollary}

\begin{proof}
Let $S$ be a nonabelian simple subgroup of $G$. If $S$ is a direct factor of $\text{Soc}(G)$, then $\text{Soc}(G) = S^k \times T$ for some $k \geq 1$ and some $T$; choose $T$ such that $k$ is maximal. Then the normal closure of $S$ is a minimal normal subgroup of $\text{Soc}(G)$ which contains $S$ as a normal subgroup. Since the normal subgroups of a direct product of nonabelian simple groups are precisely direct products of subsets of the factors, the normal closure of $S$ is some $S^{k'}$ for $1 \leq k' \leq k$.

Conversely, suppose the normal closure $N$ of $S$ is isomorphic to $S^k$ for some $k \geq 1$ and $S \unlhd N$. By \Lem{LemmaSocle}, $S$ is in $\text{Soc}(G)$, and thus so is $N$ (being the normal closure of a subgroup of the socle). Furthermore, as a normal subgroup of $G$ contained in $\text{Soc}(G)$, $N$ is a direct product of minimal normal subgroups and a direct factor of $\text{Soc}(G)$ (in fact it is minimal normal itself, but we haven't established that yet, nor will we need to). Since $S$ is a normal subgroup of $N$, and $N$ is a direct product of non-Abelian simple groups, $S$ is a direct factor of $N$. Since $N$ is a direct factor of $\text{Soc}(G)$, and $S$ is a direct factor of $N$, $S$ is a direct factor of $\text{Soc}(G)$. This completes the proof.
\end{proof}


\begin{lemma} \label{LemmaDirectProdSimple}
Let $S_1, \dotsc, S_k \leq G$ be nonabelian simple subgroups such that for all distinct $i,j \in [k]$ we have $[S_i, S_j] = 1$. Then $\langle S_1, \dotsc, S_k \rangle = S_1 S_2 \dotsb S_k = S_1 \times \dotsb \times S_k$.
\end{lemma}

\begin{proof}
By induction on $k$. The base case $k=1$ is vacuously true. Suppose $k \geq 2$ and that the result holds for $k-1$. Then $T := S_1 S_2 \dotsb S_{k-1} = S_1 \times \dotsb \times S_{k-1}$. Now, since $S_k$ commutes with each $S_i$, and they generate $T$, we have that $[S_k, T] = 1$. Hence $T$ is contained in the normalizer (or even the centralizer) of $S_k$, so $TS_k = S_kT = \langle T, S_k \rangle$, and $S_k$ and $T$ are normal subgroups of $TS_k$. As $TS_k = \langle T,S_k \rangle$ and $T,S_k$ are both normal subgroups of $TS_k$ with $[T, S_k] = 1$, we have that $TS_k$ is a central product of $T$ and $S_k$. As $Z(T) = Z(S_k)=1$, it is their direct product.
\end{proof}

\subsection{Groups without Abelian Normal Subgroups in Parallel}
Here we establish \Thm{thm:ListSemisimpleIsomorphisms}. We begin with the following.

\begin{proposition} \label{IdentifySemisimple}
Let $G$ be a semisimple group of order $n$, and let $H$ be an arbitrary group of order $n$. If $H$ is not semisimple, then $3$-WL will distinguish $G$ and $H$ in at most $3$ rounds.
\end{proposition}

\begin{proof}
Recall that a group is semisimple if and only if it contains no Abelian normal subgroups. As $H$ is not semisimple, $\text{Soc}(H) = A \times T$, where $A$ is the direct product of elementary Abelian groups and $T$ is a direct product of non-Abelian simple groups. We show that Spoiler can win using at most $4$ pebbles and $5$ rounds. Let $f : G \to H$ be the bijection that Duplicator selects. Let $a \in A$. So $\text{ncl}_{H}(a) \leq A$. Let $b := f^{-1}(a) \in G$, and let $B := \text{ncl}_{G}(b)$. As $G$ is semisimple, we have that $B$ is not Abelian. Spoiler begins by pebbling $b \mapsto a$.

So there exist $g_{1}, g_{2} \in G$ such that $g_{1}bg_{1}^{-1}$ and $g_{2}bg_{2}^{-1}$ do not commute (for $B$ is generated by $\{g b g^{-1} : g \in G\}$, and if they all commuted then $B$ would be Abelian). Let $f', f'' : G \to H$ be the bijections that Duplicator selects at the next two rounds. Spoiler pebbles $g_{1} \mapsto f'(g_{1})$ and $g_{2} \mapsto f''(g_{2})$ at the next two rounds. As $\ncl(a) = A$ is Abelian, $f'(g_{1})f(b)f'(g_{1})^{-1}$ and $f''(g_{2})f(b)f''(g_{2})^{-1}$ commute. Spoiler now wins.
\end{proof}
 
We now apply Lemma \ref{LemmaSocle} to show that Duplicator must map the direct factors of $\text{Soc}(G)$ to isomorphic direct factors of $\text{Soc}(H)$. 


\begin{lemma} \label{LemmaProdSimple}
Let $G,H$ be finite semisimple groups of order $n$. Let $\text{Fac}(\text{Soc}(G))$ denote the set of simple direct factors of $\text{Soc}(G)$. Let $S \in \text{Fac}(\text{Soc}(G))$ be a non-Abelian simple group. Let $a \in S$, and let $f : G \to H$ be the bijection that Duplicator selects. 
\begin{enumerate}[label=(\alph*)]
\item If $f(a)$ does not belong to some element of $\text{Fac}(\text{Soc}(H))$, or 
\item If there exists some $T \in \text{Fac}(\text{Soc}(H))$ such that $f(a) \in T$, but $S \not \cong T$,
\end{enumerate}


then Spoiler wins with at most $4$ pebbles and $5$ rounds.
\end{lemma}

\begin{proof}
Spoiler begins by pebbling $a \mapsto f(a)$. At the next two rounds, Spoiler pebbles generators $x, y$ for $S$. Let $f' : G \to H$ be the bijection Duplicator selects at the next round. Denote $T := \langle f'(x), f'(y) \rangle$. We note that if $T \not \cong S$ or $f(a) \not \in T$, then Spoiler wins. 

So suppose that $f(a) \in T$ and $T \cong S$. We have two cases.
\begin{itemize}
\item \textbf{Case 1:} Suppose first that $T$ does not belong to $\text{Soc}(H)$. As $S \triangleleft \text{Soc}(G)$, the normal closure $\text{ncl}(S)$ is minimal normal in $G$ \cite[Exercise 2.A.7]{Isaacs2008FiniteGT}. As $T$ is not even contained in $\text{Soc}(H)$, we have by Lemma \ref{LemmaSocle} that $\text{ncl}(T)$ is not a direct product of non-Abelian simple groups, so $\text{ncl}(S) \not\cong \text{ncl}(T)$. We note that $\text{ncl}(S) = \langle \{ gSg^{-1} : g \in G \} \rangle$.

As $\text{ncl}(T)$ is not isomorphic to a direct power of $S$, there is some conjugate $g S g^{-1} \neq S$ such that $f'(g)Tf'(g)^{-1}$ does not commute with $T$, by Lemma~\ref{LemmaDirectProdSimple}. Yet since $S \unlhd \text{Soc}(G)$, $gSg^{-1}$ and $S$ do commute. Spoiler moves the pebble pair from $a \mapsto f(a)$ and pebbles $g$ with $f'(g)$. Since Spoiler has now pebbled $x,y,g$ which generate $\langle S, gSg^{-1} \rangle = S \times gSg^{-1} \cong S \times S$ but the image is not isomorphic to $S \times S$, the map $(x,y,g) \mapsto (f'(x), f'(y), f'(g))$ does not extend to an isomorphism of $S \times T$. Spoiler now wins. In total, Spoiler used $3$ pebbles and $4$ rounds.

\item \textbf{Case 2:} Suppose instead that $T \leq \text{Soc}(H)$, but that $T$ is not normal in $\text{Soc}(H)$. As $T$ is not normal in $\text{Soc}(H)$, there exists $Q = \langle q_{1}, q_{2} \rangle \in \text{Fac}(\text{Soc}(H))$ such that $Q$ does not normalize $T$. At the next two rounds, Spoiler pebbles $q_{1}, q_{2}$, and their respective preimages, which we label $r_{1}, r_{2}$. When pebbling $r_{1} \mapsto q_{1}$, we may assume that Spoiler moves the pebble placed on $a \mapsto f(a)$. By Case 1, we may assume that $r_{1}, r_{2} \in \text{Soc}(G)$, or Spoiler wins with an additional $1$ pebble and $1$ round. Now as $S \trianglelefteq \text{Soc}(G)$, $\langle r_{1}, r_{2}\rangle$ normalizes $S$. However, $Q$ does not normalize $T$. So the pebbled map $(x, y, r_{1}, r_{2}) \mapsto (f'(x), f'(y), q_{1}, q_{2})$ does not extend to an isomorphism. Thus, Spoiler used $4$ pebbles and $5$ rounds.
\end{itemize}
\end{proof}

\begin{lemma} \label{IdentifyDirectFactors}
Let $G$ be a semisimple group. There is a logspace algorithm that decides, given $g_{1}, g_{2} \in G$, whether $\langle g_{1}, g_{2} \rangle \in \text{Fac}(\text{Soc}(G))$.
\end{lemma}

\begin{proof}
Using a membership test \cite{BarringtonMcKenzie, TangThesis}, we may enumerate the elements of $S := \langle g_{1}, g_{2} \rangle$ by a logspace transducer. We first check whether $S$ is simple. For each $g \in S$, we check whether $\ncl_{S}(g) = S$. This check is $\textsf{L}$-computable \cite[Thm.~7.3.3]{VijayaraghavanThesis}. 

It remains to check whether $S \in \text{Fac}(\text{Soc}(G))$. By \Cor{CorSocleFactor}, $S \in \text{Fac}(\text{Soc}(G))$ if and only if $N := \ncl_{G}(S) = S^{k}$ for some $k$ and $S \unlhd N$. As $S$ is simple, it suffices to check that each conjugate of $S$ is either (1) equal to $S$ or (2) intersects trivially with $S$ and commutes with $S$. For a given $g \in G$ and each $h \in S$, we may check whether $h \in gSg^{-1}$. If there exist non-trivial $h_{1}, h_{2} \in S$ such that $h_{1} \in gSg^{-1}$ and $h_{2} \not \in gSg^{-1}$, we return that $S \not \in \text{Fac}(\text{Soc}(G))$. Otherwise, we know that all conjugates of $S$ are either equal to $S$ or intersect $S$ trivially. Next we check that those conjugates that intersect $S$ trivially commute with $S$. For each $g \in G, h_1, h_2 \in S$ we check whether $g h_1 g^{-1} \in S$; if not, we check that $[gh_1 g^{-1}, h_2]=1$. If not, then we return that $S \not \in \text{Fac}(\text{Soc}(G))$. If all these tests pass, then $S$ is a direct factor of the socle. For both of these procedures, we only need to iterate over 3- and 4-tuples of elements of $G$ or $S$, so this entire procedure is $\textsf{L}$-computable. The result follows.
\end{proof}


\begin{lemma} \label{LemmaAC1Factors}
Let $G$ be a semisimple group. We can compute the direct factors of $\text{Soc}(G)$ using a  logspace transducer.
\end{lemma}

\begin{proof}
Using \Lem{IdentifyDirectFactors}, we may identify in $\textsf{L}$ the ordered pairs that generate direct factors of $\text{Soc}(G)$. Now for $x \in G$ and a pair $(g_{1}, g_{2})$ that generates a direct factor of $\text{Soc}(G)$, define an indicator $Y(x, g_{1}, g_{2}) = 1$ if and only if $x \in \langle g_{1}, g_{2} \rangle$. We may use a membership test \cite{BarringtonMcKenzie, TangThesis} to decide in $\textsf{L}$ whether $x \in \langle g_{1}, g_{2} \rangle$. Thus, we are able to write down the direct factors of $\text{Soc}(G)$ and their elements in $\textsf{L}$.
\end{proof}


We now prove \Thm{thm:ListSemisimpleIsomorphisms}

\begin{proof}[Proof of \Thm{thm:ListSemisimpleIsomorphisms}]
We first note that, by \Lem{LemmaProdSimple}, if $\text{Soc}(G) \not \cong \text{Soc}(H)$, then $(4, O(1))$-WL Version II will distinguish $G$ from $H$. For in this case, there is some simple normal factor $S \in \text{Fac}(\text{Soc}(G))$ such that there are more copies of $S$ in $\text{Fac}(\text{Soc}(G))$ than in $\text{Fac}(\text{Soc}(H))$. Thus under any bijection Duplicator selects, some element of $S$ must get mapped into a simple direct factor of $\text{Soc}(H)$ that is not isomorphic to $S$, and thus by \Lem{LemmaProdSimple}, Spoiler can win with 4 pebbles and 5 rounds.

So suppose $\text{Soc}(G) \cong \text{Soc}(H)$. By \Lem{LemmaAC1Factors}, in $\textsf{L}$ we may enumerate the non-Abelian simple direct factors of $\text{Soc}(G)$ and $\text{Soc}(H)$. Furthermore, we may decide in $\textsf{L}$---and therefore, $\textsf{SAC}^{1}$---with a membership test \cite{BarringtonMcKenzie, TangThesis} whether two non-Abelian simple direct factors of the socle are conjugate. Thus, in $\textsf{SAC}^{1}$, we may compute a decomposition $\text{Soc}(G)$ and $\text{Soc}(H)$ of the form $T_{1}^{t_{1}} \times \cdots \times T_{k}^{t_{k}}$, where each $T_{i}$ is non-Abelian simple and each $T_{i}^{t_{i}}$ is minimal normal.

There are $O(|S|^{2})$ automorphisms of each simple factor $|S|$, and so there are at most
\[
n^{2} k! \prod_{i=1}^{k} t_{i}!
\]
isomorphisms between $\text{Soc}(G)$ and $\text{Soc}(H)$. From \cite{BCGQ}, we note that this quantity is bounded by $n^{O(\log \log n)}$. (This is bound is tight, as in the case of the groups $A_{5}^{k}$.) Given a bijection $\psi : \text{Fac}(\text{Soc}(G)) \to \text{Fac}(\text{Soc}(H))$, we may in $\textsf{L}$ enumerate the $O(n^{2})$ isomorphisms between $\text{Fac}(\text{Soc}(G))$ and $\text{Fac}(\text{Soc}(H))$ respecting $\psi$ by fixing generators of each element $S \in \text{Fac}(\text{Soc}(G))$ and enumerating their possible images in $\psi(S)$.

We now turn to testing isomorphism of $G$ and $H$. To do so, we use the individualize and refine strategy. We individualize in $G$ arbitrary generators for each element of $\text{Fac}(\text{Soc}(G))$ (2 for each factor). Then for each configuration of generators for the elements of $\text{Fac}(\text{Soc}(H))$, we individualize those in such a way that respects $\psi$. Precisely, if $\psi(S) = T$ and $(g_{1}, g_{2})$ are individualized in $S$, then for the desired generators $(h_{1}, h_{2})$ of $T$, we individualize $h_{i}$ to receive the same color as $g_{i}$. Observe that in two more rounds, no two elements of $\text{Soc}(G)$ have the same color. Similarly, in two more rounds, no two elements of $\text{Soc}(H)$ have the same color. However, an element of $\text{Soc}(G)$ and an element of $\text{Soc}(H)$ may share the same color.

Suppose now that $G \not \cong H$. Let $f : G \to H$ be the bijection that Duplicator selects. As $G \not \cong H$, there exists $g \in G$ and $s \in \text{Soc}(G)$ such that $f(gsg^{-1}) \neq f(g)f(s)f(g^{-1})$. Spoiler pebbles $g$. Let $f' : G \to H$ be the bijection Duplicator selects at the next round. As no two elements of $\text{Soc}(G)$ have the same color and no two elements of $\text{Soc}(H)$ have the same color, we have that $f'(s) = f(s)$. Spoiler pebbles $s$ and wins. So after the individualization step, $(2,4)$-WL Version II will decide whether the given map extends to an isomorphism of $G \cong H$. Now $(2,4)$-WL Version II is $\textsf{L}$-computable, and so $\textsf{SAC}^{1}$ computable. As we have to test at most $n^{O(\log \log n)}$ isomorphisms of $\text{Soc}(G) \cong \text{Soc}(H)$, our circuit has size $n^{O(\log \log n)}$. The result now follows.
\end{proof}

\begin{remark}
Here, we use Weisfeiler--Leman to decide in $\textsf{L}$ whether a given isomorphism of $\text{Soc}(G) \cong \text{Soc}(H)$ extends to an isomorphism of $G \cong H$. This procedure was known to be polynomial-time computable via membership checking in the setting of permutation groups; the proof of \cite[Proposition~3.1]{BCGQ} cites \cite{FurstHopcroftLuks}. Furthermore, membership checking in the setting of permutation groups is known to be $\textsf{NC}$-computable \cite{BabaiLuksSeress}. The proof from \cite{BabaiLuksSeress} is quite involved; it effectively computes Schreier generators using  $O(\log n)$ iterations. Furthermore, multiplying a product of permutations is $\textsf{FL}$-complete \cite{COOK1987385}. Thus, it does not appear that membership testing in the permutation group is known to be even $\textsf{AC}^{1}$-computable. So already, our $\textsf{quasiSAC}^{1}$ bound is new. Furthermore, Weisfeiler--Leman provides a much simpler algorithm. We note, however, that Weisfeiler--Leman requires access to the multiplication table for the underlying group. Thus, this technique cannot be leveraged for more general membership testing in permutation groups.
\end{remark}

We also obtain the following corollary, which improves upon \cite[Corollary~4.4]{BCGQ} in the direction of parallel complexity.

\begin{corollary}
Let $G$ and $H$ be semisimple with $\text{Soc}(G) \cong \text{Soc}(H)$. If $\text{Soc}(G) \cong \text{Soc}(H)$ have $O(\log n / \log \log n)$ non-Abelian simple direct factors, then we can decide isomorphism between $G$ and $H$, and list all the isomorphisms between $G$ and $H$ in $\textsf{L}$.
\end{corollary}






\section{Count-Free Weisfeiler--Leman} \label{CountFreeWL}
In this section, we examine consequence for parallel complexity of the \emph{count-free} WL algorithm. Our first main result here is to show a $\Omega(\log |G|)$ lower bound (optimal, up to the constant factor) on count-free WL-dimension for identifying Abelian groups (\Thm{CountFreeAbelian}). Despite this result showing that count-free WL on its own is not useful for testing isomorphism of Abelian groups, we nonetheless use count-free WL for Abelian groups, in combination with a few other ideas, to get improved upper bounds on the parallel complexity of testing isomorphism (\Thm{ThmAbelian}) of Abelian groups. 

We begin by defining analogous pebble games and logics for the three count-free WL versions. Furthermore, we establish the equivalence of the three count-free WL versions up to $O(\log n)$ rounds. These results extend \cite[Section~3]{WLGroups} to the count-free setting.


\subsection{Equivalence Between Count-Free WL, Pebble Games, and Logics}
We define analogous pebble games for count-free WL Versions I-III. The count-free $(k+1)$-pebble game consists of two players: Spoiler and Duplicator, as well as $(k+1)$ pebble pairs $(p, p^{\prime})$. In Versions I and II, Spoiler wishes to show that the two groups $G$ and $H$ are not isomorphic; and in Version III, Spoiler wishes to show that the corresponding graphs $\Gamma_{G}, \Gamma_{H}$ are not isomorphic. Duplicator wishes to show that the two groups (Versions I and II) or two graphs (Version III) are isomorphic. Each round of the game proceeds as follows.
\begin{enumerate}
\item Spoiler picks up a pebble pair $(p_{i}, p_{i}^{\prime})$.
\item The winning condition is checked. This will be formalized later.
\item In Versions I and II, Spoiler places one of the pebbles on some group element (either $p_{i}$ on some element of $G$ or $p_{i}'$ on some element of $H$). In Version III, Spoiler places one of the pebbles on some vertex of one of the graphs (either $p_{i}$ on some vertex of $\Gamma_{G}$ or $p_{i}'$ on some element of $\Gamma_{H}$).
\item Duplicator places the other pebble on some element of the other group (Versions I and II) or some vertex of the other graph (Version III).
\end{enumerate}

Let $v_{1}, \ldots, v_{m}$ be the pebbled elements of $G$ (resp., $\Gamma_{G}$) at the end of step 1, and let $v_{1}^{\prime}, \ldots, v_{m}^{\prime}$ be the corresponding pebbled vertices of $H$ (resp., $\Gamma_{H}$). Spoiler wins precisely if the map $v_{\ell} \mapsto v_{\ell}^{\prime}$ does not extend to a marked equivalence in the appropriate version of WL. Duplicator wins otherwise. Spoiler wins, by definition, at round $0$ if $G$ and $H$ do not have the same number of elements. We note that $G$ and $H$ (resp., $\Gamma_{G}, \Gamma_{H}$) are not distinguished by the first $r$ rounds of $k$-WL if and only if Duplicator wins the first $r$ rounds of the $(k+1)$-pebble game. 

The count-free $r$-round, $k$-WL algorithm for graphs is equivalent to the $r$-round, $(k+1)$-pebble count-free pebble game \cite{CFI}. Thus, the count-free $r$-round, $k$-WL Version III algorithm for groups introduced in Brachter \& Schweitzer \cite{WLGroups} is equivalent to the $r$-round, $(k+1)$-pebble count-free pebble game on the graphs $\Gamma_G, \Gamma_H$ associated to the groups $G,H$. We establish the same equivalence for the count-free WL Versions I and II.

\begin{lemma}
Let $\overline{g} := (g_{1}, \ldots, g_{k}) \in G^{k}$ and $\overline{h} := (h_{1}, \ldots, h_{k}) \in H^{k}$. If the count-free $(k,r)$-WL distinguishes $\overline{g}$ and $\overline{h}$, then Spoiler can win in the count-free $(k+1)$-pebble game within $r$ moves on the initial configuration $(\overline{g}, \overline{h})$. (We use the same version of WL and the pebble game).
\end{lemma}

\begin{proof}
\noindent
\begin{itemize}
\item \textbf{Version I:} For $r = 0$, then $\overline{g}$ and $\overline{h}$ differ with respect to the Version I marked equivalence type. Fix $r > 0$. Suppose that $\chi_{r}(\overline{g}) \neq \chi_{r}(\overline{h})$. We have two cases. Suppose first that $\chi_{r-1}(\overline{g}) \neq \chi_{r-1}(\overline{h})$. Then by the inductive hypothesis, Spoiler can win in the $(k+1)$-pebble game using at most $r-1$ moves. 

Suppose instead that $\chi_{r-1}(\overline{g}) = \chi_{r-1}(\overline{h})$. So without loss of generality, there exists an $x \in G$ such that the color configuration $(\chi_{r-1}(\overline{g}(g_{1}/x)), \ldots, \chi_{r-1}(\overline{g}(g_{k}/x))$ does not appear amongst the colored $k$-tuples of $H$. Thus, for some $j \in [k]$ and all $y \in H$, $\chi_{r-1}(\overline{g}(g_{j}/x)) \neq \chi_{r-1}(\overline{h}(h_{j}/y))$. Spoiler moves pebble $p_{j}$ to $x$. By the inductive hypothesis, Spoiler wins with $r-1$ additional moves. 

\item \textbf{Version II:} We modify the Version I argument above to use the Version II marked equivalence type. Otherwise, the argument is identical.
\end{itemize}
\end{proof}


We now prove the converse.

\begin{lemma}
Let $\overline{g} := (g_{1}, \ldots, g_{k}) \in G^{k}$ and $\overline{h} := (h_{1}, \ldots, h_{k}) \in H^{k}$. Suppose that Spoiler can win in the count-free $(k+1)$-pebble game within $r$ moves on the initial configuration $(\overline{g}, \overline{h})$. Then the count-free $(k,r)$-WL distinguishes $\overline{g}$ and $\overline{h}$. (We use the same version of WL and the pebble game).
\end{lemma}

\begin{proof}
\noindent
\begin{itemize}
\item \textbf{Version I:} If $r = 0$, then the initial configuration is already a winning one for Spoiler. By definition, $\overline{g}, \overline{h}$ receive different colorings at the initial round of WL. Let $r > 0$, and suppose that Spoiler wins at round $r > 1$ of the pebble game. Suppose that at round $r$, Spoiler moved the $j$th pebble from $g_{j}$ to $x$. Suppose Duplicator responded by moving the corresponding pebble from $h_{j}$ to $y$. Then the map $(g_{1}, \ldots, g_{j-1}, x, g_{j+1}, \ldots, g_{k}) \mapsto (h_{1}, \ldots, h_{j-1}, y, h_{j+1}, \ldots, h_{k})$ is not a marked equivalence. By the inductive hypothesis, $\overline{g}(g_{j}/x)$ and $\overline{h}(h_{j}/x)$ receive different colors at round $r-1$ of $k$-WL. As Spoiler had a winning strategy by moving the $j$th pebble from $g_{j} \mapsto x$, we have that for any $y \in H$, $\chi_{r-1}(\overline{g}(g_{j}/x)) \neq \chi_{r-1}(\overline{h}(h_{j}/))$. By the definition of the WL refinement, it follows that $\chi_{r}(\overline{g}) \neq \chi_{r}(\overline{h})$. The result follows.

\item \textbf{Version II:} We modify the Version I argument above to use the Version II marked equivalence type. Otherwise, the argument is identical.
\end{itemize}
\end{proof}

\begin{lemma} \label{CountFreePebbleGame}
Let $G$ and $H$ be groups of order $n$. Consider the count-free $k$-pebble game on the graphs $\Gamma_{G}$ and $\Gamma_{H}$. If $k \geq 6$ and one of the following happens:
\begin{enumerate}[label=(\alph*)]
\item Spoiler places a pebble $p$ on a vertex corresponding to a group element $g \in G$ and Duplicator places the corresponding pebble $p'$ on a vertex $v$ that does not correspond to a group element of $H$,

\item Suppose that there is a pebble pair $(p, p')$ for which pebble $p$ is on some vertex of $M(g_{1}, g_{2})$ that is not a group element and $p'$ is on some vertex of $M(h_{1}, h_{2})$ that is not a group element. Write $g_{3} := g_{1}g_{2}$ and $h_{3} := h_{1}h_{2}$. If Spoiler places a pebble on $g_{i}$ ($i = 1, 2, 3$) and Duplicator does not respond by pebbling $h_{i}$ (or vice-versa),

\item the map induced by the group elements pebbled or implicitly pebbled by $k-2$ pebbles does not extend to an isomorphism between the corresponding generated subgroups,
\end{enumerate}	

then Spoiler can win with $2$ additional pebbles and $O(\log n)$ additional rounds.
\end{lemma}

\begin{proof}
We have the following.
\begin{enumerate}[label=(\alph*)]

\item The vertices that do not correspond to group elements have degree at most $3$. So Spoiler can win with $4$ additional pebbles by pebbling the neighbors of the vertex corresponding to the group element.

\item We note that if pebble $p$ is not on the same type of vertex (i.e., type $a, b, c,$ or $d$, as in Figure \ref{MultiplicationGadget}) as pebble $p'$, then Spoiler wins in $O(1)$ more rounds with at most $4$ more pebbles and $4$ more rounds, as either the vertices or their neighbors have different degrees. 

So suppose now that $p$ and $p'$ are on the same type of vertex. Now without loss of generality, suppose that pebble $q$ is placed on $g_{i}$ for some $i = 1, 2, 3$ and the corresponding pebble $q'$ is not placed on $h_{i}$. Observe that for each non-group-element vertex in a gadget $M(g_1, g_2)$, the distances to the three group-element vertices of that gadget are all distinct, and any path from a vertex not in $M(g_1, g_2)$ to a non-group-element vertex in $M(g_1, g_2)$ must go through one of the group element vertices $g_1, g_2, g_1g_2$. Thus, there is some $k$ such that the vertex pebbled by $p$ is connected to $g_i$ by a path made up of exactly $k$ non-group element vertices, but the same is not true for any path from the vertex pebbled by $p'$ to that pebbled by $q'$. 
Using a third pebble pair, Spoiler can explore the path from $p$ to $g_i$ and win, using at most $7$ additional rounds (as a multiplication gadget has $7$ vertices).


\item Suppose that the map $f : g_{i} \mapsto h_{i}$ for all $i \in [k-2]$ does not extend to an isomorphism of $\langle g_{1}, \ldots, g_{k-2} \rangle$ and $\langle h_{1}, \ldots, h_{k-2}\rangle$. Let $\hat{f} : \langle g_{1}, \ldots, g_{k-2} \rangle \to \langle h_{1}, \ldots, h_{k-2} \rangle$ be an extension of $f$. As $\hat{f}$ is not an isomorphism, there exists a smallest word $\omega = g_{i_{1}} \cdots g_{i_{j}}$ over $g_{1}, \ldots, g_{k-2}$ such that $\hat{f}(\omega) \neq \hat{f}(g_{i_{1}}) \cdots \hat{f}(g_{i_{j}})$. By minimality, we have that 
\[
\hat{f}(g_{i_{1}}) \cdots \hat{f}(g_{i_{j}}) = \hat{f}(g_{i_{1}}) \hat{f}(g_{i_{2}} \cdots g_{i_{j}}) \neq \hat{f}(\omega).
\]

Spoiler pebbles $\omega$ in $\Gamma_{G}$, and Duplicator responds by pebbling $\omega'$ in $\Gamma_{H}$. Denote $\omega[x, \ldots, y] := g_{i_{x}} \cdots g_{i_{y}}$. At the next round, Spoiler implicitly pebbles $(\omega[1, \ldots, \lfloor j/2 \rfloor], \omega[\lfloor j/2 \rfloor + 1, \ldots, j]).$ Spoiler responds by pebbling a pair $(c, d)$. By part (b), we may assume that $cd = \omega'$; otherwise, Spoiler can win by reusing the pebble pair on $\omega, \omega'$ and exploring the multiplication gadget $M(\omega[1, \ldots, \lfloor j/2 \rfloor], \omega[\lfloor j/2 \rfloor + 1, \ldots, j]).$ So now either:
\begin{align*}
&c \neq h_{i_{1}} \cdots h_{i_{\lfloor j/2 \rfloor}}, \text{ or } \\
&d \neq h_{i_{\lfloor j/2 \rfloor +1}} \cdots h_{i_{j}}.
\end{align*}

Without loss of generality, suppose that:
\[
c \neq h_{i_{1}} \cdots h_{i_{\lfloor j/2 \rfloor}}.
\]

Spoiler iterates on the above strategy, starting from $c$ rather than $\omega$. We eventually reach the case of part (b), for a total of $\log_{2} j + O(1) \leq \log_{2} n + O(1)$ rounds. To see that two additional pebbles are required, after implicitly pebbling the multiplication gadget, Spoiler may move reuse the pebble from the previous round. The result now follows.
\end{enumerate}
\end{proof}


\subsection{Logics}

We recall the central aspects of first-order logic. We have a countable set of variables $\{x_{1}, x_{2}, \ldots, \}$. Formulas are defined inductively. As our basis, $x_{i} = x_{j}$ is a formula for all pairs of variables. Now if $\varphi$ is a formula, then so are the following: $\varphi \land \varphi, \varphi \vee \varphi, \neg{\varphi}, \exists{x_{i}} \, \varphi,$ and $\forall{x_{i}} \, \varphi$. In order to define logics on groups, it is necessary to define a relation that relates the group multiplication. We recall the two different logics introduced by Brachter \& Schweitzer \cite{WLGroups}.
\begin{itemize}
\item \textbf{Version I:} We add a ternary relation $R$ where $R(x_{i}, x_{j}, x_{\ell}) = 1$ if and only if $x_{i}x_{j} = x_{\ell}$ in the group. In keeping with the conventions of \cite{CFI}, we refer to the first-order logic with relation $R$ as $\mathcal{L}_{I}$ and its $k$-variable fragment as $\mathcal{L}_{I}^{k}$. We refer to the logic $\mathcal{C}_{I}$ as the logic obtained by adding counting quantifiers $\exists^{\geq n} x_{i} \, \varphi$ and $\exists{!n} \, \varphi$ as $\mathcal{C}_{I}$ and its $k$-variable fragment as $\mathcal{C}_{I}^{k}$. 

\item \textbf{Version II:} We add a relation $R$, defined as follows. Let $w \in (\{x_{i_{1}}, \ldots, x_{i_{t}}\} \cup \{ x_{i_{1}}^{-1}, \ldots, x_{i_{t}}^{-1}\})^{*}$. We have that $R(x_{i_{1}}, \ldots, x_{i_{t}}; w) = 1$ if and only if multiplying the group elements according to $w$ yields the identity. For instance, $R(a, b; [a,b])$ holds precisely if $a, b$ commute. Again, in keeping with the conventions of \cite{CFI}, we refer to the first-order logic with relation $R$ as $\mathcal{L}_{II}$ and its $k$-variable fragment as $\mathcal{L}_{II}^{k}$. We refer to the logic $\mathcal{C}_{II}$ as the logic obtained by adding counting quantifiers $\exists^{\geq n} x_{i} \, \varphi$ and $\exists{!n} \, \varphi$ as $\mathcal{C}_{I}$ and its $k$-variable fragment as $\mathcal{C}_{II}^{k}$. 
\end{itemize}


\begin{remark}
Brachter \& Schweitzer \cite{WLGroups} refer to $\mathcal{L}_{I}$ and $\mathcal{L}_{II}$ as the logics with counting quantifiers. We instead adhere to the conventions in \cite{CFI}.
\end{remark}

Brachter \& Schweitzer \cite[Lemma~3.6]{WLGroups} showed that for $J \in \{I, II\}$ two $k$-tuples $\overline{g}, \overline{h}$ receive a different initial color under $k$-WL Version $J$ if and only if there is a quantifier-free formula in $\mathcal{C}_{J}$ that distinguishes $\overline{g}, \overline{h}$. As such formulas do not use any quantifiers, $\overline{g}, \overline{h}$ receive a different initial color under $k$-WL Version $J$ if and only if there is a quantifier-free formula in $\mathcal{L}_{J}$ that distinguishes $\overline{g}, \overline{h}$. Now the equivalence between the $(k+1)$-pebble, $r$-round Version $J$ count-free pebble game and the $(k+1)$-varible, quantifier-depth $r$ fragment of $\mathcal{L}_{J}$ follows identically from the argument as in the case of graphs \cite{CFI}. We record this with the following theorem.

\begin{theorem}
Let $G$ and $H$ be groups of order $n$, and let $J \in \{I, II\}$. We have that $(k,r)$-WL Version $J$ distinguishes $G$ from $H$ if and only if there exists a sentence $\varphi \in \mathcal{L}_{J}$ that uses at most $k+1$ variables and quantifier depth $r$, such that $\varphi$ holds on one group but not the other.
\end{theorem}






\subsection{Equivalence of Count-Free WL Versions}

We show that the three count-free WL Versions are equivalent, up to a factor of $2$ in the dimension and up to a tradeoff of $O(\log n)$ additional rounds.

\begin{definition}
Let $k, k' \geq 2, r, r' \geq 1$, and $J, J' \in \{I, II, III\}$. We say that $(k, r)$-WL$_{J} \preceq (k', r')$-WL$_{J'}$ if whenever $(k,r)$-WL$_{J}$ distinguishes groups $G$ and $H$, then $(k', r')$-WL$_{J'}$ also distinguishes $G$ and $H$.
\end{definition}

\begin{theorem} \label{thm:ParallelWLTradeoffCountFree}
Fix $k \geq 2$ and $r \geq 1$. In the count-free setting, we have the following:
\begin{enumerate}[label=(\alph*)]
\item $(k,r)$-WL$_{I} \preceq (k,r)$-WL$_{II}$,
\item $(k,r)$-WL$_{II} \preceq (\lceil k/2 \rceil + 2, 3r + O(\log n))$-WL$_{III}$,
\item $(\lceil k/2 \rceil + 2, 3r + O(\log n))$-WL$_{III} \preceq (k+5, 6r + O(\log n))$-WL$_{I}$.
\end{enumerate}
\end{theorem}


\noindent \\ We first note that count-free $(k,r)$-WL$_{II}$ can simulate each step of $(k,r)$-WL$_{I}$. Thus, it remains to prove \Thm{thm:ParallelWLTradeoffCountFree}(b)-(c). We do so with a series of lemmas.



\begin{lemma}
Let $G$ and $H$ be groups of order $n$. Suppose that the count-free $(k,r)$-WL Version II  distinguishes $G$ and $H$. Then the count-free $(\lceil k/2 \rceil + 2, 3r + O(\log n))$-WL Version III algorithm distinguishes $G$ and $H$.
\end{lemma}

\begin{proof}
We adapt the strategy of \cite[Lemma~3.11]{WLGroups} to the count-free setting and control for rounds. Suppose that Spoiler has a winning strategy in the $r$-round Version II $(k+1)$-pebble game. Let $g_{1}, \ldots, g_{r}$ be the sequence of group elements that Spoiler pebbles. Suppose that at round $1 \leq i \leq r$ of the Version II game that Spoiler introduces a new pebble. If there are an even number of group elements pebbled; then in the Version III game, Spoiler pebbles the group element vertex $g_{i}$. If instead there are an odd number of group elements pebbled; then in the Version III game, Spoiler implicitly pebbles $(g_{i}, g_{i+1})$ and reuses the pebble on $g_{i}$ at the next round.

Suppose that Spoiler instead moves a pebble at round $i$ of the Version II game. If the corresponding pebble in the Version III game is on a group element vertex, then this is treated identically as in the case when a new pebble is introduced. Suppose instead the corresponding pebble in the Version III game is on a multiplication gadget vertex $M(a, b)$ and in the Version II game, Spoiler moves the pebble from $b$. In this case in the Version III game, Spoiler introduces a new pebble onto $g_{i}$, and then moves the pebble from $M(a, b)$ to a non-group element vertex of $M(a, g_{i})$. At the next round, Spoiler reuses the pebble on $g_{i}$. 

We now argue that, without loss of generality, we may assume that the configuration of pebbled group elements at the end of at most $3r$ rounds in the Version III game is the same configuration at the end of round $r$ of the Version II game. Suppose at the end of round $r$ of the Version II game that Duplicator has pebbled $(h_{1}, \ldots, h_{k})$, and suppose that at the end of round $3r$ of the count-free pebble game that Duplicator has (implicitly) pebbled $(h_{1}', \ldots, h_{k}')$. By \Lem{CountFreePebbleGame}(a), if a pebble $p_{i}$ belongs to a group element (respectively, multiplication gadget) vertex and $p_{i}'$ does not belong to a group element (respectively, multiplication gadget) vertex, then Spoiler can win with $2$ pebbles and $O(1)$ rounds. So we may assume at the end of round $3r$ of the Version III game that Duplicator has (implicitly) pebbled $k$ group elements.

Now suppose for a contradiction that Duplicator wins with this strategy in the Version III game, even with $2$ additional pebbles and $O(\log n)$ additional rounds. Then by \Lem{LemBS}(c), the map $(g_{1}, \ldots, g_{k}) \mapsto (h_{1}', \ldots, h_{k}')$ extends to an isomorphism of the subgroups $\langle g_{1}, \ldots, g_{k} \rangle$ and $\langle h_{1}', \ldots, h_{k}' \rangle$. So in the Version II game, Duplicator could have won by pebbling $(h_{1}', \ldots, h_{k}')$ rather than $(h_{1}, \ldots, h_{k})$, contradicting the assumption that Spoiler wins at round $r$ of the Version II pebble game. Thus, we may assume at the end of round $r$ of the Version III game that $(h_{1}, \ldots, h_{k}) = (h_{1}', \ldots, h_{k}')$. 

As Spoiler wins at the end of round $r$ at the Version II game, we have that the induced map on the configurations does not extend to an isomorphism. So by \Lem{CountFreePebbleGame}(c), Spoiler wins in the Version III game with $2$ additional pebbles and $O(\log n)$ additional rounds, as desired.
\end{proof}



\begin{lemma}
Let $G$ and $H$ be groups of order $n$. Suppose that the count-free $(k,r)$-WL Version III  distinguishes $G$ and $H$. Then the count-free $2k+1$-WL Version I algorithm distinguishes $G$ and $H$ in at most $2r$ rounds.
\end{lemma}

\begin{proof}
We adapt the strategy of \cite[Lemma~3.12]{WLGroups} to the count-free setting and control for rounds. Suppose that at round $0 \leq i \leq r$ of the Version III pebble game, that Spoiler pebbles the group element vertex $g_{i}$. Then in the Version I game, Spoiler may pebble $g_{i}$. Suppose instead in the Version III game that Spoiler implicitly pebbles $M(x_{1}, x_{2})$, and Duplicator responds by implicitly pebbling $M(y_{1}, y_{2})$. We simulate this step in two rounds of the Version I game. At the first stage, Spoiler pebbles $x_{1}$. Duplicator responds by pebbling some group element $y_{1}'$. At the next stage, Spoiler pebbles $x_{2}$, and Duplicator responds by pebbling $y_{2}'$. Observe that at most $2$ rounds of the Version I game are required to simulate $1$ round of the Version III game.

Now suppose at round $r$ of the Version III game that Duplicator has pebbled $(h_{1}, \ldots, h_{d})$, where due to implicit pebbling, $d \leq 2k$. Suppose that at round $2r$ of the Version I game that Duplicator has pebbled $(h_{1}', \ldots, h_{d}')$. Now suppose for a contradiction that Duplicator wins at round $2r$ of the Version I game.  Let $\Gamma_{G}'$ be the induced subgraph $\Gamma_{G}[\{g_{1}, \ldots, g_{d}\}]$ together with the multiplication gadgets $M(g_{i}, g_{j})$ for all $i, j \in [d]$ where $g_{i}g_{j} \in \{ g_{1}, \ldots, g_{d}\}$. Define $\Gamma_{H}'$ analogously for $\{ h_{1}', \ldots, h_{d}'\}$. Consider the map $\varphi : V(\Gamma_{G}') \to V(\Gamma_{H}')$ induced by $(g_{1}, \ldots, g_{d}) \mapsto (h_{1}', \ldots, h_{d}')$. By the definition of the Version I winning condition, the map $(g_{1}, \ldots, g_{d}) \mapsto (h_{1}', \ldots, h_{d}')$ respects multiplication. Thus, $\varphi$ will be a graph isomorphism, as multiplicativity can be expressed equivalently in terms of mapping the multiplication gadgets accordingly. It follows that Duplicator could have won in the Version III pebble game by (implicitly) pebbling $(h_{1}', \ldots, h_{d}')$ instead of $(h_{1}, \ldots, h_{d})$, contradicting the assumption that Spoiler wins in the count-free $(k+1)$-pebble, $r$-round Version III game. The result now follows.
\end{proof}





\subsection{Count-Free WL and Abelian Groups}
We now turn to showing that the count-free WL Version II algorithm fails to yield a polynomial-time isomorphism test for even Abelian groups.

\begin{theorem} \label{CountFreeAbelian}
For $n \geq 5$, let $G_{n} := (\mathbb{Z}/2\mathbb{Z})^{n} \times (\mathbb{Z}/4\mathbb{Z})^{n}$ and $H_{n} := (\mathbb{Z}/2\mathbb{Z})^{n-2} \times (\mathbb{Z}/4\mathbb{Z})^{n+1}$. The $n/4$-dimensional count-free WL Version II algorithm does not distinguish $G_{n}$ from $H_{n}$.
\end{theorem}

\begin{proof}
The proof is by induction on the number of pebbles. For our first pebble, Spoiler may pebble one element in $G_{n}$, which generate one of the following subgroups: $\{1\}, \mathbb{Z}/2\mathbb{Z},$ or $\mathbb{Z}/4\mathbb{Z}$. For each of these options, Duplicator may respond in kind.

Now fix $1 \leq k \leq n/4$. Suppose that Duplicator has a winning strategy with $k$ pebbles. In particular, we suppose that pebble pairs $(p_{1}, p_{1}^{\prime}), \ldots, (p_{k}, p_{k}^{\prime})$ have been placed on the board, and that the map $p_{i} \mapsto p_{i}^{\prime}$ for all $i \in [k]$ extends to a marked isomorphism on a subgroup of the form $(\mathbb{Z}/2\mathbb{Z})^{a} \times (\mathbb{Z}/4\mathbb{Z})^{b}$. Furthermore, suppose that $0 \leq a_{1} \leq a$ of the $\mathbb{Z}/2\mathbb{Z}$ direct factors of $\langle p_{1}, \ldots, p_{k} \rangle$ are contained in copies of $\mathbb{Z}/4\mathbb{Z}$ in $G_{n}$. Duplicator will maintain the invariant that the same number of copies of the $\mathbb{Z}/2\mathbb{Z}$ direct factors of $\langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$ are contained in copies of $\mathbb{Z}/4\mathbb{Z}$ in $H_{n}$.


As Duplicator had a winning strategy in the $k$-pebble game, it is not to Spoiler's advantage to move pebbles $p_{1}, \ldots, p_{k}$. Thus, Spoiler picks up a new pebble $p_{k+1}$. Spoiler may pebble one additional element $G_{n}$. Now if the element Spoiler pebbles belongs to $\langle p_{1}, \ldots, p_{k} \rangle$; then as the map $p_{i} \mapsto p_{i}^{\prime}$ for all $i \in [k]$ extends to a marked isomorphism, Duplicator may respond by pebbling the corresponding element in $\langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$. 

We may now assume that Spoiler does not pebble any element in $\langle p_{1}, \ldots, p_{k} \rangle$. Spoiler may pebble one additional element. We have the following cases.
\begin{itemize}
\item \textbf{Case 1:} As $k \leq n/4$, if Spoiler pebbles an element $g_{i}$ generating $\mathbb{Z}/2\mathbb{Z}$, then Duplicator may respond in kind. We note that any copy of $\mathbb{Z}/2\mathbb{Z}$ that is pebbled and does not belong to $\langle p_{1}, \ldots, p_{k} \rangle$ is a direct complement to $\langle p_{1}, \ldots, p_{k} \rangle$ (in the sense that they commute and intersect trivially---they will not generate the whole group). Similarly, any copy of $\mathbb{Z}/2\mathbb{Z}$ that is pebbled and does not belong to $\langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$ is a direct complement to $\langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$. Furthermore, as $k \leq n/4$, we may assume that Duplicator pebbles a copy of $\mathbb{Z}/2\mathbb{Z}$ that is contained within a copy of $\mathbb{Z}/4\mathbb{Z}$ in $H_{n}$ if and only if Spoiler pebbles a copy of $\mathbb{Z}/2\mathbb{Z}$ that is contained within a copy of $\mathbb{Z}/4\mathbb{Z}$ in $G_{n}$.

\item \textbf{Case 2:} We now consider the case in which Spoiler pebbles an element $g_{1}$ generating a copy of $\mathbb{Z}/4\mathbb{Z}$. We consider the following subcases.
\begin{itemize}
\item \textbf{Subcase 2(a):} As $k \leq n/4$, there exist copies of $\mathbb{Z}/4\mathbb{Z}$ in $G_{n}$ that intersect trivially (and thus, are direct complements) with $\langle p_{1}, \ldots, p_{k} \rangle$; and similarly, there exist copies of $\mathbb{Z}/4\mathbb{Z}$ that intersect trivially (and thus, are direct complements) with $\langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$. So if $\langle g_{1} \rangle$ forms a direct complement with $\langle p_{1}, \ldots, p_{k} \rangle$, then Duplicator may respond by pebbling an element $h_{1}$ that generates a copy of $\mathbb{Z}/4\mathbb{Z}$ which is a direct complement with $\langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$.

\item \textbf{Subcase 2(b):} Suppose instead that $\langle g_{1} \rangle \cong \mathbb{Z}/4\mathbb{Z}$ intersects properly and non-trivially with $\langle p_{1}, \ldots, p_{k}\rangle$. In this case, $\langle g_{1} \rangle$ shares a copy of $\mathbb{Z}/2\mathbb{Z}$ with $\langle p_{1}, \ldots, p_{k} \rangle$. This yields two additional subcases.

\begin{itemize}
\item \textbf{Subcase 2(b).i:} Suppose first that this copy of $\mathbb{Z}/2\mathbb{Z}$ is contained within a copy of $\mathbb{Z}/4\mathbb{Z} \leq \langle p_{1}, \ldots, p_{k} \rangle$. By the inductive hypothesis, both $\langle p_{1}, \ldots, p_{k} \rangle$ and $\langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$ have $a_{1}$ copies of $\mathbb{Z}/2\mathbb{Z}$ that are contained in copies of $\mathbb{Z}/4\mathbb{Z}$ within $G_{n}$ and $H_{n}$ respectively. Using this fact, together with the fact that $k \leq n/4$, we have that Duplicator may respond by pebbling an element $h_{1}$ generating a copy of $\mathbb{Z}/4\mathbb{Z}$, where $\langle h_{1} \rangle \cap \langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$ is a copy of $\mathbb{Z}/2\mathbb{Z}$ that is contained within a copy of $\mathbb{Z}/4\mathbb{Z} \leq \langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$.

\item \textbf{Subcase 2(b).ii:} Suppose instead that this copy of $\mathbb{Z}/2\mathbb{Z}$ is contained within a copy of $\mathbb{Z}/4\mathbb{Z} \not \leq \langle p_{1}, \ldots, p_{k} \rangle$. By the inductive hypothesis, both $\langle p_{1}, \ldots, p_{k} \rangle$ and $\langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$ have $a_{1}$ copies of $\mathbb{Z}/2\mathbb{Z}$ that are contained in copies of $\mathbb{Z}/4\mathbb{Z}$ within $G_{n}$ and $H_{n}$ respectively. Using this fact, together with the fact that $k \leq n/4$, we have that Duplicator may respond by pebbling an element $h_{1}$ generating a copy of $\mathbb{Z}/4\mathbb{Z}$, where $\langle h_{1} \rangle \cap \langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$ is a copy of $\mathbb{Z}/2\mathbb{Z}$ that is not contained within a copy of $\mathbb{Z}/4\mathbb{Z} \leq \langle p_{1}^{\prime}, \ldots, p_{k}^{\prime} \rangle$.
\end{itemize}
\end{itemize}
\end{itemize}

Thus, in all cases, Duplicator has a winning strategy at round $k+1$. The result now follows by induction.
\end{proof}



\begin{remark}
\Thm{CountFreeAbelian} shows that count-free WL fails to serve as a polynomial-time (or even $|G|^{o(\log |G|)}$) isomorphism test for Abelian groups. In particular, by \Thm{thm:ParallelWLTradeoffCountFree}, our lower-bound holds (up to a constant factor in the number of pebbles) for all three versions of WL. As the $n/4$-dimensional count-free WL algorithm fails to distinguish $G_{n}$ and $H_{n}$, we also obtain an $\Omega(\log(|G_{n}|))$ lower bound on the quantifier rank of any $\textsf{FO}$ formula identifying $G_{n}$. In particular, this suggests that $\algprobm{GpI}$ is not in $\textsf{FO}(\poly \log \log n)$, even for Abelian groups. As $\textsf{FO}(\poly \log \log n)$ cannot compute $\algprobm{Parity}$ \cite{Smolensky87algebraicmethods}, this suggests that counting is necessary to solve \algprobm{GpI}. This is particularly interesting, as $\algprobm{Parity}$ is not $\textsf{AC}^{0}$-reducible to $\algprobm{GpI}$ \cite{ChattopadhyayToranWagner}.
\end{remark}


While count-free WL is unable to distinguish Abelian groups, the multiset of colors computed actually provides enough information to do so. Barrington, Kadau, Lange, \& McKenzie \cite{BKLM} previously showed that order-finding is $\textsf{FOLL}$-computable. Our next result (\Prop{CountFreeOrder}) shows that the count-free Weisfeiler--Leman effectively implements this strategy. 

\begin{lemma} \label{LemmaCountFreeExponent}
Let $G,H$ be groups of order $n$. Suppose in the count-free WL-III game, pebbles have already been placed on $g \mapsto h$ and $g^i \mapsto x$ with $x \neq h^i$. Then Spoiler can win with $O(1)$ additional pebbles in $O(\log \log i)$ rounds.
\end{lemma}

\begin{proof}
By induction on $i$. If $i=0$ the result follows from the fact that the identity is the unique element such that the gadget $M(1,1)$ has all three of its group element vertices the same and \Lem{CountFreePebbleGame}(b). If $i=1$, the result follows immediately from the winning condition of the game. So we now suppose $i > 1$, and that the result is true for all smaller exponents, say in $\leq c \log \log i'$ rounds for all $i' < i$.

The structure of the argument is as follows. If $i$ is not a power of $2$, we show how to cut the number of 1s in the binary expansion of $i$ by half using $O(1)$ rounds and only $O(1)$ pebbles that may be reused. Since the number of 1s in the binary expansion of $i$ is at most $\log_2 i$, and we cut this number in half each time, this takes only $O(\log \log i)$ rounds (and $O(1)$ pebbles) before $i$ has just one 1 in its binary expansion, that is, $i$ is a power of $2$. Once $i$ is a power of 2, we will show how to cut $\log_2 i$ in half using $O(1)$ rounds and $O(1)$ pebbles that may be reused. This takes only $O(\log \log i)$ rounds (and $O(1)$ pebbles) before getting down to the base case above. Concatenating these two strategies uses only $O(1)$ pebbles and $O(\log \log i)$ rounds. Now to the details.

If $i$ is not a power of $2$, we will show how cut the number of 1s in the binary expansion of $i$ in half. Write $i=j+k$ where $j,k$ each have at most half as many 1s in their binary expansion as $i$ does (rounded up). (Examine the binary expansion $i_\ell i_{\ell-1} \dotsb i_0$ and finding an index $z$ such that half the ones are on either side of $z$. Then let $j$ have binary expansion $i_\ell i_{\ell-1} \dotsb i_z 0 0 \dotsc 0$ and let $k$ have binary expansion $i_{z-1} i_{z-2} \dotsb i_0$.) Spoiler implicitly pebbles $(g^j, g^k)$. Duplicator responds by implicitly pebbling a pair $(a,b)$. If $ab \neq x$, then we have a pebble on a non-group-element vertex of $M(g^j,g^k)$ as well as on its group element vertex $g^{j+k}=g^i$. But the corresponding pebbles are on $M(a,b)$ and $x$ which differs from $ab$, so Spoiler wins by \Lem{CountFreePebbleGame}(b). Thus we may now assume $ab=x$.

Since $x \neq h^i$, we necessarily have $\{a,b\} \neq \{h^j, h^k\}$. Without loss of generality, suppose $a \notin \{h^j, h^k\}$. Spoiler now picks up the pebble on $g^i$ and places it on $g^j$ instead. Because of the implicit pebble mapping $M(g^j, g^k) \mapsto M(a,b)$, Duplicator must respond by placing the pebble on $a$ or Spoiler can win by \Lem{CountFreePebbleGame}(b). At this point, Spoiler can reuse the implicit pebble on $M(g^j, g^k)$ and the pebble on $g^i$, and we are now in a situation where $g \mapsto h$ and $g^j \mapsto a \neq h^j$ are pebbled, and $j$ has at most half as many 1s in its binary expansion as $i$ did. (So there are only two pebbles that can't be re-used, which is precisely the number we started with.) The cost to get here was $O(1)$ rounds and no non-reusable pebbles.

After that has been iterated $\log \log i$ times, we come to the case where $i$ is a power of 2. We will show how to reduce to a case where $\log_2 i$ has been cut in half. Write $i=jk$ with $jk$ powers of $2$ such that $\log_2 j, \log_2 k \leq \lceil \frac{\log_2 i}{2}\rceil$ (if $i=2^z$, let $j=2^{\lceil z/2 \rceil}, k=2^{z-\lceil z/2 \rceil}$). Note that  we have $g^i = (g^j)^k$. Spoiler now pebbles $g^j$, and Duplicator responds by pebbling some $a$. If $a \neq h^j$, then Spoiler can re-use the pebble from $g^i$, and we now have $g \mapsto h, g^j \mapsto a \neq h^j$ pebbled with $\log_2 j \leq \lceil (1/2)\log_2 i \rceil$. This took $O(1)$ rounds and no non-reusable pebbles. On the other hand, if $a = h^j$, then we have $a^k = h^{jk} = h^i \neq x$. Spoiler may now reuse the pebble on $g \mapsto h$, and we are now in a situation where $g^j \mapsto a$ and $(g^j)^k \mapsto x \neq a^k$, just as we started, and with $\log_2 k \leq \lceil(1/2) \log_2 i \rceil$. As in the other case, this took $O(1)$ rounds and no non-reusable pebbles. This completes the proof.
\end{proof}

\begin{proposition}[Order finding in WL-III] \label{CountFreeOrder}
Let $G$ be a group. Let $g, h \in G$ such that $|g| \neq |h|$. The count-free $(O(1), O(\log \log n))$-WL Version III distinguishes $g$ and $h$.
\end{proposition}

\begin{proof}
We use the pebble game characterization, starting from the initial configuration $( (g), (h))$. We first note that if $g = 1$ and $h \neq 1$, that Spoiler implicitly pebbles the multiplication gadget $M(1, 1)$. This is the unique multiplication gadget where all three group element vertices are the same. Regardless of what Duplicator pebbles, we have by \Lem{CountFreePebbleGame} that Spoiler can win with $O(1)$ additional pebbles and $O(1)$ additional rounds.So now suppose that $g \neq 1$ and $h \neq 1$. 

Without loss of generality suppose $|g| < |h|$. Note that $g \mapsto h$ has already been pebbled by assumption. Spoiler now pebbles $1$. By the same argument as above, Duplicator must respond by pebbling $1$. But we have $g^i = 1$ and by assumption $h^i \neq 1$. Thus, by \Lem{LemmaCountFreeExponent}, Spoiler can now win with $O(1)$ pebbles in $O(\log \log |g|) \leq O(\log \log n)$ rounds.
\end{proof}

As finite simple groups are uniquely identified amongst all groups by their order and the set of orders of their elements \cite{SimpleOrder}, we obtain the following immediate corollary.

\begin{corollary}
If $G$ is a finite simple group, then $G$ is identified by the count-free $(O(1), O(\log \log n))$-WL.
\end{corollary}

We also obtain an improved upper bound on the parallel complexity of Abelian Group Isomorphism:

\begin{theorem} \label{ThmAbelian}
$\algprobm{GpI}$ for Abelian groups is in $\beta_{1}\textsf{MAC}^{0}(\textsf{FOLL})$.
\end{theorem}

Here, $\beta_1 \mathsf{MAC}^0(\mathsf{FOLL})$ denotes the class of languages decidable by a (uniform) family of circuits that have $O(\log n)$ nondeterministic input bits, are of depth $O(\log \log n)$, have gates of unbounded fan-in, and the only gate that is not an $\textsf{And}$, $\textsf{Or}$, or $\textsf{Not}$ gate is the output gate, which is a $\textsf{Majority}$ gate of unbounded fan-in. Note that, by simulating the $\poly(n)$ possibilities for the nondeterministic bits, $\beta_1 \mathsf{MAC}^0(\mathsf{FOLL})$ is contained in $\mathsf{TC}^0(\mathsf{FOLL})$, at the expense of using $\poly(n)$ \textsf{Majority} gates. Thus, our result improves on the prior upper bound of $\mathsf{TC}^0(\mathsf{FOLL})$ \cite{ChattopadhyayToranWagner}.

\Thm{ThmAbelian} is an example of the strategy of using \emph{count-free} WL, followed by a limited amount of counting afterwards. (We contrast this with the parallel implementation of the classical (counting) WL algorithm, which---for fixed $k$---uses a polynomial number of $\textsf{Majority}$ gates at each iteration \cite{GroheVerbitsky}.) After the fact, we realized this same bound could be achieved by existing techniques; we include both proofs to highlight an example of how WL was used in the discovery process.

\begin{proof}[Proof using Weisfeiler--Leman]
Let $G$ be Abelian, and let $H$ be an arbitrary group such that $G \not \cong H$. Suppose first that $H$ is not Abelian. We show that count-free $(O(1), O(1))$-WL can distinguish $G$ from $H$. Suppose first that $H$ is not Abelian. Spoiler implicitly pebbles a pair of elements $(x, y)$ in $H$ that do not commute. $H$ responds by pebbling $(u, v) \in G$. At the next round, Spoiler implicitly pebbles $(v, u)$. Regardless of what Duplicator pebbles, we have by \Lem{CountFreePebbleGame}(b) that Spoiler wins with $O(1)$ additional pebbles and $O(1)$ additional rounds.

Suppose now that $H$ is Abelian. We run the count-free $(O(1), O(\log \log n))$-WL using the parallel WL implementation due to Grohe \& Verbitsky. As $G$ and $H$ are non-isomorphic Abelian groups, they have different order multisets. In particular, there exists a color class of greater multiplicity in $G$ than in $H$. By \Prop{CountFreeOrder}, two elements with different orders receive different colors. We use a $\beta_{1}\textsf{MAC}^{0}$ circuit to distinguish $G$ from $H$. Using $O(\log n)$ non-deterministic bits, we  guess the color class $C$ where the multiplicity differs. At each iteration, the parallel WL implementation due to Grohe \& Verbitsky records indicators as to whether two $k$-tuples receive the same color. As we have already run the count-free WL algorithm, we may in $\textsf{AC}^{0}$ decide whether two $k$-tuples have the same color. For each $k$-tuple of  $V(\Gamma_{G})^{k}$ having color class $C$, we feed a $1$ to the $\textsf{Majority}$ gate. For each $k$-tuple of $V(\Gamma_{H})^{k}$ having color class $C$, we feed a $0$ to the $\textsf{Majority}$ gate. The $\textsf{Majority}$ gate outputs a $1$ if and only if there are strictly more $1$'s than $0$'s. The result now follows.
\end{proof}

\begin{proof}[Alternative proof using prior techniques, that we only realized after discovering the WL proof]
This proof follows the strategy of Chattopadhyay, Tor\'an, \& Wagner \cite{ChattopadhyayToranWagner}, realizing that their use of many threshold gates can be replaced by $O(\log n)$ nondeterministic bits and a single threshold gate. 

Compute the multiset of orders in $\mathsf{FOLL}$ \cite[Prop.~3.1]{BKLM}, guess the order $k$ such that $G$ has more elements of order $k$ than $H$ does. Use a single $\textsf{Majority}$ gate to compare those counts.
\end{proof}


\section{Conclusion}

We combined the parallel WL implementation of Grohe \& Verbitsky \cite{GroheVerbitsky} with the WL for groups algorithms due to Brachter \& Schweitzer \cite{WLGroups} to obtain an efficient parallel canonization procedure for several families of groups, including: (i) coprime extensions $H \ltimes N$ where $N$ is Abelian and $H$ is $O(1)$-generated, and (ii) direct products, where WL can efficiently identify the indecomposable direct factors. 

We also showed that the individualize-and-refine paradigm allows us to list all isomorphisms of semisimple groups with an $\textsf{AC}$ circuit of depth $O(\log n)$ size $n^{O(\log \log n)}$. Prior to our paper, no parallel bound was known. And in light of the fact that multiplying permutations is $\textsf{FL}$-complete \cite{COOK1987385}, it is not clear that the techniques of Babai, Luks, \& Seress \cite{BabaiLuksSeress} can yield circuit depth $o(\log^{2} n)$.

Finally, we showed that $\Omega(\log(n))$-dimensional count-free WL is required to identify Abelian groups. It follows that count-free WL fails to serve as a polynomial-time isomorphism test even for Abelian groups. Nonetheless, count-free WL distinguishes group elements of different orders. We leveraged this fact to obtain a new $\beta_{1}\textsf{MAC}^{0}(\textsf{FOLL})$ upper bound on isomorphism testing of Abelian groups.

Our work leaves several directions for further research that we believe are approachable and interesting.

\begin{question} \label{Question1}
Show that coprime extensions of the form $H \ltimes N$ with both $H,N$ Abelian have constant WL-dimension (the WL analogue of \cite{QST11}). More generally, a WL analogue of Babai--Qiao \cite{BQ} would be to show that when $|H|,|N|$ are coprime and $N$ is Abelian, the WL dimension of $H \ltimes N$ is no more than that of $H$ (or the maximum of that of $H$ and a constant independent of $N,H$). 
\end{question}


\begin{question}
Is the WL dimension of semisimple groups bounded? 
\end{question}

It would be of interest to address this question even in the non-permuting case when $G = \text{PKer}(G)$. Alternatively, establish an upper bound of $O(\log \log n)$ for the WL dimension of semisimple groups. These questions would form the basis of a WL analogue of \cite{BCGQ}, without needing individualize-and-refine. 



In general, if an uncolored class of graphs is identified by WL, then so is the corresponding class of colored graphs. So if constant-dimensional WL identifies a class of graphs, it may readily be extended to an efficient canonization procedure (c.f., \cite{grohe2019canonisation}). In the case of groups, it is not clear whether WL easily identifies colored variants. To this end, we ask the following.

\begin{question}
Does constant-dimensional Weisfeiler--Leman identify every colored Abelian group?
\end{question}

In instances where running constant-dimensional WL for a polylogarithmic number of rounds suffices to identify a class of colored groups, we may combine the parallel WL implementation of Grohe \& Verbitsky \cite{GroheVerbitsky}, the WL canonization procedure for graphs (c.f., \cite{grohe2019canonisation}), and the generator enumeration procedure to obtain efficient parallel canonization. For full details, see Appendix \ref{ParallelCanonization}.

For the classes of groups we have studied, when we have been able to give an $O(1)$ bound on their WL-dimension, we also get an $O(\log n)$ bound on the number of rounds needed. The dimension bound alone puts the problem into $\cc{P}$, while the bound on rounds puts it into $\cc{TC}^{1}$. A priori, these two should be distinct. For example, in the case of graphs, Kiefer \& McKay \cite{KieferMcKay} have shown that there are graphs for which color refinement takes $n-1$ rounds to stabilize.

\begin{question}
Is there a family of groups identified by $O(1)$-WL but requiring $\omega(\log n)$ rounds? 
\end{question}

We also wish to highlight a question that essentially goes back to \cite{ChattopadhyayToranWagner}, who showed that \algprobm{GpI} cannot be hard under $\cc{AC}^0$ reductions for any class containing \algprobm{Parity}. In Theorem \ref{CountFreeAbelian}, we showed that count-free WL requires dimension $\geq \Omega(\log(n))$ to identify even Abelian groups. This shows that this particular, natural method does not put \algprobm{GpI} into $\cc{FO}(\poly \log \log n)$, though it does not actually prove $\algprobm{GpI} \notin \cc{FO}(\poly \log \log n)$, since we cannot rule out clever bit manipulations of the Cayley (multiplication) tables. While we think the latter lower bound would  be of significant interest, we think even the following question is interesting:

\begin{question}
Show that $\algprobm{GpI}$ does not belong to (uniform) $\cc{AC}^0$.
\end{question}




