The Minimum Generating Set Problem

2023/06/13 by Lucchini, Andrea, Thakkar, Dhara
#FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2306.07633

Abstract

Let G be a finite group. In order to determine the smallest cardinality d(G) of a generating set of G and a generating set with this cardinality, one should repeat many times the test whether a subset of G of small cardinality generates G. We prove that if a chief series of G is known, then the numbers of these generating tests can be drastically reduced. At most |G|^13/5 subsets must be tested. This implies that the minimum generating set problem for a finite group G can be solved in polynomial time.

Related

• Finite groups with the minimal generating set exchange property
• Minimal sized generating sets of permutation groups
• Algorithms for the Minimum Generating Set Problem
• Large minimal invariable generating sets in the finite symmetric groups
• Flexibility in generating sets of finite groups