{'fraction_non_alphanumeric': 0.028923660502607872, 'fraction_numerical': 0.002844950213371266, 'mean_word_length': 4.509138381201044, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Recognizing simplicity of black-box groups and the frequency of p-singular elements in affine groups

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 non-abelian 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 nonsimple 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 = PSL(2, q) where q = p , p prime. We show that PSL(2, p) can be recognized in Monte Carlo polynomial time among all black-box groups of known characteristic. The situation for f ≥ 2 seems much harder; we exhibit challenging open cases for every f ≥ 2 when q is large. Along with S = 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. 2 Laszlo Babai and Aner Shalev