Quelle fpf.gi Sprache: unbekannt

##
## AUXILIARY FUNCTIONS FOR DETERMINING FPF REPRESENTATIONS
##

 Maxfactor := function( m, prime )

## returns the maximal power of prime dividing m

 local q;

 q := prime;
 while m mod q = 0 do
 q := q*prime;
 od;
 return q/prime;
 end;

 Cofactor := function( m, n )

## returns the maximal integer mprime dividing m and coprime to n
## if each prime divisor of n divides m, otherwise 0 is returned

 local mprime, prime, q;

 if n = 1 then
 return m;
 fi;

 mprime := m;
 for prime in Set( FactorsInt( n ) ) do
 q := Maxfactor( m, prime );
 if q = 1 then
## undefined, m and r are not feasible for our purpose
return 0;
 fi;
 mprime := mprime/q;
 od;

 return mprime;
 end;

 MatrixInt := function( matrix )
 return List( matrix, x -> List( x, Int ) );
 end;

#############################################################################
##
 BlockDiagonalMatrix := function( blocks )
##
## note: as in the case of BlockMatrix( arg ) all the blocks must have
## the same dimensions rpb, cpb

 return BlockMatrix(
List( [1..Length( blocks )], x -> [x, x, blocks[x]] ),
Length( blocks ), Length( blocks ) );
 end;

#############################################################################
##
 SolutionDiophant := function( a, b, c )
##
## gives one solution (x, y) of the diophant equation a*x+b*y = c
## if existing
##

 local coeff, d, l;

 coeff := GcdRepresentation( a, b );
 d := a*coeff[1]+b*coeff[2];

 if c mod d <> 0 then
 return fail;
 fi;

 return QuoInt( c, d )*coeff;
 end;

#############################################################################
##
 SolutionMatMod := function ( mat, vec, p )
##
## returns one solution <x> of <mat>*<x> = <vec> or `fail' over the
## ring ZmodnZ(p) with a prime power
##
## this function is an adaption of the GAP-function
## SolutionMat (SolutionMatNoCo) avoiding inversion
##

 local h, v, i, l, r, s, c, zero, root,
 A, b, d, m, n, found, done, indices, minindex, q, qnow, res,
 x, t, temp;

 # solve <mat>*x = <vec>.
 vec := ShallowCopy( vec );
 A := MatrixInt( mat );
 b := List( vec, Int );
 m := Length( mat );
 n := Length( mat[1] );
 d := 0; r := 0; c := 0;
 zero := Zero( mat[1][1] );
 root := SmallestRootInt( p );
 q := root;
 indices := [1..m];
 Info( InfoNearRing, 1, "SolutionMatMod called" );

 done := false;
 while d < n and not done do
## run through all columns of the matrix to search for minimal pivot-element
 c := d;
 qnow := p; found := false;
 while not found and c < n do
 c := c+1; r := d;
 while not found and r < m do
 r := r+1;
 if A[r][c] mod q <> 0 then
 found := true;
 minindex := [r,c]; qnow := QuoInt( q, root );
 elif A[r][c] mod qnow <> 0 then
 minindex := [r,c];
 qnow := Gcd( A[r][c], qnow );
 fi;
 od;
 od;

 if qnow = p then
## all the subsequent entries of mat are zero
done := true;
 else
## put this column in the appropriate position
 d := d+1;
 r := minindex[1]; c := minindex[2];
 temp := indices[c];
 indices[c] := indices[d];
 indices[d] := temp;
 for i in [1..m] do
 temp := A[i][c];
 A[i][c] := A[i][d];
 A[i][d] := temp;
 od;

## normalize this row and clear this column

 q := qnow;

#if Gcd( A[r][d], p ) <> q then
# return false;
#fi;
 t := SolutionDiophant( A[r][d], p, q )[1];
 l := List( A[r], x -> t*x mod p );
Info( InfoNearRing, 3, "l = ", l );
 temp := t*b[r] mod p;
 A[r] := A[d]; b[r] := b[d];
 A[d] := l; b[d] := temp;

 for i in [d+1..m] do
#if A[i][d] mod q <> 0 then
# return false;
#fi;
 t := QuoInt( A[i][d], q );
 A[i] := (A[i]-t*l) mod p; b[i] := (b[i]-t*b[d]) mod p;
 od;
 fi;
 od; ## while d < n and not done do

 Info( InfoNearRing, 2, "rowreduced matrix = ", A );
 Info( InfoNearRing, 2, "vector = ", b );

## now find a solution

 temp := [];
 for i in [1..d] do
 if b[i] mod A[i][i] <> 0 then return fail; fi;
 od;
 for i in [d+1..m] do
 if b[i] mod p <> 0 then return fail; fi;
 temp[i] := 0;
 od;

 i := d-1;
 temp[d] := QuoInt( b[d], A[d][d] );
 while i > 0 do
 temp[i] := QuoInt( b[i]-A[i]{[i+1..d]}*temp{[i+1..d]}, A[i][i] );
 i := i-1;
 od;

 res := [];
 for i in [1..n] do
 res[indices[i]] := temp[i];
 od;

 Info( InfoNearRing, 2, "mat * x = vec solved by x^t = ", res );
 Info( InfoNearRing, 1, "SolutionMatMod returns" );
 return res*One( mat[1][1] );
end;

#############################################################################
##
 GroupHomomorphismByMatrix := function( G, gens, mats )
##
## for an abelian group G with generators gens this function returns
## GroupHomomorphismByImages( G, G, gens, imgs )
## where imgs is described by mats (the coefficients of images with respect
## to gens)
## e.g., for G elementary abelian with "basis" gens and mats = [A]
## this would simply return the homomorphism x -> x*A
##
 local d, n,
 imgs,
 i, j, x;

 imgs := []; d := 0;
 for i in [1..Length( mats )] do
n := Length( mats[i] );
for j in [1..n] do
## add the image of the (d+j)-th generator:
 Add( imgs,
 Product( List( [1..n], x -> gens[d+x]^Int(mats[i][j][x]) ) ) );
od;
d := d+n;
 od;

 return GroupHomomorphismByImages( G, G, gens, imgs );
 end;

##
## FPF BASICS
##

############################################################################
##
#M IsFpfAutomorphismGroup( <phi>, <G> )
##
## - tests whether <phi> acts fpf on <G> by converting <phi> to a
## permutation group
##

InstallMethod(
IsFpfAutomorphismGroup,
"default",
true,
[IsGroup, IsGroup],
0,
 function( phi, G )

 local k, n, O;

 k := Size( phi );
 n := Size( G );
 if n mod k <> 1 then
 return false;
 fi;

 O := SortedList( G );
 RemoveSet( O, Identity( G ) );

 return IsSemiRegular( phi, O );
 end );

############################################################################
##
#M FpfAutomorphismGroupsMaxSize( <G> )
##
## - returns an upper bound for the maximal size of a fixed point free
## automorphism group on <G>
## - tests whether a fixed point free automorphism group on <G> has to be
## necessarily cyclic
## - uses only the size of <G>
##

InstallMethod(
FpfAutomorphismGroupsMaxSize,
"default",
true,
[IsGroup],
0,
 function( G )

 local primesandexp, # list of primes and exponents [[p1,d1],...[pn,dn]]
 # such that Size(G) = p1^d1*...pn^dn
kmax, # maximum possible size of an fpf aut grp on <G>
dmax, # maximum possible size of a factor in a noncyclic
 # fpf aut grp on <G>, see presentations
 # dmax = 1 means that all fpf aut grps are cyclic
factors, f, x;

 if not IsNilpotentGroup( G ) then
 return [1,1];
 fi;

 primesandexp := Collected( Factors( Size( G ) ) );

 if IsCyclic( G ) then
return [Gcd( List( primesandexp, x -> x[1]-1 ) ), 1];
 fi;

 kmax := Gcd( List( primesandexp, x -> x[1]^x[2]-1 ) );

 if not IsAbelian( G ) then
## <kmax> is certainly odd
 while IsEvenInt( kmax ) do
 kmax := kmax/2;
 od;
 fi;

 dmax := Gcd( List( primesandexp, x -> x[2] ) );
 dmax := Gcd( [dmax, kmax, Phi(kmax)] );
 factors := Collected( Factors( dmax ) );
 for f in factors do
## pq-condition
 if kmax mod f[1]^(f[2]+1) <> 0 then
 dmax := dmax/f[1];
fi;
 od;
 return [kmax,dmax];
 end );

##
## functions returning the degree of irreducible fpf representations over
## GF(p) for solvable groups as described in
##
## PM: Fpf representations over fields of prime characteristic. Technical
## Report
##
## NOTE: no checking whether the input-parameters are feasible
##

############################################################################
##
 DegreeOfIrredFpfRepCyclic := function( p, m )
## error if p and m are not coprime
 return OrderMod( p, m );
 end;

############################################################################
##
 DegreeOfIrredFpfRepMetacyclic := function( p, m, r )
##
 local n, q, mprime;

## check the necessary conditions whether the input-parameters are feasible:
 n := OrderMod( r, m );
 if n = 0 then
 Error( "parameters are not feasible: <m> and <r> coprime" );
 fi;

 q := Maxfactor( m, 2 );
 if q > 2 and (r+1) mod q = 0 and n mod 4 = 2 then
## type II, quaternion 2-Sylow subgroup
 mprime := Cofactor( m/2, n/2 );
 if mprime = 0 or r mod (m/mprime) <> 1 then
