6 Databases of Residue-Class-Wise Affine Groups and -Mappings

The RCWA package contains a number of databases of rcwa groups and rcwa mappings. They can be loaded into a GAP session by the functions described in this chapter.

6.1 The collection of examples

6.1-1 LoadRCWAExamples

Returns: the name of the variable to which the record containing the collection of examples of rcwa groups and -mappings loaded from the file pkg/rcwa/examples/examples.g got bound.

The components of the examples record are records which contain the individual groups and mappings. A detailed description of some of the examples can be found in Chapter 7.

gap> LoadRCWAExamples();
"RCWAExamples"                                
gap> Set(RecNames(RCWAExamples));
[ "AbelianGroupOverPolynomialRing", "Basics", "CT3Z", "CTPZ", 
  "CheckingForSolvability", "ClassSwitches", 
  "ClassTranspositionProducts", "ClassTranspositionsAsCommutators", 
  "CollatzFactorizationOld", "CollatzMapping", "CollatzlikePerms", 
  "CoprimeMultDiv", "F2_PSL2Z", "Farkas", "FiniteQuotients", 
  "FiniteVsDenseCycles", "GF2xFiniteCycles", "GrigorchukQuotients", 
  "Hexagon", "HicksMullenYucasZavislak", "HigmanThompson", 
  "LongCyclesOfPrimeLength", "MatthewsLeigh", 
  "MaybeInfinitelyPresentedGroup", "ModuliOfPowers", 
  "OddNumberOfGens_FiniteOrder", "Semilocals", 
  "SlowlyContractingMappings", "Syl3_S9", "SymmetrizingCollatzTree", 
  "TameGroupByCommsOfWildPerms", "Venturini", "ZxZ" ]
gap> AssignGlobals(RCWAExamples.CollatzMapping);
The following global variables have been assigned:
[ "T", "T5", "T5m", "T5p", "Tm", "Tp" ]

6.2 Databases of rcwa groups

6.2-1 LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions

Returns: the name of the variable to which the record containing the database of all groups generated by 3 class transpositions which interchange residue classes with moduli ≤ 6 got bound.

The database record has at least the following components (the index i is always an integer in the range [1..52394], and the term "indices" always refers to list indices in that range):

cts

The list of all 69 class transpositions which interchange residue classes with moduli ≤ 6.

grps

The list of the 52394 groups -- 21948 finite and 30446 infinite ones.

sizes

The list of group orders -- it is Size(grps[i]) = sizes[i].

mods

The list of moduli of the groups -- it is Mod(grps[i]) = mods[i].

equalityclasses

A list of lists of indices i of groups which are known to be equal, i.e. if i and j lie in the same list, then grps[i] = grps[j].

samegroups

A list of lists, where samegroups[i] is a list of indices of groups which are known to be equal to grps[i].

conjugacyclasses

A list of lists of indices of groups which are known to be conjugate in RCWA(ℤ).

subgroups

A list of lists, where subgroups[i] is a list of indices of groups which are known to be proper subgroups of grps[i].

supergroups

A list of lists, where supergroups[i] is a list of indices of groups which are known to be proper supergroups of grps[i].

chains

A list of lists, where each list contains the indices of the groups in a descending chain of subgroups.

respectedpartitions

The list of shortest respected partitions. If grps[i] is finite, then respectedpartitions[i] is a list of pairs (residue, modulus) for the residue classes in the shortest respected partition grps[i]. If grps[i] is infinite, then respectedpartitions[i] = fail.

partitionlengths

The list of lengths of shortest respected partitions. If the group grps[i] is finite, then partitionlengths[i] is the length of the shortest respected partition of grps[i]. If grps[i] is infinite, then partitionlengths[i] = 0.

degrees

The list of permutation degrees, i.e. numbers of moved points, in the action of the finite groups on their shortest respected partitions. If there is no respected partition, i.e. if grps[i] is infinite, then degrees[i] = 0.

orbitlengths

The list of lists of orbit lengths in the action of the finite groups on their shortest respected partitions. If grps[i] is infinite, then orbitlengths[i] = fail.

permgroupgens

The list of lists of generators of the isomorphic permutation groups induced by the finite groups on their shortest respected partitions. If grps[i] is infinite, then permgroupgens[i] = fail.

