#############################################################################
##
#W  stdgen.gd                GAP library                        Thomas Breuer
##
#Y  (C) 1999 School Math and Comp. Sci., University of St.  Andrews, Scotland
##
##  This file contains the declarations needed for dealing with standard
##  generators of finite groups.
##


#T TO DO:
#T - a function that can be used to *define* standard generators,
#T   using the character table with underlying group (perhaps also the
#T   table of marks or an explicit description of all maximal subgroups)


#############################################################################
##
##  Standard Generators of Groups
##  <#GAPDoc Label="[1]{stdgen}">
##  An <M>s</M>-tuple of <E>standard generators</E> of a given group <M>G</M>
##  is a vector <M>(g_1, g_2, \ldots, g_s)</M> of elements <M>g_i \in G</M>
##  satisfying certain conditions (depending on the isomorphism type of
##  <M>G</M>) such that
##  <Enum>
##  <Item>
##      <M>\langle g_1, g_2, \ldots, g_s \rangle = G</M> and
##  </Item>
##  <Item>
##      the vector is unique up to automorphisms of <M>G</M>,
##      i.e., for two vectors <M>(g_1, g_2, \ldots, g_s)</M> and
##      <M>(h_1, h_2, \ldots, h_s)</M> of standard generators,
##      the map <M>g_i \mapsto h_i</M> extends to an automorphism of <M>G</M>.
##  </Item>
##  </Enum>
##  For details about standard generators, see <Cite Key="Wil96"/>.
##  <#/GAPDoc>
##


#############################################################################
##
#A  StandardGeneratorsInfo( <G> )
##
##  <#GAPDoc Label="StandardGeneratorsInfo:stdgen">
##  <ManSection>
##  <Attr Name="StandardGeneratorsInfo" Arg='G' Label="for groups"/>
##
##  <Description>
##  When called with the group <A>G</A>,
##  <Ref Func="StandardGeneratorsInfo" Label="for groups"/> returns a list of
##  records with at least one of the components <C>script</C> and
##  <C>description</C>.
##  Each such record defines <E>standard generators</E> of groups isomorphic
##  to <A>G</A>, the <M>i</M>-th record is referred to as the <M>i</M>-th set
##  of standard generators for such groups.
##  The value of <C>script</C> is a dense list of lists, each encoding a
##  command that has one of the following forms.
##  <List>
##  <Mark>A <E>definition</E> <M>[ i, n, k ]</M> or <M>[ i, n ]</M></Mark>
##  <Item>
##      means to search for an element of order <M>n</M>,
##      and to take its <M>k</M>-th power as candidate for the <M>i</M>-th
##      standard generator (the default for <M>k</M> is <M>1</M>),
##  </Item>
##  <Mark>a <E>relation</E> <M>[ i_1, k_1, i_2, k_2, \ldots, i_m, k_m, n ]</M> with <M>m > 1</M></Mark>
##  <Item>
##      means a check whether the element
##      <M>g_{{i_1}}^{{k_1}} g_{{i_2}}^{{k_2}} \cdots g_{{i_m}}^{{k_m}}</M>
##      has order <M>n</M>; if <M>g_j</M> occurs then of course the
##      <M>j</M>-th generator must have been defined before,
##  </Item>
##  <Mark>a <E>relation</E> <M>[ [ i_1, i_2, \ldots, i_m ], <A>slp</A>, n ]</M></Mark>
##  <Item>
##      means a check whether the result of the straight line program
##      <A>slp</A> (see <Ref Sect="Straight Line Programs" BookName="ref"/>) applied to
##      the candidates <M>g_{{i_1}}, g_{{i_2}}, \ldots, g_{{i_m}}</M> has
##      order <M>n</M>, where the candidates <M>g_j</M> for the <M>j</M>-th
##      standard generators must have been defined before,
##  </Item>
##  <Mark>a <E>condition</E> <M>[ [ i_1, k_1, i_2, k_2, \ldots, i_m, k_m ], f, v ]</M></Mark>
##  <Item>
##      means a check whether the &GAP; function in the global list
##      <Ref Var="StandardGeneratorsFunctions"/>
##      that is followed by the list <M>f</M> of strings returns the value
##      <M>v</M> when it is called with <M>G</M> and
##      <M>g_{{i_1}}^{{k_1}} g_{{i_2}}^{{k_2}} \cdots g_{{i_m}}^{{k_m}}</M>.
##  </Item>
##  </List>
##  Optional components of the returned records are
##  <List>
##  <Mark><C>generators</C></Mark>
##  <Item>
##      a string of names of the standard generators,
##  </Item>
##  <Mark><C>description</C></Mark>
##  <Item>
##      a string describing the <C>script</C> information in human readable
##      form, in terms of the <C>generators</C> value,
##  </Item>
##  <Mark><C>classnames</C></Mark>
##  <Item>
##      a list of strings, the <M>i</M>-th entry being the name of the
##      conjugacy class containing the <M>i</M>-th standard generator,
##      according to the &ATLAS; character table of the group
##      (see <Ref Func="ClassNames" BookName="ref"/>), and
##  <!-- function that tries to compute the classes from the <C>description</C> value-->
##  <!-- and the character table? -->
##  </Item>
##  <Mark><C>ATLAS</C></Mark>
##  <Item>
##      a boolean; <K>true</K> means that the standard generators coincide
##      with those defined in Rob Wilson's &ATLAS; of Group Representations
##      (see <Cite Key="AGR"/>), and <K>false</K> means that this
##      property is not guaranteed.
##  </Item>
##  <Mark><C>standardization</C></Mark>
##  <Item>
## a positive integer <M>i</M>; Whenever <C>ATLAS</C> returns <K>true</K> the value of <M>i</M> means that the generators 
## stored in the group are standard generators w.r.t. standardization <M>i</M>, in the sense of Rob Wilson's &ATLAS; of Group Representations.
##  </Item>
##  </List>
##  <P/>
##  There is no default method for an arbitrary isomorphism type,
##  since in general the definition of standard generators is not obvious.
##  <P/>
##  The function <Ref Func="StandardGeneratorsOfGroup"/>
##  can be used to find standard generators of a given group isomorphic
##  to <A>G</A>.
##  <P/>
##  The <C>generators</C> and <C>description</C> values, if not known,
##  can be computed by <Ref Func="HumanReadableDefinition"/>.
##  <Example><![CDATA[
##  gap> StandardGeneratorsInfo( TableOfMarks( "L3(3)" ) );
##[ rec( ATLAS := true, 
##      description := "|a|=2, |b|=3, |C(b)|=9, |ab|=13, |ababb|=4", 
##      generators := "a, b", 
##      script := [ [ 1, 2 ], [ 2, 3 ], [ [ 2, 1 ], [ "|C(",, ")|" ], 9 ], 
##          [ 1, 1, 2, 1, 13 ], [ 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 4 ] ], 
##      standardization := 1 ) ]
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareAttribute( "StandardGeneratorsInfo", IsGroup );
#T make this an operation also for strings?


