Computational Complexity of Finding Subgroups of a Given Order

K. Lakshmanan · 2025

Read Computational Complexity of Finding Subgroups of a Given Order by K. Lakshmanan (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-2503-11238.txt.

Introduction

Lakshmanan studies a group theory task in this 2025 paper: given a finite group as a full table of its operations, find a smaller group inside it of a set size. The paper asks how hard that task is in computing terms. It centers on the special case of abelian groups, where the order of operations does not matter.

For that case, the author gives an algorithm and argues that it is the best possible for this input form. The paper notes that no prior work had studied the task's cost when the group is given as such a table. Readers get a clear result on what can and cannot be done fast in this setting.

Catalog record

CREATORK. Lakshmanan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-11238

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computational Complexity of Finding Subgroups of a Given Order K. Lakshmanan Abstract We study the problem of finding a subgroup of a given order in a finite group, where the group is represented by its Cayley table. We establish that this problem is NP-hard in the general case by providing a reduction from the Hamiltonian Cycle problem. Additionally, we analyze the complexity of the problem in the special case of abelian groups and present a linear-time algorithm for finding a subgroup of a given order when the input is given in the form of a Cayley table. To the best of our knowledge, no prior work has addressed the complexity of this problem under the Cayley table representation. Our results also provide insight into the computational difficulty of finding subgroup across different ways of groups representations. Keywords: Computational group theory, Cayley table representation, NP-hardness, subgroup enumeration, abelian groups, algorithmic group theory Mathematics Subject Classification 2020: 68Q17, 20-08 1 Introduction In this paper, we study the problem of computing a subgroup of a given order in a finite group. We establish that this problem is NP-hard in the general case and present a linear-time algorithm for abelian groups when given in the Cayley table representation. To the best of our knowledge, no prior work explicitly addresses these results in the literature. We begin by discussing the Cayley table representation, which provides a fundamental but computationally expensive way to describe a group. While representations such as generators and relations or permutation representations often allow structural insights for efficient algorithms, the Cayley table offers a general, uniform description applicable to any finite group. Hardness results in this representation often indicate worst-case intractability unless alternative representations permit structural exploitation. Despite its high space complexity, the Cayley table representation appears in several computational settings. It is used in group isomorphism testing [ 13 ] , where small groups are explicitly stored as lookup tables. In computational algebra systems, finite groups of moderate size are often manipulated via Cayley tables for efficient lookup operations. Additionally, in automata theory and symbolic computation, transition functions of finite-state systems can sometimes be encoded as group operations, making the Cayley table a natural representation in certain algorithmic contexts. Next, we analyze conditions under which hardness results transfer to other representations, highlighting implications for different group structures. 1.1 Cayley Table Representation The Cayley table representation provides a brute-force encoding of a group, explicitly listing the results of all group operations. While this representation is often used to establish worst-case complexity results, the extent to which these results transfer to other representations depends on the structure of the group and the nature of the problem. Hardness Transfer from Cayley Table to Other Representations Hardness results in the Cayley table model can transfer to other group representations under certain conditions. In particular, if a problem remains hard regardless of how the group is specified, then Cayley table hardness serves as strong evidence of intractability in the general case. This occurs when: • The problem is combinatorial in nature and does not rely on specific algebraic properties of the group. Many problems, such as finding a subgroup of a given order, involve searching through subsets of group elements and are unlikely to admit efficient algorithms, regardless of representation. • No structural advantage exists in alternative representations. If no known method exploits algebraic properties to obtain a faster solution, then the complexity in the Cayley table model is expected to be representative of the general case. • Known reductions exist between different representations. If a problem is NP-hard for general groups under the Cayley table model and reductions exist that transform instances into more compact representations (such as permutation groups or groups given by generators and relations), then hardness likely extends to those cases as well. While the Cayley table is a natural choice for proving worst-case complexity, it is often inefficient in practice. Some group representations [ 6 ] , such as permutations, matrices, or generators with relations, encode the group more compactly and allow for more efficient computations. In these cases, problems that are intractable for general groups may have polynomial-time solutions in structured settings [ 2 , 11 ] . We list the cases where the Cayley table representation is the worst case but not representative of all cases: • Permutation group representations often admit efficient algorithms. For example, the problem of computing a subgroup given a set of generators is intractable for arbitrary groups but can be solved efficiently for permutation groups using the Schreier–Sims algorithm. • Matrix groups over finite fields allow algebraic techniques to improve efficiency. Many computational problems that are difficult in general become tractable when the group elements are matrices, as linear algebra techniques can be applied. • Groups given by generators and relations may allow structure-specific optimizations. The word problem, for instance, is undecidable in some finitely presented groups but trivial in the Cayley table model, as the full operation table allows constant-time lookup. • Commutative (abelian) groups often admit efficient solutions. Many problems that are NP-hard for general groups, such as finding a subgroup of a given order, are solvable in polynomial time when restricted to abelian groups. Thus, while proving hardness in the Cayley table model provides a strong indication of computational difficulty, additional analysis is required to determine whether the result holds in alternative representations. 1.2 Hardness Transfer Across Group Representations The complexity of computational problems in group theory can vary depending on how the group is represented. However, for the problem of determining whether a subgroup of a given order exists, we establish that NP-hardness in the Cayley table representation extends to other standard representations. • Cayley Table as a General Representation The Cayley table provides a complete and explicit description of a group, listing all group operations. It allows no shortcuts—algorithms working on the Cayley table cannot exploit additional structure, making it a natural worst-case representation. • Polynomial-Time Transformations A Cayley table can be converted in polynomial time into other common representations such as: Generators and relations (via presentation extraction algorithms) Permutation representation (by representing elements as permutations on themselves) These conversions ensure that any hardness result for the Cayley table carries over to these representations if no additional structure is exploited. • Implication of Efficient Algorithms Suppose there existed a polynomial-time algorithm for finding a subgroup of a specified order in one of these alternative representations. Since we can transform the Cayley table into that representation efficiently, we could solve the problem for the Cayley table as well. This contradicts the established NP-hardness of the problem in the Cayley table representation. • When Hardness Does Not Automatically Transfer In structured groups (e.g., permutation groups, matrix groups), additional algebraic properties can sometimes be leveraged for more efficient algorithms. For instance, Abelian groups admit polynomial-time solutions, and certain permutation group problems have more efficient algorithms using stabilizer chains and coset enumeration. Since we have shown the problem to be NP-hard for the Cayley table representation, and since Cayley tables can be transformed into other standard representations in polynomial time, the problem remains NP-hard in all these representations unless additional structure can be exploited. This establishes a broad complexity classification across different models

Read the complete text