# On the Descriptive Complexity of Groups without Abelian Normal Subgroups
(Extended Abstract)

Joshua A. Grochow Department of Computer Science University of Colorado
Boulder, CO USADepartment of Mathematics University of Colorado Boulder, CO
USA<EMAIL_ADDRESS>Department of Computer Science, College of
Charleston, SC USA Michael Levet Department of Computer Science, College of
Charleston, SC USA<EMAIL_ADDRESS>
###### Abstract

In this paper, we explore the descriptive complexity theory of finite groups
by examining the power of the second Ehrenfeucht–Fraïssé bijective pebble game
in Hella’s (Ann. Pure Appl. Log., 1989) hierarchy. This is a
Spoiler–Duplicator game in which Spoiler can place up to two pebbles each
round. While it trivially solves graph isomorphism, it may be nontrivial for
finite groups, and other ternary relational structures. We first provide a
novel generalization of Weisfeiler–Leman (WL) coloring, which we call 2-ary
WL. We then show that the 2-ary WL is equivalent to the second
Ehrenfeucht–Fraïssé bijective pebble game in Hella’s hierarchy.

Our main result is that, in the pebble game characterization, only $O(1)$
pebbles and $O(1)$ rounds are sufficient to identify all groups without
Abelian normal subgroups (a class of groups for which isomorphism testing is
known to be in $\mathsf{P}$; Babai, Codenotti, & Qiao, ICALP 2012). In
particular, we show that within the first few rounds, Spoiler can force
Duplicator to select an isomorphism between two such groups at each subsequent
round. By Hella’s results (_ibid._), this is equivalent to saying that these
groups are identified by formulas in first-order logic with generalized 2-ary
quantifiers, using only $O(1)$ variables and $O(1)$ quantifier depth.

##  1 Introduction

Descriptive complexity theory studies the relationship between the complexity
of describing a given problem in some logic, and the complexity of solving the
problem by an algorithm. When the problems involved are isomorphism problems,
Immerman and Lander [45] showed that complexity of a logical sentence
describing the isomorphism type of a graph was essentially the same as the
Weisfeiler–Leman coloring dimension of that graph, and the complexity of an
Ehrenfeucht–Fraïssé pebble game (see also [18]).

It is a well-known open question whether there is a logic that exactly
captures the complexity class P on unordered (unlabeled) structures; on
ordered structures such a logic was given by Immerman [44] and Vardi [68]. The
difference between these two settings is essentially the Graph Canonization
problem, whose solution allows one to turn an unordered graph into an ordered
graph in an isomorphism-preserving way.

One natural approach in trying to capture P on unordered structures is thus to
attempt to extend first-order logic FO by generalized quantifiers (c.f.,
Mostowski [61] and Lindstrom [58]) in the hopes that the augmented logics can
characterize finite graphs up to isomorphism, thus reducing the unordered case
to the previously solved ordered case. A now-classical approach, initiated by
Immerman [44], was to augment fixed-point logic with counting quantifiers,
which can be analyzed in terms of an equivalence induced by (variable
confined) fragments of first-order logic with counting. However, Cai, Fürer, &
Immerman [18] showed that $\textsf{FO}+\textsf{LFP}$ plus counting does not
capture P on finite graphs. More generally, Flum & Grohe have characterized
when FO plus counting captures P on unordered structures [27].

The approach of Cai, Fürer, & Immerman (ibid., see also [45]) was to prove a
three-way equivalence: between (1) counting logics, (2) the higher-dimensional
Weisfeiler–Leman coloring procedure, and (3) Ehrenfeucht–Fraïssé pebble games.
Ehrenfeucht–Fraïssé pebble games [25, 28] have long been an important tool in
proving the inexpressibility of certain properties in various logics; in this
case, they used such games to show that the logics could not express the
difference between certain pairs of non-isomorphic graphs. Consequently, Cai,
Fürer, & Immerman ruled out the Weisfeiler–Leman algorithm as a polynomial-
time isomorphism test for graphs, which resolved a long-standing open question
in isomorphism testing. Nonetheless, the Weisfeiler–Leman coloring procedure
is a key subroutine in many algorithms for Graph Isomorphism, including
Babai’s quasi-polynomial-time algorithm [5]. It is thus interesting to study
its properties and its distinguishing power.

While the result of Cai, Fürer, & Immerman ruled out Weisfeiler–Leman as a
polynomial-time isomorphism test for graphs, for _groups_ it remains an
interesting open question. The general WL procedure for groups was introduced
by Brachter & Schweitzer [13] and has been studied in several papers since
then [14, 31]. Outside the scope of WL, it is known that Group Isomorphism is
$\textsf{AC}^{0}$-reducible to Graph Isomorphism, and there is no
$\textsf{AC}^{0}$ reduction in the opposite direction [20]. For this and other
reasons, group isomorphism is believed to be the easier of the two problems,
so it is possible that WL—and more generally, tools from descriptive
complexity—could yield stronger results for groups than for graphs.

On graphs, which are binary relational structures, if Spoiler is allowed to
pebble two elements per turn, then Spoiler can win on any pair of non-
isomorphic graphs. However, groups are ternary relational structures (the
relation is $\\{(a,b,c):ab=c\\}$), so such a game may yield nontrivial
insights into the descriptive complexity of finite groups. Hella [42, 43]
introduced such games in a more general context, and showed that allowing
Spoiler to pebble $q$ elements per round corresponded to the generalized
$q$-ary quantifiers of Mostowski [61] and Lindstrom [58]. When $q=1$, Hella
shows that this pebble game is equivalent in power to the FO plus counting
logics mentioned above. Our focus in this paper is to study the power of the
$q=2$-ary game for identifying finite groups.

Main Results. In this paper, we initiate the study of Hella’s $2$-ary
Ehrenfeucht–Fraïssé-style pebble game, in the setting of groups. Our main
result is that this pebble game efficiently characterizes isomorphism in a
class of groups for which isomorphism testing is known to be in $\mathsf{P}$,
but only by quite a nontrivial algorithm (see remark below). The full version
of this paper appears on arXiv [30].

######  Theorem 1.1.

Let $G$ be a group with no Abelian normal subgroups (a.k.a. Fitting-free or
semisimple), and let $H$ be arbitrary. If $G\not\cong H$, then Spoiler has a
winning strategy in the Ehrenfeucht–Fraïssé game at the second level of
Hella’s hierarchy, using $9$ pebbles and $O(1)$ rounds.

In proving Thm. 1.1, we show that with the use of only a few pebbles, Spoiler
can effectively force Duplicator to select an isomorphism of $G$ and $H$. We
contrast this with the setting of Weisfeiler–Leman (which is equivalent to the
$1$-ary pebble game), for which the best upper bound we have on the WL-
dimension is the trivial bound of $\log n$. Furthermore, we do not have any
lower bounds on the WL-dimension for semisimple groups.

######  Remark 1.2.

Every group $G$ can be written as an extension of its solvable radical
$\operatorname{Rad}(G)$ by the quotient $G/\operatorname{Rad}(G)$, which does
not have Abelian normal subgroups. As such, the latter class of groups is
quite natural, both group-theoretically and computationally. Computationally,
it has been used in algorithms for general finite groups both in theory (e.g.,
[6, 7]) and in practice (e.g., [19]). Isomorphism testing in this family of
groups can be solved efficiently in practice [19], and is known to be in
$\mathsf{P}$ through a series of two papers [8, 9].

In Section 3 we also complete the picture by giving a Weisfeiler–Leman-style
coloring procedure and showing that it corresponds precisely to Hella’s
$q$-ary pebble games and $q$-ary generalized Lindstrom quantifiers [58]. When
the groups are given by their multiplication tables, this procedure runs in
time $n^{\Theta(\log^{2}n)}$ by reduction to Graph Isomorphism. We note that
Hella’s results deal with infinitary logics [42, 43]. However, as we are
dealing with finite groups, the infinitary quantifiers and connectives are not
necessary (see the discussion in [43], right above Theorem 5.3).

Further Related Work. Despite the fact that Weisfeiler–Leman is insufficient
to place Graph Isomorphism (GI) into PTIME, it remains an active area of
research. For instance, Weisfeiler–Leman is a key subroutine in Babai’s
quasipolynomial-time GI algorithm [5]. Furthermore, Weisfeiler–Leman has led
to advances in simultaneously developing both efficient isomorphism tests and
the descriptive complexity theory for finite graphs- see for instance, [33,
39, 50, 51, 35, 37, 36, 52, 2, 3, 65]. Weisfeiler–Leman also has close
connections to the Sherali–Adams hierarchy in linear programming [38].

The complexity of the Group Isomorphism (GpI) problem is a well-known open
question. In the Cayley (multiplication) table model, GpI belongs to
$\textsf{NP}\cap\textsf{coAM}$. The generator-enumerator algorithm, attributed
to Tarjan in 1978 [60], 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$. This
bound has escaped largely unscathed: Rosenbaum [64] (see [56, Sec. 2.2])
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., [12, 26, 11, 19]) still results in an
$n^{\Theta(\log n)}$-time algorithm in the general case (see [71, Page 2]). 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 [48, 69, 66], direct product decompositions
[70, 49], groups with no Abelian normal subgroups [8, 9], coprime and tame
group extensions [55, 63, 10, 32], low-genus $p$-groups and their quotients
[57, 16], Hamiltonian groups [21], and groups of almost all orders [24].

Key motivation for GpI is due to its close relation to GI. In the Cayley
(verbose) model, GpI reduces to GI [72], while GI reduces to the succinct GpI
problem [41, 59] (recently simplified [40]). In light of Babai’s breakthrough
result that GI is quasipolynomial-time solvable [5], GpI in the Cayley model
is a key barrier to improving the complexity of GI. Both verbose GpI and GI
are considered to be candidate NP-intermediate problems, that is, problems
that belong to NP, but are neither in P nor NP-complete [54]. There is
considerable evidence suggesting that GI is not NP-complete [67, 17, 46, 5,
53, 4]. As verbose GpI reduces to GI, this evidence also suggests that GpI is
not NP-complete. It is also known that GI is strictly harder than GpI under
$\textsf{AC}^{0}$ reductions [20].

