Quelle probgen.g Sprache: unbekannt

# This file was created from probgen.xml, do not edit!
#############################################################################
##
#A PositionsProperty( <list>, <prop> )
##
## Let <list> be a dense list and <prop> be a unary function that returns
## `true' or `false' when applied to the entries of <list>.
## `PositionsProperty' returns the set of positions in <list> for which
## `true' is returned.
##
if not IsBound( PositionsProperty ) then
 PositionsProperty:= function( list, prop )
 return Filtered( [ 1 .. Length( list ) ], i -> prop( list[i] ) );
 end;
 fi;

#############################################################################
##
#A UnorderedTuplesNoSort( <list>, <k> )
##
## Let <list> be a dense list and <k> be a nonnegative integer.
## `UnorderedTuplesNoSort' returns a list of all unordered <k>-tuples with
## repetitions of elements in <list>.
## The only difference to the GAP library function `UnorderedTuples' is
## that the entries in the result of `UnorderedTuplesNoSort' need not be
## sorted.
## This is advantageous when the comparison of elements in <list> is
## expensive, e.~g., when these elements are conjugacy classes in a group.
##
BindGlobal( "UnorderedTuplesNoSort", function( list, k )
 return List( UnorderedTuples( [ 1 .. Length( list ) ], k ),
 tuple -> list{ tuple } );
end );

#############################################################################
##
#F TripleWithProperty( <threelists>, <prop> )
#F QuadrupleWithProperty( <fourlists>, <prop> )
##
## Let <threelists> be a list of three lists $l_1, l_2, l_3$,
## and <prop> be a unary function that takes a triple $[ x_1, x_2, x_3 ]$
## with $x_i \in l_i$ as its argument and returns either `true' or `false'.
## `TripleWithProperty' returns a triple for which `prop' returns `true'
## if such a triple exists, and `fail' otherwise.
##
## Analogously, the first argument of `QuadrupleWithProperty' is a list
## <fourlists> of four lists, and the second argument <prop> takes a
## quadruple as its argument.
##
BindGlobal( "TripleWithProperty", function( threelists, prop )
 local i, j, k, test;
 for i in threelists[1] do
 for j in threelists[2] do
 for k in threelists[3] do
 test:= [ i, j, k ];
 if prop( test ) then
 return test;
 fi;
 od;
 od;
 od;
 return fail;
end );
BindGlobal( "QuadrupleWithProperty", function( fourlists, prop )
 local i, j, k, l, test;
 for i in fourlists[1] do
 for j in fourlists[2] do
 for k in fourlists[3] do
 for l in fourlists[4] do
 test:= [ i, j, k, l ];
 if prop( test ) then
 return test;
 fi;
 od;
 od;
 od;
 od;
 return fail;
end );

#############################################################################
##
#F PrintFormattedArray( <array> )
##
## Let <array> be a rectangular table.
## `PrintFormattedArray' prints <array> such that each column is right
## aligned.
## The only difference to the GAP library function `PrintArray'
## is that the latter prints all columns at the same width.
##
BindGlobal( "PrintFormattedArray", function( array )
 local colwidths, n, row;
 array:= List( array, row -> List( row, String ) );
 colwidths:= List( TransposedMat( array ),
 col -> Maximum( List( col, Length ) ) );
 n:= Length( array[1] );
 for row in List( array, row -> List( [ 1 .. n ],
 i -> String( row[i], colwidths[i] ) ) ) do
 Print( " ", JoinStringsWithSeparator( row, " " ), "\n" );
 od;
end );

#############################################################################
##
#F PossiblePermutationCharacters( , <tbl> )
##
## For two ordinary character tables and <tbl>,
## `PossiblePermutationCharacters' returns the set of all induced class
## functions of the trivial character of to <tbl>,
## w.r.t.~the possible class fusions from to <tbl>.
##
if not IsBound( PossiblePermutationCharacters ) then
 BindGlobal( "PossiblePermutationCharacters", function( sub, tbl )
 local fus, triv;
 fus:= PossibleClassFusions( sub, tbl );
 if fus = fail then
 return fail;
 fi;
 triv:= [ TrivialCharacter( sub ) ];
 return Set(
 List( fus, map -> Induced( sub, tbl, triv, map )[1] ) );
 end );
 fi;

#############################################################################
##
#A PrimitivePermutationCharacters( <tbl> )
##
## For an ordinary character table <tbl> for which either the value of one
## of the attributes `Maxes' or `UnderlyingGroup' is stored or the table of
## marks is contained in the GAP library of tables of marks,
## `PrimitivePermutationCharacters' returns the list of all primitive
## permutation characters of <tbl>.
## Otherwise `fail' is returned.
##
## We use 'InstallOtherMethod' not 'InstallMethod' because another test file
## declares the same attribute and installs the same method.
##
DeclareAttribute( "PrimitivePermutationCharacters",
 IsCharacterTable );
InstallOtherMethod( PrimitivePermutationCharacters,
 [ IsCharacterTable ],
 function( tbl )
 local maxes, i, fus, poss, tom, G;
 if HasMaxes( tbl ) then
 maxes:= List( Maxes( tbl ), CharacterTable );
 for i in [ 1 .. Length( maxes ) ] do
 fus:= GetFusionMap( maxes[i], tbl );
 if fus = fail then
 fus:= PossibleClassFusions( maxes[i], tbl );
 poss:= Set( fus,
 map -> InducedClassFunctionsByFusionMap(
 maxes[i], tbl,
 [ TrivialCharacter( maxes[i] ) ], map )[1] );
 if Length( poss ) = 1 then
 maxes[i]:= poss[1];
 else
 return fail;
 fi;
 else
 maxes[i]:= TrivialCharacter( maxes[i] )^tbl;
 fi;
 od;
 return maxes;
 elif HasFusionToTom( tbl ) then
 tom:= TableOfMarks( tbl );
 maxes:= MaximalSubgroupsTom( tom );
 return PermCharsTom( tbl, tom ){ maxes[1] };
 elif HasUnderlyingGroup( tbl ) then
 G:= UnderlyingGroup( tbl );
 return List( MaximalSubgroupClassReps( G ),
 M -> TrivialCharacter( M )^tbl );
 fi;
 return fail;
end );

