SHORT PRESENTATIONS FOR FINITE-GROUPS

We conjecture that every finite group G has a short presentation (in t erms of generators and relations) in the sense that the rotal length o f the relations is (log\G\)(0(1)). We show that it suffices to prove t his conjecture for simple groups. Motivated by applications in computa tional complexity theory, we conjecture that for finite simple groups, such a short presentation is computable in polynomial time from the s tandard name of G, assuming in the case of Lie type simple groups over CF(p(m)) that an irreducible polynomial f of degree m over GF(p) and a primitive root of GF(p(m)) are given. We verify this (stronger) conj ecture for all finite simple groups except for the three families of r ank 1 twisted groups: we do not handle the unitary groups PSU(3, q) = (2)A(2)(q), the Suzuki groups Sz(q) = B-2(2)(q), and the Ree groups R( q) = (2)G(2)(q). In particular, all finite groups G without compositio n factors of these types have presentations of length O((log\G\)(3)). For groups of Lie type (normal or twisted) of rank greater than or equ al to 2, we use a reduced version of the Curtis-Steinberg-Tits present ation. (C) 1997 Academic Press.