For each family of finite classical groups, and their associated simple quotients, we provide an explicit presentation on a specific generating set of size at most 8. Since there exist efficient algorithms to construct this generating set in any copy of the group, our presentations can be used to verify claimed isomorphisms between representations of the classical group. The presentations are available in Magma.
Babai and Szemer 'e di @cite_21 formulated the Short Presentation Conjecture : there exists a constant @math such that every finite simple group @math has a presentation of bit-length @math . The results of @cite_26 @cite_12 @cite_7 establish this conjecture with @math for all finite simple groups, with the possible exception of the Ree groups @math .
@cite_7 @cite_21 @cite_12 @cite_26
1964155237 1997911818 2123560844 2099601775
We conjecture that every finite groupGhas a short presentation (in terms of generators and relations) in the sense that the totallengthof the relations is (log|G|)O(1). We show that it suffices to prove this conjecture for simple groups. Motivated by applications in computational complexity theory, we conjecture that for finite simple groups, such a short presentation is computable in polynomial time from the standard name ofG, assuming in the case of Lie type simple groups overGF(pm) that an irreducible polynomialfof degreemoverGF(p) and a primitive root ofGF(pm) are given. We verify this (stronger) conjecture for all finite simple groups except for the three families of rank 1 twisted groups: we do not handle the unitary groupsPSU(3, q) = 2A2(q), the Suzuki groupsSz(q) = 2B2(q), and the Ree groupsR(q) = 2G2(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 (normal or twisted) of rank ≥ 2, we use a reduced version of the Curtis–Steinberg–Tits presentation. All nonabelian finite simple groups of rank @math over a field of size @math , with the possible exception of the Ree groups @math , have presentations with at most @math relations and bit-length @math . Moreover, @math and @math have presentations with 3 generators @math 7 relations and bit-length @math , while @math has a presentation with 7 generators, @math relations and bit-length @math There is a constant such that all nonabelian finite simple groups of rank over , with the possible exception of the Ree groups , have presentations with at most generators and relations and total length at most . As a corollary, we deduce a conjecture of Holt: there is a constant such that for every finite simple group , every prime and every irreducible -module We prove the existence of a polynomial time computable pseudorandom generator that @math -fools constant width regular read-once branching programs of length @math using a seed of length @math . The previous best pseudorandom generator for regular branching programs used a seed of length @math , and was due to Braverman et. al. and Brody and Verbin (FOCS 2010). Our pseudorandom generator is the INW generator due to Impagliazzo et. al. (STOC 1994). Our work shares some similarity with the recent work of Kouck ' y et. al. (STOC 2011)who get similar seed length for permutation branching programs. However, our work proceeds by analyzing the eigenvalues of the stochastic matrices that arise in the transitions of the branching program which arguably makes the technique more robust. As a corollary of our techniques, we present new results on the small biased spaces for group products'' problem by Meka and Zuckerman (RANDOM 2009). We get a pseudorandom generator with seed length @math . Previously, using the result of Kouck ' y et. al., it was possible to get a seed length of @math for this problem.