5
Residue-Class-Wise Affine Mappings, Groups and Monoids over ℤ^2

This chapter describes how to compute with residue-class-wise affine mappings of ℤ^2 and with groups and monoids formed by them.

The rings on which we have defined residue-class-wise affine mappings so far have all been principal ideal domains, and it has been crucial that all nontrivial principal ideals had finite index. However, the rings ℤ^d, d > 1 are not principal ideal domains. Furthermore, their principal ideals have infinite index. Therefore as moduli of residue-class-wise affine mappings we can only use lattices of full rank, for these are precisely the ideals of ℤ^d of finite index. However, on the other hand we can also be more permissive and look at ℤ^d not as a ring, but rather as a free ℤ-module. The consequence of this is that then an affine mapping of ℤ^d is not just given by v ↦ (av+b)/c for some a, b, c ∈ ℤ^d, but rather by v ↦ (vA+b)/c, where A ∈ ℤ^d × d. Also for technical reasons concerning the implementation in **GAP**, looking at ℤ^d as a free ℤ-module is preferable -- in **GAP**, `Integers^d`

is not a ring, and multiplying lists of integers means forming their scalar product.

Let d ∈ ℕ. We call a mapping f: ℤ^d → ℤ^d *residue-class-wise affine* if there is a lattice L = ℤ^d M where M ∈ ℤ^d × d is a matrix of full rank, such that the restrictions of f to the residue classes r + L ∈ ℤ^d/L are all affine. This means that for any residue class r + L ∈ ℤ^d/L, there is a matrix A_r+L ∈ ℤ^d × d, a vector b_r+L ∈ ℤ^d and a positive integer c_r+L such that the restriction of f to r + L is given by f|_r + L: r + L → ℤ^d, v ↦ (v ⋅ A_r+L + b_r+L)/c_r+L. For reasons of uniqueness, we assume that L is chosen maximal with respect to inclusion, and that no prime factor of c_r+L divides all coefficients of A_r+L and b_r+L.

We call the lattice L the *modulus* of f, written Mod(f). Further we define the *prime set* of f as the set of all primes which divide the determinant of at least one of the coefficients A_r+L or which divide the determinant of M, and we call the mapping f *class-wise translating* if all coefficients A_r+L are identity matrices and all coefficients c_r+L are equal to 1.

For the sake of simplicity, we identify a lattice with the Hermite normal form of the matrix by whose rows it is spanned.

Residue-class-wise affine mappings of ℤ^2 can be entered using the general constructor `RcwaMapping`

(2.2-5) or the more specialized functions `ClassTransposition`

(2.2-3), `ClassRotation`

(2.2-4) and `ClassShift`

(2.2-1). The arguments differ only slightly.

`‣ RcwaMapping` ( R, L, coeffs ) | ( method ) |

`‣ RcwaMapping` ( P1, P2 ) | ( method ) |

`‣ RcwaMapping` ( cycles ) | ( method ) |

`‣ RcwaMapping` ( f, g ) | ( method ) |

Returns: an rcwa mapping of ℤ^2.

The above methods return

**(a)**the rcwa mapping of

with modulus`R`= Integers^2`L`and coefficients`coeffs`,**(b)**an rcwa permutation which induces a bijection between the partitions

`P1`and`P2`of ℤ^2 into residue classes and which is affine on the elements of`P1`,**(c)**an rcwa permutation with "residue class cycles" given by a list

`cycles`of lists of pairwise disjoint residue classes of ℤ^2 each of which it permutes cyclically, and**(d)**the rcwa mapping of ℤ^2 whose projections to the coordinates are given by

`f`and`g`,

respectively.

The modulus of an rcwa mapping of ℤ^2 is a lattice of full rank. It is represented by a matrix `L` in Hermite normal form, whose rows are the spanning vectors.

A coefficient list for an rcwa mapping of ℤ^2 with modulus `L` consists of |det(`L`)| coefficient triples `[`

A_r+ℤ^2`L`, b_r+ℤ^2`L`, c_r+ℤ^2`L``]`

