gap-libs 4r6p5-3 / usr / share / gap / lib / grplatt.gd

#############################################################################
##
#W  grplatt.gd                GAP library                   Martin Schönert,
#W                                                          Alexander Hulpke
##
##
#Y  Copyright (C)  1996,  Lehrstuhl D für Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1998 School Math and Comp. Sci., University of St Andrews, Scotland
#Y  Copyright (C) 2002 The GAP Group
##
##  This  file  contains declarations for subgroup latices
##


#############################################################################
##
#V  InfoLattice                                    Information
##
##  <#GAPDoc Label="InfoLattice">
##  <ManSection>
##  <InfoClass Name="InfoLattice"/>
##
##  <Description>
##  is the information class used by the cyclic extension methods for
##  subgroup lattice calculations.
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareInfoClass("InfoLattice");


#############################################################################
##
#R  IsConjugacyClassSubgroupsRep( <obj> )
#R  IsConjugacyClassSubgroupsByStabilizerRep( <obj> )
##
##  <#GAPDoc Label="IsConjugacyClassSubgroupsRep">
##  <ManSection>
##  <Filt Name="IsConjugacyClassSubgroupsRep" Arg='obj'
##   Type='Representation'/>
##  <Filt Name="IsConjugacyClassSubgroupsByStabilizerRep" Arg='obj'
##   Type='Representation'/>
##
##  <Description>
##  Is the representation &GAP; uses for conjugacy classes of subgroups.
##  It can be used to check whether an object is a class of subgroups.
##  The second representation
##  <Ref Func="IsConjugacyClassSubgroupsByStabilizerRep"/> in
##  addition is an external orbit by stabilizer and will compute its
##  elements via a transversal of the stabilizer.
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareRepresentation("IsConjugacyClassSubgroupsRep",
  IsExternalOrbit,[]);
DeclareRepresentation("IsConjugacyClassSubgroupsByStabilizerRep",
  IsConjugacyClassSubgroupsRep and IsExternalOrbitByStabilizerRep,[]);


#############################################################################
##
#O  ConjugacyClassSubgroups( <G>, <U> )
##
##  <#GAPDoc Label="ConjugacyClassSubgroups">
##  <ManSection>
##  <Oper Name="ConjugacyClassSubgroups" Arg='G, U'/>
##
##  <Description>
##  generates the conjugacy class of subgroups of <A>G</A> with
##  representative <A>U</A>.
##  This class is an external set,
##  so functions such as <Ref Attr="Representative"/>,
##  (which returns <A>U</A>),
##  <Ref Func="ActingDomain"/> (which returns <A>G</A>),
##  <Ref Func="StabilizerOfExternalSet"/> (which returns the normalizer of
##  <A>U</A>), and <Ref Func="AsList"/> work for it.
##  <P/>
##  (The use of the <C>[]</C>
##  list access to select elements of the class is considered obsolescent
##  and will be removed in future versions.
##  Use <Ref Func="ClassElementLattice"/> instead.)
##  <P/>
##  <Example><![CDATA[
##  gap> g:=Group((1,2,3,4),(1,2));;IsNaturalSymmetricGroup(g);;
##  gap> cl:=ConjugacyClassSubgroups(g,Subgroup(g,[(1,2)]));
##  Group( [ (1,2) ] )^G
##  gap> Size(cl);
##  6
##  gap> ClassElementLattice(cl,4);
##  Group([ (2,3) ])
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareOperation("ConjugacyClassSubgroups", [IsGroup,IsGroup]);

#############################################################################
##
#O  ClassElementLattice(<C>,<n>)
##
##  <#GAPDoc Label="ClassElementLattice">
##  <ManSection>
##  <Oper Name="ClassElementLattice" Arg='C, n'/>
##
##  <Description>
##  For a class <A>C</A> of subgroups, obtained by a lattice computation,
##  this operation returns the <A>n</A>-th conjugate subgroup in the class.
##  <P/>
##  <E>Because of other methods installed, calling <Ref Func="AsList"/> with
##  <A>C</A> can give a different arrangement of the class elements!</E>
##  <P/>
##  The &GAP; package <Package>XGAP</Package> permits a graphical display of
##  the lattice of subgroups in a nice way.
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareOperation("ClassElementLattice", [IsExternalOrbit,IsPosInt]);

