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

Karlsruhee Institute of Technology
Department of Mathematics
Building 20.30
Englerstraße 2

Lectures

• Thursday: 11:30-13:00; SR 2.058
• Friday: 9:45-11:15; SR 2.059

Tutorials

• Wednesday 14:00-15:30, SR 2.59

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
10. Character tables (Dixon-Schneider algorithm)

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.

Notes

1. Basics – What is computational group theory? Group actions, orbits and stabilizers.
2. Orbits and transversals – Transversals in simple and compressed form; Schreier generators; pseudo-random group elements through product replacement algorithm.
3. Stabilizer chains – Working with permutation groups: bases, stabilizer chains and sifting; Schreier-Sims algorithm.
4. Backtrack searches – Going through stabilizer chain of a group: backtracking and pruning.
5. Intransitive groups – decomposing intransitive groups as sub-direct products.
6. Imprimitive groups – finding block systems for transitive groups (union-find).
7. O’Nan-Scott theorem – classifying primitive group actions.
8. Monoids and the word problem – dealing with monoid presentations.
9. Rewriting and confluence – making the rewriting process independent of choices.
10. Knuth-Bendix completion – confluent beasts and where to find them.
11. Languages and Automata – Index automata showing off their usefullness.
12. Coset enumeration – finitely generated subgroups of $F_n$ and their important cosets (automata).
13. General coset enumeration – tackling fintely f.g. subgroups of f.i. normal subgroups of $F_n$.
14. Computing character tables – step-by-step Dixon-Schneider algorithm with examples.
15. Bonus episode on property (T) – i.e. what got me into bussiness of computational group theory; Here are the three accompanying notebooks on sum of squares: symbolic one, optimization and proving property (T) for $SL_3(\mathbb{Z})$

Materials

0. Basics – a gentle introduction to programming in julia.
1. My first project in julia – on how to start your adventure for the final assignments. Other useful resources are:
   • Pkg documentation on package creation,
   • Pkg documentation on environments,
   • the julia manual on environments/projects,
   • the julia manual on modules.

Course repository

The git repository with course materials is available at github. All other course materials are in the form of Pluto notebooks here, check them out!

Instructions for running the notebooks

TL;DR version (after instantiation!):

Start terminal in CGT_KIT_WS2022 with

> julia --project=.

run

julia> using Pluto

julia> Pluto.run()

Getting julia

Go to the official julia page and navigate to “Downloads”. Pick the Current stable release (1.8.3 at the time of writing) appropriate to your operating system and download it; Unpack/install locally.

WARNING: You really should be using the official binaries of julia for this course.

Getting the official repository

The official repository for code and materials in hosted on github. It is best if you simply navigate to a directory of your choice, open terminal there (for Linux users - it’s usually under right click in file manager; for Windows - hold Shift while right clicking) and type there

> git clone https://github.com/kalmarek/CGT_KIT_WS2022

Instantiating the project

Navigate to the created directory

> cd CGT_KIT_WS2022

and launch julia there by typing (you might need to add full path to the julia binary if it’s not available directly).

> julia --project=.

You should see something like this:

              _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.8.2 (2022-09-29)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia>

You can type standard julia expressions here and obtain the answers – it’s REPL mode (Read-Evaluate-Print-Loop). Pressing ] on the keyboard will take you to so called “Pkg mode” where instead of using julia the commands manage package/project installations. If julia was started correctly (with --project=.) you should see something like this:

(CGT_KIT_WS2022) pkg>

execute now

(CGT_KIT_WS2022) pkg> `instantiate`

and observe a long list of packages that get installed. After this (and if everything goes okay) You are ready to start! Pressing Backspace will take you back to the REPL mode.

Running the notebooks!

Start julia in the CGT_KIT_WS2022 directory using julia --project=. and run

julia> using Pluto

julia> Pluto.run()
 Info: Loading...
┌ Info: 
└ Opening http://localhost:1234/?secret=P9nK6ztg in your default browser... ~ have fun!
┌ Info: 
│ Press Ctrl+C in this terminal to stop Pluto
└ 

In “Open a notebook” type notebooks and pick the notebook you’d like to run!