Short presentations for finite groups
type: Item
instance of: scholarly article
title: Short presentations for finite groups
zbMATH Open document ID: 0896.20025
published in: Journal of Algebra
publication date: 1998-06-04T00:00:00Z
review text: The authors conjecture that every finite group \(G\) has a short presentation (in terms of generators and relations) in the sense that the total length of the relations is \((\log| G|)^{O(1)}\). They show that it suffices to prove this conjecture for simple groups. Motivated by applications in computational complexity theory, they conjecture also that for finite simple groups, such short presentation is computable in polynomial time from the standard name of \(G\), assuming in the case of Lie type simple groups over \(\text{GF}(p^m)\) that an irreducible polynomial \(f\) of degree \(m\) over \(\text{GF}(p)\) and a primitive root of \(\text{GF}(p^m)\) are given. The authors verify this (stronger) conjecture for all finite simple groups except for the following groups: \(^2A_2(q)\), \(^2B_2(q)\), and \(^2G_2(q)\). In particular, all finite groups \(G\) without composition factors of these types have presentations of length \(O((\log| G|)^3)\). For groups of Lie type of rank \(>1\), the authors use a reduced version of the Curtis-Steinberg-Tits presentation.
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 20D60
Mathematics Subject Classification ID: 20D06
Mathematics Subject Classification ID: 20D08
zbMATH DE Number: 1053877
zbMATH Keywords: finite groups
zbMATH Keywords: short presentations
zbMATH Keywords: finite simple groups of Lie type
zbMATH Keywords: computational complexity
zbMATH Keywords: generators
zbMATH Keywords: relations
author: László Babai
author: Albert J. Goodman
author: William M. Kantor
author: Eugene M. Luks
author: Péter P. Pálfy
reviewed by: Anatoli Kondrat'ev
MaRDI profile type: Publication
OpenAlex ID: W1964155237
cites work: Q4011250
cites work: Bounded Round Interactive Proofs in Finite Groups
cites work: Q4335288
cites work: Factoring Polynomials Over Large Finite Fields
cites work: Q3485067
cites work: A New Algorithm for Factoring Polynomials Over Finite Fields
cites work: Q5662096
cites work: Q5650865
cites work: Central extensions of groups of Lie type.
cites work: Q4198056
cites work: Q5577154
cites work: Schur Multipliers of Finite Simple Groups of Lie Type
cites work: Enumerating p -Groups. I: Inequalities
cites work: Introduction to Lie Algebras and Representation Theory
cites work: Q3996618
cites work: Probabilistic Algorithms in Finite Fields
cites work: A note on a paper by J. A. Todd
cites work: Q3215137
cites work: Generators, relations and coverings of algebraic groups. II
cites work: Presentations of the Groups SL(2,m) And PSL(2,m)
cites work: A Second Note on the Linear Fractional Group
DOI: 10.1006/JABR.1996.6980
Recommended article: Q3812439
Recommended article: Q4732626
Recommended article: Short presentations for alternating and symmetric groups
Recommended article: Efficient presentations for certain simple groups
Recommended article: Q2965186
Recommended article: Q4463895
Recommended article: Q4263816
Recommended article: Presentations of finite simple groups: A quantitative approach
Recommended article: Q4247801
Recommended article: Q3222360
description: scientific article; zbMATH DE number 1053877