#############################################################################
##
#R  IsLatticeSubgroupsRep(<obj>)
##
##  <ManSection>
##  <Filt Name="IsLatticeSubgroupsRep" Arg='obj' Type='Representation'/>
##
##  <Description>
##  This representation indicates lattices of subgroups.
##  </Description>
##  </ManSection>
##
DeclareRepresentation("IsLatticeSubgroupsRep",
  IsComponentObjectRep and IsAttributeStoringRep,
  ["group","conjugacyClassesSubgroups"]);

#############################################################################
##
#A  Zuppos(<G>) .  set of generators for cyclic subgroups of prime power size
##
##  <#GAPDoc Label="Zuppos">
##  <ManSection>
##  <Attr Name="Zuppos" Arg='G'/>
##
##  <Description>
##  The <E>Zuppos</E> of a group are the cyclic subgroups of prime power order.
##  (The name <Q>Zuppo</Q> derives from the German abbreviation for <Q>zyklische
##  Untergruppen von Primzahlpotenzordnung</Q>.) This attribute
##  gives generators of all such subgroups of a group <A>G</A>. That is all elements
##  of <A>G</A> of prime power order up to the equivalence that they generate the
##  same cyclic subgroup.
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareAttribute("Zuppos",IsGroup);

#############################################################################
##
#F  LatticeByCyclicExtension( <G>[, <func>[, <noperf>]] )
##
##  <#GAPDoc Label="LatticeByCyclicExtension">
##  <ManSection>
##  <Func Name="LatticeByCyclicExtension" Arg='G[, func[, noperf]]'/>
##
##  <Description>
##  computes the lattice of <A>G</A> using the cyclic extension algorithm. If the
##  function <A>func</A> is given, the algorithm will discard all subgroups not
##  fulfilling <A>func</A> (and will also not extend them), returning a partial
##  lattice. This can be useful to compute only subgroups with certain
##  properties. Note however that this will <E>not</E> necessarily yield all
##  subgroups that fulfill <A>func</A>, but the subgroups whose subgroups are used
##  for the construction must also fulfill <A>func</A> as well.
##  (In fact the filter <A>func</A> will simply discard subgroups in the cyclic
##  extension algorithm. Therefore the trivial subgroup will always be
##  included.) Also note, that for such a partial lattice
##  maximality/minimality inclusion relations cannot be computed.
##  (If <A>func</A> is a list of length 2, its first entry is such a
##  discarding function, the second a function for discarding zuppos.)
##  <P/>
##  The cyclic extension algorithm requires the perfect subgroups of <A>G</A>.
##  However &GAP; cannot analyze the function <A>func</A> for its implication
##  but can only apply it. If it is known that <A>func</A> implies solvability,
##  the computation of the perfect subgroups can be avoided by giving a
##  third parameter <A>noperf</A> set to <K>true</K>. 
##  <P/>
##  <Example><![CDATA[
##  gap> g:=WreathProduct(Group((1,2,3),(1,2)),Group((1,2,3,4)));;
##  gap> l:=LatticeByCyclicExtension(g,function(G)
##  > return Size(G) in [1,2,3,6];end);
##  <subgroup lattice of <permutation group of size 5184 with 
##  9 generators>, 47 classes, 
##  2628 subgroups, restricted under further condition l!.func>
##  ]]></Example>
##  <P/>
##  The total number of classes in this example is much bigger, as the
##  following example shows:
##  <Example><![CDATA[
##  gap> LatticeSubgroups(g);
##  <subgroup lattice of <permutation group of size 5184 with 
##  9 generators>, 566 classes, 27134 subgroups>
##  ]]></Example> ##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction("LatticeByCyclicExtension");

#############################################################################
##
#F  LatticeViaRadical(<G>)
##
##  <ManSection>
##  <Func Name="LatticeViaRadical" Arg='G'/>
##
##  <Description>
##  computes the lattice of <A>G</A> using the homomorphism principle to lift the
##  result from factor groups.
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("LatticeViaRadical");

