Quelle  rcwamono.gi   Sprache: Shell

#############################################################################
##
#W  rcwamono.gi                GAP4 Package `RCWA'                Stefan Kohl
##
##  This file contains implementations of methods and functions for computing
##  with rcwa monoids over
##
##    - the ring Z of the integers, over
##    - the ring Z^2, over
##    - the semilocalizations Z_(pi) of the ring of integers, and over
##    - the polynomial rings GF(q)[x] in one variable over a finite field.
##
##  See the definitions given in the file rcwamap.gd.
##
#############################################################################

#############################################################################
##
#S  Implications between the categories of rcwa monoids. ////////////////////
##
#############################################################################

InstallTrueMethod( IsMonoid, IsRcwaMonoid );
InstallTrueMethod( IsRcwaMonoid, IsRcwaMonoidOverZOrZ_pi );
InstallTrueMethod( IsRcwaMonoidOverZOrZ_pi, IsRcwaMonoidOverZ );
InstallTrueMethod( IsRcwaMonoidOverZOrZ_pi, IsRcwaMonoidOverZ_pi );
InstallTrueMethod( IsRcwaMonoid, IsRcwaMonoidOverZxZ );
InstallTrueMethod( IsRcwaMonoid, IsRcwaMonoidOverGFqx );

#############################################################################
##
#S  Conversion of rcwa monoids between standard and sparse representation. //
##
#############################################################################

#############################################################################
##
#M  SparseRepresentation( <M> )
##
InstallMethod( SparseRepresentation,
               "for rcwa monoids over Z (RCWA)",
               true, [ IsRcwaMonoidOverZ ], 0,

  function ( M )

    local  M_sparse;

    M_sparse := MonoidByGenerators(List(GeneratorsOfMonoid(M),SparseRep));
    if HasIsTame(M) then SetIsTame(M_sparse,IsTame(M)); fi;
    if   HasModulusOfRcwaMonoid(M)
    then SetModulusOfRcwaMonoid(M_sparse,ModulusOfRcwaMonoid(M)); fi;
    if HasSize(M) then SetSize(M_sparse,Size(M)); fi;
    return M_sparse;
  end );

#############################################################################
##
#M  StandardRepresentation( <M> )
##
InstallMethod( StandardRepresentation,
               "for rcwa monoids over Z (RCWA)",
               true, [ IsRcwaMonoidOverZ ], 0,

  function ( M )

    local  M_standard;

    M_standard := MonoidByGenerators(List(GeneratorsOfMonoid(M),
                                          StandardRep));
    if HasIsTame(M) then SetIsTame(M_standard,IsTame(M)); fi;
    if   HasModulusOfRcwaMonoid(M)
    then SetModulusOfRcwaMonoid(M_standard,ModulusOfRcwaMonoid(M)); fi;
    if HasSize(M) then SetSize(M_standard,Size(M)); fi;
    return M_standard;
  end );

#############################################################################
##
#S  Methods for `View', `Print' and `Display'. //////////////////////////////
##
#############################################################################

#############################################################################
##
#M  ViewObj( <M> ) . . . . . . . . . . . . . . . . . . . . . for rcwa monoids
##
InstallMethod( ViewObj,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid ], 0,

  function ( M )

    local  NrGens, RingString;

    RingString := RingToString(Source(One(M)));
    if   IsTrivial(M)
    then Print("Trivial rcwa monoid over ",RingString);
    else Print("<");
         if   HasIsTame(M) and not (HasSize(M) and IsInt(Size(M)))
         then if IsTame(M) then Print("tame "); else Print("wild "); fi; fi;
         NrGens := Length(GeneratorsOfMonoid(M));
         Print("rcwa monoid over ",RingString," with ",NrGens," generator");
         if NrGens > 1 then Print("s"); fi;
         if   HasSize(M) and not (HasIsTame(M) and not IsTame(M))
         then Print(", of size ",Size(M)); fi;
         Print(">");
    fi;
  end );

#############################################################################
##
#M  Print( <M> ) . . . . . . . . . . . . . . . . . . . . . . for rcwa monoids
##
InstallMethod( PrintObj,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid ], 0,

  function ( M )
    Print( "Monoid( ", GeneratorsOfMonoid( M ), " )" );
  end );

