Algebraic Interpretation of the Weisfeiler–Leman Algorithm: Schur Ring Analysis of Direct Power Groups (Published)
In this paper, we explore the algebraic interpretation of the partitioning obtained by the 𝑚-dimensional Weisfeiler–Leman algorithm on the direct power Gm of a finite group G. We define and study a Schur ring over Gm, 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 Gm 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