While the descriptive complexity of graphs has been extensively studied, the
work on the descriptive complexity of groups is scant compared to the
algorithmic literature on Group Isomorphism (GpI). There has been work
relating first order logics and groups [62], as well as work examining the
descriptive complexity of finite abelian groups [29]. Recently, Brachter &
Schweitzer [13] introduced three variants of Weisfeiler–Leman for groups,
including corresponding logics and pebble games. These pebble games correspond
to the first level of Hella’s hierarchy [42, 43]. In particular, Brachter &
Schweitzer showed that $3$-dimensional Weisfeiler–Leman can distinguish
$p$-groups arising from the CFI graphs [18] via Mekler’s construction [59],
suggesting that $\textsf{FO}+\textsf{LFP}+\textsf{C}$ may indeed capture PTIME
on groups. Determining whether even $o(\log n)$-dimensional Weisfeiler–Leman
can resolve GpI is an open question.

The use on Weisfeiler–Leman for groups is quite new. To the best of our
knowledge, using Weisfeiler–Leman for Group Isomorphism testing was first
attempted by Brooksbank, Grochow, Li, Qiao, & Wilson [15]. Brachter &
Schweitzer [13] subsequently introduced three variants of Weisfeiler–Leman for
groups that more closely resemble that of graphs. In particular, Brachter &
Schweitzer [13] characterized their algorithms in terms of logics and
Ehrenfeucht–Fraïssé pebble games. The relationship between the works of
Brachter & Schweitzer and Brooksbank, Grochow, Li, Qiao, & Wilson [15] is an
interesting question.

In subsequent work, Brachter & Schweitzer [14] further developed the
descriptive complexity of finite groups. They showed in particular that low-
dimensional Weisfeiler–Leman can detect key group-theoretic invariants such as
composition series, radicals, and quotient structure. Furthermore, they also
showed that Weisfeiler–Leman can identify direct products in polynomial-time,
provided it can also identify the indecomposable direct factors in polynomial-
time. Grochow & Levet [31] extended this result to show that Weisfeiler–Leman
can compute direct products in parallel, provided it can identify each of the
indecomposable direct factors in parallel. Additionally, Grochow & Levet
showed that constant-dimensional Weisfeiler–Leman can in a constant number of
rounds identify coprime extensions $H\ltimes N$, where the normal Hall
subgroup $N$ is Abelian and the complement $H$ is $O(1)$-generated. This
placed isomorphism testing into L; the previous bound for isomorphism testing
in this family was P [63]. Grochow & Levet also ruled out
$\textsf{FO}+\textsf{LFP}$ as a candidate logic for capturing PTIME on finite
groups, by showing that the count-free Weisfeiler–Leman algorithm cannot even
identify Abelian groups in polynomial-time.

##  2 Preliminaries

We recall the bijective pebble game of Hella [42, 43], in the context of WL on
graphs as that is likely more familiar to more readers. 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ïssé game, with two players: Spoiler and
Duplicator. Each graph begins with $k+1$ pebbles,
$p_{\\_}1,\dotsc,p_{\\_}{k+1}$ for $X$ and
$p_{\\_}1^{\prime},\dotsc,p_{\\_}{k+1}^{\prime}$ for $Y$, which are placed
beside the graphs. Each round proceeds as follows.

  1. 1.

Spoiler chooses $i\in[k+1]$, and picks up pebbles
$p_{\\_}i,p^{\prime}_{\\_}i$.

  2. 2.

We check the winning condition, which will be formalized later.111In the
literature, some authors check the winning condition at this point, and others
check the winning condition at the end of each round. The choice merely has
the effect of changing the number of required pebbles by at most $1$ in
ordinary WL, or at most $q$ in the $q$-ary version, and changing the number of
rounds by at most 1. We have chosen this convention for consistency with other
works on WL specific to groups [13, 14, 31].

  3. 3.

Duplicator chooses a bijection $f:V(X)\to V(Y)$.

  4. 4.

Spoiler places $p_{\\_}{i}$ on some vertex $v\in V(X)$. Then
$p_{\\_}{i}^{\prime}$ is placed on $f(v)$.

In a given round, let $v_{\\_}{1},\ldots,v_{\\_}{m}$ be the vertices of $X$
pebbled at the end of step 1 (in the list above), 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}$ is not an isomorphism of the induced subgraphs
$X[\\{v_{\\_}{1},\ldots,v_{\\_}{m}\\}]$ and
$Y[\\{v_{\\_}{1}^{\prime},\ldots,v_{\\_}{m}^{\prime}\\}]$. Otherwise, at that
point, Duplicator wins the game. 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 [42, 43, 18].

Hella [42, 43] exhibited a hierarchy of pebble games where, for $q\geq 1$,
Spoiler could pebble a sequence of $1\leq j\leq q$ elements
$(v_{\\_}{1},\ldots,v_{\\_}{j})\mapsto(f(v_{\\_}{1}),\ldots,f(v_{\\_}{j}))$ in
a single round; more formally, following the description above, in step 1,
Spoiler picks up $q$ pebbles $p_{\\_}{i_{\\_}1},\dotsc,p_{\\_}{i_{\\_}q}$ and
their partners $p^{\prime}_{\\_}{i_{\\_}1},\dotsc,p^{\prime}_{\\_}{i_{\\_}q}$,
with step 4 changed accordingly. The case of $q=1$ corresponds to the case of
Weisfeiler–Leman. As remarked by Hella [43, p. 6, just before §4], the $q$-ary
game immediately identifies all relational structures of arity $\leq q$. For
example, the $q=2$ game on graphs solves GI: for if two graphs $X$ and $Y$ are
non-isomorphic, then any bijection $f:V(X)\to V(Y)$ that Duplicator selects
must map an adjacent pair of vertices $u,v$ in $X$ to a non-adjacent pair
$f(u),f(v)$ in $Y$ or vice-versa. Spoiler immediately wins by pebbling
$(u,v)\mapsto(f(u),f(v))$. However, as groups are ternary relational
structures (the relation being $\\{(a,b,c):a,b,c\in G,ab=c\\}$), the $q=2$
case can, at least in principle, be non-trivial on groups.

Brachter & Schweitzer [13] adapted Hella’s [42, 43] pebble games in the $q=1$
case to the setting of groups, obtaining three different versions. Their
Version III involves reducing to graphs and playing the pebble game on graphs,
so we don’t consider it further here. Versions I and II are both played on the
groups $G$ and $H$ directly.

Both versions are played identically as for graphs, with the only difference
being the winning condition. We recall the following standard definitions in
order to describe these winning conditions.

######  Definition 2.1.

Let $G,H$ be two groups. Given $k$-tuples
$\overline{g}=(g_{\\_}1,\dotsc,g_{\\_}k)\in G^{k}$ and
$\overline{h}=(h_{\\_}1,\dotsc,h_{\\_}k)\in H^{k}$, we say
$(\overline{g},\overline{h})$ …

  1. 1.

… _gives a well-defined map_ if $g_{\\_}i=g_{\\_}j\Leftrightarrow
h_{\\_}i=h_{\\_}j$ for all $i\neq j$;

  2. 2.

…are _partially isomorphic_ or _give a partial isomorphism_ if they give a
well-defined map, and for all $i,j,k$ we have
$g_{\\_}ig_{\\_}j=g_{\\_}k\Leftrightarrow h_{\\_}ih_{\\_}j=h_{\\_}k$;

  3. 3.

…are _marked isomorphic_ or _give a marked isomorphism_ if it gives a well-
defined map, and the map extends to an isomorphism $\langle
g_{\\_}1,\dotsc,g_{\\_}k\rangle\to\langle h_{\\_}1,\dotsc,h_{\\_}k\rangle$.

Let $v_{\\_}{1},\ldots,v_{\\_}{m}$ be the group elements of $G$ pebbled at the
end of step 1, and let $v_{\\_}{1}^{\prime},\ldots,v_{\\_}{m}^{\prime}$ be the
corresponding pebbled vertices of $H$. In Version I, Spoiler wins precisely if
$(\overline{v},\overline{v}^{\prime})$ does not give a partial isomorphism,
and in Version II Spoiler wins precisely if
$(\overline{v},\overline{v}^{\prime})$ does not give a marked isomorphism.

Both Versions I and II may be generalized to allow Spoiler to pebble up to $q$
group elements at a single round, for some $q\geq 1$. Mimicking the proof
above for $q=2$ for graphs, we have that $q=3$ is sufficient to solve GpI in a
single round. The distinguishing power, however, of the $q=2$ game for groups
remains unclear, and is the main subject of this paper. As we are interested
in the round complexity, we introduce the following notation.

######  Definition 2.2 (Notation for pebbles, rounds, arity, and WL version).

Let $k\geq 2,r\geq 1$, $q\geq 1$, and $J\in\\{I,II\\}$. Denote
$(k,r)$-WL${}^{q}_{\\_}J$ to be the $k$-pebble, $r$-round, $q$-ary Version $J$
pebble game.

We refer to $q$ as the _arity_ of the pebble game, as it corresponds to the
arity of generalized quantifiers222As our focus in this paper is not on the
viewpoint of generalized quantifiers, we refer the reader to [42] for details.
in a logic whose distinguishing power is equivalent to that of the game:

######  Remark 2.3 (Equivalence with logics with generalized $2$-ary
quantifiers).

Hella [42] describes the game (essentially the same as our description, but
with no restriction on number of pebbles, and a transfinite number of rounds)
for general $q$ at the bottom of p. 245, for arbitrary relational structures.
We restrict to the case of $q=2$, a finite number of pebbles and rounds, and
the (relational) language of groups. Hella proves that this game is equivalent
to first-order logic with arbitrary $q$-ary equantifiers in [42, Thm. 2.5].

######  Observation 2.4.

In the $2$-ary pebble game, we may assume that Duplicator selects bijections
that preserve inverses.

###### Proof.

Suppose not. First, Duplicator must select bijections that preserve the
identity, for if not, Spoiler pebbles $1_{\\_}G\mapsto f(1)\neq 1_{\\_}H$ and
wins immediately. Next, let $f:G\to H$ be a bijection such that $f(g^{-1})\neq
f(g)^{-1}$. Spoiler pebbles $(g,g^{-1})\mapsto(f(g),f(g^{-1}))$. Now
$gg^{-1}=1$, while $f(g)f(g^{-1})\neq 1$. So Spoiler wins. ∎

