Recognizing simplicity of black-box groups and the frequency of \(p\)-singular elements in affine groups. (English) Zbl 1052.20031
Kantor, William M. (ed.) et al., Groups and computation III. Proceedings of the international conference at the Ohio State University, Columbus, OH, USA, June 15–19, 1999. Berlin: Walter de Gruyter (ISBN 3-11-016721-2/hbk). Ohio State Univ. Math. Res. Inst. Publ. 8, 39-62 (2001).
Summary: We consider the asymptotic complexity of manipulating matrix groups over finite fields. The question is, given a matrix group \(G\) by a list of generators, what can we say in polynomial time about the structure of \(G\)?
While considerable progress has been made recently in identifying the nonabelian composition factors of a matrix group, the fundamental question of recognizing the simplicity of a nonabelian matrix group remains open.
For the purposes of polynomial time computation, we reduce this problem to the following ‘affine case’: Let \(A\) be an elementary Abelian \(p\)-group which is a non-central minimal normal subgroup of a finite group \(G\). Assume further that the quotient \(G/A\) is a finite simple group \(S\) of Lie type of characteristic \(p\). The algorithmic goal is to distinguish the simple group \(S\) from the non-simple group \(G\). Both \(S\) and \(G\) are given as ‘black-box groups of characteristic \(p\)’.
The reduction to this basic problem involves a large number of recent techniques and results which we review along the way.
We address the affine case for the groups \(S=\text{PSL}(2,q)\) where \(q=p^f\), \(p\) prime. We show that \(\text{PSL}(2,p)\) can be recognized in Monte Carlo polynomial time among all black-box groups of known characteristic. The situation for \(f\geq 2\) seems much harder; we exhibit challenging open cases for every \(f\geq 2\) when \(q\) is large.
Along with \(S=\text{PSL}(2,p)\), the positive result holds for all simple groups \(S\) of Lie type of characteristic \(p\) with the property that in every nontrivial \(S\)-module in characteristic \(p\), every element of \(S\) has a fixed point. We call these groups ‘unisingular’. Very recently, Guralnick, Saxl, and Tiep classified these groups. They found that a large number of classes of simple groups are unisingular, including certain classes of linear and unitary groups, all symplectic groups over an odd prime field, all orthogonal groups of odd degree over an odd prime field, many orthogonal groups of even degree, and a number of classes of exceptional groups.
For the entire collection see [Zbl 0959.00030].
While considerable progress has been made recently in identifying the nonabelian composition factors of a matrix group, the fundamental question of recognizing the simplicity of a nonabelian matrix group remains open.
For the purposes of polynomial time computation, we reduce this problem to the following ‘affine case’: Let \(A\) be an elementary Abelian \(p\)-group which is a non-central minimal normal subgroup of a finite group \(G\). Assume further that the quotient \(G/A\) is a finite simple group \(S\) of Lie type of characteristic \(p\). The algorithmic goal is to distinguish the simple group \(S\) from the non-simple group \(G\). Both \(S\) and \(G\) are given as ‘black-box groups of characteristic \(p\)’.
The reduction to this basic problem involves a large number of recent techniques and results which we review along the way.
We address the affine case for the groups \(S=\text{PSL}(2,q)\) where \(q=p^f\), \(p\) prime. We show that \(\text{PSL}(2,p)\) can be recognized in Monte Carlo polynomial time among all black-box groups of known characteristic. The situation for \(f\geq 2\) seems much harder; we exhibit challenging open cases for every \(f\geq 2\) when \(q\) is large.
Along with \(S=\text{PSL}(2,p)\), the positive result holds for all simple groups \(S\) of Lie type of characteristic \(p\) with the property that in every nontrivial \(S\)-module in characteristic \(p\), every element of \(S\) has a fixed point. We call these groups ‘unisingular’. Very recently, Guralnick, Saxl, and Tiep classified these groups. They found that a large number of classes of simple groups are unisingular, including certain classes of linear and unitary groups, all symplectic groups over an odd prime field, all orthogonal groups of odd degree over an odd prime field, many orthogonal groups of even degree, and a number of classes of exceptional groups.
For the entire collection see [Zbl 0959.00030].
MSC:
| 20G40 | Linear algebraic groups over finite fields |
| 20D06 | Simple groups: alternating groups and groups of Lie type |
| 68W30 | Symbolic computation and algebraic computation |
