Quelle nq_non.gi Sprache: unbekannt

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

############################################################################
##
#M  NilpotentQuotient ( <LpGroup>, <int> ) . . . for non-inv LpGroups
##
## computes a polycyclic presentation for the class-<int> quotient of
## <LpGroup>.
##
InstallOtherMethod( NilpotentQuotient,
  "for an L-presented group and a positive integer",
  true,
  [ IsLpGroup, IsPosInt ],0,
  function(G,c)
  local InvLp, # ascending L-presentation
i, # loop variable
Q, # current quotient system
QS, # old quotient system
time, # runtime
NQs; # nilpotent quotients of <G> (NilpotentQuotients)

  # InitQuotientSystem works also for non-invariantly LpGroups
  Q:=InitQuotientSystem(G);
  NQs:= [ Q.Epimorphism ];
  SetNilpotentQuotients(G,NQs);

  # an underlying invariant L-presentation
  InvLp:=UnderlyingInvariantLPresentation(G);

  # if the underlying invariant L-presentation was set manually
  if not HasIsInvariantLPresentation( InvLp ) then
    SetIsInvariantLPresentation( InvLp, true );
  fi;

  # if the underlying invariant L-presentation is <G> itself
  if Length( FixedRelatorsOfLpGroup( G ) ) =
     Length( FixedRelatorsOfLpGroup( InvLp ) )  then
    SetIsInvariantLPresentation( G, true );
    return( NilpotentQuotient( G, c ) );
  fi;

  time := Runtime();

  # a weighted nilpotent quotient system for the abelian quotient of <InvLp>
  Q:=InitQuotientSystem(InvLp);

  # store the largest nilpotent quotient system of <InvLp>
  SetNilpotentQuotientSystem(InvLp,Q);

  if c > 1 then
    if Length(Q.Weights) > InfoLPRES_MAX_GENS then
      Info(InfoLPRES, 1,"Class InvLpGroup ", Maximum(Q.Weights),": ",
   Length(Q.Weights), " generators");
    else
      Info(InfoLPRES, 1,"Class InvLpGroup ",Maximum(Q.Weights),": ",
    Length(Q.Weights),
   " generators with relative orders: ",
   RelativeOrders(Q.Pccol));
    fi;
  fi;
  Info(InfoLPRES,2,"Runtime for the invariant step ",StringTime(Runtime()-time));

  for i in [2..c] do
    QS:=ShallowCopy(Q);

    time := Runtime();

    # extend the weighted nilpotent quotient system of <InvLp>/\gamma_i(<InvLp>)
    # to a weighted nilpotent quotient system of <InvLp>/\gamma_{i+1}(<InvLp>)
    Q:=ExtendQuotientSystem(Q);
    if Q = fail then
      Error("the underlying invariant LpGroup is not invariant");
    fi;

    if QS.Weights <> Q.Weights then
      if Length(Q.Weights)-Length(QS.Weights) > InfoLPRES_MAX_GENS then
        Info(InfoLPRES,1,"Class InvLpGroup ",Maximum(Q.Weights),": ",
   Length(Q.Weights)-Length(QS.Weights), " generators");
      else
        Info(InfoLPRES,1,"Class InvLpGroup ",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 the invariant step ",StringTime(Runtime()-time));

    if QS.Weights = Q. Weights then
      # quotient system of the invariant L-presentation terminated
      if not IsBound(NilpotentQuotients(G)[i-1]) then
        Error("unbound entry in NilpotentQuotients");
      else
        SetLargestNilpotentQuotient(G, Range(NilpotentQuotients(G)[i-1]) );
        Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
                 Maximum(Q.Weights));
        return( LargestNilpotentQuotient(G) );
      fi;
    elif LPRES_TerminatedNonInvariantNQ(G,Q) then
      if not IsBound(NilpotentQuotients(G)[i-1]) then
        Error("unbound entry in NilpotentQuotients");
      else
        SetLargestNilpotentQuotient(G, Range(NilpotentQuotients(G)[i-1]));
        Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
             NilpotencyClassOfGroup( Range(NilpotentQuotients(G)[i-1])));
        return(LargestNilpotentQuotient(G));
      fi;
    else
      # largest quotient system of the invariant L-presentation
      ResetFilterObj(UnderlyingInvariantLPresentation(G),
   NilpotentQuotientSystem);
      SetNilpotentQuotientSystem(UnderlyingInvariantLPresentation(G),Q);
    fi;
    Info(InfoLPRES,2,"Runtime for the whole step ",StringTime(Runtime()-time));
  od;

  return( Range(NilpotentQuotients(G)[c]) );
  end);

