|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Franz Gähler.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains operations for matrix groups over the rationals
##
#############################################################################
##
#M IsRationalMatrixGroup( G )
##
InstallMethod( IsRationalMatrixGroup, [ IsCyclotomicMatrixGroup ],
G -> ForAll( Flat( GeneratorsOfGroup( G ) ), IsRat ) );
InstallTrueMethod( IsRationalMatrixGroup, IsIntegerMatrixGroup );
#############################################################################
##
#M IsIntegerMatrixGroup( G )
##
InstallMethod( IsIntegerMatrixGroup, [ IsCyclotomicMatrixGroup ],
function( G )
local gen;
gen := GeneratorsOfGroup( G );
return ForAll( gen, mat -> ForAll( mat, row -> ForAll( row, IsInt ) ) ) and
ForAll( gen, g -> AbsInt( DeterminantMat( g ) ) = 1 );
end
);
#############################################################################
##
#M GeneralLinearGroupCons(IsMatrixGroup,n,Integers)
##
InstallMethod( GeneralLinearGroupCons,
"some generators for GL_n(Z)",
[ IsMatrixGroup, IsPosInt, IsIntegers ],
function(fil,n,ints)
local gens,mat,G;
# permutations
gens:=List(GeneratorsOfGroup(SymmetricGroup(n)),i->PermutationMat(i,n));
# sign swapper
mat:= IdentityMat(n,1);
mat[1,1]:=-1;
Add(gens,mat);
# elementary addition
if n>1 then
mat:= IdentityMat(n,1);
mat[1,2]:=1;
Add(gens,mat);
fi;
gens:=List(gens,Immutable);
G:= GroupByGenerators( gens, IdentityMat( n, 1 ) );
Setter(IsNaturalGLnZ)(G,true);
SetName(G,Concatenation("GL(",String(n),",Integers)"));
if n>1 then
SetSize(G,infinity);
SetIsFinite(G,false);
else
SetIsFinite(G,true);
SetSize(G,2);
SetNiceMonomorphism(G,DoSparseLinearActionOnFaithfulSubset(G, OnRight, false));
fi;
return G;
end);
#############################################################################
##
#M SpecialLinearGroupCons(IsMatrixGroup,n,Integers)
##
InstallMethod(SpecialLinearGroupCons,"some generators for SL_n(Z)",
[IsMatrixGroup,IsPosInt,IsIntegers],
function(fil,n,ints)
local gens,mat,G;
# permutations
gens:=List(GeneratorsOfGroup(AlternatingGroup(n)),i->PermutationMat(i,n));
if n>1 then
mat:= IdentityMat(n,1);
mat{[1..2]}{[1..2]}:=[[0,1],[-1,0]];
Add(gens,mat);
# elementary addition
mat:= IdentityMat(n,1);
mat[1,2]:=1;
Add(gens,mat);
fi;
gens:=List(gens,Immutable);
G:= GroupByGenerators( gens, IdentityMat( n, 1 ) );
Setter(IsNaturalSLnZ)(G,true);
SetName(G,Concatenation("SL(",String(n),",Integers)"));
if n>1 then
SetSize(G,infinity);
SetIsFinite(G,false);
else
SetIsFinite(G,true);
SetSize(G,1);
SetNiceMonomorphism(G,DoSparseLinearActionOnFaithfulSubset(G, OnRight, false));
fi;
return G;
end);
#############################################################################
##
#M \in( <g>, GL( <n>, Integers ) )
##
InstallMethod( \in,
"for matrix and GL(n,Z)", IsElmsColls,
[ IsMatrix, IsNaturalGLnZ ],
function ( g, GLnZ )
return DimensionsMat(g) = DimensionsMat(One(GLnZ))
and ForAll(Flat(g),IsInt) and DeterminantMat(g) in [-1,1];
end );
#############################################################################
##
#M \in( <g>, SL( <n>, Integers ) )
##
InstallMethod( \in,
"for matrix and SL(n,Z)", IsElmsColls,
[ IsMatrix, IsNaturalSLnZ ],
function ( g, SLnZ )
return DimensionsMat(g) = DimensionsMat(One(SLnZ))
and ForAll(Flat(g),IsInt) and DeterminantMat(g) = 1;
end );
#############################################################################
##
#M Normalizer( GLnZ, G ) . . . . . . . . . . . . . . . . .Normalizer in GLnZ
##
InstallMethod( NormalizerOp, IsIdenticalObj,
[ IsNaturalGLnZ, IsCyclotomicMatrixGroup ],
function( GLnZ, G )
return NormalizerInGLnZ( G );
end );
#############################################################################
##
#M Centralizer( GLnZ, G ) . . . . . . . . . . . . . . . .Centralizer in GLnZ
##
InstallMethod( CentralizerOp, IsIdenticalObj,
[ IsNaturalGLnZ, IsCyclotomicMatrixGroup ],
function( GLnZ, G )
return CentralizerInGLnZ( G );
end );
#############################################################################
##
#M CrystGroupDefaultAction . . . . . . . . . . . . . . RightAction initially
##
BindGlobal( "CrystGroupDefaultAction", RightAction );
#############################################################################
##
#M SetCrystGroupDefaultAction( <action> ) . . . . .RightAction or LeftAction
##
InstallGlobalFunction( SetCrystGroupDefaultAction, function( action )
if action = LeftAction then
MakeReadWriteGlobal( "CrystGroupDefaultAction" );
CrystGroupDefaultAction := LeftAction;
MakeReadOnlyGlobal( "CrystGroupDefaultAction" );
elif action = RightAction then
MakeReadWriteGlobal( "CrystGroupDefaultAction" );
CrystGroupDefaultAction := RightAction;
MakeReadOnlyGlobal( "CrystGroupDefaultAction" );
else
Error( "action must be either LeftAction or RightAction" );
fi;
end );
#############################################################################
##
#M IsBravaisGroup( <G> ) . . . . . . . . . . . . . . . . . . .IsBravaisGroup
##
InstallMethod( IsBravaisGroup,
[ IsCyclotomicMatrixGroup ],
function( G )
return G = BravaisGroup( G );
end );
#############################################################################
##
#M InvariantLattice( G ) . . . . .invariant lattice of rational matrix group
##
InstallMethod( InvariantLattice, "for rational matrix groups",
[ IsCyclotomicMatrixGroup ],
function( G )
local gen, dim, trn, rnd, tab, den;
if not IsRationalMatrixGroup( G ) then
TryNextMethod();
fi;
# return fail if no invariant lattice exists
gen := GeneratorsOfGroup( G );
if ForAny( gen, x -> not IsInt( TraceMat( x ) ) ) then
return fail;
fi;
if ForAny( gen, x -> AbsInt( DeterminantMat( x ) ) <> 1 ) then
return fail;
fi;
dim := DimensionOfMatrixGroup( G );
trn := Immutable( IdentityMat( dim ) );
rnd := Random( GeneratorsOfGroup( G ) );
# refine lattice until it contains its image
repeat
# if there are elements with non-integer trace,
# we will find one, sooner or later (with probability 1)
rnd := rnd * Random( gen );
if not IsInt( TraceMat( rnd ) ) then
return fail;
fi;
tab := List( gen, g -> trn * g * trn^-1 );
tab := Concatenation( tab );
tab := Filtered( tab, vec -> ForAny( vec, x -> not IsInt( x ) ) );
if Length( tab ) > 0 then
den := Lcm( List( Flat( tab ), x -> DenominatorRat( x ) ) );
tab := Concatenation( den * Immutable( IdentityMat( dim ) ),
den * tab );
tab := HermiteNormalFormIntegerMat( tab ) / den;
trn := tab{[1..dim]} * trn;
else
den := 1;
fi;
until den = 1;
return trn;
end );
BindGlobal("MinkowskiMultiple", function(n)
local res;
if n <= 0 then
Error("<n> must be a positive integer");
fi;
res := 2;
for n in [n,n-1..2] do
if IsOddInt(n) then
res := res * 2;
else
res := res * DenominatorRat(Bernoulli(n)/n);
fi;
od;
return res;
end);
#############################################################################
##
#M IsFinite( G ) . . . . . . . . . . . IsFinite for cyclotomic matrix group
##
InstallMethod( IsFinite,
"cyclotomic matrix group",
[ IsCyclotomicMatrixGroup ],
function( G )
# The code below is based on the algorithm described in [DFO13]
local badPrimes, n, g, FindPrimesInMatDenominators, p, e, H, phi, gens, rels, nice, inv, Hnice;
# if not rational, use the nice monomorphism into a rational matrix group
if not IsRationalMatrixGroup( G ) then
# the following does not use NiceObject(G) as the only method for
# that currently requires IsHandledByNiceMonomorphism
SetNiceObject( G, Image( NiceMonomorphism( G ), G ) );
return IsFinite( NiceObject( G ) );
fi;
# if not integer, choose basis in which it is integer
badPrimes := [ 2 ];
n := DimensionOfMatrixGroup( G );
FindPrimesInMatDenominators := function( mat )
local i, j, d;
for i in [1..n] do
for j in [1..n] do
d := DenominatorRat(mat[i,j]);
if d > 1 then
UniteSet(badPrimes, PrimeDivisors(d));
fi;
od;
od;
end;
for g in GeneratorsOfGroup( G ) do
FindPrimesInMatDenominators(g);
FindPrimesInMatDenominators(g^-1);
od;
p := 3;
while p in badPrimes do
p := NextPrimeInt(p);
od;
# now reduce mod p
e := One(GF(p));
H := Group( GeneratorsOfGroup( G ) * e );
# check Minkowski bounds here to immediately reject some G as infinite
if MinkowskiMultiple(n) mod Size(H) <> 0 then
return false;
fi;
Hnice := NiceMonomorphism(H);
H := NiceObject(H);
# evaluate relators
phi := IsomorphismFpGroupByGeneratorsNC(H, GeneratorsOfGroup( H ) : method := "fast");
gens := GeneratorsOfGroup(FreeGroupOfFpGroup(Range(phi)));
rels := RelatorsOfFpGroup(Range(phi));
if not ForAll(rels, r -> IsOne(MappedWord(r, gens, GeneratorsOfGroup(G)))) then
return false;
fi;
# bypass the finite field matrix group in the middle so that we can
# compute preimages more easily
inv := GroupHomomorphismByImagesNC(H, G : noassert);
# set as a nice monomorphism
nice := GroupHomomorphismByFunction(G, H,
function(x)
if ValueOption("actioncanfail")=true then
if not ForAll( x, r -> ForAll( r, v -> IsRat(v) and DenominatorRat( v ) mod p <> 0 ) ) then
return fail;
fi;
fi;
return ImageElm(Hnice, x * e);
end,
function(y)
return inv(y);
end
);
SetNiceMonomorphism(G, nice);
SetNiceObject(G, H);
SetIsHandledByNiceMonomorphism(G, true);
return true;
end );
#############################################################################
##
#M Size( <G> ) . . . . . for cyclotomic matrix group not known to be finite
##
InstallMethod( Size,
"cyclotomic matrix group not known to be finite",
[ IsCyclotomicMatrixGroup ],
function( G )
if IsFinite( G ) then
return Size( G ); # now G knows it is finite
else
return infinity;
fi;
end );
#############################################################################
##
#M NiceMonomorphism( <G> ) . . . . . . . . . . for a cyclotomic matrix group
##
## For a *nonrational* cyclotomic matrix group, the nice monomorphism is
## defined as an isomorphism to a rational matrix group.
##
## Note that a stored nice monomorphism does *not* imply that the group is
## handled by the nice monomorphism; as for matrix groups in general,
## we want to set `IsHandledByNiceMonomorphism' only for *finite* matrix
## groups.
##
InstallMethod( NiceMonomorphism,
"for a (nonrational) cyclotomic matrix group",
[ IsCyclotomicMatrixGroup ],
function( G )
if IsRationalMatrixGroup( G ) then
TryNextMethod();
else
return BlowUpIsomorphism( G, Basis( FieldOfMatrixGroup( G ) ) );
fi;
end );
#############################################################################
##
#M IsHandledByNiceMonomorphism( <G> ) . . . . for a cyclotomic matrix group
##
## A matrix group shall be handled via nice monomorphism if and only if it
## is finite.
## We install the method here because for cyclotomic matrix groups,
## we can decide finiteness.
##
## (Note that nice monomorphisms may be used also for infinite groups,
## for example for non-rational matrix groups over the cyclotomics,
## where the image of the monomorphism is a rational matrix group.)
##
InstallMethod( IsHandledByNiceMonomorphism,
"for a cyclotomic matrix group",
[ IsCyclotomicMatrixGroup ],
IsFinite );
#############################################################################
##
#F MayBeHandledByNiceMonomorphism( <G> ) . . . for a cyclotomic matrix group
##
## Since we can decide finiteness for a cyclotomic matrix group,
## it makes sense to set 'MayBeHandledByNiceMonomorphism' for it,
## see the documentation of this filter.
##
InstallTrueMethod( MayBeHandledByNiceMonomorphism, IsCyclotomicMatrixGroup );
#############################################################################
##
#M IsomorphismPermGroup( <G> ) . . . . . . . . . . for rational matrix group
##
## The only difference to the method installed for matrix groups is that
## finiteness of (finitely generated) matrix groups over the cyclotomics can
## be decided and hence no warning need to be issued.
##
InstallMethod( IsomorphismPermGroup,
"cyclotomic matrix group",
[ IsCyclotomicMatrixGroup ], 10,
function( G )
if HasNiceMonomorphism(G) and IsPermGroup(Range(NiceMonomorphism(G))) then
return RestrictedMapping(NiceMonomorphism(G),G);
elif not IsFinite(G) then
Error("Cannot compute permutation representation of infinite group");
else
return NicomorphismOfGeneralMatrixGroup(G,false,false);
fi;
end);
#############################################################################
##
## *Finite* matrix groups lie in the filter `IsHandledByNiceMonomorphism'.
## In order to make the corresponding methods for the operations involved in
## the following `RedispatchOnCondition' calls applicable for finite
## matrix groups over the cyclotomics,
## we force a finiteness check as ``last resort''.
##
RedispatchOnCondition( \in, true,
[ IsMatrix, IsCyclotomicMatrixGroup ],
[ IsObject, IsFinite ], 0 );
RedispatchOnCondition( \=, IsIdenticalObj,
[ IsCyclotomicMatrixGroup, IsCyclotomicMatrixGroup ],
[ IsFinite, IsFinite ], 0 );
RedispatchOnCondition( IndexOp, IsIdenticalObj,
[ IsCyclotomicMatrixGroup, IsCyclotomicMatrixGroup ],
[ IsFinite, IsFinite ], 0 );
RedispatchOnCondition( IndexNC, IsIdenticalObj,
[ IsCyclotomicMatrixGroup, IsCyclotomicMatrixGroup ],
[ IsFinite, IsFinite ], 0 );
RedispatchOnCondition( NormalizerOp, IsIdenticalObj,
[ IsCyclotomicMatrixGroup, IsCyclotomicMatrixGroup ],
[ IsFinite, IsFinite ], 0 );
RedispatchOnCondition( NormalClosureOp, IsIdenticalObj,
[ IsCyclotomicMatrixGroup, IsCyclotomicMatrixGroup ],
[ IsFinite, IsFinite ], 0 );
RedispatchOnCondition( CentralizerOp, true,
[ IsCyclotomicMatrixGroup, IsObject ],
[ IsFinite ], 0 );
RedispatchOnCondition( ClosureGroup, true,
[ IsCyclotomicMatrixGroup, IsObject ],
[ IsFinite ], 0 );
RedispatchOnCondition( SylowSubgroupOp, true,
[ IsCyclotomicMatrixGroup, IsPosInt ],
[ IsFinite ], 0 );
RedispatchOnCondition( ConjugacyClasses, true,
[ IsCyclotomicMatrixGroup ],
[ IsFinite ], 0 );
#T as we have installed a method for this situation,
#T no fallback is needed
# RedispatchOnCondition( IsomorphismPermGroup, true,
# [ IsCyclotomicMatrixGroup ],
# [ IsFinite ], 0 );
RedispatchOnCondition( IsomorphismPcGroup, true,
[ IsCyclotomicMatrixGroup ],
[ IsFinite ], 0 );
# Note that there is a unary method with requirement 'IsGroup'
# that calls the two-argument variant.
RedispatchOnCondition( IsomorphismFpGroup, true,
[ IsCyclotomicMatrixGroup, IsString ],
[ IsFinite, IsObject ], 0 );
RedispatchOnCondition( CompositionSeries, true,
[ IsCyclotomicMatrixGroup ],
[ IsFinite ], 0 );
RedispatchOnCondition( NiceMonomorphism, true,
[ IsCyclotomicMatrixGroup ],
[ IsFinite ], 0 );
[ Dauer der Verarbeitung: 0.33 Sekunden
(vorverarbeitet)
]
|