. The entries A_r+ℤ^2`L` are 2 × 2 integer matrices, the b_r+ℤ^2`L` are elements of ℤ^2, i.e. lists of two integers, and the c_r+ℤ^2`L` are integers. The ordering of the coefficient triples is determined by the ordering of the representatives of the residue classes r+ℤ^2`L` in the sorted list returned by `AllResidues(Integers^2,`

.`L`)

The methods for the operation `RcwaMapping`

perform a number of argument checks, which can be skipped by using `RcwaMappingNC`

instead.

Last but not least, regarding Method (d) it should be mentioned that only very special rcwa mappings of ℤ^2 have projections to coordinates.

gap> R := Integers^2;; gap> twice := RcwaMapping(R,[[1,0],[0,1]], > [[[[2,0],[0,2]],[0,0],1]]); # method (a) Rcwa mapping of Z^2: (m,n) -> (2m,2n) gap> [4,5]^twice; [ 8, 10 ] gap> twice1 := RcwaMapping(R,[[1,0],[0,1]], > [[[[2,0],[0,1]],[0,0],1]]); # method (a) Rcwa mapping of Z^2: (m,n) -> (2m,n) gap> [4,5]^twice1; [ 8, 5 ] gap> Image(twice1); (0,0)+(2,0)Z+(0,1)Z gap> hyperbolic := RcwaMapping(R,[[1,0],[0,2]], > [[[[4,0],[0,1]],[0, 0],2], > [[[4,0],[0,1]],[2,-1],2]]); # method (a) <rcwa mapping of Z^2 with modulus (1,0)Z+(0,2)Z> gap> IsBijective(hyperbolic); true gap> Display(hyperbolic); Rcwa permutation of Z^2 with modulus (1,0)Z+(0,2)Z / | (2m,n/2) if (m,n) in (0,0)+(1,0)Z+(0,2)Z (m,n) |-> < (2m+1,(n-1)/2) if (m,n) in (0,1)+(1,0)Z+(0,2)Z | \ gap> Trajectory(hyperbolic,[0,10000],20); [ [ 0, 10000 ], [ 0, 5000 ], [ 0, 2500 ], [ 0, 1250 ], [ 0, 625 ], [ 1, 312 ], [ 2, 156 ], [ 4, 78 ], [ 8, 39 ], [ 17, 19 ], [ 35, 9 ], [ 71, 4 ], [ 142, 2 ], [ 284, 1 ], [ 569, 0 ], [ 1138, 0 ], [ 2276, 0 ], [ 4552, 0 ], [ 9104, 0 ], [ 18208, 0 ] ] gap> P1 := AllResidueClassesModulo(R,[[2,1],[0,2]]); [ (0,0)+(2,1)Z+(0,2)Z, (0,1)+(2,1)Z+(0,2)Z, (1,0)+(2,1)Z+(0,2)Z, (1,1)+(2,1)Z+(0,2)Z ] gap> P2 := AllResidueClassesModulo(R,[[1,0],[0,4]]); [ (0,0)+(1,0)Z+(0,4)Z, (0,1)+(1,0)Z+(0,4)Z, (0,2)+(1,0)Z+(0,4)Z, (0,3)+(1,0)Z+(0,4)Z ] gap> g := RcwaMapping(P1,P2); # method (b) <rcwa permutation of Z^2 with modulus (2,1)Z+(0,2)Z> gap> P1^g = P2; true gap> Display(g:AsTable); Rcwa permutation of Z^2 with modulus (2,1)Z+(0,2)Z [m,n] mod (2,1)Z+(0,2)Z | Image of [m,n] -----------------------------+------------------------------------------- [0,0] | [m/2,-m+2n] [0,1] | [m/2,-m+2n-1] [1,0] | [(m-1)/2,-m+2n+3] [1,1] | [(m-1)/2,-m+2n+2] gap> classes := List([[[0,0],[[2,1],[0,2]]],[[1,0],[[2,1],[0,4]]], > [[1,1],[[4,2],[0,4]]]],ResidueClass); [ (0,0)+(2,1)Z+(0,2)Z, (1,0)+(2,1)Z+(0,4)Z, (1,1)+(4,2)Z+(0,4)Z ] gap> g := RcwaMapping([classes]); # method (c) <rcwa permutation of Z^2 with modulus (4,2)Z+(0,4)Z, of order 3> gap> Permutation(g,classes); (1,2,3) gap> Support(g); (0,0)+(2,1)Z+(0,2)Z U (1,0)+(2,1)Z+(0,4)Z U (1,1)+(4,2)Z+(0,4)Z gap> Display(g); Rcwa permutation of Z^2 with modulus (4,2)Z+(0,4)Z, of order 3 / | (m+1,(-m+4n)/2) if (m,n) in (0,0)+(2,1)Z+(0,2)Z | (2m-1,(m+2n+1)/2) if (m,n) in (1,0)+(2,1)Z+(0,4)Z (m,n) |-> < ((m-1)/2,(n-1)/2) if (m,n) in (1,1)+(4,2)Z+(0,4)Z | (m,n) otherwise | \ gap> g := RcwaMapping(ClassTransposition(0,2,1,2), > ClassReflection(0,2)); # method (d) <rcwa mapping of Z^2 with modulus (2,0)Z+(0,2)Z> gap> Display(g); Rcwa mapping of Z^2 with modulus (2,0)Z+(0,2)Z / | (m+1,-n) if (m,n) in (0,0)+(2,0)Z+(0,2)Z | (m+1,n) if (m,n) in (0,1)+(2,0)Z+(0,2)Z (m,n) |-> < (m-1,-n) if (m,n) in (1,0)+(2,0)Z+(0,2)Z | (m-1,n) if (m,n) in (1,1)+(2,0)Z+(0,2)Z | \ gap> g^2; IdentityMapping( ( Integers^2 ) ) gap> List(ProjectionsToCoordinates(g),Factorization); [ [ ( 0(2), 1(2) ) ], [ ClassReflection( 0(2) ) ] ]

