Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | 6 | Bib | Ind

### 3. Residue Class-Wise Affine Groups

This chapter describes the functionality provided by this package for computing with residue class-wise affine groups.

#### 3.1 Constructing residue class-wise affine groups

Residue class-wise affine groups can be constructed using either `Group`, `GroupByGenerators` or `GroupWithGenerators`, as usual (see the reference manual). Note that currently except of the groups RCWA(R) only finitely generated rcwa groups are supported.

    gap> g := RcwaMapping([[1,0,1],[1,1,1],[3,6,1],
    >                      [1,0,3],[1,1,1],[3,6,1],
    >                      [1,0,1],[1,1,1],[3,-21,1]]);;
    gap> h := RcwaMapping([[1,0,1],[1,1,1],[3,6,1],
    >                      [1,0,3],[1,1,1],[3,-21,1],
    >                      [1,0,1],[1,1,1],[3,6,1]]);;
    gap> List([g,h],Order);
    [ 9, 9 ]
    gap> G := Group(g,h);
    <rcwa group over Z with 2 generators>
    gap> Size(G);
    infinity

For rcwa groups, there are methods available for the operations `Display` and `Print`.

All rcwa groups over the ring R are subgroups of RCWA(R). The group RCWA(R) is not finitely generated, thus cannot be constructed as described above. It is handled as a special case:

##### 3.1-1 RCWA

`> RCWA`( R ) | ( function )

Returns: The group RCWA(R) of all bijective rcwa mappings of the ring R.

    gap> RCWA_Z := RCWA(Integers);
    RCWA(Z)
    gap> Size(RCWA_Z);
    infinity
    gap> IsFinitelyGeneratedGroup(RCWA_Z);
    false
    gap> One(RCWA_Z);
    IdentityMapping( Integers )
    gap> IsSolvable(RCWA_Z);
    false
    gap> IsPerfect(RCWA_Z);
    false
    gap> Centre(RCWA_Z);
    Trivial rcwa group over Z
    gap> IsSubgroup(RCWA_Z, Group(RcwaMapping((1,2,3),[1..4]),
    >                             RcwaMapping(2,[[0,1],[1,0],[2,3],[3,2]])));
    true

##### 3.1-2 Random

`> Random`( RCWA_Z ) | ( method )

Returns: A pseudo-random element of the group RCWA(Z).

This method is designed to be suitable for generating interesting examples. No particular distribution is guaranteed -- in fact, the author has no idea what a "reasonable" random distribution on RCWA(Z) should be.

    gap> elm := Random(RCWA_Z);
    <bijective rcwa mapping of Z with modulus 60>
    gap> Display(elm);

    Bijective rcwa mapping of Z with modulus 60

                   n mod 60                |                 n^f
    ---------------------------------------+--------------------------------------
       0  4  6  8 10 14 16 18 20 24 26 28  |
      30 34 36 38 40 44 46 48 50 54 56 58  | -3n - 5
       1                                   | (n - 1)/5
       2 22 42                             | (3n + 24)/5
       3  9 15 21 27 33 39 45 51 57        | (-5n + 12)/3
       5 11 17 29 35 41 47 59              | -n + 2
       7 13 19 25 37 43 49 55              | -n
      12 32 52                             | (3n + 4)/5
      23                                   | (n - 3)/5
      31                                   | (n + 19)/5
      53                                   | (n + 17)/5

The elements returned by this method are obtained by multiplying class shifts (see `ClassShift` (2.2-2)), class reflections (see `ClassReflection` (2.2-3)) and class transpositions (see `ClassTransposition` (2.2-4)). These factors are stored as an attribute value:

    gap> Perform(FactorizationIntoGenerators(elm),Display);

    Rcwa mapping of Z with modulus 6

                    n mod 6                |                 n^f
    ---------------------------------------+--------------------------------------
      0 2 4                                | 3n + 5
      1 3                                  | n
      5                                    | (n - 5)/3

    Rcwa mapping of Z with modulus 6

                    n mod 6                |                 n^f
    ---------------------------------------+--------------------------------------
      0 2 4                                | 3n + 3
      1 5                                  | n
      3                                    | (n - 3)/3

    Rcwa mapping of Z with modulus 10

                   n mod 10                |                 n^f
    ---------------------------------------+--------------------------------------
       0  2  4  6  8                       | 5n + 1
       1                                   | (n - 1)/5
       3  5  7  9                          | n

    Rcwa mapping of Z with modulus 4

                    n mod 4                |                 n^f
    ---------------------------------------+--------------------------------------
      0 1 3                                | n
      2                                    | n + 4

    Rcwa mapping of Z: n -> -n

    Rcwa mapping of Z with modulus 2

                    n mod 2                |                 n^f
    ---------------------------------------+--------------------------------------
      0                                    | -n
      1                                    | n

Another possible way to get an rcwa group is by taking the image of an rcwa representation, or by "translating" a permutation group:

##### 3.1-3 IsomorphismRcwaGroup

`> IsomorphismRcwaGroup`( G ) | ( attribute )

`> RcwaGroupByPermGroup`( G ) | ( function )

