Complexity of Minimal Faithful Permutation Degree for Fitting-free Groups

2025/01/27 by Levet, Michael, Srivastava, Pranjal, Thakkar, Dhara
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2501.16039

Abstract

In this paper, we investigate the complexity of computing the minimal faithful permutation degree for groups without abelian normal subgroups. When our groups are given as quotients of permutation groups, we establish that this problem is in \textsfP. Furthermore, in the setting of permutation groups, we obtain an upper bound of \textsfNC for this problem. This improves upon the work of Das and Thakkar (STOC 2024), who established a Las Vegas polynomial-time algorithm for this class in the setting of permutation groups.

Related

• Minimal Faithful Permutation Degrees for Irreducible Coxeter Groups and Binary Polyhedral Groups
• A Strict Inequality for a Minimal Degree of a Direct Product
• Minimal degrees for faithful permutation representations of groups of order p⁶ where p is an odd prime
• On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
• Magma Proof of Strict Inequalities for Minimal Degrees of Finite Groups