I am interested in algorithms for finite groups as implemented in the GAP package. It seems that all known algorithms in this field deal with permutation groups/matrix groups; two fundamental ones are Schreier-Sims [1970] and Butler [1979], see e.g. 'Algorithms for Permutation groups' by Alice Niemeyer as a possible reference (?)

Hence, I was wondering whether there had been significant progress in the field in the last 50 years. I've seen that user NisaiVloot asked some questions about braid groups that may constitute an interesting extension of known results about permutation groups, though it's unclear to me what is the current state of research in this field as the mathematics/algorithmics communities seem somewhat out-of-sync nowadays.

  • $\begingroup$ A good start would probably be to see if any members of the computational group theory at cmsc.uwa.edu.au/research/cgt (Cheryl Praeger, Alice Niemeyer or Ákos Seress) have published a survey or given a talk about that recently. $\endgroup$ – Anthony Labarre May 24 '14 at 9:40

Certainly there has been tons of progress! (And if you really meant to ask about the last 50 years, then that includes the algorithms of Schreier-Sims and Butler that you already mentioned...)

For example, see Seress's book [1], which includes many algorithms that upgrade standard tasks into $\mathsf{NC}$ and/or quasi-linear (sometimes Las Vegas) time, such as membership testing, computing the order, and even computing the entire composition series! The finite simple groups can be recognized in the black-box model [2] (more general/stronger than permutation groups or matrix groups), and permutational isomorphism of permutation groups of degree $n$ can be decided in $O(2^{n} |G|)$ time [3] (prior to that, the best known was the trivial $n! \cdot poly(n)$ algorithm). Many of these results were in the last 20 years, and the latter is even from 2012.

[1] Seress, Ákos Permutation group algorithms. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003

[2] Babai, László; Kantor, William M.; Pálfy, Péter P.; Seress, Ákos Black-box recognition of finite simple groups of Lie type by statistics of element orders. J. Group Theory 5 (2002), no. 4, 383–401.

[3] László Babai, Paolo Codenotti, Youming Qiao: Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups (Extended Abstract). In: Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP'12), Springer LNCS 7391, 2012, pp. 51-62.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.