chap6.txt

  
  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
  
  LoadRCWAExamples(  )  function
  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.
  
    Example  
    
    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
  
  LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions(  )  function
  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.
  
    Example  
    
    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
  
  LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions( max_m )  function
  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.
  
    Example  
    
    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
  
  LoadDatabaseOfGroupsGeneratedBy4ClassTranspositions(  )  function
  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.
  
    Example  
    
    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
  
  LoadDatabaseOfProductsOf2ClassTranspositions(  )  function
  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.
  
    Example  
    
    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
  
  LoadDatabaseOfNonbalancedProductsOfClassTranspositions(  )  function
  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.
  
    Example  
    
    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) ) ] 
     ]