An Implementation of the Neumann–Praeger Algorithm for the Recognition of Special Linear Groups (Q5285866)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 223013
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | An Implementation of the Neumann–Praeger Algorithm for the Recognition of Special Linear Groups |
scientific article; zbMATH DE number 223013 |
Statements
An Implementation of the Neumann–Praeger Algorithm for the Recognition of Special Linear Groups (English)
0 references
29 June 1993
0 references
special linear group
0 references
Neumann-Praeger algorithm
0 references
\(GAP\) system
0 references
random elements
0 references
generators
0 references
0.8035388
0 references
0 references
0 references
0 references
0.76681125
0 references
0.75360316
0 references
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 [\textit{P. Neumann} and \textit{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.
0 references