#############################################################################
##
#F ApproxP( <primitives>, <spos> )
##
## Let <primitives> be a list of primitive permutation characters of a group
## $G$, say, and <spos> the position of the conjugacy class of the element
## $s \in G$.
## Assume that the elements in <primitives> have the form $1_M^G$,
## for suitable maximal subgroups $M$ of $G$,
## and let $\MM$ be the set of these groups $M$.
## `ApproxP' returns the class function $\psi$ of $G$ that is defined by
## $\psi(1) = 0$ and
## \[
## \psi(g) = \sum_{M \in \MM}
## \frac{1_M^G(s) \cdot 1_M^G(g)}{1_M^G(1)}
## \]
## otherwise.
##
## If <primitives> contains all those primitive permutation characters
## $1_M^G$ of $G$ (with multiplicity according to the number of conjugacy
## classes of these maximal subgroups) that do not vanish at $s$,
## and if all these $M$ are self-normalizing in $G$
## --this holds for example if $G$ is a finite simple group--
## then $\psi(g) = &total;( g, s )$ holds.
##
## The latter is an upper bound for the proportion
## $∝( g, s )$ of elements in the conjugacy class of $s$ that generate
## together with $g$ a proper subgroup of $G$.
##
## Note that if $∝( g, s )$ is less than $1/k$ for all
## $g \in G^{\times}$ then $G$ has spread at least $k$.
##
BindGlobal( "ApproxP", function( primitives, spos )
 local sum;
 sum:= ShallowCopy( Sum( List( primitives,
 pi -> pi[ spos ] * pi / pi[1] ) ) );
 sum[1]:= 0;
 return sum;
end );

#############################################################################
##
#F ProbGenInfoSimple( <tbl> )
##
## Let <tbl> be the ordinary character table of a finite simple group $S$.
## If the full list of primitive permutation characters of <tbl> cannot be
## computed with `PrimitivePermutationCharacters' then `fail' is returned.
## Otherwise `ProbGenInfoSimple' returns a list of length $5$, containing
## the identifier of <tbl>,
## the value $&total;(S)$,
## the value $\sprtotal( S )$,
## a list of {\ATLAS} names of the classes of elements $s$ for which
## $&total;(S) = &total;( S, s )$ holds,
## and the list of the corresponding cardinalities $|&M;(S,s)|$.
##
BindGlobal( "ProbGenInfoSimple", function( tbl )
 local prim, max, min, bound, s;
 prim:= PrimitivePermutationCharacters( tbl );
 if prim = fail then
 return fail;
 fi;
 max:= List( [ 1 .. NrConjugacyClasses( tbl ) ],
 i -> Maximum( ApproxP( prim, i ) ) );
 min:= Minimum( max );
 bound:= Inverse( min );
 if IsInt( bound ) then
 bound:= bound - 1;
 else
 bound:= Int( bound );
 fi;
 s:= PositionsProperty( max, x -> x = min );
 s:= List( Set( s, i -> ClassOrbit( tbl, i ) ), i -> i[1] );
 return [ Identifier( tbl ),
 min,
 bound,
 AtlasClassNames( tbl ){ s },
 Sum( List( prim, pi -> pi{ s } ) ) ];
end );

#############################################################################
##
#F ProbGenInfoAlmostSimple( <tblS>, <tblG>, <sposS> )
##
## Let <tblS> be the ordinary character table of a finite simple group $S$,
## <tblG> be the character table of an automorphic extension $G$ of $S$
## in which $S$ has prime index,
## and <sposS> a list of class positions in <tblS>.
##
## If the full list of primitive permutation characters of <tblG> cannot be
## computed with `PrimitivePermutationCharacters' then `fail' is returned.
## Otherwise `ProbGenInfoAlmostSimple' returns a list of length five,
## containing
## the identifier of <tblG>,
## the maximum $m$ of $&total;^{\prime}( G, s )$,
## for $s$ in the classes described by <sposS>,
## a list of {\ATLAS} names (w.r.t. $G$) of the classes of elements $s$
## for which this maximum is attained,
## and the list of the corresponding cardinalities $|\M^{\prime}(G,s)|$.
##
BindGlobal( "ProbGenInfoAlmostSimple", function( tblS, tblG, sposS )
 local p, fus, inv, prim, sposG, outer, approx, l, max, min,
 s, cards, i, names;
 p:= Size( tblG ) / Size( tblS );
 if not IsPrimeInt( p )
 or Length( ClassPositionsOfNormalSubgroups( tblG ) ) <> 3 then
 return fail;
 fi;
 fus:= GetFusionMap( tblS, tblG );
 if fus = fail then
 return fail;
 fi;
 inv:= InverseMap( fus );
 prim:= PrimitivePermutationCharacters( tblG );
 if prim = fail then
 return fail;
 fi;
 sposG:= Set( fus{ sposS } );
 outer:= Difference( PositionsProperty(
 OrdersClassRepresentatives( tblG ), IsPrimeInt ), fus );
 approx:= List( sposG, i -> ApproxP( prim, i ){ outer } );
 if IsEmpty( outer ) then
 max:= List( approx, x -> 0 );
 else
 max:= List( approx, Maximum );
 fi;
 min:= Minimum( max);
 s:= sposG{ PositionsProperty( max, x -> x = min ) };
 cards:= List( prim, pi -> pi{ s } );
 for i in [ 1 .. Length( prim ) ] do
 # Omit the character that is induced from the simple group.
 if ForAll( prim[i], x -> x = 0 or x = prim[i][1] ) then
 cards[i]:= 0;
 fi;
 od;
 names:= AtlasClassNames( tblG ){ s };
 Perform( names, ConvertToStringRep );
 return [ Identifier( tblG ),
 min,
 names,
 Sum( cards ) ];
end );

