In this chapter, we describe how to construct residue-class-wise affine groups and how to compute with them.
As any other groups in GAP, residue-class-wise affine (rcwa-) groups can be constructed by Group, GroupByGenerators or GroupWithGenerators.
gap> G := Group(ClassTransposition(0,2,1,4),ClassShift(0,5)); <rcwa group over Z with 2 generators> gap> IsTame(G); Size(G); IsSolvable(G); IsPerfect(G); true infinity false false
An rcwa group isomorphic to a given group can be obtained by taking the image of a faithful rcwa representation:
‣ IsomorphismRcwaGroup( G, R ) | ( attribute ) |
‣ IsomorphismRcwaGroup( G ) | ( attribute ) |
Returns: a monomorphism from the group G to RCWA(R) or to RCWA(ℤ), respectively.
The best-supported case is R = ℤ. Currently there are methods available for finite groups, for free products of finite groups and for free groups. The method for free products of finite groups uses the Table-Tennis Lemma (cf. e.g. Section II.B. in [dlH00]), and the method for free groups uses an adaptation of the construction given on page 27 in [dlH00] from PSL(2,ℂ) to RCWA(ℤ).
gap> F := FreeProduct(Group((1,2)(3,4),(1,3)(2,4)),Group((1,2,3)), > SymmetricGroup(3)); <fp group on the generators [ f1, f2, f3, f4, f5 ]> gap> IsomorphismRcwaGroup(F); [ f1, f2, f3, f4, f5 ] -> [ <rcwa permutation of Z with modulus 12>, <rcwa permutation of Z with modulus 24>, <rcwa permutation of Z with modulus 12>, <rcwa permutation of Z with modulus 72>, <rcwa permutation of Z with modulus 36> ] gap> IsomorphismRcwaGroup(FreeGroup(2)); [ f1, f2 ] -> [ <wild rcwa permutation of Z with modulus 8>, <wild rcwa permutation of Z with modulus 8> ] gap> F2 := Image(last); <wild rcwa group over Z with 2 generators>
Further, new rcwa groups can be constructed from given ones by taking direct products and by taking wreath products with finite groups or with the infinite cyclic group:
‣ DirectProduct( G1, G2, ... ) | ( method ) |
Returns: an rcwa group isomorphic to the direct product of the rcwa groups over ℤ given as arguments.
There is certainly no unique or canonical way to embed a direct product of rcwa groups into RCWA(ℤ). This method chooses to embed the groups G1, G2, G3 ... via restrictions by \(n \mapsto mn\), \(n \mapsto mn+1\), \(n \mapsto mn+2\) ... (\(\rightarrow\) Restriction (3.1-6)), where \(m\) denotes the number of groups given as arguments.
gap> F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));; gap> F2xF2 := DirectProduct(F2,F2); <wild rcwa group over Z with 4 generators> gap> Image(Projection(F2xF2,1)) = F2; true
‣ WreathProduct( G, P ) | ( method ) |
‣ WreathProduct( G, Z ) | ( method ) |
Returns: an rcwa group isomorphic to the wreath product of the rcwa group G over ℤ with the finite permutation group P or with the infinite cyclic group Z, respectively.
The first-mentioned method embeds the NrMovedPoints(P)th direct power of G using the method for DirectProduct, and lets the permutation group P act naturally on the set of residue classes modulo NrMovedPoints(P). The second-mentioned method restricts (\(\rightarrow\) Restriction (3.1-6)) the group G to the residue class 3(4), and maps the generator of the infinite cyclic group Z to ClassTransposition(0,2,1,2) * ClassTransposition(0,2,1,4).
gap> F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));; gap> F2wrA5 := WreathProduct(F2,AlternatingGroup(5));; gap> Embedding(F2wrA5,1); [ <wild rcwa permutation of Z with modulus 8>, <wild rcwa permutation of Z with modulus 8> ] -> [ <wild rcwa permutation of Z with modulus 40>, <wild rcwa permutation of Z with modulus 40> ] gap> Embedding(F2wrA5,2); [ (1,2,3,4,5), (3,4,5) ] -> [ ( 0(5), 1(5), 2(5), 3(5), 4(5) ), ( 2(5), 3(5), 4(5) ) ] gap> ZwrZ := WreathProduct(Group(ClassShift(0,1)),Group(ClassShift(0,1))); <wild rcwa group over Z with 2 generators> gap> Embedding(ZwrZ,1); [ ClassShift( Z ) ] -> [ <tame rcwa permutation of Z with modulus 4, of order infinity> ] gap> Embedding(ZwrZ,2); [ ClassShift( Z ) ] -> [ <wild rcwa permutation of Z with modulus 4> ]
Also, rcwa groups can be obtained as particular extensions of finite permutation groups:
‣ MergerExtension( G, points, point ) | ( operation ) |
Returns: roughly spoken, an extension of G by an involution which "merges" points into point.
The arguments of this operation are a finite permutation group G, a set points of points moved by G and a single point point moved by G which is not in points.
Let \(n\) be the largest moved point of G, and let \(H\) be the tame subgroup of CT(ℤ) which respects the partition \(\mathcal{P}\) of ℤ into the residue classes (mod \(n\)), and which acts on \(\mathcal{P}\) as G acts on \(\{1, \dots, n\}\). Further assume that points = \(\{p_1, \dots, p_k\}\) and point = \(p\), and put \(r_i := p_i-1, \ i = 1, \dots, k\) and \(r := p-1\). Now let \(\sigma\) be the product of the class transpositions \(\tau_{r_i(n),r+(i-1)n(kn)}, \ i = 1, \dots, k\). The group returned by this operation is the extension of \(H\) by the involution \(\sigma\). -- On first reading, this may look a little complicated, but really the code of the method is only about half as long as this description.
gap> # First example -- a group isomorphic to PSL(2,Z): gap> G := MergerExtension(Group((1,2,3)),[1,2],3); <rcwa group over Z with 2 generators> gap> Size(G); infinity gap> GeneratorsOfGroup(G); [ ( 0(3), 1(3), 2(3) ), ( 0(3), 2(6) ) ( 1(3), 5(6) ) ] gap> B := Ball(G,One(G),6:Spheres);; gap> List(B,Length); [ 1, 3, 4, 6, 8, 12, 16 ] gap> # gap> # Second example -- a group isomorphic to Thompson's group V: gap> G := MergerExtension(Group((1,2,3,4),(1,2)),[1,2],3); <rcwa group over Z with 3 generators> gap> Size(G); infinity gap> GeneratorsOfGroup(G); [ ( 0(4), 1(4), 2(4), 3(4) ), ( 0(4), 1(4) ), ( 0(4), 2(8) ) ( 1(4), 6(8) ) ] gap> B := Ball(G,One(G),6:Spheres);; gap> List(B,Length); [ 1, 4, 11, 28, 69, 170, 413 ] gap> G = Group(List([[0,2,1,2],[1,2,2,4],[0,2,1,4],[1,4,2,4]], > ClassTransposition)); true
It is also possible to build an rcwa group from a list of residue classes:
‣ GroupByResidueClasses( classes ) | ( function ) |
Returns: the group which is generated by all class transpositions which interchange disjoint residue classes in classes.
The argument classes must be a list of residue classes.
If the residue classes in classes are pairwise disjoint, then the returned group is the symmetric group on classes. If any two residue classes in classes intersect non-trivially, then the returned group is trivial. In many other cases, the returned group is infinite.
gap> G := GroupByResidueClasses(List([[0,2],[0,4],[1,4],[2,4],[3,4]], > ResidueClass)); <rcwa group over Z with 8 generators> gap> H := Group(List([[0,2,1,2],[1,2,2,4],[0,2,1,4],[1,4,2,4]], > ClassTransposition)); # Thompson's group V <(0(2),1(2)),(1(2),2(4)),(0(2),1(4)),(1(4),2(4))> gap> G = H; true
Various ways to construct rcwa groups are based on certain monomorphisms from the group RCWA(\(R\)) into itself. Examples are the constructions of direct products and wreath products described above. The support of the image of such a monomorphism is the image of a given injective rcwa mapping. For this reason, these monomorphisms are called restriction monomorphisms. The following operation computes images of rcwa mappings and -groups under these embeddings of RCWA(\(R\)) into itself:
‣ Restriction( g, f ) | ( operation ) |
‣ Restriction( G, f ) | ( operation ) |
Returns: the restriction of the rcwa mapping g (respectively the rcwa group G) by the injective rcwa mapping f.
By definition, the restriction \(g_f\) of an rcwa mapping g by an injective rcwa mapping f is the unique rcwa mapping which satisfies the equation \(f \cdot g_f = g \cdot f\) and which fixes the complement of the image of f pointwise. If f is bijective, the restriction of g by f is just the conjugate of g under f.
The restriction of an rcwa group G by an injective rcwa mapping f is defined as the group whose elements are the restrictions of the elements of G by f. The restriction of G by f acts on the image of f and fixes its complement pointwise.
gap> F2tilde := Restriction(F2,RcwaMapping([[5,3,1]])); <wild rcwa group over Z with 2 generators> gap> Support(F2tilde); 3(5)
‣ Induction( g, f ) | ( operation ) |
‣ Induction( G, f ) | ( operation ) |
Returns: the induction of the rcwa mapping g (respectively the rcwa group G) by the injective rcwa mapping f.
Induction is the right inverse of restriction, i.e. it is Induction(Restriction(g,f),f) = g and Induction(Restriction(G,f),f) = G. The mapping g respectively the group G must not move points outside the image of f.
gap> Induction(F2tilde,RcwaMapping([[5,3,1]])) = F2; true
Once having constructed an rcwa group, it is sometimes possible to obtain a smaller generating set by the operation SmallGeneratingSet.
There are methods for the operations View, Display, Print and String which are applicable to rcwa groups.
Basic attributes of an rcwa group which are derived from the coefficients of its elements are Modulus, Multiplier, Divisor and PrimeSet. The modulus of an rcwa group is the lcm of the moduli of its elements if such an lcm exists, i.e. if the group is tame, and 0 otherwise. The multiplier respectively divisor of an rcwa group is the lcm of the multipliers respectively divisors of its elements in case such an lcm exists and \(\infty\) otherwise. The prime set of an rcwa group is the union of the prime sets of its elements. There are shorthands Mod, Mult and Div defined for Modulus, Multiplier and Divisor, respectively. An rcwa group is called class-wise translating, integral or class-wise order-preserving if all of its elements are so. There are corresponding methods available for IsClassWiseTranslating, IsIntegral and IsClassWiseOrderPreserving. There is a property IsSignPreserving, which indicates whether a given rcwa group over ℤ acts on the set of nonnegative integers. The latter holds for any subgroup of CT(ℤ) (cf. below).
gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(1,3,2,6), > ClassReflection(2,4)); <rcwa group over Z with 3 generators> gap> List([Modulus,Multiplier,Divisor,PrimeSet,IsClassWiseTranslating, > IsIntegral,IsClassWiseOrderPreserving,IsSignPreserving],f->f(G)); [ 24, 2, 2, [ 2, 3 ], false, false, false, false ]
All rcwa groups over a ring \(R\) are subgroups of RCWA(\(R\)). The group 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 group RCWA(R) of all residue-class-wise affine permutations of the ring R.
gap> RCWA_Z := RCWA(Integers); RCWA(Z) gap> IsSubgroup(RCWA_Z,G); true
Examples of rcwa permutations can be obtained via Random(RCWA(R)), see Section 3.5. The number of conjugacy classes of RCWA(ℤ) of elements of given order is known, cf. Corollary 2.7.1 (b) in [Koh05]. It can be determined by the function NrConjugacyClassesOfRCWAZOfOrder:
gap> List([2,105],NrConjugacyClassesOfRCWAZOfOrder); [ infinity, 218 ]
We denote the group which is generated by all class transpositions of the ring \(R\) by CT(\(R\)). This group is handled as a special case as well:
‣ CT( R ) | ( function ) |
‣ CT( P, Integers ) | ( function ) |
Returns: the group CT(R) which is generated by all class transpositions of the ring R, respectively, the group CT(P,ℤ) which is generated by all class transpositions of ℤ which interchange residue classes whose moduli have only prime factors in the finite set P.
gap> CT_Z := CT(Integers); CT(Z) gap> IsSimpleGroup(CT_Z); # One of a number of stored attributes/properties. true gap> V := CT([2],Integers); CT_[ 2 ](Z) gap> GeneratorsOfGroup(V); [ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 0(2), 1(4) ), ( 1(4), 2(4) ) ] gap> G := CT([2,3],Integers); CT_[ 2, 3 ](Z) gap> GeneratorsOfGroup(G); [ ( 0(2), 1(2) ), ( 0(3), 1(3) ), ( 1(3), 2(3) ), ( 0(2), 1(4) ), ( 0(2), 5(6) ), ( 0(3), 1(6) ) ]
The group CT(ℤ) has an outer automorphism which is given by conjugation with \(n \mapsto -n - 1\). This automorphism can be applied to an rcwa mapping of ℤ or to an rcwa group over ℤ by the operation Mirrored. The group Mirrored(G) acts on the nonnegative integers as G acts on the negative integers, and vice versa.
gap> ct := ClassTransposition(0,2,1,6); ( 0(2), 1(6) ) gap> Mirrored(ct); ( 1(2), 4(6) ) gap> G := Group(List([[0,2,1,2],[0,3,2,3],[2,4,1,6]],ClassTransposition));; gap> ShortOrbits(G,[-100..100],100); [ [ 0 .. 5 ] ] gap> ShortOrbits(Mirrored(G),[-100..100],100); [ [ -6 .. -1 ] ]
Under the hypothesis that CT(ℤ) is the setwise stabilizer of \(ℕ_0\) in RCWA(ℤ), the elements of CT(ℤ) with modulus dividing a given positive integer \(m\) are parametrized by the ordered partitions of ℤ into \(m\) residue classes. The list of these elements for given \(m\) can be obtained by the function AllElementsOfCTZWithGivenModulus, and the numbers of such elements for \(m \leq 24\) are stored in the list NrElementsOfCTZWithGivenModulus.
gap> NrElementsOfCTZWithGivenModulus{[1..8]}; [ 1, 1, 17, 238, 4679, 115181, 3482639, 124225680 ]
The number of conjugacy classes of CT(ℤ) of elements of given order is also known under the hypothesis that CT(ℤ) is the setwise stabilizer of \(ℕ_0\) in RCWA(ℤ). It can be determined by the function NrConjugacyClassesOfCTZOfOrder.
In the previous section we have seen how to construct rcwa groups. The purpose of this section is to describe how to obtain information on the structure of an rcwa group and on its action on the underlying ring. The easiest way to get a little (but really only a very little!) information on the group structure is a dedicated method for the operation StructureDescription:
‣ StructureDescription( G ) | ( method ) |
Returns: a string which sometimes gives a little glimpse of the structure of the rcwa group G.
The attribute StructureDescription for finite groups is documented in the GAP Reference Manual. Therefore we describe here only issues which are specific to infinite groups, and in particular to rcwa groups.
Wreath products are denoted by wr, and free products are denoted by *. The infinite cyclic group (ℤ,+) is denoted by Z, the infinite dihedral group is denoted by D0 and free groups of rank \(2,3,4,\dots\) are denoted by F2, F3, F4, \(\dots\). While for finite groups the symbol . is used to denote a non-split extension, for rcwa groups in general it stands for an extension which may be split or not. For wild groups in most cases it happens that there is a large section on which no structural information can be obtained. Such sections of the group with unknown structure are denoted by <unknown>. In general, the structure of a section denoted by <unknown> can be very complicated and very difficult to exhibit.
gap> G := Group(ClassTransposition(0,2,1,4),ClassShift(0,5));; gap> StructureDescription(G); "(Z x Z x Z x Z x Z x Z x Z) . (C2 x S7)" gap> G := Group(ClassTransposition(0,2,1,4), > ClassShift(2,4),ClassReflection(1,2));; gap> StructureDescription(G:short); "Z^2.((S3xS3):2)" gap> F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));; gap> PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(3), > CyclicGroup(2))));; gap> G := DirectProduct(PSL2Z,F2); <wild rcwa group over Z with 4 generators> gap> StructureDescription(G); "(C3 * C2) x F2" gap> G := WreathProduct(G,CyclicGroup(IsRcwaGroupOverZ,infinity)); <wild rcwa group over Z with 5 generators> gap> StructureDescription(G); "((C3 * C2) x F2) wr Z" gap> Collatz := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; gap> G := Group(Collatz,ClassShift(0,1));; gap> StructureDescription(G:short); "<unknown>.Z"
The extent to which the structure of an rcwa group can be exhibited automatically is severely limited. In general, one can find out much more about the structure of a given rcwa group in an interactive session using the functionality described in the rest of this section and elsewhere in this manual.
The order of an rcwa group can be computed by the operation Size. An rcwa group is finite if and only if it is tame and its action on a suitably chosen respected partition (see RespectedPartition (3.4-1)) is faithful. Hence the problem of computing the order of an rcwa group reduces to the problem of deciding whether it is tame, the problem of deciding whether it acts faithfully on a respected partition and the problem of computing the order of the finite permutation group induced on the respected partition.
gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(1,3,2,3), > ClassReflection(0,5)); <rcwa group over Z with 3 generators> gap> Size(G); 46080
For a finite rcwa group, an isomorphism to a permutation group can be computed by IsomorphismPermGroup:
gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(0,3,1,3));; gap> IsomorphismPermGroup(G); [ ( 0(2), 1(2) ), ( 0(3), 1(3) ) ] -> [ (1,2)(3,4)(5,6), (1,2)(4,5) ]
In general the membership problem for rcwa groups is algorithmically unsolvable, see Corollary 4.5 in [Koh10]. A consequence of this is that a membership test "g in G" may run into an infinite loop if the rcwa permutation g is not an element of the rcwa group G. For tame rcwa groups however membership can always be decided. For wild rcwa groups, membership can very often be decided quite quick as well, but -- as said -- not always. Anyway, if g is contained in G, the membership test will eventually always return true, provided that there are sufficient computing resources available (memory etc.).
On Info level 2 of InfoRCWA the membership test provides information on reasons why the given rcwa permutation is an element of the given rcwa group or not.
The membership test "g in G" recognizes an option OrbitLengthBound. If this option is set, it returns false once it has computed balls of size exceeding OrbitLengthBound about 1 and g in G, and these balls are still disjoint. Note however that due to the algorithmic unsolvability of the membership problem, RCWA has no means to check the correctness of such bound in a given case. So the correct use of this option has to remain within the full responsibility of the user.
gap> G := Group(ClassShift(0,3),ClassTransposition(0,3,2,6));; gap> ClassShift(2,6)^7 * ClassTransposition(0,3,2,6) > * ClassShift(0,3)^-3 in G; true gap> ClassShift(0,1) in G; false
The conjugacy problem for rcwa groups is difficult, and RCWA provides only methods to solve it in some reasonably easy cases.
gap> IsConjugate(RCWA(Integers), > ClassTransposition(0,2,1,4),ClassShift(0,1)); false gap> IsConjugate(CT(Integers),ClassTransposition(0,2,1,6), > ClassTransposition(1,4,0,8)); true gap> g := RepresentativeAction(CT(Integers),ClassTransposition(0,2,1,6), > ClassTransposition(1,4,0,8)); <rcwa permutation of Z with modulus 48> gap> ClassTransposition(0,2,1,6)^g = ClassTransposition(1,4,0,8); true
There is a property IsTame which indicates whether an rcwa group is tame or not:
gap> G := Group(ClassTransposition(0,2,1,4),ClassShift(1,3));; gap> H := Group(ClassTransposition(0,2,1,6),ClassShift(1,3));; gap> IsTame(G); true gap> IsTame(H); false
For tame rcwa groups, there are methods for IsSolvableGroup and IsPerfectGroup available, and usually derived subgroups and subgroup indices can be computed as well. Linear representations of tame groups over the rationals can be determined by the operation IsomorphismMatrixGroup. Testing a wild group for solvability or perfectness is currently not always feasible, and wild groups have in general no faithful finite-dimensional linear representations. There is a method for Exponent available, which works basically for any rcwa group.
gap> G := Group(ClassTransposition(0,2,1,4),ClassShift(1,2));; gap> IsPerfect(G); false gap> IsSolvable(G); true gap> D1 := DerivedSubgroup(G);; D2 := DerivedSubgroup(D1);; gap> IsAbelian(D2); true gap> Index(G,D1); Index(D1,D2); infinity 9 gap> StructureDescription(G); StructureDescription(D1); "(Z x Z x Z) . S3" "(Z x Z) . C3" gap> Q := D1/D2; Group([ (), (1,2,4)(3,5,7)(6,8,9), (1,3,6)(2,5,8)(4,7,9) ]) gap> StructureDescription(Q); "C3 x C3" gap> Exponent(G); infinity gap> phi := IsomorphismMatrixGroup(G);; gap> Display(Image(phi,ClassTransposition(0,2,1,4))); [ [ 0, 0, 1/2, -1/2, 0, 0 ], [ 0, 0, 0, 1, 0, 0 ], [ 2, 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 1 ] ]
When investigating a group, a basic task is to find relations among the generators:
‣ EpimorphismFromFpGroup( G, r ) | ( method ) |
‣ EpimorphismFromFpGroup( G, r, maxparts ) | ( method ) |
Returns: an epimorphism from a finitely presented group to the rcwa group G.
The argument r is the "search radius", i.e. the radius of the ball around 1 which is scanned for relations. In general, the larger r is chosen the smaller the kernel of the returned epimorphism is. If the group G has finite presentations, the kernel will in principle get trivial provided that r is chosen large enough. If the optional argument maxparts is given, it limits the search space to elements with at most maxparts affine parts.
gap> a := ClassTransposition(2,4,3,4);; gap> b := ClassTransposition(4,6,8,12);; gap> c := ClassTransposition(3,4,4,6);; gap> G := SparseRep(Group(a,b,c)); <(2(4),3(4)),(4(6),8(12)),(3(4),4(6))> gap> phi := EpimorphismFromFpGroup(G,6); #I there are 3 generators and 12 relators of total length 330 #I there are 3 generators and 11 relators of total length 312 [ a, b, c ] -> [ ( 2(4), 3(4) ), ( 4(6), 8(12) ), ( 3(4), 4(6) ) ] gap> RelatorsOfFpGroup(Source(phi)); [ a^2, b^2, c^2, (b*c)^3, (a*b)^6, (a*b*c*b)^3, (a*c*b*c)^3, (a*b*a*c)^12, ((a*b)^2*a*c)^12, (a*b*(a*c)^2)^12, (a*b*c*a*c*b)^12 ]
A related very common task is to factor group elements into generators:
‣ PreImagesRepresentative( phi, g ) | ( method ) |
Returns: a representative of the set of preimages of g under the epimorphism phi from a free group to an rcwa group.
The epimorphism phi must map the generators of the free group to the generators of the rcwa group one-by-one.
This method can be used for factoring elements of rcwa groups into generators. The implementation is based on RepresentativeActionPreImage, see RepresentativeAction (3.3-10).
Quite frequently, computing several preimages is not harder than computing just one, i.e. often several preimages are found simultaneously. The operation PreImagesRepresentatives takes care of this. It takes the same arguments as PreImagesRepresentative and returns a list of preimages. If multiple preimages are found, their quotients give rise to nontrivial relations among the generators of the image of phi.
gap> a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; SetName(a,"a"); gap> b := ClassShift(0,1);; SetName(b,"b"); gap> G := Group(a,b);; # G = <<Collatz permutation>, n -> n + 1> gap> phi := EpimorphismFromFreeGroup(G);; gap> g := Comm(a^2*b^4,a*b^3); # a sample element to be factored <rcwa permutation of Z with modulus 8> gap> PreImagesRepresentative(phi,g); # -> a factorization of g b^-3*(b^-1*a^-1)^2*b^3*a*b^-1*a*b^3 gap> g = b^-4*a^-1*b^-1*a^-1*b^3*a*b^-1*a*b^3; # check true gap> g := Comm(a*b,Comm(a,b^3)); <rcwa permutation of Z with modulus 8> gap> pre := PreImagesRepresentatives(phi,g); [ (b^-1*a^-1)^2*b^2*(b*a)^2*b^-2, b^-1*(a^-1*b)^2*b^2*(a*b^-1)^2*b^-1 ] gap> rel := pre[1]/pre[2]; # -> a nontrivial relation (b^-1*a^-1)^2*b^3*a*b^2*a^-1*b^-2*(b^-1*a)^2*b gap> rel^phi; IdentityMapping( Integers )
Knowing a natural permutation representation of a group usually helps significantly in computing in it and in obtaining results on its structure. This holds particularly for the natural action of an rcwa group on its underlying ring. In this section we describe RCWA's functionality related to this action.
The support, i.e. the set of moved points, of an rcwa group can be determined by Support or MovedPoints (these are synonyms). Testing for transitivity on the underlying ring or on a union of residue classes thereof is often feasible:
gap> G := Group(ClassTransposition(1,2,0,4),ClassShift(0,2));; gap> IsTransitive(G,Integers); true
Groups generated by class transpositions of the integers act on the set of nonnegative integers. There is a property IsTransitiveOnNonnegativeIntegersInSupport(G) which indicates whether such group acts transitively on the set of nonnegative integers in its support. Since such transitivity test is a computationally hard problem, methods may fail. If IsTransitiveOnNonnegativeIntegersInSupport returns true, an attribute TransitivityCertificate is set; this is a record containing components phi, words, classes, smallpointbound, status and complete as follows:
phiis an epimorphism from a free group to G which maps generators to generators.
words, classestwo lists. -- words[i] is a preimage under phi of an element of G which maps all sufficiently large positive integers in the residue classes classes[i] to smaller nonnegative integers.
smallpointboundin addition to finding a list of group elements \(g_i\) such that for any large enough integer \(n\) in the support of G there is some \(g_i\) such that \(n^{g_i} < n\), for verifying transitivity it was necessary to check that all integers less than or equal to smallpointbound in the support of G lie in the same orbit.
statusthe string "transitive" in case all checks have been completed successfully.
completetrue in case all checks have been completed successfully.
Parts of this information for possibly intransitive groups can be obtained by the operation TryToComputeTransitivityCertificate(G,searchlimit), where searchlimit is the maximum radius about a point within which smaller points are searched and taken into consideration. This operation interprets an option abortdensity -- if set, the operation returns the data computed so far once the density of the set of positive integers in the support of G for which no group element is found which maps them to smaller integers reaches or drops below abortdensity. A simplified certificate can be obtained via SimplifiedCertificate(cert).
gap> G := Group(List([[0,2,1,2],[0,3,2,3],[1,2,2,4]], > ClassTransposition)); <(0(2),1(2)),(0(3),2(3)),(1(2),2(4))> gap> IsTransitiveOnNonnegativeIntegersInSupport(G); true gap> TransitivityCertificate(G); rec( classes := [ [ 1(2) ], [ 2(6) ], [ 6(12), 10(12) ], [ 0(12) ], [ 4(12) ] ], complete := true, phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 0(3), 2(3) ), ( 1(2), 2(4) ) ], smallpointbound := 4, status := "transitive", words := [ a, b, c, b*c, a*b ] ) gap> SimplifiedCertificate(last); rec( classes := [ [ 1(2) ], [ 2(4) ], [ 4(12) ], [ 0(12), 8(12) ] ], complete := true, phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 0(3), 2(3) ), ( 1(2), 2(4) ) ], smallpointbound := 4, status := "transitive", words := [ a, c, a*b, b*c ] ) gap> G := Group(List([[0,2,1,2],[1,2,2,4],[1,4,2,6]], > ClassTransposition)); # '3n+1 group' <(0(2),1(2)),(1(2),2(4)),(1(4),2(6))> gap> cert := TryToComputeTransitivityCertificate(G,10); rec( classes := [ [ 1(2) ], [ 2(4) ], [ 4(32) ], [ 8(24), 44(48), 20(96) ], [ 0(24), 16(24) ] ], complete := false, phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 1(4), 2(6) ) ], remaining := [ 12(48), 28(48), 52(96), 84(96) ], smallpointbound := 42, status := "unclear", words := [ a, b, (a*c)^2*b*a*b, c, a*c*b ] ) gap> Union(Flat(cert.classes)); <union of 90 residue classes (mod 96) (6 classes)> gap> Difference(Integers,Union(Flat(cert.classes))); 12(48) U 28(48) U 52(96) U 84(96) gap> cert := TryToComputeTransitivityCertificate(G,20); # try larger bound rec( classes := [ [ 1(2) ], [ 2(4) ], [ 4(32) ], [ 8(24), 44(48), 20(96) ], [ 0(24), 16(24) ], [ 12(768), 268(768) ], [ 28(768), 540(768) ] ], complete := false, phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 1(4), 2(6) ) ], remaining := [ 52(96), 84(96), 60(192), 108(192), 124(192), 172(192), 76(384), 204(384), 220(384), 348(384), 156(768), 396(768), 412(768), 652(768) ], smallpointbound := 1074, status := "unclear", words := [ a, b, (a*c)^2*b*a*b, c, a*c*b, (a*c)^3*b*c*b*a*b, (a*c)^4*b*a*b*a*b ] ) gap> Difference(Integers,Union(Flat(cert.classes))); <union of 44 residue classes (mod 768) (14 classes)> gap> Intersection([0..100],last); [ 52, 60, 76, 84 ]
Let G be a subgroup of CT(ℤ). Then, a set which has nontrivial intersection with every orbit of G on \(ℕ_0\) can be determined by the operation SupersetOfOrbitRepresentatives(G,maxsaddle,maxprog). This operation returns a record with the following components:
RA set which -- possibly among other numbers -- contains the smallest representatives of all the orbits of G on the nonnegative integers. The parameters maxsaddle and maxprog can be used to control the size of this set. In general, larger values may make the set smaller.
DA list of residue class unions whose union is a (not necessarily proper) superset the complement of R in ℤ. The intersection of R and the union of the sets in D is always finite.
gA list of elements of G such that n^g[i] < n for all sufficiently large n in D[i], for i = 1, ... , Length(g) = Length(D).
phiAn epimorphism from a free group F of rank the number of generators of G to G which maps generators to generators.
wA list of words w[i] in F such that w[i]^phi = g[i], for i = 1, ... , Length(w) = Length(g).
gap> G := Group(ClassTransposition(1,3,2,3),ClassTransposition(3,4,4,6), > ClassTransposition(2,4,1,6)); <(1(3),2(3)),(3(4),4(6)),(2(4),1(6))> gap> R := SupersetOfOrbitRepresentatives(G,4,6); rec( D := [ 2(3), 4(6), 1(6) ], R := 0(3) U [ 1 ], g := [ ( 1(3), 2(3) ), <rcwa permutation of Z with modulus 12 and 5 affine parts>, <rcwa permutation of Z with modulus 12 and 5 affine parts> ], pi := [ a, b, c ] -> [ ( 1(3), 2(3) ), ( 3(4), 4(6) ), ( 2(4), 1(6) ) ], w := [ a, b, c ] )
Further, there are methods to compute orbits under the action of an rcwa group:
‣ Orbit( G, point ) | ( method ) |
‣ Orbit( G, set ) | ( method ) |
Returns: the orbit of the point point respectively the set set under the natural action of the rcwa group G on its underlying ring.
The second argument can either be an element or a subset of the underlying ring of the rcwa group G. Since orbits under the action of rcwa groups can be finite or infinite, and since infinite orbits are not necessarily residue class unions, the orbit may either be returned in the form of a list, in the form of a residue class union or in the form of an orbit object. It is possible to loop over orbits returned as orbit objects, they can be compared and there is a membership test for them. However note that equality and membership for such orbits cannot always be decided.
gap> G := Group(ClassShift(0,2),ClassTransposition(0,3,1,3)); <rcwa group over Z with 2 generators> gap> Orbit(G,0); Z \ 5(6) gap> Orbit(G,5); [ 5 ] gap> Orbit(G,ResidueClass(0,2)); [ 0(2), 1(6) U 2(6) U 3(6), 1(3) U 3(6), 0(3) U 1(6), 0(3) U 4(6), 1(3) U 0(6), 0(3) U 2(6), 0(6) U 1(6) U 2(6), 2(6) U 3(6) U 4(6), 1(3) U 2(6) ] gap> Length(Orbit(G,ResidueClass(0,4))); 80 gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(0,2,1,4), > ClassReflection(0,3)); <rcwa group over Z with 3 generators> gap> orb := Orbit(G,2); <orbit of 2 under <wild rcwa group over Z with 3 generators>> gap> 1015808 in orb; true gap> First(orb,n->ForAll([n,n+2,n+6,n+8,n+30,n+32,n+36,n+38],IsPrime)); -19
‣ GrowthFunctionOfOrbit( G, n, r_max, size_max ) | ( operation ) |
‣ GrowthFunctionOfOrbit( orb, r_max, size_max ) | ( method ) |
Returns: a list whose (\(r+1\))-th entry is the size of the sphere of radius \(r\) about n under the action of the group G, where the argument r_max is the largest possible radius to be considered, and the computation stops once the sphere size exceeds size_max.
An option "small" is interpreted -- see example below. In place of the group G and the point n, one can pass as first argument also an rcwa group orbit object orb.
gap> G := Group(List([[0,4,1,4],[0,3,5,6],[0,4,5,6]],ClassTransposition)); <(0(4),1(4)),(0(3),5(6)),(0(4),5(6))> gap> GrowthFunctionOfOrbit(G,18,100,20); [ 1, 1, 2, 3, 4, 3, 4, 4, 4, 4, 3, 3, 3, 4, 3, 4, 4, 5, 5, 6, 8, 6, 5, 5, 4, 3, 3, 4, 4, 4, 3, 3, 5, 4, 5, 6, 5, 2, 3, 3, 2, 3, 3, 4, 5, 4, 4, 4, 6, 5, 5, 3, 4, 2, 3, 4, 4, 2, 3, 4, 4, 2, 3, 3, 4, 3, 5, 3, 5, 4, 5, 6, 5, 3, 4, 5, 6, 5, 4, 3, 5, 4, 5, 5, 4, 4, 5, 5, 3, 4, 5, 3, 3, 4, 5, 4, 2, 3, 4, 4, 4 ] gap> last = GrowthFunctionOfOrbit(Orbit(G,18),100,20); true gap> GrowthFunctionOfOrbit(G,18,20,20:small:=[0..100]); rec( smallpoints := [ 18, 24, 25, 27, 30, 32, 33, 36, 37, 39, 40, 41, 42, 44, 45, 48, 49, 51, 52, 53, 56, 57, 59, 60, 61, 64, 65, 66, 68, 69, 71, 75, 76, 77, 80, 81, 83, 88, 89, 92, 93, 95, 100 ], spheresizes := [ 1, 1, 2, 3, 4, 3, 4, 4, 4, 4, 3, 3, 3, 4, 3, 4, 4, 5, 5, 6, 8 ] ) gap> G := Group(List([[0,2,1,2],[1,2,2,4],[1,4,2,6]],ClassTransposition)); <(0(2),1(2)),(1(2),2(4)),(1(4),2(6))> gap> GrowthFunctionOfOrbit(G,0,100,10000); [ 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4, 5, 7, 6, 7, 9, 12, 14, 19, 21, 28, 29, 37, 42, 55, 57, 72, 78, 99, 113, 148, 164, 215, 226, 288, 344, 462, 478, 612, 686, 894, 985, 1284, 1416, 1847, 2018, 2620, 2902, 3786, 4167, 5432, 5958, 7749, 8568, 11178 ]
Given an rcwa group G over ℤ and an integer n, DistanceToNextSmallerPointInOrbit(G,n) computes the smallest number \(d\) such that there is a product \(g\) of \(d\) generators or inverses of generators of G which maps n to an integer with absolute value less than |n|, provided that the orbit of n contains such integer. RCWA provides a function to draw pictures of orbits of rcwa groups on \(ℤ^2\). The pictures are written to files in bitmap- (bmp-) format. The author has successfully tested this feature both under Linux and under Windows, and the generated pictures can be processed further with many common graphics programs:
‣ DrawOrbitPicture( G, p0, bound, h, w, colored, palette, filename ) | ( function ) |
Returns: nothing.
Draws a picture of the orbit(s) of the point(s) p0 under the action of the group G on \(ℤ^2\). The argument p0 is either one point or a list of points. The argument bound denotes the bound to which the ball about p0 is to be computed, in terms of absolute values of coordinates. The size of the generated picture is h x w pixels. The argument colored is a boolean which indicates whether a 24-bit true color picture or a monochrome picture should be generated. In the former case, palette must be a list of triples of integers in the range \(0, \dots, 255\), denoting the RGB values of the colors to be used. In the latter case, palette is not used, and any value can be passed. The picture is written in bitmap- (bmp-) format to a file named filename. This is done using the utility function SaveAsBitmapPicture from ResClasses.
gap> PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(2), > CyclicGroup(3))));; gap> DrawOrbitPicture(PSL2Z,[0,1],2000,512,512,false,fail,"example1.bmp"); gap> DrawOrbitPicture(PSL2Z,Combinations([1..4],2),2000,512,512,true, > [[255,0,0],[0,255,0],[0,0,255]],"example2.bmp");
The pictures drawn in the examples are shown on RCWA's webpage.
Finite orbits give rise to finite quotients of a group, and finite cycles can help to check for conjugacy. Therefore it is important to be able to determine them:
‣ ShortOrbits( G, S, maxlng ) | ( operation ) |
‣ ShortOrbits( G, S, maxlng, maxn ) | ( operation ) |
‣ ShortCycles( g, S, maxlng ) | ( operation ) |
‣ ShortCycles( g, S, maxlng, maxn ) | ( operation ) |
‣ ShortCycles( g, maxlng ) | ( operation ) |
Returns: in the first form a list of all orbits of the rcwa group G of length at most maxlng which intersect non-trivially with the set S. In the second form a list of all orbits of the rcwa group G of length at most maxlng which intersect non-trivially with the set S and which, in terms of euclidean norm, do not exceed maxn. In the third form a list of all cycles of the rcwa permutation g of length at most maxlng which intersect non-trivially with the set S. In the fourth form a list of all cycles of the rcwa permutation g of length at most maxlng which intersect non-trivially with the set S and which, in terms of euclidean norm, do not exceed maxn. In the fifth form a list of all cycles of the rcwa permutation g of length at most maxlng which do not correspond to cycles consisting of residue classes.
The operation ShortOrbits recognizes an option finite. If this option is set, it is assumed that all orbits are finite, in order to speed up the computation. If furthermore maxlng is negative, a list of all orbits which intersect non-trivially with S is returned.
There is an operation CyclesOnFiniteOrbit(G,g,n) which returns a list of all cycles of the rcwa permutation g on the orbit of the point n under the action of the rcwa group G. Here g is assumed to be an element of G, and the orbit of n is assumed to be finite.
gap> G := Group(ClassTransposition(1,4,2,4)*ClassTransposition(1,4,3,4), > ClassTransposition(3,9,6,18)*ClassTransposition(1,6,3,9));; gap> List(ShortOrbits(G,[-15..15],100), > orb->StructureDescription(Action(G,orb))); [ "A15", "A4", "1", "1", "C3", "1", "(C2 x C2 x C2) : (C7 : C3)", "1", "1", "C3", "A19" ] gap> ShortCycles(mKnot(7),[1..100],20); [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7, 8 ], [ 9, 10 ], [ 11, 12 ], [ 13, 14, 16, 18, 20, 22, 19, 17, 15 ], [ 21, 24 ], [ 23, 26 ], [ 25, 28, 32, 36, 31, 27, 30, 34, 38, 33, 29 ], [ 35, 40 ], [ 37, 42, 48, 54, 47, 41, 46, 52, 45, 39, 44, 50, 43 ], [ 77, 88, 100, 114, 130, 148, 127, 109, 124, 107, 122, 105, 120, 103, 89 ] ] gap> G := Group(List([[0,2,1,2],[0,5,4,5],[1,4,0,6]],ClassTransposition));; gap> CyclesOnFiniteOrbit(G,G.1*G.2,0); [ [ 0, 1, 4, 9, 8, 5 ], [ 6, 7 ], [ 10, 11, 14, 19, 18, 15 ], [ 12, 13 ] ] gap> List(CyclesOnFiniteOrbit(G,G.1*G.2*G.3*G.1*G.3*G.2,32),Length); [ 3148, 3148 ]
‣ ShortResidueClassOrbits( G, modulusbound, maxlng ) | ( operation ) |
‣ ShortResidueClassCycles( g, modulusbound, maxlng ) | ( operation ) |
‣ ResidueClassCyclesThroughResidueClass( g, cl, modulusbound ) | ( operation ) |
Returns: in the first form a list of all orbits of residue classes under the action of the rcwa group G which contain a residue class \(r(m)\) such that \(m\) divides modulusbound and which are not longer than maxlng. In the second form a list of all cycles of residue classes of the rcwa permutation g which contain a residue class \(r(m)\) such that \(m\) divides modulusbound and which are not longer than maxlng. In the third form a list of all cycles of residue classes of the rcwa permutation g which contain a residue class \(r(m)\) which is a subset of the residue class cl on which g is affine and whose modulus \(m\) divides modulusbound.
We are only talking about a cycle of residue classes of an rcwa permutation \(g\) if the restrictions of \(g\) to all contained residue classes are affine. Similarly we are only talking about an orbit of residue classes under the action of an rcwa group \(G\) if the restrictions of all elements of \(G\) to all residue classes in the orbit are affine.
The returned lists may contain additional cycles, resp., orbits, which do not contain a residue class \(r(m)\) such that \(m\) divides modulusbound, but which happen to be found without additional efforts.
gap> g := ClassTransposition(0,2,1,2)*ClassTransposition(0,4,1,6); <rcwa permutation of Z with modulus 12> gap> ShortResidueClassCycles(g,Mod(g)^2,20); [ [ 2(12), 3(12) ], [ 10(12), 11(12) ], [ 4(24), 5(24), 7(36), 6(36) ], [ 20(24), 21(24), 31(36), 30(36) ], [ 8(48), 9(48), 13(72), 19(108), 18(108), 12(72) ], [ 40(48), 41(48), 61(72), 91(108), 90(108), 60(72) ], [ 16(96), 17(96), 25(144), 37(216), 55(324), 54(324), 36(216), 24(144) ], [ 80(96), 81(96), 121(144), 181(216), 271(324), 270(324), 180(216), 120(144) ] ] gap> ResidueClassCyclesThroughResidueClass(g,ResidueClass(1,4),2^2*12); [ [ 5(24), 7(36), 6(36), 4(24) ], [ 21(24), 31(36), 30(36), 20(24) ], [ 9(48), 13(72), 19(108), 18(108), 12(72), 8(48) ], [ 41(48), 61(72), 91(108), 90(108), 60(72), 40(48) ] ] gap> Collected(List(ResidueClassCyclesThroughResidueClass(g, > ResidueClass(1,4),2^6*12),Length)); [ [ 4, 2 ], [ 6, 4 ], [ 8, 6 ], [ 10, 8 ], [ 12, 4 ], [ 14, 2 ] ] gap> List(ResidueClassCyclesThroughResidueClass(g, > ResidueClass(1,4),2^4*12),cyc->cyc[1]); [ 5(24), 21(24), 9(48), 41(48), 13(72), 61(72), 17(96), 81(96), 25(144), 121(144), 33(192), 161(192) ] gap> Display(Difference(ResidueClass(1,4),Union(last))); 1(36) U 49(144) U 97(144) U 65(192) U 129(192) gap> G := Group(List([[0,6,5,6],[1,4,4,6],[2,4,3,6]],ClassTransposition)); <(0(6),5(6)),(1(4),4(6)),(2(4),3(6))> gap> ShortResidueClassOrbits(G,48,10); [ [ 7(12) ], [ 8(12) ], [ 1(24), 4(36) ], [ 2(24), 3(36) ], [ 12(24), 17(24), 28(36) ], [ 18(24), 23(24), 27(36) ], [ 37(48), 58(72), 87(108) ], [ 38(48), 57(72), 88(108) ], [ 0(48), 5(48), 10(72), 15(108) ], [ 6(48), 11(48), 9(72), 16(108) ] ]
‣ ComputeCycleLength( g, n ) | ( function ) |
Returns: a record containing the length, the largest point and the position of the largest point of the cycle of the rcwa permutation g which contains the point n, provided that this cycle is finite.
If the cycle is infinite, the function will run into an infinite loop unless the option "abortat" is set to the maximum number of iterates to be tried before aborting. Iterates are not stored, to save memory. The function interprets an option "notify", which defaults to 10000; every "notify" iterations, the number of binary digits of the latest iterate is printed. This output can be suppressed by the option quiet. The function also interprets an option "small", which may be set to a range within which small points are recorded and returned in a component smallpoints.
gap> g := Product(List([[0,5,3,5],[1,2,0,6],[2,4,3,6]], > ClassTransposition)); <rcwa permutation of Z with modulus 180> gap> ComputeCycleLength(g,20:small:=[0..1000]); n = 20: after 10000 steps, the iterate has 1919 binary digits. n = 20: after 20000 steps, the iterate has 2908 binary digits. n = 20: after 30000 steps, the iterate has 1531 binary digits. n = 20: after 40000 steps, the iterate has 708 binary digits. rec( aborted := false, g := <rcwa permutation of Z with modulus 180>, length := 45961, maximum := 180479928411509527091314790144929480041473309862957394384783\ 0525935437431021442346166422201250935268553945158085769924448388724679753\ 5271669245363980744610119632280105994423399614803956244808653465492205657\ 8650363041608376587943180444494842094693691286183613056599672737336761093\ 3101035841077322874883200384115281051837032147150147712534199292886436789\ 7520389780289517825203780151058517520194926468391308525704499649905091899\ 9667529835495635671154681958992898010506577172313321500572646883756736685\ 0158653917532084531267455434808219032998691038943070902228427549279555530\ 6429870190316109419051531138721361826083376315737131067799731181096142797\ 4868525347003646887454985757711743327946232372385342293662007684758208408\ 8635715976464060647431260835037213863991037813998261883899050447111540742\ 5857187943077255493709629738212709349458790098815926920248565399938335540\ 8092502449690267365120996852, maxpos := 19825, n := 20, smallpoints := [ 20, 23, 66, 99, 294, 295, 298, 441, 447, 882, 890, 893 ] )
‣ CycleRepresentativesAndLengths( g, S ) | ( operation ) |
Returns: a list of pairs (cycle representative, length of cycle) for all cycles of the rcwa permutation g which have a nontrivial intersection with the set S, where fixed points are omitted.
The rcwa permutation g is assumed to have only finite cycles. If g has an infinite cycle which intersects non-trivially with S, this may cause an infinite loop unless a cycle length limit is set via the option abortat. The output can be suppressed by the option quiet.
gap> g := ClassTransposition(0,2,1,2)*ClassTransposition(0,4,1,6);; gap> CycleRepresentativesAndLengths(g,[0..50]); [ [ 2, 2 ], [ 4, 4 ], [ 8, 6 ], [ 10, 2 ], [ 14, 2 ], [ 16, 8 ], [ 20, 4 ], [ 22, 2 ], [ 26, 2 ], [ 28, 4 ], [ 32, 10 ], [ 34, 2 ], [ 38, 2 ], [ 40, 6 ], [ 44, 4 ], [ 46, 2 ], [ 50, 2 ] ] gap> g := Product(List([[0,5,3,5],[1,2,0,6],[2,4,3,6]], > ClassTransposition)); <rcwa permutation of Z with modulus 180> gap> CycleRepresentativesAndLengths(g,[0..100]:abortat:=100000); n = 20: after 10000 steps, the iterate has 1919 binary digits. n = 20: after 20000 steps, the iterate has 2908 binary digits. n = 20: after 30000 steps, the iterate has 1531 binary digits. n = 20: after 40000 steps, the iterate has 708 binary digits. n = 79: after 10000 steps, the iterate has 1679 binary digits. n = 100: after 10000 steps, the iterate has 712 binary digits. n = 100: after 20000 steps, the iterate has 2507 binary digits. n = 100: after 30000 steps, the iterate has 3311 binary digits. n = 100: after 40000 steps, the iterate has 3168 binary digits. n = 100: after 50000 steps, the iterate has 3947 binary digits. n = 100: after 60000 steps, the iterate has 4793 binary digits. n = 100: after 70000 steps, the iterate has 5325 binary digits. n = 100: after 80000 steps, the iterate has 6408 binary digits. n = 100: after 90000 steps, the iterate has 7265 binary digits. n = 100: after 100000 steps, the iterate has 7918 binary digits. [ [ 0, 7 ], [ 5, 3 ], [ 7, 7159 ], [ 11, 9 ], [ 19, 342 ], [ 20, 45961 ], [ 25, 3 ], [ 26, 21 ], [ 29, 2 ], [ 31, 3941 ], [ 34, 19 ], [ 37, 7 ], [ 40, 5 ], [ 41, 7 ], [ 46, 3 ], [ 49, 2 ], [ 59, 564 ], [ 61, 577 ], [ 65, 3 ], [ 67, 23 ], [ 71, 41 ], [ 79, 16984 ], [ 80, 5 ], [ 85, 3 ], [ 86, 3 ], [ 89, 2 ], [ 91, 9 ], [ 94, 1355 ], [ 97, 7 ], [ 100, fail ] ]
Often one also wants to know which residue classes an rcwa mapping or an rcwa group fixes setwise:
‣ FixedResidueClasses( g, maxmod ) | ( operation ) |
‣ FixedResidueClasses( G, maxmod ) | ( operation ) |
Returns: the set of residue classes with modulus greater than 1 and less than or equal to maxmod which the rcwa mapping g, respectively the rcwa group G, fixes setwise.
gap> FixedResidueClasses(ClassTransposition(0,2,1,4),8); [ 2(3), 3(4), 4(5), 6(7), 3(8), 7(8) ] gap> FixedResidueClasses(Group(ClassTransposition(0,2,1,4), > ClassTransposition(0,3,1,3)),12); [ 2(3), 8(9), 11(12) ]
Frequently one needs to compute balls of certain radius around points or group elements, be it to estimate the growth of a group, be it to see how an orbit looks like, be it to search for a group element with certain properties or be it for other purposes:
‣ Ball( G, g, r ) | ( method ) |
‣ Ball( G, p, r, action ) | ( method ) |
‣ Ball( G, p, r ) | ( method ) |
Returns: the ball of radius r around the element g in the group G, respectively the ball of radius r around the point p under the action action of the group G, respectively the ball of radius r around the point p under the action OnPoints of the group G,
All balls are understood with respect to GeneratorsOfGroup(G). As membership tests can be expensive, the former method does not check whether g is indeed an element of G. The methods require that element- / point comparisons are cheap. They are not only applicable to rcwa groups. If the option Spheres is set, the ball is split up and returned as a list of spheres. There is a related operation RestrictedBall(G,g,r,modulusbound) specifically for rcwa groups which computes only those elements of the ball whose moduli do not exceed modulusbound, and which can be reached from g without computing intermediate elements whose moduli do exceed modulusbound. The latter operation interprets an option "boundaffineparts". -- If this option is set and the group G and the element g are in sparse representation, then modulusbound is actually taken to be a bound on the number of affine parts rather than a bound on the modulus.
gap> PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(2), > CyclicGroup(3))));; gap> List([1..10],k->Length(Ball(PSL2Z,[0,1],k,OnTuples))); [ 4, 8, 14, 22, 34, 50, 74, 106, 154, 218 ] gap> Ball(Group((1,2),(2,3),(3,4)),(),2:Spheres); [ [ () ], [ (3,4), (2,3), (1,2) ], [ (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,3,2) ] ] gap> G := Group(List([[1,2,4,6],[1,3,2,6],[2,3,4,6]],ClassTransposition));; gap> B := RestrictedBall(G,One(G),20,36:Spheres);; # try replacing 36 by 72 gap> List(B,Length); [ 1, 3, 6, 12, 4, 6, 6, 4, 4, 4, 6, 6, 3, 3, 2, 0, 0, 0, 0, 0, 0 ]
It is possible to determine group elements which map a given tuple of elements of the underlying ring to a given other tuple, if such elements exist:
‣ RepresentativeAction( G, source, destination, action ) | ( method ) |
Returns: an element of G which maps source to destination under the action given by action.
If an element satisfying this condition does not exist, this method either returns fail or runs into an infinite loop. The problem whether source and destination lie in the same orbit under the action action of G is hard, and in its general form most likely computationally undecidable.
In cases where rather a word in the generators of G than the actual group element is needed, one should use the operation RepresentativeActionPreImage instead. This operation takes five arguments. The first four are the same as those of RepresentativeAction, and the fifth is a free group whose generators are to be used as letters of the returned word. Note that RepresentativeAction calls RepresentativeActionPreImage and evaluates the returned word. The evaluation of the word can very well take most of the time if G is wild and coefficient explosion occurs.
The algorithm is based on computing balls of increasing radius around source and destination until they intersect non-trivially.
gap> a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; SetName(a,"a"); gap> b := ClassShift(1,4:Name:="b");; G := Group(a,b);; gap> elm := RepresentativeAction(G,[7,4,9],[4,5,13],OnTuples);; gap> Display(elm); Rcwa permutation of Z with modulus 12 / | n-3 if n in 1(6) U 10(12) | n+4 if n in 5(12) U 9(12) n |-> < n+1 if n in 4(12) | n if n in 0(6) U 2(6) U 3(12) U 11(12) | \ gap> List([7,4,9],n->n^elm); [ 4, 5, 13 ] gap> elm := RepresentativeAction(G,[6,-3,8],[-9,4,11],OnPoints);; gap> Display(elm); Rcwa permutation of Z with modulus 12 / | 2n/3 if n in 0(6) U 3(12) | (4n+1)/3 if n in 2(6) U 11(12) | (4n-1)/3 if n in 4(6) U 7(12) n |-> < (2n-8)/3 if n in 1(12) | (4n-17)/3 if n in 5(12) | (4n-15)/3 if n in 9(12) | \ gap> [6,-3,8]^elm; List([6,-3,8],n->n^elm); # `OnPoints' allows reordering [ -9, 4, 11 ] [ 4, -9, 11 ] gap> F := FreeGroup("a","b");; phi := EpimorphismByGenerators(F,G);; gap> w := RepresentativeActionPreImage(G,[10,-4,9,5],[4,5,13,-8], > OnTuples,F); a*b^-1*a^-1*(b^-1*a)^2*b*a*b^-2*a*b*a^-1*b gap> elm := w^phi; <rcwa permutation of Z with modulus 324> gap> List([10,-4,9,5],n->n^elm); [ 4, 5, 13, -8 ]
Sometimes an rcwa group fixes a certain partition of the underlying ring into unions of residue classes. If this happens, then any orbit is clearly a subset of exactly one of these parts. Further, such a partition often gives rise to proper quotients of the group:
‣ ProjectionsToInvariantUnionsOfResidueClasses( G, m ) | ( operation ) |
Returns: the projections of the rcwa group G to the unions of residue classes (mod m) which it fixes setwise.
The corresponding partition of a set of representatives for the residue classes (mod m) can be obtained by the operation OrbitsModulo(G,m).
gap> G := Group(ClassTransposition(0,2,1,2),ClassShift(3,4));; gap> ProjectionsToInvariantUnionsOfResidueClasses(G,4); [ [ ( 0(2), 1(2) ), ClassShift( 3(4) ) ] -> [ ( 0(4), 1(4) ), IdentityMapping( Integers ) ], [ ( 0(2), 1(2) ), ClassShift( 3(4) ) ] -> [ ( 2(4), 3(4) ), <rcwa permutation of Z with modulus 4> ] ] gap> List(last,phi->Support(Image(phi))); [ 0(4) U 1(4), 2(4) U 3(4) ]
Given two partitions of the underlying ring into the same number of unions of residue classes, there is always an rcwa permutation which maps the one to the other:
‣ RepresentativeAction( RCWA(R), P1, P2 ) | ( method ) |
Returns: an element of RCWA(\(R\)) which maps the partition P1 to P2.
The arguments P1 and P2 must be partitions of the underlying ring \(R\) into the same number of unions of residue classes. The method for \(R = ℤ\) recognizes the option IsTame, which can be used to demand a tame result. If this option is set and there is no tame rcwa permutation which maps P1 to P2, the method runs into an infinite loop. This happens if the condition in Theorem 2.8.9 in [Koh05] is not satisfied. If the option IsTame is not set and the partitions P1 and P2 both consist entirely of single residue classes, then the returned mapping is affine on any residue class in P1.
gap> P1 := AllResidueClassesModulo(3); [ 0(3), 1(3), 2(3) ] gap> P2 := List([[0,2],[1,4],[3,4]],ResidueClass); [ 0(2), 1(4), 3(4) ] gap> elm := RepresentativeAction(RCWA(Integers),P1,P2); <rcwa permutation of Z with modulus 3> gap> P1^elm = P2; true gap> IsTame(elm); false gap> elm := RepresentativeAction(RCWA(Integers),P1,P2:IsTame); <tame rcwa permutation of Z with modulus 24> gap> P1^elm = P2; true gap> elm := RepresentativeAction(RCWA(Integers), > [ResidueClass(1,3), > ResidueClassUnion(Integers,3,[0,2])], > [ResidueClassUnion(Integers,5,[2,4]), > ResidueClassUnion(Integers,5,[0,1,3])]); <rcwa permutation of Z with modulus 6> gap> [ResidueClass(1,3),ResidueClassUnion(Integers,3,[0,2])]^elm; [ 2(5) U 4(5), Z \ 2(5) U 4(5) ]
‣ CollatzLikeMappingByOrbitTree( G, n, min_r, max_r ) | ( operation ) |
Returns: either an rcwa mapping \(f\) which maps the sphere of radius \(r\) about n under the action of G into the sphere of radius \(r-1\) about n for every \(r\) ranging from min_r to max_r, or fail.
Obviously not for every rcwa group and every root point a mapping \(f\) with these properties exists, and if it exists, it usually depends on the choice of generators of the group.
gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(1,2,2,4), > ClassTransposition(1,4,2,6));; gap> G := SparseRep(G);; gap> f := CollatzLikeMappingByOrbitTree(G,0,4,10); <rcwa mapping of Z with modulus 4 and 4 affine parts> gap> Display(f); Rcwa mapping of Z with modulus 4 and 4 affine parts / | n+1 if n in 0(4) | (3n+1)/2 if n in 1(4) n |-> < n/2 if n in 2(4) | n-1 if n in 3(4) | \ gap> B := Ball(G,0,15:Spheres); [ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 6 ], [ 7 ], [ 14 ], [ 9, 15 ], [ 8, 18, 30 ], [ 5, 19, 31 ], [ 4, 10, 38, 62 ], [ 11, 25, 39, 41, 63 ], [ 22, 24, 40, 50, 78, 82, 126 ], [ 23, 33, 51, 79, 83, 127 ], [ 32, 46, 66, 102, 158, 166, 254 ], [ 21, 47, 67, 103, 105, 159, 167, 169, 255 ] ] gap> List([3..15],i->IsSubset(B[i-1],B[i]^f)); [ true, true, true, true, true, true, true, true, true, true, true, true, true ] gap> Trajectory(f,52,[0,1]); [ 52, 53, 80, 81, 122, 61, 92, 93, 140, 141, 212, 213, 320, 321, 482, 241, 362, 181, 272, 273, 410, 205, 308, 309, 464, 465, 698, 349, 524, 525, 788, 789, 1184, 1185, 1778, 889, 1334, 667, 666, 333, 500, 501, 752, 753, 1130, 565, 848, 849, 1274, 637, 956, 957, 1436, 1437, 2156, 2157, 3236, 3237, 4856, 4857, 7286, 3643, 3642, 1821, 2732, 2733, 4100, 4101, 6152, 6153, 9230, 4615, 4614, 2307, 2306, 1153, 1730, 865, 1298, 649, 974, 487, 486, 243, 242, 121, 182, 91, 90, 45, 68, 69, 104, 105, 158, 79, 78, 39, 38, 19, 18, 9, 14, 7, 6, 3, 2, 1 ]
There are a couple of attributes which a priori make only sense for tame rcwa groups. With their help, various structural information about a given such group can be obtained. We have already seen above that there are for example methods for IsSolvableGroup, IsPerfectGroup and DerivedSubgroup available for tame rcwa groups, while testing wild groups for solvability or perfectness is currently not always feasible. The purpose of this section is to describe the specific attributes of tame groups which are needed for these computations.
‣ RespectedPartition( G ) | ( attribute ) |
‣ RespectedPartition( g ) | ( attribute ) |
Returns: a shortest and coarsest possible respected partition of the rcwa group G / of the rcwa permutation g.
A tame element \(g\) \(\in\) RCWA(\(R\)) permutes a partition of \(R\) into finitely many residue classes on all of which it is affine. Given a tame group \(G\) \(<\) RCWA(\(R\)), there is a common such partition for all elements of \(G\). We call the mentioned partitions respected partitions of \(g\) or \(G\), respectively.
An rcwa group or an rcwa permutation has a respected partition if and only if it is tame. This holds either by definition or by Theorem 2.5.8 in [Koh05], depending on how one introduces the notion of tameness.
There is an operation RespectsPartition(G,P) / RespectsPartition(g,P), which tests whether G or g respects a given partition P. The permutation induced by g on P can be computed efficiently by PermutationOpNC(g,P,OnPoints).
gap> G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2)); <rcwa group over Z with 2 generators> gap> IsTame(G); true gap> Size(G); infinity gap> P := RespectedPartition(G); [ 0(4), 2(4), 1(6), 3(6), 5(6) ]
‣ ActionOnRespectedPartition( G ) | ( attribute ) |
‣ KernelOfActionOnRespectedPartition( G ) | ( attribute ) |
‣ RankOfKernelOfActionOnRespectedPartition( G ) | ( attribute ) |
Returns: the action of the tame rcwa group G on RespectedPartition(G), the kernel of this action or the rank of the latter, respectively.
The method for KernelOfActionOnRespectedPartition uses the package Polycyclic [EHN13]. The rank of the largest free abelian subgroup of the kernel of the action of G on its stored respected partition is RankOfKernelOfActionOnRespectedPartition(G).
gap> G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));; gap> H := ActionOnRespectedPartition(G); Group([ (1,3), (1,2) ]) gap> H = Action(G,P); true gap> Size(H); 6 gap> K := KernelOfActionOnRespectedPartition(G); <rcwa group over Z with 3 generators> gap> RankOfKernelOfActionOnRespectedPartition(G); 3 gap> Index(G,K); 6 gap> List(GeneratorsOfGroup(K),Factorization); [ [ ClassShift( 0(4) ) ], [ ClassShift( 2(4) ) ], [ ClassShift( 1(6) ) ] ] gap> Image(IsomorphismPcpGroup(K)); Pcp-group with orders [ 0, 0, 0 ]
Let \(G\) be a tame rcwa group over ℤ, let \(\mathcal{P}\) be a respected partition of \(G\) and put \(m := |\mathcal{P}|\). Then there is an rcwa permutation \(g\) which maps \(\mathcal{P}\) to the partition of ℤ into the residue classes (mod \(m\)), and the conjugate \(G^g\) of \(G\) under such a permutation is integral (cf. [Koh05], Theorem 2.5.14).
The conjugate \(G^g\) can be determined by the operation IntegralConjugate, and the conjugating permutation \(g\) can be determined by the operation IntegralizingConjugator. Both operations are applicable to rcwa permutations as well. Note that a tame rcwa group does not determine its integral conjugate uniquely.
gap> G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));; gap> G^IntegralizingConjugator(G) = IntegralConjugate(G); true gap> RespectedPartition(G); [ 0(4), 2(4), 1(6), 3(6), 5(6) ] gap> RespectedPartition(G)^IntegralizingConjugator(G); [ 0(5), 1(5), 2(5), 3(5), 4(5) ] gap> last = RespectedPartition(IntegralConjugate(G)); true
There are methods for the operation Random for RCWA(\(R\)) and CT(\(R\)). These methods are designed to be suitable for generating interesting examples. No particular distribution is guaranteed.
gap> elm := Random(RCWA(Integers));; gap> Display(elm); Rcwa permutation of Z with modulus 180 / | 6n+12 if n in 2(10) U 4(10) U 6(10) U 8(10) | 3n+3 if n in 1(20) U 5(20) U 9(20) U 17(20) | 6n+10 if n in 0(10) | (n+1)/2 if n in 15(60) U 27(60) U 39(60) U 51(60) | (n+7)/2 if n in 19(60) U 31(60) U 43(60) U 55(60) | 3n+1 if n in 13(20) | (-n+17)/6 if n in 23(180) U 35(180) U 59(180) U 71(180) U n |-> < 95(180) U 131(180) U 143(180) U 179(180) | (-n-1)/6 if n in 11(180) U 47(180) U 83(180) U 155(180) | (-n+7)/2 if n in 3(60) | (n+3)/2 if n in 7(60) | (n-17)/6 if n in 107(180) | (-n+11)/6 if n in 119(180) | (-n+29)/6 if n in 167(180) | \
The elements which are returned by this method are obtained by multiplying class shifts (see ClassShift (2.2-1)), class reflections (see ClassReflection (2.2-2)) and class transpositions (see ClassTransposition (2.2-3)). These factors can be retrieved by factoring:
gap> Factorization(elm); [ ClassTransposition(0,2,3,4), ClassTransposition(1,2,4,6), ClassShift(0,2), ClassShift(1,3), ClassReflection(2,5), ClassReflection(1,3), ClassReflection(1,2) ]
‣ IsRcwaGroup( G ) | ( filter ) |
‣ IsRcwaGroupOverZ( G ) | ( filter ) |
‣ IsRcwaGroupOverZ_pi( G ) | ( filter ) |
‣ IsRcwaGroupOverGFqx( G ) | ( filter ) |
Returns: true if G is an rcwa group, an rcwa group over the ring of integers, an rcwa group over a semilocalization of the ring of integers or an rcwa group over a polynomial ring in one variable over a finite field, respectively, and false otherwise.
Often the same methods can be used for rcwa groups over the ring of integers and over its semilocalizations. For this reason there is a category IsRcwaGroupOverZOrZ_pi which is the union of IsRcwaGroupOverZ and IsRcwaGroupOverZ_pi.
To allow distinguishing the groups RCWA(\(R\)) and CT(\(R\)) from others, they have the characteristic property IsNaturalRCWA or IsNaturalCT, respectively.
generated by GAPDoc2HTML