2025-11-11T14:25:09.393579

On the Descriptive Complexity of Groups without Abelian Normal Subgroups

Grochow, Levet

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.

academic

On the Descriptive Complexity of Groups without Abelian Normal Subgroups

基本信息

论文ID: 2209.13725
标题: On the Descriptive Complexity of Groups without Abelian Normal Subgroups
作者: Joshua A. Grochow (University of Colorado Boulder), Michael Levet (College of Charleston)
分类: cs.LO (Logic in Computer Science), cs.CC (Computational Complexity), math.GR (Group Theory), math.LO (Mathematical Logic)
发表时间/会议: 初步版本发表于 GandALF 2023，完整版本提交于 2022年9月
论文链接: https://arxiv.org/abs/2209.13725

摘要

本文通过研究Hella层次结构中第二层Ehrenfeucht-Fraïssé双射卵石博弈的能力来探索有限群的描述复杂性理论。这是一个Spoiler-Duplicator博弈，其中Spoiler每轮可以放置最多两个卵石。虽然该博弈可以平凡地解决图同构问题，但对于有限群和其他三元关系结构可能是非平凡的。作者首先提供了Weisfeiler-Leman(WL)着色的新颖推广，称为2-ary WL，然后证明了2-ary WL等价于Hella层次结构中的第二层Ehrenfeucht-Fraïssé双射卵石博弈。主要结果是在卵石博弈刻画中，仅需要O(1)个卵石和O(1)轮就足以识别所有无阿贝尔正规子群的群（这类群的同构测试已知在P中）。具体地，7个卵石和7轮就足够了。

研究背景与动机

1. 核心问题

本文要解决的核心问题是理解有限群的描述复杂性，特别是通过高阶Ehrenfeucht-Fraïssé博弈和相应的Weisfeiler-Leman算法来刻画群同构问题的复杂性。

2. 问题重要性

理论意义: 群同构问题是计算复杂性理论中的一个基本问题，被认为是NP-intermediate问题的候选者
实际应用: 群同构测试在代数计算系统中有重要应用
方法论价值: 描述复杂性理论为理解算法和逻辑之间的关系提供了重要工具

3. 现有方法局限性

经典的1-ary Weisfeiler-Leman算法对于群的区分能力尚不清楚
虽然存在针对特定群类的多项式时间算法，但一般情况下群同构问题的最佳算法仍然是指数时间的
对于群的描述复杂性研究相对匮乏，与图的情况形成对比

4. 研究动机

群是三元关系结构（关系为{(a,b,c) : ab = c}），因此2-ary博弈可能提供非平凡的洞察
无阿贝尔正规子群的群类在理论和实践中都很重要，且已知其同构测试在P中
建立博弈、逻辑和算法之间的等价关系

核心贡献

提出了2-ary Weisfeiler-Leman着色算法：这是对经典WL算法的新颖推广，适用于高阶博弈
建立了等价性定理：证明了2-ary WL等价于Hella层次结构中的第二层Ehrenfeucht-Fraïssé双射卵石博弈
主要理论结果：证明了7个卵石和7轮足以识别所有无阿贝尔正规子群的群
技术创新：在博弈过程中，Spoiler可以强制Duplicator在后续轮次中选择同构映射
逻辑刻画：等价地说明这些群可以被带有广义2-ary量词的一阶逻辑公式识别

方法详解

任务定义

给定两个有限群G和H，通过2-ary Ehrenfeucht-Fraïssé博弈或等价的2-ary WL着色来判断它们是否同构。博弈中Spoiler试图证明两个群不同构，而Duplicator试图维持它们可能同构的假象。

模型架构

2-ary WL着色算法

对于k维2-ary WL，算法维护群元素k-元组上的着色：

初始着色：
- Version I：基于偏同构关系
- Version II：基于标记同构关系
着色细化：对于每个k-元组x，构造边着色图Γ_{x,χ,i,j}：
- 当i = j时：在群上的自环图，每个自环(g,g)的颜色为χ(x_{i←g})
- 当i ≠ j时：完全有向图，每条边(y,z)的颜色为χ(x_{(i,j)←(y,z)})
新着色：R(χ)(x) = (χ(x); Γ_{x,χ,1,1}, Γ_{x,χ,1,2}, ..., Γ_{x,χ,k,k})