Returns: A monomorphism from the finite group G to RCWA(Z), resp. an rcwa group over Z, which is isomorphic to the (finite) permutation group G, and acts on the range `[1..LargestMovedPoint(`G`)]` as G does.

    gap> G := GL(2,5);;
    gap> IsomorphismRcwaGroup(G);
    CompositionMapping(
    [ (2,3,5,8)(4,7,12,18)(6,10,17,22)(9,15,21,24)(13,14,19,23),
      (1,2,4)(3,6,11)(5,9,16)(7,13,12)(8,14,20)(10,18,17)(15,22,21)(19,24,23)
     ] -> [ <rcwa mapping of Z with modulus 24>, <rcwa mapping of Z with modulus
        24> ], <action isomorphism> )
    gap> H := RcwaGroupByPermGroup(Group((1,2),(3,4),(5,6),(7,8),
    >                                    (1,3)(2,4),(1,3,5,7)(2,4,6,8)));
    <rcwa group over Z with 6 generators>
    gap> Size(H);; List(DerivedSeries(H),Size);
    [ 384, 96, 32, 2, 1 ]

#### 3.2 Attributes and properties of rcwa groups

##### 3.2-1 Modulus

`> Modulus`( G ) | ( method )

`> Mod`( G ) | ( method )

Returns: The modulus of the rcwa group G.

The Modulus of an rcwa group is the lcm of the moduli of its elements in case such an lcm exists and 0 otherwise.

See also `IsTame` (3.2-2).

    gap> Modulus(Group(g,h));
    27
    gap> g1 := RcwaMapping((1,2),[1..2]);
    <rcwa mapping of Z with modulus 2>
    gap> g2 := RcwaMapping((1,2,3),[1..3]);
    <rcwa mapping of Z with modulus 3>
    gap> g3 := RcwaMapping((1,2,3,4,5),[1..5]);
    <rcwa mapping of Z with modulus 5>

    gap> G := Group(g1,g2,g3);
    <rcwa group over Z with 3 generators>
    gap> Modulus(G);
    30
    gap> a := RcwaMapping([[3,0,2],[3,1,4],[3,0,2],[3,-1,4]]);; SetName(a,"a");
    gap> b := ClassShift(1,4)*a;; SetName(b,"b");
    gap> c := ClassShift(3,4)*a;; SetName(c,"c");
    gap> Modulus(Group(a,b));
    0

##### 3.2-2 IsTame

`> IsTame`( G ) | ( property )

Returns: `true` if the rcwa group G is tame and `false` otherwise.

An rcwa group is called tame if its modulus is not equal to 0.

    gap> IsTame(G);
    true
    gap> IsTame(Group(a,b));
    false
    gap> IsTame(Group(Comm(a,b),Comm(a,c)));
    true

##### 3.2-3 PrimeSet

`> PrimeSet`( G ) | ( operation )

Returns: The prime set of the rcwa group G.

The prime set of an rcwa group is the union of the prime sets of its elements. See also `PrimeSet` (2.6-3) for rcwa mappings.

    gap> [ PrimeSet(G), PrimeSet(H) ];
    [ [ 2, 3, 5 ], [ 2 ] ]

An rcwa group is called integral resp. class-wise order-preserving if all of its elements are so. There are corresponding methods available for `IsIntegral` and `IsClassWiseOrderPreserving`.

#### 3.3 Membership testing, order computation, permutation- / matrix representations

##### 3.3-1 \in

`> \in`( g, G ) | ( method )

Returns: `true` if the rcwa mapping g is an element of the rcwa group G and `false` if not.

Tries to figure out whether g is an element of G or not. This will be successful if G is tame and class-wise order-preserving. For wild groups only a number of easy cases are covered. On `InfoLevel(InfoRCWA) = 3` the method will give information about reasons why g is an element of G or not.

    gap> u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;
    gap> u in H;
    false

##### 3.3-2 Size

`> Size`( G ) | ( method )

Returns: The order of the rcwa group G.

    gap> Size(G);
    265252859812191058636308480000000

##### 3.3-3 IsomorphismPermGroup

`> IsomorphismPermGroup`( G ) | ( method )

Returns: An isomorphism from the finite rcwa group G to some permutation group.

    gap> H := Group(g1,g2);
    <rcwa group over Z with 2 generators>
    gap> phi := IsomorphismPermGroup(H);
    [ <bijective rcwa mapping of Z with modulus 2, of order 2>,
      <bijective rcwa mapping of Z with modulus 3, of order 3> ] ->
    [ (1,2)(3,4)(5,6), (1,2,3)(4,5,6) ]

##### 3.3-4 IsomorphismMatrixGroup

`> IsomorphismMatrixGroup`( G ) | ( attribute )

Returns: An isomorphism from the rcwa group G to some matrix group.

