Subgroups of minimal index in polynomial time

2018/07/31 by Skresanov, Saveliy V.
#05E18 #20B40 #20E28 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1807.11773

Abstract

Let G be a finite group and let H be a proper subgroup of G of minimal index. By applying an old result of Y. Berkovich, we provide a polynomial algorithm for computing |G : H| for a permutation group G. Moreover, we find H explicitly if G is given by a Cayley table. As a corollary, we get an algorithm for testing whether a finite permutation group acts on a tree or not.

Related

• Computational Complexity of Finding Subgroups of a Given Order
• Algorithms for the Minimum Generating Set Problem
• Formations of Finite Groups in Polynomial Time: \mathfrakF-residuals and \mathfrakF-subnormality
• Most Rigid Representations and Cayley index
• σ-properties of finite groups in polynomial time