<!-- #################################################################### --> <!-- ## ## --> <!-- ## rcwagrp.xml RCWA documentation Stefan Kohl ## --> <!-- ## ## --> <!-- ## $Id: rcwagrp.xml,v 1.155 2007/09/26 14:16:45 stefan Exp $ ## --> <!-- ## ## --> <!-- #################################################################### --> <Chapter Label="ch:RcwaGroups"> <Heading>Residue-Class-Wise Affine Groups</Heading> <Ignore Remark="set screen width to 75, for the example tester"> <Example> <![CDATA[ gap> SizeScreen([75,24]);; ]]> </Example> </Ignore> In this chapter, we describe how to construct residue-class-wise affine groups and how to compute with them. <!-- #################################################################### --> <Section Label="sec:ContructingRcwaGroups"> <Heading>Constructing residue-class-wise affine groups</Heading> <Index Key="Group"><C>Group</C></Index> <Index Key="GroupByGenerators"><C>GroupByGenerators</C></Index> <Index Key="GroupWithGenerators"><C>GroupWithGenerators</C></Index> As any other groups in &GAP;, residue-class-wise affine groups can be constructed by <C>Group</C>, <C>GroupByGenerators</C> or <C>GroupWithGenerators</C>. <Example> <![CDATA[ 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 ]]> </Example> <Index Key="View" Subkey="for an rcwa group"><C>View</C></Index> <Index Key="Display" Subkey="for an rcwa group"><C>Display</C></Index> <Index Key="Print" Subkey="for an rcwa group"><C>Print</C></Index> <Index Key="String" Subkey="for an rcwa group"><C>String</C></Index> There are methods for the operations <C>View</C>, <C>Display</C>, <C>Print</C> and <C>String</C> which are applicable to rcwa groups. All rcwa groups over a ring <M>R</M> are subgroups of RCWA(<M>R</M>). The group RCWA(<M>R</M>) itself is not finitely generated, thus cannot be constructed as described above. It is handled as a special case: <ManSection> <Func Name="RCWA" Arg="R" Label="the group of all rcwa permutations of a ring"/> <Returns> The group RCWA(<A>R</A>) of all residue-class-wise affine permutations of the ring <A>R</A>. </Returns> <Description> <Example> <![CDATA[ gap> RCWA_Z := RCWA(Integers); RCWA(Z) gap> IsSubgroup(RCWA_Z,G); true ]]> </Example> </Description> </ManSection> Examples of rcwa permutations can be obtained via <C>Random(RCWA(<A>R</A>))</C>, see Section <Ref Label="sec:Random"/>. <P/> <Alt Only="LaTeX">\pagebreak[4]</Alt> We denote the group which is generated by all class transpositions of the ring <M>R</M> by CT(<M>R</M>). This group is handled as a special case as well: <ManSection> <Func Name="CT" Arg="R" Label="the group generated by all class transpositions of a ring"/> <Returns> The group CT(<A>R</A>) which is generated by all class transpositions of the ring <M>R</M>. </Returns> <Description> <Example> <![CDATA[ gap> CT_Z := CT(Integers); CT(Z) gap> IsSimple(CT_Z); # One of a longer list of stored attributes/properties. true gap> IsSubgroup(CT_Z,G); false ]]> </Example> </Description> </ManSection> Another way of constructing an rcwa group is taking the image of an rcwa representation: <ManSection> <Attr Name="IsomorphismRcwaGroup" Arg="G, R" Label="for a group, over a given ring"/> <Attr Name="IsomorphismRcwaGroup" Arg="G" Label="for a group"/> <Returns> A monomorphism from the group <A>G</A> to RCWA(<A>R</A>) or to RCWA(<M>\mathbb{Z}</M>), respectively. </Returns> <Description> The best-supported case is <A>R</A> = <M>\mathbb{Z}</M>. 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 <Cite Key="LaHarpe00"/>), and the method for free groups uses an adaptation of the construction given on page 27 in <Cite Key="LaHarpe00"/> from PSL(2,<M>\mathbb{C}</M>) to RCWA(<M>\mathbb{Z}</M>). <P/> <Example> <![CDATA[ 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 ] -> [ <bijective rcwa mapping of Z with modulus 12>, <bijective rcwa mapping of Z with modulus 24>, <bijective rcwa mapping of Z with modulus 12>, <bijective rcwa mapping of Z with modulus 72>, <bijective rcwa mapping of Z with modulus 36> ] gap> IsomorphismRcwaGroup(FreeGroup(2)); [ f1, f2 ] -> [ <wild bijective rcwa mapping of Z with modulus 8>, <wild bijective rcwa mapping of Z with modulus 8> ] gap> F2 := Image(last); <wild rcwa group over Z with 2 generators> ]]> </Example> </Description> </ManSection> The class of groups which can faithfully be represented as rcwa groups over the integers is closed under taking direct products, under taking wreath products with finite groups and under taking wreath products with the infinite cyclic group <M>(\mathbb{Z},+)</M>. Therefore these operations can be used to build rcwa groups as well: <ManSection> <Meth Name="DirectProduct" Arg="G1, G2, ..." Label="for rcwa groups over Z"/> <Returns> An rcwa group isomorphic to the direct product of the rcwa groups over <M>\mathbb{Z}</M> given as arguments. </Returns> <Description> There is certainly no unique or canonical way to embed a direct product of rcwa groups into RCWA(<M>\mathbb{Z}</M>). This method chooses to embed the groups <A>G1</A>, <A>G2</A>, <A>G3</A> ... via restrictions by <M>n \mapsto mn</M>, <M>n \mapsto mn+1</M>, <M>n \mapsto mn+2</M> ... (<M>\rightarrow</M> <Ref Oper="Restriction" Label="of an rcwa group, by an injective rcwa mapping"/>), where <M>m</M> denotes the number of groups given as arguments. <Example> <![CDATA[ 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 ]]> </Example> </Description> </ManSection> <ManSection> <Heading> WreathProduct (for an rcwa group over Z, with a permutation group or (<M>\mathbb{Z}</M>,+)) </Heading> <Meth Name="WreathProduct" Arg="G, P" Label="for an rcwa group over Z and a permutation group"/> <Meth Name="WreathProduct" Arg="G, Z" Label="for an rcwa group over Z and the infinite cyclic group"/> <Returns> An rcwa group isomorphic to the wreath product of the rcwa group <A>G</A> over <M>\mathbb{Z}</M> with the finite permutation group <A>P</A> or with the infinite cyclic group <A>Z</A>, respectively. </Returns> <Description> The first-mentioned method embeds the <C>DegreeAction(<A>P</A>)</C>th direct power of <A>G</A> using the method for <C>DirectProduct</C>, and lets the permutation group <A>P</A> act naturally on the set of residue classes modulo <C>DegreeAction(<A>P</A>)</C>. The second-mentioned method restricts (<M>\rightarrow</M> <Ref Oper="Restriction" Label="of an rcwa group, by an injective rcwa mapping"/>) the group <A>G</A> to the residue class 3(4), and maps the generator of the infinite cyclic group <A>Z</A> to <C>ClassTransposition(0,2,1,2) * ClassTransposition(0,2,1,4)</C>. <Example> <![CDATA[ gap> F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));; gap> F2wrA5 := WreathProduct(F2,AlternatingGroup(5));; gap> Embedding(F2wrA5,1); [ <wild bijective rcwa mapping of Z with modulus 8>, <wild bijective rcwa mapping of Z with modulus 8> ] -> [ <wild bijective rcwa mapping of Z with modulus 40>, <wild bijective rcwa mapping of Z with modulus 40> ] gap> Embedding(F2wrA5,2); [ (1,2,3,4,5), (3,4,5) ] -> [ <bijective rcwa mapping of Z with modulus 5, of order 5>, <bijective rcwa mapping of Z with modulus 5, of order 3> ] gap> ZwrZ := WreathProduct(Group(ClassShift(0,1)),Group(ClassShift(0,1))); <wild rcwa group over Z with 2 generators> gap> Embedding(ZwrZ,1); [ ClassShift(0,1) ] -> [ <tame bijective rcwa mapping of Z with modulus 4, of order infinity> ] gap> Embedding(ZwrZ,2); [ ClassShift(0,1) ] -> [ <wild bijective rcwa mapping of Z with modulus 4> ] ]]> </Example> </Description> </ManSection> Many of the above group constructions are based on certain monomorphisms from the group RCWA(<M>R</M>) into itself. 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 <E>restriction monomorphisms</E>. The following operation computes images of rcwa mappings and -groups under them: <ManSection> <Heading> Restriction (of an rcwa mapping or -group, by an injective rcwa mapping) </Heading> <Oper Name="Restriction" Arg="g, f" Label="of an rcwa mapping, by an injective rcwa mapping"/> <Oper Name="Restriction" Arg="G, f" Label="of an rcwa group, by an injective rcwa mapping"/> <Returns> The restriction of the rcwa mapping <A>g</A> (respectively the rcwa group <A>G</A>) by the injective rcwa mapping <A>f</A>. </Returns> <Description> By definition, the <E>restriction</E> <M>g_f</M> of an rcwa mapping <A>g</A> by an injective rcwa mapping <A>f</A> is the unique rcwa mapping which satisfies the equation <M>f \cdot g_f = g \cdot f</M> and which fixes the complement of the image of <A>f</A> pointwise. If <A>f</A> is bijective, the restriction of <A>g</A> by <A>f</A> is just the conjugate of <A>g</A> under <A>f</A>. <P/> The <E>restriction</E> of an rcwa group <A>G</A> by an injective rcwa mapping <A>f</A> is defined as the group whose elements are the restrictions of the elements of <A>G</A> by <A>f</A>. The restriction of <A>G</A> by <A>f</A> acts on the image of <A>f</A> and fixes its complement pointwise. <Example> <![CDATA[ gap> F2tilde := Restriction(F2,RcwaMapping([[5,3,1]])); <wild rcwa group over Z with 2 generators> gap> Support(F2tilde); 3(5) ]]> </Example> </Description> </ManSection> <ManSection> <Heading> Induction (of an rcwa mapping or -group, by an injective rcwa mapping) </Heading> <Oper Name ="Induction" Arg="g, f" Label="of an rcwa mapping, by an injective rcwa mapping"/> <Oper Name ="Induction" Arg="G, f" Label="of an rcwa group, by an injective rcwa mapping"/> <Returns> The induction of the rcwa mapping <A>g</A> (respectively the rcwa group <A>G</A>) by the injective rcwa mapping <A>f</A>. </Returns> <Description> <E>Induction</E> is the right inverse of restriction, i.e. it is <C>Induction(Restriction(<A>g</A>,<A>f</A>),<A>f</A>) = <A>g</A></C> and <C>Induction(Restriction(<A>G</A>,<A>f</A>),<A>f</A>) = <A>G</A></C>. The mapping <A>g</A> respectively the group <A>G</A> must not move points outside the image of <A>f</A>. <Example> <![CDATA[ gap> Induction(F2tilde,RcwaMapping([[5,3,1]])) = F2; true ]]> </Example> </Description> </ManSection> <Index Key="rcwa group" Subkey="modulus">rcwa group</Index> <Index Key="rcwa group" Subkey="multiplier">rcwa group</Index> <Index Key="rcwa group" Subkey="divisor">rcwa group</Index> <Index Key="rcwa group" Subkey="prime set">rcwa group</Index> <Index Key="rcwa group" Subkey="integral">rcwa group</Index> <Index Key="rcwa group" Subkey="class-wise order-preserving"> rcwa group </Index> <Index Key="Modulus" Subkey="of an rcwa group"><C>Modulus</C></Index> <Index Key="Mod" Subkey="for an rcwa group"><C>Mod</C></Index> <Index Key="ModulusOfRcwaMonoid" Subkey="for an rcwa group"> <C>ModulusOfRcwaMonoid</C> </Index> <Index Key="Multiplier" Subkey="of an rcwa group"><C>Multiplier</C></Index> <Index Key="Mult" Subkey="for an rcwa group"><C>Mult</C></Index> <Index Key="Divisor" Subkey="of an rcwa group"><C>Divisor</C></Index> <Index Key="Div" Subkey="for an rcwa group"><C>Div</C></Index> <Index Key="PrimeSet" Subkey="of an rcwa group"><C>PrimeSet</C></Index> <Index Key="IsIntegral" Subkey="for an rcwa group"><C>IsIntegral</C></Index> <Index Key="IsClassWiseOrderPreserving" Subkey="for an rcwa group"> <C>IsClassWiseOrderPreserving</C> </Index> <Index Key="IsSignPreserving" Subkey="for an rcwa group"> <C>IsSignPreserving</C> </Index> Basic attributes of an rcwa group which are derived from the coefficients of its elements are <C>Modulus</C>, <C>Multiplier</C>, <C>Divisor</C> and <C>PrimeSet</C>. The <E>modulus</E> 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 <E>multiplier</E> respectively <E>divisor</E> of an rcwa group is the lcm of the multipliers respectively divisors of its elements in case such an lcm exists and <M>\infty</M> otherwise. The <E>prime set</E> of an rcwa group is the union of the prime sets of its elements. There are shorthands <C>Mod</C>, <C>Mult</C> and <C>Div</C> defined for <C>Modulus</C>, <C>Multiplier</C> and <C>Divisor</C>, respectively. An rcwa group is called <E>integral</E> respectively <E>class-wise order-preserving</E> if all of its elements are so. There are corresponding methods available for <C>IsIntegral</C> and <C>IsClassWiseOrderPreserving</C>. There is a property <C>IsSignPreserving</C>, which indicates whether a given rcwa group over <M>\mathbb{Z}</M> acts on the set of nonnegative integers. The latter holds for any subgroup of CT(<M>\mathbb{Z}</M>). <Example> <![CDATA[ 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,IsIntegral, > IsClassWiseOrderPreserving,IsSignPreserving],f->f(G)); [ 24, 2, 2, [ 2, 3 ], false, false, false ] ]]> </Example> </Section> <!-- #################################################################### --> <Section Label="sec:InvestigatingRcwaGroups"> <Heading> Basic routines for investigating residue-class-wise affine groups </Heading> 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 some information on the group structure is a dedicated method for the operation <C>StructureDescription</C>: <ManSection> <Meth Name="StructureDescription" Arg="G" Label="for an rcwa group"/> <Returns> A string which describes the structure of the rcwa group <A>G</A> to some extent. </Returns> <Description> The attribute <C>StructureDescription</C> 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. <P/> Wreath products are denoted by <C>wr</C>, and free products are denoted by <C>*</C>. The infinite cyclic group <M>(\mathbb{Z},+)</M> is denoted by <C>Z</C>, the infinite dihedral group is denoted by <C>D0</C> and free groups of rank <M>2,3,4,\dots</M> are denoted by <C>F2</C>, <C>F3</C>, <C>F4</C>, <M>\dots</M>. While for finite groups the symbol <C>.</C> 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 <C><unknown></C>. In general, the structure of a section denoted by <C><unknown></C> can be very complicated and very difficult to exhibit. While for isomorphic finite groups always the same structure description is computed, this cannot be guaranteed for isomorphic rcwa groups. <Example> <![CDATA[ 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" ]]> </Example> </Description> </ManSection> However the extent to which the structure of an rcwa group can be exhibited automatically is certainly 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. <P/> <Index Key="Size" Subkey="for an rcwa group"><C>Size</C></Index> The order of an rcwa group can be computed by the operation <C>Size</C>. An rcwa group is finite if and only if it is tame and its action on a suitably chosen respected partition (see <Ref Attr="RespectedPartition" Label="of a tame rcwa group"/>) 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. <Example> <![CDATA[ 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 ]]> </Example> <Index Key="IsomorphismPermGroup" Subkey="for a finite rcwa group"> <C>IsomorphismPermGroup</C> </Index> For a finite rcwa group, an isomorphism to a permutation group can be computed by <C>IsomorphismPermGroup</C>: <Example> <![CDATA[ gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(0,3,1,3));; gap> IsomorphismPermGroup(G); [ ClassTransposition(0,2,1,2), ClassTransposition(0,3,1,3) ] -> [ (1,2)(3,4)(5,6), (1,2)(4,5) ] ]]> </Example> <Index Key="rcwa group" Subkey="membership test">rcwa group</Index> Next we say a few words about the membership test for rcwa groups. For tame rcwa groups, membership or non-membership can always be decided. For wild groups, membership or non-membership can very often be decided quite quick as well, but not always. On Info level 2 of <C>InfoRCWA</C> the membership test provides information on reasons why the given rcwa permutation is an element of the given rcwa group or not. <P/> The direct product of two free groups of rank 2 can faithfully be represented as an rcwa group. According to <Cite Key="Mihailova58"/> this implies that in general the membership problem for rcwa groups is algorithmically undecidable. <Alt Only="LaTeX">\pagebreak[4]</Alt> <Example> <![CDATA[ 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 ]]> </Example> <Index Key="rcwa group" Subkey="conjugacy problem">rcwa group</Index> <Index Key="IsConjugate" Subkey="for elements of RCWA(R)"> <C>IsConjugate</C> </Index> <Index Key="IsConjugate" Subkey="for elements of CT(R)"> <C>IsConjugate</C> </Index> The conjugacy problem for rcwa groups is difficult, and &RCWA; provides only methods to solve it in some reasonably easy cases. <Example> <![CDATA[ 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)); <bijective rcwa mapping of Z with modulus 48> gap> ClassTransposition(0,2,1,6)^g = ClassTransposition(1,4,0,8); true ]]> </Example> <Index Key="NrConjugacyClassesOfRCWAZOfOrder"> <C>NrConjugacyClassesOfRCWAZOfOrder</C> </Index> The number of conjugacy classes of RCWA(<M>\mathbb{Z}</M>) of elements of given order is known, cf. Corollary 2.7.1 (b) in <Cite Key="Kohl05"/>. It can be determined by the function <C>NrConjugacyClassesOfRCWAZOfOrder</C>: <Example> <![CDATA[ gap> List([2,105],NrConjugacyClassesOfRCWAZOfOrder); [ infinity, 218 ] ]]> </Example> <Index Key="IsTame" Subkey="for an rcwa group"><C>IsTame</C></Index> There is a property <C>IsTame</C> which indicates whether an rcwa group is tame or not: <Example> <![CDATA[ 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 ]]> </Example> <Index Key="IsSolvable" Subkey="for an rcwa group"><C>IsSolvable</C></Index> <Index Key="IsPerfect" Subkey="for an rcwa group"><C>IsPerfect</C></Index> <Index Key="DerivedSubgroup" Subkey="of an rcwa group"> <C>DerivedSubgroup</C> </Index> <Index Key="Index" Subkey="for rcwa groups"><C>Index</C></Index> <Index Key="IsomorphismMatrixGroup" Subkey="for an rcwa group"> <C>IsomorphismMatrixGroup</C> </Index> <Index Key="Exponent" Subkey="of an rcwa group"><C>Exponent</C></Index> For tame rcwa groups, there are methods for <C>IsSolvable</C> and <C>IsPerfect</C> 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 <C>IsomorphismMatrixGroup</C>. 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 <C>Exponent</C> available, which works basically for any rcwa group. <Example> <![CDATA[ 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 ] ] ]]> </Example> When investigating a group, a basic task is to find relations among the generators: <ManSection> <Meth Name="EpimorphismFromFpGroup" Arg="G, r" Label="for an rcwa group and a search radius"/> <Returns> An epimorphism from a finitely presented group to the rcwa group <A>G</A>. </Returns> <Description> The argument <A>r</A> is the <Q>search radius</Q>, i.e. the radius of the ball around 1 which is scanned for relations. In general, the larger <A>r</A> is chosen the smaller the kernel of the returned epimorphism is. If the group <A>G</A> has finite presentations, the kernel will in principle get trivial provided that <A>r</A> is chosen large enough. <P/> Both the performance and the returned epimorphism depend on whether the package <Package>FR</Package> <Cite Key="FR"/> is present or not. <Alt Only="LaTeX">\pagebreak[4]</Alt> <Example> <![CDATA[ gap> a := ClassTransposition(2,4,3,4 :Name:="a");; gap> b := ClassTransposition(4,6,8,12:Name:="b");; gap> c := ClassTransposition(3,4,4,6 :Name:="c");; gap> G := Group(a,b,c); <rcwa group over Z with 3 generators> gap> phi := EpimorphismFromFpGroup(G,6); [ a, b, c ] -> [ a, b, c ] gap> RelatorsOfFpGroup(Source(phi)); [ a^2, b^2, c^2, c*b*c*b*c*b, c*b*c*a*c*b*c*a*c*b*c*a, b*a*b*a*b*a*b*a*b*a*b*a ] ]]> </Example> </Description> </ManSection> A related very common task is to factor group elements into generators: <ManSection> <Meth Name ="PreImagesRepresentative" Arg="phi, g" Label="for an epi. from a free group to an rcwa group"/> <Returns> A representative of the set of preimages of <A>g</A> under the epimorphism <A>phi</A> from a free group to an rcwa group. </Returns> <Description> The epimorphism <A>phi</A> must map the generators of the free group to the generators of the rcwa group one-by-one. <P/> This method can be used for factoring elements of rcwa groups into generators. The implementation is based on <C>RepresentativeActionPreImage</C>, see <Ref Oper="RepresentativeAction" Label="G, source, destination, action"/>. <P/> <Index Key="PreImagesRepresentatives" Subkey="for an epi. from a free group to an rcwa group"> <C>PreImagesRepresentatives</C> </Index> Quite frequently, computing several preimages is not harder than computing just one, i.e. often several preimages are found simultaneously. The operation <C>PreImagesRepresentatives</C> takes care of this. It takes the same arguments as <C>PreImagesRepresentative</C> 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 <A>phi</A>. <Example> <![CDATA[ gap> a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; SetName(a,"a"); gap> b := ClassShift(0,1:Name:="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 <bijective rcwa mapping of Z with modulus 8> gap> PreImagesRepresentative(phi,g); # -> a factorization of g b^-4*a^-1*b^-1*a^-1*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)); <bijective rcwa mapping of Z with modulus 8> gap> pre := PreImagesRepresentatives(phi,g); [ b^-1*a^-1*b^-1*a^-1*b^3*a*b*a*b^-2, b^-1*a^-1*b*a^-1*b^3*a*b^-1*a*b^-2 ] gap> rel := CyclicallyReducedWord(pre[1]/pre[2]); # -> a nontriv. relation b^-1*a^-1*b^3*a*b^2*a^-1*b^-3*a*b^-1 gap> rel^phi; IdentityMapping( Integers ) ]]> </Example> </Description> </ManSection> </Section> <!-- #################################################################### --> <Section Label="sec:ActionOnR"> <Heading> The natural action of an rcwa group on the underlying ring </Heading> 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. <P/> <Index Key="Support" Subkey="of an rcwa group"><C>Support</C></Index> <Index Key="MovedPoints" Subkey="of an rcwa group"><C>MovedPoints</C></Index> <Index Key="IsTransitive" Subkey="for an rcwa group, on its underlying ring"> <C>IsTransitive</C> </Index> The support, i.e. the set of moved points, of an rcwa group can be determined by <C>Support</C> or <C>MovedPoints</C> (these are synonyms). Testing for transitivity on the underlying ring is often feasible: <Example> <![CDATA[ gap> G := Group(ClassTransposition(1,2,0,4),ClassShift(0,2));; gap> IsTransitive(G,Integers); true ]]> </Example> There are methods to compute orbits under the action of an rcwa group: <ManSection> <Heading> Orbit (for an rcwa group and either a point or a set) </Heading> <Meth Name="Orbit" Arg="G, point" Label="for an rcwa group and a point"/> <Meth Name="Orbit" Arg="G, set" Label="for an rcwa group and a set"/> <Returns> The orbit of the point <A>point</A> respectively the set <A>set</A> under the natural action of the rcwa group <A>G</A> on its underlying ring. </Returns> <Description> The second argument can either be an element or a subset of the underlying ring of the rcwa group <A>G</A>. 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. <Example> <![CDATA[ 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> 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 ]]> </Example> </Description> </ManSection> &RCWA; permits drawing pictures of orbits of rcwa groups on <M>\mathbb{Z}^2</M>. 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 produced pictures can be processed further with many common graphics programs: <ManSection> <Func Name="DrawOrbitPicture" Arg="G, p0, r, h, w, colored, palette, filename" Label="G, p0, r, h, w, colored, palette, filename"/> <Returns> Nothing. </Returns> <Description> Draws a picture of the orbit(s) of the point(s) <A>p0</A> under the action of the group <A>G</A> on <M>\mathbb{Z}^2</M>. The argument <A>p0</A> is either one point or a list of points. The argument <A>r</A> denotes the radius of the ball around <A>p0</A> to be computed. The size of the created picture is <A>h</A> x <A>w</A> pixels. The argument <A>colored</A> is a boolean which indicates whether a 24-bit True-Color picture or a monochrome picture should be drawn. In the former case, <A>palette</A> must be a list of triples of integers in the range <M>0, \dots, 255</M>, denoting the RGB values of colors to be used. In the latter case, <A>palette</A> is not used, and any value can be passed. The picture is written in bitmap- (bmp-) format to a file named <A>filename</A>. This is done using the utility function <Ref Func="SaveAsBitmapPicture" Label="picture, filename"/>. <Log> <![CDATA[ gap> PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(2), > CyclicGroup(3))));; gap> DrawOrbitPicture(PSL2Z,[0,1],20,512,512,false,fail,"example1.bmp"); gap> DrawOrbitPicture(PSL2Z,Combinations([1..4],2),20,512,512,true, > [[255,0,0],[0,255,0],[0,0,255]],"example2.bmp"); ]]> </Log> </Description> </ManSection> The pictures drawn in the examples are shown on &RCWA;'s webpage. <P/> 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: <ManSection> <Heading> ShortOrbits (for rcwa groups) & ShortCycles (for rcwa permutations) </Heading> <Oper Name="ShortOrbits" Arg="G, S, maxlng" Label="for rcwa group, set of points and bound on length"/> <Oper Name="ShortCycles" Arg="g, S, maxlng" Label="for rcwa permutation, set of points and bound on length"/> <Oper Name="ShortCycles" Arg="g, maxlng" Label="for rcwa permutation and bound on length"/> <Returns> In the first form a list of all finite orbits of the rcwa group <A>G</A> of length at most <A>maxlng</A> which intersect nontrivially with the set <A>S</A>. <P/> In the second form a list of all cycles of the rcwa permutation <A>g</A> of length at most <A>maxlng</A> which intersect nontrivially with the set <A>S</A>. <P/> In the third form a list of all cycles of the rcwa permutation <A>g</A> of length at most <A>maxlng</A> which do not correspond to cycles consisting of residue classes. </Returns> <Description> <Example> <![CDATA[ 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 ] ] ]]> </Example> </Description> </ManSection> 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: <ManSection> <Heading> Ball (for group, element and radius or group, point, radius and action) </Heading> <Meth Name ="Ball" Arg="G, g, r" Label="for group, element and radius"/> <Meth Name ="Ball" Arg="G, p, r, action" Label="for group, point, radius and action"/> <Returns> The ball of radius <A>r</A> around the element <A>g</A> in the group <A>G</A>, respectively the ball of radius <A>r</A> around the point <A>p</A> under the action <A>action</A> of the group <A>G</A>. </Returns> <Description> All balls are understood with respect to <C>GeneratorsOfGroup(<A>G</A>)</C>. As membership tests can be expensive, the former method does not check whether <A>g</A> is indeed an element of <A>G</A>. The methods require that element- / point comparisons are cheap. They are not only applicable to rcwa groups. If the option <A>Spheres</A> is set, the ball is splitted up and returned as a list of spheres. <Example> <![CDATA[ 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) ] ] ]]> </Example> </Description> </ManSection> 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: <ManSection> <Meth Name="RepresentativeAction" Arg="G, source, destination, action" Label="G, source, destination, action"/> <Returns> An element of <A>G</A> which maps <A>source</A> to <A>destination</A> under the action given by <A>action</A>. </Returns> <Description> If an element satisfying this condition does not exist, this method either returns <C>fail</C> or runs into an infinite loop. The problem whether <A>source</A> and <A>destination</A> lie in the same orbit under the action <A>action</A> of <A>G</A> is hard, and in its general form most likely computationally undecidable. <P/> <Index Key="RepresentativeActionPreImage" Subkey="G, source, destination, action, F"> <C>RepresentativeActionPreImage</C> </Index> In cases where rather a word in the generators of <A>G</A> than the actual group element is needed, one should use the operation <C>RepresentativeActionPreImage</C> instead. This operation takes five arguments. The first four are the same as those of <C>RepresentativeAction</C>, and the fifth is a free group whose generators are to be used as letters of the returned word. Note that <C>RepresentativeAction</C> calls <C>RepresentativeActionPreImage</C> and evaluates the returned word. The evaluation of the word can very well take most of the time if <A>G</A> is wild and coefficient explosion occurs. <P/> The algorithm is based on computing balls of increasing radius around <A>source</A> and <A>destination</A> until they intersect nontrivially. <Example> <![CDATA[ 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); Bijective rcwa mapping of Z with modulus 12 n mod 12 | n^f ------------------------------------+------------------------------------ 0 2 3 6 8 11 | n 1 7 10 | n - 3 4 | n + 1 5 9 | n + 4 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); Bijective rcwa mapping of Z with modulus 12 n mod 12 | n^f ------------------------------------+------------------------------------ 0 3 6 | 2n/3 1 | (2n - 8)/3 2 8 11 | (4n + 1)/3 4 7 10 | (4n - 1)/3 5 | (4n - 17)/3 9 | (4n - 15)/3 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*b^-1*a*b*a*b^-2*a*b*a^-1*b gap> elm := w^phi; <bijective rcwa mapping of Z with modulus 324> gap> List([10,-4,9,5],n->n^elm); [ 4, 5, 13, -8 ] ]]> </Example> </Description> </ManSection> 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: <ManSection> <Oper Name ="Projections" Arg="G, m" Label="for an rcwa group and a modulus"/> <Returns> The projections of the rcwa group <A>G</A> to the unions of residue classes (mod <A>m</A>) which it fixes setwise. </Returns> <Description> The corresponding partition of a set of representatives for the residue classes (mod <A>m</A>) can be obtained by the operation <C>OrbitsModulo(<A>G</A>,<A>m</A>)</C>. <Index Key="OrbitsModulo" Subkey="for an rcwa group and a modulus"> <C>OrbitsModulo</C> </Index> <Example> <![CDATA[ gap> G := Group(ClassTransposition(0,2,1,2),ClassShift(3,4));; gap> Projections(G,4); [ [ ClassTransposition(0,2,1,2), ClassShift(3,4) ] -> [ <bijective rcwa mapping of Z with modulus 4>, IdentityMapping( Integers ) ], [ ClassTransposition(0,2,1,2), ClassShift(3,4) ] -> [ <bijective rcwa mapping of Z with modulus 4>, <bijective rcwa mapping of Z with modulus 4> ] ] gap> List(last,phi->Support(Image(phi))); [ 0(4) U 1(4), 2(4) U 3(4) ] ]]> </Example> </Description> </ManSection> 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: <ManSection> <Meth Name="RepresentativeAction" Arg="RCWA(R), P1, P2" Label="for RCWA(R) and 2 partitions of R into residue classes"/> <Returns> An element of RCWA(<M>R</M>) which maps the partition <A>P1</A> to <A>P2</A>. </Returns> <Description> The arguments <A>P1</A> and <A>P2</A> must be partitions of the underlying ring <M>R</M> into the same number of unions of residue classes. The method for <M>R = \mathbb{Z}</M> recognizes the option <C>IsTame</C>, which can be used to demand a tame result. If this option is set and there is no tame rcwa permutation which maps <A>P1</A> to <A>P2</A>, the method runs into an infinite loop. This happens if the condition in Theorem 2.8.9 in <Cite Key="Kohl05"/> is not satisfied. If the option <C>IsTame</C> is not set and the partitions <A>P1</A> and <A>P2</A> both consist entirely of single residue classes, then the returned mapping is affine on any residue class in <A>P1</A>. <Example> <![CDATA[ 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); <bijective rcwa mapping of Z with modulus 3> gap> P1^elm = P2; true gap> IsTame(elm); false gap> elm := RepresentativeAction(RCWA(Integers),P1,P2:IsTame); <tame bijective rcwa mapping 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])]); <bijective rcwa mapping 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) ] ]]> </Example> </Description> </ManSection> </Section> <!-- #################################################################### --> <Section Label="sec:MethodsForTameGroups"> <Heading> Special attributes of tame residue-class-wise affine groups </Heading> 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 <C>IsSolvable</C>, <C>IsPerfect</C> and <C>DerivedSubgroup</C> 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. <ManSection> <Heading> RespectedPartition (of a tame rcwa group or -permutation) </Heading> <Attr Name="RespectedPartition" Arg="G" Label="of a tame rcwa group"/> <Attr Name="RespectedPartition" Arg="g" Label="of a tame rcwa permutation"/> <Returns> A respected partition of the rcwa group <A>G</A> / of the rcwa permutation <A>g</A>. </Returns> <Description> A tame element <M>g</M> <M>\in</M> RCWA(<M>R</M>) permutes a partition of <M>R</M> into finitely many residue classes on all of which it is affine. Given a tame group <M>G</M> <M><</M> RCWA(<M>R</M>), there is a common such partition for all elements of <M>G</M>. We call the mentioned partitions <E>respected partitions</E> of <M>g</M> or <M>G</M>, respectively. <P/> 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 <Cite Key="Kohl05"/>, depending on how one introduces the notion of tameness. <P/> <Index Key="RespectedPartitionShort" Subkey="for a tame rcwa group"> <C>RespectedPartitionShort</C> </Index> <Index Key="RespectedPartitionShort" Subkey="for a tame rcwa permutation"> <C>RespectedPartitionShort</C> </Index> <Index Key="RespectedPartitionLong" Subkey="for a tame rcwa group"> <C>RespectedPartitionLong</C> </Index> <Index Key="RespectedPartitionLong" Subkey="for a tame rcwa permutation"> <C>RespectedPartitionLong</C> </Index> Related attributes are <C>RespectedPartitionShort</C> and <C>RespectedPartitionLong</C>. The first of these denotes a respected partition consisting of residue classes <M>r(m)</M> where <M>m</M> divides the modulus of <A>G</A> or <A>g</A>, respectively. The second denotes a respected partition consisting of residue classes <M>r(m)</M> where the modulus of <A>G</A> (respectively <A>g</A>) divides <M>m</M>. <P/> <Index Key="RespectsPartition" Subkey="for an rcwa group"> <C>RespectsPartition</C> </Index> <Index Key="RespectsPartition" Subkey="for an rcwa permutation"> <C>RespectsPartition</C> </Index> There is an operation <C>RespectsPartition(<A>G</A>,<A>P</A>)</C> / <C>RespectsPartition(<A>g</A>,<A>P</A>)</C>, which tests whether <A>G</A> or <A>g</A> respects a given partition <A>P</A>. The permutation induced by <A>g</A> on <C>P</C> can be computed efficiently by <C>PermutationOpNC(<A>g</A>,P,OnPoints)</C>. <Index Key="PermutationOpNC" Subkey="g, P, OnPoints"> <C>PermutationOpNC</C> </Index> <Example> <![CDATA[ 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); [ 3(6), 5(6), 0(8), 2(8), 4(8), 6(8), 1(12), 7(12) ] ]]> </Example> </Description> </ManSection> <ManSection> <Heading> ActionOnRespectedPartition & KernelOfActionOnRespectedPartition </Heading> <Attr Name="ActionOnRespectedPartition" Arg="G" Label="for a tame rcwa group"/> <Attr Name="KernelOfActionOnRespectedPartition" Arg="G" Label="for a tame rcwa group"/> <Returns> The action of the tame rcwa group <A>G</A> on <C>RespectedPartition(<A>G</A>)</C> or the kernel of this action, respectively. </Returns> <Description> The method for <C>KernelOfActionOnRespectedPartition</C> uses the package <Package>Polycyclic</Package> <Cite Key="Polycyclic"/>. The rank of the largest free abelian subgroup of the kernel of the action of <A>G</A> on its stored respected partition can be computed by <C>RankOfKernelOfActionOnRespectedPartition(<A>G</A>)</C>. <Example> <![CDATA[ gap> G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));; gap> H := ActionOnRespectedPartition(G); Group([ (3,7)(5,8), (3,4,5,6) ]) gap> H = Action(G,P); true gap> Size(H); 48 gap> K := KernelOfActionOnRespectedPartition(G); <rcwa group over Z with 3 generators> gap> RankOfKernelOfActionOnRespectedPartition(G); 3 gap> Index(G,K); 48 gap> List(GeneratorsOfGroup(K),Factorization); [ [ ClassShift(0,4)^2 ], [ ClassShift(2,4)^2 ], [ ClassShift(1,6)^2 ] ] gap> Image(IsomorphismPcpGroup(K)); Pcp-group with orders [ 0, 0, 0 ] ]]> </Example> </Description> </ManSection> Let <M>G</M> be a tame rcwa group over <M>\mathbb{Z}</M>, let <M>\mathcal{P}</M> be a respected partition of <M>G</M> and put <M>m := |\mathcal{P}|</M>. Then there is an rcwa permutation <M>g</M> which maps <M>\mathcal{P}</M> to the partition of <M>\mathbb{Z}</M> into the residue classes (mod <M>m</M>), and the conjugate <M>G^g</M> of <M>G</M> under such a permutation is integral (cf. <Cite Key="Kohl05"/>, Theorem 2.5.14). <P/> <Index Key="IntegralConjugate" Subkey="of a tame rcwa group"> <C>IntegralConjugate</C> </Index> <Index Key="IntegralConjugate" Subkey="of a tame rcwa permutation"> <C>IntegralConjugate</C> </Index> <Index Key="IntegralizingConjugator" Subkey="of a tame rcwa group"> <C>IntegralizingConjugator</C> </Index> <Index Key="IntegralizingConjugator" Subkey="of a tame rcwa permutation"> <C>IntegralizingConjugator</C> </Index> The conjugate <M>G^g</M> can be determined by the operation <C>IntegralConjugate</C>, and the conjugating permutation <M>g</M> can be determined by the operation <C>IntegralizingConjugator</C>. Both operations are applicable to rcwa permutations as well. Note that a tame rcwa group does not determine its integral conjugate uniquely. <Example> <![CDATA[ gap> G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));; gap> G^IntegralizingConjugator(G) = IntegralConjugate(G); true gap> RespectedPartition(G); [ 3(6), 5(6), 0(8), 2(8), 4(8), 6(8), 1(12), 7(12) ] gap> RespectedPartition(G)^IntegralizingConjugator(G); [ 0(8), 1(8), 2(8), 3(8), 4(8), 5(8), 6(8), 7(8) ] gap> last = RespectedPartition(IntegralConjugate(G)); true ]]> </Example> </Section> <!-- #################################################################### --> <Section Label="sec:Random"> <Heading>Generating pseudo-random elements of RCWA(R) and CT(R)</Heading> <Index Key="Random" Subkey="RCWA(R)"><C>Random</C></Index> <Index Key="Random" Subkey="CT(R)"><C>Random</C></Index> There are methods for the operation <C>Random</C> for RCWA(<M>R</M>) and CT(<M>R</M>). These methods are designed to be suitable for generating interesting examples. No particular distribution is guaranteed. <Log> <![CDATA[ gap> elm := Random(RCWA(Integers));; gap> Display(elm); Bijective rcwa mapping of Z with modulus 12 n mod 12 | n^f ------------------------------------+------------------------------------ 0 2 4 6 8 10 | 3n + 2 1 5 9 | -n + 2 3 7 | (n - 7)/2 11 | (-n + 20)/3 ]]> </Log> The elements which are returned by this method are obtained by multiplying class shifts (see <Ref Func="ClassShift" Label="r, m"/>), class reflections (see <Ref Func="ClassReflection" Label="r, m"/>) and class transpositions (see <Ref Func="ClassTransposition" Label="r1, m1, r2, m2"/>). These factors can be retrieved by factoring: <Log> <![CDATA[ gap> Factorization(elm); [ ClassTransposition(0,2,3,4), ClassTransposition(3,4,4,6), ClassShift(0,2)^-1, ClassReflection(3,4), ClassReflection(1,4) ] ]]> </Log> There is an auxiliary function <C>ClassPairs([<A>R</A>,] <A>m</A>)</C>, which is used in this context. <Index Key="ClassPairs" Subkey="m"><C>ClassPairs</C></Index> <Index Key="ClassPairs" Subkey="R, m"><C>ClassPairs</C></Index> In its one-argument form, this function returns a list of 4-tuples <M>(r_1,m_1,r_2,m_2)</M> of integers corresponding to the unordered pairs of disjoint residue classes <M>r_1(m_1)</M> and <M>r_2(m_2)</M> with <M>m_1, m_2 \leq m</M>. In its two-argument form, it does <Q>the equivalent</Q> for the ring <A>R</A>. <Example> <![CDATA[ gap> List(ClassPairs(4),ClassTransposition); [ ClassTransposition(0,2,1,2), ClassTransposition(0,2,1,4), ClassTransposition(0,2,3,4), ClassTransposition(0,3,1,3), ClassTransposition(0,3,2,3), ClassTransposition(0,4,1,4), ClassTransposition(0,4,2,4), ClassTransposition(0,4,3,4), ClassTransposition(1,2,0,4), ClassTransposition(1,2,2,4), ClassTransposition(1,3,2,3), ClassTransposition(1,4,2,4), ClassTransposition(1,4,3,4), ClassTransposition(2,4,3,4) ] gap> List(last,TransposedClasses); [ [ 0(2), 1(2) ], [ 0(2), 1(4) ], [ 0(2), 3(4) ], [ 0(3), 1(3) ], [ 0(3), 2(3) ], [ 0(4), 1(4) ], [ 0(4), 2(4) ], [ 0(4), 3(4) ], [ 1(2), 0(4) ], [ 1(2), 2(4) ], [ 1(3), 2(3) ], [ 1(4), 2(4) ], [ 1(4), 3(4) ], [ 2(4), 3(4) ] ] ]]> </Example> </Section> <!-- #################################################################### --> <Section Label="sec:CategoriesOfRcwaGroups"> <Heading>The categories of residue-class-wise affine groups</Heading> <ManSection> <Filt Name="IsRcwaGroup" Arg="G"/> <Filt Name="IsRcwaGroupOverZ" Arg="G"/> <Filt Name="IsRcwaGroupOverZ_pi" Arg="G"/> <Filt Name="IsRcwaGroupOverGFqx" Arg="G"/> <Returns> <C>true</C> if <A>G</A> 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 <C>false</C> otherwise. </Returns> <Description> <Index Key="IsRcwaGroupOverZOrZ_pi"> <C>IsRcwaGroupOverZOrZ&uscore;pi</C> </Index> 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 <C>IsRcwaGroupOverZOrZ&uscore;pi</C> which is the union of <C>IsRcwaGroupOverZ</C> and <C>IsRcwaGroupOverZ&uscore;pi</C>. <P/> <Index Key="IsNaturalRCWA"><C>IsNaturalRCWA</C></Index> <Index Key="IsNaturalCT"><C>IsNaturalCT</C></Index> To allow distinguishing the groups RCWA(<M>R</M>) and CT(<M>R</M>) from others, they have the characteristic property <C>IsNaturalRCWA</C> or <C>IsNaturalCT</C>, respectively. </Description> </ManSection> </Section> <!-- #################################################################### --> </Chapter> <!-- #################################################################### -->