The Minimal Faithful Permutation Degree of Groups Without Abelian Normal Subgroups

SIAM Journal on Computing 2026

View at publisher
Authors: Bireswar Das, Dhara Thakkar
DOI: 10.1137/24m1685353
Cited by: 0
References: 33

Abstract

Abstract. The minimal faithful permutation degree [Formula: see text] of a finite group [Formula: see text] is the smallest integer [Formula: see text] for which there is an injective homomorphism [Formula: see text] from [Formula: see text] to [Formula: see text]. The main result of this paper is a randomized polynomial-time algorithm for computing the minimal faithful permutation degree groups without abelian normal subgroups. Additionally, we show that: 1. For any primitive permutation group [Formula: see text], [Formula: see text] can be computed in quasi-polynomial time. 2. For a group [Formula: see text] given by its Cayley table, [Formula: see text] can be computed in [Formula: see text].

Fields of Study & Subjects

Finite Group Theory Research Complexity and Algorithms in Graphs Advanced Graph Theory Research

Publication details

Journal / source
SIAM Journal on Computing
Volume
55
Issue
2
Pages
307–331
Publication date
3 March 2026
Language
EN