#############################################################################
##
#A  MaximalSubgroupsLattice(<lat>)
##
##  <#GAPDoc Label="MaximalSubgroupsLattice">
##  <ManSection>
##  <Attr Name="MaximalSubgroupsLattice" Arg='lat'/>
##
##  <Description>
##  For a lattice <A>lat</A> of subgroups this attribute contains the maximal
##  subgroup relations among the subgroups of the lattice.
##  It is a list corresponding to the <Ref Func="ConjugacyClassesSubgroups"/>
##  value of the lattice, each entry giving a list of the maximal subgroups
##  of the representative of this class.
##  Every maximal subgroup is indicated by a list of the form <M>[ c, n ]</M>
##  which means that the <M>n</M>-th subgroup in class number <M>c</M> is a
##  maximal subgroup of the representative. 
##  <P/>
##  The number <M>n</M> corresponds to access via
##  <Ref Func="ClassElementLattice"/>
##  and <E>not</E> necessarily the <Ref Func="AsList"/> arrangement!
##  See also <Ref Func="MinimalSupergroupsLattice"/>.
##  <Example><![CDATA[
##  gap> MaximalSubgroupsLattice(l);
##  [ [  ], [ [ 1, 1 ] ], [ [ 1, 1 ] ], [ [ 1, 1 ] ], 
##    [ [ 2, 1 ], [ 2, 2 ], [ 2, 3 ] ], [ [ 3, 1 ], [ 3, 6 ], [ 2, 3 ] ], 
##    [ [ 2, 3 ] ], [ [ 4, 1 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ], 
##    [ [ 7, 1 ], [ 6, 1 ], [ 5, 1 ] ], 
##    [ [ 5, 1 ], [ 4, 1 ], [ 4, 2 ], [ 4, 3 ], [ 4, 4 ] ], 
##    [ [ 10, 1 ], [ 9, 1 ], [ 9, 2 ], [ 9, 3 ], [ 8, 1 ], [ 8, 2 ], 
##        [ 8, 3 ], [ 8, 4 ] ] ]
##  gap> last[6];
##  [ [ 3, 1 ], [ 3, 6 ], [ 2, 3 ] ]
##  gap> u1:=Representative(ConjugacyClassesSubgroups(l)[6]);
##  Group([ (3,4), (1,2)(3,4) ])
##  gap> u2:=ClassElementLattice(ConjugacyClassesSubgroups(l)[3],1);;
##  gap> u3:=ClassElementLattice(ConjugacyClassesSubgroups(l)[3],6);;
##  gap> u4:=ClassElementLattice(ConjugacyClassesSubgroups(l)[2],3);;
##  gap> IsSubgroup(u1,u2);IsSubgroup(u1,u3);IsSubgroup(u1,u4);
##  true
##  true
##  true
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareAttribute("MaximalSubgroupsLattice",IsLatticeSubgroupsRep);