#############################################################################
##
#F SigmaFromMaxes( <tbl>, <sname>, <maxes>, <numpermchars> )
#F SigmaFromMaxes( <tbl>, <sname>, <maxes>, <numpermchars>, <choice> )
##
## Let <tbl> be the ordinary character table of a finite almost simple group
## $G$ with socle $S$,
## <sname> be the name of a class in <tbl>,
## <maxes> be a list of character tables of all those maximal subgroups
## of $G$ which contain elements $s$ in the class with the name <sname>.
## Further let <numpermchars> be a list of integers such that the $i$-th
## entry in <maxes> induces `<numpermchars>[i]' different permutation
## characters.
## (So if several classes of maximal subgroups in $G$ induce the same
## permutation character then the table of this subgroup must occur with
## this multiplicity in <maxes>, and the corresponding entries in
## <numpermchars> must be $1$.
## Conversely, if there are $n$ classes of isomorphic maximal subgroups
## which induce $n$ different permutation characters then the table must
## occur only once in <maxes>, and the corresponding multiplicity in
## <numpermchars> must be $n$.)
##
## The return value is `fail' if there is an entry `<maxes>[i]' such that
## `PossiblePermutationCharacters' does not return a list of length
## `<numpermchars>[i]' when its arguments are `<maxes>[i]' and <tbl>.
##
## If the string `"outer"' is entered as the optional argument <choice> then
## $G$ is assumed to be an automorphic extension of $S$,
## with $[G:S]$ a prime,
## and $&total;^{\prime}(G,s)$ is returned.
##
## Otherwise `SigmaFromMaxes' returns $&total;(G,s)$.
##
BindGlobal( "SigmaFromMaxes", function( arg )
 local t, sname, maxes, numpermchars, prim, spos, outer;
 t:= arg[1];
 sname:= arg[2];
 maxes:= arg[3];
 numpermchars:= arg[4];
 prim:= List( maxes, s -> PossiblePermutationCharacters( s, t ) );
 spos:= Position( AtlasClassNames( t ), sname );
 if ForAny( [ 1 .. Length( maxes ) ],
 i -> Length( prim[i] ) <> numpermchars[i] ) then
 return fail;
 elif Length( arg ) = 5 and arg[5] = "outer" then
 outer:= Difference(
 PositionsProperty( OrdersClassRepresentatives( t ), IsPrimeInt ),
 ClassPositionsOfDerivedSubgroup( t ) );
 return Maximum( ApproxP( Concatenation( prim ), spos ){ outer } );
 else
 return Maximum( ApproxP( Concatenation( prim ), spos ) );
 fi;
end );

#############################################################################
##
#F DisplayProbGenMaxesInfo( <tbl>, <snames> )
##
## For a character table <tbl> with known `Maxes' value and a list <snames>
## of class names in <tbl>,
## `DisplayProbGenMaxesInfo' prints a description of the maximal subgroups
## of <tbl> that contain an element $s$ in the classes with names in the
## list <snames>.
## Printed are the `Identifier' values of the tables of the maximal
## subgroups and the number of conjugate subgroups in this class
## that contain $s$.
##
BindGlobal( "DisplayProbGenMaxesInfo", function( tbl, snames )
 local mx, prim, i, spos, nonz, indent, j;
 if not HasMaxes( tbl ) then
 Print( Identifier( tbl ), ": fail\n" );
 return;
 fi;
 # Now we are sure that the order of the characters returned by
 # 'PrimitivePermutationCharacters' is compatible with 'Maxes( tbl )'.
 mx:= List( Maxes( tbl ), CharacterTable );
 prim:= List( PrimitivePermutationCharacters( tbl ), ShallowCopy );
 for i in [ 1 .. Length( prim ) ] do
 # Deal with the case that the subgroup is normal.
 if ForAll( prim[i], x -> x = 0 or x = prim[i][1] ) then
 prim[i]:= prim[i] / prim[i][1];
 fi;
 od;
 spos:= List( snames,
 nam -> Position( AtlasClassNames( tbl ), nam ) );
 nonz:= List( spos, x -> PositionsProperty( prim, pi -> pi[x] <> 0 ) );
 for i in [ 1 .. Length( spos ) ] do
 Print( Identifier( tbl ), ", ", snames[i], ": " );
 indent:= ListWithIdenticalEntries(
 Length( Identifier( tbl ) ) + Length( snames[i] ) + 4, ' ' );
 if not IsEmpty( nonz[i] ) then
 Print( Identifier( mx[ nonz[i][1] ] ), " (",
 prim[ nonz[i][1] ][ spos[i] ], ")\n" );
 for j in [ 2 .. Length( nonz[i] ) ] do
 Print( indent, Identifier( mx[ nonz[i][j] ] ), " (",
 prim[ nonz[i][j] ][ spos[i] ], ")\n" );
 od;
 else
 Print( "\n" );
 fi;
 od;
end );

#############################################################################
##
#F PcConjugacyClassReps( <G> )
##
## Let <G> be a finite solvable group.
## `PcConjugacyClassReps' returns a list of representatives of
## the conjugacy classes of <G>,
## which are computed using a polycyclic presentation for <G>.
##
BindGlobal( "PcConjugacyClassReps", function( G )
 local iso;
 iso:= IsomorphismPcGroup( G );
 return List( ConjugacyClasses( Image( iso ) ),
 c -> PreImagesRepresentative( iso, Representative( c ) ) );
end );