Error( "parameters are not feasible" );
 fi;
 Info( InfoNearRing, 1,
 "parameters are feasible; metacyclic group of type II" );
 else
## type I, all Sylow subgroups are cyclic
 mprime := Cofactor( m, n );
 if mprime = 0 or r mod (m/mprime) <> 1 then
Error( "parameters are not feasible" );
 fi;
 Info( InfoNearRing, 1,
 "parameters are feasible; metacyclic group of type I" );
 fi;

 return Size( GroupByPrimeResidues( [p,r], m ) );

 end;

############################################################################
##
 DegreeOfIrredFpfRep2 := function( p, m, r, k )
##
## necessary conditions:
## all prime divisors of n := OrderMod( r, m ) divide m
## n/2 is an odd number
## not k in GroupByPrimeResidues( [r], m )
## k = -1 mod Maxfactor( m, 2 )
## OrderMod( k, m ) = 2


 local n, q, mprime;

## check the necessary conditions whether the input-parameters are feasible:
 n := OrderMod( r, m );
 q := Maxfactor( m, 2 );
 mprime := Cofactor( m, n );
 if n mod 4 <> 2 then
 Error( "parameters are not feasible: <m> and <r> coprime" );
 elif q = 1 then
 Error( "parameters are not feasible: <m> is even" );
# elif q > 1 and (r+1) mod q = 0 then
# Error( "parameters are not feasible: 4 divides <r>-1" );
 elif mprime = 0 or r mod (m/mprime) <> 1 then
 Error( "parameters are not feasible: pq-condition" );
 elif OrderMod( k, m ) <> 2 or (k+1) mod q <> 0 or
 ( m <> mprime*q and k mod (m/(mprime*q)) <> 1 ) then
 Error( "parameters are not feasible: pq-condition" );
 fi;

 return Size( GroupByPrimeResidues( [p,r,k], m ) );
 end;

############################################################################
##
 DegreeOfIrredFpfRep3 := function( p, m, r )
##
## necessary conditions:
## 3 divides m,
## m is odd
## all prime divisors of n := OrderMod( r, m ) divide m

 local n, mprime;

 n := OrderMod( r, m );
 if n = 0 then
 Error( "parameters are not feasible: <m> and <r> coprime" );
 fi;

 mprime := Cofactor( m, n );
 if m mod 2 = 0 or m mod 3 <> 0 or mprime = 0 or
 (n > 1 and r mod (m/mprime) <> 1) then
 Error( "parameters are not feasible" );
 elif m mod 9 <> 0 and n mod 3 <> 0 then
## return 2*DegreeOfIrredFpfRepMetacyclic( p, m/3, r );
 return 2*Size( GroupByPrimeResidues( [p, r], m/3 ) );
 else
## return 2*DegreeOfIrredFpfRepMetacyclic( p, m, r );
 return 2*Size( GroupByPrimeResidues( [p, r], m ) );
 fi;
 end;

############################################################################
##
 DegreeOfIrredFpfRep4 := function( p, m, r, k )
##
## necessary conditions:
## m is odd
## all prime divisors of n := OrderMod( r, m ) divide m
## in particular n is odd
## 3 divides m, but 3 does not divide n
## OrderMod( k, m ) = 2
## k = -1 mod 3
## k = 1 mod prime divisors of n

 local n, mprime;

 n := OrderMod( r, m );
 if n = 0 then
 Error( "parameters are not feasible: <m> and <r> coprime" );
 fi;

 mprime := Cofactor( m, n );
 if m mod 2 = 0 or mprime mod 3 <> 0 or mprime = 0 or
 (n > 1 and r mod (m/mprime) <> 1) then
 Error( "parameters are not feasible: 3" );
 elif OrderMod( k, m ) <> 2 or (k+1) mod 3 <> 0 or
 (n > 1 and k mod (m/mprime) <> 1) then
 Error( "parameters are not feasible: 4" );
 elif m mod 9 <> 0 and p^2 mod 16 = 1 then
 return 2*Size( GroupByPrimeResidues( [p,r,k], m/3 ) );
 elif m mod 9 <> 0 then
 return Lcm( 4, 2*Size( GroupByPrimeResidues( [p,r,k], m/3 ) ) );
 else
 return 2*Size( GroupByPrimeResidues( [p,r,k], m ) );
 fi;
 end;

##
## DETERMINING THE REPRESENTATIONS OVER GF(P)
##

############################################################################
##
#M IsFpfRepresentation( <matrices>, <F> )
##
## - tests whether the group of d times d matrices in the list <matrices>
## over F acts fpf by multiplication on the d-dimensional vector space
## (module) over F
## - converts <phi> to a permutation group acting on the row vectors F^d from
## the right (GAP-convention, x -> x*A)
##

InstallMethod(
IsFpfRepresentation,
"default",
true,
[IsList, IsDomain],
0,
 function( matrices, F )

 local d, # degree of the matrix representation
phi, # matrix group generated by <matrices> over F
 n,
 o,
 I,
 l;

 d := Length( matrices[1] );
 phi := Group( matrices*One(F) );
 n := Size( F )^d;

 if n mod Size( phi ) <> 1 then
 return false;
 fi;

 o := Zero(F);
 I := IdentityMat( d, F );
 l := SortedList( phi );
 RemoveSet( l, I );

 return ForAll( l, x -> Determinant( x-I ) <> o );
 end );

############################################################################
##
 FGRepC := function( p, f, m )
##
## returns a matrix <AR> representing an fpf automorphism of order m over
## the ring R = ZmodnZ( p^f ) with p a prime
## <AR> acts from the right, x -> x*AR
##

 local e, F, gens, a, A, AR, R,
i, x, y;

 e := OrderMod( p, m );
 if e = 0 then
 Error( "size of the group, m, and characteristic, p, have to be coprime" );
 fi;
 F := GF( p^e );
 gens := Basis( F );
 a := Z(p^e)^((p^e-1)/m);
 A := List( gens, x -> Coefficients( gens, a*x ) );

 if f = 1 then
 return A;
 fi;

## the representation over GF(p) determines a representation over ZmodnZ( p^f )
 R := ZmodnZ( p^f );
 AR := MatrixInt( A )*One( R );
 AR := AR^(p^(f-1));
## now AR has order m over R, but AR is not necessarily congruent to A mod p
 return AR;
 end;

############################################################################
##
#M FpfRepresentationsCyclic( , <size> )
##
## determines the irreducible fixed point free representations of a cyclic
## group of order <size> over ZmodnZ( p )
##
## returns a list of matrices { A^i | i in indexlist }
## such that each matrix A^i operates from the right on a ZmodnZ(p)-module
## thus determining a representation.
## The A^i describe all irred. representation up to equivalence.
## additionally <indexlist> is returned.
##

InstallMethod(
FpfRepresentationsCyclic,
"default",
true,
[IsInt, IsInt],
0,
 function( p, size )

 local A, # matrix (i.e., representation of the generator
 # of the cyclic group of order <size> )
 # linear map: x -> x*A
CmodsizeCstar, # multiplicative group of residues prime to <size>
U,
indexlist, # A^i for i in <indexlist> form all the irreducible
 # nonequivalent representations
prime, f,
x;

 prime := SmallestRootInt( p );
 f := LogInt( p, prime );


 if size mod prime = 0 then
 Error( "size of group and characteristic of field have to be coprime" );
 elif size = 1 then
 return [[[[One( ZmodnZ( p ) )]]], [1]];
 elif size = 2 then
 return [[[[-One( ZmodnZ( p ) )]]], [1]];
 fi;

 A := FGRepC( prime, f, size );
 CmodsizeCstar := Units( Integers mod size );
 U := GroupByPrimeResidues( [prime], size );
 indexlist := List( RightCosets( CmodsizeCstar, U ),
 x -> Int( Representative(x) ) );

 return [List( indexlist, x -> A^x ), indexlist];
 end );

############################################################################
##
 FGRepQ := function( prime, f )
##
## returns matrices P, Q representing an fpf quaternion group over Z(prime^f)
## this irreducible fpf representation is unique (upto equivalence)
## note that p has to be an odd prime
##

 local P, Q,
u, v, p,
x;

 p := prime^f;
 u := 0; v := 0;
## find the solution by trial and error:
 while (u^2+v^2+1) mod p <> 0 and u 0 and v < p do
 v := v+1;
od;
 od;

 P := [[u,v],[v,-u]];
 Q := [[0,-1],[1,0]];

 return [P,Q]*One( ZmodnZ( p ) );
 end;

############################################################################
##
 FGRepMC := function( p, f, m, mprime, d )
##
## returns matrices AR, WR^u, BR representing a metacyclic fpf automorphism
## group over the ring R = ZmodnZ( p^f ) with p a prime such that
## m ... order of AR
## d ... (BR*WR^u)^-1*AR*(BR*WR^u) = AR^(p^d)
## WR is induced by x -> x*w and w is primitive in GF(p^e)
## additionally, with n = e/gcd(e,d) and q = p^d:
## (BR*WR^u)^n = (WR^u)^[1+p^d+p^2d+...+p^(n-1)d]
## = (WR^u)^[1+q+q^2+...+q^(n-1)]
## = (WR^u)^[(q^n-1)/(q-1)]
## = AR^mprime
##

 local e, # degree of irred. representation of C_m over GF(p)