stabilize_digitsum_base2_mod2

The list of indices of groups which stabilize the digit sum in base 2 modulo 2.

stabilize_digitsum_base2_mod3

The list of indices of groups which stabilize the digit sum in base 2 modulo 3.

stabilize_digitsum_base3_mod2

The list of indices of groups which stabilize the digit sum in base 3 modulo 2.

freeproductcandidates

A list of indices of groups which may be isomorphic to the free product of 3 copies of the cyclic group of order 2.

freeproductlikes

A list of indices of groups which are not isomorphic to the free product of 3 copies of the cyclic group of order 2, but where the shortest relation indicating this is relatively long.

abc_torsion

A list of pairs (index, order of product of generators) for all infinite groups for which the product of the generators has finite order.

cyclist

A list described in the comments in rcwa/data/3ctsgroups6/spheresizecycles.g.

finiteorbits

A record described in the comments in rcwa/data/3ctsgroups6/finite-orbits.g.

intransitivemodulo

For every modulus m from 1 to 60, intransitivemodulo[m] is the list of indices of groups none of whose orbits on ℤ has nontrivial intersection with all residue classes modulo m.

trsstatus

A list of strings which describe what is known about whether the groups grps[i] act transitively on the nonnegative integers in their support, or how the computation has failed.

orbitgrowthtype

A list of integers and lists of integers which encode what has been observed heuristically on the growth of the orbits of the groups grps[i] on ℤ.

Note that the database contains an entry for every unordered 3-tuple of distinct class transpositions in cts, which means that it contains multiple copies of equal groups -- cf. the components equalityclasses and samegroups described above.

To mention an example, the group grps[44132] might be called the "Collatz group" -- its action on the set of positive integers which are not multiples of 6 is transitive if and only if the Collatz conjecture holds.

gap> LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions();
"3CTsGroups6"
gap> AssignGlobals(3CTsGroups6); # for convenience
The following global variables have been assigned:
[ "3CTsGroupsWithGivenOrbit", "Id3CTsGroup", 
  "ProbablyFixesDigitSumsModulo", "ProbablyStabilizesDigitSumsModulo", 
  "TriangleTypes", "abc_torsion", "chains", "conjugacyclasses", "cts", 
  "cyclist", "degrees", "epifromfpgroupto_ct23z", 
  "epifromfpgrouptocollatzgroup_c", "epifromfpgrouptocollatzgroup_t", 
  "equalityclasses", "finiteorbits", "freeproductcandidates", 
  "freeproductlikes", "groups", "grps", "intransitivemodulo", 
  "minwordlengthcoprimemultdiv", "minwordlengthnonbalanced", "mods", 
  "orbitgrowthtype", "orbitlengths", "partitionlengths", "permgroupgens",
  "redundant_generator", "refinementseqlngs", "respectedpartitions", 
  "samegroups", "shortresidueclassorbitlengths", "sizes", "sizespos", 
  "sizesset", "spheresizebound_12", "spheresizebound_24", 
  "spheresizebound_4", "spheresizebound_6", 
  "stabilize_digitsum_base2_mod2", "stabilize_digitsum_base2_mod3", 
  "stabilize_digitsum_base3_mod2", "subgroups", "supergroups", 
  "trsstatus", "trsstatuspos", "trsstatusset" ]
gap> grps[44132]; # the "3n+1 group"
<(2(3),4(6)),(1(3),2(6)),(1(2),4(6))>
gap> trsstatus[44132]; # deciding this would solve the 3n+1 problem
"exceeded memory bound"
gap> Length(Set(sizes));
1066
gap> Maximum(Filtered(sizes,IsInt)); # order of largest finite group stored
7165033589793852697531456980706732548435609645091822296777976465116824959\
2135499174617837911754921014138184155204934961004073853323458315539461543\
4480515260818409913846161473536000000000000000000000000000000000000000000\
000000
gap> PrintFactorsInt(last);                                    
2^200*3^103*5^48*7^28*11^16*13^13*17^8*19^6*23^6*29
gap> Positions(sizes,last);                               
[ 33814, 36548 ]
gap> grps{last};
[ <(1(5),4(5)),(0(3),1(6)),(3(4),0(6))>, 
  <(0(5),3(5)),(2(3),4(6)),(0(4),5(6))> ]
