#############################################################################
##
## This file is part of recog, a package for the GAP computer algebra system
## which provides a collection of methods for the constructive recognition
## of groups.
##
## This files's authors include Max Neunhöffer, Ákos Seress.
##
## Copyright of recog belongs to its developers whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-3.0-or-later
##
##
## Implementation stuff for derived subgroup method
##
#############################################################################
RECOG.DerivedSubgroupMonteCarlo := function(g)
local gens,gens2,i,x,y;
gens := [];
for i in [1..10] do
x := PseudoRandom(g);
y := PseudoRandom(g);
Add(gens,Comm(x,y));
od;
gens2 := FastNormalClosure(GeneratorsOfGroup(g),gens,10);
return GroupWithGenerators(gens2);
end;
#! @BeginChunk Derived
#! This method computes the derived subgroup, if this has not yet been done
#! by other methods. It then uses the MeatAxe to decide whether
#! the derived subgroup acts irreducibly or not. If it acts reducibly,
#! then we can apply Clifford theory to the natural module. The natural
#! module restricted to the derived subgroup is a direct sum of simple
#! modules. If all the summands are isomorphic, we immediately get either
#! an action of <A>G</A> on blocks or a tensor decomposition. Otherwise,
#! we get an action of <A>G</A> on the isotypic components. Either way,
#! we find a reduction.
#!
#! If the derived group acts irreducibly, we return <K>false</K> in the current
#! implementation.
#! @EndChunk
FindHomMethodsProjective.Derived :=
function(ri,G)
# We assume G to act absolutely irreducible
local H,a,basis,collf,conjgensG,f,hom,homcomp,homs,homsimg,kro,o,r,subdim;
f := ri!.field;
if not IsBound(ri!.derived) then
ri!.derived := RECOG.DerivedSubgroupMonteCarlo(G);
ri!.derived_mtx := GModuleByMats(GeneratorsOfGroup(ri!.derived),f);
fi;
if ForAll(GeneratorsOfGroup(ri!.derived),IsOneProjective) then
Info(InfoRecog,2,"Derived subgroup is trivial.");
return false;
fi;
if MTX.IsIrreducible(ri!.derived_mtx) then
if not MTX.IsAbsolutelyIrreducible(ri!.derived_mtx) then
# FIXME: Check for field automorphisms:
return false;
Error("not yet done");
fi;
return false;
fi;
collf := MTX.CollectedFactors(ri!.derived_mtx);
if Length(collf) = 1 then
if MTX.Dimension(collf[1][1]) = 1 then
Error("This should never have happened (2), tell Max.");
# This should have been caught by the triviality test above.
fi;
Info(InfoRecog,2,"Restriction to derived subgroup is homogeneous.");
homs := MTX.Homomorphisms(collf[1][1],ri!.derived_mtx);
basis := Concatenation(homs);
ConvertToMatrixRep(basis);
subdim := MTX.Dimension(collf[1][1]);
r := rec(t := basis, ti := basis^-1,
blocksize := MTX.Dimension(collf[1][1]));
# Note that we already checked for semilinear, so we know that
# the irreducible N-submodule is absolutely irreducible!
# Now we believe to have a tensor decomposition:
conjgensG := List(GeneratorsOfGroup(G),x->r.t * x * r.ti);
kro := List(conjgensG,g->RECOG.IsKroneckerProduct(g,r.blocksize));
if not(ForAll(kro,k->k[1] = true)) then
Info(InfoRecog,1,"VERY, VERY, STRANGE!");
Info(InfoRecog,1,"False alarm, was not a tensor decomposition.");
return false;
fi;
H := GroupWithGenerators(conjgensG);
hom := GroupHomByFuncWithData(G,H,RECOG.HomDoBaseChange,r);
SetHomom(ri,hom);
# Hand down information:
InitialDataForImageRecogNode(ri).blocksize := r.blocksize;
InitialDataForImageRecogNode(ri).generatorskronecker := kro;
Add( InitialDataForImageRecogNode(ri).hints,
rec( method := FindHomMethodsProjective.KroneckerProduct,
rank := 4000, stamp := "KroneckerProduct" ) );
# This is an isomorphism:
findgensNmeth(ri).method := FindKernelDoNothing;
return true;
fi;
Info(InfoRecog,2,"Using action on the set of homogeneous components",
" (",Length(collf)," elements)...");
# Now find a homogeneous component to act on it:
homs := MTX.Homomorphisms(collf[1][1],ri!.derived_mtx);
homsimg := BasisVectors(Basis(VectorSpace(f,Concatenation(homs))));
homcomp := MutableCopyMat(homsimg);
# FIXME: This will go:
ConvertToMatrixRep(homcomp);
TriangulizeMat(homcomp);
o := Orb(G,homcomp,OnSubspacesByCanonicalBasis,rec(storenumbers := true));
Enumerate(o);
a := OrbActionHomomorphism(G,o);
SetHomom(ri,a);
Setmethodsforimage(ri,FindHomDbPerm);
return true;
end;