n, # n = e/gcd(e,d)
q, # q = p^d
u,
F, gens,
w, W, WR,
a, A, AR, B, BR, R, ARq, XR, M, y, I,
i, j, x;

 e := OrderMod( p, m );
 if e = 0 then
 Error( "size of group and characteristic of field have to be coprime" );
 fi;
 n := e/Gcd(e,d);

## now: beta^n = alpha^mprime
## m/mprime divides q-1

 q := p^d;
 if q mod (m/mprime) <> 1 then
 Error( "parameters not feasible: m/mprime has to divide q-1" );
 fi;

 F := GF( p^e );
 w := Z(p^e);
 gens := Basis( F );
 W := List( gens, x -> Coefficients( gens, x*w ) );
 B := List( gens, x -> Coefficients( gens, x^q ) );

## u is determined by (WR^u)^[(q^n-1)/(q-1)] = AR^mprime
 u := ((p^(e/n)-1)*mprime)/m;
## for an integer i coprime to m: (W^i)^((p^e-1)/m) and
## B*(W^i)^u together form the irred representations

 if f = 1 then
 return [W^((p^e-1)/m), W^u, B];
 fi;

## the representation over GF(p) determines a representation over ZmodnZ( p^f )
 R := ZmodnZ( p^f );
 WR := (MatrixInt( W )*One( R ))^(p^(f-1));
## now WR has order relatively prime to p over R
## but WR is not necessarily congruent to W mod p

 AR := WR^((p^e-1)/m);
 BR := MatrixInt( B )*One( R );
## BR does not necessarily normalize the group generated by AR
 ARq := AR^q;
 y := Flat( AR*BR-BR*ARq );
 I := IdentityMat( e )*One( R );
 M := KroneckerProduct( I, TransposedMat( ARq ))-KroneckerProduct( AR, I );
 x := SolutionMatMod( M, y, p^f );

 if x = fail then
 return fail;
 fi;

 XR := List( [1..e], i -> x{[(i-1)*e+1..i*e]} );
## Now (BR+XR)^-1*AR*(BR+XR) = AR^q but (BR+XR) has not yet order n.
## Let j be minimal such that j*e > f. Then (BR+XR)^(p^(j*e)) has order n
## and maps AR to AR^q by conjugation.
 BR := (BR+XR)^( p^((QuoInt(f-1, e)+1)*e) );

 return [AR, WR^u, BR];
 end;

############################################################################
##
#M FpfRepresentationsMetacyclic( , <m>, <r> )
##
## determines the fixed point free representations of a metacyclic group
## with generators a, b and relations a^m = 1, b^n = a^mprime,
## b^(-1)*a*b = a^r where n is the multiplicative order of r in the group
## of prime residues modulo m.
## Additional conditions are: mprime divides m
## each prime divisor of n divides m/mprime and
## r = 1 mod (m/mprime)
##
## returns a list of pairs of matrices corresponding to a and b
## which operate from the right on a ZmodnZ(p)-module
## additionally a list <indexlist> of indices is returned
##

InstallMethod(
FpfRepresentationsMetacyclic,
"quaternion group",
true,
[IsInt, IsInt, IsInt],
10,
 function( p, m, r )

 local prime, f;

 if m <> 4 then
 TryNextMethod();
 fi;
 prime := SmallestRootInt( p );
 f := LogInt( p, prime );
 return [[FGRepQ( prime, f )], [1]];
 end );

InstallMethod(
FpfRepresentationsMetacyclic,
"default",
true,
[IsInt, IsInt, IsInt],
0,
 function( p, m, r )

 local A, B, C, I, # auxiliary matrices (blocks) for the representations
AA, BB, # matrices (representations of the generators of the
 # metacyclic group of determined by the
 # parameters <m> and <r> )
 # linear maps, a: x -> x*AA
 # b: x -> x*BB
fpfreps, # list of matrices [AA, BB] determining the
 # nonequivalent representations
indexlist, # AA^i, BB(i) for i in <indexlist> form all the
 # nonequivalent representations
CmodmCstar, # multiplicative group of residues prime to <m>
e, t, q, d,
Ubyrandprime, # subgroup of CmodmCstar generated by r and prime
n, # size of Ubyr
 mprime,
factors, aux, subdiagonal, prime, f,
i, x;

 prime := SmallestRootInt( p );
 f := LogInt( p, prime );
 e := OrderMod( prime, m );
## e is the degree of an irreducible fpf representation of <a> over GF(prime)
 if e = 0 then
 Error( "size of group and characteristic of field have to be coprime" );
 fi;

## check the necessary conditions whether the input-parameters are feasible:
 r := r mod m;
 n := OrderMod( r, m );
 if n = 0 then
 Error( "parameters are not feasible: <m> and <r> coprime" );
 elif n = 1 then
 Error( "parameters of a cyclic group of size <m>" );
 fi;

 q := Maxfactor( m, 2 );
 if q > 2 and (r+1) mod q = 0 and n mod 4 = 2 then
## type II, quaternion 2-Sylow subgroup
 mprime := Cofactor( m/2, n/2 );
 if mprime = 0 or r mod (m/mprime) <> 1 then
Error( "parameters are not feasible" );
 fi;
 Info( InfoNearRing, 1, "parameters are feasible; metacyclic group of type II" );
 else
## type I, all Sylow subgroups are cyclic
 mprime := Cofactor( m, n );
 if mprime = 0 or r mod (m/mprime) <> 1 then
Error( "parameters are not feasible" );
 fi;
 Info( InfoNearRing, 1, "parameters are feasible; metacyclic group of type I" );
 fi;

 Ubyrandprime := GroupByPrimeResidues( [r, prime], m );
 t := Size( Ubyrandprime )/e;
## r^t is congruent to a power of prime modulo m

 if n = t then
## prime^x = r^t mod m implies that x = e
 A := FGRepC( prime, f, m );
 C := A^mprime;
 B := IdentityMat( Length( A ), ZmodnZ(p) );
 else
 q := r^t mod m;
 d := LogMod( q, prime, m );
 aux := FGRepMC( prime, f, m, mprime, d );
 A := aux[1]; C := aux[2]; B := aux[3];
 fi;

 CmodmCstar := Units( Integers mod m );
 indexlist := List( RightCosets( CmodmCstar, Ubyrandprime ), x ->
 Int( Representative(x) ) );

 I := IdentityMat( Length( A ), ZmodnZ( p ) );
 subdiagonal := List( [1..t-1], x -> [x+1, x, I] );

 fpfreps := [];
 for i in indexlist do
 AA := BlockDiagonalMatrix( List( [0..t-1], x -> A^(i*r^x) ) );
 BB := BlockMatrix( Concatenation( subdiagonal, [[1, t, B*C^i]] ), t, t );
 Add( fpfreps, [AA,BB] );
 od;

 return [fpfreps, indexlist];
 end );

############################################################################
##
 FGRep2 := function( p, f, m, mprime, d, l )
##
## returns matrices AR, WR^u, BR = DR^2, WR^v, QR = DR^n representing an fpf
## automorphism group of type 2 over the ring R = ZmodnZ(p^f) such that
## m ... order of AR with AR a power of WR
## d ... (BR*WR^u)^-1*AR*(BR*WR^u) = AR^(p^d)
## WR is induced by x -> x*w and w is primitive in GF(p^e)
## Note that d has to be even and n = e/gcd(e,d) odd; d <> 0 but possibly
## d = e.
## DR is induced by x -> x^(p^(d/2))
## Then B = D^2 and Q = D^n commute and with q = p^d:
## (BR*WR^u)^n = (WR^u)^[1+p^d+p^2d+...+p^(n-1)d]
## = (WR^u)^[1+q+q^2+...+q^(n-1)]
## = (WR^u)^[(q^n-1)/(q-1)]
## = AR^mprime
## e ... (QR*WR^v)^-1*AR*(QR*WR^v) = AR^(p^(e/2))
## l ... (QR*WR^v)^-1*(BR*WR^u)*(QR*WR^v) = (BR*WR^u)^l
##

 local e, # degree of irred. representation of C_m over GF(p)
n, # n = e/gcd(e,d)
q, # q = p^d
u, v, k,
F, gens,
w, W, WR, D, DR,
a, A, AR, R, ARq, ARk, XR, M, y, I,
i, j, x;

 e := OrderMod( p, m );

 if e = 0 or e mod 2 <> 0 then
 Error( "parameters not feasible: e has to be even" );
 fi;

 n := e/Gcd( e, d );

## now: beta^n = alpha^mprime
## m/mprime divides q-1

 k := p^(e/2);
 q := p^d;
 Info( InfoNearRing, 3, " p^d = ", q );
 if q mod (m/mprime) <> 1 then
 Error( "parameters not feasible: m/mprime divides q-1" );
 fi;

## u is determined by (WR^u)^[(q^n-1)/(q-1)] = AR^mprime
## same as in FGRepMC( p, f, m, mprime, d) with possibly q = p^e
 u := ((p^(e/n)-1)*mprime)/m;
 if n = 1 then
## v is determined by ( Q*W^[v*(p^(e/2)-1)/2] )^2 = -I, that is, for example
 v := 1;
 else
## v has to be determined from the equality q^-1*beta*q = beta^l
 v := SolutionDiophant( (q-1)*(k-1)/2, p^e-1, u*(k-(q^l-1)/(q-1)) );
 if v = fail then
 Error( "parameters not feasible" );
 fi;
 v := v[1];
 fi;

 F := GF( p^e );
 w := Z(p^e);
 gens := Basis( F );
 W := List( gens, x -> Coefficients( gens, w*x ) );
 D := List( gens, x -> Coefficients( gens, x^(p^(d/2)) ) );

