On the Descriptive Complexity of Groups without Abelian Normal Subgroups

Basic Information

• Paper ID: 2209.13725
• Title: On the Descriptive Complexity of Groups without Abelian Normal Subgroups
• Authors: Joshua A. Grochow (University of Colorado Boulder), Michael Levet (College of Charleston)
• Classification: cs.LO (Logic in Computer Science), cs.CC (Computational Complexity), math.GR (Group Theory), math.LO (Mathematical Logic)
• Publication Date/Conference: Preliminary version published at GandALF 2023; full version submitted September 2022
• Paper Link: https://arxiv.org/abs/2209.13725

Abstract

This paper explores the descriptive complexity theory of finite groups by investigating the power of the second level of the Hella hierarchy through Ehrenfeucht-Fraïssé pebble games. This is a Spoiler-Duplicator game where Spoiler can place at most two pebbles per round. While this game trivially solves graph isomorphism, it may be non-trivial for finite groups and other ternary relational structures. The authors first provide a novel generalization of Weisfeiler-Leman (WL) coloring, called 2-ary WL, and then prove that 2-ary WL is equivalent to the second level Ehrenfeucht-Fraïssé pebble game in the Hella hierarchy. The main result is that in the pebble game characterization, O(1) pebbles and O(1) rounds suffice to identify all groups without abelian normal subgroups (for which isomorphism testing is known to be in P). Specifically, 7 pebbles and 7 rounds are sufficient.

Research Background and Motivation

1. Core Problem

The core problem addressed in this paper is understanding the descriptive complexity of finite groups, particularly through higher-order Ehrenfeucht-Fraïssé games and corresponding Weisfeiler-Leman algorithms to characterize the complexity of group isomorphism problems.

2. Problem Significance

• Theoretical Significance: The group isomorphism problem is a fundamental problem in computational complexity theory, considered a candidate for NP-intermediate problems
• Practical Applications: Group isomorphism testing has important applications in computer algebra systems
• Methodological Value: Descriptive complexity theory provides important tools for understanding the relationship between algorithms and logic

3. Limitations of Existing Methods

• The discriminating power of the classical 1-ary Weisfeiler-Leman algorithm for groups remains unclear
• Although polynomial-time algorithms exist for specific group classes, the best known algorithm for general group isomorphism remains exponential-time
• Research on descriptive complexity of groups is relatively sparse compared to the case of graphs

4. Research Motivation

• Groups are ternary relational structures (with relation {(a,b,c) : ab = c}), so 2-ary games may provide non-trivial insights
• Groups without abelian normal subgroups are important both theoretically and practically, and their isomorphism testing is known to be in P
• Establishing equivalences between games, logic, and algorithms

Core Contributions

1. Proposed 2-ary Weisfeiler-Leman coloring algorithm: A novel generalization of the classical WL algorithm applicable to higher-order games
2. Established equivalence theorem: Proved that 2-ary WL is equivalent to the second level Ehrenfeucht-Fraïssé pebble game in the Hella hierarchy
3. Main theoretical result: Proved that 7 pebbles and 7 rounds suffice to identify all groups without abelian normal subgroups
4. Technical innovation: During the game, Spoiler can force Duplicator to choose an isomorphism in subsequent rounds
5. Logical characterization: Equivalently, these groups can be identified by first-order logic formulas with generalized 2-ary quantifiers

Methodology Details

Task Definition

Given two finite groups G and H, determine whether they are isomorphic through 2-ary Ehrenfeucht-Fraïssé games or equivalently through 2-ary WL coloring. In the game, Spoiler attempts to prove the two groups are non-isomorphic, while Duplicator attempts to maintain the illusion that they could be isomorphic.

Model Architecture

2-ary WL Coloring Algorithm

For k-dimensional 2-ary WL, the algorithm maintains colorings on k-tuples of group elements:

1. Initial Coloring:
   • Version I: Based on partial isomorphism relations
   • Version II: Based on marked isomorphism relations
2. Coloring Refinement: For each k-tuple x, construct edge-colored graphs Γ_{x,χ,i,j}:
   • When i = j: Self-loop graph on the group, each self-loop (g,g) colored by χ(x_{i←g})
   • When i ≠ j: Complete directed graph, each edge (y,z) colored by χ(x_{(i,j)←(y,z)})
3. New Coloring: R(χ)(x) = (χ(x); Γ_{x,χ,1,1}, Γ_{x,χ,1,2}, ..., Γ_{x,χ,k,k})

Game Rules

Each round of the game consists of the following steps:

1. Spoiler selects which pebble to move
2. Duplicator selects a bijection f : G → H
3. Spoiler places at most 2 pebbles
4. Check winning condition (whether there exists a mapping extending to an isomorphism)

Technical Innovations

1. Weight Concept

Defined the weight wt(s) of group elements to track element complexity in socle decomposition:

• For s ∈ Soc(G) = S_1 × ... × S_k, weight equals the number of non-identity components
• Weight preservation is an important constraint Duplicator must satisfy

2. Forced Isomorphism Strategy