############################################################################
##
#M  NilpotentQuotient ( <LpGroup>, <int> ) . .  for non-inv. LpGroups
##
## computes a polycyclic presentation for the class-<int> quotient of
## <LpGroup> if the group has NilpotentQuotients as attribute.
##
InstallOtherMethod( NilpotentQuotient,
  "for an L-presented group with a quotient system and a positive integer",
  true,
  [ IsLpGroup and HasNilpotentQuotients, IsPosInt ], 0,
  function(G,c)
  local Q, # largest known quotient system
i, # loop variable
QS, # smaller quotient system
      EpiInv, # epimorphism from the ascending LpGroup into <H>
  H, # nilpotent quotient of <InvLp>
        fam, # family of elements in <G>
U, # normal subgroup of the images of the (unit.) relators
      Epi,MGI,# epimorphism from the LpGroup <G> into <H>/<U>
NQs, # nilpotent quotients of <G> (NilpotentQuotients)
  n,  # nilpotency class of the largest known quotient system
time, # runtime
nat; # natural homomorphism <H> -> <H>/<U>

  # check whether this quotient is already known
  if IsBound(NilpotentQuotients(G)[c]) then
    return(Range(NilpotentQuotients(G)[c]));
  elif HasLargestNilpotentQuotient(G) and Length(NilpotentQuotients(G)) < c then
    Info( InfoLPRES, 1, "The group has a largest nilpotent quotient of class ",
                      NilpotencyClassOfGroup(LargestNilpotentQuotient(G)) );
    return( LargestNilpotentQuotient(G) );
  fi;

  # restore the largest known quotient system of the underlying invariant L-pres
  Q:=NilpotentQuotientSystem(UnderlyingInvariantLPresentation(G));

  # nilpotency class of <Q>
  n:=Maximum(Q.Weights);

  NQs:=NilpotentQuotients(G);
  if NilpotencyClassOfGroup( Range( NQs[Length(NQs)] ) ) < n then
    Error("may not occur");
  fi;

  if n < c then
    if HasLargestNilpotentQuotient(G) then
      Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
               NilpotencyClassOfGroup(LargestNilpotentQuotient(G)));
      return(LargestNilpotentQuotient(G));
    fi;
    for i in [n+1..c] do
      QS:=ShallowCopy(Q);

      time := Runtime();

      # extend the weighted nilpotent quotient system of InvLp/\gamma_i(InvLp)
      # to a weighted nilpotent quotient system of InvLp/\gamma_{i+1}(InvLp)
      Q:=ExtendQuotientSystem(Q);
      if Q = fail then
        Error("the underlying invariant LpGroup is not invariant");
      fi;

      if QS.Weights <> Q.Weights then
        if Length(Q.Weights)-Length(QS.Weights) > InfoLPRES_MAX_GENS then
          Info(InfoLPRES,1,"Class InvLpGroup ",Maximum(Q.Weights),": ",
   Length(Q.Weights)-Length(QS.Weights), " generators");
        else
          Info(InfoLPRES,1,"Class InvLpGroup ",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 the invariant step ",StringTime(Runtime()-time));

      if QS.Weights = Q.Weights then
        # the quotient system of the ascending presentation terminated
        if not IsBound(NilpotentQuotients(G)[i-1]) then
          Error("unbound entry in NilpotentQuotients");
        else
   SetLargestNilpotentQuotient(G,Range(NilpotentQuotients(G)[i-1]));
    Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
     Maximum(Q.Weights));
    return(LargestNilpotentQuotient(G));
        fi;
      elif LPRES_TerminatedNonInvariantNQ(G,Q) then
        if not IsBound(NilpotentQuotients(G)[i-1]) then
          Error("unbound entry in NilpotentQuotients");
        else
   SetLargestNilpotentQuotient(G,Range(NilpotentQuotients(G)[i-1]));
    Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
        NilpotencyClassOfGroup( Range( NilpotentQuotients(G)[i-1]) ) );
    return(LargestNilpotentQuotient(G));
        fi;
      else
        # largest quotient system of the underl. invariant L-presentation
        ResetFilterObj(UnderlyingInvariantLPresentation(G),
    NilpotentQuotientSystem);
        SetNilpotentQuotientSystem(UnderlyingInvariantLPresentation(G),Q);
      fi;
      Info(InfoLPRES,2,"Runtime for the whole step ",StringTime(Runtime()-time));
    od;

    return( Range(NilpotentQuotients(G)[c]) );
  else
    # all known smaller quotients are stored in `NilpotentQuotients'
    Error(" may not occur (redundant in LPRES 0.03) ");
  fi;
  end);