#############################################################################
##
#F ClassesOfPrimeOrder( <G>, <primes>, <N> )
##
## Let <G> be a finite group, <primes> be a list of primes,
## and <N> be a normal subgroup of <G>.
## `ClassesOfPrimeOrder' returns a list of those conjugacy classes of <G>
## that are not contained in <N>
## and whose elements' orders occur in <primes>.
##
## For each prime $p$ in <primes>, first class representatives of order $p$
## in a Sylow $p$ subgroup of <G> are computed,
## then the representatives in <N> are discarded,
## and then representatives w. r. t. conjugacy in <G> are computed.
##
## (Note that this approach may be inappropriate if an elementary abelian
## Sylow $p$ subgroup for a large prime $p$ occurs, and if the conjugacy
## tests in <G> are expensive.)
##
BindGlobal( "ClassesOfPrimeOrder", function( G, primes, N )
 local ccl, p, syl, Greps, reps, r, cr;
 ccl:= [];
 for p in primes do
 syl:= SylowSubgroup( G, p );
 Greps:= [];
 reps:= Filtered( PcConjugacyClassReps( syl ),
 r -> Order( r ) = p and not r in N );
 for r in reps do
 cr:= ConjugacyClass( G, r );
 if ForAll( Greps, c -> c <> cr ) then
 Add( Greps, cr );
 fi;
 od;
 Append( ccl, Greps );
 od;
 return ccl;
end );

#############################################################################
##
#F IsGeneratorsOfTransPermGroup( <G>, <list> )
##
## Let <G> be a finite group that acts *transitively* on its moved points,
## and <list> a list of elements in <G>.
##
## `IsGeneratorsOfTransPermGroup' returns `true' if the elements in <list>
## generate <G>, and `false' otherwise.
## The main point is that the return value `true' requires the group
## generated by `list' to be transitive, and the check for transitivity
## is much cheaper than the test whether this group is equal to `G'.
##
if not IsBound( IsGeneratorsOfTransPermGroup) then
 BindGlobal( "IsGeneratorsOfTransPermGroup", function( G, list )
 local S;
 if not IsTransitive( G ) then
 Error( "<G> must be transitive on its moved points" );
 fi;
 S:= SubgroupNC( G, list );
 return IsTransitive( S, MovedPoints( G ) ) and
 Size( S ) = Size( G );
 end );
 fi;

#############################################################################
##
#F RatioOfNongenerationTransPermGroup( <G>, <g>, <s> )
##
## Let <G> be a finite group that acts *transitively* on its moved points,
## and <g> and <s> be two elements in <G>.
##
## `RatioOfNongenerationTransPermGroup' returns the proportion
## $∝(g,s)$.
##
BindGlobal( "RatioOfNongenerationTransPermGroup", function( G, g, s )
 local nongen, pair;
 if not IsTransitive( G ) then
 Error( "<G> must be transitive on its moved points" );
 fi;
 nongen:= 0;
 for pair in DoubleCosetRepsAndSizes( G, Centralizer( G, g ),
 Centralizer( G, s ) ) do
 if not IsGeneratorsOfTransPermGroup( G, [ s, g^pair[1] ] ) then
 nongen:= nongen + pair[2];
 fi;
 od;
 return nongen / Size( G );
end );

#############################################################################
##
#F DiagonalProductOfPermGroups( <groups> )
##
## Let $G$ be a group, and let <groups> be a list
## $[ G_1, G_2, \ldots, G_n ]$ of permutation groups such that $G_i$
## describes the action of $G$ on a set $\Omega_i$, say.
## Moreover, we require that for $1 \leq i, j \leq n$,
## mapping the `GeneratorsOfGroup' list of $G_i$ to that of $G_j$
## defines an isomorphism.
##
## `DiagonalProductOfPermGroups' takes `groups' as its argument,
## and returns the action of $G$ on the disjoint union of
## $\Omega_1, \Omega_2, \ldots \Omega_n$.
##
BindGlobal( "DiagonalProductOfPermGroups", function( groups )
 local prodgens, deg, i, gens, D, pi;
 prodgens:= GeneratorsOfGroup( groups[1] );
 deg:= NrMovedPoints( prodgens );
 for i in [ 2 .. Length( groups ) ] do
 gens:= GeneratorsOfGroup( groups[i] );
 D:= MovedPoints( gens );
 pi:= MappingPermListList( D, [ deg+1 .. deg+Length( D ) ] );
 deg:= deg + Length( D );
 prodgens:= List( [ 1 .. Length( prodgens ) ],
 i -> prodgens[i] * gens[i]^pi );
 od;
 return Group( prodgens );
end );

#############################################################################
##
#F RepresentativesMaximallyCyclicSubgroups( <tbl> )
##
## For an ordinary character table <tbl>,
## `RepresentativesMaximallyCyclicSubgroups' returns a list of class
## positions containing exactly one class of generators for each class of
## maximally cyclic subgroups.
##
BindGlobal( "RepresentativesMaximallyCyclicSubgroups", function( tbl )
 local n, result, orders, p, pmap, i, j;
 # Initialize.
 n:= NrConjugacyClasses( tbl );
 result:= BlistList( [ 1 .. n ], [ 1 .. n ] );
 # Omit powers of smaller order.
 orders:= OrdersClassRepresentatives( tbl );
 for p in PrimeDivisors( Size( tbl ) ) do
 pmap:= PowerMap( tbl, p );
 for i in [ 1 .. n ] do
 if orders[ pmap[i] ] < orders[i] then
 result[ pmap[i] ]:= false;
 fi;
 od;
 od;
 # Omit Galois conjugates.
 for i in [ 1 .. n ] do
 if result[i] then
 for j in ClassOrbit( tbl, i ) do
 if i <> j then
 result[j]:= false;
 fi;
 od;
 fi;
 od;
 # Return the result.
 return ListBlist( [ 1 .. n ], result );
end );

