sgrplats.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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

`FactorCosetAction' 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 -> FactorCosetAction( 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> LoadPackage("crystcat");;
gap> LoadPackage("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: