Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
Michael Levet, Pranjal Srivastava, Dhara Thakkar · 2025
Read Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups by Michael Levet, Pranjal Srivastava, Dhara Thakkar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16039.txt.
Introduction
Michael Levet, Pranjal Srivastava, and Dhara Thakkar study the cost of representing groups in a paper from 2025. A group can be represented by permutations, which are rearrangements of a set. A faithful representation must keep all group elements distinct, and the smallest set size is of interest. The team focuses on groups with no abelian normal subgroups, called Fitting-free groups.
For groups given as quotients of permutation groups, they give a fast algorithm that builds the smallest representation. For plain permutation groups, they give a highly parallel method for the smallest size. A randomized parallel method builds the representation itself. The results improve on a recent breakthrough for this group class.
Catalog record
| CREATOR | Michael Levet, Pranjal Srivastava, Dhara Thakkar |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 156 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-16039
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups Michael Levet, Pranjal Srivastava, Dhara Thakkar Abstract In this paper, we investigate the complexity of computing minimal faithful permutation representations for groups without abelian normal subgroups (a.k.a. Fitting-free groups). When our groups are given as quotients of permutation groups, we exhibit a polynomial-time algorithm for constructing such representations. Furthermore, in the setting of permutation groups, we obtain an NC procedure for computing the minimal faithful permutation degree, and a randomized NC ( RNC ) algorithm for computing a minimal faithful permutation representation. This improves upon the work of Das and Thakkar (STOC 2024, SIAM J. Comput. 2026), who established a Las Vegas polynomial-time algorithm for computing the minimal faithful permutation degree for this class in the setting of permutation groups. A preliminary version of this work appeared in the proceedings of FCT 2025 [ 49 ] . 1 Introduction Cayley’s theorem states that for every finite group G , there exists m\in\mathbb{N} such that G can be embedded into \text{Sym}(m) . The minimal faithful permutation degree , denoted \mu(G) , is the smallest such m for which G can be embedded into \text{Sym}(m) . A permutation representation of G on \mu(G) points is called a minimal faithful permutation representation . Note that \mu(G)\leq|G|\leq\mu(G)! . By convention, \mu(G)=0 if and only if G=1 . Johnson [ 41 ] exhibited the following characterization of \mu(G) . Proposition 1.1 ( [ 41 ] ) . Let G be a finite group, and let \mathcal{G} be the collection of all subgroups of G . We have that: \mu(G):=\min_{\emptyset\neq\mathcal{H}\subseteq\mathcal{G}}\left\{\sum_{H\in\mathcal{H}}[G:H]\ \biggr|\bigcap_{H\in\mathcal{H}}\text{Core}_{G}(H)=1\right\}, where \text{Core}_{G}(H)=\bigcap_{g\in G}gHg^{-1} and |\mathcal{H}|\leq\log|G| . 1 1 1 The fact that we can require any witnessing collection of subgroups \mathcal{H} to satisfy |\mathcal{H}|\leq\log|G| was carefully analyzed by [ 23 ] . In this paper, we investigate the computational complexity of computing \mu(G) . Precisely, we will consider the decision variant, Min-Per-Deg , which takes as input a finite group G and k\in\mathbb{N} , and asks if \mu(G)\leq k . We will also consider the search variant of Min-Per-Deg , for which we will construct an explicit embedding \varphi:G\to\text{Sym}(\mu(G)) . Key motivation for this comes from the setting of permutation group algorithms. Given a group G\leq\text{Sym}(n) , there is a natural divide-and-conquer strategy where we decompose G in terms of a normal subgroup N\trianglelefteq G and the corresponding quotient G/N . We then seek to solve the algorithmic problem on N and G/N , before recombining the solutions on the subproblems to a solution for G . The techniques involved when reasoning about quotients of two permutation groups are considerably more involved than when dealing with a single permutation group [ 44 ] . Thus, if G/N has a small faithful permutation representation that can be efficiently constructed, then we can take advantage of the extensive suite of permutation group algorithms (e.g., [ 17 , 62 , 3 , 53 ] ). This approach is not always possible, as there exist quotients with exponentially large degree. Let D_{8} be the dihedral group of order 8 . Neumann observed that D_{8}^{\ell} admits a faithful permutation representation on 4\ell points, but admits a quotient Q that is an extraspecial 2 -group with \mu(Q)\geq 2^{\ell+1} [ 58 ] . For a survey of algorithms to deal with quotient groups, we refer to [ 44 , 71 , 51 , 62 ] . The parameter \mu(G) has received considerable attention, primarily from a mathematical perspective. Johnson showed that the Cayley representation of G (that is, the representation of G induced by the left-regular action of G on itself) is minimal ( \mu(G)=|G| ) if and only if G is cyclic of prime power order, a generalized quaternion 2 -group, or the Klein group of order 4 [ 41 ] . Povzner [ 59 ] and Johnson [ 41 ] independently showed that for an abelian group G , \mu(G) is the sum of the prime powers that occur in the direct product decomposition of G into indecomposable factors. For a general survey, we refer to [ 74 , 58 , 28 , 40 , 6 , 48 , 30 , 39 , 61 ] and the references therein. To the best of our knowledge, Kantor and Luks [ 44 , Sec. 13, Problem 1] were the first to propose investigating the computational complexity of Min-Per-Deg . In the setting of permutation groups and their quotients, Min-Per-Deg belongs to NP [ 44 , 23 ] . Proposition 1.1 yields a trivial upper-bound of |G|^{O(\log^{2}|G|)} -time for this problem, in the multiplication (Cayley) table model. This is essentially the generator-enumeration strategy. Namely, we enumerate over all collections \mathcal{H} of subgroups of G , where |\mathcal{H}|\leq\log|G| . Each subgroup in \mathcal{H} is specified by generators, and so we require at most \log|G| generators per subgroup in \mathcal{H} . Note that, given generators for a subgroup H\leq G , we may write down the elements of H in polynomial time. Given the explicit elements belonging to each subgroup H\in\mathcal{H} , we may easily handle the remainder of the computations. Das and Thakkar [ 23 ] recently made significant progress in the computational complexity of the decision variant of Min-Per-Deg . Note that their work was non-constructive; they computed the minimal faithful permutation degree \mu(G) , but did not construct witnessing representations \varphi:G\to\text{Sym}(\mu(G)) . In the setting of permutation groups, they exhibited a Las Vegas polynomial-time algorithm for groups without abelian normal subgroups, and a quasipolynomial-time algorithm for primitive permutation groups. When the groups are given by their multiplication (Cayley) tables, Das and Thakkar exhibited an upper bound of \textsf{DSPACE}(\log^{3}|G|) , which improves upon the trivial |G|^{O(\log^{2}|G|)} bound. Our Contributions. In this paper, we further investigate both the decision and search variants of the Min-Per-Deg problem for groups without abelian normal subgroups, addressing one of the open questions posed by Das and Thakkar [ 23 ] . Our main result is the following. Theorem 1.2 . Let G be a group without abelian normal subgroups (a.k.a. Fitting-free). 2 2 2 In this paper, we will use the term Fitting-free to refer to the class of groups without abelian normal subgroups, and semisimple to refer to algebraic structure decomposes as a direct sum of simple objects. The terms Fitting-free or trivial-Fitting are common in the group theory literature (see e.g., [ 17 , 38 ] ), while the term semisimple has been used in the complexity theory literature to refer to the class of groups without abelian normal subgroups (see e.g., [ 4 , 5 ] ). (a) Suppose G is given as the quotient G/K of two permutation groups K\trianglelefteq G\leq\text{Sym}(n) . Then we can compute \mu(\textbf{G}) , as well as a minimal faithful permutation representation \varphi:\textbf{G}\to\text{Sym}(\mu(G)) , in polynomial time. (b) If G is given as a permutation group ( K=1 ), then we can compute \mu(\textbf{G}) in NC . Furthermore, we can construct a minimal faithful permutation representation \varphi:\textbf{G}\to\text{Sym}(\mu(G)) using a randomized NC ( RNC ) algorithm. Given a finite group G by its multiplication (Cayley) table, we may easily construct the regular representation in NC . Thus, Theorem 1.2 yields the following immediate corollary. Corollary 1.3 . Let G be a