Fast recognition of alternating groups of unknown degree. (Q2438377): Difference between revisions

There are very effective algorithms to determine whether a black box group \(G\) is isomorphic to an alternating group of degree \(n\) when the degree is known [see \textit{R. Beals} et al., Trans. Am. Math. Soc. 355, No. 5, 2097-2113 (2003; Zbl 1022.20004)] but these are inefficient if \(n\) is not known. In the present paper the authors present a (one-sided Monte Carlo) algorithm for the following. Let \(G=\langle X\rangle\) be a black box group, \(N\) be a positive integer and \(\varepsilon\) a real number between \(0\) and \(1\). If \(G\cong A_n\) or \(S_n\) for some \(n\) with \(9\leq n\leq N\) then with probability \(>1-\varepsilon\) the algorithm returns an isomorphism from \(G\) onto \(A_n\) or \(S_n\); otherwise it reports failure. The time the algorithm takes is bounded by \(O(N(\log N)^{2}\log(1/\varepsilon)(|X|\mu+\rho))\) where \(\mu\) bounds the time taken to multiply two elements of \(G\) and \(\rho\) bounds the time taken to compute a random element of \(G\). The space required is proportional to \(\log N\). The proof of this result depends on the following facts about permutation groups. Suppose that \(G=A_n\) or \(S_n\) (\(n\geq 9\)) and \(s\) is an involution moving \(2k\) points where \(1\leq k\leq\tfrac{2}{3}\sqrt n\). Then: (i) the proportion of elements \(x\) of even order satisfying \(|\text{supp }x^{|x|/2}|\leq\tfrac{4}{3}\sqrt n\) is at least \(1/(13\log n)\); (ii) the proportion of elements \(r\) in the conjugacy class \(s^G\) such that the supports of \(r\) and \(s\) have exactly one common point is at least \(10/(3n)\); (iii) \((sr)^2\) is a \(3\)-cycle for at least one third of the elements \(r\) satisfying the condition in (ii).