#############################################################################
##
#A  MinimalSupergroupsLattice(<lat>)
##
##  <#GAPDoc Label="MinimalSupergroupsLattice">
##  <ManSection>
##  <Attr Name="MinimalSupergroupsLattice" Arg='lat'/>
##
##  <Description>
##  For a lattice <A>lat</A> of subgroups this attribute contains the minimal
##  supergroup relations among the subgroups of the lattice.
##  It is a list corresponding to the <Ref Func="ConjugacyClassesSubgroups"/>
##  value of the lattice, each entry giving a list of the minimal supergroups
##  of the representative of this class.
##  Every minimal supergroup is indicated by a list of the form
##  <M>[ c, n ]</M>, which means that the <M>n</M>-th subgroup in class
##  number <M>c</M> is a minimal supergroup of the representative.
##  <P/>
##  The number <M>n</M> corresponds to access via
##  <Ref Func="ClassElementLattice"/>
##  and <E>not</E> necessarily the <Ref Func="AsList"/> arrangement!
##  See also <Ref Func="MaximalSubgroupsLattice"/>.
##  <Example><![CDATA[
##  gap> MinimalSupergroupsLattice(l);
##  [ [ [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ], 
##        [ 3, 4 ], [ 3, 5 ], [ 3, 6 ], [ 4, 1 ], [ 4, 2 ], [ 4, 3 ], 
##        [ 4, 4 ] ], [ [ 5, 1 ], [ 6, 2 ], [ 7, 2 ] ], 
##    [ [ 6, 1 ], [ 8, 1 ], [ 8, 3 ] ], [ [ 8, 1 ], [ 10, 1 ] ], 
##    [ [ 9, 1 ], [ 9, 2 ], [ 9, 3 ], [ 10, 1 ] ], [ [ 9, 1 ] ], 
##    [ [ 9, 1 ] ], [ [ 11, 1 ] ], [ [ 11, 1 ] ], [ [ 11, 1 ] ], [  ] ]
##  gap> last[3];
##  [ [ 6, 1 ], [ 8, 1 ], [ 8, 3 ] ]
##  gap> u5:=ClassElementLattice(ConjugacyClassesSubgroups(l)[8],1);
##  Group([ (3,4), (2,4,3) ])
##  gap> u6:=ClassElementLattice(ConjugacyClassesSubgroups(l)[8],3);
##  Group([ (1,3), (1,3,4) ])
##  gap> IsSubgroup(u5,u2);
##  true
##  gap> IsSubgroup(u6,u2);
##  true
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareAttribute("MinimalSupergroupsLattice",IsLatticeSubgroupsRep);

#############################################################################
##
#F  DotFileLatticeSubgroups( <L>, <file> )
##
##  <#GAPDoc Label="DotFileLatticeSubgroups">
##  <ManSection>
##  <Func Name="DotFileLatticeSubgroups" Arg='L, file'/>
##
##  <Description>
##  <Index>dot-file</Index>
##  <Index>graphviz</Index>
##  <Index>OmniGraffle</Index>
##  This function produces a graphical representation of the subgroup
##  lattice <A>L</A> in file <A>file</A>. The output is in <C>.dot</C> (also known as
##  <C>GraphViz</C> format). For details on the format, and information about how to
##  display or edit this format see <URL>http://www.graphviz.org</URL>. (On the
##  Macintosh, the program <C>OmniGraffle</C> is also able to read this format.)
##  <P/>
##  Subgroups are labelled in the form <C><A>i</A>-<A>j</A></C> where <A>i</A> is the number of
##  the class of subgroups and <A>j</A> the number within this class. Normal
##  subgroups are represented by a box. 
##  <P/>
##  <Log><![CDATA[
##  gap> DotFileLatticeSubgroups(l,"s4lat.dot");
##  ]]></Log>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction("DotFileLatticeSubgroups");

#############################################################################
##
#F  ExtendSubgroupsOfNormal( <G>, <N>,<Nsubs> )
##
##  <#GAPDoc Label="ExtendSubgroupsOfNormal">
##  <ManSection>
##  <Func Name="ExtendSubgroupsOfNormal" Arg='G,N,Nsubs'/>
##
##  <Description>
##  If $N$ is normal in $G$ and $Nsubs$ is a list of subgroups of $N$ up to
##  conjugacy, this function extends this list to taht of all subgroups of $G$.
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction("ExtendSubgroupsOfNormal");

#############################################################################
##
#F  SubdirectSubgroups( <D> )
##
##  <#GAPDoc Label="SubdirectSubgroups">
##  <ManSection>
##  <Func Name="SubdirectSubgroups" Arg='D'/>
##
##  <Description>
##  If $D$ is created as a direct product, this function determines all
##  subgroups of $D$ up to conjugacy, using subdirect products.
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction("SubdirectSubgroups");

#############################################################################
##
#F  SubgroupsTrivialFitting( <G> )
##
##  <#GAPDoc Label="SubgroupsTrivialFitting">
##  <ManSection>
##  <Func Name="SubgroupsTrivialFitting" Arg='G'/>
##
##  <Description>
##  Determines representatives of the conjugacy classes of subgroups of a
##  trivial-fitting group $G$.
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction("SubgroupsTrivialFitting");

#############################################################################
##
#E