Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

BRS: Subgroup lattice of a Permutation Group via GAP

  1. Mar 11, 2010 #1

    Chris Hillman

    User Avatar
    Science Advisor

    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. No-one 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
    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 G-sets X where |X| is not too large,
    • a canonical list of all sufficiently small primitive permutation groups, i.e. all irreducible G-sets X where |X| is not too large (irreducible means: no nontrivial quotient G-sets; like groups themselves, G-sets can be built up from the simple objects in the appropriate category, in this case irreducible G-sets),
    • table of marks for all sufficiently small permutation groups,
    • character tables for the linear representations of all sufficiently small groups.
    GAP has been so influential that the research literature often uses GAP notation, and other packages often reference these lists using GAP notation too. For example, number theorists often use pari/gp, another open source package available as a deb, which is designed for computations in algebraic number theory and elliptic curves, and which includes a Galois group utility which is even faster than the one in GAP and which quotes results in GAP notation.

    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 (Text):

    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,q|p^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,q|p^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, q|p^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
    Notational issues:
    • 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
      where only the minimal edges are drawn in a fairly obvious sense, to make something which looks like a decorated Hasse diagram (for a poset).
    The information required is contained in a useful construct little known outside group theory, the so-called table of marks popularized in one of the first group theory textbooks, the one by Burnside, which is still useful.

    (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 (Text):

    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)));
    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:
    Code (Text):

    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 non-abbreviated 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)

    Attached Files:

    Last edited: Mar 11, 2010
  2. jcsd
  3. Mar 11, 2010 #2

    Chris Hillman

    User Avatar
    Science Advisor

    BRS: Galois Group of a Polynomial over the Rationals via GAP

    the OP asked for a rational coefficient polynomial whose Galois group is the eight element group of unit quaternions.

    Most of you probably know that an irreducible separable degree n polynomial has a Galois group which is a transitive permutation group on the n roots, which may or not be a solvable group. The great theorem of Galois is that the polynomial is solvable by elementary operations (multiplication, addition) plus extraction of k-th roots iff the Galois group is solvable (which means it can be built up from smaller "factors" in a nice way, in a sense which is meaningful in group theory).

    Many SA/Ms may know that it is an important open problem whether every finite group arises as the Galois group of such a polynomial. Not so well known, perhaps, is that one can find and verify with GAP lists of examples of polynomials of degree n having as Galois group any desired transitive permutation group of degree n, up to degree 15 inclusive. This work is nontrivial; much of it has been done by Guenter Malle. Separable irreducible polynomials whose Galois group is not a symmetric group are not easy to find, as you will discover if you try some random examples!

    Here are some of my favorite examples:

    {\rm perm} \; {\rm group} & {\rm iso} \; {\rm class} & {\rm order} & {\rm polynomial} \\
    2T1 = S(2) & S_2 & 2 & x^2-x+1 \\
    3T1 = S(3) & S_3 & 6 & x^3-x^2-2x+1 \\
    3T2 = A(3) & A_3 & 3 & x^3-x^2+1 \\
    4T1 = C(4) & C_4 & 4 & x^4-x^3+x^2-x+1 \\
    4T2 = E(4) & C_2 \times C_2 & 4 & x^4-x^2+1 \\
    4T3 = D(4) & D_4 & 8 & x^4-2x^3+x-1 \\
    4T4 = A(4) & A_4 & 12 & x^4-2x^3+2x^2+2 \\
    4T5 = S(4) & S_4 & 24 & x^4-x^3+1 \\
    5T1 = C(5) & C_5 & 5 & x^5-x^4-4x^3+3x^2+3x-1 \\
    5T2 = D(5) & D_5 & 10 & x^5-2x^4+2x^3-x^2+1 \\
    5T3 = F(5) & F_{5:4} & 20 & x^5-9x^3-4x^2+17x+12 \\
    5T4 = A(5) & A_5 & 60 & x^5-x^4+2x^2-2x+2 \\
    5T5 = S(5) & S_5 & 120 & x^5-x^3-2x^2+1 \\

    [EDIT: strange, VB doesn't seem to handle a large table, so apparently I need to split it in half]

    {\rm perm} \; {\rm group} & {\rm iso} \; {\rm class} & {\rm order} & {\rm polynomial} \\
    6T1 = C(6) & C_6 & 6 & x^6-x^5+x^4-x^3+x^2-x+1 \\
    6T2 = D_6(6) & D_6 & 6 & x^6-3x^5-2x^4+9x^3-5x+1\\
    6T3 = S(3)[x]2 & S_3 \times C_2 & 12 & x^6+x^4-2x^3+x^2-x+1 \\
    6T4 = A_4(6) & A_4 & 12 & x^6+x^4-2x^2-1 \\
    6T5 = F_18(6) & C_3 \wr C_2 & 18 & x^6-3x^5+4x^4-2x^3+x^2-x+1 \\
    6T6 = 2A_4(6) & C_2 \wr C_3 & 24 & x^6-2x^5+2x^3-x-1 \\
    6T7 = [2^2]S(3) & S_4 & 24 & x^6+x^4-1 \\
    6T8 = 1/2[2^3]S(3) & S_4 & 24 & x^6+4x^5-9x^4-51x^3-46x^2+8 \\
    6T9 = F_18(6):2 & S_3 \times S_3 & 36 & x^6-3x^5+4x^4-x^3+x^2-2x+7 \\
    6T10 = 1/2[S(3)^2]2 & & 36 & x^6-x^5+x^4-x^3-4x^2+5 \\
    6T11 = [2^3]S(3) & C_2 \wr S_3 & 48 & x^6-x^5-x^3-x+1 \\
    6T12 = PSL(2,5) & A_5 & 60 & x^6-10x^4-7x^3+15x^2+14x+3 \\
    6T13 = F_36(6):2 & S_3 \wr C_2 & 72& x^6-2x^5+2x^4-x+1 \\
    6T14 = PGL(2,5) & S_5 & 120 & x^6+3x^4-2x^3+6x^2+1 \\
    6T15 = A(6) & A_6 & 360 & x^6-2x^4+x^2-2x-1 \\
    6T16 = S(6) & S_6 & 720 & x^6-x^5+x^3-x^2+1
    The designations of the iso classes is somewhat arbitrary, since many groups obtained by taking direct products of smaller groups are isomorphic to familiar groups, e.g. [itex]A_{12} \times C_2 \simeq C_2 \wr C_3[/itex].

    Here's how to check my work in GAP:
    Code (Text):

    x := Indeterminate(Rationals);
    f := x^6 - 2*x^5 + 2*x^3-x-1;
    G := TransitiveGroup(Degree(f),GaloisType(f));
    Here, I checked that the polynomial is irreducible, computed the Galois group, checked that it has degree 6; and asked GAP for its idenfification, which turns out to be 6T6.

    Notation: in the literature, 6T4 usually means the fourth transitive group of degree 6 in GAP's list.

    To check that f is separable, I should take the derivative and check that f' and f have no common factors. GAP would have complained if I tried to ask for the Galois group of a polynomial which is not separable; in practice, checking irreducibility is more important.

    Here's you do it in pari/gp:
    Code (Text):

    f := x^6 - 2*x^5 + 2*x^3-x-1
    gcd(f, deriv(f,x))
    Here, I checked that the polynomial is irreducible and separable, then computed the Galois group.

    The result: the Galois group of [itex]x^6 - 2x^5 + 2x^3-x-1[/itex] is, up to isomorphism of groups, the wreath product [itex]C_2 \wr C_3[/itex]. This is a finite group of order 24, a certain semidirect product, which contains a normal subgroup isomorphic to [itex]C_2^3[/itex] and a nonnormal subgroup isomorphic to [itex]C_2[/itex]. I plan to devote a later BRS posts to wreath products, but the idea is very simple: take three pairs of points, each acted on by C_2, and permute the pairs by C_3, obtaining a certain permutation group of degree six.

    You might notice that f is palindromic. It is no accident that its Galois group turns out to be a simple wreath product: a separable irreducible palindromic polynomial of degree 2n will always have a Galois group which is a transitive subgroup of the symmetry group of the n-cube, [itex]C_2 \wr S_n[/itex]. These groups are always solvable, so palindromic polynomials of degree 2n provide an interesting example of a class of polynomials of large degree which can be solved by radicals. See Littlewood, The Skeleton Key of Mathematics, Dover reprint, for a sketch of how to obtain this solution!

    You might want to know which of the transitive groups of degree six, say, are solvable, or primitive (no nontrivial "quotient" actions), or abelian. In GAP
    Code (Text):

    AllTransitiveGroups(NrMovedPoints,6, IsSolvable, true);
    AllTransitiveGroups(NrMovedPoints,6, IsPrimitive, true);
    AllTransitiveGroups(NrMovedPoints,6, IsAbelian, true);
    All of these transitive permutation groups are associated with finite Kleinian geometries, some more familiar than others, such as the primitive group PGL(2,5), the group of the finite projective line over the Galois field GF(5).

    There's an interesting connection with the BRS threads on cohomology
    which arises because Frobenius showed how to construct any transitive G-set which has a quotient X from the skew product [itex]X \, |\!\!\!\times_{\alpha} Y[/itex]. This is a sort of discrete fiber bundle with base the G-set X and the fibers all isomorphci to the H-set Y. Here, [itex]\alpha[/itex] is the "Frobenius cocycle", which really a one-cocycle in a certain variety of cohomology, and which also appears in dynamical system theory and the theory of operator algebras. If you know the Cayley graphs definition the actions on X, Y, then using [itex]\alpha[/itex] you can reconstruct the Cayley graph of the skew product. This construction obeys a some laws which are the analog of the "quotient law" in Shannon's information theory
    [tex] H(X \vee Y) = H(X) + H(Y/X) = H(Y) + H(X/Y) [/tex]
    which says that the information needed to describe the join of X, Y is the information needed to describe X plus the information needed to describe Y given X, and also the information needed to describe Y plus the information needed to describe X given Y.
    See Baumslag and Chandler, Group Theory, Schaum's Outlines (no need to sniff at Schaum's Outlines; Baumslag was a well known researcher in combinatorial group theory) for an introduction which unfortunately obscures the cohomology lurking in Frobenius's construction.

    Here are a few more examples of particular interest:
    7T5 = PGL(3,2) & PGL_3(2) & 168 & x^7-7x+3 \\
    8T5 = Q_8(8) & Q_4 & 8 & x^8+12x^6+36x^4+36x^2+9 \\
    8T8 = [D(4)]2 & C_4 \times C_2 & 8 & x^8-2 \\
    8T44 = [2^4]S(4) & C_2 \wr S_4 & 384 & x^8-x^5-x^4-x^3+1 \\
    8T48 = AL(8) & ASL_3(2) & 1344 &
    x^8+3x^7-x^6-10x^5-9x^4-x^3+7x^2+11x+4 \\
    10T5 = F(5) [x]C(2) & F_{5:4} \times C_2 & 40 & x^{10}-2 \\
    10T39 & C_2 \wr S_5 & 3840 & x^{10} + x^7 + x^5 + x^3 + 1 \\
    11T6 = M(11) & M_{11} & 7920 &
    x^{11} + 2x^{10} - 5x^9 + 50x^8 + 70x^7 - 232x^6 + 796x^5 + 1400x^4 - 5075x^3 + 10950x^2 + 2805x - 90
    • [itex]PGL(3,2)[/itex] is the simple group of order 168, acting on the projective plane over GF(2),
    • [itex]Q_4[/itex] is the eight element group of unit quaternions found by Hamilton,
    • [itex]F_{5:4}[/itex] is the Frobenius group of order 20,
    • [itex]C_2 \wr S_4[/itex] is the symmetry group of the four-cube,
    • [itex]C_2 \wr S_5[/itex] is the symmetry group of the five-cube,
    • [itex]M_{11}[/itex] is one of the sporadic simple groups found by Mathieu.
    If I recall correctly, all the sporadic finite simple groups, the Weyl groups of various reflection groups, and many other "interesting" finite groups, are now known to arise as the Galois groups of specific polynomials over the rationals.


    For degrees 2 through 9:
    J. M. C. Carro
    Code (Text):
    [/PLAIN] [Broken]
    For degrees 10 thru 11:
    Juergen Klueners and Guenter Malle
    Code (Text):
    [/PLAIN] [Broken]
    Last edited by a moderator: May 4, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: BRS: Subgroup lattice of a Permutation Group via GAP