Quelle  bbdecs.g   Sprache: unbekannt

##############################################################################
##                                                                          ##
#I This is the declaration file for the constructive recognition package of ##
## black box classical groups.                                              ##
##                                                                          ##
##############################################################################

IsBBGpElm := NewCategory ("IsBBGpElm", IsMultiplicativeElementWithInverse);
IsBBGpElmColl := CategoryCollections (IsBBGpElm);

IsPermBBGpElm := NewCategory ("IsPermBBGpElm", IsBBGpElm);
IsPermBBGpElmColl := CategoryCollections (IsPermBBGpElm);

IsNaturalPermBBGpElm := NewCategory ("IsNaturalPermBBGpElm", IsBBGpElm);
IsNaturalPermBBGpElmColl := CategoryCollections (IsNaturalPermBBGpElm);

IsMatrixBBGpElm := NewCategory ("IsMatrixBBGpElm", IsBBGpElm);
IsMatrixBBGpElmColl := CategoryCollections (IsMatrixBBGpElm);

### PAB 2-10-04  (more generally, we can implement quotient groups wherever we have
### an efficient membership test, but $p$-core is all we need for now...)
IsPQuotientBBGpElm := NewCategory ("IsPQuotientBBGpElm", IsBBGpElm);
IsPQuotientBBGpElmColl := CategoryCollections (IsPQuotientBBGpElm);

IsBBGp := IsGroup and IsBBGpElmColl;
IsPermBBGp := IsBBGp and IsPermBBGpElmColl;
IsNaturalPermBBGp := IsBBGp and IsNaturalPermBBGpElmColl;
IsMatrixBBGp := IsBBGp and IsMatrixBBGpElmColl;

### PAB 2-10-04
IsPQuotientBBGp := IsBBGp and IsPQuotientBBGpElmColl;

GpAsBBGp := NewOperation("GpAsBBGp", [IsGroup]);
BBGpAsPQuotientBBGp := NewOperation("BBGpAsPQuotientBBGp", [IsBBGp, IsInt]);
SubGpAsBBGp := NewOperation("SubGpAsBBGp", [IsBBGp, IsList]);



#############################################################################
##
#A Chain ( <bbgroup> )
##
## A Black Box Group will only have this attribute if it was constructed from
## a permutation group. The information that it contains is necessary for
## better pseudorandom elements.

Chain := NewAttribute("Chain", IsPermBBGp);
SetChain := Setter (Chain);
HasChain := Tester (Chain);


###########################################################################
##
## NaturalFlag is set true in a permutation group if it has to be converted
## to a black box group with natural group operations

NaturalFlag := NewProperty("NaturalFlag", IsPermBBGp);
SetNaturalFlag := Setter (NaturalFlag);
HasNaturalFlag := Tester (NaturalFlag);

#############################################################################
##
#F  PermInverseBBGp( <chain>, <perm> ) . . . . inverse in permutation bb group
##
##  given a list <perm> of permutations and a stabilizer chain <chain> for
##  the group $G$, the routine computes the inverse of perm as a list.

PermInverseBBGp := function (chain, perm)
local   i,          # loop variable
        y,          # element of permutation domain
        word,       # the list collecting the siftee of perm
        len,        # length of word
        inverse,    # the inverse of perm as a word; output
        len2,       # length of inverse
        coset,      # word representing a coset in a stabilizer
        stb;        # the stabilizer group we currently work with

    # perm must be a list of permutations itself!
    inverse := [];
    stb :=  chain;
    word := ShallowCopy(perm);
    while IsBound(stb.stabilizer) do
       y:=ImageInWord(stb.orbit[1],word);
       coset :=  CosetRepAsWord(stb.orbit[1],y,stb.transversal);
       len := Length(word);
       len2 := Length(inverse);
       for i in [1..Length(coset)] do
          word[len+i] := coset[i];
          inverse[len2+i] := coset[i];
       od;
       stb:=stb.stabilizer;
    od;
return inverse;
end;


##############################################################################
##
#F PermAltProd ( <chain> , <x> , <y> ) . . . inverse of x*y
##

PermAltProd := function (chain, x, y)
local   concat,     # concatenation of the input words
        inverse,    # the inverse of concat as a word
        product;    # the inverse of inverse as a word; output
    # x,y must be lists of permutations themselves!
    concat := Concatenation(x,y);
    inverse := PermInverseBBGp( chain, concat );
return(inverse);
end;


