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 (University of Colorado Boulder), Michael Levet (College of Charleston)
분류: cs.LO (컴퓨터 과학의 논리), cs.CC (계산 복잡성), math.GR (군론), math.LO (수학 논리)
발표 시간/학회: GandALF 2023에서 예비 버전 발표, 2022년 9월 완전 버전 제출
논문 링크: https://arxiv.org/abs/2209.13725

초록

본 논문은 Hella 계층 구조의 두 번째 층에서 Ehrenfeucht-Fraïssé 이분 자갈 게임의 능력을 연구함으로써 유한 군의 기술적 복잡성 이론을 탐구한다. 이는 Spoiler가 매 라운드마다 최대 2개의 자갈을 놓을 수 있는 Spoiler-Duplicator 게임이다. 이 게임이 그래프 동형 문제를 자명하게 해결할 수 있지만, 유한 군과 다른 3진 관계 구조에 대해서는 비자명할 수 있다. 저자들은 먼저 Weisfeiler-Leman(WL) 색칠의 새로운 일반화인 2-진 WL을 제시한 후, 2-진 WL이 Hella 계층 구조의 두 번째 층 Ehrenfeucht-Fraïssé 이분 자갈 게임과 동치임을 증명한다. 주요 결과는 자갈 게임 특성화에서 O(1)개의 자갈과 O(1)라운드만으로 모든 아벨 정규 부분군이 없는 군을 식별하기에 충분하다는 것이다(이 군 클래스의 동형 판정은 P에 있는 것으로 알려져 있다). 구체적으로, 7개의 자갈과 7라운드로 충분하다.

연구 배경 및 동기

1. 핵심 문제

본 논문이 해결하고자 하는 핵심 문제는 유한 군의 기술적 복잡성, 특히 고차 Ehrenfeucht-Fraïssé 게임과 대응하는 Weisfeiler-Leman 알고리즘을 통해 군 동형 문제의 복잡성을 특성화하는 것을 이해하는 것이다.

2. 문제의 중요성

이론적 의의: 군 동형 문제는 계산 복잡성 이론의 기본 문제이며, NP-중간 문제의 후보로 여겨진다
실제 응용: 군 동형 판정은 대수 계산 시스템에서 중요한 응용을 가진다
방법론적 가치: 기술적 복잡성 이론은 알고리즘과 논리 사이의 관계를 이해하기 위한 중요한 도구를 제공한다

3. 기존 방법의 한계

고전적인 1-진 Weisfeiler-Leman 알고리즘의 군 구별 능력은 여전히 명확하지 않다
특정 군 클래스에 대한 다항식 시간 알고리즘이 존재하지만, 일반적인 경우 군 동형 문제의 최선 알고리즘은 여전히 지수 시간이다
군의 기술적 복잡성에 대한 연구는 상대적으로 부족하며, 그래프의 경우와 대조를 이룬다

4. 연구 동기

군은 3진 관계 구조(관계는 {(a,b,c) : ab = c})이므로, 2-진 게임이 비자명한 통찰력을 제공할 수 있다
아벨 정규 부분군이 없는 군 클래스는 이론과 실제 모두에서 중요하며, 그 동형 판정이 P에 있는 것으로 알려져 있다
게임, 논리 및 알고리즘 사이의 동치 관계 확립

핵심 기여

2-진 Weisfeiler-Leman 색칠 알고리즘 제시: 고차 게임에 적용 가능한 고전적 WL 알고리즘의 새로운 일반화
동치성 정리 확립: 2-진 WL이 Hella 계층 구조의 두 번째 층 Ehrenfeucht-Fraïssé 이분 자갈 게임과 동치임을 증명
주요 이론적 결과: 7개의 자갈과 7라운드가 모든 아벨 정규 부분군이 없는 군을 식별하기에 충분함을 증명
기술적 혁신: 게임 과정에서 Spoiler가 Duplicator를 강제하여 후속 라운드에서 동형 사상을 선택하도록 할 수 있다
논리적 특성화: 동등하게 이들 군이 일반화된 2-진 양화사를 가진 1차 논리 공식으로 식별될 수 있음을 명시

방법 상세 설명

작업 정의

두 개의 유한 군 G와 H가 주어졌을 때, 2-진 Ehrenfeucht-Fraïssé 게임 또는 동등한 2-진 WL 색칠을 통해 이들이 동형인지 판정한다. 게임에서 Spoiler는 두 군이 동형이 아님을 증명하려 하고, Duplicator는 이들이 동형일 가능성을 유지하려 한다.

모델 구조

2-진 WL 색칠 알고리즘

k-차원 2-진 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})