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 \mapsto (av+b)/c\) for some \(a, b, c \in ℤ^d\), but rather by \(v \mapsto (vA+b)/c\), where \(A \in ℤ^{d \times 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 \in ℕ\). We call a mapping \(f: ℤ^d \rightarrow ℤ^d\) residue-class-wise affine if there is a lattice \(L = ℤ^d M\) where \(M \in ℤ^{d \times d}\) is a matrix of full rank, such that the restrictions of \(f\) to the residue classes \(r + L \in ℤ^d/L\) are all affine. This means that for any residue class \(r + L \in ℤ^d/L\), there is a matrix \(A_{r+L} \in ℤ^{d \times d}\), a vector \(b_{r+L} \in ℤ^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 \ \rightarrow \ ℤ^d, \ \ v \ \mapsto \ (v \cdot 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
the rcwa mapping of R = Integers^2 with modulus L and coefficients coeffs,
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,
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
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(\textit{L})|\) coefficient triples [\(A_{r+ℤ^2\textit{L}}\), \(b_{r+ℤ^2\textit{L}}\), \(c_{r+ℤ^2\textit{L}}\)]. The entries \(A_{r+ℤ^2\textit{L}}\) are \(2 \times 2\) integer matrices, the \(b_{r+ℤ^2\textit{L}}\) are elements of \(ℤ^2\), i.e. lists of two integers, and the \(c_{r+ℤ^2\textit{L}}\) are integers. The ordering of the coefficient triples is determined by the ordering of the representatives of the residue classes \(r+ℤ^2\textit{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 \(\tau_{r_1+ℤ^2L_1,r_2+ℤ^2L_2}\).
Let \(d \in ℕ\), and let \(L_1, L_2 \in ℤ^{d \times 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 \(\tau_{r_1+ℤ^d L_1, r_2+ℤ^d L_2} \in {\rm Sym}(ℤ^d)\) as the involution which interchanges \(r_1 + k L_1\) and \(r_2 + k L_2\) for all \(k \in ℤ^d\).
The class transposition \(\tau_{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 \(\rho_{r(m),u}\).
Let \(d \in ℕ\). Given a residue class \(r+ℤ^dL\) and a matrix \(u \in {\rm GL}(d,ℤ)\), the class rotation \(\rho_{r+ℤ^dL,u}\) is the rcwa mapping which maps \(v \in r+ℤ^dL\) to \(vu + r(1-u)\) and which fixes \(ℤ^d \setminus 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 \(\nu_{r+ℤ^dL,k}\).
Let \(d \in ℕ\). Given a residue class \(r+ℤ^dL\) and an integer \(k \in \{1, \dots, d\}\), the class shift \(\nu_{r+ℤ^dL,k}\) is the rcwa mapping which maps \(v \in r+ℤ^dL\) to \(v + L_k\) and which fixes \(ℤ^d \setminus r+ℤ^dL\) pointwise. Here \(L_k\) denotes the \(k\)th 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:
View, Display, Print, String, LaTeXStringRcwaMapping, LaTeXAndXDVI.
Modulus, Coefficients.
Support / MovedPoints, Order, Multiplier, Divisor, PrimeSet, One, Zero.
IsInjective, IsSurjective, IsBijective, IsTame, IsIntegral, IsBalanced, IsClassWiseOrderPreserving, IsOne, IsZero.
^ (for points / finite sets / residue class unions), Trajectory, ShortCycles, Multpk, ClassWiseOrderPreservingOn, ClassWiseOrderReversingOn, ClassWiseConstantOn.
=, * (multiplication / composition and multiplication by a \(2 \times 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