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

アーベル正規部分群を持たない群の記述複雑性について

基本情報

論文ID: 2209.13725
タイトル: On the Descriptive Complexity of Groups without Abelian Normal Subgroups
著者: Joshua A. Grochow (コロラド大学ボルダー校)、Michael Levet (チャールストン大学)
分類: cs.LO (計算機科学における論理)、cs.CC (計算複雑性)、math.GR (群論)、math.LO (数学論理)
発表時期/会議: 初版はGandALF 2023で発表、完全版は2022年9月投稿
論文リンク: https://arxiv.org/abs/2209.13725

要旨

本論文は、Hella階層構造における第2層のEhrenfeucht-Fraïssé二項石ゲームの能力を研究することを通じて、有限群の記述複雑性理論を探究する。これはSpoiler-Duplicatorゲームであり、各ラウンドでSpoilerは最大2つの石を配置できる。このゲームは自明に図同型問題を解くことができるが、有限群および他の3項関係構造に対しては非自明である可能性がある。著者らはまずWeisfeiler-Leman(WL)着色の新規な一般化である2-ary WLを提供し、その後、2-ary WLがHella階層構造の第2層Ehrenfeucht-Fraïssé二項石ゲームと等価であることを証明する。主要な結果は、石ゲームの特性化において、O(1)個の石とO(1)ラウンドがアーベル正規部分群を持たないすべての群を識別するのに十分であることを示す（このクラスの群の同型判定はPにあることが既知）。具体的には、7個の石と7ラウンドで十分である。

研究背景と動機

1. 核心問題

本論文が解決しようとする核心問題は、特に高階Ehrenfeucht-Fraïsséゲームと対応するWeisfeiler-Leman算法を通じて、有限群の記述複雑性、特に群同型問題の複雑性を特性化することである。

2. 問題の重要性

理論的意義: 群同型問題は計算複雑性理論における基本的な問題であり、NP-中間問題の候補と考えられている
実用的応用: 群同型判定は代数計算システムにおいて重要な応用を持つ
方法論的価値: 記述複雑性理論は、アルゴリズムと論理の関係を理解するための重要なツールを提供する

3. 既存方法の限界

古典的な1-ary Weisfeiler-Leman算法の群に対する区別能力は依然として不明確である
特定の群クラスに対する多項式時間算法は存在するが、一般的な場合、群同型問題に対する最良のアルゴリズムは依然として指数時間である
群の記述複雑性に関する研究は相対的に不足しており、図の場合と対照をなしている

4. 研究の動機

群は3項関係構造（関係は{(a,b,c) : ab = c}）であるため、2-aryゲームは非自明な洞察を提供する可能性がある
アーベル正規部分群を持たない群のクラスは理論的にも実践的にも重要であり、その同型判定がPにあることが既知である
ゲーム、論理、アルゴリズム間の等価性を確立する

核心的貢献

2-ary Weisfeiler-Leman着色算法の提案: 古典的なWL算法の新規な一般化であり、高階ゲームに適用可能
等価性定理の確立: 2-ary WLがHella階層構造の第2層Ehrenfeucht-Fraïssé二項石ゲームと等価であることを証明
主要な理論的結果: 7個の石と7ラウンドがアーベル正規部分群を持たないすべての群を識別するのに十分であることを証明
技術的革新: ゲーム過程において、Spoilerは後続ラウンドでDuplicatorが同型写像を選択することを強制できる
論理的特性化: 等価的に、これらの群は広義2-ary量詞を持つ1階論理式によって識別可能であることを示す

方法の詳細

タスク定義

2つの有限群GとHが与えられたとき、2-ary Ehrenfeucht-Fraïsséゲームまたは等価の2-ary WL着色を通じて、それらが同型であるかどうかを判定する。ゲームにおいて、Spoilerは2つの群が非同型であることを証明しようとし、Duplicatorはそれらが同型である可能性を維持しようとする。

モデルアーキテクチャ

2-ary WL着色算法

k次元2-ary WLに対して、算法は群元素のk-組上の着色を維持する：

初期着色:
- バージョンI: 部分同型関係に基づく
- バージョン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})