############################################################################
##
#M  NilpotentQuotient( <LpGroup> ) . . . . for non-invariant LpGroups
##
## attempts to compute the largest nilpotent quotient of <LpGroup>.
## Note that this method will only terminate if <LpGroup> has a largest
## nilpotent quotient!
##
InstallOtherMethod( NilpotentQuotient,
  "for L-presented groups",
  true,
  [ IsLpGroup ],0,
  function(G)
  local InvLp, # ascending L-presentation
        Q, # current quotient system
QS, # old quotient system
      EpiInv, # epimorphism from the ascending LpGroup into <H>
H, # nilpotent quotient of <InvLp>
        fam, # family of elements in <G>
U, # normal subgroup of the images of the (unit.) relators
   nat, # natural homomorphism <H> -> <H>/<U>
      Epi,MGI,# epimorphism from the ascending LpGroup into <H>/<U>
       c, # nilpotency class of the largest nilpotent quotient
        NQs, # nilpotent quotients with epimorphisms (NilpotentQuotients)
time; # runtime


  # InitQuotientSystem works also for non-invariantly LpGroups
  Q:=InitQuotientSystem(G);
  NQs:=[ Q.Epimorphism ];
  SetNilpotentQuotients(G,NQs);

  # an underlying invariant L-presentation
  InvLp := UnderlyingInvariantLPresentation(G);

  # if the underlying invariant L-presentation was set manually
  if not HasIsInvariantLPresentation( InvLp ) then
    SetIsInvariantLPresentation( InvLp, true );
  fi;

  # if the underlying invariant L-presentation is <G> itself
  if Length( FixedRelatorsOfLpGroup( G ) ) =
     Length( FixedRelatorsOfLpGroup( InvLp ) )  then
    SetIsInvariantLPresentation( G, true );
    return( NilpotentQuotient( G ) );
  fi;

  time:=Runtime();

  # a weighted nilpotent quotient system for the abelian quotient of <InvLp>
  Q:=InitQuotientSystem(InvLp);

  # store the largest nilpotent quotient system of <InvLp>
  SetNilpotentQuotientSystem(InvLp,Q);

  if Length(Q.Weights) > InfoLPRES_MAX_GENS then
    Info(InfoLPRES, 1,"Class InvLpGroup ",Maximum(Q.Weights),": ",
   Length(Q.Weights), " generators");
  else
    Info(InfoLPRES, 1,"Class InvLpGroup ",Maximum(Q.Weights),": ",
   Length(Q.Weights),
   " generators with relative orders: ",
   RelativeOrders(Q.Pccol));
  fi;
  Info(InfoLPRES,2,"Runtime for the invariant step ",StringTime(Runtime()-time));

  repeat
    QS:=ShallowCopy(Q);

    time := Runtime();

    # extend the weighted nilpotent quotient system of <InvLp>/\gamma_i(<InvLp>)
    # to a weighted nilpotent quotient system of <InvLp>/\gamma_{i+1}(<InvLp>)
    Q:=ExtendQuotientSystem(Q);
    if Q = fail then
      Error("the underlying invariant LpGroup is not invariant");
    fi;

    if QS.Weights <> Q.Weights then
      if Length(Q.Weights)-Length(QS.Weights) > InfoLPRES_MAX_GENS then
        Info(InfoLPRES,1,"Class InvLpGroup ",Maximum(Q.Weights),": ",
   Length(Q.Weights)-Length(QS.Weights), " generators");
      else
        Info(InfoLPRES,1,"Class InvLpGroup ",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 the invariant step ",StringTime(Runtime()-time));

    if LPRES_TerminatedNonInvariantNQ(G,Q) then
      Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
        NilpotencyClassOfGroup(
        Range(NilpotentQuotients(G)[Maximum(Q.Weights)-1])));
      SetLargestNilpotentQuotient(G,Range(NilpotentQuotients(G)
      [Maximum(Q.Weights)-1]));
      return(LargestNilpotentQuotient(G));
    fi;
    Info(InfoLPRES,2,"Runtime for the whole step  ",StringTime(Runtime()-time));

  until QS.Weights = Q.Weights;

  Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
    Maximum(Q.Weights));

  SetLargestNilpotentQuotient( G, Range(NilpotentQuotients(G)
      [Maximum(Q.Weights)]));
  return(LargestNilpotentQuotient(G));
  end);