#############################################################################
##
#M  Display( <M> ) . . . . . . . . . . . . . . . . . . . . . for rcwa monoids
##
InstallMethod( Display,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid], 0,

  function ( M )

    local  RingString, g, prefix;

    RingString := RingToString(Source(One(M)));
    if   IsTrivial(M) 
    then Print("Trivial rcwa monoid over ",RingString);
         if ValueOption("NoLineFeed") <> true then Print("\n"); fi;
    else prefix := false;
         if HasIsTame(M) and not (HasSize(M) and IsInt(Size(M))) then
           if IsTame(M) then Print("\nTame "); else Print("\nWild "); fi;
           prefix := true;
         fi;
         if prefix then Print("rcwa "); else Print("\nRcwa "); fi;
         Print("monoid over ",RingString);
         if   HasSize(M) and not (HasIsTame(M) and not IsTame(M))
         then Print(" of size ",Size(M)); fi;
         Print(", generated by\n\n[\n");
         for g in GeneratorsOfMonoid(M) do Display(g); od;
         Print("]\n\n");
    fi;
  end );

#############################################################################
##
#S  The trivial rcwa monoids. ///////////////////////////////////////////////
##
#############################################################################

#############################################################################
##
#V  TrivialRcwaMonoidOverZ . . . . . . . . . . . . trivial rcwa monoid over Z
##
BindGlobal( "TrivialRcwaMonoidOverZ", Monoid( IdentityRcwaMappingOfZ ) );

#############################################################################
##
#M  TrivialSubmagmaWithOne( <M> ). . . . . . . . . . . . . . for rcwa monoids
##
InstallMethod( TrivialSubmagmaWithOne,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid ], 0,

  function ( M )

    local  triv;

    triv := Monoid(One(M));
    SetParentAttr(triv,M);
    return triv;
  end );

#############################################################################
##
#M  IsTrivial( <M> ) . . . . . . . . . . . . . . . . . . . . for rcwa monoids
##
InstallMethod( IsTrivial,
               "for rcwa monoids (RCWA)", true,
               [ IsRcwaMonoid and HasGeneratorsOfMonoid ], 0,
               M -> ForAll( GeneratorsOfMonoid( M ), IsOne ) );

#############################################################################
##
#S  The construction of the monoids Rcwa(R) of all rcwa mappings of R. //////
##
#############################################################################

#############################################################################
##
#M  RcwaCons( IsRcwaMonoid, <R> ) . . . . . . . . . . . . . . . . . Rcwa( R )
##
##  Returns the monoid which is formed by all rcwa mappings of <R>.
##
InstallMethod( RcwaCons,
               "natural Rcwa(R) (RCWA)", ReturnTrue, 
               [ IsRcwaMonoid, IsDomain ], 0,

  function ( filter, R )

    local  M, id, type, rep;

    if   IsIntegers( R ) then
      type := IsRcwaMonoidOverZ;
      rep  := 2 * IdentityRcwaMappingOfZ;
    elif IsZxZ( R ) then
      type := IsRcwaMonoidOverZxZ;
      rep  := RcwaMapping(R,[[1,0],[0,1]],[[[0,0],[[[2,0],[0,2]],[0,0],1]]]);
    elif IsZ_pi( R ) then
      type := IsRcwaMonoidOverZ_pi;
      rep  := NoninvertiblePrimes( R )[ 1 ] * One( RCWA( R ) );
    elif IsUnivariatePolynomialRing( R ) and
         IsFiniteFieldPolynomialRing( R )
    then
      type := IsRcwaMonoidOverGFqx;
      rep  := IndeterminatesOfPolynomialRing( R )[ 1 ] * One( RCWA( R ) );
    else TryNextMethod( ); fi;

    id := One( RCWA( R ) );

    M  := Objectify( NewType( FamilyObj( Monoid( id ) ),
                              type and IsAttributeStoringRep ), rec( ) );

    SetIsTrivial( M, false );
    SetOne( M, id );
    SetFilterObj( M, IsNaturalRcwa );
    SetIsWholeFamily( M, true );
    SetIsFinite( M, false );
    SetSize( M, infinity );
    SetIsTame( M, false );
    SetMultiplier( M, infinity );
    SetDivisor( M, infinity );
    SetIsCommutative( M, false );
    SetRepresentative( M, rep );
    SetName( M, Concatenation( "Rcwa(", RingToString(R), ")" ) );
    SetStructureDescription( M, Name( M ) );

    return M;
  end );

#############################################################################
##
#F  Rcwa( <R> ) . . . . . . . . . . . . . . . . . . . . . . . . . . Rcwa( R )
##
InstallGlobalFunction( Rcwa, R -> RcwaCons( IsRcwaMonoid, R ) );

#############################################################################
##
#M  IsWholeFamily . . . . . . . . . . . . . . . . . . . .  for an rcwa monoid
##
InstallMethod( IsWholeFamily,
               "for an rcwa monoid (RCWA)", true,
               [ IsRcwaMonoid ], 0, IsNaturalRcwa );