gap> samegroups[1];    
[ 1, 2, 68 ]
gap> grps[1] = grps[68];
true
gap> Maximum(mods);
77760
gap> Positions(mods,last);
[ 26311, 26313, 26452, 26453, 26455, 26456, 26457, 26459, 26461, 26462, 
  27781, 27784, 27785, 27786, 27788, 27789, 27790, 27791, 27829, 27832, 
  30523, 30524, 30525, 30526, 30529, 30530, 30532, 30534, 32924, 32927, 
  32931, 32933 ]
gap> Set(sizes{last});     
[ 45509262704640000 ]
gap> Collected(mods);
[ [ 0, 30446 ], [ 3, 1 ], [ 4, 37 ], [ 5, 120 ], [ 6, 1450 ], [ 8, 18 ], 
  [ 10, 45 ], [ 12, 3143 ], [ 15, 165 ], [ 18, 484 ], [ 20, 528 ], 
  [ 24, 1339 ], [ 30, 2751 ], [ 36, 2064 ], [ 40, 26 ], [ 48, 515 ], 
  [ 60, 2322 ], [ 72, 2054 ], [ 80, 44 ], [ 90, 108 ], [ 96, 108 ], 
  [ 108, 114 ], [ 120, 782 ], [ 144, 310 ], [ 160, 26 ], [ 180, 206 ], 
  [ 192, 6 ], [ 216, 72 ], [ 240, 304 ], [ 270, 228 ], [ 288, 14 ], 
  [ 360, 84 ], [ 432, 36 ], [ 480, 218 ], [ 540, 18 ], [ 720, 120 ], 
  [ 810, 112 ], [ 864, 8 ], [ 960, 94 ], [ 1080, 488 ], [ 1620, 44 ], 
  [ 1920, 38 ], [ 2160, 506 ], [ 3240, 34 ], [ 3840, 12 ], 
  [ 4320, 218 ], [ 4860, 16 ], [ 6480, 282 ], [ 7680, 10 ], 
  [ 8640, 16 ], [ 12960, 120 ], [ 14580, 2 ], [ 25920, 34 ], 
  [ 30720, 2 ], [ 38880, 12 ], [ 51840, 8 ], [ 77760, 32 ] ]
gap> Collected(trsstatus);
[ [ "> 1 orbit (mod m)", 593 ], 
  [ "Mod(U DecreasingOn) exceeded <maxmod>", 23 ], 
  [ "U DecreasingOn stable and exceeded memory bound", 11 ], 
  [ "U DecreasingOn stable for <maxeq> steps", 5753 ], 
  [ "exceeded memory bound", 497 ], [ "finite", 21948 ], 
  [ "intransitive, but finitely many orbits", 8 ], 
  [ "seemingly only finite orbits (long)", 1227 ], 
  [ "seemingly only finite orbits (medium)", 2501 ], 
  [ "seemingly only finite orbits (short)", 4816 ], 
  [ "seemingly only finite orbits (very long)", 230 ], 
  [ "seemingly only finite orbits (very long, very unclear)", 76 ], 
  [ "seemingly only finite orbits (very short)", 208 ], 
  [ "there are infinite orbits which have exponential sphere size growth"
        , 2934 ], 
  [ "there are infinite orbits which have linear sphere size growth", 
      10881 ],
  [ "there are infinite orbits which have unclear sphere size growth", 
      86 ], [ "transitive", 562 ], 
  [ "transitive up to one finite orbit", 40 ] ]

6.2-2 LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions

Returns: the name of the variable to which the record containing the database of all groups generated by 3 class transpositions which interchange residue classes with moduli less than or equal to max_m got bound, where max_m is either 6 or 9.

If max_m is 6, this is equivalent to the call of the function without argument described above. If max_m is 9, the function returns a record with at least the following components (in the sequel, the indices i > j > k are always integers in the range [1..264]):

cts

The list of all 264 class transpositions which interchange residue classes with moduli ≤ 9.

mods

The list of moduli of the groups, i.e. Mod(Group(cts{[i,j,k]})) = mods[i][j][k].

partlengths

