 #1
Chris Hillman
Science Advisor
 2,345
 8
Main Question or Discussion Point
I am somewhat distracted so this post will not be what it should, given that GAP is one of my interests.
For those who don't already know: GAP is a powerful open source software package for computational algebra, especially computational group theory and allied subjects. This long running project is remarkable for having harmoniously developed under dozens of developers and some years ago, when the leaders retired, leadership was successfully handed on the new generation. I'll have to give links later to the huge GAP documentation book, approximately as heavy and as essential for anyone interested in group theory as MTW is for anyone interested in gravitation theory, not as easy to read as MTW, but available for free download. The software itself can be installed with a few mouseclicks, for those who use Linux (at least, if you use a distro sufficiently closely related to Debian to know what to do with a deb file), and I am pretty sure it is also available for other OSs.
GAP is among other things a powerful programming language, but you can get a great deal of work done without ever writing any GAP programs. Noone would accuse GAP of using elegant syntax, I think (compare Macaulay2, which has an attractive and mathematically natural syntax), but the unparalleled power of GAP makes this failing (shared with say, Mathematica, some would say) acceptable.
The genesis of this post is that someone asked in
https://www.physicsforums.com/showthread.php?p=2619232#post2619232
about listing and identifying the subgroups of a specific group (the user didn't say, but from context it seems he/she means a not too huge permutation group). And a bit earlier, someone asked for a polynomial over the rationals whose Galois group is the group of unit quaternions (the eight element finite group generated by Hamilton's three unit quaternions i,j,k). The first question is easily answered by GAP, and a correct answer to the second question is easily confirmed with GAP, although finding a polynomial which works is probably not so trivial.
GAP comes with a huge database (if RAM is limited on your machine, you can choose not to load all the database upon starting GAP), including:
GAP does not provide a translation of its list of small groups into the ways in which the older literature typically refered to them, so it's useful to keep handy a small dictionary:
Notational issues:
Simply listing the subgroups up to isomorphism is not enough for group theory; it is crucial to list them by conjugacy class. Fortunately, GAP is up to the task: it has a way of defining lattices, computing the subgroup lattice, and identifying conjugacy classes. Because even small groups tend to have a huge number of subgroups, this is however inefficient. Moreover, the subgroup lattice is too complicated to draw (except in the simplest cases) unless you adopt a useful abbreviation in which you draw the lattice of conjugacy classes,
(Some of you may know that in the first edition, Burnside famously commented in the introduction that his book ignored the then new methods of Frobenius, now taught to math and physics students as the representation theory of finite groups, because these methods hadn't yet been used to prove anything the older methods could not accomplish. Soon after, Burnside himself used the methods of Frobenius to obtain an elegant solution of a long open problem which he had tried and failed to solve for many years! The second edition of his textbook acknowledged his newfound appreciation for representation theory and included an introduction to the representation theory of finite groups. This is a powerful and elegant theory with few prerequisites; a readable modern introduction is James and Liebeck, Representations and Characters of Groups. A fine followup book would be Sturmfels, Algorithms in Invariant Theory, a very readable introduction to the invariant theory of finite groups, another very elegant and powerful theory. These two theories are like two gloves if you only wear one you will probably look a bit...eccentric. The corresponding theories for Lie groups are of course also powerful but much more involved; they work best for the reflection groups studied by the great Canadian geometer, H. S. M. Coxeter.)
Here's how to carry out this procedure for [itex]S_4[/itex] using GAP: fire up GAP and load the small groups library, then:
Notice that the output falls into blocks which correspond to natural "layers" in the abbreviated subgroup lattice. In more complicated examples, this might not happen automatically (or at all), but GAP provides a way to reorder rows and columns, which can help so "see" the shape of the graph.
To try to quickly identify the conjugacy classes up to isomorphism of groups, it's best to try the following commands line by line (referring to the table of marks) since GAP doesn't handle errors very cleanly, but in a very small group you can do it all at once:
Anyway, see if you can figure out how to get from the table of marks in the form output if you enter the command suggested above into a GAP session to the abbreviated subgroup graph in the figure. In this simple example, only one edge has a nontrivial labeling, the one from the vertex C labeled 4 D_3 down to the vertec C' labeled 6 C_2, which I labeled 3/2, meaning each subgroup in C includes 3 subgroups in C', and each subgroup in C' is included in 2 subgroups in C. Notice that 4*3 = 12 = 6*2.
If you're lazy, there is a separate package you can install which draws the nonabbreviated subgroup lattice, which is only useful for very small groups, but some of you may wish to find it and try it. It's called XGAP.
For those interested in Kleinian geometry, GAP also enables one to quickly draw a sublattice of the full subgroup lattice, the lattice of stabilizers, which is dual to the lattice of fixsets (defined just as in classical Galois theory). The abbreviated stabilizer lattice is very interesting for many reasons:
GAP also handles groups defined by means of generators and relations, and the above procedure works for them too, you simply first use GAP to obtain a permutation representation of your group. And GAP can work with matrix Lie groups fairly readily, which is particularly useful for studying reflection groups, e.g. the group E8 is rather famous these days due to Garrett Lisi's proposed theory. (Garrett is a sometime PF poster in the "Beyond the Standard Model" subforum, incidently!) GAP also recognizes other useful ways of defining groups, but these are probably of interest mainly to specialists.
Figure: Abbreviated subgroup lattice of S4 (symmetric group on four elements)
For those who don't already know: GAP is a powerful open source software package for computational algebra, especially computational group theory and allied subjects. This long running project is remarkable for having harmoniously developed under dozens of developers and some years ago, when the leaders retired, leadership was successfully handed on the new generation. I'll have to give links later to the huge GAP documentation book, approximately as heavy and as essential for anyone interested in group theory as MTW is for anyone interested in gravitation theory, not as easy to read as MTW, but available for free download. The software itself can be installed with a few mouseclicks, for those who use Linux (at least, if you use a distro sufficiently closely related to Debian to know what to do with a deb file), and I am pretty sure it is also available for other OSs.
GAP is among other things a powerful programming language, but you can get a great deal of work done without ever writing any GAP programs. Noone would accuse GAP of using elegant syntax, I think (compare Macaulay2, which has an attractive and mathematically natural syntax), but the unparalleled power of GAP makes this failing (shared with say, Mathematica, some would say) acceptable.
The genesis of this post is that someone asked in
https://www.physicsforums.com/showthread.php?p=2619232#post2619232
about listing and identifying the subgroups of a specific group (the user didn't say, but from context it seems he/she means a not too huge permutation group). And a bit earlier, someone asked for a polynomial over the rationals whose Galois group is the group of unit quaternions (the eight element finite group generated by Hamilton's three unit quaternions i,j,k). The first question is easily answered by GAP, and a correct answer to the second question is easily confirmed with GAP, although finding a polynomial which works is probably not so trivial.
GAP comes with a huge database (if RAM is limited on your machine, you can choose not to load all the database upon starting GAP), including:
 a canonical list of all sufficiently small finite groups up to isomorphism,
 a canonical list of all sufficiently small transitive permutation groups, i.e. all actions by finite groups on sufficiently small finite sets, or if you like, all Gsets X where X is not too large,
 a canonical list of all sufficiently small primitive permutation groups, i.e. all irreducible Gsets X where X is not too large (irreducible means: no nontrivial quotient Gsets; like groups themselves, Gsets can be built up from the simple objects in the appropriate category, in this case irreducible Gsets),
 table of marks for all sufficiently small permutation groups,
 character tables for the linear representations of all sufficiently small groups.
GAP does not provide a translation of its list of small groups into the ways in which the older literature typically refered to them, so it's useful to keep handy a small dictionary:
Code:
SmallGroup Name
[1,1] C1
[2,1] C2 ~ A2
[3,1] C3 ~ A3
[4,1] C4
[4,2] D2
[5,1] C5
[6,1] D3 ~ S3
[6,2] C6
[7,1] C7
[8,1] C8
[8,2] C2 x C4
[8,3] D4 ~ C2 wr C2
[8,4] Q4 = <p,qp^2 = q^2 = (pq)^2>
[8,5] C2^3 ~ E(8)
[9,1] C9
[9,2] C3^2
[10,1] D5
[10,2] C10
[11,1] C11
[12,1] Q6 = <p,q p^3 = q^2 = (pq)^2>
[12,2] C12
[12,3] A4
[12,4] D6
[12,5] C2^2 x C3
[13,1] C13
[14,1] D7
[14,2] C14
[15,1] C15
[16,1] C16
[16,2] C4 x C4
[16,3] <p,q p^4 = q^4 = (pq)^2 = (p/q)^2 = e >
[16,4] <p,q p^4 = q^4 = e, pq = q/p >
[16,5] C2 x C8
[16,6] <p,q p^2 = q^2, (pq)^2 = e >
[16,7] D8
[16,8] <p,q p^2 = e, pqp = q^3 >
[16,9] Q8 = <p,q p^4 = q^2 = (pq)^2 >
[16,10] C4 x D2
[16,11] C2 x D4
[16,12] C2 x Q4
[16,13] <p,q,r p^2 = q^2 = r^2 = e, pqr = qrp = rpq >
[16,14] C2^4 ~ D2 x D2
[17,1] C17
[18,1] D9
[18,2] C18
[18,3] C3 x S3 ~ C3 wr C2
[18,4] a semidirect product C2 x C3^2
[18,5] C2 x C3^2
[19,1] C19
[20,1] C2 x C10 ~ Q10 = <p,q p^5 = q^2 = (pq)^2 >
[20,2] C20
[20,3] F(5:4)
[20,4] D10
[20,5] C2^2 x C5
[21,1] F(7:3)
[21,2] C21
[22,1] D11
[22,2] C22
[23,1] C23
[24,1] <p,q p^3, pqp/q, q^8 >
[24,2] C24
[24,3] SL(2,3) ~ <p,qp^3 = q^3 = (pq)^2 >, binary tetrahedral
[24,4] Q12 = <p,q p^6 = q^2 = (pq)^2 >
[24,5] C4 x S3
[24,6] D12
[24,7] C2 x Q6
[24,8] <p, qp^4 = q^6 = (pq)^2 = (p/q)^2 >
[24,9] C2 x C12
[24,10] C3 x D4
[24,11] C3 x Q4
[24,12] S4
[24,13] C2 wr C3 ~ C2 x A4
[24,14] C2 x D6
[24,15] C2^2 x C6
[25,1] C25
[25,2] C5^2
[26,1] C26
[26,2] D13
[27,1] C27
[27,2] C3 x C9
[27,3] C3 x C3^2 = <p,q p^3, q^3, (pq)^3, (p/q)^3 >
[27,4] C3 x C9 = <p,q q^3, q^1*p*q=p^2 >
[27,5] C3^3
[28,1] Q14 = <p,q p^7 = q^2 = (pq)^2 >
[28,2] C28
[28,3] D14
[28,4] C2^2 x C7
[29,1] C29
[30,1] C5 x S3
[30,2] C3 x D5
[30,3] D30
[30,4] C30
[31,1] C31
 GAP refers to DihedralGroup(8) for the eight element group which most group theorists (and myself) write [itex]D_4[/itex],
 wr means the wreath product, a notion with which most SA/Ms are probably unfamiliar, so I plan to devote a later post to explaining them in easily understood (I hope) terms.
Simply listing the subgroups up to isomorphism is not enough for group theory; it is crucial to list them by conjugacy class. Fortunately, GAP is up to the task: it has a way of defining lattices, computing the subgroup lattice, and identifying conjugacy classes. Because even small groups tend to have a huge number of subgroups, this is however inefficient. Moreover, the subgroup lattice is too complicated to draw (except in the simplest cases) unless you adopt a useful abbreviation in which you draw the lattice of conjugacy classes,
 labeling each vertex with
 the number of subgroups in the class
 a familiar name for the isomorphism type of the groups in the class
 draw an edge from between class C1 to the smaller class C2, labeled m/n where
 each subgroup in C1 contains m members of C2
 each subgroup in C2 is contained in n members of C1
(Some of you may know that in the first edition, Burnside famously commented in the introduction that his book ignored the then new methods of Frobenius, now taught to math and physics students as the representation theory of finite groups, because these methods hadn't yet been used to prove anything the older methods could not accomplish. Soon after, Burnside himself used the methods of Frobenius to obtain an elegant solution of a long open problem which he had tried and failed to solve for many years! The second edition of his textbook acknowledged his newfound appreciation for representation theory and included an introduction to the representation theory of finite groups. This is a powerful and elegant theory with few prerequisites; a readable modern introduction is James and Liebeck, Representations and Characters of Groups. A fine followup book would be Sturmfels, Algorithms in Invariant Theory, a very readable introduction to the invariant theory of finite groups, another very elegant and powerful theory. These two theories are like two gloves if you only wear one you will probably look a bit...eccentric. The corresponding theories for Lie groups are of course also powerful but much more involved; they work best for the reflection groups studied by the great Canadian geometer, H. S. M. Coxeter.)
Here's how to carry out this procedure for [itex]S_4[/itex] using GAP: fire up GAP and load the small groups library, then:
Code:
G := SymmetricGroup(4);
pts := MovedPoints(G);
# Lattice of subgroups
tom := TableOfMarks(G);
Display(tom, rec( form := "supergroups"));
Display(tom, rec( form := "subgroups"));
num := Length(List(ClassTypesTom(tom)));
To try to quickly identify the conjugacy classes up to isomorphism of groups, it's best to try the following commands line by line (referring to the table of marks) since GAP doesn't handle errors very cleanly, but in a very small group you can do it all at once:
Code:
List([1..num],j>[j,IsTransitive(RepresentativeTom(tom,j),[1..deg])]);
List([1..num],j>[j,IdSmallGroup(RepresentativeTom(tom,j))]);
If you're lazy, there is a separate package you can install which draws the nonabbreviated subgroup lattice, which is only useful for very small groups, but some of you may wish to find it and try it. It's called XGAP.
For those interested in Kleinian geometry, GAP also enables one to quickly draw a sublattice of the full subgroup lattice, the lattice of stabilizers, which is dual to the lattice of fixsets (defined just as in classical Galois theory). The abbreviated stabilizer lattice is very interesting for many reasons:
 identifies the "geometric elements" in the appropriate "finite geometry" defined by our permutation group, e.g. points, lines for a finite projective plane,
 tells how these objects are related to one another (e.g. so many points lie in each line),
 gives more information than Polya counting, by passing to a suitable wreath product and taking the abbreviated subgroup lattice of the new permutation group,
 problems in elementary combinatorics can be formulated in terms of structors (aka combinatorial species a structor a certain kind of functor) and then this viewpoint can be seen as a reformulation of combinatorics in terms of group actions,
 gives a kind of common generalization of classical Galois theory and the theory of Boltzmann entropy (log of multinomial coefficient; closely related to Shannon's information theory); the fixsets up to conjugacy and inclusion relations captured by the table of marks are analogous to entropies and conditional entropies.
GAP also handles groups defined by means of generators and relations, and the above procedure works for them too, you simply first use GAP to obtain a permutation representation of your group. And GAP can work with matrix Lie groups fairly readily, which is particularly useful for studying reflection groups, e.g. the group E8 is rather famous these days due to Garrett Lisi's proposed theory. (Garrett is a sometime PF poster in the "Beyond the Standard Model" subforum, incidently!) GAP also recognizes other useful ways of defining groups, but these are probably of interest mainly to specialists.
Figure: Abbreviated subgroup lattice of S4 (symmetric group on four elements)
Attachments

4.1 KB Views: 439
Last edited: