Group Theory

Aleksandar Makelov

Abstract

A module for handling the essentials of group theory, exclusively for finite and finitely presented groups using basic concepts and algorithms from computational group theory. Permutation & matrix presentations, orbits, stabilizers and group actions, quotient groups, representations and characters,...

Additional Information

The aim is to be able to do most of the following operations:

 

  • Calculation of orbits and stabilizers (permutation groups)
  • Order of a group (permutation groups / finite finitely presented groups)
  • Order of an element (permutation groups / finite finitely presented groups - by the number of cosets of the cyclic group generated by the element)
  • Outputting all elements of a group as a list (which makes sense only for fairly small groups)
  • Membership testing for permutation groups
  • Testing if a permutation group is "large" (S_n or A_n)
  • Testing for subgroups (easy by membership testing for permutation groups)
  • Testing for normal subgroups (using normal closure)
  • Finding the normal closure of a subgroup (done in [1], optimized for groups of large index by adjoining random conjugates; membership testing necessary)
  • Commutator subgroups & derived series
  • Cosets and transversals for subgroups (done in [1])
  • Quotients: for permutation groups this can be done by considering the quotient as a permutation group acting on the set of cosets; for finitely presented groups, this is more complicated (but done in [1])
  • Algorithms specific for Abelian groups: decomposition according to the structure theorem, optimized algorithms for Abelian groups. Presently the problem with this is that my references don't have a lot to say about Abelian groups specifically, so I might need other sources (or, in the worst case, come up with some naive algorithm (or, in the best case, come up with some efficient algorithm)). Though in [1] there is a broad section for algorithms optimized for polycyclic groups, of which Abelian groups form a subclass.
  • Direct product of several groups: this can be implemented for permutation groups, but the references don't address this operation explicitly. I came up with one possible way of doing it, but it may not be the most efficient one. Further inquiry is needed here.

Code samples