%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Chapter{Subgroup Lattices - Examples} {\XGAP} provides a graphical interface to the lattice or a partial lattice of subgroups of groups. For finitely presented groups it gives you easy access for example to the low index, prime quotient and Reidemeister-Schreier algorithms in order to build a partial lattice interactively. For other types of groups it provides easy access to many of the group functions (for example, the normalizer, normal subgroups, and Sylow subgroups). This chapter explains how to use this interface by way of examples. Chapter "Subgroup Lattices - Systematic Description" gives details about the various options and menus available. These two chapters will not describe how to write your own programs using the graphic extensions supplied by {\XGAP}, see chapters "Graphic Sheets - Basic graphic operations" to "Graphic Graphs" for details. It is assumed that you have already started {\XGAP}. On most systems you do this by typing \begintt user@host:~> xgap \endtt on the command line. Ask your system administrator if this does not work. This command will create a new window, the so called {\GAP} window, in which {\GAP} is awaiting your input. Depending on the window system and window manager you use, placing a new window on your screen might be done automatically or might require you to use the mouse to choose a position for the window and pressing the left mouse button to place the window. The small arrow or cross you see on your screen is called a pointer. Although the device used to move this pointer can be anything, a mouse, a track ball, a glide-pad, or even something as exotic as a rat, we will use the term mouse to refer to this pointer device. In case that some computation takes longer than expected, for instance the low index and the prime quotient can be quite time consuming, you can always interrupt a computation by making the {\GAP} window active and pressing <CTRL-C> or selecting `Interrupt' in the `Run' menu. Again, making a window active is system and window manager dependent. In most cases you either have to move the pointer inside the {\GAP} window or you have to click on the title bar of the {\GAP} window. Note that for each of the following examples there is a small {\GAP} script in the `examples' subdirectory of the {\XGAP} home directory which contains the necessary commands. However we consider it better for learning {\XGAP} in a first time session if you type the commands by hand as suggested in the next few sections of this manual. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{The Subgroup Lattice of the Dihedral Group of Order 8} This section gives you an example on how to use the function `GraphicSubgroupLattice' (see "GraphicSubgroupLattice" for details), which will display the Hasse diagram of the subgroup lattice of a given group. Using the dihedral group of size $8$ as example the following will show you most features of the `GraphicSubgroupLattice' program. This exercise is best carried out in front of {\XGAP}, trying the various commands yourself. First you have to define a group in {\GAP}, this example uses a dihedral group defined as polycyclic group. \begintt gap> d8 := DihedralGroup(8); <pc group of size 8 with 3 generators> gap> SetName(d8,"d8"); \endtt Now you ask for a graphical display by \begintt gap> s := GraphicSubgroupLattice(d8); <graphic subgroup lattice "GraphicSubgroupLattice of d8"> \endtt {\XGAP} will open a window containing a new graphic sheet, a menu bar (menus are described below) above the graphic sheet and a title. On most systems the title will be either below the graphic sheet or above the menu bar. The dimension of the graphic sheet is fixed, changing the size of the window will *not* change the size of the graphic sheet, see "GraphicSubgroupLattice, Poset Menu" how to resize the graphic sheet. It is possible that the graphic sheet is larger (depending on the lattice it might be much larger) than the window. In this case the window will contain so called scrollbars which allow you to select the portion of the graphic sheet which will be displayed. {\XGAP} first shows only the whole group (which is already selected) and the trivial subgroup, connected by a line indicating inclusion. `ConjugacyClassesSubgroups' computes and returns the conjugacy classes of subgroups, so summing up the sizes of the classes tells you how many elements the lattice has. \begintt gap> Sum( List( ConjugacyClassesSubgroups(d8), Size ) ); 10 \endtt $10$ is small enough to use `AllSubgroups' without painting the screen black. After you have clicked this menu entry in the `Subgroups' menu you see the complete Hasse diagram in the graphic sheet. The following initial remarks can be made about the graphical representation of the subgroup lattice: \beginlist \item{--} The vertex representing the trivial subgroup is labeled $1$. \item{--} Vertices representing subgroups of the same size are drawn at the same height. They are said to be ``on the same level''. In our example the subgroups that belong to the vertices $2$, $4$, $5$, $8$ and $9$ all have size 2, and the subgroups of $3$, $6$, and $7$ have size $4$. The default behaviour is to place a vertex above another one if the size of the subgroup represented by the first vertex is larger than the size of the subgroup of the second, but see "GraphicSubgroupLattice" for details. At the right edge of the graphic sheet each level is labeled with the index of the subgroups contained. See "levelsintro" for details on the labelling of levels. \item{--} Vertices belonging to the same conjugacy class are placed closely together. In our example the subgroups of $4$ and $5$ form one conjugacy class. \endlist The initial placement of the vertices chosen by `GraphicSubgroupLattice' might not be optimal or you might want to choose a different one in order to exploit certain features of the diagram. It is therefore possible to move the vertices around using the mouse. The mouse together with the left mouse button can be used to move and select vertices. A selected vertex is represented by a thicker circle, colored red if your screen supports color. For example, in order to *move* vertex $4$ use the mouse to place the pointer inside the circle around $4$ and press the *left* mouse button. Keep the mouse button pressed and start moving the mouse. The vertex will now follow the pointer. Because of the height restrictions given by the size it is not possible to move $4$ above $6$ or below $1$. It must always stay within its level. If you release the left mouse button vertex $4$ will stay at its current position and the rest of the conjugacy class (in this example $5$) will be moved to this new position. In order to *select* vertex $G$ place the pointer inside the diamond around $G$, press the *left* mouse button and release it immediately. Do not move the mouse while you hold down the left mouse button. Vertex $G$ now has a slightly thicker boundary and is red if you have a color screen. There are two different ways to select more than one vertex, see "A Partial Subgroup Lattice of the Symmetric Group on 6 Points" or "GraphicSubgroupLattice, Selecting Vertices". On the top of the window, above the graphic sheet, you can see a list of menu names: `Sheet', `Poset', and `Subgroups'. In order to open any of these *pull down menus* place the pointer inside the button containing the menu name and press the left mouse button. Keep the button pressed. A pull down menu will be shown and by moving the pointer down you can choose a menu entry. By choosing an entry and then releasing the mouse button the entry is selected, the corresponding function is executed and the pull down menu is closed. If you release the mouse button while the pointer is outside the pull down menu the menu is closed without selecting any entry. Note that this behaviour is different from that of some other graphical user interfaces such as for example Windows. Now select `Change Labels' from the `Poset' menu. If this entry is not available you have failed to select vertex $G$. After selecting `Change Labels' a small dialog box is opened asking for a label. Type in `D8' and press the <return> key or click on `OK'. The label of vertex $G$ will now be changed to ``$D8$''. Note that in the X Window System you have to move the pointer on the text field if you want to edit the label. In order to find out which vertex represents the centre of $D_8$, first select vertex $D8$ and then the menu entry `Centres' from the `Subgroups' menu. In case of a color screen, vertex $D8$ will be selected and colored red, and vertex $2$ will be colored green. The color green indicates that vertex $2$ is the result of a computation. There will also be a message in the {\GAP} window saying that vertex $2$ represents the centre of the group belonging to vertex $D8$. \begintt #I Centres (D8) --> (2) \endtt Most of the menu entries in `Subgroups' should be self-explanatory, for details and the difference between `Closure' and `Closures' see "GraphicSubgroupLattice, Subgroups Menu". If you have selected some vertices (in the example $D8$ is now selected), and you want to investigate the subgroups corresponding to these vertices further in {\GAP}, the function `SelectedGroups' will return a list of these subgroups (note that you can also achieve calling this function by selecting `SelectedGroups to GAP' in the `Subgroups' menu): \label{gapxgap} \begintt gap> SelectedGroups(s); [ d8 ] \endtt On the other hand, the functions supplied via the `Subgroups' menu are by far not all functions applicable to groups. In order to show results of a computation in {\GAP} in the diagram, you can use `SelectGroups'. The function `SelectGroups' allows you to mark any set of subgroups of $D_8$ in the diagram. For instance, you can compute the lower central series of this (nilpotent) group in {\GAP}. \begintt gap> l := LowerCentralSeries(d8); [ d8, Group([ f3 ]), Group([ <identity> of ... ]) ] gap> SelectGroups(s,l); \endtt This lower central series corresponds to the vertices $D8$, $2$ and $1$ which will now be selected. If, as it is not the case in this example, the subgroups are not yet depicted in the lattice, a warning appears in the {\GAP} command window. You have to use `InsertVertex' to insert a new vertex into the lattice (note that you can also achieve this by selecting `InsertVertices from GAP' in the `Subgroups' menu, see section "InsertVertex" for the complete description of this function or section "xgapgap" for an example). To summarize the above: the function `SelectedGroups' can be used to transfer information from the diagram to {\GAP}, the functions `SelectGroups' and `InsertVertex' can be used to transfer information from {\GAP} to the diagram. In order to finish this example, close the window by selecting `close graphic sheet' from the `Sheet' menu. This will close the window containing the Hasse diagram of $D_8$. In this example you have learned, how to display the Hasse diagram of the subgroup lattice of a group using `GraphicSubgroupLattice', how to use the mouse to move and select vertices, how to select a menu entry and how to transfer information between the Hasse diagram and {\GAP} using `SelectGroups' and `SelectedGroups'. In order to learn more about the menus `Sheet' and `Poset', which were only mentioned very briefly, see "GraphicSubgroupLattice, Sheet Menu", and "GraphicSubgroupLattice, Poset Menu". % obsolete: %This example also did not discuss %two additional menus, namely the `Information' and `Sheet' menu. The first %is discussed in "A Partial Subgroup Lattice of the Symmetric Group on 6 %Points" and "GraphicSubgroupLattice, Information Menu", the latter in %"GraphicSubgroupLattice, Sheet Menu". %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{A Partial Subgroup Lattice of the Symmetric Group on 6 Points} This section investigates the subgroup lattice of $S_6$. \begintt gap> s6 := SymmetricGroup(6); Sym( [ 1 .. 6 ] ) gap> SetName(s6,"S6"); gap> cc := ConjugacyClassesSubgroups(s6);; gap> Sum(List(cc,Size)); 1455 \endtt As there are $1455$ subgroups, displaying the whole lattice of subgroups would not be helpful because there are simply too many. Therefore this example builds only a partial subgroup lattice. We assume that you are familiar with the general ideas, mouse actions and menus, which were discussed in "The Subgroup Lattice of the Dihedral Group of Order 8". We again start to build a partial lattice, by using `GraphicSubgroupLattice' (see "GraphicSubgroupLattice"). After you have entered \begintt gap> s := GraphicSubgroupLattice(s6); <graphic subgroup lattice "GraphicSubgroupLattice of S6"> \endtt {\XGAP} will open a window containing a new graphic sheet with two connected vertices labeled $1$ and $G$. Vertex $1$ represents the trivial subgroup and vertex $G$ the group $S_6$. Vertex $G$ is already selected, so it will be red if your screen supports color. {\XGAP} can automatically write a protocol of all the subsequent actions you perform via mouse clicks. This is convenient because in comparison to normal {\GAP} sessions you do not have the script of typed commands. You can activate this feature by selecting `Start Logging' from the `Subgroups' menu. {\XGAP} prompts you for a filename via a file selector box. See "loggingfacility" for details about this feature. In order to find all subgroups of size $60$, we cannot not use the `Subgroups' menu directly, so go back into the {\GAP} window and extract the conjugacy classes of `cc' whose representatives have size $60$. \begintt gap> c60 := Filtered(cc,x->Size(Representative(x))=60);; gap> s60 := List(c60,Representative); [ Group([ (1,2)(3,4), (1,3,5) ]), Group([ (1,2)(3,4), (1,2,3)(4,5,6) ]) ] \endtt \label{xgapgap} We now use the function `InsertVertex' (see "InsertVertex") to add these two subgroups to your partial lattice. \begintt gap> for g in s60 do InsertVertex(s,g); od; \endtt Note that we could have achieved this result with the entry `InsertVertices from GAP' in the `Subgroups' menu, see "InsertVertex". The Hasse diagram now contains four vertices. The new vertices are *not* selected automatically. You can do this as mentioned above by clicking with the *left* mouse button on them. Selecting `Conjugate Subgroups' from the `Subgroups' menu adds the complete conjugacy classes. Please do this first for vertex $2$ and then for vertex $3$ such that the numbering of vertices in the following description is correct! In order to find out what type of subgroups we are looking at, use another kind of menu not discussed so far, namely the ``Information'' menu. Place the pointer inside vertex $3$, press the *right* mouse button and release it immediately. This will pop up a new window, containing some text describing vertex $3$ (as mentioned above, depending on the window system and window manager, placing this window on the screen might require some interaction with the mouse). \begintt Size 60 Index 12 IsAbelian unknown IsCentral unknown IsCyclic unknown IsNilpotent false IsNormal false IsPerfect true IsSimple unknown IsSolvable false Isomorphism unknown \endtt Note that {\GAP} does not yet automatically draw the conclusion that a nonsolvable subgroup is also not abelian, cyclic or central. Place the pointer on top of the entry ``Isomorphism'' and press the *left* mouse button. After a while this entry is changed to \begintt Isomorphism [ 60, 5 ] \endtt telling you that the subgroup represented by vertex $3$ is isomorphic to the alternating group on five symbols. The notation `[ 60, 5 ]' comes out of the small groups library and is the only information about the isomorphism type we can get from {\GAP4} up to now. Select <close> to close the ``Information'' menu. Repeat this with vertex $2$, you will see that the subgroup of vertex $2$ is also isomorphic to $A_5$, however these two $A_5$ inside $S_6$ are not conjugate in $S_6$. The ``Information'' menu is described in detail in "GraphicSubgroupLattice, Information Menu". Now we want to compute the normalizers of the elements of the conjugacy class containing the subgroup of vertex $3$. You could either select vertex $3$ and then <Normalizers> and repeat this process for the vertices $9$ to $13$, or you can first select the vertices $3$, $9$ to $13$ and then select <Normalizers>. But how to select more than one vertex? If you first select $3$ and then $9$, vertex $3$ will get deselected as soon as $9$ gets selected. However, if you select vertex $3$, place the pointer inside vertex $9$, hold down the <SHIFT> key on your keyboard and then select vertex $9$ using the left mouse button, vertex $9$ will be selected in addition to vertex $3$. Another method to select more than one vertex is to use the rubber band to catch vertices inside a rectangle. Place the pointer left and a bit higher than vertex $3$ *outside* any other vertex. Press the *left* mouse button and hold it down. Now, using the mouse, move the pointer right and slightly below vertex $13$. You see a rectangle, one corner at your start position and the other following the pointer. If vertices $3$ and $9$ to $13$ are all inside this rectangle, release the mouse button. Now these vertices are selected. Select `Normalizers' from the `Subgroups' menu to compute and display the normalizers. Now select vertex $3$ and $4$ and compute the intersection. The intersection is of size $10$. Select this intersection and use `SelectedGroups' to get a {\GAP} record describing the subgroup. \begintt gap> l := SelectedGroups(s); [ Group([ (2,3)(4,6), (1,2)(3,4) ]) ] gap> u := l[1]; Group([ (2,3)(4,6), (1,2)(3,4) ]) \endtt In order to find out which subgroups of the complete lattice lie above the subgroup `u' you can use `Intermediate Subgroups'. You select the whole group in addition to `u' and choose `Intermediate Subgroups' in the `Subgroups' menu. You get 6 groups, some of them are already in the lattice, the others are added. There is another feature we have not seen yet. Close the current graphic sheet and start again with a fresh one. \begintt gap> Close(s); gap> s := GraphicSubgroupLattice(s6); <graphic subgroup lattice "GraphicSubgroupLattice of S6"> \endtt In order to compute a Sylow $2$ subgroup select `Sylow Subgroup' from the `Subgroups' menu. A small dialog box will pop up asking for a prime, type in $2$ and press <return> or click on `OK'. Now select this new vertex $2$ representing the Sylow $2$ subgroup and compute its normal subgroups. This is rather slow because the function checks for each new vertex if the corresponding subgroup is conjugate to an old one of the same size. %obsolete?: %There is however a limit on the index of the normalizer or %subgroup up to which this test is performed. % %\begintt %gap> s.limits.conjugates; %100 %\endtt % %If `limit.conjugates' contains a positive number the index of the %normalizer of the new subgroup is checked. If `limit.conjugates' contains %a negative number, only the index of the subgroup itself is checked. If %the index is less than the absolute value then the conjugacy test is %carried out. Change this limit to $-10$. % %\begintt %gap> s.limits.conjugates := -10; %-10 %\endtt % %Select vertex $3$ and compute a random conjugate by selecting `Random %Conjugate' from the `Subgroups' menu. Select this new vertex and compute %its normal subgroups. You will see that now the vertices of the new %subgroups appear faster on the graphic sheet, however, they have a %different shape. They are represented by a square instead of a circle. %A square is meant as a danger sign, because {\GAP} has not checked if %subgroups associated with square vertices are conjugate to any of the %other subgroups. Therefore these subgroups might be (and in this example %will be) conjugate to an old subgroup. %FIXME: do we want this feature? %In order to untangle the Hasse diagram you can move the new (selected) %vertices en block. Hold down the <SHIFT> key and move any of the new %vertices to the right. All selected vertices will automatically be moved %as soon as you release the left mouse button. %FIXME: This feature does not yet exist. This is now the end of our partial investigation of the (partial) subgroup lattice of $S_6$, close the graphic sheet(s) using `close graphic sheet' of the `Sheet' menu. If you started the logging facility of {\XGAP} as described above you now have a file (probably called `xgap.log' if you did not change the default) describing the actions we performed. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{A Partial Subgroup Lattice of the Cavicchioli Group} This section investigates the following finitely presented group $C_2$, which was first investigated by Alberto Cavicchioli in \cite{Cav86}: $$ \langle a, b \;;\; aba^{-2}ba=b, (b^{-1}a^3b^{-1}a^{-3})^2=a^{-1}\rangle. $$ In this example we will show a way to prove a finitely presented group to be infinite, and to find some big nonabelian factor groups of it. The following {\GAP} commands define $C_2$. \begintt gap> f := FreeGroup( "a", "b" ); a := f.1;; b := f.2;; <free group on the generators [ a, b ]> gap> c2 := f / [ a*b*a^-2*b*a/b, (b^-1*a^3*b^-1*a^-3)^2*a ]; <fp group on the generators [ a, b ]> gap> SetName(c2,"c2"); \endtt We again assume that you are familiar with the general ideas, mouse actions and menus, which were discussed in "The Subgroup Lattice of the Dihedral Group of Order 8" and "A Partial Subgroup Lattice of the Symmetric Group on 6 Points". In order to build a partial lattice of a finitely presented group, you again use the function `GraphicSubgroup\-Lattice'. But if the first argument to `GraphicSubgroupLattice' is a finitely presented group the available menus are different from the example in the previous section. After you have entered \begintt gap> s := GraphicSubgroupLattice(c2); <graphic subgroup lattice "GraphicSubgroupLattice of c2"> \endtt {\XGAP} will open a window containing a new graphic sheet. Compared to the interactive lattice of a permutation group as described in the previous section, there are the following differences: -- There is only one vertex instead of two. This vertex labeled $G$ is the whole group $C_2$. There is no vertex for the trivial subgroup (yet). -- If you pull down the `Subgroups' menu, you will see that this menu is now very different. It gives you access to various algorithms for finitely presented groups but most of the entries from the last two examples are missing because most of the {\GAP} functions behind these entries are not applicable to (infinite) finitely presented groups. This example will show you how to prove that $C_2$ is infinite. First look at the abelian invariants in order to see what the commutator factor group is. In order to compute the abelian invariants pop up the ``Information'' menu. This is done in exactly the same manner as in the previous section. Place the pointer inside vertex $G$, press the *right* mouse button and release it immediately. This ``Information'' menu is described in detail in "GraphicSubgroupLattice for FpGroups, Information Menu". \begintt Index 1 IsNormal true IsFpGroup unknown Abelian Invariants unknown Coset Table unknown IsomorphismFpGroup unknown Factor Group unknown \endtt This tells you what {\XGAP} already knows about the group associated with vertex $G$. In order to compute the abelian invariants click onto this line. After a while this entry will change to \begintt Abelian Invariants perfect \endtt telling you that $C_2$ is perfect. So none of the `Subgroups' menu entries `Abelian Prime Quotient', `All Overgroups', `Conjugacy Class', `Cores', `Derived Subgroups', `Intersection', `Intersections', `Normalizers' or `Prime Quotient' will compute any new subgroups. In order to avoid accidents the menu entries `Abelian Prime Quotient', `All Overgroups', `Epimorphisms (GQuotients)', `Conjugacy Class', `Low Index Subgroups', and `Prime Quotient' from the `Subgroups' menu are only selectable if exactly one vertex is selected because the functions behind these entries are in general quite time and space consuming. Close the ``Information'' window and select `Low Index Subgroups' from the `Subgroups' menu. A small dialog box will pop up asking for a limit on the index. Type in $12$ and press <return> or click on `OK'. In general it is hard to say what kind of index limit will still work, for some groups even $5$ might be too much while for others $20$ works fine, see also "ref:LowIndexSubgroupsFpGroup". {\GAP} computes $10$ subgroups of index $11$ and $8$ subgroups of index $12$. If you now start to check the abelian invariants of the index $12$ subgroups you will find out that all subgroups represented by vertices $3$ to $10$ have a finite commutator factor group except the subgroup belonging to vertex $4$ which has an infinite abelian quotient. Therefore the group $C_2$ itself is infinite. Now we want to investigate $C_2$ a little further using {\GAP}. Select vertices $3$, $4$, and $5$ and switch to the {\GAP} window. Use `SelectedGroups' to get the subgroups associated with these vertices. \begintt gap> u := SelectedGroups( s ); [ Group([ a, b*a^2*b^-2, b*a*b^2*a^-1*b^-1*a^-1*b^-1, b^4*a^-2*b^-2, b^2*a^3*b^-1*a^-1*b^-2 ]), Group([ a, b^2*a*b^-1*a^-1*b^-1, b^3*a^-1*b^-1, b*a*b*a^3*b^-1 ]), Group([ a, b^2*a*b^-1*a^-1*b^-1, b*a^3*b^-2, b^4*a^-1*b^-3, b*a*b^3*a^-1*b^-1 ]) ] \endtt `FactorCosetOperation' computes for each of these subgroups $u_i$ the operation of $C_2$ on its cosets. It returns the result as a homomorphism of $C_2$ onto a permutation group. The operation on $u_i$ is therefore a permutation representation of the factor group $$C_2 / Core(u_i).$$ Using `DisplayCompositionSeries' we can identify these factor groups. \begintt gap> p := List( u, x -> FactorCosetOperation( c2, x ) );; gap> l := List( p, Image );; gap> for x in l do DisplayCompositionSeries(x); Print("\n"); od; G (2 gens, size 95040) | M(12) 1 (0 gens, size 1) G (2 gens, size 660) | A(1,11) = L(2,11) ~ B(1,11) = O(3,11) ~ C(1,11) = S(2,11) ~ 2A(1,11) = U(2,11) 1 (0 gens, size 1) G (2 gens, size 239500800) | A(12) 1 (0 gens, size 1) \endtt (This display can look a little different according to the {\GAP} version you use.) So $C_2$ contains the Mathieu group $M_{12}$, the alternating group on $12$ symbols and $PSL(2,11)$ as factor groups. Therefore it would have been possible to find vertex $4$ using `Epimorphisms (GQuotients)' instead of `Low Index Subgroups'. Close the graphic sheet by selecting the menu entry `close graphic sheet' from the `Sheet' menu and start with a fresh one. \begintt gap> s := GraphicSubgroupLattice(c2); <graphic subgroup lattice "GraphicSubgroupLattice of c2"> \endtt Select `Epimorphisms (GQuotients)' from the `Subgroups' menu. This pops up a menu similar to the ``Information'' menu (see "GraphicSubgroupLattice for FpGroups, Subgroups Menu"). \begintt Sym(n) Alt(n) PSL(d,q) Library User Defined \endtt Select <PSL(d,q)>, which pops up a dialog box asking for a dimension. Enter `2' and click on <OK>. Then a second dialog box pops up asking for a field size. Enter `11' and click on <OK>. After a short time of computation the display in the `Epimorphisms (GQuotients)' menu changes and shows \begintt PSL(2,11) 1 found \endtt telling you, that {\GAP} has found $1$ epimorphism (up to inner automorphisms of $PSL(2,11)$) from $C_2$ onto $PSL(2,11)$. Click on <display point stabilizer> to create a new vertex representing a subgroup $u$ such that the factor group of $C_2 / Core(u)$ is isomorphic to $PSL(2,11)$. You could have clicked on <display> to create a new vertex representing the kernel of the epimorphism. This is now the end of our partial investigation of the (partial) subgroup lattice of $C_2$, you have seen that $C_2$ is infinite and contains $M_{12}$, $Alt(12)$, and $PSL(2,11)$ as factor groups. Close the graphic sheet by selecting `close graphic sheet' from the `Sheet' menu. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{A Partial Subgroup Lattice of the Trefoil Knot Group} This section investigates the following finitely presented group, the trefoil knot group $K_3$. $$ \langle a, b \;;\; aba = bab \rangle $$ This examples shows some limitations of the methods available, in particular if infinite factors occur. \begintt gap> f := FreeGroup( "a", "b" ); <free group on the generators [ a, b ]> gap> k3 := f / [ f.1*f.2*f.1 / (f.2*f.1*f.2) ]; <fp group on the generators [ a, b ]> gap> s := GraphicSubgroupLattice(k3); <graphic subgroup lattice "GraphicSubgroupLattice"> \endtt If you compute the Abelian invariants of $K_3$ you will see that the commutator factor group is isomorphic to the infinite cyclic group. If you try to compute the derived subgroups it works! Just click on `Derived Subgroups' in the `Subgroups' menu. A vertex appears in a level marked with `[ infinity, 1 ]'. However, there are not too many things you can do with such infinite index subgroups up to now, as we will illustrate below: First produce some more subgroups by `Low Index Subgroups' (for example with index limit 5). If you now try to compare one of the new subgroups with the derived subgroup, this is possible. If you however try to calculate the intersection of one of the finite-index subgroups with the derived subgroups, {\GAP} will run into an error: \begintt Error the coset enumeration has defined more than 256000 cosets: type 'return;' if you want to continue with a new limit of 512000 cosets, type 'quit;' if you want to quit the coset enumeration, type 'maxlimit := 0; return;' in order to continue without a limit, ... (a few lines follow) \endtt This can happen if the coset enumeration algorithm tries to enumerate the cosets of a subgroup with infinite index. This situation can also occur with other operations. You can leave this break loop by entering the command `quit;' or by clicking `Leave Break Loop' in the `Run' menu of the main {\XGAP} window. Earlier you have computed the subgroups of index at most $5$. There is one normal subgroup of index $2$ belonging to vertex $6$ and one of index $4$ belonging to vertex $8$. There is *no* line between those two vertices. Select both and click on `Compare Subgroups' in the `Subgroups' menu. A line appears and the line between vertices $8$ and $G$ vanishes. The reason for this is, that the `LowIndexSubgroupsFpGroup' call did not deliver the complete inclusion info. This can always happen for finitely presented groups in {\XGAP}. In this case you have to compare the subgroups manually by `Compare Subgroups'. Note that this can mean large computations, especially if the indices are huge. Now select vertex $10$ and choose `Cores' from the `Subgroups' menu. You will get a new vertex $12$ for an index $24$ subgroup. Select the vertices $12$ and $G$ and choose `Intermediate Subgroups' from the `Subgroups' menu. You will get lots of new vertices. Note that some of them are duplicates of those which were already in the lattice. This is because comparison of subgroups can be quite expensive and is therefore *not* performed automatically in the case of finitely presented groups. Select all vertices with a rubber band (click into the top left corner of the sheet, hold down the mouse and move the pointer to the lower right corner, then release the mouse button), and choose `Compare Subgroups' from the `Subgroups' menu. A few vertices will disappear and you get some messages in the {\GAP} window about merging of vertices. The display is also not fully correct with respect to conjugacy classes. `IntermediateSubgroups' does not return the complete information about conjugacy of subgroups. Because also conjugacy tests can be very expensive, they are also *not* performed automatically for finitely presented groups. Select `Test Conjugacy' from the `Subgroups' menu to trigger this test manually (note that all vertices are still selected!). The vertices belonging to conjugate subgroups are arranged together and if you move those containing the normal subgroup of index $24$ above this one you recognize the subgroup lattice of the symmetric group on $4$ points above that normal subgroup. This is now the end of our partial investigation of the (partial) subgroup lattice of $K_3$, close the graphic sheet by selecting `close graphic sheet' from the `Sheet' menu. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{A Partial Subgroup Lattice of a Finitely Presented Group} This section describes the investigation of the following finitely presented group: $$ G := \langle a, b \; ; \; a^6 = 1 \rangle $$ We will show especially how to deal with subgroups which have a very large index like those occuring in the prime quotient algorithm. Define the group and open the subgroup lattice window: \begintt gap> f := FreeGroup(2); <free group on the generators [ f1, f2 ]> gap> g := f/[f.1^6]; <fp group on the generators [ f1, f2 ]> gap> s := GraphicSubgroupLattice(g); <graphic subgroup lattice "GraphicSubgroupLattice"> \endtt First compute prime quotients by `Prime Quotient' in the `Subgroups' menu. You are asked for a prime and a class. Enter $2$ and $7$ respectively. You get lots of output in the {\GAP} command window and seven new vertices. Some of the corresponding subgroups have huge indices. Note that these groups are only represented as kernels of epimorphisms within {\GAP}. So explicit calculation of a coset table or a presentation could take very long or be absolutely impossible! Now compute epimorphisms onto the symmetric group on $3$ points by `Epimorphisms (GQuotients)' in the `Subgroups' menu, but use a polycyclic presentation as follows (the reason for this will be explained below): \begintt gap> IdGroup(SymmetricGroup(3)); [ 6, 1 ] gap> s3 := SmallGroup(6,1); <pc group with 2 generators> gap> IMAGE_GROUP := s3;; \endtt This first determines the identification number of the symmetric group on $3$ points within the small groups library, and then fetches this group as a polycyclic group. For groups of size less than $1000$ this is often a good way to get a polycyclic presentation. Note that `SymmetricGroup(3)' leads to a permutation group. The last statement stores the group in a variable which can be used by {\XGAP}. Select vertex $G$, then click on `Epimorphisms (GQuotient)' in the `Subgroups' menu and select `User defined' in the window that pops up. This will always use the group stored in the global variable `IMAGE_GROUP'. {\GAP} finds three epimorphisms. Display the three kernels by selecting <display> in the epimorphisms window. Note that the new vertex $9$ will be drawn on the line between vertices $2$ and $3$ because there is not yet a vertex in the level corresponding to index 6. You can move it aside by dragging it with the mouse to some better position within its level. Now select vertices $8$ and $11$ and calculate the intersection of the two subgroups of indices $137438953472$ and $6$ respectively. {\GAP} can calculate this intersection by calculating the subdirect product of the image groups of the epimorphisms (the index of the subgroup belonging to vertex $12$ in $G$ is $412316860416$ which is three times of the index of the subgroup belonging to vertex $11$). Note that this subdirect product can only be calculated because the two image groups are polycyclic groups. This is the reason why we needed $S_3$ as polycyclic group earlier. This is now the end of our partial investigation of the (partial) subgroup lattice of $G$, close the graphic sheet by selecting `close graphic sheet' from the `Sheet' menu. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{A Partial Subgroup Lattice of a Space Group} This section describes an investigation of an (infinite) space group provided by the catalogue CRYSTCAT of crystallographic groups and using the package CRYST. Here you will see that subgroups of finite index and of finite size can occur at the same time in a graphic subgroup lattice of an infinite group. Note that you have to install these packages to try this example. Load the packages, define the group and open the subgroup lattice window: \begintt gap> RequirePackage("crystcat");; gap> RequirePackage("cryst");; gap> g := SpaceGroupBBNWZ(4,6,3,1,2); SpaceGroupOnRightBBNWZ( 4, 6, 3, 1, 2 ) gap> s := GraphicSubgroupLattice(g); <graphic subgroup lattice "GraphicSubgroupLattice of SpaceGroupOnRightBBNWZ( 4, \ 6, 3, 1, 2 )"> \endtt This fetches the space group of dimension $4$, associated crystal system number $6$, $\Q$-class 3, $\Z$-class $1$, and space group type $2$ (see the CRYSTCAT documentation for an explanation of this). Now we calculate some maximal subgroups with finite index and choose three of them: \begintt gap> m := MaximalSubgroupClassReps(g,rec(latticeequal := true));; gap> mm := m{[1..3]}; [ <matrix group with 7 generators>, <matrix group with 7 generators>, <matrix group with 7 generators> ] \endtt Again refer to the CRYST package documentation for an explanation of these commands. Insert this list of three subgroups into the lattice by selecting `InsertSubgroups from GAP' from the `Subgroups' menu. Next calculate subgroups of infinite index but with finite size: \begintt gap> w := WyckoffPositions(g);; gap> ww := w{[1..3]}; [ < Wyckoff position, point group 11, translation := [ 0, 1/2, 0, 0 ], basis := [ ] > , < Wyckoff position, point group 11, translation := [ 0, 1/2, 0, 1/2 ], basis := [ ] > , < Wyckoff position, point group 11, translation := [ 0, 1/2, 1/2, 0 ], basis := [ ] > ] gap> www := List(ww,WyckoffStabilizer); [ <matrix group with 3 generators>, <matrix group with 3 generators>, <matrix group with 3 generators> ] \endtt Insert these subgroups into the lattice by selecting `InsertSubgroups from GAP' from the `Subgroups' menu. They will be inserted in the level for groups of size 8. Now you can compute the intersection of a subgroup with finite index and a subgroup with finite size, select for example vertex $2$ and vertex $5$ and choose `Intersection' from the `Subgroups' menu. You get a new vertex representing a subgroup of size $4$. If you now calculate the centralizers of the fifteen latticeequal maximal subgroups from above, you get among them four non-trivial cyclic subgroups: \begintt gap> c := List(m,x->Centralizer(g,x)); [ <matrix group with 1 generators>, Group([ ]), Group([ ]), Group([ ]), <matrix group with 1 generators>, Group([ ]), Group([ ]), <matrix group with 1 generators>, Group([ ]), <matrix group with 1 generators>, Group([ ]), Group([ ]), Group([ ]), Group([ ]), Group([ ]) ] \endtt Insert these into the graphic sheet by selecting `Insert Vertices from GAP' from the `Subgroups' menu. You will get four different new vertices representing groups with infinite index *and* infinite size. Each such vertex is placed into a level on its own, which is marked by `[ H1, <n>]' where <n> is replaced with subsequent natural numbers (see section "levelsintro" for details about levels). ``H1'' means Hirsch length 1, that is, each subnormal series of the group contains one and only one infinite cycle. In fact, since these are subgroups of space groups, it indicates that the translation subgroup is of dimension 1. (Note that by calculating the point groups of these centralizers you can in fact see, that the infinite cyclic groups consist of translations only.) Take two of these centralizers and calculate the closure by selecting `Closure' from the `Subgroups' menu. You will get a new subgroup of Hirsch length 2, which is also placed on a level of its own. Next select three of them, and calculate the closure. What do you observe? Also, select all four of them and calculate the closure. This time you get a subgroup of index 16, hence its level is marked by this finite index rather than a Hirsch number (which would be 4 here). Note that the finite index is used rather than the Hirsch length for this placement. Finally, check, whether the centralizers are normal in the whole space group by clicking on the vertices with the right mouse button and choosing `IsNormal' in the ``Information'' window, which springs up. Now form the closures of each of them with each of the size 8 point stabilizers. You will get some other subgroups of Hirsch length 1. Both the centralizers and the point stabilizers are abelian. Is this also true for the closures? This is now the end of our partial investigation of the (partial) subgroup lattice of $G$, close the graphic sheet by selecting `close graphic sheet' from the `Sheet' menu. %%% Local Variables: %%% mode: latex %%% TeX-master: "manual" %%% End: