CGT@UniHeidelberg SS2022

Prerequisites:

The course requires the knowledge of basic group theory (groups, normal subgroups etc.) and is intended for master students. Nonetheless, students of earlier years who are keen on programming and can work independently are encouraged to apply.

Date and time

University of Heidelberg; Building INF 205

• Lectures: Tuesday & Thursday; 11:15, SR2 (Seminar room 2, 2nd floor)
• Exercise sessions: Wednesday 14:00, SR2 (Seminar room 2, 2nd floor)

If you are interested please sign through Müsli and let me know via email!

Topics covered:

1. Group actions, orbits, stabilizers, Schreier vectors
2. Permutation groups, bases, Stabilizer chains, Schreier-Sims algorithm.
3. Broad overview of transitive groups, primitive groups
4. Finitely presented groups, their homomorphisms, quotients
5. Subgroups and their presentations
6. Formal languages, and rewriting systems
7. Knuth-Bendix completion
8. Automata
9. Coset enumeration

Literature

• Alexander Hulpke, Notes on Computaional Group Theory, 2010, available here.
• Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien, Handbook of Computational Group Theory, Discrete Mathematics and its Applications, Chapman & Hall/CRC, 2005
• Akos Seress, Permutation group algorithms, Cambridge University Press, 2003
• Charles C. Sims, Computation with finitely presented groups, Cambridge University Press, 1994.

Materials

0. Basics – a gentle introduction to programming in julia.
1. Orbits and Permutations – we’re implementing our first group element – permutation.
2. Transversals and Schreier Vectors – we learn how to compute coset representatives and then how to compress this information.
3. The Schreier-Sims algorithm – we’re discussing an implementation of the Schreier-Sims algorithm and troubles to make it generic enough.
4. Implementing Groups – we finally wrap what we have learned so far into a PermutationGroup structure, learning about lazy evaluation, locks, thread-safety, etc.
5. Alphabets and Words – starting with the basic building blocks for finitely presented groups
6. First take on rewriting – a mutable take on rewriting and a bit about orderings
7. Knuth-Bendix completion – the first naive version of the completion procedure
8. Indexing Automata – an implementation of indexing automaton for rewriting systems.

Notes

1. What is CGT?
2. Permutations, Orbits and Transversals
3. Schreier-Sims algorithm
4. Backtrack search
5. Intransitive groups, imprimitive groups & classification
6. Finitely presented groups
7. Classical algorithms for fp groups
8. Orderings and rewriting
9. Knuth-Bendix completion
10. Rational languages and the Indexing Automaton