#############################################################################
##
#F  HumanReadableDefinition( <info> )
#F  ScriptFromString( <string> )
##
##  <#GAPDoc Label="HumanReadableDefinition">
##  <ManSection>
##  <Func Name="HumanReadableDefinition" Arg='info'/>
##  <Func Name="ScriptFromString" Arg='string'/>
##
##  <Description>
##  Let <A>info</A> be a record that is valid as value of
##  <Ref Func="StandardGeneratorsInfo" Label="for groups"/>.
##  <Ref Func="HumanReadableDefinition"/> returns a string that describes the
##  definition of standard generators given by the <C>script</C> component of
##  <A>info</A> in human readable form.
##  The names of the generators are taken from the <C>generators</C>
##  component (default names <C>"a"</C>, <C>"b"</C> etc. are computed
##  if necessary),
##  and the result is stored in the <C>description</C> component.
##  <P/>
##  <Ref Func="ScriptFromString"/> does the converse of
##  <Ref Func="HumanReadableDefinition"/>, i.e.,
##  it takes a string <A>string</A> as returned by
##  <Ref Func="HumanReadableDefinition"/>, and returns a corresponding
##  <C>script</C> list.
##  <P/>
##  If <Q>condition</Q> lines occur in the script
##  (see <Ref Func="StandardGeneratorsInfo" Label="for groups"/>)
##  then the functions that occur must be contained in
##  <Ref Var="StandardGeneratorsFunctions"/>.
##  <Example><![CDATA[
##  gap> scr:= ScriptFromString( "|a|=2, |b|=3, |C(b)|=9, |ab|=13, |ababb|=4" );
##  [ [ 1, 2 ], [ 2, 3 ], [ [ 2, 1 ], [ "|C(",, ")|" ], 9 ], [ 1, 1, 2, 1, 13 ], 
##    [ 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 4 ] ]
##  gap> info:= rec( script:= scr );
##  rec( script := [ [ 1, 2 ], [ 2, 3 ], [ [ 2, 1 ], [ "|C(",, ")|" ], 9 ], 
##        [ 1, 1, 2, 1, 13 ], [ 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 4 ] ] )
##  gap> HumanReadableDefinition( info );
##  "|a|=2, |b|=3, |C(b)|=9, |ab|=13, |ababb|=4"
##  gap> info;
##  rec( description := "|a|=2, |b|=3, |C(b)|=9, |ab|=13, |ababb|=4", 
##    generators := "a, b", 
##    script := [ [ 1, 2 ], [ 2, 3 ], [ [ 2, 1 ], [ "|C(",, ")|" ], 9 ], 
##        [ 1, 1, 2, 1, 13 ], [ 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 4 ] ] )
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "HumanReadableDefinition" );

