/usr/share/gap/pkg/tomlib/gap/stdgen.gd is in gap-table-of-marks 1r2p6-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 | #############################################################################
##
#W stdgen.gd GAP library Thomas Breuer
##
#H @(#)$Id: stdgen.gd,v 1.6 2010/09/28 16:47:46 alexk Exp $
##
#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.
##
Revision.stdgen_gd :=
"@(#)$Id: stdgen.gd,v 1.6 2010/09/28 16:47:46 alexk Exp $";
#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" BookName="ref"/>
## 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>
##
DeclareGlobalVariable( "StandardGeneratorsFunctions",
"list of functions used in scripts, and their translations to strings" );
#############################################################################
##
#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" BookName="ref"/>,
## 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" BookName="ref"/> 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" BookName="ref"/>
## 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" BookName="ref"/>.
## <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
|