Quelle  nq.gi   Sprache: unbekannt

############################################################################
##
#W nq.gi   LPRES    René Hartung
##

############################################################################
##
#M  NilpotentQuotient ( <LpGroup>, <int> ) . . for invariant LpGroups
##
## computes a weighted nilpotent presentation for the class-<int> quotient
## of the invariant <LpGroup> if it already has a nilpotent quotient system.
##
InstallOtherMethod( NilpotentQuotient,
  "for invariantly L-presented groups (with qs) and positive integer",
  true,
  [ IsLpGroup and HasIsInvariantLPresentation and IsInvariantLPresentation
    and HasNilpotentQuotientSystem, IsPosInt], 0,
  function(G,c)
  local Q,  # current quotient system
        QS, # old quotient system
 H, # the nilpotent quotient of <G>
       i, # loop variable
 time, # runtime
        j; # nilpotency class

  # known quotient system of <G>
  Q:=NilpotentQuotientSystem(G);
 
  # nilpotency class
  j:=MaximumList(Q.Weights,0);
 
  if c=j then 
    # the given nilpotency class <j> is already known
    H:=PcpGroupByCollectorNC(Q.Pccol);
    SetLowerCentralSeriesOfGroup(H,LPRES_LCS(Q));

    return(H);
  elif c<j then
    # the given nilpotency class <c> is already computed 
    QS:=SmallerQuotientSystem(Q,c);

    # build the nilpotent quotient with lcs
    H:=PcpGroupByCollectorNC(QS.Pccol);
    SetLowerCentralSeriesOfGroup(H,LPRES_LCS(QS));

    return(H);
  else
    if HasLargestNilpotentQuotient(G) then 
      return(LargestNilpotentQuotient(G));
    fi;

    # extend the largest known quotient system
    for i in [j+1..c] do
      QS:=ShallowCopy(Q);

      time := Runtime();

      # extend the quotient system of G/\gamma_i to G/\gamma_{i+1}
      Q:=ExtendQuotientSystem(Q);
      if Q = fail then 
        return(fail);
      fi;

      # if we couldn't extend the quotient system any more, we're finished
      if QS.Weights=Q.Weights then 
        SetLargestNilpotentQuotient(G,PcpGroupByCollectorNC(Q.Pccol));
        break;
      fi;

      if Length(Q.Weights)-Length(QS.Weights) > InfoLPRES_MAX_GENS then 
        Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
                Length(Q.Weights)-Length(QS.Weights), " generators");
      else
        Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
                Length(Q.Weights)-Length(QS.Weights),
         " generators with relative orders: ",
         RelativeOrders(Q.Pccol)
         {[Length(QS.Weights)+1..Length(Q.Weights)]});
      fi;
      Info(InfoLPRES,2,"Runtime for this step ",StringTime(Runtime()-time) );
    od;

    # store the largest nilpotent quotient system
    ResetFilterObj(G,NilpotentQuotientSystem);
    SetNilpotentQuotientSystem(G,Q);

    # build the nilpotent quotient with its lower central series attribute
    H:=PcpGroupByCollectorNC(Q.Pccol);
    SetLowerCentralSeriesOfGroup(H,LPRES_LCS(Q));

    return(H);
  fi;
  end);