#############################################################################
##
#F ClassesPerhapsCorrespondingToTableColumns( <G>, <tbl>, <cols> )
##
## For a group <G>, its ordinary character table <tbl>, and a list <cols>
## of class positions in <tbl>,
## `ClassesPerhapsCorrespondingToTableColumns' returns the sublist
## of those conjugacy classes of `G' for which the corresponding column
## in `tbl' can be contained in `cols',
## according to element order and class length.
##
BindGlobal( "ClassesPerhapsCorrespondingToTableColumns",
 function( G, tbl, cols )
 local orders, classes, invariants;
 orders:= OrdersClassRepresentatives( tbl );
 classes:= SizesConjugacyClasses( tbl );
 invariants:= List( cols, i -> [ orders[i], classes[i] ] );
 return Filtered( ConjugacyClasses( G ),
 c -> [ Order( Representative( c ) ), Size(c) ] in invariants );
end );

#############################################################################
##
#F UpperBoundFixedPointRatios( <G>, <maxesclasses>, <truetest> )
##
## Let <G> be a finite group, and <maxesclasses> be a list
## $[ l_1, l_2, ..., l_n ]$ such that each $l_i$ is a list of conjugacy
## classes of maximal subgroups $M_i$ of <G>, such that all classes of
## prime element order in $M_i$ are contained in $l_i$,
## and such that the $M_i$ are all those maximal subgroups of <G>
## (in particular, \emph{not} only conjugacy class representatives of
## subgroups) that contain a fixed element $s \in G$.
##
## `UpperBoundFixedPointRatios' returns a list $[ x, y ]$, where
## \[
## x = \max_{1 \not= p \mid |G|} \max_{g \in G \setminus Z(G), |g|=p}
## \sum_{i=1}^n \sum_{h \in S(i,p,g)} |h^{M_i}| / |g^G|,
## \]
## and $S(i,p,g)$ is a set of representatives $h$ of all those classes in
## $l_i$ that satisfy $|h| = p$ and $|C_G(h)| = |C_G(g)|$,
## and in the case that $G$ is a permutation group additionally that
## $h$ and $g$ move the same number of points.
## Since $S(i,p,g) \supseteq g^G \cap M_i$ holds,
## $x$ is an upper bound for $&total;(G,s)$.
##
## The second entry is `true' if the first value is in fact equal to
## $\max_{g \in G \setminus Z(G)} &fpr;(g,G/M}$, and `false' otherwise.
##
## The third argument <truetest> must be `true' or `false',
## where `true' means that the exact value of $&total;(G,s)$ is computed
## not just an upper bound; this can be much more expensive.
## (We try to reduce the number of conjugacy tests in this case,
## the second half of the code is not completely straightforward.)
##
## If $G$ is an automorphic extension of a simple group $S$,
## with $[G:S] = p$ a prime, then `UpperBoundFixedPointRatios' can be used
## to compute $&total;^{\prime}(G,s)$,
## by choosing $M_i$ the maximal subgroups of $G$ containing $s$,
## except $S$, such that $l_i$ contains only the classes of element order
## $p$ in $M_i \setminus (M_i \cap S)$.
##
## Note that in the case $n = 1$, we have $&total;(G,s) = ∝(G,s)$,
## so in this case the second entry `true' means that the first entry is
## equal to $\max_{g \in G \setminus Z(G)} &fpr;(g,G/M_1}$.
##
BindGlobal( "UpperBoundFixedPointRatios",
 function( G, maxesclasses, truetest )
 local myIsConjugate, invs, info, c, r, o, inv, pos, sums, max, maxpos,
 maxlen, reps, split, i, found, j;
 myIsConjugate:= function( G, x, y )
 local movx, movy;
 movx:= MovedPoints( x );
 movy:= MovedPoints( y );
 if movx = movy then
 G:= Stabilizer( G, movx, OnSets );
 fi;
 return IsConjugate( G, x, y );
 end;
 invs:= [];
 info:= [];
 # First distribute the classes according to invariants.
 for c in Concatenation( maxesclasses ) do
 r:= Representative( c );
 o:= Order( r );
 # Take only prime order representatives.
 if IsPrimeInt( o ) then
 inv:= [ o, Size( Centralizer( G, r ) ) ];
 # Omit classes that are central in `G'.
 if inv[2] <> Size( G ) then
 if IsPerm( r ) then
 Add( inv, NrMovedPoints( r ) );
 fi;
 pos:= First( [ 1 .. Length( invs ) ], i -> inv = invs[i] );
 if pos = fail then
 # This class is not `G'-conjugate to any of the previous ones.
 Add( invs, inv );
 Add( info, [ [ r, Size( c ) * inv[2] ] ] );
 else
 # This class may be conjugate to an earlier one.
 Add( info[ pos ], [ r, Size( c ) * inv[2] ] );
 fi;
 fi;
 fi;
 od;
 if info = [] then
 return [ 0, true ];
 fi;
 repeat
 # Compute the contributions of the classes with the same invariants.
 sums:= List( info, x -> Sum( List( x, y -> y[2] ) ) );
 max:= Maximum( sums );
 maxpos:= Filtered( [ 1 .. Length( info ) ], i -> sums[i] = max );
 maxlen:= List( maxpos, i -> Length( info[i] ) );
 # Split the sets with the same invariants if necessary
 # and if we want to compute the exact value.
 if truetest and not 1 in maxlen then
 # Make one conjugacy test.
 pos:= Position( maxlen, Minimum( maxlen ) );
 reps:= info[ maxpos[ pos ] ];
 if myIsConjugate( G, reps[1][1], reps[2][1] ) then
 # Fuse the two classes.
 reps[1][2]:= reps[1][2] + reps[2][2];
 reps[2]:= reps[ Length( reps ) ];
 Unbind( reps[ Length( reps ) ] );
 else
 # Split the list. This may require additional conjugacy tests.
 Unbind( info[ maxpos[ pos ] ] );
 split:= [ reps[1], reps[2] ];
 for i in [ 3 .. Length( reps ) ] do
 found:= false;
 for j in split do
 if myIsConjugate( G, reps[i][1], j[1] ) then
 j[2]:= reps[i][2] + j[2];
 found:= true;
 break;
 fi;
 od;
 if not found then
 Add( split, reps[i] );
 fi;
 od;
 info:= Compacted( Concatenation( info,
 List( split, x -> [ x ] ) ) );
 fi;
 fi;
 until 1 in maxlen or not truetest;
 return [ max / Size( G ), 1 in maxlen ];
end );