## for an integer i coprime to m the irred representations are formed by:
## (W^i)^QuoInt( p^e-1, m )
## D^2*W^(iu)
## D^n*(W^iv)^[(p^(e/2)-1)/2]
 if f = 1 then
 return [W^QuoInt( p^e-1, m ), W^u, D^2, W^(v*((k-1)/2)), D^n];
 fi;

## the representation over GF(p) determines a representation over ZmodnZ( p^f )
 R := ZmodnZ( p^f );
 WR := (MatrixInt( W )*One( R ))^(p^(f-1));
## now WR has order relatively prime to p over R
## but WR is not necessarily congruent to W mod p
 AR := WR^QuoInt( p^e-1, m );
 DR := MatrixInt( D )*One( R );
 ARq := AR^(p^(d/2));
 y := Flat( AR*DR-DR*ARq );
 I := IdentityMat( e )*One( R );
 M := KroneckerProduct( I, TransposedMat(ARq) )-KroneckerProduct( AR, I );
 x := SolutionMatMod( M, y, p^f );
 XR := List( [1..e], i -> x{[(i-1)*e+1..i*e]} );
## Now (DR+XR)^-1*AR*(DR+XR) = AR^(p^(d/2)) but (DR+XR) has not yet order 2n.
## Let j be minimal such that j*e > f. Then (DR+XR)^(p^(j*e)) has order 2n
## (important: 2n divides p^e-1) and maps AR to AR^(p^(d/2)) by conjugation.
 DR := (DR+XR)^( p^((QuoInt(f-1, e)+1)*e) );

 return [AR, WR^u, DR^2, WR^(v*(k-1)/2), DR^n];
 end;

############################################################################
##
#M FpfRepresentations2( , <m>, <r>, <k> )
##
## determines the fixed point free representations of a group of type 2
## that is, with generators a, b, q
## and relations a^m = 1, b^n = a^mprime, q^2 = a^(m/2)
## b^(-1)*a*b = a^r where n is the multiplicative order of r in the group of
## prime residues modulo m
## q^(-1)*a*q = a^k, q^(-1)*b*q = b^l and k has order 2 in the group of prime
## residues modulo m
## l is determined by: l = -1 mod 2s and l = 1 mod (nm)/(2s*mprime) where
## s is the maximal power of 2 dividing m
## Additional conditions are: mprime divides m
## each prime divisor of n divides m/mprime
## r = 1 mod (m/mprime)
## m is even, n is 2 times an odd number
## k = -1 mod 4
## k = l mod (m/mprime)
## k <> r^(n/2) mod m
## thus: <a,b,q>/<a> is isomorphic to C_2 x C_n not cyclic
##
## if k = p^(e/2)*r^(n/2) mod m, then a different presentation for the
## same group with k = p^(e/2) mod m is chosen to compute the representations
## more efficiently
##
## returns a list of triples of matrices corresponding to a, b and q
## which operate from the right on a ZmodnZ(p)-module
## additionally a list <indexlist> of indices is returned
##

InstallMethod(
FpfRepresentations2,
"default",
true,
[IsInt, IsInt, IsInt, IsInt],
0,
 function( p, m, r, k )

 local CmodmCstar, # group of prime residues mod <m>
e, # multiplicative order of mod <m>
n, # multiplicative order of <r> mod <m>
Ubyrandprime, t, # subgroup of the group of prime residues mod
 # <m> generated by <r,prime>
indexlist_ab, fpfreps_ab, # representations of <a,b>
Ubykpr, # subgroup of the group of prime residues mod
 # <m> generated by <k,prime,r>
conjugates, # elements of Ubykpr
 # sublist of indexlist_ab desbcribing the
 # representations of <a,b> that are conjugate
 # to another list of reps
indexlist, fpfreps, # result, representations of <a,b,q>
A, B, Q, I, # auxiliary matrices (blocks) for the
C, S, # representation
AA, BB, QQ, # matrices (representations of the generators
 # of the group of type II determined by the
 # parameters m, r and k
 # linear maps a: x -> x*AA
 # b: x -> x*BB
 # q: x -> x*QQ
kchanged, # <true> if k = r^(n/2)*p^(e/2) mod m;
 # then for computational reasons k = p^(e/2)
mprime, l, s,
q, d, prime, f,
factors, auxiliary, inv, subdiagonal, M,
i, x;

 prime := SmallestRootInt( p );
 f := LogInt( p, prime );
 r := r mod m;
 k := k mod m;
 n := OrderMod( r, m );
 s := Maxfactor( m, 2 );
 mprime := Cofactor( m, n );
## determine <l>:
 l := ChineseRem( [(n*m)/(2*s*mprime), 2*s], [1,-1] );

 if n mod 4 <> 2 then
 Error( "parameters are not feasible: <m> and <r> coprime" );
 elif s = 1 then
 Error( "parameters are not feasible: <m> is even" );
# elif s > 2 and (r+1) mod s = 0 then
# Error( "parameters are not feasible: 4 divides <r>-1" );
 elif mprime = 0 or r mod (m/mprime) <> 1 then
 Error( "parameters are not feasible: pq-condition" );
 elif k = r^(n/2) mod m then
 Error( "parameters are not feasible: k = r^(n/2) mod m, metacyclic" );
 elif OrderMod( k, m ) <> 2 or (k-l) mod (m/mprime) <> 0 then
 Error( "parameters are not feasible: k = l mod (m/mprime)" );
 fi;


 indexlist := []; fpfreps := [];
 Ubyrandprime := GroupByPrimeResidues( [r, prime], m );
 conjugates := List( Ubyrandprime, Int );

 if not k in conjugates then
## The irreducible fpf representations of <a,b,q> are induced by the
## irreducible fpf representations of the metacyclic group <a,b>.
## Note: one rep of <a,b,q> is induced by 2 nonequivalent reps of <a,b>
 Info( InfoNearRing, 1, "GF(", prime,
 ")-representations of the type-II-group are induced" );
 auxiliary := FpfRepresentationsMetacyclic( p, m, r );
 fpfreps_ab := auxiliary[1];
 indexlist_ab := auxiliary[2];
## the degrees of the reps of <a,b> are Length( fpfreps_ab[1][1] )
 I := IdentityMat( Length( fpfreps_ab[1][1] ), ZmodnZ(p) );
 QQ := BlockMatrix( [[2, 1, I], [1, 2, -I]], 2, 2 );
 for i in [1..Length( indexlist_ab )] do
inv := SolutionDiophant( indexlist_ab[i], m, 1 )[1];
if not ForAny( indexlist, x -> (x*k*inv) mod m in conjugates ) then
## the induction of the conjugate representation gives again the same
## and is therefore omitted
 A := fpfreps_ab[i][1];
 B := fpfreps_ab[i][2];
 AA := BlockDiagonalMatrix( [A, A^k] );
 BB := BlockDiagonalMatrix( [B, B^l] );

 Add( indexlist, indexlist_ab[i] );
 Add( fpfreps, [AA,BB,QQ] );
fi;
 od;

 return [fpfreps, indexlist];
 fi;

 Info( InfoNearRing, 1, "GF(", prime,
 ")-representations of the type-II-group are not induced" );

 e := OrderMod( prime, m );
## either k = p^(e/2) mod m or k = r^(n/2)*p^(e/2) mod m
## in any case e is even

 kchanged := false;
 if k = (r^(n/2)*prime^(e/2)) mod m then
## intermediate change of the presentation for computational convenience
 k := prime^QuoInt( e, 2 ) mod m;
 kchanged := true;
 Info( InfoNearRing, 3, "intermediate change of presentation, k = ", k );
 fi;

## for the rest of this function we may assume that k = prime^(e/2) mod m
## but the returned representations are for the initial value of k

 t := QuoInt( Size( Ubyrandprime ), e );
## r^t is congruent to a power of prime modulo m
 q := r^t mod m;
 if q = 1 then
 d := e;
 else
 d := LogMod( q, prime, m );
 fi;

 auxiliary := FGRep2( prime, f, m, mprime, d, l );
 A := auxiliary[1]; C := auxiliary[2]; B := auxiliary[3];
 S := auxiliary[4]; Q := auxiliary[5];
 I := IdentityMat( Length( A ), ZmodnZ(p) );

 CmodmCstar := Units( Integers mod m );
 indexlist := List( RightCosets( CmodmCstar, Ubyrandprime ), x ->
 Int( Representative(x) ) );
 subdiagonal := List( [1..t-1], x -> [x+1, x, I] );
 M := ((l-1)/n)*mprime*prime^(e/2);
 fpfreps := [];
 for i in indexlist do
 AA := BlockDiagonalMatrix( List( [0..t-1], x -> A^(i*r^x) ) );
 BB := BlockMatrix( Concatenation( subdiagonal, [[1, t, C^i*B]] ), t, t );
 QQ := BlockDiagonalMatrix( List( [0..t-1], x -> S^i*Q*A^(M*(t-1-x) ) ) );

 if kchanged then
## the conjugation of AA by BB^(m*n/(mprime*2*s))*QQ yields AA^(r^(n/2)*p^(e/2)
 Add( fpfreps, [AA,BB,BB^(m*n/(mprime*2*s))*QQ] );
 else
 Add( fpfreps, [AA,BB,QQ] );
 fi;
 od;

 return [fpfreps, indexlist];
 end);

############################################################################
##
 FGRepT := function( prime, f )