############################################################################
##
#M  NilpotentQuotient ( <LpGroup>, <int> ) . . for invariant LpGroups 
##
## computes a weighted nilpotent presentation for the class-<int> quotient
## of the invariant <LpGroup>.
##
InstallOtherMethod( NilpotentQuotient,
  "for an invariantly L-presented group and a positive integer",
  true,
  [ IsLpGroup and HasIsInvariantLPresentation and IsInvariantLPresentation,
    IsPosInt ], 0,
  function(G,c)
  local Q, # current quotient system
 H, # the nilpotent quotient of <G>
 QS, # old quotient system
 i, # loop variable
 time; # runtime

  time:=Runtime();
  # Compute a confluent nilpotent presentation for G/G'
  Q:=InitQuotientSystem(G);

  if Length(Q.Weights) > InfoLPRES_MAX_GENS then
    Info(InfoLPRES,1,"Class ",1,": ",Length(Q.Weights), " generators");
  else
    Info(InfoLPRES,1,"Class ",1,": ",Length(Q.Weights),
       " generators with relative orders: ",
       RelativeOrders(Q.Pccol));
  fi;
  Info(InfoLPRES,2,"Runtime for this step ", StringTime(Runtime()-time));
  
  for i in [1..c-1] do 
    # copy the old quotient system to compare with the extended qs.
    QS:=ShallowCopy(Q);

    time:=Runtime();
    # extend the quotient system of G/\gamma_i to G/\gamma_{i+1}
    Q:=ExtendQuotientSystem(Q);
    if Q = fail then 
      return(fail);
    fi;
   
    # if we couldn't extend the quotient system any more, we're finished
    if QS.Weights=Q.Weights then 
      SetLargestNilpotentQuotient(G,PcpGroupByCollectorNC(Q.Pccol));
      break;
    fi;

    if Length(Q.Weights)-Length(QS.Weights) > InfoLPRES_MAX_GENS then 
      Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
    Length(Q.Weights)-Length(QS.Weights), " generators");
    else
      Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
    Length(Q.Weights)-Length(QS.Weights),
    " generators with relative orders: ",
    RelativeOrders(Q.Pccol)
      {[Length(QS.Weights)+1..Length(Q.Weights)]});
    fi;
    Info(InfoLPRES,2,"Runtime for this step ", StringTime(Runtime()-time));
  od;
  
  # store the largest known nilpotent quotient of <G>
  ResetFilterObj(G,NilpotentQuotientSystem);
  SetNilpotentQuotientSystem(G,Q);

  # build the nilpotent quotient with lcs
  H:=PcpGroupByCollectorNC(Q.Pccol);
  SetLowerCentralSeriesOfGroup(H,LPRES_LCS(Q));

  return(H);
  end);

############################################################################
##
#M  NilpotentQuotient ( <LpGroup> ) . . . . . . for invariant LpGroups
##
## attempts to compute the largest nilpotent quotient of <LpGroup>.
## Note that this method only terminates if <LpGroup> has a largest 
## nilpotent quotient.
##
InstallOtherMethod( NilpotentQuotient,
  "for an invariantly L-presented group with a quotient system",
  true,
  [ IsLpGroup and HasIsInvariantLPresentation and IsInvariantLPresentation
    and HasNilpotentQuotientSystem ], 0,
  function(G)
  local Q, # current quotient system
 H, # largest nilpotent quotient of <G>
 QS, # old quotient system
 time, # runtime
 i; # loop variable

  if HasLargestNilpotentQuotient(G) then 
    return(LargestNilpotentQuotient(G));
  fi;

  # Compute a confluent nilpotent presentation for G/G'
  Q:=NilpotentQuotientSystem(G);
  
  repeat
    QS:=ShallowCopy(Q);
    
    time := Runtime();
    # extend the quotient system of G/\gamma_i to G/\gamma_{i+1}
    Q:=ExtendQuotientSystem(Q);
    if Q = fail then 
      return(fail);
    fi;
  
    if QS.Weights <> Q.Weights then 
      if Length(Q.Weights)-Length(QS.Weights) > InfoLPRES_MAX_GENS then 
        Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
                 Length(Q.Weights)-Length(QS.Weights), " generators");
      else
        Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
    Length(Q.Weights)-Length(QS.Weights),
    " generators with relative orders: ",
    RelativeOrders(Q.Pccol)
      {[Length(QS.Weights)+1..Length(Q.Weights)]});
      fi; 
    else 
      Info(InfoLPRES,1,"the group has a maximal nilpotent quotient of class ",
                      Maximum(Q.Weights) );
    fi;
    Info(InfoLPRES,2,"Runtime for this step ", StringTime(Runtime()-time));

  until QS.Weights = Q.Weights;
  
  SetLargestNilpotentQuotient(G,PcpGroupByCollectorNC(Q.Pccol));

  # store the largest known nilpotent quotient of <G>
  ResetFilterObj(G,NilpotentQuotientSystem);
  SetNilpotentQuotientSystem(G,Q);

  # build the nilpotent quotient with lcs
  H:=PcpGroupByCollectorNC(Q.Pccol);
  SetLowerCentralSeriesOfGroup(H,LPRES_LCS(Q));

  return(H);
  end);

