Count-Free Weisfeiler--Leman and Group Isomorphism

Abstract

We investigate the power of counting in Group Isomorphism. We first leverage the count-free variant of the Weisfeiler--Leman Version I algorithm for groups (Brachter & Schweitzer, LICS 2020) in tandem with limited non-determinism and limited counting to improve the parallel complexity of isomorphism testing for several families of groups. These families include: - Direct products of non-Abelian simple groups. - Coprime extensions, where the normal Hall subgroup is Abelian and the complement is an $O(1)$-generated solvable group with solvability class $\text{poly}\log \log n$. This notably includes instances where the complement is an $O(1)$-generated nilpotent group. This problem was previously known to be in $\text{P}$ (Qiao, Sarma, & Tang, STACS 2011), and the complexity was recently improved to $\text{L}$ (Grochow & Levet, FCT 2023). - Graphical groups of class $2$ and exponent $p>2$ (Mekler, J. Symb. Log., 1981) arising from the CFI and twisted CFI graphs (Cai, Fürer, & Immerman, Combinatorica 1992) respectively. In particular, our work improves upon previous results of Brachter & Schweitzer (LICS 2020). We finally show that the $q$-ary count-free pebble game is unable to distinguish even Abelian groups. This extends the result of Grochow & Levet (ibid), who established the result in the case of $q=1$. The general theme is that some counting appears necessary to place Group Isomorphism into $\text{P}$.

arXiv commentarXiv admin note: text overlap with arXiv:2112.11487