#############################################################################
##
#S  Constructing rcwa monoids: //////////////////////////////////////////////
#S  Restriction monomorphisms and induction epimorphisms. ///////////////////
##
#############################################################################

#############################################################################
##
#M  Restriction( <M>, <f> ) . . . . . . . . . . . . . . . .  for rcwa monoids
##
InstallMethod( Restriction,
               "for rcwa monoids (RCWA)", ReturnTrue,
               [ IsRcwaMonoid, IsRcwaMapping ], 0,

  function ( M, f )

    local Mf;

    if   Source(One(M)) <> Source(f) or not IsInjective(f)
    then return fail; fi;

    Mf := MonoidByGenerators(List(GeneratorsOfMonoid(M),
                                  g->Restriction(g,f)));

    if HasIsTame(M) then SetIsTame(Mf,IsTame(M)); fi;
    if HasSize(M)   then SetSize(Mf,Size(M)); fi;

    return Mf;
  end );

#############################################################################
##
#M  Induction( <M>, <f> ) . . . . . . . . . . . . . . . . .  for rcwa monoids
##
InstallMethod( Induction,
               "for rcwa monoids (RCWA)", ReturnTrue,
               [ IsRcwaMonoid, IsRcwaMapping ], 0,

  function ( M, f )

    local Mf;

    if Source(One(M)) <> Source(f) or not IsInjective(f)
      or not IsSubset(Image(f),MovedPoints(M))
    then return fail; fi;

    Mf := MonoidByGenerators(List(GeneratorsOfMonoid(M),g->Induction(g,f)));

    if HasIsTame(M) then SetIsTame(Mf,IsTame(M)); fi;
    if HasSize(M)   then SetSize(Mf,Size(M)); fi;

    return Mf;
  end );

#############################################################################
##
#S  The automorphism switching action on negative and nonnegative integers. /
##
#############################################################################

#############################################################################
##
#M  Mirrored( <M> ) . . . . . . . . . . . . . . . . . for rcwa monoids over Z
##
InstallOtherMethod( Mirrored,
                    "for rcwa monoids over Z (RCWA)",
                    true, [ IsRcwaMonoidOverZ ], 0,

  function ( M )

    local  img;

    img := MonoidByGenerators(List(GeneratorsOfMonoid(M),Mirrored));
    if HasIsTame(M) then SetIsTame(img,IsTame(M)); fi;
    if HasSize(M)   then SetSize(img,Size(M)); fi;
    return img;
  end );

#############################################################################
##
#S  Methods for the attributes and properties derived from the coefficients.
##
#############################################################################

#############################################################################
##
#M  PrimeSet( <M> ) . . . . . . . . . . . . . . . . . . . .  for rcwa monoids
##
InstallMethod( PrimeSet,
               "for rcwa monoids over Z or Z_(pi) (RCWA)", true,
               [ IsRcwaMonoid ], 0,

  function ( M )
    if   IsRcwaGroup(M)
    then return Union(List(GeneratorsOfGroup (M),PrimeSet));
    else return Union(List(GeneratorsOfMonoid(M),PrimeSet)); fi;
  end );

#############################################################################
##
#M  IsIntegral( <M> ) . . . . . . . . . . . . . . . . . . .  for rcwa monoids
##
InstallMethod( IsIntegral,
               "for rcwa monoids over Z or Z_(pi) (RCWA)", true,
               [ IsRcwaMonoid ], 0,

  function ( M )
    if   IsRcwaGroup(M)
    then return ForAll(GeneratorsOfGroup (M),IsIntegral);
    else return ForAll(GeneratorsOfMonoid(M),IsIntegral); fi;
  end );

#############################################################################
##
#M  IsClassWiseTranslating( <M> ) . . . . . . . . . . . . .  for rcwa monoids
##
InstallMethod( IsClassWiseTranslating,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid ], 0,

  function ( M )
    if   IsRcwaGroup(M)
    then return ForAll(GeneratorsOfGroup (M),IsClassWiseTranslating);
    else return ForAll(GeneratorsOfMonoid(M),IsClassWiseTranslating); fi;
  end );

#############################################################################
##
#M  IsClassWiseOrderPreserving( <M> ) . . . for rcwa monoids over Z or Z_(pi)
##
InstallMethod( IsClassWiseOrderPreserving,
               "for rcwa monoids over Z or Z_(pi) (RCWA)", true,
               [ IsRcwaMonoidOverZOrZ_pi ], 0,

  function ( M )
    if   IsRcwaGroup(M)
    then return ForAll(GeneratorsOfGroup (M),IsClassWiseOrderPreserving);
    else return ForAll(GeneratorsOfMonoid(M),IsClassWiseOrderPreserving); fi;
  end );