##
## returns matrices P, Q, R representing an fpf tetrahedral group, SL(2,3),
## over Z(prime^f)
## this irreducible fpf representation is unique (upto equivalence)
## note that prime has to be a prime distinct from 2 and 3
##

 local P, Q, R,
u, v, p,
x;

 p := prime^f;
 u := 0; v := 0;
 while (u^2+v^2+1) mod p <> 0 and u 0 and v < p do
 v := v+1;
od;
 od;

 P := [[u,v],[v,-u]];
 Q := [[0,-1],[1,0]];
## (p+1)/2 represents 1/2 in ZmodnZ( p )
 R := (p+1)/2*[[-1+u+v,-1-u+v],[1-u+v,-1-u-v]];

 return [P, Q, R]*One( ZmodnZ( p ) );
 end;

############################################################################
##
#M FpfRepresentations3( , <m>, <r> )
##
## determines the fixed point free representations of a group of type 3
## that is, with generators p, q, a, b
## and relations a^m = 1, b^n = a^mprime
## b^(-1)*a*b = a^r where n is the multiplicative order of r in the group of
## prime residues modulo m
## p and q generate the quaternion group of size 8
## if 3 divides n, then a commutes with p,q and
## b^(-1)*p*b = q, b^(-1)*q*b = pq
## if 3 does not divide n, then b commutes with p,q and
## a^(-1)*p*a = q, a^(-1)*q*a = pq
##
## m and r have to fulfill the following conditions:
## 3 divides m; m is odd; m and r are coprime.
## Let n be the mult. order of r mod m. Then each prime divisor of n
## divides m.
## Let m' be maximal such that m' divides m and m' is coprime to n. Then
## r = 1 \mod (m/m').
##
## returns a list of lists of matrices corresponding to p, q, a and b
## (or if r = 1 a list of triples of matrices corresponding to p, q and a)
## which operate from the right on a ZmodnZ(p)-module
## additionally a list <indexlist> of indices is returned as for metacyclic
## or cyclic groups
##

InstallMethod(
FpfRepresentations3,
"SL(2,3)",
true,
[IsInt, IsInt, IsInt],
10,
 function( p, m, r )

 local prime, f;

 if m <> 3 or r mod m <> 1 then
 TryNextMethod();
 fi;
 prime := SmallestRootInt( p );
 f := LogInt( p, prime );
 return [[FGRepT( prime, f )], [1]];
 end );

InstallMethod(
FpfRepresentations3,
"default",
true,
[IsInt, IsInt, IsInt],
0,
 function( p, m, r )

 local CmodmCstar, # group of prime residues mod <m>
n, # multiplicative order of <r> modulo <m>
P, Q, R, # matrix representation of the binary tetrahedral
 # group of size 24
fpfreps_ab, # representations of <a,b>
A, AandB, # auxiliary matrices
PP, QQ, AA, BB, # matrices (representations of the generators
 # of the type III group determined by the
 # parameters <m> and <r> )
 # linear maps, a: x -> x*AA
 # b: x -> x*BB
fpfreps, # list of matrices [PP, QQ, AA, BB]
 # determining the nonequivalent representations
indexlist, # AA^i, BB(i) for i in <indexlist> form all the
 # nonequivalent representations of <p,q,a,b>
prime, f,
t, mprime,
auxiliary, I, I2,
x;

 prime := SmallestRootInt( p );
 f := LogInt( p, prime );
 r := r mod m;
 n := OrderMod( r, m );
 mprime := Cofactor( m, n );

 if n = 0 then
 Error( "parameters are not feasible: <m> and <r> coprime" );
 elif prime = 2 or prime = 3 then
Error( "field characteristic has to be coprime to 6" );
 elif m mod 2 = 0 or m mod 3 <> 0 or mprime = 0 or
 (n > 1 and r mod (m/mprime) <> 1) then
Error( "parameters are not feasible" );
 fi;

 auxiliary := FGRepT( prime, f );
 if m = 3 then
 return [auxiliary,[1]];
 fi;
 P := auxiliary[1]; Q := auxiliary[2]; R := auxiliary[3];

 fpfreps := [];
 if n = 1 then
## that is, if <a,b> is cyclic
if m mod 9 = 0 then
 auxiliary := FpfRepresentationsCyclic( p, m );
else
 auxiliary := FpfRepresentationsCyclic( p, m/3 );
 fi;
fpfreps_ab := auxiliary[1];
indexlist := auxiliary[2];
I := IdentityMat( Length( fpfreps_ab[1] ), ZmodnZ(p) );
PP := KroneckerProduct( I, P );
QQ := KroneckerProduct( I, Q );
for A in fpfreps_ab do
 AA := KroneckerProduct( A, R );
 Add( fpfreps, [PP,QQ,AA] );
od;
return [fpfreps, indexlist];
 fi;

## <a,b> is not cyclic

 if n mod 3 = 0 or m mod 9 = 0 then
auxiliary := FpfRepresentationsMetacyclic( p, m, r );
 else
auxiliary := FpfRepresentationsMetacyclic( p, m/3, r );
 fi;
 fpfreps_ab := auxiliary[1];
 indexlist := auxiliary[2];
 I := IdentityMat( Length( fpfreps_ab[1][1] ), ZmodnZ(p) );
 PP := KroneckerProduct( I, P );
 QQ := KroneckerProduct( I, Q );
 I2 := IdentityMat( 2, ZmodnZ(p) );

 if n mod 3 = 0 then
for AandB in fpfreps_ab do
 AA := KroneckerProduct( AandB[1], I2 );
 BB := KroneckerProduct( AandB[2], R );
 Add( fpfreps, [PP,QQ,AA,BB] );
od;
 elif m mod 9 = 0 then
for AandB in fpfreps_ab do
 AA := KroneckerProduct( AandB[1], R );
 BB := KroneckerProduct( AandB[2], I2 );
 Add( fpfreps, [PP,QQ,AA,BB] );
od;
 else
# Note: if 9 does not divide m, then we still want AA^mprime = BB^n,
# and not AA^mprime = BB^(3*n). Thus:
 t := SolutionDiophant( 3, m/3, 1)[1];
 for AandB in fpfreps_ab do
 AA := KroneckerProduct( AandB[1]^t, R );
 BB := KroneckerProduct( AandB[2], I2 );
 Add( fpfreps, [PP,QQ,AA,BB] );
od;
 fi;

 return [fpfreps, indexlist];
 end );

############################################################################
##
 FGRepO := function( prime, f )
##
## returns matrices P, Q, R, Z representing an fpf binary octahedral group
## of order 48 over ZmodnZ(prime^f)
## note that prime has to be a prime distinct from 2 and 3
##

 local P, Q, R, Z, I,
u, v, one, c, p,
x;

 p := prime^f;
 u := 0; v := 0;
 while (u^2+v^2+1) mod p <> 0 and u 0 and v < p do
 v := v+1;
od;
 od;

 P := [[u,v],[v,-u]];
 Q := [[0,-1],[1,0]];
 R := [[-1+u+v,-1-u+v],[1-u+v,-1-u-v]]*((p+1)/2);
 Z := [[u-v,u+v],[u+v,-u+v]];

 if prime^2 mod 16 = 1 then
## x^2-2 splits over GF(p), c^2 = 1/2
## In this case we obtain 2 non-equivalent irreducible fpf representations of
## degree 2.
 c := RootMod( (p+1)/2, p );
 return [[P, Q, R, c*Z], [P, Q, R, -c*Z]]*One( ZmodnZ (p) );
 else
## x^2-2 does not split over GF(p)
## In this case we obtain one unique (upto equivalence) irreducible fpf
## representation of degree 4, which is induced from the unique irreducible fpf
## representation of the binary tetrahedral group, <p,q,r>.
I := [[1,0],[0,1]];
return [[BlockDiagonalMatrix( [P, Q*P] ),
 BlockDiagonalMatrix( [Q, -Q] ),
 BlockDiagonalMatrix( [R, R^2] ),
 BlockMatrix( [[2,1,I], [1,2,-I]], 2, 2 )]*One( ZmodnZ (p) )];
 fi;
 end;

############################################################################
##
 FGRep4C := function( p, f, m )
##
## returns matrices AR, CR such that
## AR^m = 1,
## CR^(-1)*AR*CR = AR^(p^(e/2)),
## CR^2 = 1/2
## for the representation of an fpf type-IV-group over R = ZmodnZ(p^f)
## cases c,d) with cyclic complement of the quaternion group in H
##
## note that p has to be a prime distinct from 2 and 3
##

 local e, # degree of irred. representation of C_m over GF(p)
k, # k = p^(e/2)
l, # logarithm of 1/2 for the base w
gens, w,
x;

 if f > 1 then
 Error( "Sorry, these ZmodnZ(p^f)-reps are not yet implemented" );
 fi;

 e := OrderMod( p, m );
 k := p^(e/2);
 w := Z(p^e);
 gens := Basis( GF( p^e ) );
 l := -LogFFE( 2*Z(p)^0, w );
## thus w^l = 1/2
 return [List( gens, x -> Coefficients( gens, x*w^((p^e-1)/m) ) ),
 List( gens, x -> Coefficients( gens, x^k*w^(l/(k+1)) ) )];
 end;

############################################################################
##
 FGRep4 := function( p, f, m, mprime, d )