Force Duplicator to choose an isomorphism through the following steps:

1. Identify socle structure
2. Force weight preservation
3. Ensure correct mapping of simple factors
4. Verify compatibility of conjugation actions

3. Case-by-Case Analysis

Employ fine-grained case analysis for different situations:

• Whether the group is semisimple
• Compatibility of socle structures
• Equivalence of permutation representations

Experimental Setup

This paper is purely theoretical work and contains no experimental section. All results are derived through rigorous mathematical proofs.

Experimental Results

Main Theoretical Results

Theorem 1.1 (Main Result): Let G be a group without abelian normal subgroups and H be an arbitrary group. If G ≄ H, then Spoiler has a winning strategy in the Ehrenfeucht-Fraïssé game at the second level of the Hella hierarchy using 7 pebbles and 7 rounds.

Key Lemmas and Propositions

1. Proposition 4.5: If G is semisimple and H is not, then Spoiler can win in the (3,2)-WL²_II game
2. Lemma 4.6: Duplicator must map direct factors of Soc(G) to isomorphic direct factors of Soc(H)
3. Proposition 4.13: Under appropriate pebble configurations, Duplicator must choose a bijection that is an isomorphism on the socle
4. Theorem 4.17: Complete 7-pebble 7-round result

Version Equivalence

Theorem 3.6: (k,r)-WL²_I ⪯ (k,r)-WL²_II ⪯ (k+2,r+1)-WL²_I

This shows the two versions are equivalent within constant factors.

Related Work

Descriptive Complexity Theory

• Pioneering work by Immerman and Lander established connections between logic, games, and algorithms
• Cai, Fürer, and Immerman proved that WL cannot solve general graph isomorphism
• Hella introduced higher-order quantifiers and corresponding game hierarchies

Group Isomorphism Algorithms

• Work by Babai, Codenotti, and Qiao proved that isomorphism testing for groups without abelian normal subgroups is in P
• Polynomial-time algorithms for various special group classes
• Brachter and Schweitzer introduced WL to group isomorphism research

Weisfeiler-Leman Algorithm

• Applications and limitations in graph isomorphism
• Connections to linear programming Sherali-Adams hierarchy
• Recent developments in group theory

Conclusions and Discussion

Main Conclusions

1. Algorithm Equivalence: Established equivalence between 2-ary WL coloring and Hella second-level games
2. Constant Bounds: Proved that groups without abelian normal subgroups can be identified using constant pebbles and rounds
3. Constructive Proof: Provided concrete game strategies that not only prove distinguishability but also explain how to distinguish

Limitations

1. Group Class Restriction: Results apply only to groups without abelian normal subgroups
2. Dependence on CFSG: Relies on the Classification of Finite Simple Groups through 2-generation of simple groups
3. Large Constants: Although constant, 7 pebbles and 7 rounds may be large in practice
4. General Groups: WL dimension for general groups remains unknown

Future Directions

The paper proposes several open problems:

1. Can 2-ary WL algorithm be implemented in n^{o(log n)} time
2. 1-ary WL dimension for groups without abelian normal subgroups
3. Extension to other group classes (e.g., coprime extensions)
4. Bounded genus p-groups
5. Whether the Hella hierarchy collapses on groups

In-Depth Evaluation

Strengths

1. Theoretical Depth: Establishes profound connections between games, logic, and algorithms
2. Technical Innovation: The definition and analysis of 2-ary WL is original
3. Proof Techniques: Employs sophisticated group-theoretic and game-theoretic techniques
4. Completeness: Provides complete equivalence proofs and concrete bounds
5. Writing Quality: Paper is well-structured with sufficient technical detail

Weaknesses

1. Limited Scope: Restricted to specific group classes with limited generalizability
2. Practical Applicability: Theoretical results lacking actual algorithm implementation and performance analysis
3. Constant Optimization: The bound of 7 pebbles and 7 rounds may not be optimal
4. Missing Lower Bounds: No corresponding lower bound results provided

Impact

1. Theoretical Contribution: Establishes important foundations for descriptive complexity theory of groups
2. Methodological Value: The 2-ary WL method may apply to other algebraic structures
3. Open Problems: Proposes valuable directions for future research
4. Interdisciplinary: Connects logic, complexity theory, and group theory

Applicable Scenarios

1. Theoretical Research: Provides new tools for studying complexity of group isomorphism
2. Algorithm Design: Offers theoretical guidance for designing new group isomorphism algorithms
3. Computer Algebra: Potential applications in computer algebra systems
4. Descriptive Complexity: Provides template for studying other algebraic structures

References

The paper cites extensive relevant literature, including:

• Hella's original work establishing quantifier hierarchies
• Series of works by Babai et al. on group isomorphism algorithms
• Pioneering research by Brachter and Schweitzer on WL algorithms for groups
• Classical literature in descriptive complexity theory
• Relevant background in group theory and algebra

This paper makes important contributions at the intersection of theoretical computer science and group theory, providing new perspectives and tools for understanding the descriptive complexity of group isomorphism problems. While results apply only to specific group classes, the methods and techniques have broad potential applications.