gap-libs 4r7p9-1 / usr / share / gap / lib / factgrp.gd

#############################################################################
##
#W  factgrp.gd                      GAP library              Alexander Hulpke
##
##
#Y  Copyright (C)  1997,  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 the declarations of operations for factor group maps
##

##
##  To implement new factor group methods, one does not need to deal with
##  most of the following operations (which are only used to cache known
##  homomorphisms and extend them to subdirect factors). Instead only methods
##  for the following three operations might need to be supplied:
##  If a suitable homomorphism cannot be found from the cached homomorphisms
##  pool, `NaturalHomomorphismByNormalSubgroupOp(<G>,<N>)' is called to
##  construct one.
##  The default method for `NaturalHomomorphismByNormalSubgroupOp' then uses
##  two other operations: `DoCheapActionImages' computes actions that come
##  naturally from a groups representation (for example permutation action
##  on orbits and blocks) and can be computed quickly. This is intended
##  as a first test to avoid hard work for homomorphisms that are easy to
##  get.
##  If this fails, `FindActionKernel' is called which will try to find some
##  action which will give a suitable homomorphism. (This can be very time
##  consuming.)
##  The existing methods seem to work reasonably well for permutation groups
##  and pc groups, for other kinds of groups it might be necessary to
##  implement completely new methods.
##  

#############################################################################
##
#O  DoCheapActionImages(<G>)
##
##  <ManSection>
##  <Oper Name="DoCheapActionImages" Arg='G'/>
##
##  <Description>
##  computes natural actions for <A>G</A> and stores the resulting
##  <C>NaturalHomomorphismByNormalSubgroup</C>. The type of the natural actions
##  varies with the representation of <A>G</A>, for permutation groups it are for
##  example constituent and block homomorphisms.
##  A method for <C>DoCheapActionImages</C> must register all found actions with
##  <C>AddNaturalHomomorphismsPool</C> so they become available.
##  </Description>
##  </ManSection>
##
DeclareOperation("DoCheapActionImages",[IsGroup]);
DeclareSynonym("DoCheapOperationImages",DoCheapActionImages);


#############################################################################
##
#O  FindActionKernel( <G>, <N> )  . . . . . . . . . . . . . . . . local
##
##  <ManSection>
##  <Oper Name="FindActionKernel" Arg='G, N'/>
##
##  <Description>
##  This operation tries to find a suitable action for the group <A>G</A> such
##  that its kernel is <A>N</A>. This is used to construct faithful permutation
##  representations for the factor group.
##  </Description>
##  </ManSection>
##
DeclareOperation( "FindActionKernel",[IsGroup,IsGroup]);
DeclareSynonym( "FindOperationKernel",FindActionKernel);

#############################################################################
##
#V  InfoFactor
##
##  <ManSection>
##  <InfoClass Name="InfoFactor"/>
##
##  <Description>
##  </Description>
##  </ManSection>
##
DeclareInfoClass("InfoFactor");

#############################################################################
##
#A  NaturalHomomorphismsPool(<G>)
##
##  <ManSection>
##  <Attr Name="NaturalHomomorphismsPool" Arg='G'/>
##
##  <Description>
##  The <C>NaturalHomomorphismsPool</C> is a record which contains the following
##  components:
##    <C>group</C> is the corresponding group.
##    <C>ker</C> is a list of normal subgroups, which defines the arrangements.
##          It is sorted.
##    <C>ops</C> is a list which gives the best know actions for each normal 
##          subgroup. Its entries are either Homomorphisms from G or
##  generator lists (G.generators images) or lists of integers. In the
##  latter case the factor is subdirect product of the factors with
##  the given numbers.
##    <C>cost</C> gives the difficulty for each actions (degree of permgroup). It
##           is used to check whether a new actions is better.
##    <C>lock</C> is a bitlist, which indicates whether certain actions are
##  locked. If this happens, a better new actions is not entered.
##  This allows a computation to access the pool several times and to
##  be guaranteed to be returned the same object. Usually a routine
##  initially locks and finally unlocks.
##  <!-- #AH probably one even would like to have a lock counter ? -->
##    <C>GopDone</C> indicates whether all <C>obvious</C> actions have been tried
##              already
##    <C>intersects</C> is a list of all intersections that have already been
##              formed.
##    <C>blocksdone</C> indicates if the actions already has been improved
##         using blocks
##    <C>in_code</C> can be set by the code to avoid addition of new actions
##              (and thus resorting)
##  </Description>
##  </ManSection>
##
DeclareAttribute("NaturalHomomorphismsPool",IsGroup,
                                         "mutable");