`‣ ClassTransposition` ( r1, L1, r2, L2 ) | ( function ) |

`‣ ClassTransposition` ( cl1, cl2 ) | ( function ) |

Returns: the class transposition τ_r_1+ℤ^2L_1,r_2+ℤ^2L_2.

Let d ∈ ℕ, and let L_1, L_2 ∈ ℤ^d × d be matrices of full rank which are in Hermite normal form. Further let r_1 + ℤ^d L_1 and r_2 + ℤ^d L_2 be disjoint residue classes, and assume that the representatives r_1 and r_2 are reduced modulo ℤ^d L_1 and ℤ^d L_2, respectively. Then we define the *class transposition* τ_r_1+ℤ^d L_1, r_2+ℤ^d L_2 ∈ Sym(ℤ^d) as the involution which interchanges r_1 + k L_1 and r_2 + k L_2 for all k ∈ ℤ^d.

The class transposition τ_r_1+ℤ^d L_1, r_2+ℤ^d L_2 interchanges the residue classes r_1+ℤ^d L_1 and r_2+ℤ^d L_2, and fixes the complement of their union pointwise. The set of all class transpositions of ℤ^d generates the simple group CT(ℤ^d) (cf. [Koh13]).

In the four-argument form, the arguments `r1`, `L1`, `r2` and `L2` stand for r_1, L_1, r_2 and L_2, respectively. In the two-argument form, the arguments `cl1` and `cl2` stand for the residue classes r_1+ℤ^2 L_1 and r_2+ℤ^2 L_2, respectively. Enclosing the argument list in list brackets is permitted. The residue classes r_1+ℤ^2 L_1 and r_2+ℤ^2 L_2 are stored as an attribute `TransposedClasses`

.

There is also a method for `SplittedClassTransposition`