############################################################################
##
#M  NilpotentQuotient( <LpGroup> ) . . . . . . . for non-inv LpGroups
##
## attempts to compute the largest nilpotent quotient of <LpGroup> if
## it has the attribute `NilpotentQuotients'.
## Note that this method only terminates if <LpGroup> has a largest
## nilpotent quotient.
##
InstallOtherMethod( NilpotentQuotient,
  "for an L-presented group with a quotient system",
  true,
  [ IsLpGroup and HasNilpotentQuotients ], 0,
  function(G)
  local Q, # current quotient system
InvLp, # the underlying invariant L-presentation
QS, # old quotient system
time, # runtime
        NQs; # nilpotent quotients with epimorphisms (NilpotentQuotients)

  # the largest nilpotent quotient has been computed
  if HasLargestNilpotentQuotient(G) then
    Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
   NilpotencyClassOfGroup(LargestNilpotentQuotient(G)));
    return(LargestNilpotentQuotient(G));
  fi;

  # largest known nilpotent quotient system of the underlying invariant LpGroup
  InvLp:=UnderlyingInvariantLPresentation(G);
  Q:=NilpotentQuotientSystem(InvLp);

  # is the nilpotency class of the largest quotient system too large
  NQs := NilpotentQuotients(G);
  if NilpotencyClassOfGroup(Range(NQs[Length(NQs)])) < Maximum(Q.Weights) then
    Error("may not occur");
  fi;

  repeat
    QS:=ShallowCopy(Q);

    time := Runtime();

    # extend the weighted nilpotent quotient system of <InvLp>/\gamma_i(<InvLp>)
    # to a weighted nilpotent quotient system of <InvLp>/\gamma_{i+1}(<InvLp>)
    Q:=ExtendQuotientSystem(Q);
    if Q = fail then
      Error("the underlying invariant LpGroup is not invariant");
    fi;

    if QS.Weights <> Q.Weights then
      if Length(Q.Weights)-Length(QS.Weights) > InfoLPRES_MAX_GENS then
        Info(InfoLPRES,1,"Class InvLpGroup ",Maximum(Q.Weights),": ",
   Length(Q.Weights)-Length(QS.Weights), " generators");
      else
        Info(InfoLPRES,1,"Class InvLpGroup ",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 the invariant step ",StringTime(Runtime()-time));

    if LPRES_TerminatedNonInvariantNQ(G,Q) then
      if not IsBound(NilpotentQuotients(G)[Maximum(Q.Weights)-1]) then
        Error( "unbound entry in NilpotentQuotients");
      else
        SetLargestNilpotentQuotient(G,
           Range(NilpotentQuotients(G)[Maximum(Q.Weights)-1]));
        Info( InfoLPRES,1 ,"Largest nilpotent quotient of class ",
       NilpotencyClassOfGroup( LargestNilpotentQuotient(G) ) );
        return(LargestNilpotentQuotient(G));
      fi;
    fi;

  until QS.Weights = Q.Weights;

  Info(InfoLPRES,1,"Largest nilpotent quotient of class ",
    Maximum(Q.Weights));

  SetLargestNilpotentQuotient(G,
     Range(NilpotentQuotients(G)[Maximum(Q.Weights)]));
  return(LargestNilpotentQuotient(G));
  end);

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

  H:=NilpotentQuotient(G,c);
  if not HasLargestNilpotentQuotient( G ) then
    return(NilpotentQuotients(G)[c]);
  else
    return(NilpotentQuotients(G)[Length(NilpotentQuotients(G))]);
  fi;
  end);