#############################################################################
##
#O  FactorCosetAction( <G>, <U>[, <N>] )  action on the right cosets Ug
##
##  <#GAPDoc Label="FactorCosetAction">
##  <ManSection>
##  <Oper Name="FactorCosetAction" Arg='G, U[, N]'/>
##
##  <Description>
##  This command computes the action of the group <A>G</A> on the
##  right cosets of the subgroup <A>U</A>.
##  If a normal subgroup <A>N</A> of <A>G</A> is given,
##  it is stored as kernel of this action.
##  <Example><![CDATA[
##  gap> g:=Group((1,2,3,4,5),(1,2));;u:=SylowSubgroup(g,2);;Index(g,u);
##  15
##  gap> FactorCosetAction(g,u);
##  <action epimorphism>
##  gap> Range(last);
##  Group([ (1,9,13,10,4)(2,8,14,11,5)(3,7,15,12,6), 
##    (1,7)(2,8)(3,9)(5,6)(10,11)(14,15) ])
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareOperation( "FactorCosetAction", [IsGroup,IsGroup] );

#############################################################################
##
#F  ImproveActionDegreeByBlocks( <G>, <N> , <hom> [,forceblocks] )
#F  ImproveActionDegreeByBlocks( <G>, <N> , <U> [,forceblocks] )
##
##  <ManSection>
##  <Func Name="ImproveActionDegreeByBlocks" Arg='G, N , hom [,forceblocks]'/>
##  <Func Name="ImproveActionDegreeByBlocks" Arg='G, N , U [,forceblocks]'/>
##
##  <Description>
##  In the first usage, <A>N</A> is a normal subgroup of <A>G</A> and <A>hom</A> a
##  homomorphism from <A>G</A> to a permutation group with kernel <A>N</A>. In the second
##  usage, <A>hom</A> is taken to be the action of <A>G</A> on the cosets of <A>U</A> by right
##  multiplication.
##  The function tries to find another homomorphism with the same kernel but
##  image group of smaller degree by looking for block systems of the image
##  group. An improved result is stored in the <C>NaturalHomomorphismsPool</C>, the
##  function returns the degree of this image (or the degree of the original
##  image).
##  If the image degree is larger than 500, only one block system is tested by
##  standard. A test of all block systems is enforced by the optional boolean
##  parameter <A>forceblocks</A>
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction( "ImproveActionDegreeByBlocks" );
DeclareSynonym( "ImproveOperationDegreeByBlocks",
                        ImproveActionDegreeByBlocks );