available for class transpositions of ℤ^2. This method takes as first argument the class transposition, and as second argument a list of two integers. These integers are the numbers of parts into which the class transposition is to be sliced in each dimension. Note that the product of the returned class transpositions is not always equal to the class transposition passed as first argument. However this equality holds if the first entry of the second argument is 1.

gap> ct := ClassTransposition([0,0],[[2,1],[0,2]],[1,0],[[2,1],[0,4]]); ( (0,0)+(2,1)Z+(0,2)Z, (1,0)+(2,1)Z+(0,4)Z ) gap> Display(ct); Rcwa permutation of Z^2 with modulus (2,1)Z+(0,4)Z, of order 2 / | (m+1,(-m+4n)/2) if (m,n) in (0,0)+(2,1)Z+(0,2)Z (m,n) |-> < (m-1,(m+2n-1)/4) if (m,n) in (1,0)+(2,1)Z+(0,4)Z | (m,n) otherwise \ gap> TransposedClasses(ct); [ (0,0)+(2,1)Z+(0,2)Z, (1,0)+(2,1)Z+(0,4)Z ] gap> ct = ClassTransposition(last); true gap> SplittedClassTransposition(ct,[1,2]); [ ( (0,0)+(2,1)Z+(0,4)Z, (1,0)+(2,1)Z+(0,8)Z ), ( (0,2)+(2,1)Z+(0,4)Z, (1,4)+(2,1)Z+(0,8)Z ) ] gap> Product(last) = ct; true gap> SplittedClassTransposition(ct,[2,1]); [ ( (0,0)+(4,0)Z+(0,2)Z, (1,0)+(4,2)Z+(0,4)Z ), ( (2,1)+(4,0)Z+(0,2)Z, (3,1)+(4,2)Z+(0,4)Z ) ] gap> Product(last) = ct; false

`‣ ClassRotation` ( r, L, u ) | ( function ) |

`‣ ClassRotation` ( cl, u ) | ( function ) |

Returns: the class rotation ρ_r(m),u.

Let d ∈ ℕ. Given a residue class r+ℤ^dL and a matrix u ∈ GL(d,ℤ), the *class rotation* ρ_r+ℤ^dL,u is the rcwa mapping which maps v ∈ r+ℤ^dL to vu + r(1-u) and which fixes ℤ^d ∖ r+ℤ^dL pointwise. In the two-argument form, the argument `cl` stands for the residue class r+ℤ^dL. Enclosing the argument list in list brackets is permitted. The argument `u` is stored as an attribute `RotationFactor`

.

gap> interchange := ClassRotation([0,0],[[1,0],[0,1]],[[0,1],[1,0]]); ClassRotation( Z^2, [ [ 0, 1 ], [ 1, 0 ] ] ) gap> Display(interchange); Rcwa permutation of Z^2: (m,n) -> (n,m) gap> classes := AllResidueClassesModulo(Integers^2,[[2,1],[0,3]]); [ (0,0)+(2,1)Z+(0,3)Z, (0,1)+(2,1)Z+(0,3)Z, (0,2)+(2,1)Z+(0,3)Z, (1,0)+(2,1)Z+(0,3)Z, (1,1)+(2,1)Z+(0,3)Z, (1,2)+(2,1)Z+(0,3)Z ] gap> transvection := ClassRotation(classes[5],[[1,1],[0,1]]); ClassRotation((1,1)+(2,1)Z+(0,3)Z,[[1,1],[0,1]]) gap> Display(transvection); Tame rcwa permutation of Z^2 with modulus (2,1)Z+(0,3)Z, of order infinity / | (m,(3m+2n-3)/2) if (m,n) in (1,1)+(2,1)Z+(0,3)Z (m,n) |-> < (m,n) otherwise | \

`‣ ClassShift` ( r, L, k ) | ( function ) |

`‣ ClassShift` ( cl, k ) | ( function ) |

Returns: the class shift ν_r+ℤ^dL,k.