############################################################################
##
#M  NqEpimorphismNilpotentQuotient ( <LpGroup>, <int> )
##
## computes an epimorphism from <LpGroup> onto its class-<int> quotient
## if <LpGroup> has the attribute `NilpotentQuotients'.
##
InstallOtherMethod( NqEpimorphismNilpotentQuotient,
  "for an L-presented group with a quotient system",
  true,
  [ IsLpGroup and HasNilpotentQuotients, IsPosInt ], 0,
  function(G,c)
  local Q, # largest known nilpotent quotient system of <G>
H,  # nilpotent quotient of <G>
        n, # nilpotency class of the largest nilp. qs. of <G>
  NQs; # all known nilpotent quotients of <G>

  if IsBound(NilpotentQuotients(G)[c]) then
    return(NilpotentQuotients(G)[c]);
  elif HasLargestNilpotentQuotient(G) and Length(NilpotentQuotients(G)) < c then
    Info( InfoLPRES, 1, "The group has a largest nilpotent quotient of class ",
          NilpotencyClassOfGroup(LargestNilpotentQuotient(G)) );
    return(LargestNilpotentQuotient(G));
  else
    H:=NilpotentQuotient(G,c);
    if not HasLargestNilpotentQuotient( G ) then
      return(NilpotentQuotients(G)[c]);
    else
      return(NilpotentQuotients(G)[Length(NilpotentQuotients(G))]);
    fi;
  fi;
  end);

############################################################################
##
#M  NqEpimorphismNilpotentQuotient ( <LpGroup>, <PcpGroup> )
##
## computes an epimorphism from <LpGroup> onto its nilpotent quotient
## <PcpGroup>. The <PcpGroup> must be an image of an epimorphism from
## the list `NilpotentQuotients'.
##
InstallOtherMethod( NqEpimorphismNilpotentQuotient,
  "for an L-presented group",
  true,
  [ IsLpGroup and HasNilpotentQuotients, IsPcpGroup ], 0,
  function(G,H)
  local i,  # loop variable
NQs; # all known nilpotent quotients of <G>

  # the known nilpotent quotients of the group <G>
  NQs:=NilpotentQuotients(G);

  for i in [1..Length(NQs)] do
    if IsBound( NQs[i] ) and Range(NQs[i]) = H then
      return( NQs[i] );
    fi;
  od;
  Error("<H> must be nilpotent quotient of <G>");
  end);