##
## returns matrices A, Wu, B, Ws, C such that
## A^m = 1,
## (B*Wu)^(-1)*A*(B*Wu) = A^(p^d), (B*Wu)^n = A^mprime,
## (C*Ws)^(-1)*A*(C*Ws) = A^(p^(e/2)), (B*Wu)*(C*Ws) = (C*Ws)*(B*Wu)
## (C*Ws)^2 = 1/2*I
## for the representation of an fpf type-IV-group over R = ZmodnZ(p^f)
## cases c,d) with non-cyclic complement of the quaternion group in H
##
## note that p has to be a prime distinct from 2 and 3
##

 local e, # degree of irred. representation of C_m over GF(p)
n, # n = e/gcd(e,d)
q, # q = p^d
k, # k = p^(e/2)
l, # logarithm of 1/2 for the base w
u, v, r, s,
F, gens, w,
W, B, C, I,
x;

 if f > 1 then
 Error( "Sorry, these ZmodnZ(p^f)-reps are not yet implemented" );
 fi;

 e := OrderMod( p, m );
 n := e/Gcd( e, d );

## now: beta^n = alpha^mprime
## m/mprime divides q-1

 k := p^(e/2);
 q := p^d;
 F := GF( p^e );
 w := Z(p^e);
 gens := Basis( F );

 W := List( gens, x -> Coefficients( gens, w*x ) );
 C := List( gens, x -> Coefficients( gens, x^k ) );

 l := -LogFFE( 2*Z(p)^0, w );
## thus w^l = 1/2
 v := l/(k+1);

 if n = 1 then
 u := ((p^e-1)*mprime)/m;
 I := IdentityMat(e)*One(F);
 return [W^((p^e-1)/m), W^u, I, I, C*W^v];
 fi;

 B := List( gens, x -> Coefficients( gens, x^q ) );
## u is determined by (WR^u)^[(q^n-1)/(q-1)] = AR^mprime
## same as in FGRepMC( p, f, m, mprime, d)
 u := ((p^(e/n)-1)*mprime)/m;
## v is determined by (C*W^v)^2 = 1/2*I and (B*W^u)*(C*W^v) = (C*W^v)*(B*W^u)
 r := SolutionDiophant( q-1, k+1, -(v*(q-1))/(k-1) )[1];
 s := SolutionDiophant( q-1, k+1, u )[1];

 B := List( gens, x -> Coefficients( gens, x^q ) );

 return [W^((p^e-1)/m), W^u, B, W^((k-1)*s), C*W^(v+(k-1)*r)];
 end;

############################################################################
##
 FGRepSQHalf := function( p, f, e )
##
## returns an e times e matrix C over ZmodnZ(p^f) such that C^2 = 1/2*I
## e is even and 16 does not divide p^2-1
##

 local w, gens,
 n, c, half, C,
x, i;

 if f > 1 then
## This case poses a problem:
## C has to commute with the representation-matrices, A and B, of the
## metacyclic complement for the quaternion group in H.
## To guarantee this, we would have to compute C together with A and B.
 Error( "Sorry, these ZmodnZ(p^f)-reps are not yet implemented" );
 fi;

 w := Z(p^e);
 gens := Basis( GF(p^e) );

 c := w^(-LogFFE( 2*Z(p)^0, w )/2);
 C := List( gens, x -> Coefficients( gens, x*c ) );
 return C;
 end;

############################################################################
##
#M FpfRepresentations4( , <m>, <r>, <k> )
##
## determines the fixed point free representations of a group of type 4
## that is, with generators p, q, a, b, z
## and relations a^m = 1, b^n = a^mprime,
## b^(-1)*a*b = a^r where n is the multiplicative order of r in the group of
## prime residues modulo m
## p and q generate the quaternion group of size 8
## b commutes with p,q and a^(-1)*p*a = q, a^(-1)*q*a = p*q
##
## Hence, p, q, a, b generate a group of type 3, determined by m and r.
##
## z^2 = p^2, z^(-1)*p*z = q*p, z^(-1)*q*z = q^(-1), z^(-1)*a*z = a^k and
## z commutes with b
##
## m, r and k have to fulfill the following conditions:
## 3 divides m but 3 does not divide n; m is odd; m and r are coprime.
## Let n be the mult. order of r mod m. Then each prime divisor of n
## divides m.
## Let m' be maximal such that m' divides m and m' is coprime to n. Then
## r = 1 \mod (m/m').
## k = -1 mod 3^s where s is maximal such that 3^s divides m
## k = 1 mod (m/mprime) and k^2 = 1 mod m
##
## returns a list of lists of matrices corresponding to p, q, a, b, z
## (or if r = 1 a list of lists of matrices corresponding to p, q, a and z)
## which operate from the right on a ZmodnZ(p)-module
## additionally a list <indexlist> of indices is returned
##

InstallMethod(
FpfRepresentations4,
"m = 3",
true,
[IsInt, IsInt, IsInt, IsInt],
50,
 function( p, m, r, k )

 local prime, f,
fpfreps;

 if m <> 3 then
 TryNextMethod();
 fi;

 prime := SmallestRootInt( p );
 f := LogInt( p, prime );

 if prime = 2 or prime = 3 then
 Error( "field characteristic has to be coprime to 6" );
 elif r mod 3 <> 1 or k mod 3 <> 2 then
 Error( "parameters are not feasible" );
 fi;

 fpfreps := FGRepO( prime, f );
 if Length( fpfreps ) = 1 then
## case b)
 Info( InfoNearRing, 1, "induced representation from SL(2,3)" );
 return [fpfreps, [1]];
 else
## case a)
 Info( InfoNearRing, 1,
 "exception (a): representations as direct products" );
 return [fpfreps, [[1,1],[-1,1]]];
 fi;
end );

InstallMethod(
FpfRepresentations4,
"case a",
true,
[IsInt, IsInt, IsInt, IsInt],
40,
 function( p, m, r, k )

 local P, Q, # fpf representation of the quaternion group over
quaternion, # ZmodnZ(p)
fpfreps_H, # fpf representations of H over ZmodnZ(p)
indexlist_H,
c, Z2, ZZ,
fpfreps, # list of matrices [PP,QQ,AA,BB,ZZ] (resp. for r = 1
 # [PP,QQ,AA,ZZ]) determining
 # the nonequivalent representations
indexlist,
n, # mult. order of r modulo m
auxiliary,
prime, f,
mprime,
 x;

## checking the necessary conditions on the input parameters m, r, k:
 prime := SmallestRootInt( p );
 n := OrderMod( r, m );
 mprime := Cofactor( m, n );

 if prime = 2 or prime = 3 then
 Error( "field characteristic has to be coprime to 6" );
 elif m mod 2 = 0 or n mod 3 = 0 or mprime = 0 or
 (n > 1 and r mod (m/mprime) <> 1) then
 Error( "parameters are not feasible: 3 divides m; pq-condition" );
 elif OrderMod( k, m ) <> 2 or (k+1) mod 3 <> 0 or
 (n > 1 and k mod (m/mprime) <> 1) then
 Error( "parameters are not feasible: k has order 2" );
 fi;

 if not( m mod 9 <> 0 and (k mod (m/3) = 1 or m = 3) and
 prime^2 mod 16 = 1 ) then
 TryNextMethod();
 fi;
##
## exception (a): 2 is a square in GF(prime)
##
 Info( InfoNearRing, 1,
 "exception (a): representations as direct products" );

 auxiliary := FpfRepresentations3( p, m, r );
 fpfreps_H := auxiliary[1];
 indexlist_H := auxiliary[2];
 P := fpfreps_H[1][1]; Q := fpfreps_H[1][2];
 Z2 := P-P*Q;
 c := RootMod( (p+1)/2, p );
 ZZ := c*Z2;
## Each irred representation of H can be extended to two non-equivalent
## irred representations of <p,q,a,b,z> of the same degree by adding
## ZZ resp. -ZZ
 fpfreps := Concatenation( List( fpfreps_H, x ->
 [Concatenation( x, [ZZ] ), Concatenation( x, [-ZZ] )] ) );
 indexlist := Concatenation( List( indexlist_H, x -> [[1,x],[-1,x]] ) );

 return [fpfreps, indexlist];
end );

InstallMethod(
FpfRepresentations4,
"case b",
true,
[IsInt, IsInt, IsInt, IsInt],
30,
 function( p, m, r, k )

 local P, Q, # fpf representation of the quaternion group over
quaternion, # ZmodnZ(p)
fpfreps_H, # fpf representations of H over ZmodnZ(p)
indexlist_H,
C, Z2, ZZ,
e, auxiliary, t,
prime, f,
 x;

 prime := SmallestRootInt( p );
 e := OrderMod( p, m/3 );

 if not (m mod 9 <> 0 and (k mod (m/3) = 1 or m = 3) and e mod 2 = 0) then
 TryNextMethod();
 fi;
##
## exception (b): determine a 2 times 2 matrix C induced by scalar
## multiplication in GF(prime^2) such that C^2 = 1/2 I2
##
 Info( InfoNearRing, 1, "exception (b): extending type-III representations" );
 auxiliary := FpfRepresentations3( p, m, r );
 fpfreps_H := auxiliary[1];
 indexlist_H := auxiliary[2];

 f := LogInt( p, prime );
 quaternion := FGRepQ( p, f );
 P := quaternion[1]; Q := quaternion[2];
 Z2 := P-P*Q;
## Note: For f > 1 there is a problem:
## C has to commute with the representation-matrices, A and B, of the
## metacyclic complement for the quaternion group in H.
## To guarantee this, we would have to compute C together with A and B.
 t := Size( GroupByPrimeResidues( [p,r], m/3 ) )/e;
 C := FGRepSQHalf( prime, f, e );
 ZZ := BlockDiagonalMatrix( List( [1..t], x ->
 KroneckerProduct( C, Z2 ) ) );

## each irred representation of H can be extended to an irred rep of
## <p,q,a,b,z> of the same degree by adding ZZ

 return [List( fpfreps_H, x -> Concatenation( x, [ZZ] ) ), indexlist_H];
end );

