Short presentations for finite groups (Q1365014)

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.