#############################################################################
##
#M  IsSignPreserving( <M> ) . . . . . . . . for rcwa monoids over Z or Z_(pi)
##
InstallMethod( IsSignPreserving,
               "for rcwa monoids over Z or Z_(pi) (RCWA)", true,
               [ IsRcwaMonoidOverZOrZ_pi ], 0,

  function ( M )
    if   IsRcwaGroup(M)
    then return ForAll(GeneratorsOfGroup (M),IsSignPreserving);
    else return ForAll(GeneratorsOfMonoid(M),IsSignPreserving); fi;
  end );

#############################################################################
##
#S  The support of an rcwa monoid. //////////////////////////////////////////
##
#############################################################################

#############################################################################
##
#M  MovedPoints( <M> ) . . . . . . . . . . . . . . . . . . . for rcwa monoids
##
##  Returns the set of moved points (support) of the rcwa monoid <M>.
##
InstallMethod( MovedPoints,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid ], 0,

  function ( M )
    if IsNaturalRcwa(M) then return Source(One(M)); fi;
    return Union(List(GeneratorsOfMonoid(M),MovedPoints));
  end );

#############################################################################
##
#M  Support( <M> ) . . . . . . . . . . . . . . . . . . . . . for rcwa monoids
##
InstallMethod( Support,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid ], 0,
               MovedPoints );

#############################################################################
##
#S  Finding finite orbits of rcwa monoids. //////////////////////////////////
##
#############################################################################

#############################################################################
## 
#M  ShortOrbits( <M>, <S>, <maxlng> ) . . . . . . . . . . .  for rcwa monoids
## 
InstallMethod( ShortOrbits,
               "for rcwa monoids (RCWA)", ReturnTrue,
               [ IsRcwaMonoid, IsList, IsInt ], 0,

  function ( M, S, maxlng )

    local  gens, finite, orbs, orb, oldlength, remaining, f;

    # Option "finite": assume finiteness of all orbits.
    # If "finite" is set and <maxlng> is < 0, a list of all orbits
    # which have nontrivial intersection with <S> is returned.

    finite := ValueOption("finite") = true;
    if maxlng <= 0 and not finite then TryNextMethod(); fi;

    if IsRcwaGroup(M) then gens := GeneratorsOfGroup(M);
                      else gens := GeneratorsOfMonoid(M); fi;

    orbs := []; remaining := ShallowCopy(Set(S));
    while remaining <> [] do
      if finite then
        orb := Orbit(M,remaining[1]);
        if   maxlng < 0 or Length(orb) <= maxlng
        then Add(orbs,Set(orb)); fi;
      else
        orb := [remaining[1]];
        repeat
          oldlength := Length(orb);
          for f in gens do orb := Union(orb,orb^f); od;
        until Length(orb) > maxlng or Length(orb) = oldlength;
        if Length(orb) <= maxlng then Add(orbs,Set(orb)); fi;
      fi;
      remaining := Difference(remaining,orb);
    od;
    return orbs;
  end );

InstallMethod( ShortOrbits,
               "for rcwa monoids; convert finite residue class union (RCWA)",
               ReturnTrue, [ IsRcwaMonoid, IsResidueClassUnion and IsFinite,
                             IsPosInt ], 0,
  function ( M, S, maxlng )
    return ShortOrbits(M,AsList(S),maxlng);
  end );

#############################################################################
## 
#M  ShortOrbits( <G>, <S>, <maxlng>, <maxn> ) . . . . . . . . for rcwa groups
## 
InstallMethod( ShortOrbits,
               Concatenation("for an rcwa group over Z, a set and ",
                             "two positive integers (RCWA)"),
               ReturnTrue, [ IsRcwaGroup, IsList, IsPosInt, IsPosInt ], 0,

  function ( G, S, maxlng, maxn )

    local  gens, orbs, orb, oldlength, remaining, f;

    gens := GeneratorsOfGroup(G);
    orbs := []; remaining := ShallowCopy(Set(S));
    while remaining <> [] do
      orb := [remaining[1]];
      repeat
        oldlength := Length(orb);
        for f in gens do orb := Union(orb,orb^f); od;
      until Length(orb) > maxlng or Length(orb) = oldlength
            or ForAny(orb,n->n>maxn);
      if Length(orb) = oldlength then Add(orbs,Set(orb)); fi;
      remaining := Difference(remaining,orb);
    od;
    return orbs;
  end );

#############################################################################
##
#S  Computing balls of given radius in rcwa monoids and on the //////////////
#S  underlying rings. ///////////////////////////////////////////////////////
##
#############################################################################