#############################################################################
##
#F  PermProductBBGp( <chain>, <x>, <y> ) . . . . product in permutation bb group
##
##  given lists <x> and <y> of permutations and a stabilizer chain <chain> for
##  the group $G$, the routine computes xy as a list.

PermProductBBGp := function (chain, x, y)
local   inverse,    # the inverse of concat as a word
        product;    # the inverse of inverse as a word; output

    # x,y must be lists of permutations themselves!
    inverse:=PermAltProd(chain,x,y);
    product := PermInverseBBGp( chain, inverse );
return product;
end;


############################################################################
##
#F PermEqualsBBGp( <chain> , <x> , <y> )
##
## For two strings, we test equality by tracing base images.

PermEqualsBBGp:=function( chain , x , y )
local stb;
    stb:=chain;
    while IsBound(stb.stabilizer) do
      if not ImageInWord(stb.orbit[1],x)=ImageInWord(stb.orbit[1],y) then
           return(false);
      fi;
      stb:=stb.stabilizer;
    od;
return(true);
end;

##############################################################################
##
#F PQuotientEqualsBBGp( <bbg> , <p> , <x> , <y> )
##
## PAB: 02-12-04
## this test presumes that the $p$-core of <gp> is nilpotent class-2:
## in particular, it covers the setting we
## are interested in, namely extraspecial $p$-groups

PQuotientEqualsBBGp := function (gp, p, x, y)
local  w, gens, conj, comm, ord, i, j, equal, u, v, z, o, one, central;
   w:=x*Inverse(y);
      ## first test whether <w> has order dividing <p>( 2 , <p> )
   one:=One(gp);
   ord:=p*Gcd(p,2);
   o:=w^ord;

   if not ( o![1]=one![1] ) then return false; fi;

   gens:=GeneratorsOfGroup( gp );
   if ( Length(gens) < 11 ) then
       conj:=List( gens, x->w^x );
   else
       conj:=List( [1..10], i->w^PseudoRandom(gp) );
   fi;
   comm:=[];
   for i in [1..Length(conj)] do
      for j in [i+1..Length(conj)] do
         Add( comm, Comm( conj[i] , conj[j] ) );
      od;
   od;

   equal:=true;
      ## first ensure the elements of <comm> have order dividing <p>(2,<p>)
   for z in comm do
      o:=z^ord;
      equal := equal and (o![1]=one![1]);
         ## here we just want to test whether the underlying elements
  ## are equal -- essentially this is just testing equality in
  ## the original bb group, not the quotient.
   od;
   if (not equal) then return false; fi;
   for u in conj do
      for z in comm do
         v:=Comm(u,z);
         equal := equal and (v![1]=one![1]);
      od;
   od;

if ( equal ) then  ## want to detect whenever we have a noncentral element
     central:=true;
     for z in comm do
        central:=central and (z![1]=one![1]);
     od;
     if ( not central ) then   ## we have found our non-central element
Error(999);
     fi;
fi;

return equal;
end;

##############################################################################
##
#F EqualsModPCore( <bbg> , <p> , <x> , <y> )
##
## PAB: 02-16-04
## This test presumes that the $p$-core of <bbg> is nilpotent class-2.
## In particular, it covers the setting we are interested in: extraspecial $p$-groups
## The procedure is exactly as in <PQuotientEqualsBBGp> except the output is either
## a flag ( <true> or <false> ) or a black box group elements (a non-central element
## of the $p$-core of <bbg>

EqualsModPCore := function (gp, p, x, y)
local  w, gens, conj, comm, ord, i, j, equal, u, v, z, o, one, central;
   w:=x*Inverse(y);
      ## first test whether <w> has order dividing <p>( 2 , <p> )
   one:=One(gp);
   ord:=p*Gcd(p,2);
   o:=w^ord;

   if not ( o![1]=one![1] ) then return false; fi;

   gens:=GeneratorsOfGroup( gp );
   if ( Length(gens) < 11 ) then
       conj:=List( gens, x->w^x );
   else
       conj:=List( [1..10], i->w^PseudoRandom(gp) );
   fi;
   comm:=[];
   for i in [1..Length(conj)] do
      for j in [i+1..Length(conj)] do
         Add( comm, Comm( conj[i] , conj[j] ) );
      od;
   od;

   equal:=true;
      ## first ensure the elements of <comm> have order dividing <p>(2,<p>)
   for z in comm do
      o:=z^ord;
      equal := equal and (o![1]=one![1]);
         ## here we just want to test whether the underlying elements
  ## are equal -- essentially this is just testing equality in
  ## the original bb group, not the quotient.
   od;
   if (not equal) then return false; fi;
   for u in conj do
      for z in comm do
         v:=Comm(u,z);
         equal := equal and (v![1]=one![1]);
      od;
   od;

  if ( equal ) then  ## want to detect whenever we have a noncentral element
     central:=true;
     for z in comm do
        central:=central and (z![1]=one![1]);
     od;
     if ( not central ) then   ## we have found our non-central element
        return w;
     fi;
  fi;