#############################################################################
##
#F  SmallerDegreePermutationRepresentation( <G> )
##
##  <#GAPDoc Label="SmallerDegreePermutationRepresentation">
##  <ManSection>
##  <Func Name="SmallerDegreePermutationRepresentation" Arg='G'/>
##
##  <Description>
##  Let <A>G</A> be a permutation group that acts transitively
##  on its moved points.
##  <Ref Func="SmallerDegreePermutationRepresentation"/> tries to find a
##  faithful permutation representation of smaller degree.
##  The result is a group homomorphism onto a permutation group,
##  in the worst case this is the identity mapping on <A>G</A>.
##  <P/>
##  If the <C>cheap</C> option is given, the function only tries to reduce
##  to orbits or actions on blocks, otherwise also actions on cosets of
##  random subgroups are tried.
##  <P/>
##  Note that the result is not guaranteed to be a faithful permutation
##  representation of smallest degree,
##  or of smallest degree among the transitive permutation representations
##  of <A>G</A>.
##  Using &GAP; interactively, one might be able to choose subgroups
##  of small index for which the cores intersect trivially;
##  in this case, the actions on the cosets of these subgroups give rise to
##  an intransitive permutation representation
##  the degree of which may be smaller than the original degree.
##  <P/>
##  The methods used might involve the use of random elements and the
##  permutation representation (or even the degree of the representation) is
##  not guaranteed to be the same for different calls of
##  <Ref Func="SmallerDegreePermutationRepresentation"/>.
##  <P/>
##  If the option cheap is given less work is spent on trying to get a small
##  degree representation, if the value of this option is set to the string 
##  "skip" the identity mapping is returned. (This is useful if a function
##  called internally might try a degree reduction.)
##  <P/>
##  <Example><![CDATA[
##  gap> image:= Image( iso );;  NrMovedPoints( image );
##  24
##  gap> small:= SmallerDegreePermutationRepresentation( image );;
##  gap> Image( small );
##  Group([ (2,3), (2,3,4), (1,2)(3,4), (1,3)(2,4) ])
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "SmallerDegreePermutationRepresentation" );


#############################################################################
##
#F  AddNaturalHomomorphismsPool(G,N,op[,cost[,blocksdone]])
##
##  <ManSection>
##  <Func Name="AddNaturalHomomorphismsPool" Arg='G,N,op[,cost[,blocksdone]]'/>
##
##  <Description>
##  This function stores a computed action of <A>G</A> with kernel <A>N</A> in the
##  <C>NaturalHomomorphismsPool</C> of <A>G</A>, unless a <Q>better</Q> action is already
##  known. <A>op</A> usually is a homomorphism of <A>G</A> with kernel <A>N</A>. It may also
##  be a subgroup of <A>G</A>, in which case the action of <A>G</A> on its cosets is
##  taken.
##  If the optional parameter <A>cost</A> is not given, <A>cost</A> is taken to be the
##  degree of the image representation (or 1 if the image is a pc group). This
##  <A>cost</A> is stored with the action to determine later whether another
##  action is <Q>better</Q>.
##  The optional boolean parameter <A>blocksdone</A> indicates if set to true, that
##  all block systems of the image of <A>op</A> have already been computed and the
##  resulting (lower degree, but not necessarily faithful for <M>G/N</M>) actions
##  have been already considered. (Otherwise such a test may be done later by
##  <C>DoCheapActionImages</C>.)
##  The function internally re-sorts the list of normal subgroups to permit
##  binary search among them. If a new action is returns the re-sorting
##  permutation applied there. If returns <K>false</K> if a <Q>better</Q> action was
##  already known, it returns <Q>fail</Q> if this factor is locked.
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("AddNaturalHomomorphismsPool");


#############################################################################
##
#F  LockNaturalHomomorphismsPool(<G>,<N>)  . .  store flag to prohibit changes 
##
##  <ManSection>
##  <Func Name="LockNaturalHomomorphismsPool" Arg='G,N'/>
##
##  <Description>
##  Calling this function stores a flag in the <C>NaturalHomomorphismsPool</C> of
##  <A>G</A> to prohibit it to store new (even better) faithful actions for <M>G/N</M>.
##  This can be used in algorithms to ensure that
##  <C>NaturalHomomorphismByNormalSubgroup(<A>G</A>,<A>N</A>)</C> will always return the same
##  mapping, even if in the meantime other homomorphisms are computed anew,
##  which &ndash;as a side effect&ndash; obtained a better action for <M>G/N</M> which &GAP;
##  normally would store.
##  The locking can be reverted by <C>UnlockNaturalHomomorphismsPool(<A>G</A>,<A>N</A>)</C>.
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("LockNaturalHomomorphismsPool");