############################################################################
##
#M  NilpotentQuotient( <LpGroup> ) . . . . . . for invariant LpGroups
##
## determines the largest nilpotent quotient of <LpGroup> if it 
## has a nilpotent quotient system as an attribute.
## Note that this method only terminates if <LpGroup> has a largest 
## nilpotent quotient.
##
InstallOtherMethod( NilpotentQuotient,
  "for an invariantly L-presented group",
  true,
  [ IsLpGroup and HasIsInvariantLPresentation and IsInvariantLPresentation ], 0,
  function(G)
  local Q, # current quotient system
 H, # largest nilpotent quotient of <G>
 QS, # old quotient system
 i, # loop variable
 time; # runtime

  time:=Runtime();

  # Compute a confluent nilpotent presentation for G/G'
  Q:=InitQuotientSystem(G);

  if Length(Q.Weights) > InfoLPRES_MAX_GENS then 
    Info(InfoLPRES,1,"Class ",1,": ", Length(Q.Weights), " generators");
  else
    Info(InfoLPRES,1,"Class ",1,": ", Length(Q.Weights),
               " generators with relative orders: ", RelativeOrders(Q.Pccol));
  fi;
  Info(InfoLPRES,2,"Runtime for this step ", StringTime(Runtime()-time));
  
  repeat
    QS:=ShallowCopy(Q);
    
    time := Runtime();
    # extend the quotient system of G/\gamma_i to G/\gamma_{i+1}
    Q:=ExtendQuotientSystem(Q);
    if Q = fail then
      return(fail);
    fi;
  
    if QS.Weights <> Q.Weights then 
      if Length(Q.Weights)-Length(QS.Weights) > InfoLPRES_MAX_GENS then 
        Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
    Length(Q.Weights)-Length(QS.Weights), " generators");
      else
        Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
    Length(Q.Weights)-Length(QS.Weights),
    " generators with relative orders: ",
    RelativeOrders(Q.Pccol)
      {[Length(QS.Weights)+1..Length(Q.Weights)]});
      fi;
    fi;
    Info(InfoLPRES,2,"Runtime for this step ", StringTime(Runtime()-time));

  until QS.Weights = Q.Weights;
  
  SetLargestNilpotentQuotient(G,PcpGroupByCollectorNC(Q.Pccol));

  # store the largest known nilpotent quotient of <G>
  ResetFilterObj(G,NilpotentQuotientSystem);
  SetNilpotentQuotientSystem(G,Q);

  # build the nilpotent quotient with lcs
  H:=PcpGroupByCollectorNC(Q.Pccol);
  SetLowerCentralSeriesOfGroup(H,LPRES_LCS(Q));

  return(H);
  end);

