An implementation of the Neumann-Praeger algorithm for the recognition of special linear groups. (English) Zbl 0790.20001

Holt, Derek F.; Rees, Sarah

Exp. Math. 1, No. 3, 237-242 (1992).

Given a finite subset \(X\) of \(d \times d\) matrices over the field of order \(q\), does the group \(G\) generated by \(X\) contain the special linear group \(SL(d,q)\)? The Neumann-Praeger algorithm [P. Neumann and C. Praeger, Proc. Lond. Math. Soc., III. Ser. 65, No. 3, 555-603 (1992; Zbl 0770.20010)] solves this problem by a Monte Carlo method; the authors report on their implementation in the \(GAP\) system (Aachen) for \(d\) up to at least 60 and \(\log q = 16\).
A main (general) problem is a feasible procedure for choosing random elements from \(G\). In a preprocessing phase the authors add \(\max(10,n)\) new generators to the given \(n\) generators in \(X\) by forming random words of length about 30 in the existing generators. After choosing \(x\) and \(y\) randomly from the present \(m\) generators, \(x\) is replaced by \(xy\); and this is done \(m^ 2\) times completing the preprocessing phase. Thereafter the authors take such elements \(xy\) as the “random” elements for the algorithm thereby abandoning their aim of selecting all group elements with equal probability. They regret not to have a theoretical justification of the procedure and cannot estimate any small deviation between the actual and the expected probabilities. However, they have extremely convincing statistical evidence for justification of their procedure from a variety of examples where they never obtained a value of \(\chi^ 2\) outside the 0.005 probability zone.

Reviewer: U.Schoenwaelder (Aachen)

MSC:

20-04	Software, source code, etc. for problems pertaining to group theory
20G40	Linear algebraic groups over finite fields
68W30	Symbolic computation and algebraic computation
20D06	Simple groups: alternating groups and groups of Lie type
20F05	Generators, relations, and presentations of groups

Keywords:

special linear group; Neumann-Praeger algorithm; \(GAP\) system; random elements; generators

Citations:

Zbl 0770.20010

Software:

GAP

References:

[1]	Aschbacher M., Invent. Math. 76 pp 469– (1984) · Zbl 0537.20023 · doi:10.1007/BF01388470
[2]	Babai, L. ”Local expansion of vertex-transitive graphs and random generation in groups”. Proc. 23rd ACM Symp. Theory of Computing. New Orleans. pp.164–174. [Babai 1991]
[3]	Neumann P. M., Proc. London Math. Soc. 65 pp 555– (1992) · Zbl 0770.20010 · doi:10.1112/plms/s3-65.3.555
[4]	Schönert M., GAP: Groups, Algorithms, and Programming (1992)
[5]	Taylor D., The Cayley Bulletin (Univ. of Sydney) 3 pp 76– (1987)