#############################################################################
##
#F  UnlockNaturalHomomorphismsPool(<G>,<N>) .  clear flag to allow changes of
##
##  <ManSection>
##  <Func Name="UnlockNaturalHomomorphismsPool" Arg='G,N'/>
##
##  <Description>
##  clears the flag set by <C>LockNaturalHomomorphismsPool(<A>G</A>,<A>N</A>)</C>.
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("UnlockNaturalHomomorphismsPool");

#############################################################################
##
#F  KnownNaturalHomomorphismsPool(<G>,<N>) . . .  check whether Hom is stored
##
##  <ManSection>
##  <Func Name="KnownNaturalHomomorphismsPool" Arg='G,N'/>
##
##  <Description>
##  This function tests whether an homomorphism for
##  <C>NaturalHomomorphismByNormalSubgroup(<A>G</A>,<A>N</A>)</C> is already known (or
##  computed trivially for <M>G=N</M> or <M>N=\langle1\rangle</M>).
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("KnownNaturalHomomorphismsPool");

#############################################################################
##
#F  GetNaturalHomomorphismsPool(<G>,<N>) . . . get action for G/N if known
##
##  <ManSection>
##  <Func Name="GetNaturalHomomorphismsPool" Arg='G,N'/>
##
##  <Description>
##  returns a <C>NaturalHomomorphismByNormalSubgroup(<A>G</A>,<A>N</A>)</C> if one is
##  stored already in the <C>NaturalHomomorphismsPool</C> of <A>G</A>.
##  (As the homomorphism may be stored by a <Q>recipe</Q> this command can
##  still take some time when called the first time.)
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("GetNaturalHomomorphismsPool");

#############################################################################
##
#F  DegreeNaturalHomomorphismsPool(<G>,<N>) degree for action for G/N 
##
##  <ManSection>
##  <Func Name="DegreeNaturalHomomorphismsPool" Arg='G,N'/>
##
##  <Description>
##  returns the cost (see <Ref Func="AddNaturalHomomorphismsPool"/>) of a stored action
##  for <M>G/N</M> and fail if no such action is stored.
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("DegreeNaturalHomomorphismsPool");


#############################################################################
##
#F  CloseNaturalHomomorphismsPool(<G>[,<N>]) . . calc intersections of known
##
##  <ManSection>
##  <Func Name="CloseNaturalHomomorphismsPool" Arg='G[,N]'/>
##
##  <Description>
##  This command tries to build actions for (new) factor groups from the
##  already known actions in the <C>NaturalHomomorphismsPool(<A>G</A>)</C> by considering
##  intransitive representations for subdirect products. Any new or better
##  homomorphism obtained this way is stored (see
##  <Ref Func="AddNaturalHomomorphismsPool"/>). 
##  If the optional parameter <A>N</A> is given, only actions which have <A>N</A> in their
##  kernel are considered.
##  The function keeps track of already considered subdirect products, thus
##  there is no overhead in calling it several times.
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("CloseNaturalHomomorphismsPool");

#############################################################################
##
#F  PullBackNaturalHomomorphismsPool(<hom>]) . . transfer nathoms of image
##
##  <ManSection>
##  <Func Name="PullBackNaturalHomomorphismsPool" Arg='hom'/>
##
##  <Description>
##  If <A>hom</a> is a homomorphism, this command transfers the natural
##  homomorphisms of the image of <A>hom</A> to the source of <A>hom</A>.
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("PullBackNaturalHomomorphismsPool");

#############################################################################
##
#F  EraseNaturalHomomorphismsPool(<G>)
##
##  <ManSection>
##  <Func Name="EraseNaturalHomomorphismsPool" Arg='G'/>
##
##  <Description>
##  This command erases all stored natural homomorphisms associated to the
##  group <A>G</A>. It is used to recover memory.
##  </Description>
##  </ManSection>
##
DeclareGlobalFunction("EraseNaturalHomomorphismsPool");


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