############################################################################
##
#M  NqEpimorphismNilpotentQuotient ( <LpGroup>, <int> )
##
## computes an epimorphism from <LpGroup> onto its class-<int> quotient 
## if a nilpotent quotient system of <LpGroup> is already known.
##
InstallOtherMethod( NqEpimorphismNilpotentQuotient,
  "for an invariantly L-presented group with a quotient system and an integer",
  true,
  [ IsLpGroup and HasIsInvariantLPresentation and IsInvariantLPresentation
    and HasNilpotentQuotientSystem,
    IsPosInt], 0,
  function(G,c)
  local Q,  # current quotient system
        QS, # old quotient system
       i, # loop variable
 time, # runtime
        n; # nilpotency class

  # known quotient system of <G>
  Q:=NilpotentQuotientSystem(G);
 
  # nilpotency class of <Q>
  n:=MaximumList(Q.Weights,0);
 
  if c=n then 
    # the given nilpotency class <n> is already known
    return(Q.Epimorphism);
  elif c<n then
    # the given nilpotency class <c> is already computed 
    QS:=SmallerQuotientSystem(Q,c);
    return(QS.Epimorphism);
  else
    if HasLargestNilpotentQuotient(G) then 
      Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
       NilpotencyClassOfGroup(LargestNilpotentQuotient(G)));
      return(Q.Epimorphism);
    fi;

    # extend the largest known quotient system
    for i in [n+1..c] do
      QS:=ShallowCopy(Q);

      time := Runtime();
      # extend the quotient system of G/\gamma_i to G/\gamma_{i+1}
      Q:=ExtendQuotientSystem(Q);
      if Q = fail then 
        return(fail);
      fi;
  
      # if we couldn't extend the quotient system any more, we're finished
      if QS.Weights = Q.Weights then 
        SetLargestNilpotentQuotient(G,PcpGroupByCollectorNC(Q.Pccol));
        Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
                        Maximum(Q.Weights));
       
        break;
      else 
        if Length(Q.Weights)-Length(QS.Weights) > InfoLPRES_MAX_GENS then 
          Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
     Length(Q.Weights)-Length(QS.Weights), " generators");
        else
          Info(InfoLPRES,1,"Class ",Maximum(Q.Weights),": ",
    Length(Q.Weights)-Length(QS.Weights),
    " generators with relative orders: ",
    RelativeOrders(Q.Pccol)
      {[Length(QS.Weights)+1..Length(Q.Weights)]});
        fi;
      fi;
      Info(InfoLPRES,2,"Runtime for this step ", StringTime(Runtime()-time));
  
    od;

    # store the largest nilpotent quotient system
    ResetFilterObj(G,NilpotentQuotientSystem);
    SetNilpotentQuotientSystem(G,Q);

    return(Q.Epimorphism); 
  fi;
  end);

############################################################################
##
#M  NqEpimorphismNilpotentQuotient ( <LpGroup>, <int> )
##
## computes an epimorphism from <LpGroup> onto its class-<int> quotient.
##
InstallOtherMethod( NqEpimorphismNilpotentQuotient,
  "for an invariantly L-presented group",
  true,
  [ IsLpGroup and HasIsInvariantLPresentation and IsInvariantLPresentation,
    IsPosInt], 0,
  function(G,c)
  local H;  # nilpotent quotient <G>/gamma_<c>(<G>)

  # compute the nilpotent quotient of <G>
  H:=NilpotentQuotient(G,c);
 
  return(NilpotentQuotientSystem(G).Epimorphism);
  end);

############################################################################
##
#M  NqEpimorphismNilpotentQuotient ( <LpGroup> , <PcpGroup> ) 
##
## computes an epimorphism from the invariant LpGroup into the nilpotent 
## quotient <PcpGroup>.
##
InstallOtherMethod( NqEpimorphismNilpotentQuotient,
  "for an L-presented group and its nilpotent quotient",
  true,  
  [ IsLpGroup and HasIsInvariantLPresentation and IsInvariantLPresentation
    and HasNilpotentQuotientSystem, IsPcpGroup ], 0,
  function(G,H)
  local ftl, # collector of the PcpGroup <H>
 Q, # largest known nilpotent quotient system of G
      QS,  # nilpotent quotient system of <H>
    imgs, # images of the epimorphism
        i, # loop variable
        c, # nilpotency class of <H>
 n; # number of generators of G/gamma_c(G)

  # number of generators of the Pcp group (used to determine its qs.)
  ftl:=Collector(H);
  n:=NumberOfGenerators(ftl);

  # the largest known quotient system
  Q:=NilpotentQuotientSystem(G);
  
  # nilpotency class of <H>
  c:=Q.Weights[n];

  # determine the quotient system of <H>
  QS:=SmallerQuotientSystem(Q,c);
 
  imgs:=[];
  for i in [1..Length(QS.Imgs)] do
    if IsInt(QS.Imgs[i]) then 
      imgs[i]:=[QS.Imgs[i],1];
    else
      imgs[i]:=QS.Imgs[i];
    fi;
  od;
  imgs:=List(imgs,x->PcpElementByGenExpList(ftl,x));
  return(GroupHomomorphismByImagesNC(G,H,GeneratorsOfGroup(G),imgs));
  end);