The list of lengths of shortest respected partitions of the groups in the database, i.e. Length(RespectedPartition(Group(cts{[i,j,k]}))) = partlengths[i][j][k].

sizes

The list of orders of the groups, i.e. Size(Group(cts{[i,j,k]})) = sizes[i][j][k].

All3CTs9Indices

A selector function which takes as argument a function func of three arguments i, j and k. It returns a list of all triples of indices [i,j,k] where 264 ≥ i > j > k ≥ 1 for which func returns true.

All3CTs9Groups

A selector function which takes as argument a function func of three arguments i, j and k. It returns a list of all groups Group(cts{[i,j,k]}) from the database for which func(i,j,k) returns true.

gap> LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions(9);
"3CTsGroups9"
gap> AssignGlobals(3CTsGroups9);
The following global variables have been assigned:
[ "All3CTs9Groups", "All3CTs9Indices", "cts", "mods", "partlengths", 
  "sizes" ]
gap> PrintFactorsInt(Maximum(Filtered(Flat(sizes),n->n<>infinity)));
2^1283*3^673*5^305*7^193*11^98*13^84*17^50*19^41*23^25*29^13*31^4

6.2-3 LoadDatabaseOfGroupsGeneratedBy4ClassTranspositions

Returns: the name of the variable to which the record containing the database of all groups generated by 4 class transpositions which interchange residue classes with moduli ≤ 6 for which all subgroups generated by 3 out of the 4 generators are finite got bound.

The record has at least the following components (the index i is always an integer in the range [1..140947], and the term "indices" always refers to list indices in that range):

cts

The list of all 69 class transpositions which interchange residue classes with moduli ≤ 6.

grps4_3finite

The list of all 140947 groups in the database.

grps4_3finitepos

The list obtained from grps4_3finite by replacing every group by the list of positions of its generators in the list cts.

sizes4

The list of group orders -- it is Size(grps4_3finite[i]) = sizes4[i].

mods4

The list of moduli of the groups -- it is Mod(grps4_3finite[i]) = mods4[i].

conjugacyclasses4cts

A list of lists of indices of groups which are known to be conjugate in RCWA(ℤ).

grps4_3finite_reps

Tentative conjugacy class representatives from the list grps4_3finite -- tentative in the sense that likely some of the groups in the list are still conjugate.

Note that the database contains an entry for every suitable unordered 4-tuple of distinct class transpositions in cts, which means that it contains multiple copies of equal groups.

gap> LoadDatabaseOfGroupsGeneratedBy4ClassTranspositions(); 
"4CTsGroups6"
gap> AssignGlobals(4CTsGroups6);
The following global variables have been assigned:
[ "conjugacyclasses4cts", "cts", "grps4_3finite", "grps4_3finite_reps", 
  "grps4_3finitepos", "mods4", "sizes4", "sizes4pos", "sizes4set" ]
gap> Length(grps4_3finite);
140947
gap> Length(sizes4);
140947
gap> Size(grps4_3finite[1]);
518400
gap> sizes4[1];
518400
gap> Maximum(Filtered(sizes4,IsInt));
<integer 420...000 (3852 digits)>
gap> Modulus(grps4_3finite[1]);
12
gap> mods4[1];
12
gap> Length(Set(sizes4));
7339
gap> Length(Set(mods4));
91
gap> conjugacyclasses4cts{[1..4]};
[ [ 1, 23, 563, 867 ], [ 2, 859 ], [ 3, 622 ], [ 4, 16, 868, 873 ] ]
gap> grps4_3finite[1] = grps4_3finite[23];
true
gap> grps4_3finite[4] = grps4_3finite[16];
false

6.3 Databases of rcwa mappings

6.3-1 LoadDatabaseOfProductsOf2ClassTranspositions

Returns: the name of the variable to which the record containing the database of products of 2 class transpositions got bound.

There are 69 class transpositions which interchange residue classes with moduli ≤ 6, thus there is a total of (69 ⋅ 68)/2 = 2346 unordered pairs of distinct such class transpositions. Looking at intersection- and subset relations between the 4 involved residue classes, we can distinguish 17 different "intersection types" (or 18, together with the trivial case of equal class transpositions). The intersection type does not fully determine the cycle structure of the product. -- In total, we can distinguish 88 different cycle types of products of 2 class transpositions which interchange residue classes with moduli ≤ 6.