return equal;
end;

################################################################################
##
#F BBGpElmFromList( <family> , <list> )
##

BBGpElmFromList := function (elmfam, list)
return Objectify (elmfam!.defaultType, [list]);
end;



##############################################################################
##
#M  GpAsBBGp ( <perm group> )
##
InstallMethod(GpAsBBGp, "perm group -> black box group", true, [IsPermGroup],0,
function(grp)
local elmfam,gens,i,G;
  elmfam:=NewFamily("elements family of bbg",IsObject,IsPermBBGpElm);
  elmfam!.defaultType :=NewType(elmfam,
                                IsPermBBGpElm and IsPositionalObjectRep);

  # now tell the elements family about the underlying permutation group
  elmfam!.stabChainGroup:=StabChain(grp);

  SetOne(elmfam,BBGpElmFromList(elmfam,[One(grp)]));
  # make black box group elements from the permutation generators
  gens:=[];
  for i in GeneratorsOfGroup(grp) do
    Add(gens,BBGpElmFromList(elmfam,[i]));
  od;

  G:=GroupWithGenerators(gens,BBGpElmFromList(elmfam,[One(grp)]));
  SetChain(G,StabChain(grp));
return G;
end);

##############################################################################
##
#M  GpAsBBGp ( <perm group> )
##
InstallMethod(GpAsBBGp, "perm group -> black box group w/ natural operations",
 true, [IsPermGroup and NaturalFlag],0,
function(grp)
local elmfam,gens,i,G;
  elmfam:=NewFamily("elements family of bbg",IsObject,IsNaturalPermBBGpElm);
  elmfam!.defaultType :=NewType(elmfam,
                              IsNaturalPermBBGpElm and IsPositionalObjectRep);
  SetOne(elmfam,BBGpElmFromList(elmfam,One(grp)));
  # make black box group elements from the perm group generators
  gens:=[];
  for i in GeneratorsOfGroup(grp) do
    Add(gens,BBGpElmFromList(elmfam,i));
  od;

  G:=GroupWithGenerators(gens,BBGpElmFromList(elmfam,One(grp)));
return G;
end);


##############################################################################
##
#M  GpAsBBGp ( <matrix group> )
##
InstallMethod(GpAsBBGp, "matrix group -> black box group", true, [IsMatrixGroup],0,
function(grp)
local elmfam,gens,i,G;
  elmfam:=NewFamily("elements family of bbg",IsObject,IsMatrixBBGpElm);
  elmfam!.defaultType :=NewType(elmfam,
                                IsMatrixBBGpElm and IsPositionalObjectRep);
  SetOne(elmfam,BBGpElmFromList(elmfam,One(grp)));
  # make black box group elements from the matrix generators
  gens:=[];
  for i in GeneratorsOfGroup(grp) do
    Add(gens,BBGpElmFromList(elmfam,i));
  od;
  G:=GroupWithGenerators(gens,BBGpElmFromList(elmfam,One(grp)));
return G;
end);

###############################################################################
##
#M BBGpAsPQuotientBBGp( <bb group> )        ... PAB 2-10-04
##
InstallMethod( BBGpAsPQuotientBBGp, "bb group -> quotient bb group", true,
[IsBBGp,IsInt],0,
function( bbg , p )
local elmfam,gens,i,G,x;
  elmfam:=NewFamily("elements family of bbg",IsObject,IsPQuotientBBGpElm);
  elmfam!.defaultType := NewType( elmfam, IsPQuotientBBGpElm and IsPositionalObjectRep );
  elmfam!.prime:=p;
  SetOne(elmfam,BBGpElmFromList(elmfam,One(bbg)![1]));
  gens:=[];
  for i in GeneratorsOfGroup( bbg ) do
     x:=BBGpElmFromList(elmfam,i![1]);
     Add(gens,x);
  od;
  G:=GroupWithGenerators(gens,BBGpElmFromList(elmfam,One(bbg)![1]));
  elmfam!.group:=G;
return G;
end);

#############################################################################
## Methods for group operations
##

