Algebraic Interpretation of the Weisfeiler–Leman Algorithm: Schur Ring Analysis of Direct Power Groups

In this paper, we explore the algebraic interpretation of the partitioning obtained by the 𝑚-dimensional Weisfeiler–Leman algorithm on the direct power G^m of a finite group G. We define and study a Schur ring over G^m, which provides insights into the structure of the group G. Our analysis reveals that this ring determines the group G up to isomorphism when m≥3. Furthermore, we demonstrate that as m increases, the Schur ring associated with the group of automorphisms of G acting on G^m emerges naturally. Surprisingly, we establish that finding the limit ring is polynomial-time equivalent to solving the group isomorphism problem. This paper presents a novel algebraic framework for understanding the behavior of the Weisfeiler–Leman algorithm and its implications for group theory and computational complexity.

Keywords: Schur ring, Weisfeiler–Leman algorithm, algebraic interpretation, computational complexity., direct power groups, group isomorphism