Computational group theory

Computational group theory is a well-developed area of computer algebra. The word problems for finitely presented monoids and groups are special cases of the word problem for finitely presented categories.

Software

  • GAP : Groups, Algorithms, Programming (GitHub )
  • Magma : originally specialized in group theory, now covers algebra generally

Literature

The subject seems to divide into computation on “abstract groups” (presented by generators and relations) and on permutation groups (subgroups of the symmetric group). Cayley’s theorem notwithstanding, computing on permutation groups is usually easier than computing on abstract groups.

General

  • Holt, 2005: Handbook of Computational Group Theory

Abstract groups

Books

  • Rotman, 1994: Introduction to the Theory of Groups, 4th ed., Ch. 12: The Word Problem
  • Sims, 1994: Computation with Finitely Presented Groups

Papers

  • Kapovich et al, 2003: Generic-case complexity, decision problems in group theory and random walks (arxiv)
  • Diaconis, 2009: The Markov chain Monte Carlo revolution (doi), Sec. 6.4: Contacts outside math
    • References on randomized algorithms in computational group theory

Permutation groups

Books

  • Seress, 2002: Permutation Group Algorithms (doi)
  • Sagan, 2001: The Symmetric Group, 2nd ed., Ch. 3: Combinatorial algorithms (doi)
  • Butler, 1991: Fundamental Algorithms for Permutation Groups (doi)