chap4.txt

  
  4 Residue-Class-Wise Affine Monoids
  
  In  this  short  chapter, we describe how to compute with residue-class-wise
  affine  monoids.  Residue-class-wise  affine  monoids,  or  rcwa monoids for
  short, are monoids whose elements are residue-class-wise affine mappings.
  
  
  4.1 Constructing residue-class-wise affine monoids
  
  As  any  other  monoids  in  GAP,  residue-class-wise  affine monoids can be
  constructed by Monoid or MonoidByGenerators.
  
    Example  
    
    gap> M := Monoid(RcwaMapping([[ 0,1,1],[1,1,1]]),
    >                RcwaMapping([[-1,3,1],[0,2,1]]));
    <rcwa monoid over Z with 2 generators>
    gap> Size(M);
    11
    gap> Display(MultiplicationTable(M));
    [ [   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11 ], 
      [   2,   8,   5,  11,   8,   3,  10,   5,   2,   8,   5 ], 
      [   3,  10,  11,   5,   5,   5,   8,   8,   8,   2,   3 ], 
      [   4,   9,   6,   8,   8,   8,   5,   5,   5,   7,   4 ], 
      [   5,   8,   5,   8,   8,   8,   5,   5,   5,   8,   5 ], 
      [   6,   7,   4,   8,   8,   8,   5,   5,   5,   9,   6 ], 
      [   7,   5,   8,   6,   5,   4,   9,   8,   7,   5,   8 ], 
      [   8,   5,   8,   5,   5,   5,   8,   8,   8,   5,   8 ], 
      [   9,   5,   8,   4,   5,   6,   7,   8,   9,   5,   8 ], 
      [  10,   8,   5,   3,   8,  11,   2,   5,  10,   8,   5 ], 
      [  11,   2,   3,   5,   5,   5,   8,   8,   8,  10,  11 ] ]
    
  
  
  There  are  methods for the operations View, Display, Print and String which
  are  applicable  to  rcwa  monoids.  All  rcwa  monoids  over  a  ring R are
  submonoids  of Rcwa(R). The monoid Rcwa(R) itself is not finitely generated,
  thus  cannot  be  constructed as described above. It is handled as a special
  case:
  
  4.1-1 Rcwa
  
  Rcwa( R )  function
  Returns:  the  monoid  Rcwa(R)  of all residue-class-wise affine mappings of
            the ring R.
  
    Example  
    
    gap> RcwaZ := Rcwa(Integers);
    Rcwa(Z)
    gap> IsSubset(RcwaZ,M);
    true
    
  
  
  In  our  methods  to  construct  rcwa groups, two kinds of mappings played a
  crucial role, namely the restriction monomorphisms (cf. Restriction (3.1-6))
  and  the  induction  epimorphisms  (cf. Induction  (3.1-7)). The restriction
  monomorphisms  extend  in  a  natural  way  to  the monoids Rcwa(R), and the
  induction  epimorphisms  have corresponding generalizations, also. Therefore
  the  operations  Restriction and Induction can be applied to rcwa monoids as
  well:
  
    Example  
    
    gap> M2 := Restriction(M,2*One(Rcwa(Integers)));
    <rcwa monoid over Z with 2 generators, of size 11>
    gap> Support(M2);
    0(2)
    gap> Action(M2,ResidueClass(1,2));
    Trivial rcwa group over Z
    gap> Induction(M2,2*One(Rcwa(Integers))) = M;
    true
    
  
  
  
  4.2 Computing with residue-class-wise affine monoids
  
  There  is  a  method  for  Size  which computes the order of an rcwa monoid.
  Further  there  is a method for in which checks whether a given rcwa mapping
  lies  in  a  given  rcwa monoid (membership test), and there is a method for
  IsSubset which checks for a submonoid relation.
  
  There  are  also methods for Support, Modulus, IsTame, PrimeSet, IsIntegral,
  IsClassWiseOrderPreserving and IsSignPreserving available for rcwa monoids.
  
  The  support of an rcwa monoid is the union of the supports of its elements.
  The  modulus  of  an rcwa monoid is the lcm of the moduli of its elements in
  case  such  an  lcm exists and 0 otherwise. An rcwa monoid is called tame if
  its  modulus is nonzero, and wild otherwise. The prime set of an rcwa monoid
  is  the  union  of  the prime sets of its elements. An rcwa monoid is called
  integral,  class-wise  order-preserving  or  sign-preserving  if  all of its
  elements are so.
  
    Example  
    
    gap> f1 := RcwaMapping([[-1, 1, 1],[ 0,-1, 1]]);;
    gap> f2 := RcwaMapping([[ 1,-1, 1],[-1,-2, 1],[-1, 2, 1]]);; 
    gap> f3 := RcwaMapping([[ 1, 0, 1],[-1, 0, 1]]);; 
    gap> N := Monoid(f1,f2,f3);;
    gap> Size(N);
    366
    gap> List([Monoid(f1,f2),Monoid(f1,f3),Monoid(f2,f3)],Size);
    [ 96, 6, 66 ]
    gap> f1*f2*f3 in N;
    true
    gap> IsSubset(N,M);
    false
    gap> IsSubset(N,Monoid(f1*f2,f3*f2));
    true
    gap> Support(N);
    Integers
    gap> Modulus(N);
    6
    gap> IsTame(N) and IsIntegral(N);
    true
    gap> IsClassWiseOrderPreserving(N) or IsSignPreserving(N);
    false
    gap> Collected(List(AsList(N),Image)); # The images of the elements of N.
    [ [ Integers, 2 ], [ 1(2), 2 ], [ Z \ 1(3), 32 ], [ 0(6), 44 ], 
      [ 0(6) U 1(6), 4 ], [ Z \ 4(6) U 5(6), 32 ], [ 0(6) U 2(6), 4 ], 
      [ 0(6) U 5(6), 4 ], [ 1(6), 44 ], [ 1(6) U [ -1 ], 2 ], 
      [ 1(6) U 3(6), 4 ], [ 1(6) U 5(6), 40 ], [ 2(6), 44 ], 
      [ 2(6) U 3(6), 4 ], [ 3(6), 44 ], [ 3(6) U 5(6), 4 ], [ 5(6), 44 ], 
      [ 5(6) U [ 1 ], 2 ], [ [ -5 ], 1 ], [ [ -4 ], 1 ], [ [ -3 ], 1 ], 
      [ [ -1 ], 1 ], [ [ 0 ], 1 ], [ [ 1 ], 1 ], [ [ 2 ], 1 ], [ [ 3 ], 1 ], 
      [ [ 5 ], 1 ], [ [ 6 ], 1 ] ]
    
  
  
  Finite forward orbits under the action of an rcwa monoid can be found by the
  operation ShortOrbits:
  
  4.2-1 ShortOrbits
  
  ShortOrbits( M, S, maxlng )  method
  Returns:  a  list of finite forward orbits of the rcwa monoid M of length at
            most maxlng which start at points in the set S.
  
    Example  
    
    gap> ShortOrbits(M,[-5..5],20);
    [ [ -5, -4, 1, 2, 7, 8 ], [ -3, -2, 1, 2, 5, 6 ], [ -1, 0, 1, 2, 3, 4 ] ]
    gap> Print(Action(M,last[1]),"\n");
    Monoid( [ Transformation( [ 2, 3, 4, 3, 6, 3 ] ), 
      Transformation( [ 4, 5, 4, 3, 4, 1 ] ) ] )
    gap> orbs := ShortOrbits(N,[0..10],100);
    [ [ -5, -4, -3, -1, 0, 1, 2, 3, 5, 6 ], 
      [ -11, -10, -9, -7, -6, -5, -4, -3, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
          11, 12 ], 
      [ -17, -16, -15, -13, -12, -11, -10, -9, -7, -6, -5, -4, -3, -1, 0, 1, 
          2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18 ] ]
    gap> quots := List(orbs,orb->Action(N,orb));;
    gap> List(quots,Size);
    [ 268, 332, 366 ]
    
  
  
  Balls of given radius around an element of an rcwa monoid can be computed by
  the  operation  Ball.  This operation can also be used for computing forward
  orbits or subsets of such under the action of an rcwa monoid:
  
  
  4.2-2  Ball  (for  monoid,  element  and radius or monoid, point, radius and
  action)
  
  Ball( M, f, r )  method
  Ball( M, p, r, action )  method
  Returns:  the  ball  of  radius r  around  the  element f  in  the monoid M,
            respectively  the  ball  of  radius r around the point p under the
            action action of the monoid M.
  
  All   balls   are  understood  with  respect  to  GeneratorsOfMonoid(M).  As
  membership tests can be expensive, the first-mentioned method does not check
  whether  f  is  indeed  an  element  of M. The methods require that point- /
  element comparisons are cheap. They are not only applicable to rcwa monoids.
  If the option Spheres is set, the ball is split up and returned as a list of
  spheres.
  
    Example  
    
    gap> List([0..12],k->Length(Ball(N,One(N),k)));
    [ 1, 4, 11, 26, 53, 99, 163, 228, 285, 329, 354, 364, 366 ]
    gap> Ball(N,[0..3],2,OnTuples);
    [ [ -3, 3, 3, 3 ], [ -1, -3, 0, 2 ], [ -1, -1, -1, -1 ], 
      [ -1, -1, 1, -1 ], [ -1, 1, 1, 1 ], [ -1, 3, 0, -4 ], [ 0, -1, 2, -3 ], 
      [ 0, 1, 2, 3 ], [ 1, -1, -1, -1 ], [ 1, 3, 0, 2 ], [ 3, -4, -1, 0 ] ]
    gap> l := 2*IdentityRcwaMappingOfZ; r := l+1;
    Rcwa mapping of Z: n -> 2n
    Rcwa mapping of Z: n -> 2n + 1
    gap> Ball(Monoid(l,r),1,4,OnPoints:Spheres);
    [ [ 1 ], [ 2, 3 ], [ 4, 5, 6, 7 ], [ 8, 9, 10, 11, 12, 13, 14, 15 ], 
      [ 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 ] ]