Currently, there is only a method installed which works for tame rcwa groups.

    gap> g := RcwaMapping([[2,2,1],[1, 4,1],[1,0,2],[2,2,1],[1,-4,1],[1,-2,1]]);;
    gap> h := RcwaMapping([[2,2,1],[1,-2,1],[1,0,2],[2,2,1],[1,-1,1],[1, 1,1]]);;
    gap> SetName(g,"g"); SetName(h,"h");
    gap> G := Group(g,h);
    <rcwa group over Z with 2 generators>
    gap> phi := IsomorphismMatrixGroup(G);;
    gap> FieldOfMatrixGroup(Image(phi));
    Rationals
    gap> DegreeOfMatrixGroup(Image(phi));
    28
    gap> List(GeneratorsOfGroup(Image(phi)),Order);
    [ 7, 12 ]
    gap> Display(GeneratorsOfGroup(Image(phi))[1]*One(GF(5)));
     . . . . . . 1 1 . . . . . . . . . . . . . . . . . . . .
     . . . . . . . 1 . . . . . . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . . . . . . . 3 . . . . . . .
     . . . . . . . . . . . . . . . . . . . . . 1 . . . . . .
     . . . . . . . . 1 3 . . . . . . . . . . . . . . . . . .
     . . . . . . . . . 1 . . . . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . . . . . . . . . 3 . . . . .
     . . . . . . . . . . . . . . . . . . . . . . . 1 . . . .
     . . 1 4 . . . . . . . . . . . . . . . . . . . . . . . .
     . . . 1 . . . . . . . . . . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . . . 1 1 . . . . . . . . . .
     . . . . . . . . . . . . . . . . . 1 . . . . . . . . . .
     . . . . . . . . . . . . . . . . . . . . . . . . 3 . . .
     . . . . . . . . . . . . . . . . . . . . . . . . . 1 . .
     . . . . . . . . . . . . . . . . . . 1 3 . . . . . . . .
     . . . . . . . . . . . . . . . . . . . 1 . . . . . . . .
     . . . . . . . . . . . . . . . . . . . . . . . . . . 3 .
     . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
     . . . . . . . . . . . . 1 4 . . . . . . . . . . . . . .
     . . . . . . . . . . . . . 1 . . . . . . . . . . . . . .
     2 2 . . . . . . . . . . . . . . . . . . . . . . . . . .
     . 1 . . . . . . . . . . . . . . . . . . . . . . . . . .
     . . . . 2 2 . . . . . . . . . . . . . . . . . . . . . .
     . . . . . 1 . . . . . . . . . . . . . . . . . . . . . .
     . . . . . . . . . . 2 2 . . . . . . . . . . . . . . . .
     . . . . . . . . . . . 1 . . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . 2 2 . . . . . . . . . . . .
     . . . . . . . . . . . . . . . 1 . . . . . . . . . . . .

#### 3.4 Factoring elements into generators

##### 3.4-1 PreImagesRepresentative

`> PreImagesRepresentative`( phi, g ) | ( method )

Returns: A representative of the set of preimages of g under the homomorphism phi from a free group to an rcwa group over Z.

This method can be used for factoring elements of rcwa groups over Z into generators, and for finding non-trivial relations among the generators if the respective group is not free and the method returns a factorization which does not happen to be equal to one which is known a priori. The homomorphism phi must map the generators of the free group to the generators of the rcwa group one-by-one. This method is also suitable for wild groups. The implementation is based on `RepresentativeActionPreImage` (3.5-3).

    gap> G := Group(g,h);
    <rcwa group over Z with 2 generators>
    gap> phi := EpimorphismFromFreeGroup(G);
    [ g, h ] -> [ g, h ]
    gap> PreImagesRepresentative(phi,h*g^3*h^2*g^-1*h*g*h^-3);
    h*g^3*h^2*g^-1*h*g*h^-3
    gap> nu := RcwaMapping([[1,1,1]]);
    Rcwa mapping of Z: n -> n + 1
    gap> SetName(nu,"nu");
    gap> G := Group(a,nu);
    <rcwa group over Z with 2 generators>
    gap> IsTame(G);
    false
    gap> phi := EpimorphismFromFreeGroup(G);
    [ a, nu ] -> [ a, nu ]
    gap> F := Source(phi);
    <free group on the generators [ a, nu ]>
    gap> w := Comm(F.1,Comm(F.1,F.2^2));
    a^-1*nu^-2*a^-1*nu^2*a*nu^-2*a*nu^2
    gap> f := w^phi;
    <bijective rcwa mapping of Z with modulus 18>
    gap> IsTame(f);
    false
    gap> pre := PreImagesRepresentative(phi,f);
    a^-2*nu^-2*a^2*nu^2
    gap> one := w*pre^-1; # pre <> w --> We have a non-trivial relation!
    a^-1*nu^-2*a^-1*nu^2*a*nu^-2*a^-1*nu^2*a^2
    gap> one^phi;
    IdentityMapping( Integers )

##### 3.4-2 PreImagesRepresentatives

`> PreImagesRepresentatives`( phi, g ) | ( operation )

Returns: A list of representatives of the set of preimages of g under the homomorphism phi from a free group to an rcwa group over Z.