DeclareGlobalFunction( "ScriptFromString" );


#############################################################################
##
#V  StandardGeneratorsFunctions
##
##  <#GAPDoc Label="StandardGeneratorsFunctions">
##  <ManSection>
##  <Var Name="StandardGeneratorsFunctions"/>
##
##  <Description>
##  <Ref Func="StandardGeneratorsFunctions"/> is a list of even length.
##  At position <M>2i-1</M>, a function of two arguments is stored,
##  which are expected to be a group and a group element.
##  At position <M>2i</M> a list of strings is stored such that first
##  inserting a generator name in all holes and then forming the
##  concatenation yields a string that describes the function at the previous
##  position;
##  this string must contain the generator enclosed in round brackets
##  <C>(</C> and <C>)</C>.
##  <P/>
##  This list is used by the functions
##  <Ref Func="StandardGeneratorsInfo" Label="for groups"/>),
##  <Ref Func="HumanReadableDefinition"/>, and
##  <Ref Func="ScriptFromString"/>.
##  Note that the lists at even positions must be pairwise different.
##  <Example><![CDATA[
##  gap> StandardGeneratorsFunctions{ [ 1, 2 ] };
##  [ function( G, g ) ... end, [ "|C(",, ")|" ] ]
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
BindGlobal( "StandardGeneratorsFunctions", [] );


#############################################################################
##
#F  IsStandardGeneratorsOfGroup( <info>, <G>, <gens> )
##
##  <#GAPDoc Label="IsStandardGeneratorsOfGroup">
##  <ManSection>
##  <Func Name="IsStandardGeneratorsOfGroup" Arg='info, G, gens'/>
##
##  <Description>
##  Let <A>info</A> be a record that is valid as value of
##  <Ref Func="StandardGeneratorsInfo" Label="for groups"/>,
##  <A>G</A> a group, and <A>gens</A> a list of generators for <A>G</A>.
##  In this case, <Ref Func="IsStandardGeneratorsOfGroup"/> returns
##  <K>true</K> if <A>gens</A> satisfies the conditions of the <C>script</C>
##  component of <A>info</A>, and <K>false</K> otherwise.
##  <P/>
##  Note that the result <K>true</K> means that <A>gens</A> is a list of
##  standard generators for <A>G</A> only if <A>G</A> has the isomorphism
##  type for which <A>info</A> describes standard generators.
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "IsStandardGeneratorsOfGroup" );


