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
| File name | Size | Date submitted |
|---|---|---|
| Aleksandar_Makelov.tar.gz | 111.8 KB | September 12 2012 14:19 UTC |