We frequently use this observation without mention.

##  3 Higher-arity Weisfeiler-Leman-style coloring corresponding to higher
arity pebble games

Given a $k$-tuple $\overline{x}=(x_{\\_}1,\dotsc,x_{\\_}k)\in G^{k}$, a pair
of distinct indices $i,j\in[k]$, and a pair of group elements $y,z$, we define
$\overline{x}_{\\_}{(i,j)\leftarrow(y,z)}$ to be the $k$-tuple
$\overline{x}^{\prime}$ that agrees with $\overline{x}$ on all indices besides
$i,j$, and with $x_{\\_}i^{\prime}=y,x_{\\_}j^{\prime}=z$. If $i=j$, we
require $y=z$, and we denote this $\overline{x}_{\\_}{i\leftarrow y}$.

Finally, two graphs $\Gamma_{\\_}1,\Gamma_{\\_}2$, with edge-colorings
$c_{\\_}i\colon E(\Gamma_{\\_}i)\to C$ to some color set $C$ (for $i=1,2$) are
color isomorphic if there is a graph isomorphism $\varphi\colon
V(\Gamma_{\\_}1)\to V(\Gamma_{\\_}2)$ that also preserves colors, in the sense
that $c_{\\_}1((u,v))=c_{\\_}2((\varphi(u),\varphi(v))$ for all edges
$(u,v)\in E(\Gamma_{\\_}1)$.

######  Definition 3.1 (2-ary $k$-dimensional Weisfeiler-Leman coloring).

Let $G,H$ be two groups of the same order, let $k\geq 1$. For all $k$-tuples
$\overline{x},\overline{y}\in G^{k}\cup H^{k}$:

  * •

(Initial coloring, Version I)
$\chi^{2,I}_{\\_}0(\overline{x})=\chi^{2,I}_{\\_}0(\overline{y})$ iff
$\overline{x},\overline{y}$ are partially isomorphic.

  * •

(Initial coloring, Version II)
$\chi^{2,II}_{\\_}0(\overline{x})=\chi^{2,II}_{\\_}0(\overline{y})$ iff
$\overline{x},\overline{y}$ have the same marked isomorphism type.

  * •

(Color refinement) Given a coloring $\chi\colon G^{k}\cup H^{k}\to C$, the
color refinement operator $R$ defines a new coloring $R(\chi)$ as follows. For
each $k$-tuple $\overline{x}\in G^{k}$ (resp., $H^{k}$), we define an edge-
colored graph $\Gamma_{\\_}{\overline{x},\chi,i,j}$. If $i=j$, it is the graph
on vertex set $V(\Gamma_{\\_}{\overline{x},\chi,i,i})=G$ (resp., $H$) with all
self-loops and no other edges, where the color of each self-loop $(g,g)$ is
$\chi(\overline{x}_{\\_}{i\leftarrow g})$. If $i\neq j$, it is the complete
directed graph with self-loops on vertex set $G$ (resp., $H$), where the color
of each edge $(y,z)$ is $\chi(\overline{x}_{\\_}{(i,j)\leftarrow(y,z)})$. For
an edge-colored graph $\Gamma$, we use $[\Gamma]$ to denote its edge-colored
isomorphism class. We then define

$R(\chi)(\overline{x})=\left(\chi(\overline{x});[\Gamma_{\\_}{\overline{x},\chi,1,1}],[\Gamma_{\\_}{\overline{x},\chi,1,2}],\dotsc,[\Gamma_{\\_}{\overline{x},\chi,k-1,k}],[\Gamma_{\\_}{\overline{x},\chi,k,k}]\right).$

That is, the new color consists of the old color, as well as the tuple of
$\binom{k+1}{2}$ edge-colored isomorphism types of the graphs
$\Gamma_{\\_}{\overline{x},\chi,i,j}$.

The refinement operator may be iterated: $R^{t}(\chi):=R(R^{t-1}(\chi))$, and
we define the _stable refinement_ of $\chi$ as $R^{t}(\chi)$ where the
partition induced by $R^{t}(\chi)$ on $G^{k}\cup H^{k}$ is the same as that
induced by $R^{t+1}(\chi)$. We denote the stable refinement by
$R^{\infty}(\chi)$.

Finally, for $J\in\\{I,II\\}$ and all $r\geq 0$, we define
$\chi^{2,J}_{\\_}{r+1}=R(\chi^{2,J}_{\\_}r)$, and
$\chi^{2,J}_{\\_}{\infty}:=R^{\infty}(\chi^{2,J}_{\\_}0)$.

######  Remark 3.2.

Brachter & Schweitzer [13] introduced Versions I and II of $1$-ary WL, which
are equivalent up to a small additive constant in the WL-dimension [13] and
$O(\log n)$ rounds [31]. For the purpose of comparison, we introduce Versions
I and II of $2$-ary WL. We will see later that only one additional round
suffices in the $2$-ary case (see Thm. 3.7). The differences in Versions I and
II of WL (both the $1$-ary and $2$-ary variants) arise from whether the group
is viewed as a structure with a ternary relational structure (Version I) or as
a structure with a binary function (Version II).

######  Remark 3.3.

Since it was one of our stumbling blocks in coming up with this generalized
coloring, we clarify here how this indeed generalizes the usual 1-ary WL
coloring procedure. In the 1-ary “oblivious” $k$-WL procedure (see [34, §5],
equivalent to ordinary WL), the color of a $k$-tuple $\overline{x}$ is refined
using its old color, together with a $k$-tuple of multisets

$(\\{\\!\\{\chi(x_{\\_}{1\leftarrow y}):y\in
G\\}\\!\\},\\{\\!\\{\chi(x_{\\_}{2\leftarrow y}):y\in
G\\}\\!\\},\dotsc,\\{\\!\\{\chi(x_{\\_}{k\leftarrow y}):y\in G\\}\\!\\}).$

For each $i$, note that two multisets $\\{\\!\\{\chi(x_{\\_}{i\leftarrow
y}):y\in G\\}\\!\\}$ and $\\{\\!\\{\chi(x^{\prime}_{\\_}{i\leftarrow y}):y\in
G\\}\\!\\}$ are equal iff the graphs $\Gamma_{\\_}{\overline{x},\chi,i,i}$ and
$\Gamma_{\\_}{\overline{x}^{\prime},\chi,i,i}$ are color-isomorphic. That is,
edge-colored graphs with only self-loops and no other edges are essentially
the same, up to isomorphism, as multisets. Our procedure generalizes this by
also considering graphs with other edges, which (as we’ll see in the proof of
equivalence, which will appear in the full version) are used to encode the
choice of 2 simultaneous pebbles by Spoiler in each move of the game.

######  Theorem 3.4.

Let $G,H$ be two groups of order $n$, with $\overline{x}\in
G^{k},\overline{y}\in H^{k}$. Starting from the initial pebbling
$x_{\\_}i\mapsto y_{\\_}i$ for all $i=1,\dotsc,k$, Spoiler has a winning
strategy in the $k$-pebble, $r$-round, 2-ary Version $J$ pebble game (for
$J\in\\{I,II\\}$) iff
$\chi^{2,J}_{\\_}r(\overline{x})\neq\chi^{2,J}_{\\_}r(\overline{y})$.

###### Proof.

To appear in the full version. ∎

######  Corollary 3.5.

For two groups $G,H$ of the same order and any $k\geq 1$, the following are
equivalent:

  1. 1.

The 2-ary $k$-pebble game does not distinguish two groups $G,H$

  2. 2.

The multisets of stable colors on $G^{k}$ and $H^{k}$ are the same, that is,
$\\{\\!\\{\chi^{2,J}_{\\_}\infty(\overline{x}):\overline{x}\in
G^{k}\\}\\!\\}=\\{\\!\\{\chi^{2,J}_{\\_}\infty(\overline{y}):\overline{y}\in
H^{k}\\}\\!\\}$

  3. 3.

$\chi^{2,J}_{\\_}\infty((1_{\\_}G,1_{\\_}G,\dotsc,1_{\\_}G))=\chi^{2,J}_{\\_}\infty((1_{\\_}H,\dotsc,1_{\\_}H))$.

The analogous result holds in the $q=1$ case, going back to [13].

###### Proof.

To appear in the full version. ∎

######  Remark 3.6.

For arbitrary relational structures with relations of arity $a+1$, the
$a$-order pebble game may still be nontrivial, as pointed out in Hella [43, p.
6, just before §4]. Our coloring procedure generalizes in the following way to
this more general setting, and the proof of the equivalence between the
coloring procedure and Hella’s pebble game is the same as the above, _mutatis
mutandis_. The main change is that for an $a$-th order pebble game, instead of
just considering a graph on edges of size 1 (when $i=j$) or 2 (when $i\neq
j$), we consider an $a^{\prime}$-uniform directed hypergraph, where each
hyperedge consists of a list of $a^{\prime}$ vertices, for all $1\leq
a^{\prime}\leq a$. This gives a coloring equivalent of the logical and game
characterizations provided by Hella; this trifecta is partly why we feel it is
justified to call this a “higher-arity Weisfeiler–Leman” coloring procedure.

We note that there has been some work on equivalences with specific binary and
higher-arity quantifiers: see for instance, the invertible map game of Dawar &
Holm [22] which generalizes rank logic, in which Spoiler can place multiple
pebbles, but the bijections Duplicator selects must satisfy additional
structure. Subsequently, Dawar & Vagnozzi [23] provided a generalization of
Weisfeiler–Leman that further subsumes the invertible map game. We note that
Dawar & Vagnozzi’s “$WL_{\\_}{k,r}$”, although it looks superficially like our
$r$-ary $k$-WL, is in fact quite different: in particular, their refinement
step “flattens” a multiset of multisets into its multiset union, which loses
information compared to our 2-ary (resp., $r$-ary) game; indeed, they show
that their WL${}_{\\_}{*,r}$ is equivalent to ordinary (1-ary) WL for any
fixed $r$, whereas already 2-ary WL can solve GI. In general, the relationship
between Hella’s $2$-ary game and the works of Dawar & Holm and Dawar &
Vagnozzi remains open.

###  3.1 Equivalence between 2-ary $(k,r)$-WL Versions I and II

In this section we show that, up to additive constants in the number of
pebbles and rounds, 2-ary WL Versions I and II are equivalent in their
distinguishing power. For two different WL versions $W,W^{\prime}$, we write
$W\preceq W^{\prime}$ to mean that if $W$ distinguishes two groups $G$ and
$H$, then so does $W^{\prime}$.

######  Theorem 3.7.

Let $k\geq 2,r\geq 1$. We have that:

$(k,r)\text{-WL}^{2}_{\\_}{I}\preceq(k,r)\text{-WL}^{2}_{\\_}{II}\preceq(k+2,r+1)\text{-WL}^{2}_{\\_}{I}.$

###### Proof.

To appear in the full version. ∎

##  4 Descriptive Complexity of Semisimple Groups

In this section, we show that the $(O(1),O(1))$-WL${}_{\\_}{II}^{2}$ pebble
game can identify groups with no Abelian normal subgroups,333In many places,
we will use $O(1)$ for number of pebbles or rounds; we believe all of these
can be replaced with particular numbers by a straightforward, if tedious,
analysis of our proofs. However, since our focus is on the fact that these
numbers are constant rather than on the exact values, we use the $O(1)$
notation. also known as semisimple groups. We begin with some preliminaries.

###  4.1 Preliminaries

Semisimple groups are motivated by the following characteristic filtration:

$1\leq\operatorname{Rad}(G)\leq\text{Soc}^{*}(G)\leq\text{PKer}(G)\leq G,$

which arises in the computational complexity community where it is known as
the Babai–Beals filtration [6], as well as in the development of practical
algorithms for computer algebra systems (c.f., [19]). We now explain the terms
of this chain. Here, $\operatorname{Rad}(G)$ is the solvable radical, which is
the unique maximal solvable normal subgroup of $G$; recall that a group $N$ is
solvable if the sequence $N^{(0)}:=N$, $N^{(i)}=[N^{(i-1)},N^{(i-1)}]$
terminates in the trivial group after finitely many steps, and $[A,B]$ denotes
the subgroup generated by $\\{aba^{-1}b^{-1}:a\in A,b\in B\\}$. The socle of a
group, denoted $\text{Soc}(G)$, is the subgroup generated by all the minimal
normal subgroups of $G$. $\text{Soc}^{*}(G)$ is the preimage of the socle
$\text{Soc}(G/\operatorname{Rad}(G))$ under the natural projection map
$\pi:G\to G/\operatorname{Rad}(G)$. To define PKer, we start by examining the
action on
$\text{Soc}(G/\operatorname{Rad}(G))\cong\text{Soc}^{*}(G)/\operatorname{Rad}(G)$
that is induced by the action of $G$ on $\text{Soc}^{*}(G)$ by conjugation. As
$\text{Soc}^{*}(G)/\operatorname{Rad}(G)\cong\text{Soc}(G/\operatorname{Rad}(G))$
is the direct product of finite, non-Abelian simple groups
$T_{\\_}{1},\ldots,T_{\\_}{k}$, this action permutes the $k$ simple factors,
yielding a homomorphism $\varphi:G\to S_{\\_}{k}$. The kernel of this action
is denoted $\text{PKer}(G)$.

When $\operatorname{Rad}(G)$ is trivial, $G$ has no Abelian normal subgroups
(and vice versa). We refer to such groups as semisimple (following [8, 9]) or
trivial-Fitting (following [19]). 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. As the conjugation action of $G$ on $\text{Soc}(G)$
permutes the direct factors of $\text{Soc}(G)$, there exists a faithful
permutation representation $\alpha:G\to
G^{*}\leq\operatorname{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$ in the sense introduced next.

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 permutational isomorphism $K\to L$ if $K^{\pi}=L$.

The following lemma, applied with $R=\text{Soc}(G)$ and $S=\text{Soc}(H)$,
gives a precise characterization of semisimple groups in terms of the
associated actions.

######  Lemma 4.1 ([8, Lemma 3.1], cf. [19, §3]).

Let $G$ and $H$ be groups, with $R\triangleleft G$ and $S\triangleleft H$
groups with trivial centralizers. Let $\alpha:G\to\operatorname{Aut}(R)$ and
$\beta:H\to\operatorname{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^{*}=Im(\alpha)$ and $H^{*}=Im(\beta)$; and if so, $\hat{f}=\alpha
f^{*}\beta^{-1}$, where $f^{*}:G^{*}\to H^{*}$ is the isomorphism induced by
$f$.

We also need the following standard group-theoretic lemmas. The first provides
a key condition for identifying whether a non-Abelian simple group belongs to
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}$.

######  Lemma 4.2 (c.f. [31, Lemma 6.5]).

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.

######  Lemma 4.3 (c.f. [31, Lemma 6.6]).

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_{\\_}1S_{\\_}2\dotsb
S_{\\_}k=S_{\\_}1\times\dotsb\times S_{\\_}k$.

###  4.2 Main Results

We show that the second Ehrenfeucht–Fraïssé game in Hella’s hierarchy can
identify both $\text{Soc}(G)$ and the conjugation action when $G$ is
semisimple. We first show that this pebble game can identify whether a group
is semisimple. Namely, if $G$ is semisimple and $H$ is not semisimple, then
Spoiler can distinguish $G$ from $H$.

######  Proposition 4.4.

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 Spoiler can win in the
$(4,2)$-WL${}_{\\_}{II}^{2}$ game.

###### Proof.

To appear in the full version. ∎

We now apply Lemma 4.2 to show that Duplicator must map the direct factors of
$\text{Soc}(G)$ to isomorphic direct factors of $\text{Soc}(H)$.

######  Lemma 4.5.

Let $G,H$ be finite 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, with $S=\langle
x,y\rangle$. If Duplicator selects a bijection $f\colon G\to H$ such that:

  1. (a)

$S\not\cong\langle f(x),f(y)\rangle$, then Spoiler can win in the
$(2,1)$-WL${}_{\\_}{II}^{2}$ game; or

  2. (b)

$f(S)\neq\langle f(x),f(y)\rangle$, then Spoiler can win in the
$(4,2)$-WL${}_{\\_}{II}^{2}$ pebble game.

Note that the lemma does not require $f|_{\\_}{S}\colon S\to f(S)$ to actually
be an isomorphism, only that $S$ and $f(S)$ are isomorphic.

###### Proof.

To appear in the full version. ∎

######  Proposition 4.6.

Let $G$ be a semisimple group of order $n$, and let $H$ be an arbitrary group
of order $n$. Let $f:G\to H$ be the bijection Duplicator selects. If there
exists $S\in\text{Fac}(\text{Soc}(G))$ such that
$f(S)\notin\text{Fac}(\text{Soc}(H))$ or $f(S)\not\cong S$, then Spoiler can
win in the $(4,2)$-WL${}_{\\_}{II}^{2}$ pebble game.

###### Proof.

To appear in the full version. ∎

######  Lemma 4.7.

Let $G,H$ be groups of order $n$, let $S$ be a nonabelian simple group in
$\text{Fac}(\text{Soc}(G))$. Let $f,f^{\prime}\colon G\to H$ be two bijections
selected by Duplicator at two different rounds. If $f(S)\cap f^{\prime}(S)\neq
1$, then $f(S)=f^{\prime}(S)$, or Spoiler can win in the
$(4,2)$-WL${}_{\\_}{II}^{2}$ pebble game.

###### Proof.

By Prop. 4.6, both $f(S)$ and $f^{\prime}(S)$ must be simple normal subgroups
of $\text{Soc}(H)$ (or Spoiler wins with $4$ pebbles and $2$ rounds). Since
they intersect nontrivially, but distinct simple normal subgroups of
$\text{Soc}(H)$ intersect trivially, the two must be equal. ∎

We next introduce the notion of weight.

######  Definition 4.8.

Let $\text{Soc}(G)=S_{\\_}1\times\dotsb\times S_{\\_}k$ where each $S_{\\_}i$
is a simple normal subgroup of $\text{Soc}(G)$. For any $s\in\text{Soc}(G)$,
write $s=s_{\\_}1s_{\\_}2\dotsb s_{\\_}k$ where each $s_{\\_}i\in S_{\\_}i$,
and define the _weight_ of $s$, denote $\text{wt}(s)$, as the number of $i$’s
such that $s_{\\_}i\neq 1$.

Note that the definition of weight is well-defined since the $S_{\\_}i$ are
the unique subsets of $\text{Soc}(G)$ that are simple normal subgroup of
$\text{Soc}(G)$, so the decomposition $s=s_{\\_}1s_{\\_}2\dotsc s_{\\_}k$ is
unique up to the order of the factors. (This is essentially a particular
instance of the “rank lemma” from [31], which intuitively states that WL
detects in $O(\log n)$ rounds the set of elements for a given subgroup
provided that it also identifies the generators. As we are now in the setting
of $2$-ary WL we give the full proof, which also has tighter bounds on the
number of rounds.)

######  Lemma 4.9 (Weight Lemma).

Let $G,H$ be semisimple groups of order $n$. If Duplicator selects a bijection
$f\colon G\to H$ that does not map $\text{Soc}(G)$ bijectively to
$\text{Soc}(H)$, or does not preserve the weight of every element in
$\text{Soc}(G)$, then Spoiler can win in the $(4,3)$-WL${}_{\\_}{II}^{2}$
game.

###### Proof.

To appear in the full version. ∎

######  Lemma 4.10.

Let $G$ and $H$ be semisimple groups with isomorphic socles. Let
$S_{\\_}{1},S_{\\_}{2}\in\text{Fac}(\text{Soc}(G))$ be distinct. Let $f:G\to
H$ be the bijection that Duplicator selects. If there exist $x_{\\_}i\in
S_{\\_}i$ such that $f(x_{\\_}1x_{\\_}2)\neq f(x_{\\_}1)f(x_{\\_}2)$, then
Spoiler can win in the $(4,3)$-WL${}_{\\_}{II}^{2}$ pebble game.

###### Proof.

By Lem. 4.9, we may assume that $\text{wt}(s)=\text{wt}(f(s))$ for all
$s\in\text{Soc}(G)$; otherwise, Spoiler wins with at most $4$ pebbles and $3$
rounds. As $f(x_{\\_}{1}x_{\\_}{2})$ has weight $2$, $f(x_{\\_}{1}x_{\\_}{2})$
belongs to the direct product of two simple factors in
$\text{Fac}(\text{Soc}(H))$, so it can be written
$f(x_{\\_}1x_{\\_}2)=y_{\\_}1y_{\\_}2$ with each $y_{\\_}i$ in distinct simple
factors in $\text{Fac}(\text{Soc}(H))$. Without loss of generality suppose
that $y_{\\_}1\neq f(x_{\\_}1)$. Spoiler pebbles
$(x_{\\_}1,x_{\\_}1x_{\\_}2)\mapsto(f(x_{\\_}1),f(x_{\\_}1x_{\\_}2))$. Now
$\text{wt}(x_{\\_}1^{-1}\cdot x_{\\_}{1}x_{\\_}{2})=1$, while
$\text{wt}(f(x_{\\_}1)^{-1}\cdot f(x_{\\_}{1}x_{\\_}{2}))\geq 2$. (Note that
we cannot quite yet directly apply Lem. 4.9, because we have not yet
identified a single element $x$ such that $\text{wt}(x)\neq\text{wt}(f(x))$.)

On the next round, Duplicator selects another bijection $f^{\prime}$. Spoiler
now pebbles $x_{\\_}2\mapsto f^{\prime}(x_{\\_}2)$. Because
$\text{wt}(x_{\\_}1^{-1}\cdot x_{\\_}1x_{\\_}2)=1$ but
$\text{wt}(f(x_{\\_}1)^{-1}f(x_{\\_}1x_{\\_}2))\geq 2$, and $f^{\prime}$
preserves weight by Lem. 4.9, we have $f^{\prime}(x_{\\_}2)\neq
f^{\prime}(x_{\\_}1)^{-1}f^{\prime}(x_{\\_}1x_{\\_}2)$. Thus, the pebbled map
$(x_{\\_}1,x_{\\_}2,x_{\\_}1x_{\\_}2)\mapsto(f^{\prime}(x_{\\_}1),f(x_{\\_}2),f(x_{\\_}1x_{\\_}2))$
does not extend to an isomorphism, and so Spoiler wins with $3$ pebbles and
$2$ rounds. ∎

Recall that if $G$ is semisimple, then
$G\leq\operatorname{Aut}(\text{Soc}(G))$. Now each minimal normal subgroup
$N\trianglelefteq G$ is of the form $N=S^{k}$, where $S$ is a non-Abelian
simple group. So
$\operatorname{Aut}(N)=\operatorname{Aut}(S)\wr\text{Sym}(k)$. In particular,

$G\leq\prod_{\\_}{\begin{subarray}{c}N\trianglelefteq G\\\ N\text{ is minimal
normal}\end{subarray}}\operatorname{Aut}(N).$

So if $g\in G$, then the conjugation action of $g$ on $\text{Soc}(G)$ acts by
(i) automorphism on each simple direct factor of $\text{Soc}(G)$, and (ii) by
permuting the direct factors of $\text{Soc}(G)$. Provided generators of the
direct factors of the socle are pebbled, Spoiler can detect inconsistencies of
the automorphism action. However, doing so directly would be too expensive as
there could be $\Theta(\log|G|)$ generators, so we employ a more subtle
approach with a similar outcome. By Lem. 4.9, Duplicator must select
bijections $f:G\to H$ that preserve weight. That is, if $s\in\text{Soc}(G)$,
then $\text{wt}(s)=\text{wt}(f(s))$. We use Lem. 4.9 in tandem with the fact
that the direct factors of the socle commute to effectively pebble the set of
all the generators at once. Namely, suppose that
$\text{Fac}(\text{Soc}(G))=\\{S_{\\_}{1},\ldots,S_{\\_}{k}\\}$, where
$S_{\\_}{i}=\langle x_{\\_}{i},y_{\\_}{i}\rangle$. Let $x:=x_{\\_}{1}\cdots
x_{\\_}{k}$ and $y:=y_{\\_}{1}\cdots y_{\\_}{k}$. We will show that it
suffices for Spoiler to pebble $(x,y)$ rather than individually pebbling
generators for each $S_{\\_}{i}$ (this will still allow the factors to be
permuted, but that is all).

######  Lemma 4.11.

Let $G$ and $H$ be semisimple groups with isomorphic socles, and write
$\text{Fac}(\text{Soc}(G))=\\{S_{\\_}1,\dotsc,S_{\\_}m\\}$, with
$S_{\\_}i=\langle x_{\\_}i,y_{\\_}i\rangle$. Let $f:G\to H$ be the bijection
that Duplicator selects, and suppose that (i) for all $i$, $f(S_{\\_}i)\cong
S_{\\_}i$ (though $f|_{\\_}{S_{\\_}i}$ need not be an isomorphism) and
$f(S_{\\_}i)\in\text{Fac}(\text{Soc}(H))$, (ii) for every $s\in\text{Soc}(G)$,
$\text{wt}(s)=\text{wt}(f(s))$, and (iii) for all $i$, $f(S_{\\_}i)=\langle
f(x),f(y)\rangle$.

Now suppose that Spoiler pebbles $(x_{\\_}{1}\cdots
x_{\\_}{m},y_{\\_}{1}\cdots y_{\\_}{m})\mapsto(f(x_{\\_}{1}\cdots
x_{\\_}{m}),f(y_{\\_}{1}\cdots y_{\\_}{m}))$. As $f$ preserves weight, we may
write $f(x_{\\_}{1}\cdots x_{\\_}{m})=h_{\\_}{1}\cdots h_{\\_}{m}$ and
$f(y_{\\_}{1}\cdots y_{\\_}{m})=z_{\\_}{1}\cdots z_{\\_}{m}$ with
$h_{\\_}i,z_{\\_}i\in f(S_{\\_}i)$ for all $i$.

Let $f^{\prime}:G\to H$ be the bijection that Duplicator selects at any
subsequent round in which the pebble used above has not moved. If any of the
following hold, then Spoiler can win in the WL${}_{\\_}{II}^{2}$ pebble game
with $5$ additional pebbles and $5$ additional rounds:

  1. (a)

$f^{\prime}$ does not satisfy conditions (i)–(iii),

  2. (b)

there exists an $i\in[m]$ such that
$f^{\prime}(x_{\\_}i)\notin\\{h_{\\_}1,\dotsc,h_{\\_}m\\}$ or
$f^{\prime}(y_{\\_}i)\notin\\{z_{\\_}1,\dotsc,z_{\\_}m\\}$

  3. (c)

$f^{\prime}|_{\\_}{S_{\\_}{i}}$ is not an isomorphism

  4. (d)

there exists $g\in G$ and $i\in[m]$ such that $gS_{\\_}{i}g^{-1}=S_{\\_}{i}$
and for some $x\in S_{\\_}{i}$, the following holds: $f^{\prime}(gxg^{-1})\neq
f^{\prime}(g)f^{\prime}(x)f^{\prime}(g)^{-1}$.

###### Proof.

To appear in the full version. ∎

Lem. 4.11 provides enough to establish that Spoiler can force Duplicator to
select at each round a bijection that restricts to an isomorphism on the
socles.

######  Proposition 4.12.

(Same assumptions as Lem. 4.11.) Let $G$ and $H$ be semisimple groups with
isomorphic socles, with
$\text{Fac}(\text{Soc}(G))=\\{S_{\\_}1,\dotsc,S_{\\_}m\\}$, with
$S_{\\_}i=\langle x_{\\_}i,y_{\\_}i\rangle$. Let $f_{\\_}0:G\to H$ be the
bijection that Duplicator selects, and suppose that (i) for all $i$,
$f_{\\_}0(S_{\\_}i)\cong S_{\\_}i$ (though $f_{\\_}0|_{\\_}{S_{\\_}i}$ need
not be an isomorphism) and $f_{\\_}0(S_{\\_}i)\in\text{Fac}(\text{Soc}(H))$,
(ii) for every $s\in\text{Soc}(G)$, $\text{wt}(s)=\text{wt}(f_{\\_}0(s))$, and
(iii) for all $i$, $f_{\\_}0(S_{\\_}i)=\langle
f_{\\_}0(x),f_{\\_}0(y)\rangle$. Now suppose that Spoiler pebbles
$(x_{\\_}{1}\cdots x_{\\_}{m},y_{\\_}{1}\cdots
y_{\\_}{m})\mapsto(f_{\\_}0(x_{\\_}{1}\cdots
x_{\\_}{m}),f_{\\_}0(y_{\\_}{1}\cdots y_{\\_}{m}))$.

Let $f^{\prime}\colon G\to H$ be the bijection that Duplicator selects at any
subsequent round in which the pebbles used above have not moved. Then
$f^{\prime}|_{\\_}{\text{Soc}(G)}\colon\text{Soc}(G)\to\text{Soc}(H)$ must be
an isomorphism, or Spoiler can win in $4$ more rounds using at most $6$ more
pebbles (for a total of $7$ pebbles and $5$ rounds) in the
WL${}_{\\_}{II}^{2}$ pebble game.

###### Proof.

To appear in the full version. ∎

######  Remark 4.13.

Brachter & Schweitzer [14, Lemma 5.22] previously showed that (1-ary)
Weisfeiler–Leman can decide whether two groups have isomorphic socles.
However, their results did not solve the search problem; that is, they did not
show Duplicator must select bijections that restrict to an isomorphism on the
socle even in the case for semisimple groups. This contrasts with Lem. 4.12,
where we show that 2-ary WL effectively solves the search problem. This is an
important ingredient in our proof that the $(7,O(1))$-WL${}_{\\_}{II}^{2}$
pebble game solves isomorphism for semisimple groups.

We obtain as a corollary of Lem. 4.11 and Lem. 4.12 that if $G$ and $H$ are
semisimple, then Duplicator must select bijections that restrict to
isomorphisms of $\operatorname{PKer}(G)$ and $\operatorname{PKer}(H)$.

######  Corollary 4.14.

Let $G$ and $H$ be semisimple groups of order $n$. Let
$\text{Fac}(\text{Soc}(G)):=\\{S_{\\_}{1},\ldots,S_{\\_}{m}\\}$, and suppose
that $S_{\\_}{i}=\langle x_{\\_}{i},y_{\\_}{i}\rangle$. Let
$x:=x_{\\_}{1}\cdots x_{\\_}{m}$ and $y:=y_{\\_}{1}\cdots y_{\\_}{m}$. and Let
$f:G\to H$ be the bijection that Duplicator selects. Spoiler begins by
pebbling $(x,y)\mapsto(f(x),f(y))$. Let $f^{\prime}:G\to H$ be the bijection
that Duplicator selects at the next round. If
$f^{\prime}|_{\\_}{\operatorname{PKer}(G)}:\operatorname{PKer}(G)\to\operatorname{PKer}(H)$
is not an isomorphism, then Spoiler can win with $5$ additional pebbles and
$5$ additional rounds in the WL${}_{\\_}{II}^{2}$ pebble game.

###### Proof.

To appear in the full version. ∎

We now show that if $G$ and $H$ are not permutationally equivalent, then
Spoiler can win.

######  Lemma 4.15.

(Same assumptions as Lem. 4.11.) Let $G$ and $H$ be semisimple groups with
isomorphic socles, with
$\text{Fac}(\text{Soc}(G))=\\{S_{\\_}1,\dotsc,S_{\\_}m\\}$, with
$S_{\\_}i=\langle x_{\\_}i,y_{\\_}i\rangle$. Let $f_{\\_}0:G\to H$ be the
bijection that Duplicator selects, and suppose that (i) for all $i$,
$f_{\\_}0(S_{\\_}i)\cong S_{\\_}i$ (though $f_{\\_}0|_{\\_}{S_{\\_}i}$ need
not be an isomorphism) and $f_{\\_}0(S_{\\_}i)\in\text{Fac}(\text{Soc}(H))$,
(ii) for every $s\in\text{Soc}(G)$, $\text{wt}(s)=\text{wt}(f_{\\_}0(s))$, and
(iii) for all $i$, $f_{\\_}0(S_{\\_}i)=\langle
f_{\\_}0(x),f_{\\_}0(y)\rangle$. Now suppose that Spoiler pebbles
$(x_{\\_}{1}\cdots x_{\\_}{m},y_{\\_}{1}\cdots
y_{\\_}{m})\mapsto(f_{\\_}0(x_{\\_}{1}\cdots
x_{\\_}{m}),f_{\\_}0(y_{\\_}{1}\cdots y_{\\_}{m}))$.

Let $f^{\prime}:G\to H$ be the bijection that Duplicator selects at the next
round. Suppose that there exist $g\in G$ and $i\in[m]$ such that
$f^{\prime}(gS_{\\_}{i}g^{-1})=f^{\prime}(S_{\\_}{j})$, but
$f^{\prime}(g)f^{\prime}(S_{\\_}{i})f^{\prime}(g)^{-1}=f^{\prime}(S_{\\_}{k})$
for some $k\neq j$. Then Spoiler can win with $4$ additional pebbles and $4$
additional rounds in the WL${}_{\\_}{II}^{2}$ pebble game.

###### Proof.

To appear in the full version. ∎

######  Theorem 4.16.

Let $G$ be a semisimple group and $H$ an arbitrary group of order $n$, not
isomorphic to $G$. Then Spoiler has a winning strategy in the
$(9,O(1))$-WL${}_{\\_}{II}^{2}$ pebble game.

###### Proof.

If $H$ is not semisimple, then by Prop. 4.4, Spoiler wins with $4$ pebbles and
$2$ rounds. So we now suppose $H$ is semisimple.

Let $\text{Fac}(\text{Soc}(G))=\\{S_{\\_}1,\dotsc,S_{\\_}k\\}$, and let
$x_{\\_}i,y_{\\_}i$ be generators of $S_{\\_}i$ for each $i$. Let $f$ be the
bijection chosen by Duplicator. Spoiler pebbles $(x_{\\_}1x_{\\_}2\dotsb
x_{\\_}k,y_{\\_}1y_{\\_}2,\dotsc,y_{\\_}k)\mapsto(f(x_{\\_}1\dotsb
x_{\\_}k),f(y_{\\_}1\dotsb y_{\\_}k))$. On subsequent rounds, we thus have
satisfied the hypotheses of Lem. 4.11 and Prop. 4.12. Spoiler will never move
this pebble, and thus all subsequent bijections chosen by Duplicator must
restrict to isomorphisms on the socle (or Spoiler wins with at most $7$
pebbles and $O(1)$ rounds).

Recall from Lem. 4.1 that $G\cong H$ iff there is an isomorphism
$\mu\colon\text{Soc}(G)\to\text{Soc}(H)$ that induces a permutational
isomorphism $\mu^{*}\colon G^{*}\to H^{*}$. Thus, since $G\not\cong H$, there
must be some $g\in G$ and $s\in\text{Soc}(G)$ such that $f(gsg^{-1})\neq
f(g)f(s)f(g)^{-1}$. Write $s=s_{\\_}1\dotsb s_{\\_}k$ with each $s_{\\_}i\in
S_{\\_}i$ (not necessarily nontrivial). We claim that there exists some $i$
such that $f(gs_{\\_}ig^{-1})\neq f(g)f(s_{\\_}i)f(g)^{-1}$. For suppose not,
then we have

$\displaystyle f(gsg^{-1})$ $\displaystyle=$ $\displaystyle
f(gs_{\\_}1g^{-1}gs_{\\_}2g^{-1}\dotsb gs_{\\_}kg^{-1})$ $\displaystyle=$
$\displaystyle f(gs_{\\_}1g^{-1})f(gs_{\\_}2g^{-1})\dotsb f(gs_{\\_}kg^{-1})$
$\displaystyle=$ $\displaystyle
f(g)f(s_{\\_}1)f(g)^{-1}f(g)f(s_{\\_}2)f(g)^{-1}\dotsb
f(g)f(s_{\\_}k)f(g)^{-1}$ $\displaystyle=$ $\displaystyle f(g)f(s_{\\_}1\dotsb
s_{\\_}k)f(g)^{-1}=f(g)f(s)f(g)^{-1},$

a contradiction. For simplicity of notation, without loss of generality we may
assume $i=1$, so we now have $f(gs_{\\_}1g)^{-1}\neq
f(g)f(s_{\\_}1)f(g)^{-1}$.

We break the argument into cases:

  1. 1.

If $gs_{\\_}1g^{-1}\in S_{\\_}{1}$, then we have $gS_{\\_}1g^{-1}=S_{\\_}1$
(any two distinct simple normal factors of the socle intersect trivially), we
have by Lem. 4.11 (d) that Spoiler can win with at most $5$ additional pebbles
(for a total of $7$ pebbles) and $5$ additional rounds (for a total of $6$
rounds).

  2. 2.

If $gs_{\\_}1g^{-1}\in S_{\\_}j$ for $j\neq 1$ and
$f(g)f(s_{\\_}{1})f(g)^{-1}\notin f(S_{\\_}j)$, we have by Lem. 4.15 that
Spoiler can win with at most $4$ additional pebbles (for a total of $6$
pebbles) and $4$ additional rounds (for a total of $5$ rounds).

  3. 3.

Suppose now that $gs_{\\_}1g^{-1}\in S_{\\_}j$ for some $j\neq 1$ and
$f(g)f(s_{\\_}{1})f(g)^{-1}\in f(S_{\\_}j)$. Spoiler begins by pebbling
$(g,gs_{\\_}{1}g^{-1})\mapsto(f(g),f(gs_{\\_}{1}g^{-1}))$. Let
$f^{\prime}:G\to H$ be the bijection that Duplicator selects at the next
round. As $gs_{\\_}{1}g^{-1}\in S_{\\_}{j}$ is pebbled, we have that
$f^{\prime}(S_{\\_}{j})=f(S_{\\_}{j})$ by Lem. 4.7 (or Spoiler wins with $4$
additional pebbles and $2$ additional rounds). Now by assumption,
$gS_{\\_}{1}g^{-1}=S_{\\_}{j}$ and $f(g)f(S_{\\_}{1})f(g)^{-1}=f(S_{\\_}{j})$.
So as $g\mapsto f(g)$ is pebbled, we claim that we may assume
$f^{\prime}(S_{\\_}{1})=f(S_{\\_}{1})$. For suppose not; then we have
$g^{-1}S_{\\_}jg=S_{\\_}1$ but
$f^{\prime}(g)^{-1}f^{\prime}(S_{\\_}j)f^{\prime}(g)=f(g)^{-1}f(S_{\\_}j)f(g)=f(S_{\\_}1)\neq
f^{\prime}(S_{\\_}1)$. But then Spoiler can with win with $4$ additional
pebbles (for a total of $8$ pebbles) and $4$ additional rounds (for a total of
$7$ rounds) by Lem. 4.15. Thus we have $f^{\prime}(S_{\\_}1)=f(S_{\\_}1)$.

In particular, we have that $f^{\prime}(x_{\\_}{1})=f(x_{\\_}{1})$ and
$f^{\prime}(y_{\\_}{1})=f(y_{\\_}{1})$, by the same argument as in the proof
of Lem. 4.11 (c). As $S_{\\_}{1}=\langle x_{\\_}{1},y_{\\_}{1}\rangle$, we
have that $f^{\prime}(s_{\\_}{1})=f(s_{\\_}{1})$, since they are both
isomorphisms on the socle by Prop. 4.12. Spoiler now pebbles
$(x_{\\_}{1},y_{\\_}{1})\mapsto(f^{\prime}(x_{\\_}{1}),f^{\prime}(y_{\\_}{1}))$.
As the pebbled map
$(g,x_{\\_}{1},y_{\\_}{1},gs_{\\_}{1}g^{-1})\mapsto(f(g),f^{\prime}(x_{\\_}{1}),f^{\prime}(y_{\\_}{1}),f^{\prime}(gs_{\\_}{1}g^{-1}))$
does not extend to an isomorphism, Spoiler wins. In this case, Spoiler used at
most $8$ pebbles and $7$ rounds.

Note that the ninth pebble is the one we pick up prior to checking the winning
condition. ∎

##  5 Conclusion

We exhibited a novel Weisfeiler–Leman algorithm that provides an algorithmic
characterization of the second Ehrenfeucht–Fraïssé game in Hella’s [42, 43]
hierarchy. We also showed that this Ehrenfeucht–Fraïssé game can identify
groups without Abelian normal subgroups using $O(1)$ pebbles and $O(1)$
rounds. In particular, within the first few rounds, Spoiler can force
Duplicator to select an isomorphism at each subsequent round. This effectively
solves the search problem in the pebble game characterization.

Our work leaves several directions for further research.

######  Question 5.1.

Can the constant-dimensional $2$-ary Wesifeiler–Leman algorithm be implemented
in time $n^{o(\log n)}$?

######  Question 5.2.

What is the (1-ary) Weisfeiler–Leman dimension of groups without Abelian
normal subgroups?

######  Question 5.3.

Show that the second Ehrenfeucht–Fraïssé game in Hella’s hierarchy can
identify coprime extensions of the form $H\ltimes N$ with both $H,N$ Abelian
(the analogue of [63]). More generally, an analogue of Babai–Qiao [10] would
be to show that when $|H|,|N|$ are coprime and $N$ is Abelian, that Spoiler
can distinguish $H\ltimes N$ from any non-isomorphic group using a constant
number of pebbles that is no more than that which is required to identify $H$
(or the maximum of that of $H$ and a constant independent of $N,H$).

######  Question 5.4.

Let $p>2$ be prime, and let $G$ be a $p$-group with bounded genus. Show that
in the second Ehrenfeucht–Fraïssé game in Hella’s hierarchy, Spoiler has a
winning strategy using a constant number of pebbles. This is a descriptive
complexity analogue of [16, 47]. It would even be of interest to start with
the case where $G$ has bounded genus over a field extension
$K/\mathbb{F}_{\\_}{p}$ of bounded degree.

In the setting of groups, Hella’s hierarchy collapses to some $q\leq 3$, since
3-ary WL can identify all ternary relational structures, including groups. It
remains open to determine whether this hierarchy collapses further to either
$q=1$ or $q=2$. Even if it does not collapse, it would also be of interest to
determine whether the $1$-ary and $2$-ary games are equivalent.
Algorithmically, this is equivalent to determining whether $1$-ary and $2$-ary
WL are have the same distinguishing power.

######  Question 5.5.

Does there exist an infinite family of non-isomorphic pairs of groups
$\\{(G_{\\_}{n},H_{\\_}{n})\\}$ for which Spoiler requires $\omega(1)$ pebbles
to distinguish $G_{\\_}{n}$ from $H_{\\_}{n}$? We ask this question for the
Ehrenfeucht–Fraïssé games at both the first and second levels of Hella’s
hierarchy.

Recall that the game at the first level of Hella’s hierarchy is equivalent to
Weisfeiler–Leman [18, 42, 43], and so a lower bound against either of these
games provides a lower bound against Weisfeiler–Leman. More generally, it
would also be of interest to investigate Hella’s hierarchy on higher arity
structures. For a $q$-ary relational structure, the $q$-ary pebble game
suffices to decide isomorphism. Are there interesting, natural classes of
higher arity structures for which Hella’s hierarchy collapses further to some
level $q^{\prime}<q$?

## Acknowledgment

The authors would like to thank Pascal Schweitzer and the anonymous referees
for feedback on earlier versions of some of the results in this paper, as well
as discussions more directly relevant to the paper. JAG would like to thank
Martin Grohe for helpful correspondence about WL versus “oblivious WL.” JAG
was partially supported by NSF award DMS-1750319 and NSF CAREER award
CCF-2047756 and during this work. ML was partially supported by J. Grochow
startup funds, NSF award CISE-2047756, and a Summer Research Fellowship
through the Department of Computer Science at the University of Colorado
Boulder.

## References

  * [1]
  * [2] Miklos Ajtai & Ronald Fagin (1990): _Reachability is harder for directed than for undirected finite graphs_.  Journal of Symbolic Logic 55(1), p. 113–150, 10.2307/2274958.
  * [3] Sanjeev Arora & Ronald Fagin (1997): _On winning strategies in Ehrenfeucht–Fraïssé games_.  Theoretical Computer Science 174(1), pp. 97–121, 10.1016/S0304-3975(96)00015-1.
  * [4] V. Arvind & Piyush P. Kurur (2006): _Graph Isomorphism is in SPP_.  Information and Computation 204(5), pp. 835–852, 10.1016/j.ic.2006.02.002.
  * [5] László Babai (2016): _Graph isomorphism in quasipolynomial time [extended abstract]_.  In: STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, pp. 684–697, 10.1145/2897518.2897542.  Preprint of full version at arXiv:1512.03547v2 [cs.DS].
  * [6] László Babai & Robert Beals (1999): _A polynomial-time theory of black box groups I_.  In: Groups St Andrews 1997 in Bath, I, 10.1017/CBO9781107360228.004.
  * [7] László Babai, Robert Beals & Ákos Seress (2009): _Polynomial-Time Theory of Matrix Groups_.  In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, Association for Computing Machinery, p. 55–64, 10.1145/1536414.1536425.
  * [8] László Babai, Paolo Codenotti, Joshua A. Grochow & Youming Qiao (2011): _Code equivalence and group isomorphism_.  In: Proceedings of the Twenty-Second Annual ACM–SIAM Symposium on Discrete Algorithms (SODA11), SIAM, Philadelphia, PA, pp. 1395–1408, 10.1137/1.9781611973082.107.
  * [9] László Babai, Paolo Codenotti & Youming Qiao (2012): _Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract)_.  In: International Colloquium on Automata, Languages, and Programming (ICALP), pp. 51–62, 10.1007/978-3-642-31594-75.
  * [10] László Babai & Youming Qiao (2012): _Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers_.  In: 29th STACS, Springer LNCS 6651, pp. 453 – 464, 10.4230/LIPIcs.STACS.2012.453.
  * [11] Hans Ulrich Besche & Bettina Eick (1999): _Construction of finite groups_.  J. Symb. Comput. 27(4), pp. 387–404, 10.1006/jsco.1998.0258.
  * [12] Hans Ulrich Besche, Bettina Eick & E.A. O’Brien (2002): _A Millennium Project: Constructing Small Groups_.  Intern. J. Alg. and Comput 12, pp. 623–644, 10.1142/S0218196702001115.
  * [13] Jendrik Brachter & Pascal Schweitzer (2020): _On the Weisfeiler–Leman Dimension of Finite Groups_.  In Holger Hermanns, Lijun Zhang, Naoki Kobayashi & Dale Miller, editors: LICS ’20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020, ACM, pp. 287–300, 10.1145/3373718.3394786.
  * [14] Jendrik Brachter & Pascal Schweitzer (2021): _A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler–Leman Dimension_.  arXiv:2111.11908 [math.GR].
  * [15] Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao & James B. Wilson (2019): _Incorporating Weisfeiler–Leman into algorithms for group isomorphism_.  arXiv:1905.02518 [cs.CC].
  * [16] Peter A. Brooksbank, Joshua Maglione & James B. Wilson (2017): _A fast isomorphism test for groups whose Lie algebra has genus 2_.  Journal of Algebra 473, pp. 545–590, 10.1016/j.jalgebra.2016.12.007.
  * [17] Harry Buhrman & Steven Homer (1992): _Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy_.  In R. K. Shyamasundar, editor: Foundations of Software Technology and Theoretical Computer Science, 12th Conference, New Delhi, India, December 18-20, 1992, Proceedings, Lecture Notes in Computer Science 652, Springer, pp. 116–127, 10.1007/3-540-56287-7_99.
  * [18] Jin-Yi Cai, Martin Fürer & Neil Immerman (1992): _An optimal lower bound on the number of variables for graph identification_.  Combinatorica 12(4), pp. 389–410, 10.1007/BF01305232.  Originally appeared in SFCS ’89.
  * [19] John J. Cannon & Derek F. Holt (2003): _Automorphism group computation and isomorphism testing in finite groups_.  J. Symb. Comput. 35, pp. 241–267, 10.1016/S0747-7171(02)00133-5.
  * [20] Arkadev Chattopadhyay, Jacobo Torán & Fabian Wagner (2013): _Graph isomorphism is not $\rm AC^{0}$-reducible to group isomorphism_.  ACM Trans. Comput. Theory 5(4), pp. Art. 13, 13, 10.1145/2540088.  Preliminary version appeared in FSTTCS ’10; ECCC Tech. Report TR10-117.
  * [21] Bireswar Das & Shivdutt Sharma (2019): _Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes_.  In René van Bevern & Gregory Kucherov, editors: Computer Science – Theory and Applications, Springer International Publishing, Cham, pp. 80–92, 10.1007/s00224-020-10010-z.
  * [22] Anuj Dawar & Bjarki Holm (2012): _Pebble Games with Algebraic Rules_.  In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts & Roger Wattenhofer, editors: Automata, Languages, and Programming, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 251–262, 10.1007/978-3-642-31585-525.
  * [23] Anuj Dawar & Danny Vagnozzi (2020): _Generalizations of k-dimensional Weisfeiler–Leman stabilization_.  Moscow Journal of Combinatorics and Number Theory 9, pp. 229–252, 10.2140/moscow.2020.9.229.
  * [24] Heiko Dietrich & James B. Wilson (2022): _Polynomial-time isomorphism testing for groups of most finite orders_ , 10.1109/FOCS52979.2021.00053.
  * [25] A. Ehrenfeucht (1960/61): _An application of games to the completeness problem for formalized theories_.  Fund. Math. 49, pp. 129–141, 10.4064/fm-49-2-129-141.
  * [26] Bettina Eick, C. R. Leedham-Green & E. A. O’Brien (2002): _Constructing automorphism groups of $p$-groups_.  Comm. Algebra 30(5), pp. 2271–2295, 10.1081/AGB-120003468.
  * [27] Jörg Flum & Martin Grohe (2000): _On Fixed-Point Logic with Counting_.  The Journal of Symbolic Logic 65(2), pp. 777–787, 10.2307/2586569.
  * [28] Roland Fraïssé (1954): _Sur quelques classifications des systèmes de relations_.  Publ. Sci. Univ. Alger. Sér. A 1, pp. 35–182 (1955).
  * [29] Walid Gomaa (2010): _Descriptive Complexity of Finite Abelian Groups._ IJAC 20, pp. 1087–1116, 10.1142/S0218196710006047.
  * [30] Joshua A. Grochow & Michael Levet (2022): _On the Descriptive Complexity of Groups without Abelian Normal Subgroups_.  arXiv:https://arxiv.org/abs/2209.13725.
  * [31] Joshua A. Grochow & Michael Levet (2022): _On the parallel complexity of Group Isomorphism and canonization via Weisfeiler–Leman_.  arXiv:2112.11487 [cs.DS].
  * [32] Joshua A. Grochow & Youming Qiao (2015): _Polynomial-Time Isomorphism Test of Groups that are Tame Extensions - (Extended Abstract)_.  In: Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, pp. 578–589, 10.1007/978-3-662-48971-049.
  * [33] Martin Grohe (2017): _Descriptive complexity, canonisation, and definable graph structure theory_.  Lecture Notes in Logic 47, Association for Symbolic Logic, Ithaca, NY; Cambridge University Press, Cambridge, 10.1017/9781139028868.
  * [34] Martin Grohe (2021): _The logic of graph neural networks_.  In: LICS ’21: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 10.1109/LICS52264.2021.9470677.  Preprint arXiv:2104.14624 [cs.LG].
  * [35] Martin Grohe & Sandra Kiefer (2019): _A Linear Upper Bound on the Weisfeiler–Leman Dimension of Graphs of Bounded Genus_.  arXiv:https://arxiv.org/abs/1904.07216.
  * [36] Martin Grohe & Sandra Kiefer (2021): _Logarithmic Weisfeiler–Leman Identifies All Planar Graphs_.  arXiv:https://arxiv.org/abs/2106.16218.
  * [37] Martin Grohe & Daniel Neuen (2019): _Canonisation and Definability for Graphs of Bounded Rank Width_.  arXiv:https://arxiv.org/abs/1901.10330.
  * [38] Martin Grohe & Martin Otto (2015): _Pebble Games and linear equations_.  J. Symb. Log. 80(3), pp. 797–844, 10.1017/jsl.2015.28.
  * [39] Martin Grohe & Oleg Verbitsky (2006): _Testing Graph Isomorphism in Parallel by Playing a Game_.  In Michele Bugliesi, Bart Preneel, Vladimiro Sassone & Ingo Wegener, editors: Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, Lecture Notes in Computer Science 4051, Springer, pp. 3–14, 10.1007/117869862.
  * [40] Xiaoyu He & Youming Qiao (2021): _On the Baer–Lovász–Tutte construction of groups from graphs: Isomorphism types and homomorphism notions_.  Eur. J. Combin. 98, p. 103404, 10.1016/j.ejc.2021.103404.
  * [41] Hermann Heineken & Hans Liebeck (1974): _The occurrence of finite groups in the automorphism group of nilpotent groups of class $2$_.  Arch. Math. (Basel) 25, pp. 8–16, 10.1007/BF01238631.
  * [42] Lauri Hella (1989): _Definability hierarchies of generalized quantifiers_.  Annals of Pure and Applied Logic 43(3), pp. 235 – 271, 10.1016/0168-0072(89)90070-5.
  * [43] Lauri Hella (1996): _Logical Hierarchies in PTIME_.  Information and Computation 129(1), pp. 1–19, 10.1006/inco.1996.0070.
  * [44] Neil Immerman (1986): _Relational Queries Computable in Polynomial Time_.  Inf. Control. 68(1-3), pp. 86–104, 10.1016/S0019-9958(86)80029-8.
  * [45] Neil Immerman & Eric Lander (1990): _Describing Graphs: A First-Order Approach to Graph Canonization_.  In Alan L. Selman, editor: Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, Springer New York, New York, NY, pp. 59–81, 10.1007/978-1-4612-4478-35.
  * [46] Russell Impagliazzo, Ramamohan Paturi & Francis Zane (2001): _Which Problems Have Strongly Exponential Complexity?_ Journal of Computer and System Sciences 63(4), pp. 512–530, 10.1006/jcss.2001.1774.
  * [47] Gábor Ivanyos & Youming Qiao (2019): _Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing_.  SIAM J. Comput. 48(3), pp. 926–963, 10.1137/18M1165682.
  * [48] T. Kavitha (2007): _Linear time algorithms for Abelian group isomorphism and related problems_.  Journal of Computer and System Sciences 73(6), pp. 986 – 996, 10.1016/j.jcss.2007.03.013.
  * [49] Neeraj Kayal & Timur Nezhmetdinov (2009): _Factoring Groups Efficiently_.  In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas & Wolfgang Thomas, editors: Automata, Languages and Programming, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 585–596, 10.1007/978-3-642-02927-149.
  * [50] Sandra Kiefer & Brendan D. McKay (2020): _The Iteration Number of Colour Refinement_.  In Artur Czumaj, Anuj Dawar & Emanuela Merelli, editors: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), LIPIcs 168, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 73:1–73:19, 10.4230/LIPIcs.ICALP.2020.73.
  * [51] Sandra Kiefer, Ilia Ponomarenko & Pascal Schweitzer (2019): _The Weisfeiler–Leman Dimension of Planar Graphs Is at Most 3_.  J. ACM 66(6), 10.1145/3333003.
  * [52] Sandra Kiefer, Pascal Schweitzer & Erkal Selman (2022): _Graphs Identified by Logics with Counting_.  ACM Trans. Comput. Log. 23(1), pp. 1:1–1:31, 10.1145/3417515.
  * [53] Johannes Köbler, Uwe Schöning & Jacobo Torán (1992): _Graph Isomorphism is Low for PP_.  Comput. Complex. 2, pp. 301–330, 10.1007/BF01200427.
  * [54] Richard E. Ladner (1975): _On the Structure of Polynomial Time Reducibility_.  J. ACM 22(1), p. 155–171, 10.1145/321864.321877.
  * [55] François Le Gall (2009): _Efficient Isomorphism Testing for a Class of Group Extensions_.  In: Proc. 26th STACS, pp. 625–636, 10.4230/LIPIcs.STACS.2009.1830.
  * [56] François Le Gall & David J. Rosenbaum (2016): _On the Group and Color Isomorphism Problems_.  arXiv:1609.08253 [cs.CC].
  * [57] Mark L. Lewis & James B. Wilson (2012): _Isomorphism in expanding families of indistinguishable groups_.  Groups - Complexity - Cryptology 4(1), pp. 73–110, 10.1515/gcc-2012-0008.
  * [58] P. Lindstrom (1966): _First Order Predicate Logic with Generalized Quantifiers_.  Theoria 32(3), pp. 186–195, 10.1111/j.1755-2567.1966.tb00600.x.
  * [59] Alan H. Mekler (1981): _Stability of Nilpotent Groups of Class 2 and Prime Exponent_.  The Journal of Symbolic Logic 46(4), pp. 781–788, 10.2307/2273227.  Available at http://www.jstor.org/stable/2273227.
  * [60] Gary L. Miller (1978): _On the $n^{\log n}$ Isomorphism Technique (A Preliminary Report)_.  In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, Association for Computing Machinery, New York, NY, USA, pp. 51–58, 10.1145/800133.804331.
  * [61] Andrzej Mostowski (1957): _On a generalization of quantifiers_.  Fundamenta Mathematicae 44(1), pp. 12–36, 10.4064/fm-44-1-12-36.  Available at http://eudml.org/doc/213418.
  * [62] André Nies & Katrin Tent (2017): _Describing finite groups by short first-order sentences_.  Israel J. Math. 221(1), pp. 85–115, 10.1007/s11856-017-1563-2.
  * [63] Youming Qiao, Jayalal M. N. Sarma & Bangsheng Tang (2011): _On Isomorphism Testing of Groups with Normal Hall Subgroups_.  In: Proc. 28th STACS, pp. 567–578, 10.4230/LIPIcs.STACS.2011.567.
  * [64] David J. Rosenbaum (2013): _Bidirectional Collision Detection and Faster Deterministic Isomorphism Testing_.  arXiv:1304.3935 [cs.DS].
  * [65] Benjamin Rossman (2009): _Ehrenfeucht–Fraïssé Games on Random Structures_.  In Hiroakira Ono, Makoto Kanazawa & Ruy J. G. B. de Queiroz, editors: Logic, Language, Information and Computation, 16th International Workshop, WoLLIC 2009, Tokyo, Japan, June 21-24, 2009. Proceedings, Lecture Notes in Computer Science 5514, Springer, pp. 350–364, 10.1007/978-3-642-02261-628.
  * [66] C. Savage (1980): _An $O(n^{2})$ Algorithm for Abelian Group Isomorphism_.  Technical Report, North Carolina State University.
  * [67] Uwe Schöning (1988): _Graph isomorphism is in the low hierarchy_.  Journal of Computer and System Sciences 37(3), pp. 312 – 323, 10.1016/0022-0000(88)90010-4.
  * [68] Moshe Y. Vardi (1982): _The Complexity of Relational Query Languages (Extended Abstract)_.  In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard & Lawrence H. Landweber, editors: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, ACM, pp. 137–146, 10.1145/800070.802186.
  * [69] Narayan Vikas (1996): _An $O(n)$ Algorithm for Abelian $p$-Group Isomorphism and an $O(n\log n)$ Algorithm for Abelian Group Isomorphism_.  Journal of Computer and System Sciences 53(1), pp. 1–9, 10.1006/jcss.1996.0045.
  * [70] James B. Wilson (2012): _Existence, algorithms, and asymptotics of direct product decompositions, I_.  Groups - Complexity - Cryptology 4(1), 10.1515/gcc-2012-0007.
  * [71] James B. Wilson (2019): _The Threshold for Subgroup Profiles to Agree is Logarithmic_.  Theory of Computing 15(19), pp. 1–25, 10.4086/toc.2019.v015a019.
  * [72] V. N. Zemlyachenko, N. M. Korneenko & R. I. Tyshkevich (1985): _Graph isomorphism problem_.  J. Soviet Math. 29(4), pp. 1426–1481, 10.1007/BF02104746.