一句话：证明无阿贝尔正规子群的有限群可由 7 个 pebble、7 轮的 Hella 双射 pebble 博弈识别。
本文研究有限群的描述复杂度，考察 Hella 层级中第二 Ehrenfeucht–Fraïssé 双射 pebble 博弈的识别能力。该博弈每轮 Spoiler 可放至多两个 pebble；对图同构平凡，但对有限群等三元关系结构可能非平凡。作者提出 Weisfeiler–Leman 着色的推广 2-ary WL，并证明它等价于上述博弈。主要结果：对不含阿贝尔正规子群的群，仅需 O(1) 个 pebble 和 O(1) 轮即可识别，具体为 7 个 pebble 与 7 轮；Spoiler 能在前几轮迫使 Duplicator 在后续每轮选择同构。由 Hella 结果，该类群可由仅用 7 个变量、7 个量词深度的广义 2-ary 量词一阶逻辑公式识别。
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 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). We actually show that $7$ pebbles and $7$ rounds suffice. 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 $7$ variables and $7$ quantifier depth.
@article{paperbot3350,
title = {On the Descriptive Complexity of Groups without Abelian Normal Subgroups},
author = {Joshua A. Grochow and Michael Levet},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 4},
year = {2025},
doi = {10.46298/lmcs-21(4:20)2025}
}