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.

As any other monoids in **GAP**, residue-class-wise affine monoids can be constructed by `Monoid`

or `MonoidByGenerators`

.

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:

`‣ Rcwa` ( R ) | ( function ) |

Returns: the monoid Rcwa(`R`) of all residue-class-wise affine mappings of the ring `R`.

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:

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 monoid over Z gap> Induction(M2,2*One(Rcwa(Integers))) = M; true

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.

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`

:

`‣ 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`.

gap> ShortOrbits(M,[-5..5],20); [ [ -5, -4, 1, 2, 7, 8 ], [ -3, -2, 1, 2, 5, 6 ], [ -1 .. 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:

`‣ 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(`

. As membership tests can be expensive, the first-mentioned method does not check whether `M`)`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.

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 .. 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 ] ]

generated by GAPDoc2HTML