Combinatorial Approaches to the Group Isomorphism Problem
Jendrik Brachter
The isomorphism problem of finite groups, that is, the task of deciding whether two given finite groups are isomorphic, is one of the most fundamental problems in computational group theory for which we currently do not have efficient algorithmic tools. This is equally true in practical applications, as well as in terms of computational complexity: in the general case, apart from minor improvements, we are essentially stuck with an upper bound of n^O(log n) (obtained from enumerating all (log n)-sized generating sets), where n is the group order. On the other hand, there are currently no substantial lower bounds.
In this thesis, we develop new algorithmic perspectives on the group isomorphism problem. We define and analyze a series of combinatorial algorithms in the context of finite groups, and in fact arbitrary relational structures. More precisely, we study the k-dimensional WL-algorithm} (k-WL) for natural numbers k, which is an essential tool for the graph isomorphism problem. It is a crucial subroutine in all state-of-the-art graph isomorphism solvers, and it forms an important building block in Babai’s break-through quasi-polynomial time (n^O((log n)^c)) algorithm for graph isomorphism. It is a combinatorial algorithm with a runtime of n^O(k), that assigns canonical colorings to graphs. It thereby serves as a non-isomorphism test, with important connections to logic, games, and graph structure theory.
Our first contribution is the generalization of the WL-algorithm from graphs to relational structures, in terms of three potentially different versions of the WL. We compare these versions, showing that they can be placed in a hierarchy of distinguishing powers. The general result that we prove is that each version is natural under a certain point of view (and can be characterized by a corresponding logic), but asymptotically, it does not matter which version of WL we work with.
In particular, we obtain an asymptotically robust notion of the Weisfeiler-Leman dimension for relational structures, which denotes the smallest natural number k, such that the k-dimensional WL-algorithm identifies a given structure up to isomorphism. This allows us to subsequently initiate a descriptive complexity theory of finite groups, where we propose the Weisfeiler-Leman dimension as a natural measure of complexity.
We construct a compendium of structural properties and group theoretic constructions that are detectable via a low-dimensional Weisfeiler-Leman algorithm. This includes various major building blocks of group theory, for example, we show that groups share the same multiset of composition factors if they are indistinguishable via 5-WL. We also provide a framework that allows one to easily extend and adapt our results to other group theoretic properties. We thereby uncover far-reaching connections between the WL-dimension and the structure of a finite group, and we provide an effective tool-kit to analyze the WL-algorithm on groups and related algebraic structures.
We then employ these tools to derive upper bounds on the WL-dimension of several important group classes. For instance, we show that the WL-dimension of coprime extensions of abelian groups and the WL-dimension of semisimple groups are both bounded by O(log log n). We also identify several natural group classes of bounded WL-dimension.
Finally, we discuss lower bounds in two ways: first, we provide explicit examples that certify Weisfeiler-Leman indistinguishability for small dimensions, and second, we devise combinatorial reductions that asymptotically preserve the WL-dimension. The latter provides potential sources for groups of unbounded Weisfeiler-Leman dimension.