The minimum generating set problem

DOI10.1016/J.JALGEBRA.2023.11.012MaRDI QIDQ6142842zbMATH OpenFDO

Authors Andrea Lucchini, Dhara Thakkar

Publication date 4 January 2024

Published in Journal of Algebra (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2306.07633

zbMATH Keywords

crowngeneration of finite groupsminimum generating set

Mathematics Subject Classification ID

Computational methods for problems pertaining to group theory (20-08) Arithmetic and combinatorial problems involving abstract finite groups (20D60) Generators, relations, and presentations of groups (20F05)

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.

Review text

If \(G\) is a finite group then \(d(G)\) denotes the minimum number of elements necessary to generate \(G\). A subset \(X \subset G\) such that \(G=\langle X \rangle\) and \(|X|=d(G)\) is a minimum generating set of \(G\). Checking whether a given subset of \(G\) generates \(G\) is called a generating test for \(G\). The authors prove the following result (Theorem 2): The number of generating tests needed to determine a minimum generating set of a finite group \(G\) is at most \(|G|^{\frac{13}{5}}\).

Recommendations

• Computing a set of generators of minimal cardinality in a solvable group
• A strong generating test and short presentations for permutation groups
• Minimal and random generation of permutation and matrix groups.
• Minimal generating sets of groups, rings, and fields
• An algorithm for finding minimal generating sets of finite groups

Cites work

• Bounding the composition length of primitive permutation groups and completely reducible linear groups
• Chains of subgroups in symmetric groups
• Classes of Finite Groups
• Computational Complexity
• Computing a set of generators of minimal cardinality in a solvable group
• Crowns and factorization of the probabilistic zeta function of a finite group.
• ENUMERATING FINITE GROUPS
• Generators and minimal normal subgroups
• Generators for finite groups with a unique minimal normal subgroup
• scientific article; zbMATH DE number 1154720 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 2236723 (Why is no real title available?)
• On complemented nonabelian chief factors of a finite group
• Pre-Frattini groups.
• Probabilistic generation of finite groups with a unique minimal normal subgroup.
• Recognizing the prime divisors of the index of a proper subgroup.
• The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem
• The smallest group with non-zero presentation rank
• The X-Dirichlet polynomial of a finite group
• Zu einem von B. H. und H. Neumann gestellten Problem

Cited in

(4)

• Computational group theory. Abstracts from the workshop held June 1--6, 2025
• On the constant-depth circuit complexity of generating quasigroups
• Constant depth circuit complexity for generating quasigroups
• Minimal sized generating sets of permutation groups

This page was built for publication: The minimum generating set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6142842)