|
#############################################################################
##
#W stdgen.gi GAP library Thomas Breuer
##
#Y (C) 1999 School Math and Comp. Sci., University of St. Andrews, Scotland
##
## This file contains the implementations needed for dealing with standard
## generators of finite groups.
##
#############################################################################
##
#F HumanReadableDefinition( <info> )
##
InstallGlobalFunction( HumanReadableDefinition, function( info )
local nrgens,
alpha,
lalpha,
generators,
i,
m,
gensstring,
nraux,
auxnames,
description,
script,
len,
line,
word,
pos,
str,
j,
strline,
linelen;
# Check the argument.
if not ( IsRecord( info ) and IsBound( info.script ) ) then
Error( "<info> must be a record with a component `script'" );
elif not IsBound( info.description ) then
# Get names of the standard generators.
alpha:= [ "a","b","c","d","e","f","g","h","i","j","k","l","m",
"n","o","p","q","r","s","t","u","v","w","x","y","z" ];
lalpha:= Length( alpha );
if not IsBound( info.generators ) then
nrgens:= Number( info.script,
line -> Length( line ) <= 3 and IsInt( line[2] ) );
generators:= [];
for i in [ 1 .. nrgens ] do
if i <= lalpha then
generators[i]:= alpha[i];
else
m:= (i-1) mod lalpha + 1;
generators[i]:= Concatenation( alpha[m],
String( ( i - m ) / lalpha ) );
fi;
od;
gensstring:= "";
for i in generators do
Append( gensstring, i );
Append( gensstring, ", " );
od;
Unbind( gensstring[ Length( gensstring ) ] );
Unbind( gensstring[ Length( gensstring ) ] );
info.generators:= gensstring;
else
gensstring:= info.generators;
generators:= SplitString( gensstring, ",", " " );
nrgens:= Length( generators );
fi;
# Get the names of auxiliary generators needed.
nraux:= Number( info.script,
line -> Length( line ) = 3 and IsInt( line[2] ) );
if nrgens + nraux <= lalpha then
auxnames:= alpha{ [ lalpha-nraux+1 .. lalpha ] };
if not IsEmpty( Intersection( generators, auxnames ) ) then
auxnames:= List( [ 1 .. nraux ],
i -> Concatenation( "X", String(i) ) );
fi;
else
auxnames:= List( [ 1 .. nraux ],
i -> Concatenation( "X", String(i) ) );
fi;
nraux:= 1;
# Initialize the result string.
description:= "";
# Scan the script linearly.
script:= info.script;
len:= Length( script );
for i in [ 1 .. len ] do
line:= script[i];
if IsList( line[2] ) and IsString( line[2][1] ) then
# condition line.
word:= "";
linelen:= Length( line[1] );
for j in [ 1, 3 .. linelen-1 ] do
Append( word, generators[ line[1][j] ] );
if line[1][ j+1 ] = 2 then
Append( word, generators[ line[1][j] ] );
elif line[1][ j+1 ] <> 1 then
Add( word, '^' );
Append( word, String( line[1][ j+1 ] ) );
fi;
od;
str:= ShallowCopy( line[2] );
for j in [ 1 .. Length( str ) ] do
if not IsBound( str[j] ) then
str[j]:= word;
fi;
od;
strline:= Concatenation( str );
Add( strline, '=' );
Append( strline, String( line[3] ) );
elif Length( line ) = 2 then
# definition line
strline:= Concatenation( "|", generators[ line[1] ], "|=",
String( line[2] ) );
elif Length( line ) = 3 and IsInt( line[2] ) then
# definition line involving an auxiliary name
strline:= Concatenation( "|", auxnames[ nraux ], "|=",
String( line[2] ), ", ", auxnames[ nraux ],
"^", String( line[3] ), "=", generators[ line[1] ] );
nraux:= nraux+1;
else
# relation line
linelen:= Length( line );
if linelen = 3 then
strline:= Concatenation( "|",
StringOfResultOfStraightLineProgram( line[2],
generators{ line[1] } ),
"|=", String( line[3] ) );
else
strline:= "|";
for j in [ 1, 3 .. linelen-2 ] do
Append( strline, generators[ line[j] ] );
if line[ j+1 ] = 2 then
Append( strline, generators[ line[j] ] );
elif line[ j+1 ] <> 1 then
Add( strline, '^' );
Append( strline, String( line[ j+1 ] ) );
fi;
od;
Append( strline, "|=" );
Append( strline, String( line[ linelen ] ) );
fi;
fi;
Append( description, strline );
if i < len then
Append( description, ", " );
fi;
od;
# Store the value.
info.description:= description;
fi;
# Return the result.
return info.description;
end );
#############################################################################
##
#F ScriptFromString( <string> )
##
InstallGlobalFunction( ScriptFromString, function( string )
local gensnames,
gensorder,
lines,
nrlines,
k,
line,
pos,
int,
aux,
len,
pos2,
script,
nrgens,
i,
found,
list,
init,
initlen,
linelen,
scr,
try,
j,
word;
gensnames:= [];
gensorder:= [];
lines:= SplitString( string, ",", " " );
nrlines:= Length( lines );
# Loop over the lines.
script:= [];
nrgens:= 0;
k:= 1;
while k <= nrlines do
line:= lines[k];
# The names of the standard generators occur in lines
# starting not with `|' or lines containing neither `(' nor `^',
# and having a letter at position $2$ and a non-letter at position $3$.
if line[1] = '|' and IsAlphaChar( line[2] )
and not IsAlphaChar( line[3] )
and not ( '(' in line or '^' in line ) then
# This entry belongs to a definition
# (perhaps of an auxiliary element) via order.
pos:= Position( line, '|', 1 );
if pos = fail or line[ pos+1 ] <> '=' then
return fail;
fi;
Add( gensnames, line{ [ 2 .. pos-1 ] } );
int:= Int( line{ [ pos+2 .. Length( line ) ] } );
if int = fail then
return fail;
fi;
Add( gensorder, int );
len:= Length( gensnames );
nrgens:= nrgens + 1;
# Check whether this was an auxiliary element,
# and the next line (if there is one)
# defines a generator relative to this one.
if k < nrlines and lines[ k+1 ][1] <> '|'
and not '(' in lines[ k+1 ] then
# This line belongs to a definition via a power.
k:= k+1;
line:= lines[k];
pos:= Position( line, '^' );
if pos = fail then
return fail;
fi;
aux:= line{ [ 1 .. pos-1 ] };
if gensnames[ len ] <> aux then
return fail;
fi;
pos2:= Position( line, '=' );
int:= Int( line{ [ pos+1 .. pos2-1 ] } );
if int = fail then
return fail;
fi;
gensnames[ len ]:= line{ [ pos2+1 .. Length( line ) ] };
# Add the definition to the script.
Add( script, [ nrgens, gensorder[ len ], int ] );
else
# Add the definition to the script.
Add( script, [ nrgens, gensorder[ len ] ] );
fi;
else
pos:= Position( line, '=' );
if pos = fail then
return fail;
fi;
int:= Int( line{ [ pos+1 .. Length( line ) ] } );
if int = fail then
return fail;
fi;
# Check whether the line matches the first part of a function string.
found:= false;
for i in [ 1, 3 .. Length( StandardGeneratorsFunctions )-1 ] do
list:= StandardGeneratorsFunctions[ i+1 ];
init:= list[1];
initlen:= Length( init );
if init[ initlen ] <> '(' then
Error( "symbol <list> must enclose arguments in ( and )" );
elif init = line{ [ 1 .. initlen ] } then
# Find the word in question, and check it.
pos2:= initlen + 1;
linelen:= Length( line );
while pos2 <= linelen and not line[ pos2 ] in "()" do
pos2:= pos2 + 1;
od;
if pos2 <= linelen and line[ pos2 ] <> '(' then
word:= line{ [ initlen+1 .. pos2-1 ] };
try:= ShallowCopy( list );
for j in [ 1 .. Length( list ) ] do
if not IsBound( try[j] ) then
try[j]:= word;
fi;
od;
try:= Concatenation( try );
if try = line{ [ 1 .. pos-1 ] } then
scr:= [];
found:= StringToStraightLineProgram( word, gensnames, scr );
if found then
Add( script, [ scr[1][1], list, int ] );
fi;
fi;
fi;
if found then
break;
fi;
fi;
od;
if not found then
# Check for a relation.
if line[1] <> '|' then
return fail;
fi;
pos:= Position( line, '=' );
if pos = fail then
return fail;
fi;
if line[ pos-1 ] <> '|' then
return fail;
fi;
int:= Int( line{ [ pos+1 .. Length( line ) ] } );
if int = fail then
return fail;
fi;
word:= [];
if not StringToStraightLineProgram( line{ [ 2 .. pos-2 ] },
gensnames, word ) then
return fail;
fi;
# Create a straight line program if brackets were found.
if Length( word ) = 1 then
word:= word[1][1];
Add( word, int );
Add( script, word );
else
Add( script, [ [ 1 .. Length( gensnames ) ],
StraightLineProgram( word, Length( gensnames ) ),
int ] );
fi;
fi;
fi;
k:= k+1;
od;
# Return the result;
return script;
end );
#############################################################################
##
#V StandardGeneratorsFunctions
##
CentralizerOrder := function( G, g ) return Size( Centralizer( G, g ) ); end;
Append( StandardGeneratorsFunctions, [ CentralizerOrder, [ "|C(",,")|" ] ] );
#############################################################################
##
#F IsStandardGeneratorsOfGroup( <info>, <G>, <gens> )
##
InstallGlobalFunction( IsStandardGeneratorsOfGroup, function( info, G, gens )
local script,
i,
line,
g,
next,
linelen,
j;
# Initialize, and start the loop.
script:= info.script;
for i in [ 1 .. Length( script ) ] do
Info( InfoGroup, 3,
"StandardGenerators: inspecting line ", i );
line:= script[i];
if IsList( line[2] ) and IsString( line[2][1] ) then
# condition line.
# First compute the element to be checked.
if IsEmpty( line[1] ) then
g:= One( G );
elif not IsBound( gens[ line[1][1] ] ) then
return false;
else
g:= gens[ line[1][1] ];
if line[1][2] <> 1 then
g:= g ^ line[1][2];
fi;
for j in [ 3, 5 .. Length( line[1] ) - 1 ] do
if not IsBound( gens[ line[1][j] ] ) then
return false;
fi;
next:= gens[ line[1][j] ];
if line[1][ j+1 ] <> 1 then
next:= next ^ line[1][ j+1 ];
fi;
g:= g * next;
od;
fi;
# Next compute the value under the function, and compare.
if StandardGeneratorsFunctions[ Position(
StandardGeneratorsFunctions, line[2] ) - 1 ]( G,
g ) <> line[3] then
return false;
fi;
elif Length( line ) <= 3 and IsInt( line[2] ) then
# definition line
if not IsBound( gens[ line[1] ] )
or ( Length( line ) = 2 and Order( gens[ line[1] ] ) <> line[2] )
or ( Length( line ) = 3 and Order( gens[ line[1] ] )
<> line[2] / Gcd( line[2], line[3] ) ) then
return false;
fi;
else
# relation line
linelen:= Length( line );
if linelen = 3 then
if Order( ResultOfStraightLineProgram( line[2], gens{ line[1] } ) )
<> line[3] then
return false;
fi;
else
g:= gens[ line[1] ]^line[2];
for j in [ 3, 5 .. linelen-2 ] do
next:= gens[ line[j] ];
if line[ j+1 ] <> 1 then
next:= next^line[ j+1 ];
fi;
g:= g * next;
od;
if Order( g ) <> line[ linelen ] then
return false;
fi;
fi;
fi;
od;
# All conditions are satisfied.
return true;
end );
#############################################################################
##
#F StandardGeneratorsOfGroup( <info>, <G>[, <randfunc>] )
##
InstallGlobalFunction( StandardGeneratorsOfGroup, function( arg )
local info,
G,
randfunc,
gens,
script,
len,
i,
line,
g,
next,
linelen,
j;
# Get and check the arguments.
if Length( arg ) = 2 and IsRecord( arg[1] ) and IsGroup( arg[2] ) then
info := arg[1];
G := arg[2];
randfunc := PseudoRandom;
elif Length( arg ) = 3 and IsRecord( arg[1] ) and IsGroup( arg[2] )
and IsFunction( arg[3] ) then
info := arg[1];
G := arg[2];
randfunc := arg[3];
else
Error( "usage: StandardGenerators( <info>, <G>[, <randfunc>] )" );
fi;
# Initialize, and start the loop.
if not IsBound( info.script ) then
if not IsBound( info.description ) then
Error( "need at least a component `script' or `description'" );
else
info.script:= ScriptFromString( info.description );
fi;
fi;
script:= info.script;
len:= Length( script );
i:= 1;
gens:= [];
while i <= len do
Info( InfoGroup, 3,
"StandardGenerators: inspecting line ", i );
line:= script[i];
if IsList( line[2] ) and IsString( line[2][1] ) then
# condition line.
# First compute the element to be checked.
if IsEmpty( line[1] ) then
g:= One( G );
elif not IsBound( gens[ line[1][1] ] ) then
Error( "definition of ", Ordinal( line[1][1] ),
" generator missing before line ", i );
else
g:= gens[ line[1][1] ];
if line[1][2] <> 1 then
g:= g ^ line[1][2];
fi;
for j in [ 3, 5 .. Length( line[1] ) - 1 ] do
if not IsBound( gens[ line[1][j] ] ) then
Error( "definition of ", Ordinal( line[1][j] ),
" generator missing before line ", i );
fi;
next:= gens[ line[1][j] ];
if line[1][ j+1 ] <> 1 then
next:= next ^ line[1][ j+1 ];
fi;
g:= g * next;
od;
fi;
# Next compute the value under the function, and compare.
if StandardGeneratorsFunctions[ Position(
StandardGeneratorsFunctions, line[2] ) - 1 ]( G,
g ) <> line[3] then
gens:= [];
i:= 0;
fi;
elif Length( line ) <= 3 and IsInt( line[2] ) then
# definition line
if IsBound( gens[ line[1] ] ) then
Error( Ordinal( line[1] ),
" generator defined a second time in line ", i );
fi;
repeat
g:= randfunc( G );
until Order( g ) = line[2];
if IsBound( line[3] ) and line[3] <> 1 then
g:= g^line[3];
fi;
gens[ line[1] ]:= g;
else
# relation line
linelen:= Length( line );
if linelen = 3 then
g:= ResultOfStraightLineProgram( line[2], gens{ line[1] } );
else
g:= gens[ line[1] ]^line[2];
for j in [ 3, 5 .. linelen-2 ] do
g:= g * gens[ line[j] ]^line[ j+1 ];
od;
fi;
if Order( g ) <> line[ linelen ] then
gens:= [];
i:= 0;
fi;
fi;
# Inspect the next line.
i:= i + 1;
od;
# Return the result.
return gens;
end );
#############################################################################
##
#E
[ Dauer der Verarbeitung: 0.5 Sekunden
(vorverarbeitet)
]
|