Let d ∈ ℕ. Given a residue class r+ℤ^dL and an integer k ∈ {1, dots, d}, the *class shift* ν_r+ℤ^dL,k is the rcwa mapping which maps v ∈ r+ℤ^dL to v + L_k and which fixes ℤ^d ∖ r+ℤ^dL pointwise. Here L_k denotes the kth row of L.

In the two-argument form, the argument `cl` stands for the residue class r+ℤ^dL. Enclosing the argument list in list brackets is permitted.

gap> shift1 := ClassShift([0,0],[[1,0],[0,1]],1); ClassShift( Z^2, 1 ) gap> Display(shift1); Tame rcwa permutation of Z^2: (m,n) -> (m+1,n) gap> s := ClassShift(ResidueClass([1,1],[[2,1],[0,2]]),2); ClassShift((1,1)+(2,1)Z+(0,2)Z,2) gap> Display(s); Tame rcwa permutation of Z^2 with modulus (2,1)Z+(0,2)Z, of order infinity / | (m,n+2) if (m,n) in (1,1)+(2,1)Z+(0,2)Z (m,n) |-> < (m,n) if (m,n) in (0,0)+(2,0)Z+(0,1)Z U | (1,0)+(2,1)Z+(0,2)Z \

As for other rings, class transpositions, class rotations and class shifts of ℤ^2 have the distinguishing properties `IsClassTransposition`

, `IsClassRotation`

and `IsClassShift`

.

There are methods available for rcwa mappings of ℤ^2 for the following general operations:

**Output**`View`

,`Display`

,`Print`

,`String`

,`LaTeXStringRcwaMapping`

,`LaTeXAndXDVI`

.**Access to components**`Modulus`

,`Coefficients`

.**Attributes**`Support`

/`MovedPoints`

,`Order`

,`Multiplier`

,`Divisor`

,`PrimeSet`

,`One`

,`Zero`

.**Properties**`IsInjective`

,`IsSurjective`

,`IsBijective`

,`IsTame`

,`IsIntegral`

,`IsBalanced`

,`IsClassWiseOrderPreserving`

,`IsOne`

,`IsZero`

.**Action on ℤ^d**`^`

(for points / finite sets / residue class unions),`Trajectory`

,`ShortCycles`

,`Multpk`

,`ClassWiseOrderPreservingOn`

,`ClassWiseOrderReversingOn`

,`ClassWiseConstantOn`

.**Arithmetical operations**`=`

,`*`

(multiplication / composition and multiplication by a 2 × 2 matrix or an integer),`^`

(exponentiation and conjugation),`Inverse`

,`+`

(addition of a constant).

The above operations are documented either in the **GAP** Reference Manual or earlier in this manual. The operations which are special for rcwa mappings of ℤ^2 are described in the sequel.

`‣ ProjectionsToCoordinates` ( f ) | ( attribute ) |

Returns: the projections of the rcwa mapping `f` of ℤ^2 to the coordinates if such projections exist, and `fail`

otherwise.

An rcwa mapping can be projected to the first / second coordinate if and only if the first / second coordinate of the image of a point depends only on the first / second coordinate of the preimage. Note that this is a very strong and restrictive condition.

gap> f := RcwaMapping(ClassTransposition(0,2,1,2),ClassReflection(0,2));; gap> Display(f); Rcwa mapping of Z^2 with modulus (2,0)Z+(0,2)Z / | (m+1,-n) if (m,n) in (0,0)+(2,0)Z+(0,2)Z | (m+1,n) if (m,n) in (0,1)+(2,0)Z+(0,2)Z (m,n) |-> < (m-1,-n) if (m,n) in (1,0)+(2,0)Z+(0,2)Z | (m-1,n) if (m,n) in (1,1)+(2,0)Z+(0,2)Z | \ gap> List(ProjectionsToCoordinates(f),Factorization); [ [ ( 0(2), 1(2) ) ], [ ClassReflection( 0(2) ) ] ]

Residue-class-wise affine groups over ℤ^2 can be entered by `Group`

, `GroupByGenerators`

and `GroupWithGenerators`

, like any groups in **GAP**. Likewise, residue-class-wise affine monoids over ℤ^2 can be entered by `Monoid`