#############################################################################
##
#M  Ball( <M>, <f>, <r> ) . . . . . . . . for a monoid and an element thereof
##
##  As element tests can be expensive, this method does not check whether <f>
##  is indeed an element of <M>.
##
InstallMethod( Ball,
               "for a monoid and an element thereof (RCWA)", ReturnTrue,
               [ IsMonoid, IsMultiplicativeElement, IsInt ], 0,

  function ( G, f, r )

    local  ball, gens, k, spheres, maxspheresize, timeout, start;

    if   not IsCollsElms(FamilyObj(G),FamilyObj(f)) or r < 0
    then TryNextMethod(); fi;

    spheres := true in List(["spheres","Spheres"],ValueOption);
    maxspheresize := GetOption("maxspheresize",infinity,IsPosInt);
    timeout := GetOption("timeout",infinity,IsPosInt);

    start := Runtime();
    if spheres then ball := [[f]]; else ball := [f]; fi;
    if IsGroup(G) then gens := Set(GeneratorsAndInverses(G));
                  else gens := Set(GeneratorsOfMonoid(G)); fi;
    for k in [1..r] do
      if spheres then
        Add(ball,Difference(Union(List(gens,gen->ball[k]*gen)),
                            Union(ball[Maximum(1,k-1)],ball[k])));
        if Length(ball[k+1]) > maxspheresize then break; fi;
      else
        ball := Union(ball,Union(List(gens,gen->ball*gen)));
      fi;
      if Runtime() - start >= timeout then break; fi;
    od;
    return ball;
  end );

#############################################################################
##
#M  Ball( <M>, <p>, <r>, <act> ) . .  for a transformation monoid and a point
##
InstallMethod( Ball,
               "for a transformation monoid and a point (RCWA)", ReturnTrue,
               [ IsMonoid, IsObject, IsInt, IsFunction ], 0,

  function ( G, p, r, act )

    local  ball, gens, k, spheres, untilsmaller, lastsize;

    if r < 0 then TryNextMethod(); fi;
    spheres := true in List(["spheres","Spheres"],ValueOption);
    if spheres then ball := [[p]]; else ball := [p]; fi;
    lastsize := 1;
    if IsGroup(G) then gens := Set(GeneratorsAndInverses(G));
                  else gens := Set(GeneratorsOfMonoid(G)); fi;
    untilsmaller := true in List(["untilsmaller","UntilSmaller"],
                                 ValueOption);
    k := 0;
    while k < r do
      k := k + 1;
      if spheres then
        Add(ball,Difference(Union(List(gens,
                                       gen->List(ball[k],pt->act(pt,gen)))),
                            Union(ball[Maximum(1,k-1)],ball[k])));
        if ball[k+1] = [] then
          break;
        fi;
        if IsInt(p) then
          if   untilsmaller and Minimum(List(ball[k+1],AbsInt)) < AbsInt(p)
          then break; fi;
        fi;
      else
        ball := Union(ball,
                      Union(List(gens,gen->List(ball,pt->act(pt,gen)))));
        if Length(ball) = lastsize then
          break;
        fi;
        lastsize := Length(ball);
        if IsInt(p) then
          if   untilsmaller and Minimum(List(ball,AbsInt)) < AbsInt(p)
          then break; fi;
        fi;
      fi;
    od;
    return ball;
  end );

#############################################################################
##
#M  Ball( <M>, <p>, <r> ) . for a transf.-monoid and a point, action OnPoints
##
InstallMethod( Ball,
               "for a transf.-monoid and a point, action OnPoints (RCWA)",
               ReturnTrue, [ IsMonoid, IsObject, IsInt ], 0,
  function ( G, p, r )
    if   IsCollsElms(FamilyObj(G),FamilyObj(p)) or r < 0
    then TryNextMethod(); fi;
    return Ball(G,p,r,OnPoints);
  end );

