Lattice( G )
Lattice returns the lattice of subgroups of the group G in the form
of a record L, say, which contains certain lists with some appropriate
information on the subgroups of G and their conjugacy classes. In
particular, in its component L.classes, L provides the same list of
all conjugacy classes of all subgroups of G as is returned by the
ConjugacyClassesSubgroups command (see ConjugacyClassesSubgroups).
The construction of the subgroup lattice record L of a group G may be
very time consuming. Therefore, as soon as L has been computed for the
first time, it will be saved as a component G.lattice in the group
record G to avoid any duplication of that effort.
The underlying routines are a reimplementation of the subgroup lattice routines which have been developed since 1958 by several people in Kiel and Aachen under the supervision of Joachim Neubaccent127 user. Their final version, written by Volkmar Felsch in 1984, has been available since then in Cayley (see BC92) and has also been used in SOGOS (see Sog89). The current implementation in GAP by Jaccent127 urgen Mnich is described in Mni92, a summary of the method and references to all predecessors can be found in FS84.
The Lattice command invokes the following procedure. In a first step,
the solvable re-si-du-um P, say, of G is computed and looked up in
a built-in catalogue of perfect groups which is given in the file
LIBNAME/"lattperf.g". A list of subgroups is read off from that
catalogue which contains just one representative of each conjugacy class
of perfect subgroups of P and hence at least one representative of each
conjugacy class of perfect subgroups of G. Then, starting from the
identity subgroup and the conjugacy classes of perfect subgroups, the so
called cyclic extension method is used to compute the non-perfect
subgroups of G by forming for each class representative all its not yet
involved cyclic extensions of prime number index and adding their
conjugacy classes to the list.
It is clear that this procedure cannot work if the catalogue of perfect
groups does not contain a group isomorphic to P. At present, it
contains only all perfect groups of order less than 5000 and, in
addition, the groups PSL(3,3), M_{11}, and A_8. If the Lattice
command is called for a group G with a solvable residuum P not in the
catalogue, it will provide an error message. As an example we handle the
group SL(2,19) of order 6840.
gap> s := [ [4,0], [0,5] ] * Z( 19 )^0;;
gap> t := [ [4,4], [-9,-4] ] * Z(19)^0;;
gap> G := Group( s, t );;
gap> Size( G );
6840
gap> Lattice( G );
Error, sorry, can' t identify the group's solvable residuum
However, if you know the perfect subgroups of G, you can use the
Lattice command to compute the whole subgroup lattice of G even if
the solvable residuum of G is not in the catalogue. All you have to do
in such a case is to create a list of subgroups of G which contains at
least one representative of each conjugacy class of proper perfect
subgroups of G, attach this list to the group record as a new component
G.perfectSubgroups, and then call the Lattice command. The
existence of that record component will prevent GAP from looking up
the solvable residuum of G in the catalogue. Instead, it will insert
the given subgroups into the lattice, leaving it to you to guarantee that
in fact all conjugacy classes of proper perfect subgroups are involved.
If you miss classes, the resulting lattice will be incomplete, but you
will not get any warning. As long as you are aware of this fact, you may
use this possibility to compute a sublattice of the subgroup lattice of
G without getting the above mentioned error message even if the
solvable residuum of G is not in the catalogue. In particular, you will
get at least the classes of all proper solvable subgroups of G if you
define G.perfectSubgroups to be an empty list.
As an example for the computation of the complete lattice of subgroups of a group which is not covered by the catalogue, we handle the Mathieu group M_{12}.
gap> # Define the Mathieu group M12.
gap> a := (2,3,5,7,11,9,8,12,10,6,4);;
gap> b := (3,6)(5,8)(9,11)(10,12);;
gap> c := (1,2)(3,4)(5,9)(6,8)(7,12)(10,11);;
gap> M12 := Group( a, b, c );;
gap> Print( "#I M12 has order ", Size( M12 ), "\n" );
#I M12 has order 95040
gap> # Define a list of proper perfect subgroups of M_12 and attach
gap> # it to the group record M12 as component M12.perfectSubgroups.
gap> L2_11a := Subgroup( M12, [ a, b ] );;
gap> M11a := Subgroup( M12, [ a, b, c*a^-1*b*a*c ] );;
gap> M11b := Subgroup( M12, [ a, b, c*a*b*a^-1*c ] );;
gap> x := a*b*a^2;;
gap> y := a*c*a^-1*b*a*c*a^6;;
gap> A6a := Subgroup( M12, [ x, y ] );;
gap> A5c := Subgroup( M12, [ x*y, x^3*y^2*x^2*y ] );;
gap> x := a^2*b*a;;
gap> y := a^6*c*a*b*a^-1*c*a;;
gap> A6b := Subgroup( M12, [ x, y ] );;
gap> A5d := Subgroup( M12, [ x*y, x^3*y^2*x^2*y ] );;
gap> x := a;;
gap> y := b*c*b;;
gap> z := c;;
gap> L2_11b := Subgroup( M12, [ x, y, z ] );;
gap> A5b := Subgroup( M12, [ y, x*z ] );;
gap> x := c;;
gap> y := b*a^-1*c*a*b;;
gap> z := a^2*b*a^-1*c*a*b*a^-2;;
gap> A5a := Subgroup( M12, [ (x*z)^2, (y*z)^2 ] );;
gap> M12.perfectSubgroups := [
> L2_11a, L2_11b, M11a, M11b, A6a, A6b, A5a, A5b, A5c, A5d ];;
gap> # Now compute the subgroup lattice of M12.
gap> lat := Lattice( M12 );
LatticeSubgroups( Group( ( 2, 3, 5, 7,11, 9, 8,12,10, 6, 4), ( 3, 6)
( 5, 8)( 9,11)(10,12), ( 1, 2)( 3, 4)( 5, 9)( 6, 8)( 7,12)(10,11) ) )
The Lattice command returns a record which represents a very
complicated structure.
gap> # Subgroup lattice of M12 (continued)
gap> RecFields( lat );
[ "isLattice", "classes", "group", "printLevel", "operations" ]
Probably the most important component of the lattice record is the list
lat.classes. Its elements are domains. They are described in section
ConjugacyClassesSubgroups. We can use this list, for instance, to print
the number of conjugacy classes of subgroups and the number of subgroups
of M_{12}.
gap> # Subgroup lattice of M12 (continued)
gap> n1 := Length( lat.classes );;
gap> n2 := Sum( [ 1 .. n1 ], i -> Size( lat.classes[i] ) );;
gap> Print( "#I M12 has ", n1, " classes of altogether ", n2,
> " subgroups\n" );
#I M12 has 147 classes of altogether 214871 subgroups
It would not make sense to get all components of a subgroup lattice
record printed in full detail whenever we ask GAP to print the
lattice. Therefore, as you can see in the above example, the default
printout is just an expression of the form "Lattice(,group,)".
However, you can ask GAP to display some additional information in any
subsequent printout of the lattice by increasing its individual print
level. This print level is stored (in the form of a list of several
print flags) in the lattice record and can be changed by an appropriate
call of the SetPrintLevel indexSetPrintLevel command described
below.
The following example demonstrates the effect of the subgroup lattice print level.
gap> # Subgroup lattice of S4
gap> s4 := Group( (1,2,3,4), (1,2) );;
gap> lat := Lattice( s4 );
LatticeSubgroups( Group( (1,2,3,4), (1,2) ) )
The default subgroup lattice print level is 0. In this case, the print command provides just the expression mentioned above.
gap> # Subgroup lattice of S4 (continued)
gap> SetPrintLevel( lat, 1 );
gap> lat;
#I class 1, size 1, length 1
#I class 2, size 2, length 3
#I class 3, size 2, length 6
#I class 4, size 3, length 4
#I class 5, size 4, length 1
#I class 6, size 4, length 3
#I class 7, size 4, length 3
#I class 8, size 6, length 4
#I class 9, size 8, length 3
#I class 10, size 12, length 1
#I class 11, size 24, length 1
LatticeSubgroups( Group( (1,2,3,4), (1,2) ) )
If the print level is set to a value greater than 0, you get, in addition, for each class a kind of heading line. This line contains the position number and the length of the respective class as well as the order of the subgroups in the class.
gap> # Subgroup lattice of S4 (continued)
gap> SetPrintLevel( lat, 2 );
gap> lat;
#I class 1, size 1, length 1
#I representative [ ]
#I maximals
#I class 2, size 2, length 3
#I representative [ (1,2)(3,4) ]
#I maximals [ 1, 1 ]
#I class 3, size 2, length 6
#I representative [ (3,4) ]
#I maximals [ 1, 1 ]
#I class 4, size 3, length 4
#I representative [ (2,3,4) ]
#I maximals [ 1, 1 ]
#I class 5, size 4, length 1
#I representative [ (1,2)(3,4), (1,3)(2,4) ]
#I maximals [ 2, 1 ] [ 2, 2 ] [ 2, 3 ]
#I class 6, size 4, length 3
#I representative [ (3,4), (1,2) ]
#I maximals [ 3, 1 ] [ 3, 4 ] [ 2, 1 ]
#I class 7, size 4, length 3
#I representative [ (1,2)(3,4), (1,4,2,3) ]
#I maximals [ 2, 1 ]
#I class 8, size 6, length 4
#I representative [ (2,3,4), (3,4) ]
#I maximals [ 4, 1 ] [ 3, 1 ] [ 3, 2 ] [ 3, 3 ]
#I class 9, size 8, length 3
#I representative [ (3,4), (1,2), (1,3)(2,4) ]
#I maximals [ 7, 1 ] [ 6, 1 ] [ 5, 1 ]
#I class 10, size 12, length 1
#I representative [ (1,2)(3,4), (1,3)(2,4), (2,3,4) ]
#I maximals [ 5, 1 ] [ 4, 1 ] [ 4, 2 ] [ 4, 3 ] [ 4, 4 ]
#I class 11, size 24, length 1
#I representative [ (1,2,3,4), (1,2) ]
#I maximals [ 10, 1 ] [ 9, 1 ] [ 9, 2 ] [ 9, 3 ] [ 8, 1 ]
[ 8, 2 ] [ 8, 3 ] [ 8, 4 ]
LatticeSubgroups( Group( (1,2,3,4), (1,2) ) )
gap> PrintClassSubgroupLattice( lat, 8 );
#I class 8, size 6, length 4
#I representative [ (2,3,4), (3,4) ]
#I maximals [ 4, 1 ] [ 3, 1 ] [ 3, 2 ] [ 3, 3 ]
If the subgroup lattice print level is at least 2, GAP prints, in
addition, for each class representative subgroup a set of generators and
a list of its maximal subgroups, where each maximal subgroup is
represented by a pair of integers consisting of its class number and its
position number in that class. As this information blows up the output,
it may be convenient to restrict it to a particular class. We can do this
by calling the PrintClassSubgroupLattice
gap> # Subgroup lattice of S4 (continued)
gap> SetPrintLevel( lat, 3 );
gap> PrintClassSubgroupLattice( lat, 8 );
#I class 8, size 6, length 4
#I representative [ (2,3,4), (3,4) ]
#I maximals [ 4, 1 ] [ 3, 1 ] [ 3, 2 ] [ 3, 3 ]
#I conjugate 2 by (1,4,3,2) is [ (1,2,3), (2,3) ]
#I conjugate 3 by (1,2) is [ (1,3,4), (3,4) ]
#I conjugate 4 by (1,3)(2,4) is [ (1,2,4), (1,2) ]
If the subgroup lattice print level has been set to at least 3, GAP displays, in addition, for each non-representative subgroup of a class its number in the class, an element which transforms the class representative subgroup into that subgroup, and a set of generators.
gap> # Subgroup lattice of S4 (continued)
gap> SetPrintLevel( lat, 4 );
gap> PrintClassSubgroupLattice( lat, 8 );
#I class 8, size 6, length 4
#I representative [ (2,3,4), (3,4) ]
#I maximals [ 4, 1 ] [ 3, 1 ] [ 3, 2 ] [ 3, 3 ]
#I conjugate 2 by (1,4,3,2) is [ (1,2,3), (2,3) ]
#I maximals [ 4, 2 ] [ 3, 2 ] [ 3, 4 ] [ 3, 5 ]
#I conjugate 3 by (1,2) is [ (1,3,4), (3,4) ]
#I maximals [ 4, 3 ] [ 3, 1 ] [ 3, 5 ] [ 3, 6 ]
#I conjugate 4 by (1,3)(2,4) is [ (1,2,4), (1,2) ]
#I maximals [ 4, 4 ] [ 3, 4 ] [ 3, 6 ] [ 3, 3 ]
A subgroup lattice print level value of at least 4 causes GAP to list the maximal subgroups not only for the class representatives, but also for the other subgroups.
gap> # Subgroup lattice of S4 (continued)
gap> SetPrintLevel( lat, 5 );
gap> PrintClassSubgroupLattice( lat, 8 );
#I class 8, size 6, length 4
#I representative [ (2,3,4), (3,4) ]
#I maximals [ 4, 1 ] [ 3, 1 ] [ 3, 2 ] [ 3, 3 ]
#I minimals [ 11, 1 ]
#I conjugate 2 by (1,4,3,2) is [ (1,2,3), (2,3) ]
#I maximals [ 4, 2 ] [ 3, 2 ] [ 3, 4 ] [ 3, 5 ]
#I minimals [ 11, 1 ]
#I conjugate 3 by (1,2) is [ (1,3,4), (3,4) ]
#I maximals [ 4, 3 ] [ 3, 1 ] [ 3, 5 ] [ 3, 6 ]
#I minimals [ 11, 1 ]
#I conjugate 4 by (1,3)(2,4) is [ (1,2,4), (1,2) ]
#I maximals [ 4, 4 ] [ 3, 4 ] [ 3, 6 ] [ 3, 3 ]
#I minimals [ 11, 1 ]
The maximal valid value of the subgroup lattice print level is 5. If it
is set, GAP displays not only the maximal subgroups, but also the
minimal supergroups of each subgroup. This is the most extensive output
of a subgroup lattice record which you can get with the Print command,
but of course you can use the RecFields command (see RecFields) to
list all record components and then print them out individually in full
detail.
If the computation of some subgroup lattice is very time consuming (as in the above example of the Mathieu group M_{12}), you might wish to see some intermediate printout which informs you about the progress of the computation. In fact, you can get such messages by activating a print mechanism which has been inserted into the subgroup lattice routines for diagnostic purposes. All you have to do is to replace the call
lat := Lattice( M12 );
by the three calls
InfoLattice1 := Print;
lat := Lattice( M12 );
InfoLattice1 := Ignore;
Note, however, that the final numbering of the conjugacy classes of subgroups will differ from the order in which they occur in the intermediate listing because they will be reordered by increasing subgroup orders at the end of the construction.
PrintClassSubgroupLattice( lattice, n )
PrintClassSubgroupLattice prints information on the nth conjugacy
class of subgroups in the subgroup lattice lattice. The amount of this
information depends on the current value of the subgroup lattice print
level of lattice. Note that the default of that print level is zero
which means that you will not get any output from the
PrintClassSubgroupLattice command without increasing it (see
SetPrintLevel below). Examples are given in the above description of
the Lattice command.
SetPrintLevel( lattice, level )
SetPrintLevel changes the subgroup lattice print level of the subgroup
lattice lattice to the specified value level by an appropriate
alteration of the list of print flags which is stored in
lattice.printLevel. The argument level is expected to be an
integer between 0 and 5.
Examples of the effect of the subgroup lattice print level are given in
the above description of the Lattice command.
GAP 3.4.4