#############################################################################
##
#F OrbitRepresentativesProductOfClasses( <G>, <classreps> )
##
## For a finite group <G> and a list
## $<classreps> = [ g_1, g_2, \ldots, g_n ]$ of elements in <G>,
## `OrbitRepresentativesProductOfClasses' returns a list of representatives
## of <G>-orbits on the Cartesian product
## $g_1^{<G>} \times g_2^{<G>} \times \cdots \times g_n^{<G>}$.
##
## The idea behind this function is to choose $R(<G>, g_1) = \{ ( g_1 ) \}$
## in the case $n = 1$,
## and, for $n > 1$,
## \[
## R(<G>, g_1, g_2, \ldots, g_n) = \{ (h_1, h_2, \ldots, h_n);
## (h_1, h_2, \ldots, h_{n-1}) \in R(<G>, g_1, g_2, \ldots, g_{n-1}),
## k_n = g_n^d, \textrm{\ for\ } d \in D \} ,
## \]
## where $D$ is a set of representatives of double cosets
## $C_{<G>}(g_n) \setminus <G> / \cap_{i=1}^{n-1} C_{<G>}(h_i)$.
##
BindGlobal( "OrbitRepresentativesProductOfClasses",
 function( G, classreps )
 local cents, n, orbreps;
 cents:= List( classreps, x -> Centralizer( G, x ) );
 n:= Length( classreps );
 orbreps:= function( reps, intersect, pos )
 if pos > n then
 return [ reps ];
 fi;
 return Concatenation( List(
 DoubleCosetRepsAndSizes( G, cents[ pos ], intersect ),
 r -> orbreps( Concatenation( reps, [ classreps[ pos ]^r[1] ] ),
 Intersection( intersect, cents[ pos ]^r[1] ), pos+1 ) ) );
 end;
 return orbreps( [ classreps[1] ], cents[1], 2 );
end );

#############################################################################
##
#F RandomCheckUniformSpread( <G>, <classreps>, <s>, <N> )
##
## Let <G> be a finite permutation group that is transitive on its moved
## points,
## <classreps> be a list of elements in <G>,
## <s> be an element in <G>,
## and <N> be a positive integer.
##
## `RandomCheckUniformSpread' computes representatives $X$ of <G>-orbits
## on the Cartesian product of the conjugacy classes of <classreps>;
## for each of them, up to <N> random conjugates $s^{\prime}$ of <s> are
## checked whether $s^{\prime}$ generates <G> with each element in the
## $n$-tuple of elements in $X$.
## If such an element $s^{\prime}$ is found this way, for all $X$,
## the function returns `true',
## otherwise a representative $X$ is returned for which no good conjugate
## of <s> is found.
##
BindGlobal( "RandomCheckUniformSpread", function( G, classreps, s, try )
 local elms, found, i, conj;
 if not IsTransitive( G, MovedPoints( G ) ) then
 Error( "<G> must be transitive on its moved points" );
 fi;
 # Compute orbit representatives of G on the direct product,
 # and try to find a good conjugate of s for each representative.
 for elms in OrbitRepresentativesProductOfClasses( G, classreps ) do
 found:= false;
 for i in [ 1 .. try ] do
 conj:= s^Random( G );
 if ForAll( elms,
 x -> IsGeneratorsOfTransPermGroup( G, [ x, conj ] ) ) then
 found:= true;
 break;
 fi;
 od;
 if not found then
 return elms;
 fi;
 od;
 return true;
end );

#############################################################################
##
#F CommonGeneratorWithGivenElements( <G>, <classreps>, <tuple> )
##
## Let <G> be a finite group,
## and <classreps> and <tuple> be lists of elements in <G>.
## `CommonGeneratorWithGivenElements' returns an element $g$ in the
## <G>-conjugacy class of one of the elements in <classreps> with the
## property that each element in <tuple> together with $g$ generates <G>,
## if such an element $g$ exists.
## Otherwise `fail' is returned.
##
BindGlobal( "CommonGeneratorWithGivenElements",
 function( G, classreps, tuple )
 local inter, rep, repcen, pair;
 if not IsTransitive( G, MovedPoints( G ) ) then
 Error( "<G> must be transitive on its moved points" );
 fi;
 inter:= Intersection( List( tuple, x -> Centralizer( G, x ) ) );
 for rep in classreps do
 repcen:= Centralizer( G, rep );
 for pair in DoubleCosetRepsAndSizes( G, repcen, inter ) do
 if ForAll( tuple,
 x -> IsGeneratorsOfTransPermGroup( G, [ x, rep^pair[1] ] ) ) then
 return rep;
 fi;
 od;
 od;
 return fail;
end );