#############################################################################
##
#M  RestrictedBall( <M>, <f>, <r>, <modulusbound> ) . . . .  for rcwa monoids
##
##  As element tests can be expensive, this method does not check whether <f>
##  is indeed an element of <M>.
##
InstallMethod( RestrictedBall,
               "for an rcwa monoid and an element thereof (RCWA)",
               ReturnTrue, [ IsRcwaMonoid, IsRcwaMapping,
                             IsInt, IsPosInt ], 0,

  function ( G, f, r, bound )

    local  R, gens, ball, old, new, h1, h2, h, k, spheres,
           boundaffineparts, boundnonidentityaffineparts, filter, identity;

    R := Source(f);
    if   not IsCollsElms(FamilyObj(G),FamilyObj(f))
      or not IsRing(R) or r < 0
    then TryNextMethod(); fi;
    spheres := true in List(["spheres","Spheres"],ValueOption);
    boundaffineparts := ValueOption("boundaffineparts") = true;
    boundnonidentityaffineparts :=
      ValueOption("boundnonidentityaffineparts") = true;
    filter := ValueOption("filter");
    identity := [One(R),Zero(R),One(R)];
    if spheres then ball := [[f]]; else ball := [f]; fi;
    if IsGroup(G) then gens := Set(GeneratorsAndInverses(G));
                  else gens := Set(GeneratorsOfMonoid(G)); fi;
    for k in [1..r] do
      if spheres then old := Last(ball);
                 else old := ball; fi;
      new := [];
      for h1 in old do
        for h2 in gens do
          h := h1 * h2;
          if   boundaffineparts then
            if Length(Coefficients(h)) <= bound
          then
            if filter = fail or filter(h) = true then Add(new,h); fi;
          fi;
          elif boundnonidentityaffineparts then
            if   Number(Coefficients(h),
                        c->c{[Length(c)-2..Length(c)]}<>identity) <= bound
            then
              if filter = fail or filter(h) = true then Add(new,h); fi;
            fi;
          else
            if NumberOfResidues(R,Mod(h)) <= bound then
              if filter = fail or filter(h) = true then Add(new,h); fi;
            fi;
          fi;
        od;
      od;
      if spheres then
        Add(ball,Difference(new,Union(ball[Maximum(1,k-1)],ball[k])));
        Info(InfoRCWA,1,"r = ",Length(ball)-1,": |S| = ",Length(Last(ball)));
      else
        ball := Union(ball,new);
      fi;
    od;
    return ball;
  end );

#############################################################################
##
#M  RestrictedBall( <G>, <p>, <r>, <act>, <bound> ) . for rcwa monoids over Z
#M  RestrictedBall( <G>, <p>, <r>, <bound> )  . . . . for rcwa monoids over Z
##
InstallMethod( RestrictedBall,
               "for rcwa monoids over Z or Z^2 (RCWA)",
               ReturnTrue, [ IsRcwaMonoid, IsObject,
                             IsObject, IsFunction, IsPosInt ], 0,

  function ( G, p, r, act, bound )

    local  ball, gens, k, spheres, untilsmaller;

    if not IsRcwaMonoidOverZ(G) and not IsRcwaMonoidOverZxZ(G)
      or not IsInt(p) and not (IsList(p) and ForAll(p,IsInt))
      or not IsPosInt(r) and not IsInfinity(r) or not IsPosInt(bound)
    then TryNextMethod(); fi;

    untilsmaller := true in List(["untilsmaller","UntilSmaller"],
                                 ValueOption);
    ball := [[p]];
    if IsGroup(G) then gens := Set(GeneratorsAndInverses(G));
                  else gens := Set(GeneratorsOfMonoid(G)); fi;
    k := 1;
    while k <= r do
      Add(ball,Difference(Union(List(gens,
                                     gen->List(ball[k],pt->act(pt,gen)))),
                          Union(ball[Maximum(1,k-1)],ball[k])));
      if IsInt(p) then
        ball[k+1] := Filtered(ball[k+1],n->AbsInt(n)<=bound);
        if ball[k+1] = [] then break; fi;
        if   untilsmaller and Minimum(List(ball[k+1],AbsInt)) < AbsInt(p)
        then break; fi;
      else
        ball[k+1] := Filtered(ball[k+1],
                              l->ForAll(Flat(l),n->AbsInt(n)<=bound));
      fi;
      if ball[k+1] = [] then break; fi;
      k := k + 1;
    od;
    
    ball := Filtered(ball,S->S<>[]);
    spheres := true in List(["spheres","Spheres"],ValueOption);
    if not spheres then ball := Union(ball); fi;
    return ball;
  end );

InstallMethod( RestrictedBall,
               "for rcwa monoids over Z or Z^2, delegate (RCWA)",
               ReturnTrue, [ IsRcwaMonoid, IsObject, IsObject, IsPosInt ], 0,

  function ( G, p, r, bound )
    return RestrictedBall(G,p,r,OnPoints,bound);
  end );

#############################################################################
##
#S  The modulus of an rcwa monoid, and tame rcwa monoids. ///////////////////
##
#############################################################################

#############################################################################
##
#M  Modulus( <M> ) . . . . . . . . . . . . . . . . . . . . . for rcwa monoids
##
InstallMethod( Modulus,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid ], 0,

  function ( M )

    local  R, gens, r, ball, size;

    if IsGroup(M) then TryNextMethod(); fi;
    R := Source(One(M));
    gens := GeneratorsOfMonoid(M);
    if IsIntegral(M) then return Lcm(R,List(gens,Modulus)); fi;
    r := 1; size := 1;
    repeat
      ball := Ball(M,One(M),r);
      if Length(ball) = size then return Lcm(R,List(ball,Modulus)); fi;
      if not ForAll(ball,IsTame) then return Zero(R); fi;
      size := Length(ball);
    until false;
  end );

