What I'm trying to do in this blog is a kind of guided tour of my HaskellForMaths library. In turn, the library itself, although it contains efficient implementations of fundamental algorithms in computer algebra, is really an educational tool. I wrote it to help me understand maths I wanted to learn about, and especially, to help develop my intuitions about the objects of study. My hope is that by retracing my steps in this blog, I can help others to do the same.
Up to now, we've been looking at graphs and their symmetries, considered as permutation groups. Group theory is sometimes described as the study of symmetry, and I hope that by introducing groups through symmetries of graphs, I've made it clear why.
We've really only looked at quite a small amount of code. The main functions we've seen (forgetting a few stepping stones along the way) are:
- graph (vs,es) - for constructing a graph with given vertices and edges
- graphAuts g - returns a strong generating set for the group of symmetries / automorphisms of the graph
- orderSGS sgs - given a strong generating set, return the order of the group - for example, the total number of symmetries of the graph
- conjClassReps - given a generating set for a group, return representatives and sizes for the conjugacy classes - the classes of elements which are "the same, just viewed from a different angle"
- p [[1,2,3],[4,5]] - given a list of cycles, return the corresponding permutation
- g*h, 1, g^-1 - multiplication, identity and inverses for group elements
- v .^ g - the action of a permutation on a vertex
- e -^ g - the action of a permutation on an edge
- sgs gs - return a strong generating set, given a set of generators
However, the graph and permutation group code represents, I would say, only about one sixth of what's in the HaskellForMaths library. (Not to mention that I have quite a lot more code in various stages of development back in the lab.) So what else is there still to look at?
Well, what I want to do next is stick with permutation groups a little longer, but widen the set of combinatorial objects that we consider, to include finite geometries, designs, and perhaps other incidence structures.
One of my aims is to take a look at a few of the sporadic finite simple groups. Finite simple groups are the "atoms of symmetry". Most of them fall in one of several infinite families (the cyclic groups of prime order, the alternating groups, and the finite groups of Lie type, aka Chevalley groups). However, it turns out that there are also 26 "sporadic" finite simple groups, which don't belong to any of these families. The HaskellForMaths library contains code for investigating both the infinite families, and some of the smaller sporadic groups.
Then there are root systems and Coxeter groups, including string rewriting and the Knuth-Bendix algorithm. Root systems have some connection to Lie algebras, and are therefore important in physics, though I don't claim to fully understand all that stuff.
Another major part of the library, which I'll get round to eventually, is commutative algebra and Groebner bases. Groebner bases provide a way of calculating with ideals in polynomial rings, which is equivalent to doing algebraic geometry.
Finally, there's some code for working in non-commutative algebra. As an example, there's some code which uses Temperley-Lieb and Hecke algebras to calculate polynomial invariants of knots (the Jones polynomial and the HOMFLY polynomial). In due course, I'm hoping to expand this part of the library to do group algebras, representation theory, and other stuff.
In case I've managed to interest anyone, I should probably mention a few of the books that I used for inspiration:
- Ronan, Symmetry and the Monster
- Godsil and Royle, Algebraic Graph Theory
- Cameron, Combinatorics
- Seress, Permutation Group Algorithms
- Holt, Handbook of Computational Group Theory
No comments:
Post a Comment