############################################################################
##
#M  NqEpimorphismNilpotentQuotient ( <LpGroup> )
##
## computes an epimorphism from <LpGroup> onto its largest nilpotent quotient
## if it exists; otherwise, this method will not terminate!
##
InstallOtherMethod( NqEpimorphismNilpotentQuotient,
  "for an L-presented group",
  true,
  [ IsLpGroup ], 0,
  function(G)
  local c; # nilpotency class of the largest nilpotent quotient

  c:=NilpotencyClassOfGroup(LargestNilpotentQuotient(G));
  return(NilpotentQuotients(G)[c]);
  end);

############################################################################
##
#M  NqEpimorphismNilpotentQuotient ( <LpGroup> )
##
## computes an epimorphism from <LpGroup> onto the largest nilpotent
## quotient.
## Note that this method will only terminate if <LpGroup> has a largest
## nilpotent quotient.
##
InstallOtherMethod( NqEpimorphismNilpotentQuotient,
  "for L-presented groups",
  true,
  [ IsLpGroup and HasNilpotentQuotients ], 0,
  function(G)
  local c; # nilpotency class of the largest nilpotent quotient

  c:=NilpotencyClassOfGroup(LargestNilpotentQuotient(G));
  return(NilpotentQuotients(G)[c]);
  end);

############################################################################
##
#F  LPRES_TerminatedNonInvariantNQ( <LpGroup>, <QS> )
##
## checks whether the non-invariant NQ already terminated.
##
InstallGlobalFunction( LPRES_TerminatedNonInvariantNQ,
  function(G,Q)
  local H, # nilpotent quotient of the invariant LpGroup
EpiInv, # epimorphism G->H
fam, # family of LpGroup-elements
U, # normal subgroup of H generated by the images of the fixed rels
nat, # natural homomorphism H->H/U
c, # nilpotency class of <Q>
MGI, # mapping generators images of EpiInv*nat
Epi, # epimorphism G->H/U
NQs; # new NilpotentQuotients

   # largest quotient system of the invariant L-presentation
   ResetFilterObj(UnderlyingInvariantLPresentation(G),NilpotentQuotientSystem);
   SetNilpotentQuotientSystem(UnderlyingInvariantLPresentation(G),Q);

   # nilpotent quotient of the ascending L-presentation
   H:=PcpGroupByCollectorNC(Q.Pccol);

   # the epimorphism from the non-ascending presentation into <H>
   EpiInv:=GroupHomomorphismByImagesNC(G,H,
      GeneratorsOfGroup(G),
                  MappingGeneratorsImages(Q.Epimorphism)[2]);

   # relators of G are objects of the free group of G
   fam:=ElementsFamily(FamilyObj(G));

   # determine the quotient of the non-ascending presentation
   U:=NormalClosure(H,Subgroup(H,List(FixedRelatorsOfLpGroup(G),
             x->ElementOfLpGroup(fam,x)^EpiInv)));

   # natural homomorphism H -> H/U
   nat:=NaturalHomomorphismByNormalSubgroup(H,U);

   # nilpotency class of <Q>
   c:=Maximum(Q.Weights);

   if NilpotencyClassOfGroup( Image(nat) ) < c then
     return(true);
   fi;

   # the epimorphism G -> H/U
   MGI:=MappingGeneratorsImages(EpiInv*nat);
   Epi:=GroupHomomorphismByImagesNC(G,Image(nat),MGI[1],MGI[2]);

   # store the epimorphism and the nilpotent quotient in NilpotentQuotients
   NQs:=ShallowCopy(NilpotentQuotients(G));
   NQs[c]:= Epi;
   ResetFilterObj(G,NilpotentQuotients);
   SetNilpotentQuotients(G,NQs);

   return(false);
   end);

Quelle nq_non.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.33 Sekunden (vorverarbeitet) ]