InstallMethod(PrintObj,"bbg elms",true,[IsBBGpElm],0,
function(e)
  Print("BBGpElm ",e![1]);
end);

InstallMethod(One,"bbg elms",true,[IsBBGpElm],0,
function(e)
  return One(FamilyObj(e));
end);

InstallMethod(\*,"bbg elms",IsIdenticalObj,[IsPermBBGpElm,IsPermBBGpElm],0,
function(a,b)
local fam;
  fam:=FamilyObj(a);
  return BBGpElmFromList(fam,
       PermProductBBGp(fam!.stabChainGroup, a![1], b![1] ));
end);

InstallMethod(\=,"bbg elms",IsIdenticalObj,[IsPermBBGpElm,IsPermBBGpElm],0,
function(a,b)
local fam;
  fam:=FamilyObj(a);
  return  PermEqualsBBGp(fam!.stabChainGroup, a![1], b![1] );
end);

InstallMethod(InverseOp,"bbg elms",true,[IsPermBBGpElm],0,
function(a)
local fam;
  fam:=FamilyObj(a);
  return BBGpElmFromList(fam,
       PermInverseBBGp(fam!.stabChainGroup, a![1] ));
end);

InstallMethod(\*,"bbg elms",IsIdenticalObj,[IsNaturalPermBBGpElm,
IsNaturalPermBBGpElm],0,
function(a,b)
local fam;
  fam:=FamilyObj(a);
  return BBGpElmFromList(fam, a![1] * b![1] );
end);

InstallMethod(\=,"bbg elms",IsIdenticalObj,[IsNaturalPermBBGpElm,
IsNaturalPermBBGpElm],0,
function(a,b)
  return  a![1] =b![1] ;
end);

InstallMethod(\<,"bbg elms",IsIdenticalObj,[IsNaturalPermBBGpElm,
IsNaturalPermBBGpElm],0,
function(a,b)
  return  a![1]<b![1] ;
end);

InstallMethod(InverseOp,"bbg elms",true,[IsNaturalPermBBGpElm],0,
function(a)
local fam;
  fam:=FamilyObj(a);
  return BBGpElmFromList(fam,
       Inverse( a![1] ));
end);

InstallMethod(\*,"bbg elms",IsIdenticalObj,[IsMatrixBBGpElm,IsMatrixBBGpElm],0,
function(a,b)
local fam;
  fam:=FamilyObj(a);
  return BBGpElmFromList(fam, a![1] * b![1] );
end);

### PAB: 02-12-04
InstallMethod(\*,"bbg elms",IsIdenticalObj,[IsPQuotientBBGpElm,IsPQuotientBBGpElm],0,
function(a,b)
local fam,x;
  fam:=FamilyObj(a);
  x:=BBGpElmFromList(fam, a![1] * b![1] );
  return x;
end);

InstallMethod(\=,"bbg elms",IsIdenticalObj,[IsMatrixBBGpElm,IsMatrixBBGpElm],0,
function(a,b)
  return  a![1]=b![1] ;
end);


InstallMethod(\<,"bbg elms",IsIdenticalObj,[IsMatrixBBGpElm,IsMatrixBBGpElm],0,
function(a,b)
  return  a![1]<b![1] ;
end);

InstallMethod(InverseOp,"bbg elms",true,[IsMatrixBBGpElm],0,
function(a)
local fam;
  fam:=FamilyObj(a);
  return BBGpElmFromList(fam,
       Inverse( a![1] ));
end);

### PAB: 02-12-04
InstallMethod(InverseOp,"bbg elms",true,[IsPQuotientBBGpElm],0,
function(a)
local fam, x;
   fam:=FamilyObj(a);
   x:=BBGpElmFromList(fam,Inverse( a![1] ));
   return x;
end);

### PAB: 02-12-04
InstallMethod(\=,"bbg elms",IsIdenticalObj,[IsPQuotientBBGpElm,IsPQuotientBBGpElm],0,
function(a,b)
   local fam;
   fam:=FamilyObj(a);
return (PQuotientEqualsBBGp(fam!.group,fam!.prime,a,b) );
end);


##############################################################################
##
#A PseudoRandom( <bbgroup> )                  . . . random function in bbg

InstallMethod( PseudoRandom , "method for permbbgs with chain" , true ,
  [HasChain] , 0 ,
function( bbg )
local fam, chain;
   chain := Chain( bbg );
   fam := FamilyObj(GeneratorsOfGroup(bbg)[1]);
return BBGpElmFromList(fam, RandomElmAsWord( chain ) );
end);