and `MonoidByGenerators`

. The groups RCWA(ℤ^2) and CT(ℤ^2) are entered as `RCWA(Integers^2)`

and `CT(Integers^2)`

, respectively. The monoid Rcwa(ℤ^2) is entered as `Rcwa(Integers^2)`

.

There are methods provided for the operations `Size`

, `IsIntegral`

, `IsClassWiseTranslating`

, `IsTame`

, `Modulus`

, `Multiplier`

and `Divisor`

.

There are methods for `IsomorphismRcwaGroup`

(3.1-1) which embed the groups SL(2,ℤ) and GL(2,ℤ) into RCWA(ℤ^2) in such a way that the support of the image is a specified residue class:

`‣ IsomorphismRcwaGroup` ( sl2z, cl ) | ( attribute ) |

`‣ IsomorphismRcwaGroup` ( gl2z, cl ) | ( attribute ) |

Returns: a monomorphism from `sl2z` respectively `gl2z` to RCWA(ℤ^2), such that the support of the image is the residue class `cl` and the generators are affine on `cl`.

gap> sl := SL(2,Integers); SL(2,Integers) gap> phi := IsomorphismRcwaGroup(sl,ResidueClass([1,0],[[2,2],[0,3]])); [ [ [ 0, 1 ], [ -1, 0 ] ], [ [ 1, 1 ], [ 0, 1 ] ] ] -> [ ClassRotation((1,0)+(2,2)Z+(0,3)Z,[[0,1],[-1,0]]), ClassRotation((1,0)+(2,2)Z+(0,3)Z,[[1,1],[0,1]]) ] gap> Support(Image(phi)); (1,0)+(2,2)Z+(0,3)Z gap> gl := GL(2,Integers); GL(2,Integers) gap> phi := IsomorphismRcwaGroup(gl,ResidueClass([1,0],[[2,2],[0,3]])); [ [ [ 0, 1 ], [ 1, 0 ] ], [ [ -1, 0 ], [ 0, 1 ] ], [ [ 1, 1 ], [ 0, 1 ] ] ] -> [ ClassRotation((1,0)+(2,2)Z+(0,3)Z,[[0,1],[1,0]]), ClassRotation((1,0)+(2,2)Z+(0,3)Z,[[-1,0],[0,1]]), ClassRotation((1,0)+(2,2)Z+(0,3)Z,[[1,1],[0,1]]) ] gap> [[-47,-37],[61,48]]^phi; ClassRotation((1,0)+(2,2)Z+(0,3)Z,[[-47,-37],[61,48]]) gap> Display(last:AsTable); Rcwa permutation of Z^2 with modulus (2,2)Z+(0,3)Z, of order 6 [m,n] mod (2,2)Z+(0,3)Z | Image of [m,n] -----------------------------+------------------------------------------- [0,0] [0,1] [0,2] [1,1] | [1,2] | [m,n] [1,0] | [(-263m+122n+266)/3,(-1147m+532n+1147)/6]

The function `DrawOrbitPicture`

(3.3-3) can also be used to depict orbits under the action of rcwa groups over ℤ^2. Further there is a function which depicts residue class unions of ℤ^2 and partitions of ℤ^2 into such:

`‣ DrawGrid` ( U, yrange, xrange, filename ) | ( function ) |

`‣ DrawGrid` ( P, yrange, xrange, filename ) | ( function ) |

Returns: nothing.

This function depicts the residue class union `U` of ℤ^2 or the partition `P` of ℤ^2 into residue class unions, respectively. The arguments `yrange` and `xrange` are the coordinate ranges of the rectangular snippet to be drawn, and the argument `filename` is the name, i.e. the full path name, of the output file. If the first argument is a residue class union, the output picture is black-and-white, where black pixels represent members of `U` and white pixels represent non-members. If the first argument is a partition of ℤ^2 into residue class unions, the produced picture is colored, and different colors are used to denote membership in different parts.

generated by GAPDoc2HTML