Quite frequently, computing several preimages is not harder than computing just one, i.e. often several preimages are found simultaneously. This operation is called by `PreImagesRepresentative` (3.4-1), which simply chooses the shortest representative -- for a slightly more concise description see there.

    gap> G := Group(g,h);
    <rcwa group over Z with 2 generators>
    gap> phi := EpimorphismFromFreeGroup(G);
    [ g, h ] -> [ g, h ]
    gap> f := g^3*h*g^-4*h^5*g;
    <bijective rcwa mapping of Z with modulus 12>
    gap> RCWAInfo(2);
    gap> pre := PreImagesRepresentatives(phi,f);
    #I  Orbit lengths after extension step 1: [ 4, 5 ]
    #I  |Candidates| = 1
    #I  Orbit lengths after extension step 1: [ 5, 5 ]
    #I  Orbit lengths after extension step 2: [ 17, 15 ]
    #I  Orbit lengths after extension step 3: [ 52, 39 ]
    #I  |Candidates| = 1
    #I  Orbit lengths after extension step 1: [ 5, 5 ]
    #I  Orbit lengths after extension step 2: [ 17, 15 ]
    #I  Orbit lengths after extension step 3: [ 53, 43 ]
    #I  Orbit lengths after extension step 4: [ 158, 119 ]
    #I  |Candidates| = 1
    #I  Orbit lengths after extension step 1: [ 5, 5 ]
    #I  Orbit lengths after extension step 2: [ 17, 17 ]
    #I  Orbit lengths after extension step 3: [ 53, 53 ]
    #I  Orbit lengths after extension step 4: [ 159, 158 ]
    #I  Orbit lengths after extension step 5: [ 472, 462 ]
    #I  Orbit lengths after extension step 6: [ 1356, 1309 ]
    #I  Orbit lengths after extension step 7: [ 3822, 3643 ]
    #I  |Candidates| = 11
    [ g^3*h*g^3*h^5*g, g^-3*h^-4*g^-3*h^-1*g*h*g, g^3*h*g^-4*h^5*g ]
    gap> RCWAInfo(0);
    gap> List(pre,Length);
    [ 13, 14, 14 ]
    gap> Set(List(pre,w->w^phi)) = [f];
    true
    gap> w := pre[1]*pre[2]^-1;
    g^3*h*g^3*h^4*g^-1*h*g^3*h^4*g^3
    gap> Length(w);
    23
    gap> w^phi; # A relation of length 23.
    IdentityMapping( Integers )

#### 3.5 The action of an rcwa group on the underlying ring R

The support (set of moved points) of an rcwa group can be determined by `MovedPoints`.

In some cases -- in particular in the case that the group in question is tame -- testing for transitivity on the underlying ring is feasible. Furthermore it is often 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.

##### 3.5-1 IsTransitive

`> IsTransitive`( G, Integers ) | ( method )

Returns: `true` if the rcwa group G acts transitively on Z and `false` otherwise.