InstallMethod(
FpfRepresentations4,
"cases c,d",
true,
[IsInt, IsInt, IsInt, IsInt],
20,
 function( p, m, r, k )

 local P, Q, R, # representation of the binary tetrahedral group of
tetrahedral, # size 24
fpfreps, # fpf representations of H over ZmodnZ(p)
indexlist,
CmodmCstar, # group of prime residues modulo m (resp. m/3 if
 # m mod 9 <> 0 )
Ubykpr,
A, B, C, Wu, Ws, I,
Z2, I2, subdiagonal,
PP, QQ, AA, BB, ZZ,
n, mprime,
e, t, auxiliary,
prime, f,
q, d,
 x, i;

 prime := SmallestRootInt( p );
 if m mod 9 = 0 then
 e := OrderMod( prime, m );
 if not( e mod 2 = 0 and (k-prime^(e/2)) mod m = 0 ) then
 TryNextMethod();
 fi;
## exceptional case d)
 Info( InfoNearRing, 1, "exception (d): extending type-III representations" );
 n := OrderMod( r, m );
 mprime := Cofactor( m, n );
 else ## m only divisible by 3
 e := OrderMod( prime, m/3 );
 if not( e mod 2 = 0 and (k-prime^(e/2)) mod (m/3) = 0 ) then
 TryNextMethod();
 fi;
## exceptional case c)
 Info( InfoNearRing, 1, "exception (c): extending type-III representations" );
 n := OrderMod( r, m ); ## OrderMod( r, m ) = OrderMod( r, m/3 )
 mprime := Cofactor( m, n );
 m := m/3;
 fi;

##
## Note: finding matrix representations for a,b,z fulfilling
## z^(-1)*a*z = a^k and z^(-1)*b*z = b is best done simultanously.
## Therefore we do not use the representations of H and extend them with a
## matrix ZZ, but compute the matrices AA, BB, ZZ from scratch.
##

 CmodmCstar := Units( Integers mod m );
 Ubykpr := GroupByPrimeResidues( [prime, r], m );
 indexlist := List( RightCosets( CmodmCstar, Ubykpr ),
 x -> Int( Representative(x) ) );
 f := LogInt (p, prime);
 tetrahedral := FGRepT( prime, f );
 P := tetrahedral[1]; Q := tetrahedral[2]; R := tetrahedral[3];
 Z2 := P-P*Q;
 I := IdentityMat(Size(Ubykpr))*One(ZmodnZ(p));
 PP := KroneckerProduct( I, P );
 QQ := KroneckerProduct( I, Q );

 if r mod m = 1 then
## that is, the complement of the quaternion group in H is cyclic
 auxiliary := FGRep4C( prime, f, m );
 A := auxiliary[1];
 C := auxiliary[2];
 ZZ := KroneckerProduct( C, Z2 );
 fpfreps := List( indexlist, x ->
 [PP,QQ, KroneckerProduct( A^x, R ), ZZ] );
 else
## that is, the complement of the quaternion group in H is not cyclic,
## but metacyclic
 t := Size( Ubykpr )/e;
 r := r mod m;
 q := r^t mod m;
 d := LogMod( q, prime, m );
# If q = 1, then d = 0.
 auxiliary := FGRep4( prime, f, m, mprime, d );
 A := auxiliary[1];
 Wu := auxiliary[2]; B := auxiliary[3];
 Ws := auxiliary[4]; C := auxiliary[5];
 I := IdentityMat(e)*One(ZmodnZ(p));
 subdiagonal := List( [1..t-1], x -> [x+1, x, I] );
 I2 := IdentityMat(2)*One(ZmodnZ(p));

 fpfreps := [];
 for i in indexlist do
 AA := KroneckerProduct(
 BlockDiagonalMatrix( List( [0..t-1], x -> A^(i*r^x) ) ), R );
 BB := KroneckerProduct(
 BlockMatrix( Concatenation( subdiagonal, [[1, t, B*Wu^i]] ), t, t ), I2);
 ZZ := KroneckerProduct(
 BlockDiagonalMatrix( List( [0..t-1], x -> C*Ws^i ) ), Z2 );
 Add( fpfreps, [PP,QQ,AA,BB,ZZ] );
 od;
 fi;

 return [fpfreps, indexlist];
end );

InstallMethod(
FpfRepresentations4,
"induced representations",
true,
[IsInt, IsInt, IsInt, IsInt],
0,
 function( p, m, r, k )

 local P, Q, A, B, I, # auxiliary matrices (representation of the
auxiliary, # generators of H)
indexlist_H, fpfreps_H,
PP, QQ, # matrices (representing the generators of the
AA, BB, ZZ, # type-IV-group determined by m,r and k)
fpfreps, # list of matrices [PP,QQ,AA,BB,ZZ] (resp. for r = 1
 # [PP,QQ,AA,ZZ]) determining
 # the nonequivalent representations
indexlist,
CmodmCstar, # group of prime residues modulo m (resp. m/3 if
 # m mod 9 <> 0 )
n, # size of the subgroup of CmodmCstar generated by r
Ubykpr, # subgroup of CmodmCstar generated by k, prime and r
rcs, # RightCosets( CmodmCstar, Ubykpr )
constituents, # for induction: list of indices i such that the
 # fpfreps_H[i] induce nonequivalent representations
prime,
 i, x, y;

##
## If none of the exceptional cases holds, then the irreducible representations
## are simply those induced by the irred reps of H of type III and index 2.
##

 prime := SmallestRootInt( p );
 n := OrderMod( r, m );

 Info( InfoNearRing, 1, "GF(", prime,
 ")-representations of the type-IV-group are induced" );

 auxiliary := FpfRepresentations3( p, m, r );
 fpfreps_H := auxiliary[1];
 indexlist_H := auxiliary[2];
 I := IdentityMat( Length(fpfreps_H[1][1]), ZmodnZ(p) );
 P := fpfreps_H[1][1]; Q := fpfreps_H[1][2];
 PP := BlockDiagonalMatrix( [P, Q*P] );
 QQ := BlockDiagonalMatrix( [Q, -Q] );
 ZZ := BlockMatrix( [[2, 1, I], [1, 2, -I]], 2, 2 );

 if m mod 9 <> 0 and (k mod (m/3) = 1 or m = 3) then
## Note: if 9 does not divide m and k = 1 modulo m/3 (and e is odd),
## then the nonequivalent irred reps of H all induce nonequivalent irred reps
## of <p,q,a,b,z>
 constituents := [1..Length(indexlist_H)];
 else
## 2 respective nonequivalent irred reps of H (index i and i*k)
## induce the same irred rep of <p,q,a,b,z>
 if m mod 9 = 0 then
 CmodmCstar := Units( Integers mod m );
 Ubykpr := GroupByPrimeResidues( [k, prime, r], m );
 else
 CmodmCstar := Units( Integers mod (m/3) );
 Ubykpr := GroupByPrimeResidues( [k, prime, r], m/3 );
 fi;
 rcs := RightCosets( CmodmCstar, Ubykpr );
 constituents := List( rcs, x ->
 PositionProperty( indexlist_H, y -> y*One(CmodmCstar) in x ) );
 fi;

 k := k mod m;
 fpfreps := []; indexlist := [];
 if n = 1 then
## that is, if <a,b> is cyclic
 for i in constituents do
 A := fpfreps_H[i][3];
AA := BlockDiagonalMatrix( [A, A^k] );
Add( indexlist, indexlist_H[i] );
Add( fpfreps, [PP, QQ, AA, ZZ] );
 od;
 else
 for i in constituents do
 A := fpfreps_H[i][3]; B := fpfreps_H[i][4];
 AA := BlockDiagonalMatrix( [A, A^k] );
 BB := BlockDiagonalMatrix( [B, B] );
 Add( indexlist, indexlist_H[i] );
 Add( fpfreps, [PP, QQ, AA, BB, ZZ] );
 od;
 fi;

 return [fpfreps, indexlist];

end );

##
## FPF AUTOMORPHISM GROUPS OF ABELIAN GROUPS
##

##
## In order to build the generators of the non-conjugate fixed point free
## automorphism groups from the irreducible fpf representations, some
## combinatorical functions are needed.
##

 OnRightSets := function( list, g )
 return SortedList( OnRight( list, g ) );
 end;

 OnRightTuplesSets := function( e, g )
 return List( e, function(i) return OnRightSets( i, g ); end );
 end;

############################################################################
##
 IndexCombs := function( nr, indexlist, invariancegrp )
##
## nr[i] number of indices to be combined
## indexlist[i] indices to be combined, coset representatives
## of the respective invariancegrp[i]
##
## returns combinations of coset-representatives not necessarily
## corresponding to the indices in indexlist;
## used to find the non-conjugate CYCLIC fpf aut groups acting on
## an abelian group from fpf representations.
## Don't use this function for non-cyclic fpf aut groups. Take IndexCombs2
## instead.
##
 local G, ## group acting on the index combinations; index combs
 ## from the same G-orbit yield conjugate aut groups