#############################################################################
##
#F  StandardGeneratorsOfGroup( <info>, <G>[, <randfunc>] )
##
##  <#GAPDoc Label="StandardGeneratorsOfGroup">
##  <ManSection>
##  <Func Name="StandardGeneratorsOfGroup" Arg='info, G[, randfunc]'/>
##
##  <Description>
##  Let <A>info</A> be a record that is valid as value of
##  <Ref Func="StandardGeneratorsInfo" Label="for groups"/>,
##  and <A>G</A> a group of the isomorphism type for which <A>info</A>
##  describes standard generators.
##  In this case, <Ref Func="StandardGeneratorsOfGroup"/> returns a list of
##  standard generators of <A>G</A>,
##  see Section <Ref Sect="Standard Generators of Groups"/>.
##  <P/>
##  The optional argument <A>randfunc</A> must be a function that returns an
##  element of <A>G</A> when called with <A>G</A>; the default is
##  <Ref Func="PseudoRandom" BookName="ref"/>.
##  <P/>
##  In each call to <Ref Func="StandardGeneratorsOfGroup"/>,
##  the <C>script</C> component of <A>info</A> is scanned line by line.
##  <A>randfunc</A> is used to find an element of the prescribed order
##  whenever a definition line is met,
##  and for the relation and condition lines in the <C>script</C> list,
##  the current generator candidates are checked;
##  if a condition is not fulfilled, all candidates are thrown away,
##  and the procedure starts again with the first line.
##  When the conditions are fulfilled after processing the last line
##  of the <C>script</C> list, the standard generators are returned.
##  <P/>
##  <!-- Admit the possibility to specify the desired classes?-->
##  <!-- For example, if there is only one class of a given order of a standard-->
##  <!-- generator then this element may be taken first and kept also after-->
##  <!-- failure for a partial vector of candidates.-->
##  <!--  (then the first element of right order may be kept, for example)-->
##  Note that if <A>G</A> has the wrong isomorphism type then
##  <Ref Func="StandardGeneratorsOfGroup"/> returns a list of elements in
##  <A>G</A> that satisfy the conditions of the <C>script</C> component of
##  <A>info</A> if such elements exist, and does not terminate otherwise.
##  In the former case, obviously the returned elements need not be standard
##  generators of <A>G</A>.
##  <Example><![CDATA[
##  gap> a5:= AlternatingGroup( 5 );
##  Alt( [ 1 .. 5 ] )
##  gap> info:= StandardGeneratorsInfo( TableOfMarks( "A5" ) )[1];
## rec( ATLAS := true, description := "|a|=2, |b|=3, |ab|=5", 
##  generators := "a, b", script := [ [ 1, 2 ], [ 2, 3 ], [ 1, 1, 2, 1, 5 ] ], 
##  standardization := 1 )
##  gap> IsStandardGeneratorsOfGroup( info, a5, [ (1,3)(2,4), (3,4,5) ] );
##  true
##  gap> IsStandardGeneratorsOfGroup( info, a5, [ (1,3)(2,4), (1,2,3) ] );
##  false
##  gap> s5:= SymmetricGroup( 5 );;
##  gap> RepresentativeAction( s5, [ (1,3)(2,4), (3,4,5) ], 
##  >        StandardGeneratorsOfGroup( info, a5 ), OnPairs ) <> fail;
##  true
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "StandardGeneratorsOfGroup" );

#############################################################################
##
#A  StandardGeneratorsInfo( <tom> )
##
##  <#GAPDoc Label="StandardGeneratorsInfo:tom">
##  <ManSection>
##  <Attr Name="StandardGeneratorsInfo" Arg='tom'
##  Label="for tables of marks"/>
##
##  <Description>
##  For a table of marks <A>tom</A>, a stored value of
##  <Ref Func="StandardGeneratorsInfo" Label="for tables of marks"/>
##  equals  the  value  of  this   attribute   for   the   underlying group
##  (see <Ref Attr="UnderlyingGroup" Label="for tables of marks" BookName="ref"/>)
##  of <A>tom</A>,
##  cf. Section <Ref Sect="Standard Generators of Groups"/>.
##  <P/>
##  In this case, the <Ref Func="GeneratorsOfGroup" BookName="ref"/> value of the underlying
##  group <M>G</M> of <A>tom</A> is assumed to be in fact a list of
##  standard generators for <M>G</M>;
##  So one should be careful when setting the
##  <Ref Func="StandardGeneratorsInfo" Label="for tables of marks"/> value
##  by hand.
##  <P/>
##  There is no default method to compute the
##  <Ref Func="StandardGeneratorsInfo" Label="for tables of marks"/> value
##  of a table of marks if it is not yet stored.
##  <P/>
##  <Example><![CDATA[
##  gap> a5:=TableOfMarks("A5");
##  gap> std:= StandardGeneratorsInfo( a5 );
##  [ rec( ATLAS := true, description := "|a|=2, |b|=3, |ab|=5", 
##      generators := "a, b", script := [ [ 1, 2 ], [ 2, 3 ], [ 1, 1, 2, 1, 5 ] 
##         ], standardization := 1 ) ]
##  gap> # Now find standard generators of an isomorphic group.
##  gap> g:= SL(2,4);;
##  gap> repeat
##  >   x:= PseudoRandom( g );
##  > until Order( x ) = 2;
##  gap> repeat  
##  >   y:= PseudoRandom( g );
##  > until Order( y ) = 3 and Order( x*y ) = 5;
##  gap> # Compute a representative w.r.t. these generators.
##  gap> RepresentativeTomByGenerators( a5, 4, [ x, y ] );
##  Group([ [ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2) ] ],
##    [ [ Z(2^2), Z(2^2)^2 ], [ Z(2^2)^2, Z(2^2) ] ] ])
##  gap> # Show that the new generators are really good.
##  gap> grp:= UnderlyingGroup( a5 );;
##  gap> iso:= GroupGeneralMappingByImages( grp, g,
##  >              GeneratorsOfGroup( grp ), [ x, y ] );;
##  gap> IsGroupHomomorphism( iso );
##  true
##  gap> IsBijective( iso );
##  true
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareAttribute( "StandardGeneratorsInfo", IsTableOfMarks );

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