Depending on the particular group this might fail or run into an infinite loop, but for tame groups things should work.

    gap> G := Group(g,h);;
    gap> RCWAInfo(3);
    gap> IsTransitive(G,Integers);
    #I  IsTransitive: testing for finiteness and searching short orbits ...
    #I  IsTame: balancedness criterion.
    #I  IsTame:`dead end' criterion.
    #I  IsTame: loop criterion.
    #I  IsTame:`finite order or integral power' criterion.

      [ ... ]

    #I  Order: the 4th power of the argument is RcwaMapping(
    [ [ 1, 12, 1 ], [ 1, 12, 1 ], [ 1, -6, 2 ], [ 2, -10, 1 ], [ 1, -7, 1 ],
      [ 2, -8, 1 ], [ 1, 12, 1 ], [ 1, 12, 1 ], [ 1, -10, 2 ], [ 2, -10, 1 ],
      [ 1, -7, 1 ], [ 2, -8, 1 ] ] );
    There is a `class shift' on the residue class 0(12).
    #I  Trying probabilistic random walk, initial m = 12
    #I  checking modulus ...
    #I  Size: use action on respected partition.
    #I  KernelOfActionOnRespectedPartition: gen. #1, lng = 1
    #I  KernelOfActionOnRespectedPartition: gen. #2, lng = 2

                           [ ... ]

    #I  KernelOfActionOnRespectedPartition: gen. #14, lng = 10
    #I  Searching for class shifts ...
    #I  ... in generators
    #I  ... in commutators of the generators
    #I  The cyclic group generated by RcwaMapping(
    [ [ 1, -9, 1 ], [ 1, 0, 1 ], [ 1, 6, 1 ], [ 1, -3, 1 ], [ 1, 0, 1 ],
      [ 1, 6, 1 ] ] ) acts transitively on the residue class 2(6).
    #I  OrbitUnion: initial set = ResidueClassUnion( Integers, 6, [ 2 ] )
    #I  Image = Integers
    true
    gap> RCWAInfo(0);

##### 3.5-2 RepresentativeAction

`> RepresentativeAction`( G, src, dest, act ) | ( method )

Returns: An element of G which maps src to dest under the action given by act.

If an element satisfying this condition does not exist, this method either returns `fail` or runs into an infinite loop. The problem of whether src and dest lie in the same orbit under the action of G in general seems to be hard. The given method is based on `RepresentativeActionPreImage` (3.5-3), and it basically just computes an image under an homomorphism. As this involves multiplications of rcwa mappings, this can be quite expensive if the group G is wild, the preimage is a rather long word and coefficient explosion happens to occur.

    gap> G := Group(a,b);
    <rcwa group over Z with 2 generators>
    gap> elm := RepresentativeAction(G,[7,4,9],[4,5,13],OnTuples);
    <bijective rcwa mapping of Z with modulus 12>
    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,[5,4,9],[13,5,4],OnTuples);
    <bijective rcwa mapping of Z with modulus 9>
    gap> Display(elm);

    Bijective rcwa mapping of Z with modulus 9

                    n mod 9                |                 n^f
    ---------------------------------------+--------------------------------------
      0                                    | 4n/9
      1                                    | (8n - 26)/9
      2                                    | (8n + 2)/9
      3                                    | (8n + 3)/9
      4                                    | (16n - 19)/9
      5                                    | (16n + 37)/9
      6                                    | (8n + 33)/9
      7                                    | (16n - 49)/9
      8                                    | (16n + 7)/9

    gap> List([5,4,9],n->n^elm);
    [ 13, 5, 4 ]
    gap> RepresentativeAction(G,[7,4,9],[4,5,8],OnTuples);
    <bijective rcwa mapping of Z with modulus 256>

##### 3.5-3 RepresentativeActionPreImage

`> RepresentativeActionPreImage`( G, src, dest, act, F ) | ( operation )

Returns: The result of `RepresentativeAction( G, src, dest, act )` as a word in the generators.

The argument F is a free group to be used to express the resulting word. Note that the dependency is just the other way round than suggested above (`RepresentativeAction` calls `RepresentativeActionPreImage`) and that the evaluation of the word sometimes takes much more time than its determination (the latter however depends very much on the particular case and is hard to predict). This causes `RepresentativeActionPreImage` sometimes to be much faster than `RepresentativeAction`. The employed algorithm is not inefficient, as the last two of the examples below suggest -- it is based on separate progressive computations of the orbits of src and dest until they intersect non-trivially. It avoids multiplying rcwa mappings. Of course the other warnings given in the description of `RepresentativeAction` (3.5-2) apply to this operation, too.

    gap> F := FreeGroup("a","b");;
    gap> w := RepresentativeActionPreImage(G,[7,4,9],[4,5,13],OnPoints,F);
    b^-1*a*b*a^-1
    gap> w := RepresentativeActionPreImage(G,[5,4,9],[13,5,4],OnTuples,F);
    b^-1*a^-1*b*a^-1
    gap> w := RepresentativeActionPreImage(G,[7,4,9],[4,5,8],OnPoints,F);
    b^2*a^2
    gap> phi := GroupHomomorphismByImages(F,G,[F.1,F.2],[a,b]);
    [ a, b ] -> [ a, b ]
    gap> w^phi;
    <bijective rcwa mapping of Z with modulus 256>
    gap> w^phi = RepresentativeAction(G,[7,4,9],[4,5,8],OnPoints);
    true
    gap> List([7,4,9],n->n^(w^phi));
    [ 4, 5, 8 ]
    gap> w := RepresentativeActionPreImage(G,[37,4,9],[4,51,8],OnPoints,F);
    a^-1*b^-1*a*b^4*a
    gap> w^phi;
    <bijective rcwa mapping of Z with modulus 4608>
    gap> w := RepresentativeActionPreImage(G,[37,4,9],[4,51,8],OnTuples,F);
    b*a^6*b*a^-3*b^-3*a^-1*b*a^2
    gap> w := RepresentativeActionPreImage(G,[17,14,9],[4,51,8],OnPoints,F);
    a^-1*b^-1*a^3*b^2*a*b*a*b^-1*a^2

##### 3.5-4 RepresentativeAction

`> RepresentativeAction`( RCWA_Z, P1, P2 ) | ( method )

Returns: An element of RCWA(Z) 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 disjoint unions of residue classes. The method recognizes the option `IsTame` -- if this option is set, the returned mapping is tame provided that there is a tame mapping satisfying the required condition. 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> rc := function(r,m) return ResidueClass(DefaultRing(m),m,r); end;;
    gap> P1 := [rc(0,3),rc(1,3),rc(2,9),rc(5,9),rc(8,9)];
    [ 0(3), 1(3), 2(9), 5(9), 8(9) ]
    gap> P2 := [rc(0,2),rc(1,8),rc(5,16),rc(3,4),rc(13,16)];
    [ 0(2), 1(8), 5(16), 3(4), 13(16) ]
    gap> elm := RepresentativeAction(RCWA(Integers),P1,P2);
    <rcwa mapping of Z with modulus 9>
    gap> Display(elm);

    Rcwa mapping of Z with modulus 9

                    n mod 9                |                 n^f
    ---------------------------------------+--------------------------------------
      0 3 6                                | 2n/3
      1 4 7                                | (8n - 5)/3
      2                                    | (16n + 13)/9
      5                                    | (4n + 7)/9
      8                                    | (16n - 11)/9

    gap> P1^elm = P2;
    true
    gap> elm := RepresentativeAction(RCWA(Integers),P1,P2:IsTame);
    <tame rcwa mapping of Z with modulus 1152>
    gap> P := RespectedPartition(elm);;
    gap> Length(P);
    313
    gap> elm := RepresentativeAction(RCWA(Integers),
    >                                [rc(1,3),Union(rc(0,3),rc(2,3))],
    >                                [Union(rc(2,5),rc(4,5)),
    >                                 Union(rc(0,5),rc(1,5),rc(3,5))]);
    <rcwa mapping of Z with modulus 6>
    gap> [rc(1,3),Union(rc(0,3),rc(2,3))]^elm;
    [ 2(5) U 4(5), 0(5) U 1(5) U 3(5) ]

##### 3.5-5 ShortOrbits

`> ShortOrbits`( G, S, maxlng ) | ( operation )

Returns: A list of all finite orbits of the rcwa group G of maximal length maxlng, which intersect non-trivially with the set S.

    gap> A5 := IntegralRcwaGroupByPermGroup(AlternatingGroup(5));;
    gap> ShortOrbits(A5,[-10..10],100);
    [ [ -14, -13, -12, -11, -10 ], [ -9, -8, -7, -6, -5 ], [ -4, -3, -2, -1, 0 ],
      [ 1, 2, 3, 4, 5 ], [ 6, 7, 8, 9, 10 ] ]
    gap> Action(A5,last[2]);
    Group([ (1,2,3,4,5), (3,4,5) ])

    gap> G := Group(Comm(a,b),Comm(a,c));;
    gap> orb := ShortOrbits(G,[-15..15],100);
    [ [ -15, -12, -7, -6, -5, -4, -3, -2, -1, 1 ],
      [ -33, -30, -24, -21, -16, -14, -13, -11, -10, -8 ], [ -9 ], [ 0 ],
      [ 2, 3, 4, 5, 6, 7, 8, 10, 12, 15 ], [ 9 ],
      [ 11, 13, 14, 16, 17, 19, 21, 24, 30, 33 ] ]
    gap> Action(G,orb[1]);
    Group([ (2,5,8,10,7,6), (1,3,6,9,4,5) ])
    gap> ShortOrbits(Group(u),[-30..30],100);
    [ [ -13, -8, -7, -5, -4, -3, -2 ], [ -10, -6 ], [ -1 ], [ 0 ], [ 1, 2 ],
      [ 3, 5 ], [ 24, 36, 39, 40, 44, 48, 60, 65, 67, 71, 80, 86, 93, 100, 112,
          128, 138, 155, 167, 187, 230, 248, 312, 446, 520, 803, 867, 1445 ] ]

##### 3.5-6 OrbitsModulo

`> OrbitsModulo`( G, m ) | ( method )

Returns: A partition of `[0..m-1]`, such that i and j lie in the same subset if and only if there is an element g of G which moves an element from the residue class i(m) to the residue class j(m).

The argument G must be an rcwa group over Z. See also `OrbitsModulo` (2.8-2) for rcwa mappings.

    gap> OrbitsModulo(G,36);
    [ [ 0 ], [ 1, 11, 13, 14, 16, 17, 19, 21, 24, 29, 30, 31, 32, 33, 34, 35 ],
      [ 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20, 22, 23, 25, 26, 28 ], [ 9 ], [ 18 ],
      [ 27 ] ]

#### 3.6 Conjugacy in RCWA(R)

##### 3.6-1 IsConjugate

`> IsConjugate`( RCWA_Z, f, g ) | ( method )

Returns: `true` if the bijective rcwa mappings f and g are conjugate in RCWA(Z), and `false` otherwise.

This may fail or run into an infinite loop. In particular the support for wild rcwa mappings is currently very poor, since the author does not know a way to solve the conjugacy problem for these. Some easy cases are handled anyway.

    gap> IsConjugate(RCWA(Integers),g,h);
    false
    gap> IsConjugate(RCWA(Integers),g,g^a);
    true
    gap> IsConjugate(RCWA(Integers),a,b);
    false

##### 3.6-2 RepresentativeAction

`> RepresentativeAction`( RCWA_Z, f, g ) | ( method )

Returns: An rcwa mapping `x` such that `f^x = g`, if such an `x` exists and `fail` otherwise.

This method currently works only for tame rcwa mappings of Z, since the author does not know a way to solve the conjugacy problem for wild rcwa mappings.

    gap> elm := RepresentativeAction(RCWA(Integers),h,h^g);
    <bijective rcwa mapping of Z with modulus 24>
    gap> h^elm = h^g; # check ...
    true
    gap> Order(elm);
    10
    gap> cent := g*elm^-1;
    <bijective rcwa mapping of Z with modulus 24>
    gap> Comm(cent,h); # cent must lie in the centralizer of h in RCWA(Z)
    IdentityMapping( Integers )
    gap> Order(cent);
    12
    gap> Display(cent);

    Bijective rcwa mapping of Z with modulus 24, of order 12

                   n mod 24                |                 n^f
    ---------------------------------------+--------------------------------------
       0  4 10 12 16 22                    | n - 1
       1 13                                | 2n
       2                                   | (n - 2)/2
       3  9 15 21                          | 2n + 2
       5  6  7 14 17 18 19                 | n
       8 20                                | n/2
      11 23                                | n + 2

##### 3.6-3 ShortCycles

`> ShortCycles`( f, maxlng ) | ( operation )

Returns: All "single" finite cycles of the rcwa mapping f of length at most maxlng.

In this context, "single" finite cycles are finite cycles not belonging to an infinite series, i.e. there is no constant m such that adding any multiple of m to the elements of the cycle always yields a new cycle.

Since GAP-permutations cannot move negative integers, rationals or even polynomials, the cycles are returned as lists. For example, the list `[-3,1,2,-2]` denotes the cycle `(-3,1,2,-2)`. Mappings having different sets of finite cycle lengths are obviously not conjugate in RCWA(R).

    gap> ShortCycles(a,5);
    [ [ 0 ], [ 1 ], [ -1 ], [ 2, 3 ], [ -3, -2 ], [ 4, 6, 9, 7, 5 ],
      [ -9, -7, -5, -4, -6 ] ]
    gap> ShortCycles(u,2);
    [ [ 0 ], [ -1 ], [ 1, 2 ], [ 3, 5 ], [ -10, -6 ] ]
    gap> ShortCycles(Comm(a,b),10);
    [  ]
    gap> ShortCycles(a*b,2);
    [ [ 0 ], [ 2 ], [ 3 ], [ -26 ], [ 7 ], [ -3 ], [ -1 ] ]
    gap> v := RcwaMapping([[-1,2,1],[1,-1,1],[1,-1,1]]);;
    gap> w := RcwaMapping([[-1,3,1],[1,-1,1],[1,-1,1],[1,-1,1]]);;
    gap> List( [ v, w ], Order );
    [ 6, 8 ]
    gap> [ ShortCycles(v,10), ShortCycles(w,10) ];
    [ [ [ 0, 2, 1 ] ], [ [ 0, 3, 2, 1 ] ] ]

##### 3.6-4 NrConjugacyClassesOfRCWAZOfOrder

`> NrConjugacyClassesOfRCWAZOfOrder`( ord ) | ( function )

Returns: The number of conjugacy classes of RCWA(Z) of elements of order ord.

    gap> NrConjugacyClassesOfRCWAZOfOrder(2);
    infinity
    gap> NrConjugacyClassesOfRCWAZOfOrder(105);
    218

#### 3.7 Restriction and induction

##### 3.7-1 Restriction

`> Restriction`( g, f ) | ( operation )

Returns: The restriction of the rcwa mapping g by the injective rcwa mapping f.

By definition, the restriction g_f of the rcwa mapping g by the injective rcwa mapping f is the uniquely determined rcwa mapping which satisfies f * g_f = g * f and 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 by f. See also `Restriction` (3.7-2) for rcwa groups.

    gap> Comm(Restriction(a,RcwaMapping([[2,0,1]])),
    >         Restriction(u,RcwaMapping([[2,1,1]])));
    IdentityMapping( Integers )

##### 3.7-2 Restriction

`> Restriction`( G, f ) | ( operation )

Returns: The restriction of the rcwa group G by the injective rcwa mapping f.

By definition, the restriction of the rcwa group G by the injective rcwa mapping f consists of the restrictions of its elements by f. The restriction of G by f acts on the image of f and fixes its complement pointwise.

    gap> G := Restriction(Group(a,b),RcwaMapping([[5,3,1]]));
    <rcwa group over Z with 2 generators>
    gap> MovedPoints(G);
    3(5) \ [ -2, 3 ]

##### 3.7-3 Induction

`> Induction`( g, f ) | ( operation )

`> Induction`( G, f ) | ( operation )

Returns: The induction of the rcwa mapping g resp. the rcwa group G by the injective rcwa mapping f.

By definition, induction is the right inverse of restriction. This means that we always have `Induction(Restriction(g,f),f) = g`, resp. `Induction(Restriction(G,f),f) = G`. The mapping g resp. the group G must not move points outside the image of f.

    gap> Induction(G,RcwaMapping([[5,3,1]])) = Group(a,b);
    true

Restriction monomorphisms permit forming direct products of any rcwa groups (regardless of whether they are tame or not):

##### 3.7-4 DirectProduct

`> DirectProduct`( G1, G2, ... ) | ( operation )

Returns: The direct product of the rcwa groups over Z given as arguments.

As there is no unique or canonical way to embed a direct product of rcwa groups into RCWA(Z), this method may choose any such embedding.

    gap> G := DirectProduct(Group(g,h),Group(a,b),Group(u));;
    gap> Embedding(G,1);
    [ g, h ] -> [ <bijective rcwa mapping of Z with modulus 18, of order 7>,
      <bijective rcwa mapping of Z with modulus 18, of order 12> ]
    gap> List([1..3],i->MovedPoints(Image(Embedding(G,i))));
    [ 0(3), 1(3) \ [ -2, 1 ], 2(3) \ [ -1, 2 ] ]
    gap> Image(Projection(G,2)) = Group(a,b);
    true

#### 3.8 Special attributes for tame rcwa groups

There is a couple of attributes which a priori make only sense for tame rcwa groups. In the sequel, these attributes are described in detail.

With their help, various structural information about a given tame rcwa group can be obtained. For example, there are methods for `IsSolvable` and `IsPerfect` available for tame rcwa groups (the latter works in some cases by other means also for wild groups). Often it is also feasible to compute the derived subgroup of a tame rcwa group.

##### 3.8-1 RespectedPartition

`> RespectedPartition`( G ) | ( attribute )

`> RespectedPartition`( sigma ) | ( attribute )

Returns: A respected partition of G resp. sigma.

This is a partition of the base ring R into a finite number of residue classes which the group G resp. the permutation sigma acts on, and on those elements all elements of G resp. the group generated by sigma are affine.

In the author's thesis it is shown that such a partition exists if and only if G resp. sigma is tame (see Theorem 2.5.8).

    gap> G := Group(g,h);;
    gap> Size(G);
    infinity
    gap> P := RespectedPartition(G);
    [ 0(12), 1(12), 3(12), 4(12), 5(12), 6(12), 7(12), 9(12), 10(12), 11(12),
      2(24), 8(24), 14(24), 20(24) ]
    gap> Permutation(g,P);
    (1,11,2,5,3,12,4)(6,13,7,10,8,14,9)

##### 3.8-2 ActionOnRespectedPartition

`> ActionOnRespectedPartition`( G ) | ( attribute )

Returns: The action of the tame rcwa group G on `RespectedPartition(G)`.

    gap> H := ActionOnRespectedPartition(G);
    Group([ (1,11,2,5,3,12,4)(6,13,7,10,8,14,9), (1,11,2,10)(3,12,4)(5,6,13,7)(8,
        14,9) ])
    gap> H = Action(G,P);
    true
    gap> [ Size(H), Size(DerivedSubgroup(H)), IsPerfect(DerivedSubgroup(H)) ];
    [ 322560, 161280, true ]

##### 3.8-3 IntegralConjugate

`> IntegralConjugate`( G ) | ( attribute )

`> IntegralConjugate`( f ) | ( attribute )

Returns: Some integral conjugate of the tame rcwa group G resp. of the tame bijective rcwa mapping f in the group RCWA(Z).

In the author's thesis it is shown that such a representative exists (see Theorem 2.5.14). Since there is usually not only one such mapping, methods for this operation will just choose one of them.

    gap> Print(LaTeXObj(IntegralConjugate(g)));
    n \ \longmapsto \
    \begin{cases}
      n + 10 & \text{if} \ n \in 0(14), \\
      n + 3  & \text{if} \ n \in 1(14) \cup 6(14), \\
      n + 9  & \text{if} \ n \in 2(14), \\
      n - 3  & \text{if} \ n \in 3(14) \cup 8(14), \\
      n - 2  & \text{if} \ n \in 4(14) \cup 9(14), \\
      n + 7  & \text{if} \ n \in 5(14), \\
      n + 6  & \text{if} \ n \in 7(14), \\
      n - 9  & \text{if} \ n \in 10(14), \\
      n - 8  & \text{if} \ n \in 11(14), \\
      n - 6  & \text{if} \ n \in 12(14), \\
      n - 5  & \text{if} \ n \in 13(14).
    \end{cases}

##### 3.8-4 IntegralizingConjugator

`> IntegralizingConjugator`( G ) | ( attribute )

`> IntegralizingConjugator`( f ) | ( attribute )

Returns: An rcwa mapping mapping x such that G^x resp. f^x is integral.

This is of course not defined uniquely, but it holds that `G^IntegralizingConjugator(G) = IntegralConjugate(G)` resp. `f^IntegralizingConjugator(f) = IntegralConjugate(f)`.

    gap> Print(LaTeXObj(IntegralizingConjugator(g)));
    n \ \longmapsto \
    \begin{cases}
      \frac{7n}{6}        & \text{if} \ n \in 0(12), \\
      \frac{7n - 1}{6}    & \text{if} \ n \in 1(12), \\
      \frac{7n + 106}{12} & \text{if} \ n \in 2(24), \\
      \frac{7n - 9}{6}    & \text{if} \ n \in 3(12), \\
      \frac{7n - 10}{6}   & \text{if} \ n \in 4(12), \\
      \frac{7n - 11}{6}   & \text{if} \ n \in 5(12), \\
      \frac{7n - 12}{6}   & \text{if} \ n \in 6(12), \\
      \frac{7n - 13}{6}   & \text{if} \ n \in 7(12), \\
      \frac{7n + 76}{12}  & \text{if} \ n \in 8(24), \\
      \frac{7n - 21}{6}   & \text{if} \ n \in 9(12), \\
      \frac{7n - 22}{6}   & \text{if} \ n \in 10(12), \\
      \frac{7n - 23}{6}   & \text{if} \ n \in 11(12), \\
      \frac{7n + 46}{12}  & \text{if} \ n \in 14(24), \\
      \frac{7n + 16}{12}  & \text{if} \ n \in 20(24).
    \end{cases}

#### 3.9 The categories and families of rcwa groups

##### 3.9-1 IsRcwaGroup

`> IsRcwaGroup`( G ) | ( filter )

`> IsIntegralRcwaGroup`( G ) | ( filter )

`> IsSemilocalIntegralRcwaGroup`( G ) | ( filter )

`> IsModularRcwaGroup`( G ) | ( filter )

Returns: `true` if G is an rcwa group resp. an rcwa group over the ring of integers resp. an rcwa group over a semilocalization of the ring of integers resp. an rcwa group over a polynomial ring in one variable over a finite field, and `false` otherwise.

##### 3.9-2 IntegralRcwaGroupsFamily

`> IntegralRcwaGroupsFamily` | ( family )

The family of all rcwa groups over the ring of integers.

Top of Book | Previous Chapter | Next Chapter

Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | 6 | Bib | Ind

generated by GAPDoc2HTML