The components of the database record are a list CTPairs of all 2346 pairs of distinct class transpositions which interchange residue classes with moduli ≤ 6, functions CTPairsIntersectionTypes, CTPairIntersectionType and CTPairProductType, as well as data lists OrdersMatrix, CTPairsProductClassification, CTPairsProductType, CTProds12 and CTProds32. -- For the description of these components, see the file pkg/rcwa/data/ctproducts/ctprodclass.g.

gap> LoadDatabaseOfProductsOf2ClassTranspositions();
"CTProducts"
gap> Set(RecNames(CTProducts));
[ "CTPairIntersectionType", "CTPairProductType", "CTPairs", 
  "CTPairsIntersectionTypes", "CTPairsProductClassification", 
  "CTPairsProductType", "CTProds12", "CTProds32", "OrdersMatrix" ]
gap> Length(CTProducts.CTPairs);
2346
gap> Collected(List(CTProducts.CTPairsProductType,l->l[2])); # order stats
[ [ 2, 165 ], [ 3, 255 ], [ 4, 173 ], [ 6, 693 ], [ 10, 2 ], 
  [ 12, 345 ], [ 15, 4 ], [ 20, 10 ], [ 30, 120 ], [ 60, 44 ], 
  [ infinity, 535 ] ]

6.3-2 LoadDatabaseOfNonbalancedProductsOfClassTranspositions

Returns: the name of the variable to which the record containing the database of non-balanced products of class transpositions got bound.

This database contains a list of the 24 pairs of class transpositions which interchange residue classes with moduli ≤ 6 and whose product is not balanced, as well as a list of all 36 essentially distinct triples of such class transpositions whose product has coprime multiplier and divisor.

gap> LoadDatabaseOfNonbalancedProductsOfClassTranspositions();
"CTProductsNB"
gap> Set(RecNames(CTProductsNB));
[ "PairsOfCTsWhoseProductIsNotBalanced", 
  "TriplesOfCTsWhoseProductHasCoprimeMultiplierAndDivisor" ]
gap> CTProductsNB.PairsOfCTsWhoseProductIsNotBalanced;
[ [ ( 1(2), 2(4) ), ( 2(4), 3(6) ) ], [ ( 1(2), 2(4) ), ( 2(4), 5(6) ) ], 
  [ ( 1(2), 2(4) ), ( 2(4), 1(6) ) ], [ ( 1(2), 0(4) ), ( 0(4), 1(6) ) ], 
  [ ( 1(2), 0(4) ), ( 0(4), 3(6) ) ], [ ( 1(2), 0(4) ), ( 0(4), 5(6) ) ], 
  [ ( 0(2), 1(4) ), ( 1(4), 2(6) ) ], [ ( 0(2), 1(4) ), ( 1(4), 4(6) ) ], 
  [ ( 0(2), 1(4) ), ( 1(4), 0(6) ) ], [ ( 0(2), 3(4) ), ( 3(4), 4(6) ) ], 
  [ ( 0(2), 3(4) ), ( 3(4), 2(6) ) ], [ ( 0(2), 3(4) ), ( 3(4), 0(6) ) ], 
  [ ( 1(2), 2(6) ), ( 3(4), 2(6) ) ], [ ( 1(2), 2(6) ), ( 1(4), 2(6) ) ], 
  [ ( 1(2), 4(6) ), ( 3(4), 4(6) ) ], [ ( 1(2), 4(6) ), ( 1(4), 4(6) ) ], 
  [ ( 1(2), 0(6) ), ( 1(4), 0(6) ) ], [ ( 1(2), 0(6) ), ( 3(4), 0(6) ) ], 
  [ ( 0(2), 1(6) ), ( 2(4), 1(6) ) ], [ ( 0(2), 1(6) ), ( 0(4), 1(6) ) ], 
  [ ( 0(2), 3(6) ), ( 2(4), 3(6) ) ], [ ( 0(2), 3(6) ), ( 0(4), 3(6) ) ], 
  [ ( 0(2), 5(6) ), ( 2(4), 5(6) ) ], [ ( 0(2), 5(6) ), ( 0(4), 5(6) ) ] 
 ]

generated by GAPDoc2HTML