#############################################################################
##
#M  ModulusOfRcwaMonoid( <M> ) . . . . . . . . . . . .  dispatch to `Modulus'
##
InstallMethod( ModulusOfRcwaMonoid,
               "dispatch to `Modulus' (RCWA)", true, [ IsRcwaMonoid ], 0,
               Modulus );

#############################################################################
##
#M  IsTame( <M> ) . . . . . . . . . . . . . . . . . . . . .  for rcwa monoids
##
InstallMethod( IsTame,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid ], 0,

  function ( M )
    if   not IsZero( Modulus( M ) )
    then return true;
    else SetSize( M, infinity ); return false; fi;
  end );

#############################################################################
##
#S  Computing the order of an rcwa monoid. //////////////////////////////////
##
#############################################################################

#############################################################################
##
#M  Size( <M> ) . . . . . . . . . . . . . . . . . . . . . .  for rcwa monoids
##
##  This method may run into an infinite loop if <M> is infinite.
##
InstallMethod( Size,
               "for rcwa monoids (RCWA)", true, [ IsRcwaMonoid ], 0,

  function ( M )

    local  R, gens, B2;

    if IsTrivial(M)   then return 1; fi;
    if IsRcwaGroup(M) then TryNextMethod(); fi;
    R    := Source(One(M));
    gens := GeneratorsOfMonoid(M);
    if   ForAny(gens,f->IsSurjective(f) and not IsInjective(f))
    then return infinity; fi; # surjective & not injective -> wild
    if   not ForAll(gens,f->IsFinite(Union(Loops(f)^f)))
    then return infinity; fi;
    if   ForAny(gens,f->IsBijective(f) and Order(f)=infinity)
    then return infinity; fi;
    if not ForAll(gens,IsTame) then return infinity; fi;
    B2 := Ball(M,One(M),2);
    if   not ForAll(B2,f->IsFinite(Union(Loops(f)^f)))
    then return infinity; fi;
    if   ForAny(B2,f->(IsBijective(f) and Order(f)=infinity)
                       or not IsTame(f))
    then return infinity; fi;
    return Length(AsList(M));
  end );

#############################################################################
##
#S  The membership- / submonoid test. ///////////////////////////////////////
##
#############################################################################