############################################################################
##
#F  LPRES_LCS( <QS> )
##
## computes the lower central series of a nilpotent quotient given by a 
## quotient system <QS>.
##
InstallGlobalFunction( LPRES_LCS,
  function(Q)
  local weights, # weights-function of <Q>
   i,  # loop variable
   c,   # nilpotency class of <Q>
  H,  # nilpotent presentation corr. to <Q>
   gens,  # generators of <H>
  lcs;  # lower central series of <H>

  # nilpotent presentation group corr. to <Q>
  H:=PcpGroupByCollectorNC(Q.Pccol);

  # generators of <H>
  gens:=GeneratorsOfGroup(H);

  # weights function of the given quotient system
  weights:=Q.Weights;

  # nilpotency class of <Q>
  c:=MaximumList(weights,0);

  # build the lower central series
  lcs:=[];
  lcs[c+1]:=SubgroupByIgs(H,[]);
  lcs[1]:=H;
 
  for i in [2..c] do
    # the lower central series as subgroups by an induced generating system
    # with weights at least <i>
    lcs[i]:=SubgroupByIgs(H,gens{Filtered([1..Length(gens)],x->weights[x]>=i)});
  od;

  return(lcs);
  end);

############################################################################
##
#A  LargestNilpotentQuotient( <LpGroup> )
##
InstallMethod( LargestNilpotentQuotient,
  "for an L-presented group",
  true,
  [ IsLpGroup ], 0,
  NilpotentQuotient);

############################################################################
##
#A  NilpotentQuotients( <LpGroup> ) .  .  .  .  . for invariant LpGroups
##
InstallMethod( NilpotentQuotients,
  "for an invariantly L-presented group with a quotient system",
  true,
  [ IsLpGroup and HasNilpotentQuotientSystem ], 0,
  function ( G )
  local c; # nilpotency class of the known quotient system
   
  c:=MaximumList(NilpotentQuotientSystem(G).Weights,0); 
  return( List([1..c], i -> NqEpimorphismNilpotentQuotient(G,i) ) );
  end);

############################################################################
##
#M  NqEpimorphismNilpotentQuotient( <FpGroup> )
##
InstallOtherMethod( NqEpimorphismNilpotentQuotient,
  "for an FpGroup using the LPRES-package", true,
  [ IsFpGroup, IsPosInt ], 0,
  function( G, c )
  local iso,  # isomorphism from FpGroup to LpGroup
 mapi, # MappingGeneratorsImages of <iso>
 epi; # epimorphism from LpGroup onto its nilpotent quotient

  iso  := IsomorphismLpGroup( G );
  mapi := MappingGeneratorsImages( iso );
  epi  := NqEpimorphismNilpotentQuotient( Range( iso ), c );
  return( GroupHomomorphismByImages( G, Range( epi ), mapi[1], 
                        List( mapi[1], x -> Image( epi, Image( iso, x ) ) ) ) );
  end);

[ Dauer der Verarbeitung: 0.31 Sekunden  (vorverarbeitet)  ]