#############################################################################
##
#F RelativeSigmaL( <d>, )
##
## Let <d> be a positive integer and a basis for a field extension
## of degree $n$, say, over the field $F$ with $q$ elements.
## `RelativeSigmaL' returns a group of $<d> n \times <d> n$ matrices
## over $F$, which is the intersection of $&SL;(<d> n, q)$ and the split
## extension of an extension field type subgroup isomorphic with
## $&GL;(<d>, q^n)$ by the Frobenius automorphism that maps each matrix
## entry to its $q$-th power.
##
## (If $q$ is a prime then the return value is isomorphic with the
## semilinear group $\SigmaL(<d>, q^n)$.)
##
RelativeSigmaL:= function( d, B )
 local n, F, q, glgens, diag, pi, frob, i;
 n:= Length( B );
 F:= LeftActingDomain( UnderlyingLeftModule( B ) );
 q:= Size( F );
 # Create the generating matrices inside the linear subgroup.
 glgens:= List( GeneratorsOfGroup( SL( d, q^n ) ),
 m -> BlownUpMat( B, m ) );
 # Create the matrix of a diagonal part that maps to determinant 1.
 diag:= IdentityMat( d*n, F );
 diag{ [ 1 .. n ] }{ [ 1 .. n ] }:= BlownUpMat( B, [ [ Z(q^n)^(q-1) ] ] );
 Add( glgens, diag );
 # Create the matrix that realizes the Frobenius action,
 # and adjust the determinant.
 pi:= List( B, b -> Coefficients( B, b^q ) );
 frob:= NullMat( d*n, d*n, F );
 for i in [ 0 .. d-1 ] do
 frob{ [ 1 .. n ] + i*n }{ [ 1 .. n ] + i*n }:= pi;
 od;
 diag:= IdentityMat( d*n, F );
 diag{ [ 1 .. n ] }{ [ 1 .. n ] }:= BlownUpMat( B, [ [ Z(q^n) ] ] );
 diag:= diag^LogFFE( Inverse( Determinant( frob ) ), Determinant( diag ) );
 # Return the result.
 return Group( Concatenation( glgens, [ diag * frob ] ) );
end;;

#############################################################################
##
#F ApproxPForSL( <d>, <q> )
##
## For a positive integer <d> and a prime power <q>,
## `ApproxPForSL' returns $[ &M;(G,s), &total;( G, s ) ]$,
## where $G = &PSL;( <d>, <q> )$, $s \in G$ is the image of a Singer cycle
## in $&SL;(d,q)$,
## and $&M;(G,s)$ is the list of names of those maximal subgroups of $G$
## that contain $s$.
##
ApproxPForSL:= function( d, q )
 local G, epi, PG, primes, maxes, names, ccl;
 # Check whether this is an admissible case (see [Be00]).
 if ( d = 2 and q in [ 2, 5, 7, 9 ] ) or ( d = 3 and q = 4 ) then
 return fail;
 fi;
 # Create the group SL(d,q), and the map to PSL(d,q).
 G:= SL( d, q );
 epi:= ActionHomomorphism( G, NormedRowVectors( GF(q)^d ), OnLines );
 PG:= ImagesSource( epi );
 # Create the subgroups corresponding to the prime divisors of `d'.
 primes:= PrimeDivisors( d );
 maxes:= List( primes, p -> RelativeSigmaL( d/p,
 Basis( AsField( GF(q), GF(q^p) ) ) ) );
 names:= List( primes, p -> Concatenation( "GL(", String( d/p ), ",",
 String( q^p ), ").", String( p ) ) );
 if 2 < q then
 names:= List( names, name -> Concatenation( name, " cap G" ) );
 fi;
 # Compute the conjugacy classes of prime order elements in the maxes.
 # (In order to avoid computing all conjugacy classes of these subgroups,
 # we work in Sylow subgroups.)
 ccl:= List( List( maxes, x -> ImagesSet( epi, x ) ),
 M -> ClassesOfPrimeOrder( M, PrimeDivisors( Size( M ) ),
 TrivialSubgroup( M ) ) );
 return [ names, UpperBoundFixedPointRatios( PG, ccl, true )[1] ];
end;;

#############################################################################
##
#F SymmetricBasis( <q>, <n> )
##
## For a positive integer <n> and a prime power <q>,
## `SymmetricBasis' returns a basis $B$ for the `GF(<q>)'-vector space
## `GF(<q>^<n>)' with the property that $`BlownUpMat'( B, x )$
## is symmetric for each element $x$ in `GF(<q>^<n>)'.
##
SymmetricBasis:= function( q, n )
 local vectors, B, issymmetric;
 if q = 2 and n = 2 then
 vectors:= [ Z(2)^0, Z(2^2) ];
 elif q = 2 and n = 3 then
 vectors:= [ Z(2)^0, Z(2^3), Z(2^3)^5 ];
 elif q = 2 and n = 5 then
 vectors:= [ Z(2)^0, Z(2^5), Z(2^5)^4, Z(2^5)^25, Z(2^5)^26 ];
 elif q = 3 and n = 2 then
 vectors:= [ Z(3)^0, Z(3^2) ];
 elif q = 3 and n = 3 then
 vectors:= [ Z(3)^0, Z(3^3)^2, Z(3^3)^7 ];
 elif q = 4 and n = 2 then
 vectors:= [ Z(2)^0, Z(2^4)^3 ];
 elif q = 4 and n = 3 then
 vectors:= [ Z(2)^0, Z(2^3), Z(2^3)^5 ];
 elif q = 5 and n = 2 then
 vectors:= [ Z(5)^0, Z(5^2)^2 ];
 elif q = 5 and n = 3 then
 vectors:= [ Z(5)^0, Z(5^3)^9, Z(5^3)^27 ];
 else
 Error( "sorry, no basis for <q> and <n> stored" );
 fi;
 B:= Basis( AsField( GF(q), GF(q^n) ), vectors );
 # Check that the basis really has the required property.
 issymmetric:= M -> M = TransposedMat( M );
 if not ForAll( B, b -> issymmetric( BlownUpMat( B, [ [ b ] ] ) ) ) then
 Error( "wrong basis!" );
 fi;
 # Return the result.
 return B;
end;;

#############################################################################
##
#F EmbeddedMatrix( <F>, <mat>, <func> )
##
## For a field <F>, a matrix <mat> and a function <func> that takes a matrix
## and returns a matrix of the same shape,
## `EmbeddedMatrix' returns a block diagonal matrix over the field <F>
## whose diagonal blocks are <mat> and `<func>( <mat> )'.
##
BindGlobal( "EmbeddedMatrix", function( F, mat, func )
 local d, result;
 d:= Length( mat );
 result:= NullMat( 2*d, 2*d, F );
 result{ [ 1 .. d ] }{ [ 1 .. d ] }:= mat;
 result{ [ d+1 .. 2*d ] }{ [ d+1 .. 2*d ] }:= func( mat );
 return result;
end );