#############################################################################
##
#M  \in( <f>, <M> ) . . . . . . . . . . . . . . . . . . . .  for rcwa monoids
##
##  This method may run into an infinite loop if <f> is not an element of
##  the monoid <M>.
##
InstallMethod( \in,
               "for rcwa monoids (RCWA)",
               ReturnTrue, [ IsRcwaMappingOfZ, IsRcwaMonoid ], 0,

  function ( f, M )

    local  R, gens, orbs, max, r;

    if IsRcwaGroup(M) then TryNextMethod(); fi;
    Info(InfoRCWA,2,"\\in for an rcwa mapping <f> and an rcwa monoid <M>");
    R    := Source(One(M));
    gens := GeneratorsOfMonoid(M);
    if f = One(M) or f in gens then
      Info(InfoRCWA,2,"<f> = 1 or <f> lies in list of generators of <M>.");
      return true;
    fi;
    if    IsZero(Multiplier(f))
      and not ForAny(gens,g->IsZero(Multiplier(g)))
    then
     Info(InfoRCWA,2,"Mult(<f>) = 0, but Mult(<M>) <> 0.");
     return false;
    fi;
    if not ForAny(Concatenation(gens,[f]),g->IsZero(Multiplier(g))) then
      if not IsSubset(PrimeSet(M),PrimeSet(f)) then
        Info(InfoRCWA,2,"<f> and <M> have incompatible prime sets.");
        return false;
      fi;
      if not IsSubset(Factors(Product(List(gens,Multiplier))),
                      Filtered(Factors(Multiplier(f)),p->p<>1))
      then
        Info(InfoRCWA,2,"The multiplier of <f> has factors which");
        Info(InfoRCWA,2,"no multiplier of a generator of <M> has.");
        return false;
      fi;
    fi;
    if not IsSubset(Factors(Product(List(gens,Divisor))),
                    Filtered(Factors(Divisor(f)),p->p<>1))
    then
      Info(InfoRCWA,2,"The divisor of <f> has factors which");
      Info(InfoRCWA,2,"no divisor of a generator of <M> has.");
      return false;
    fi;
    if (IsIntegers(R) or IsZ_pi(R)) and IsClassWiseOrderPreserving(M)
      and not IsClassWiseOrderPreserving(f) then
      Info(InfoRCWA,2,"<M> is class-wise order-preserving, but <f> is not.");
      return false;
    fi;
    if   not IsInjective(f) and ForAll(gens,IsInjective) then
      Info(InfoRCWA,2,"<f> is not injective, ",
                      "but all generators of <M> are.");
      return false;
    fi;
    if   not IsSurjective(f) and ForAll(gens,IsSurjective) then
      Info(InfoRCWA,2,"<f> is not surjective, ",
                      "but all generators of <M> are.");
      return false;
    fi;
    if not IsSubset(Support(M),Support(f)) then
      Info(InfoRCWA,2,"Support(<f>) is not a subset of Support(<M>).");
      return false;
    fi;
    if IsIntegers(R) and IsSignPreserving(M) and not IsSignPreserving(f) then
      Info(InfoRCWA,2,"<M> fixes the nonnegative integers setwise,");
      Info(InfoRCWA,2,"but <f> does not.");
      return false;
    fi;
    if IsTame(M) then
      if Modulus(M) mod Modulus(f) <> 0 then
        Info(InfoRCWA,2,"Mod(<f>) does not divide Mod(<M>).");
        return false;
      fi;
      if not IsTame(f) then
        Info(InfoRCWA,2,"<M> is tame, but <f> is wild.");
        return false;
      fi;
      if IsFinite(M) and IsBijective(f) and Order(f) = infinity then
        Info(InfoRCWA,2,"<M> is finite, but <f> has infinite order.");
        return false;
      fi;
    fi;
    orbs := ShortOrbits(M,Intersection(Support(M),[-100..100]),50);
    if orbs <> [] and not ForAll(orbs,orb->IsSubset(orb,orb^f)) then
      Info(InfoRCWA,2,"<f> does not leave some finite orbit of <M> ",
                      "invariant.");
      return false;
    fi;
    Info(InfoRCWA,2,"Trying to find <f> in balls around 1 ...");
    r := 1;
    repeat
      r := r + 1;
      if f in Ball(M,One(M),r) then
        Info(InfoRCWA,2,"<f> lies in the ball with radius ",r,".");
        return true;
      fi;
    until false;
  end );

#############################################################################
##
#M  IsSubset( <M>, <N> ) . . . . . . . . . . . . . . . . for two rcwa monoids
##
##  This method checks for a submonoid relation.
##
InstallMethod( IsSubset,
               "for two rcwa monoids (RCWA)", ReturnTrue,
               [ IsRcwaMonoid, IsRcwaMonoid ], 0,

  function ( M, N )

    local  gensM, gensN, Mmultzero, Nmultzero;

    gensM := GeneratorsOfMonoid(M); gensN := GeneratorsOfMonoid(N);
    if IsSubset(gensM,gensN) then return true; fi;
    Mmultzero := ForAny(gensM,f->IsZero(Multiplier(f)));
    Nmultzero := ForAny(gensN,f->IsZero(Multiplier(f)));
    if Nmultzero and not Mmultzero then return false; fi;
    if not Mmultzero and not Nmultzero then
      if not IsSubset(Union(Factors(Product(List(gensM,Multiplier))),[1]),
                            Factors(Product(List(gensN,Multiplier))))
      then return false; fi;
    fi;
    if not IsSubset(Union(Factors(Product(List(gensM,Divisor))),[1]),
                          Factors(Product(List(gensN,Divisor))))
    then return false; fi;
    if not IsSubset(Support(M),Support(N)) then return false; fi;
    if IsTame(M) and not IsTame(N) then return false; fi;
    return ForAll(GeneratorsOfMonoid(N),f->f in M);
  end );

#############################################################################
##
#M  \=( <M>, <N> ) . . . . . . . . . . . . . . . . . . . for two rcwa monoids
##
InstallMethod( \=,
               "for two rcwa monoids (RCWA)", ReturnTrue,
               [ IsRcwaMonoid, IsRcwaMonoid ], 0,

  function ( M, N )
    return IsSubset( M, N ) and IsSubset( N, M );
  end );

#############################################################################
##
#M  IsSubset( <G>, Rcwa(R) ) . . . . . . . . .  for an rcwa group and Rcwa(R)
##
InstallMethod( IsSubset,
               "for an rcwa group and Rcwa(R) (RCWA)", ReturnTrue,
               [ IsRcwaGroup, IsNaturalRcwa ], SUM_FLAGS, ReturnFalse );

#############################################################################
##
#E  rcwamono.gi . . . . . . . . . . . . . . . . . . . . . . . . . . ends here