one, U,
cosets, reps,
tuples, l,
i, tuple, x, y;

 G := Parent( invariancegrp[1] );
 one := One( invariancegrp[1] );
 l := Length(nr);
 cosets := []; tuples := [];
 for i in [1..l] do
 U := invariancegrp[i];
 Add( cosets, List( indexlist[i], x -> RightCoset( U, x*one ) ) );
 Add( tuples, UnorderedTuples( cosets[i], nr[i] ) );
 od;

 reps := List( Orbits( G, Cartesian( tuples ), OnRightTuplesSets ),
 Representative );
##
## Note: the indices as determined in the next step are not necessarily
## the same numbers as the initial representatives as given in indexlist.
## However, for the use of the combinations in FpfAutGrpsC
## this does not matter
##
 return List( reps, tuple -> List( tuple, set ->
 List( set, x -> Int(Representative(x)) ) ) );
end;

############################################################################
##
 IndexCombs2 := function( nr, indexlist, invariancegrp, G )
##
## nr[i] number of indices to be combined
## indexlist[i] indices to be combined, coset representatives
## of the respective invariancegrp[i]
## G group acting on the index combinations; index combs
## from the same G-orbit yield conjugate aut groups
##
## returns combinations of the positions of cosets with respect to indexlist
##

 local one,
cosets, reps, U,
tuples, l, positions,
i, tuple, x, y;

 one := One(G);
 l := Length(nr);
 cosets := []; tuples := [];
 for i in [1..l] do
 U := invariancegrp[i];
 Add( cosets, List( indexlist[i], x -> RightCoset( U, x*one ) ) );
 Add( tuples, UnorderedTuples( cosets[i], nr[i] ) );
 od;
 Info( InfoNearRing, 3, "Cartesian( tuples ) = ", Cartesian( tuples ) );
 reps := List( Orbits( G, Cartesian( tuples ), OnRightTuplesSets ),
 Representative );
 positions := [];
 for tuple in reps do
 Add( positions, List( [1..l], i -> List( tuple[i],
 x -> Position( cosets[i], x ) ) ) );
 od;
 return positions;
end;

############################################################################
##
#M FpfAutGrpsC( <primepowers>, <dimensions>, <m> )
##
## returns the "matrix"-generators for non conjugate cyclic fpf groups of
## order m on the abelian group
## (Z_p1)^d1 x...x (Z_pl)^dl for <primepowers> = [p1,...,pl]
## and the integers <dimensions> = [d1,...,dl]
##
## <primepowers> has to be sorted, [8,4,2,27,3,...], according to the order
## as given in FpfAutomorphismGroupsCyclic
##

InstallMethod(
FpfAutGrpsC,
"default",
true,
[IsList, IsList, IsInt],
0,
function( ps, ds, m )

 local CmodmCstar, # multiplicative group of residues prime to m
prime, f,
l,
nr, indexlist, invariancegrp,
A,
fpfreps,
 U, e, # subgroup of CmodmCstar generated by prime and
 # its size (degree of the irr. fpf rep over GF(prime))
matrices,
 pnew,
i, tuple, x, y;

 CmodmCstar := Units( Integers mod m );

 prime := 0;
 l := Length( ps );
 nr := []; indexlist := []; invariancegrp := []; fpfreps := [];
 for i in [1..l] do
 pnew := SmallestRootInt( ps[i] );
 f := LogInt( ps[i], pnew );
 if pnew <> prime then
prime := pnew;
A := MatrixInt( FGRepC( prime, f, m ) );
 U := GroupByPrimeResidues( [prime], m );
e := Size( U );
 fi;

 if ds[i] mod e <> 0 then
Error( "no fpf aut group of size m on this group: degree" );
 fi;

 Add( nr, ds[i]/e );
 Add( indexlist, List( RightCosets(CmodmCstar, U), Representative ) );
 Add( invariancegrp, U );

 Add( fpfreps, A*One(ZmodnZ( ps[i] )) );
 od;

 matrices := [];
 for tuple in IndexCombs( nr, indexlist, invariancegrp ) do
 Add( matrices, List( [1..l],
 i -> BlockDiagonalMatrix( List( tuple[i], x -> fpfreps[i]^x ) ) ) );
 od;

 return matrices;
 end );

############################################################################
##
#M FpfAutomorphismGroupsCyclic ( <ints>, <m> )
##
## determines one representative for each conjugacy class of cyclic
## fpf automorphism groups of size m acting on the abelian group
## AbelianGroup( ints )
## returns this list of nonconjugate fpf aut groups and AbelianGroup( ints )
##
## ints has to be a list of prime power integers and is ordered in
## the following function
##

InstallMethod(
FpfAutomorphismGroupsCyclic,
"default",
true,
[IsList, IsInt],
0,
function( ints, m )

 local coll,
ps, ds,
matrices,
G, gens,
x, y;

 coll := Collected( ints );
 Sort( coll, function( x, y )
 local p, q;
 p := SmallestRootInt(x[1]);
 q := SmallestRootInt(y[1]);
 return p > q or ( p = q and x[1] > y[1] ); end );

 ps := List( coll, x -> x[1] );
 ds := List( coll, x -> x[2] );

 matrices := FpfAutGrpsC( ps, ds, m );

 G := AbelianGroup( Concatenation( List( [1..Length( ps )], i ->
 List( [1..ds[i]], x -> ps[i] ) ) ) );
 gens := GeneratorsOfGroup( G );

 return [List( matrices, A -> GroupHomomorphismByMatrix( G, gens, A ) ),
 G];
end );

############################################################################
##
#M FpfAutGrpsMC( <primepowers>, <dimensions>, <m>, <r> )
##
## returns the matrix generators for non conjugate metacyclic fpf groups of
## order m*OrderMod(r,m) on the abelian group
## (Z_p1)^d1 x...x (Z_pl)^dl for <primepowers> = [p1,...,pl]
## and the integers <dimensions> = [d1,...,dl]
##
## <primepowers> has to be sorted, [8,4,2,27,3,...], according to the order
## as given in FpfAutomorphismGroupsMetacyclic, etc.
##

InstallMethod(
FpfAutGrpsMC,
"default",
true,
[IsList, IsList, IsInt, IsInt],
0,
function( ps, ds, m, r )

 local CmodmCstar, # multiplicative group of residues prime to m
prime, f,
l,
nr, indexlist, invariancegrp,
aux,
fpfreps,
 Ubyrandprime, # subgroup of CmodmCstar generated by r and prime and
deg, # its size (degree of the irr. fpf rep over GF(prime))
n, # OrderMod( r, m )
mprime, q,
G, ## subgroup of CmodmCstar, acting on the index
 ## combinations; index combs from the same G-orbit
 ## yield conjugate aut groups
 nrmatgens,
matrices,
 pnew,
i, g, aandb, tuple, x, y;

 CmodmCstar := Units( Integers mod m );

 prime := 0;
 l := Length( ps );
 nr := []; indexlist := []; invariancegrp := []; fpfreps := [];
 for i in [1..l] do
 pnew := SmallestRootInt( ps[i] );
 f := LogInt( ps[i], pnew );
 if pnew <> prime then
prime := pnew;
aux := FpfRepresentationsMetacyclic( ps[i], m, r );
 Ubyrandprime := GroupByPrimeResidues( [prime, r], m );
deg := Size( Ubyrandprime );
 fi;

 if ds[i] mod deg <> 0 then
Error( "no such fpf aut group on this group: degree" );
 fi;

 Add( nr, ds[i]/deg );
 Add( indexlist, aux[2] );
 Add( invariancegrp, Ubyrandprime );
 Add( fpfreps, List( aux[1], aandb -> List( aandb, MatrixInt ) ) );
 od;
##
## Determine the group G acting on the combinations of representation indices
## such that index combs from the same G-orbit yield conjugate aut groups.
## Note: For reps of cyclic groups G = CmodmCstar;
## for metacyclic groups G can be smaller than CmodmCstar.
##
 n := OrderMod( r, m );
 q := Maxfactor( m, 2 );
 if q > 2 and (r+1) mod q = 0 and n mod 4 = 2 then
## type II, quaternion 2-Sylow subgroup
 mprime := Cofactor( m/2, n/2 );
 if mprime = 0 or r mod (m/mprime) <> 1 then
Error( "parameters are not feasible" );
 fi;
 Info( InfoNearRing, 1,
 "parameters are feasible; metacyclic group of type II" );
 else
## type I, all Sylow subgroups are cyclic
 mprime := Cofactor( m, n );
 if mprime = 0 or r mod (m/mprime) <> 1 then
Error( "parameters are not feasible" );
 fi;
 Info( InfoNearRing, 1,
 "parameters are feasible; metacyclic group of type I" );
 fi;

 g := Gcd( n, m/mprime );
 G := GroupByPrimeResidues(
Filtered( List( [0..m/g-1], x -> 1+x*g ), y -> Gcd(m,y) = 1 ), m );

 Info( InfoNearRing, 3, " Size( G ) = ", Size( G ) );

 matrices := [];
 nrmatgens := 2; ## 2 generators for the metacyclic group
 for tuple in IndexCombs2( nr, indexlist, invariancegrp, G ) do
 Add( matrices, List( [1..nrmatgens], z -> List( [1..l], i ->
--> --------------------

--> maximum size reached

--> --------------------

Quelle fpf.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.57 Sekunden (vorverarbeitet) ]