In this chapter, we would like to give some "nice" examples of rcwa mappings and groups generated by them. The rcwa mappings used in this chapter can be found in the file rcwa/examples/examples.gap, so there is no need to extract them from the manual files.
This is probably not the most interesting application of this package, but we can turn the Collatz-(3n+1-) problem into an equivalent question by replacing the Collatz mapping T by one of its conjugates under an element of the pointwise stabilizer of 1 in the setwise stabilizer of the positive integers of the integral residue class-wise affine group.
Define the Collatz mapping:
gap> T := RcwaMapping([[1,0,2],[3,1,2]]); <integral rcwa mapping with modulus 2> |
A suitable bijection:
gap> a := RcwaMapping([[3,0,2],[3,1,4],[3,0,2],[3,-1,4]]); <integral rcwa mapping with modulus 4> gap> IsBijective(a); true gap> 1^a; # The mapping a stabilizes 1 1 |
Some evidence that a stabilizes the set of positive integers (this certainly can be proved easily ...):
gap> List([1..50],n->n^a); [ 1, 3, 2, 6, 4, 9, 5, 12, 7, 15, 8, 18, 10, 21, 11, 24, 13, 27, 14, 30, 16, 33, 17, 36, 19, 39, 20, 42, 22, 45, 23, 48, 25, 51, 26, 54, 28, 57, 29, 60, 31, 63, 32, 66, 34, 69, 35, 72, 37, 75 ] |
Compute T^a:
gap> f := T^a;;
gap> Display(f);
Integral rcwa mapping with modulus 12
n mod 12 | n^f
---------------------------------------+--------------------------------------
0 6 | n/2
1 4 7 10 | 3n
2 8 | (3n + 2)/2
3 | (n + 1)/4
5 11 | (3n + 1)/2
9 | (n - 1)/4
|
Have a look at resulting integer sequences:
gap> seq := function(n)
> repeat Print(n,","); n := n^f; until n = 1; Print("1.\n");
> end;
function( n ) ... end
gap> seq(7);
7,21,5,8,13,39,10,30,15,4,12,6,3,1.
gap> seq(10);
10,30,15,4,12,6,3,1.
gap> seq(20);
20,31,93,23,35,53,80,121,363,91,273,68,103,309,77,116,175,525,131,197,296,445,
1335,334,1002,501,125,188,283,849,212,319,957,239,359,539,809,1214,1822,5466,
2733,683,1025,1538,2308,6924,3462,1731,433,1299,325,975,244,732,366,183,46,
138,69,17,26,40,120,60,30,15,4,12,6,3,1.
|
It seems that they all reach 1, as the original 3n+1 sequences ... .
We give an rcwa representation of the 3-Sylow-subgroup of the symmetric group on 9 points. Certainly, this group has a very nice permutation representation, hence for computational purposes, we cannot do better here.
gap> r := RcwaMapping([[1,0,1],[1,1,1],[3,-3,1],
> [1,0,3],[1,1,1],[3,-3,1],
> [1,0,1],[1,1,1],[3,-3,1]]);;
gap> s := 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> Display(r);
Integral rcwa mapping with modulus 9
n mod 9 | n^f
---------------------------------------+--------------------------------------
0 6 | n
1 4 7 | n + 1
2 5 8 | 3n - 3
3 | n/3
gap> Display(s);
Integral rcwa mapping with modulus 9
n mod 9 | n^f
---------------------------------------+--------------------------------------
0 6 | n
1 4 7 | n + 1
2 5 | 3n + 6
3 | n/3
8 | 3n - 21
gap> G := Group(r,s);
<integral rcwa group with 2 generators>
gap> H := SylowSubgroup(SymmetricGroup(9),3);
Group([ (1,2,3), (4,5,6), (7,8,9), (1,4,7)(2,5,8)(3,6,9) ])
gap> phi := InverseGeneralMapping(IsomorphismGroups(G,H));
[ (1,5,8)(2,6,9)(3,4,7), (1,6,9,2,4,7,3,5,8) ] ->
[ <bijective integral rcwa mapping with modulus 9, of order 3>,
<bijective integral rcwa mapping with modulus 9, of order 9> ]
|
Firstly, we define some bijections of infinite order and compute commutators:
gap> a := RcwaMapping([[3,0,2],[3, 1,4],[3,0,2],[3,-1,4]]);; gap> b := RcwaMapping([[3,0,2],[3,13,4],[3,0,2],[3,-1,4]]);; gap> c := RcwaMapping([[3,0,2],[3, 1,4],[3,0,2],[3,11,4]]);; gap> Order(a); infinity gap> Order(b); infinity gap> Order(c); infinity gap> ab := Comm(a,b);; gap> ac := Comm(a,c);; gap> bc := Comm(b,c);; gap> Order(ab); 6 gap> Order(ac); 6 gap> Order(bc); 12 |
Now we would like to have a look at [ a, b ].
gap> Display(ab);
Bijective integral rcwa mapping with modulus 18, of order 6
n mod 18 | n^f
---------------------------------------+--------------------------------------
0 2 3 8 9 11 12 17 | n
1 10 | 2n - 5
4 7 13 16 | n + 3
5 14 | 2n - 4
6 | (n + 2)/2
15 | (n - 5)/2
|
Afterwards, we form the group generated by [ a, b ] and [ a, c ] and compute its action on one of its orbits ...
gap> G := Group(ab,ac); <integral rcwa group with 2 generators> gap> orb := Orbit(G,1); [ 1, -3, -4, -12, -1, -5, -6, -2, -15, -7 ] gap> H := Action(G,orb); Group([ (1,2,3,4,6,8), (3,5,7,6,9,10) ]) gap> Size(H); 3628800 gap> Size(G); 3628800 gap> H := NiceObject(G); Group([ (2,4,6,10,3,8), (1,3,5,9,2,7) ]) |
Hence, G is isomorphic to the symmetric group on 10 points and acts faithfully on the orbit containing 1. We also would like to know which groups arise if we take as generators either ab, ac or bc and the mapping t, which maps each integer to its additive inverse:
gap> t := RcwaMapping([[-1,0,1]]);
Integral rcwa mapping: n -> -n
gap> Order(t);
2
gap> G := Group(ab,t);
<integral rcwa group with 2 generators>
gap> Size(G);
7257600
gap> H := NiceObject(G);
Group([ (2,7,9,10,4,8)(13,15,16,20,14,18), (1,20)(2,19)(3,18)(4,17)(5,16)(6,
15)(7,14)(8,13)(9,12)(10,11) ])
gap> H2 := Group((1,2),(1,2,3,4,5,6,7,8,9,10),(11,12));
Group([ (1,2), (1,2,3,4,5,6,7,8,9,10), (11,12) ])
gap> phi := IsomorphismGroups(H,H2);
[ (2,7,9,10,4,8)(13,15,16,20,14,18), (1,20)(2,19)(3,18)(4,17)(5,16)(6,15)(7,
14)(8,13)(9,12)(10,11) ] ->
[ (3,8,9,4,10,7), (1,3)(2,8)(4,5)(6,7)(9,10)(11,12) ]
|
Hence, the group generated by ab and t is isomorphic to C_2 x S_10. The next group is an extension of a perfect group of order 960:
gap> G := Group(ac,t);;
gap> Size(G);
3840
gap> H := NiceObject(G);
Group([ (1,6,8,10,3,7)(12,14,16,19,13,17), (1,20)(2,19)(3,18)(4,17)(5,16)(6,
15)(7,14)(8,13)(9,12)(10,11) ])
gap> P := DerivedSubgroup(H);
Group([ (1,6,8,2,5)(3,7,9,4,10)(11,17,12,14,18)(13,15,20,16,19),
(1,2,8,4,6)(3,10,9,7,5)(11,19,16,15,13)(12,17,18,14,20) ])
gap> Size(P);
960
gap> IsPerfect(P);
true
gap> IdGroup(PerfectGroup(960,1));
[ 960, 11357 ]
gap> IdGroup(PerfectGroup(960,2));
[ 960, 11358 ]
gap> IdGroup(P);
[ 960, 11358 ]
|
The last group is infinite:
gap> G := Group(bc,t);; gap> Size(G); infinity gap> Order(bc*t); infinity gap> Modulus(G); 18 |
We define an rcwa mapping x of order 257 with modulus 32 (the easiest way to construct such a mapping is to prescribe the graph and then assign suitable affine mappings to its vertices).
gap> x := RcwaMapping([[ 16, 2, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 0, 16], [ 16, 18, 1],
> [ 1,-14, 1], [ 16, 18, 1],
> [ 1,-14, 1], [ 16, 18, 1],
> [ 1,-14, 1], [ 16, 18, 1],
> [ 1,-14, 1], [ 16, 18, 1],
> [ 1,-14, 1], [ 16, 18, 1],
> [ 1,-14, 1], [ 16, 18, 1],
> [ 1,-14, 1], [ 1,-31, 1]]);;
gap> Display(x);
Integral rcwa mapping with modulus 32
n mod 32 | n^f
---------------------------------------+--------------------------------------
0 | 16n + 2
1 3 5 7 9 11 13 15 17 19 21 23 |
25 27 29 | 16n + 18
2 4 6 8 10 12 14 | n + 16
16 | n/16
18 20 22 24 26 28 30 | n - 14
31 | n - 31
gap> Order(x);
257
gap> List([-20..20],n->n^x);
[ -4, -286, -2, -254, -1, -222, -28, -190, -26, -158, -24, -126, -22, -94,
-20, -62, -18, -30, -16, -32, 2, 34, 18, 66, 20, 98, 22, 130, 24, 162, 26,
194, 28, 226, 30, 258, 1, 290, 4, 322, 6 ]
|
Certainly, we would like to know how a cycle of this permutation looks like.
gap> Cycle(x,[1],0); [ 0, 2, 18, 4, 20, 6, 22, 8, 24, 10, 26, 12, 28, 14, 30, 16, 1, 34, 50, 36, 52, 38, 54, 40, 56, 42, 58, 44, 60, 46, 62, 48, 3, 66, 82, 68, 84, 70, 86, 72, 88, 74, 90, 76, 92, 78, 94, 80, 5, 98, 114, 100, 116, 102, 118, 104, 120, 106, 122, 108, 124, 110, 126, 112, 7, 130, 146, 132, 148, 134, 150, 136, 152, 138, 154, 140, 156, 142, 158, 144, 9, 162, 178, 164, 180, 166, 182, 168, 184, 170, 186, 172, 188, 174, 190, 176, 11, 194, 210, 196, 212, 198, 214, 200, 216, 202, 218, 204, 220, 206, 222, 208, 13, 226, 242, 228, 244, 230, 246, 232, 248, 234, 250, 236, 252, 238, 254, 240, 15, 258, 274, 260, 276, 262, 278, 264, 280, 266, 282, 268, 284, 270, 286, 272, 17, 290, 306, 292, 308, 294, 310, 296, 312, 298, 314, 300, 316, 302, 318, 304, 19, 322, 338, 324, 340, 326, 342, 328, 344, 330, 346, 332, 348, 334, 350, 336, 21, 354, 370, 356, 372, 358, 374, 360, 376, 362, 378, 364, 380, 366, 382, 368, 23, 386, 402, 388, 404, 390, 406, 392, 408, 394, 410, 396, 412, 398, 414, 400, 25, 418, 434, 420, 436, 422, 438, 424, 440, 426, 442, 428, 444, 430, 446, 432, 27, 450, 466, 452, 468, 454, 470, 456, 472, 458, 474, 460, 476, 462, 478, 464, 29, 482, 498, 484, 500, 486, 502, 488, 504, 490, 506, 492, 508, 494, 510, 496, 31 ] gap> Length(last); 257 |
We define two very similar rcwa mappings with modulus 6, and compute their orders:
gap> g := RcwaMapping([[2,2,1],[1, 4,1],[1,0,2],[2,2,1],[1,-4,1],[1,-2,1]]);
<integral rcwa mapping with modulus 6>
gap> h := RcwaMapping([[2,2,1],[1,-2,1],[1,0,2],[2,2,1],[1,-1,1],[1, 1,1]]);
<integral rcwa mapping with modulus 6>
gap> Order(g);
7
gap> Order(h);
12
gap> Display(g);
Bijective integral rcwa mapping with modulus 6, of order 7
n mod 6 | n^f
---------------------------------------+--------------------------------------
0 3 | 2n + 2
1 | n + 4
2 | n/2
4 | n - 4
5 | n - 2
|
gap> Display(h);
Bijective integral rcwa mapping with modulus 6, of order 12
n mod 6 | n^f
---------------------------------------+--------------------------------------
0 3 | 2n + 2
1 | n - 2
2 | n/2
4 | n - 1
5 | n + 1
|
gap> Display(g - h);
Integral rcwa mapping with modulus 6
n mod 6 | n^f
---------------------------------------+--------------------------------------
0 2 3 | 0
1 | 6
4 5 | -3
gap> Display(Comm(g,h));
Bijective integral rcwa mapping with modulus 6
n mod 6 | n^f
---------------------------------------+--------------------------------------
0 | n + 3
1 4 | n
2 5 | n - 6
3 | n + 9
gap> Order(Comm(g,h));
infinity
|
Both of these mappings have an rcwa graph consisting of one cycle of length 3 and one of length 4. The mapping g has order 3 + 4 = 7, because the two cycles are always passed consecutively, since running through one of them results in an addition of 6, and running through the other in a subtraction of 6, while h has order 3 * 4 = 12, because here, the two cycles are passed independant from each other, since running through one of them always ends up in the starting point.
Firstly, we define our group G:
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> Order(v); 6 gap> Order(w); 8 gap> G := Group(v,w);; gap> Size(G); infinity gap> IsAbelian(G); false gap> Modulus(G); 12 |
Then, we construct the normal subgroup N as the normal closure of some element z:
gap> z := (v*w*v)^6;
<bijective integral rcwa mapping with modulus 12>
gap> Display(z);
Bijective integral rcwa mapping with modulus 12
n mod 12 | n^f
---------------------------------------+--------------------------------------
0 2 3 6 8 9 | n
1 4 7 10 11 | n - 12
5 | n + 12
|
We are looking for generators:
gap> line := g -> List([0..11], n -> n^g - n);; gap> M := [];; gap> M[1] := line(z); [ 0, -12, 0, 0, -12, 12, 0, -12, 0, 0, -12, -12 ] gap> M[2] := line(z^v); [ -12, 0, 0, -12, 12, 0, -12, 0, 0, -12, -12, 0 ] gap> M[3] := line(z^w); [ -12, 0, 0, 0, 12, 0, -12, 0, 0, -12, -12, 12 ] gap> RankMat(M); 3 gap> M[4] := line(z^(v^-1));; gap> M[5] := line(z^(w^-1));; gap> RankMat(M); 5 gap> M[6] := line(z^(v*w));; gap> RankMat(M); 5 gap> M[6] := line(z^(w*v));; gap> RankMat(M); 6 gap> M[7] := line(z^(v^2));; gap> RankMat(M); 7 gap> M[8] := line(z^(w^2));; gap> RankMat(M); 8 gap> M[9] := line(z^(v*w*v));; gap> RankMat(M); 8 gap> M[9] := line(z^(w*v*w));; gap> RankMat(M); 9 gap> M[10] := line(z^(v^-2));; gap> RankMat(M); 10 gap> M[11] := line(z^(w^-2));; gap> RankMat(M); 10 gap> M[11] := line(z^(v^2*w));; gap> RankMat(M); 11 gap> M[12] := line(z^(w*v^2));; gap> RankMat(M); 12 gap> Display(M); [ [ 0, -12, 0, 0, -12, 12, 0, -12, 0, 0, -12, -12 ], [ -12, 0, 0, -12, 12, 0, -12, 0, 0, -12, -12, 0 ], [ -12, 0, 0, 0, 12, 0, -12, 0, 0, -12, -12, 12 ], [ 0, 0, -12, 12, 0, -12, 0, 0, -12, -12, 0, -12 ], [ 0, 0, -12, 0, 12, -12, 12, 0, 12, 0, 0, -12 ], [ 0, 0, 12, 12, 0, 12, 0, 0, 12, -12, 12, 0 ], [ 0, 0, 12, 12, 0, 12, 0, 0, 12, -12, 0, 12 ], [ 0, 0, 0, 12, 0, -12, 0, 0, -12, -12, 12, -12 ], [ 0, 12, 12, 0, 12, 0, 0, -12, -12, 12, 0, 0 ], [ 12, 0, 0, 12, 12, 0, 12, 0, 0, 12, -12, 0 ], [ 0, 12, 12, 0, 12, 0, 0, -12, -12, 0, 12, 0 ], [ 0, 12, 0, 0, 12, 12, 0, 12, 0, 12, 0, -12 ] \ ] gap> DeterminantMat(M); -285315214344192 |
Now, we have our normal subgroup:
gap> gens := [z,z^v,z^w,z^(v^-1),z^(w^-1),z^(w*v),z^(v^2), > z^(w^2),z^(w*v*w),z^(v^-2),z^(v^2*w),z^(w*v^2)];; gap> N := Group(gens); <integral rcwa group with 12 generators> gap> IsAbelian(N); true gap> Size(N); infinity |
In this section, we give some examples illustrating how different the series of the moduli of powers of a given integral rcwa mapping can look like.
gap> List([0..4],i->Modulus(a^i));
[ 1, 4, 16, 64, 256 ]
gap> List([0..6],i->Modulus(ab^i));
[ 1, 18, 18, 18, 18, 18, 1 ]
gap> List([0..3],i->Modulus(r^i));
[ 1, 9, 9, 1 ]
gap> List([0..9],i->Modulus(s^i));
[ 1, 9, 9, 27, 27, 27, 27, 27, 27, 1 ]
gap> List([0..7],i->Modulus(g^i));
[ 1, 6, 12, 12, 12, 12, 6, 1 ]
gap> List([0..3],i->Modulus(u^i));
[ 1, 5, 25, 125 ]
gap> List([0..2],i->Modulus(y^i));
[ 1, 18, 324 ]
gap> List([0..6],i->Modulus(v^i));
[ 1, 3, 3, 3, 3, 3, 1 ]
gap> List([0..8],i->Modulus(w^i));
[ 1, 4, 4, 4, 4, 4, 4, 4, 1 ]
gap> z := RcwaMapping([[2, 1, 1],[1, 1,1],[2, -1,1],[2, -2,1],
> [1, 6, 2],[1, 1,1],[1, -6,2],[2, 5,1],
> [1, 6, 2],[1, 1,1],[1, 1,1],[2, -5,1],
> [1, 0, 1],[1, -4,1],[1, 0,1],[2,-10,1]]);;
gap> Order(z);
infinity
gap> Display(z);
Bijective integral rcwa mapping with modulus 16, of order infinity
n mod 16 | n^f
---------------------------------------+--------------------------------------
0 | 2n + 1
1 5 9 10 | n + 1
2 | 2n - 1
3 | 2n - 2
4 8 | (n + 6)/2
6 | (n - 6)/2
7 | 2n + 5
11 | 2n - 5
12 14 | n
13 | n - 4
15 | 2n - 10
gap> List([0..35],i->Modulus(z^i));
[ 1, 16, 32, 64, 64, 128, 128, 128, 128, 128, 128, 256, 256, 256, 256, 256,
256, 512, 512, 512, 512, 512, 512, 1024, 1024, 1024, 1024, 1024, 1024,
2048, 2048, 2048, 2048, 2048, 2048, 4096 ]
gap> e1 := RcwaMapping([[1,4,1],[2,0,1],[1,0,2],[2,0,1]]);;
gap> Order(e1);
infinity
gap> List([1..20],i->Modulus(e1^i));
[ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ]
gap> e2 := RcwaMapping([[1,4,1],[2,0,1],[1,0,2],[1,0,1],
> [1,4,1],[2,0,1],[1,0,1],[1,0,1]]);;
gap> Order(e2);
infinity
gap> List([1..20],i->Modulus(e2^i));
[ 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4 ]
gap> Display(e2);
Bijective integral rcwa mapping with modulus 8, of order infinity
n mod 8 | n^f
---------------------------------------+--------------------------------------
0 4 | n + 4
1 5 | 2n
2 | n/2
3 6 7 | n
gap> Display(e2^2);
Integral rcwa mapping with modulus 4
n mod 4 | n^f
---------------------------------------+--------------------------------------
0 | n + 8
1 2 3 | n
|
generated by GAPDoc2HTML