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 group 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, 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:
‣ 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.
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 ] ]
generated by GAPDoc2HTML