#############################################################################
##
#F ApproxPForOuterClassesInExtensionOfSLByGraphAut( <d>, <q> )
##
## For a positive integer <d> and a prime power <q>,
## `ApproxPForOuterClassesInExtensionOfSLByGraphAut' returns
## $[ &M;(G,s), &total;^{\prime}( G, s ) ]$,
## where $G$ is $&PSL;( <d>, <q> )$ extended by a graph automorphism,
## $s \in G$ is the image of a Singer cycle in $&SL;(d,q)$,
## and $&M;(G,s)$ is the list of names of those maximal subgroups of
## $&PGL;( <d>, <q> )$ that contain $s$.
##
ApproxPForOuterClassesInExtensionOfSLByGraphAut:= function( d, q )
 local embedG, swap, G, orb, epi, PG, Gprime, primes, maxes, ccl, names;
 # Check whether this is an admissible case (see [Be00],
 # note that a graph automorphism exists only for `d > 2').
 if d = 2 or ( d = 3 and q = 4 ) then
 return fail;
 fi;
 # Provide a function that constructs a block diagonal matrix.
 embedG:= mat -> EmbeddedMatrix( GF( q ), mat,
 M -> TransposedMat( M^-1 ) );
 # Create the matrix that exchanges the two blocks.
 swap:= NullMat( 2*d, 2*d, GF(q) );
 swap{ [ 1 .. d ] }{ [ d+1 .. 2*d ] }:= IdentityMat( d, GF(q) );
 swap{ [ d+1 .. 2*d ] }{ [ 1 .. d ] }:= IdentityMat( d, GF(q) );
 # Create the group SL(d,q).2, and the map to the projective group.
 G:= ClosureGroupDefault( Group( List( GeneratorsOfGroup( SL( d, q ) ),
 embedG ) ),
 swap );
 orb:= Orbit( G, One( G )[1], OnLines );
 epi:= ActionHomomorphism( G, orb, OnLines );
 PG:= ImagesSource( epi );
 Gprime:= DerivedSubgroup( PG );
 # Create the subgroups corresponding to the prime divisors of `d'.
 primes:= PrimeDivisors( d );
 maxes:= List( primes,
 p -> ClosureGroupDefault( Group( List( GeneratorsOfGroup(
 RelativeSigmaL( d/p, SymmetricBasis( q, p ) ) ),
 embedG ) ),
 swap ) );
 # Compute conjugacy classes of outer involutions in the maxes.
 # (In order to avoid computing all conjugacy classes of these subgroups,
 # we work in the Sylow $2$ subgroups.)
 maxes:= List( maxes, M -> ImagesSet( epi, M ) );
 ccl:= List( maxes, M -> ClassesOfPrimeOrder( M, [ 2 ], Gprime ) );
 names:= List( primes, p -> Concatenation( "GL(", String( d/p ), ",",
 String( q^p ), ").", String( p ) ) );
 return [ names, UpperBoundFixedPointRatios( PG, ccl, true )[1] ];
end;;

#############################################################################
##
#F RelativeGammaL( <d>, )
##
## Let the arguments be as for `RelativeSigmaL'.
## Then `RelativeGammaL' returns the extension field type subgroup of
## $&GL;(d,q)$ that corresponds to the subgroup of $&SL;(d,q)$ returned by
## `RelativeSigmaL'.
##
RelativeGammaL:= function( d, B )
 local n, F, q, diag;
 n:= Length( B );
 F:= LeftActingDomain( UnderlyingLeftModule( B ) );
 q:= Size( F );
 diag:= IdentityMat( d * n, F );
 diag{[ 1 .. n ]}{[ 1 .. n ]}:= BlownUpMat( B, [ [ Z(q^n) ] ] );
 return ClosureGroup( RelativeSigmaL( d, B ), diag );
end;;

#############################################################################
##
#F ApproxPForOuterClassesInGL( <d>, <q> )
##
## Let the arguments be as for `ApproxPForSL'.
## Then `ApproxPForOuterClassesInGL' returns the list of names of the
## extension field type subgroups of $&GL;(<d>,<q>)$,
## and $&total;^{\prime}(&GL;(<d>,<q>),s)$,
## for a Singer cycle $s \in &SL;(d,q)$.
##
ApproxPForOuterClassesInGL:= function( d, q )
 local G, epi, PG, Gprime, primes, maxes, names;
 # Check whether this is an admissible case (see [Be00]).
 if ( d = 2 and q in [ 2, 5, 7, 9 ] ) or ( d = 3 and q = 4 ) then
 return fail;
 fi;
 # Create the group GL(d,q), and the map to PGL(d,q).
 G:= GL( d, q );
 epi:= ActionHomomorphism( G, NormedRowVectors( GF(q)^d ), OnLines );
 PG:= ImagesSource( epi );
 Gprime:= ImagesSet( epi, SL( d, q ) );
 # Create the subgroups corresponding to the prime divisors of `d'.
 primes:= PrimeDivisors( d );
 maxes:= List( primes, p -> RelativeGammaL( d/p,
 Basis( AsField( GF(q), GF(q^p) ) ) ) );
 maxes:= List( maxes, M -> ImagesSet( epi, M ) );
 names:= List( primes, p -> Concatenation( "M(", String( d/p ), ",",
 String( q^p ), ")" ) );
 return [ names,
 UpperBoundFixedPointRatios( PG, List( maxes,
 M -> ClassesOfPrimeOrder( M,
 PrimeDivisors( Index( PG, Gprime ) ), Gprime ) ),
 true )[1] ];
end;;

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

Quelle probgen.g Sprache: unbekannt

[ Dauer der Verarbeitung: 0.35 Sekunden (vorverarbeitet) ]