main.toc

\contentsline {chapter}{\numberline {1}\leavevmode {\color {Chapter }About the RCWA Package}}{5}{chapter.1}
\contentsline {chapter}{\numberline {2}\leavevmode {\color {Chapter }Residue-Class-Wise Affine Mappings}}{7}{chapter.2}
\contentsline {section}{\numberline {2.1}\leavevmode {\color {Chapter }Basic definitions}}{7}{section.2.1}
\contentsline {section}{\numberline {2.2}\leavevmode {\color {Chapter }Entering residue-class-wise affine mappings}}{8}{section.2.2}
\contentsline {subsection}{\numberline {2.2.1}\leavevmode {\color {Chapter }ClassShift (r, m)}}{9}{subsection.2.2.1}
\contentsline {subsection}{\numberline {2.2.2}\leavevmode {\color {Chapter }ClassReflection (r, m)}}{9}{subsection.2.2.2}
\contentsline {subsection}{\numberline {2.2.3}\leavevmode {\color {Chapter }ClassTransposition (r1, m1, r2, m2)}}{10}{subsection.2.2.3}
\contentsline {subsection}{\numberline {2.2.4}\leavevmode {\color {Chapter }ClassRotation (r, m, u)}}{11}{subsection.2.2.4}
\contentsline {subsection}{\numberline {2.2.5}\leavevmode {\color {Chapter } RcwaMapping (the general constructor) }}{12}{subsection.2.2.5}
\contentsline {subsection}{\numberline {2.2.6}\leavevmode {\color {Chapter }LocalizedRcwaMapping (for an rcwa mapping of Z and a prime)}}{13}{subsection.2.2.6}
\contentsline {section}{\numberline {2.3}\leavevmode {\color {Chapter }Basic arithmetic for residue-class-wise affine mappings}}{14}{section.2.3}
\contentsline {section}{\numberline {2.4}\leavevmode {\color {Chapter } Attributes and properties of residue-class-wise affine mappings }}{16}{section.2.4}
\contentsline {subsection}{\numberline {2.4.1}\leavevmode {\color {Chapter }LargestSourcesOfAffineMappings (for an rcwa mapping)}}{17}{subsection.2.4.1}
\contentsline {subsection}{\numberline {2.4.2}\leavevmode {\color {Chapter }FixedPointsOfAffinePartialMappings (for an rcwa mapping)}}{18}{subsection.2.4.2}
\contentsline {subsection}{\numberline {2.4.3}\leavevmode {\color {Chapter }Multpk (for an rcwa mapping, a prime and an exponent)}}{18}{subsection.2.4.3}
\contentsline {subsection}{\numberline {2.4.4}\leavevmode {\color {Chapter }Determinant (of an rcwa mapping of Z)}}{19}{subsection.2.4.4}
\contentsline {subsection}{\numberline {2.4.5}\leavevmode {\color {Chapter }Sign (of an rcwa permutation of Z)}}{19}{subsection.2.4.5}
\contentsline {section}{\numberline {2.5}\leavevmode {\color {Chapter }Factoring residue-class-wise affine permutations}}{20}{section.2.5}
\contentsline {subsection}{\numberline {2.5.1}\leavevmode {\color {Chapter }FactorizationIntoCSCRCT (for an rcwa permutation of Z)}}{20}{subsection.2.5.1}
\contentsline {subsection}{\numberline {2.5.2}\leavevmode {\color {Chapter }PrimeSwitch (p)}}{21}{subsection.2.5.2}
\contentsline {subsection}{\numberline {2.5.3}\leavevmode {\color {Chapter }mKnot (for an odd integer)}}{22}{subsection.2.5.3}
\contentsline {section}{\numberline {2.6}\leavevmode {\color {Chapter } Extracting roots of residue-class-wise affine mappings }}{23}{section.2.6}
\contentsline {subsection}{\numberline {2.6.1}\leavevmode {\color {Chapter }Root (k-th root of an rcwa mapping)}}{23}{subsection.2.6.1}
\contentsline {section}{\numberline {2.7}\leavevmode {\color {Chapter } Special functions for non-bijective mappings }}{23}{section.2.7}
\contentsline {subsection}{\numberline {2.7.1}\leavevmode {\color {Chapter }RightInverse (of an injective rcwa mapping)}}{23}{subsection.2.7.1}
\contentsline {subsection}{\numberline {2.7.2}\leavevmode {\color {Chapter }CommonRightInverse (of two injective rcwa mappings)}}{23}{subsection.2.7.2}
\contentsline {subsection}{\numberline {2.7.3}\leavevmode {\color {Chapter }ImageDensity (of an rcwa mapping)}}{24}{subsection.2.7.3}
\contentsline {section}{\numberline {2.8}\leavevmode {\color {Chapter } On trajectories and cycles of residue-class-wise affine mappings }}{24}{section.2.8}
\contentsline {subsection}{\numberline {2.8.1}\leavevmode {\color {Chapter } Trajectory (methods for rcwa mappings) }}{24}{subsection.2.8.1}
\contentsline {subsection}{\numberline {2.8.2}\leavevmode {\color {Chapter } Trajectory (methods for rcwa mappings -- ``accumulated coefficients'') }}{25}{subsection.2.8.2}
\contentsline {subsection}{\numberline {2.8.3}\leavevmode {\color {Chapter } IncreasingOn \& DecreasingOn (for an rcwa mapping) }}{25}{subsection.2.8.3}
\contentsline {subsection}{\numberline {2.8.4}\leavevmode {\color {Chapter }TransitionGraph (for an rcwa mapping and a modulus)}}{26}{subsection.2.8.4}
\contentsline {subsection}{\numberline {2.8.5}\leavevmode {\color {Chapter }OrbitsModulo (for an rcwa mapping and a modulus)}}{26}{subsection.2.8.5}
\contentsline {subsection}{\numberline {2.8.6}\leavevmode {\color {Chapter }FactorizationOnConnectedComponents (for an rcwa mapping and a modulus)}}{26}{subsection.2.8.6}
\contentsline {subsection}{\numberline {2.8.7}\leavevmode {\color {Chapter }TransitionMatrix (for an rcwa mapping and a modulus)}}{27}{subsection.2.8.7}
\contentsline {subsection}{\numberline {2.8.8}\leavevmode {\color {Chapter } Sources \& Sinks (of an rcwa mapping) }}{27}{subsection.2.8.8}
\contentsline {subsection}{\numberline {2.8.9}\leavevmode {\color {Chapter }Loops (of an rcwa mapping)}}{28}{subsection.2.8.9}
\contentsline {subsection}{\numberline {2.8.10}\leavevmode {\color {Chapter }GluckTaylorInvariant (of a trajectory)}}{28}{subsection.2.8.10}
\contentsline {subsection}{\numberline {2.8.11}\leavevmode {\color {Chapter }LikelyContractionCentre (of an rcwa mapping)}}{28}{subsection.2.8.11}
\contentsline {subsection}{\numberline {2.8.12}\leavevmode {\color {Chapter }GuessedDivergence (of an rcwa mapping)}}{29}{subsection.2.8.12}
\contentsline {section}{\numberline {2.9}\leavevmode {\color {Chapter } Saving memory -- the sparse representation of rcwa mappings }}{29}{section.2.9}
\contentsline {subsection}{\numberline {2.9.1}\leavevmode {\color {Chapter }SparseRepresentation (of an rcwa mapping)}}{30}{subsection.2.9.1}
\contentsline {section}{\numberline {2.10}\leavevmode {\color {Chapter }The categories and families of rcwa mappings}}{31}{section.2.10}
\contentsline {subsection}{\numberline {2.10.1}\leavevmode {\color {Chapter }IsRcwaMapping}}{31}{subsection.2.10.1}
\contentsline {subsection}{\numberline {2.10.2}\leavevmode {\color {Chapter }RcwaMappingsFamily (of a ring)}}{31}{subsection.2.10.2}
\contentsline {chapter}{\numberline {3}\leavevmode {\color {Chapter }Residue-Class-Wise Affine Groups}}{32}{chapter.3}
\contentsline {section}{\numberline {3.1}\leavevmode {\color {Chapter }Constructing residue-class-wise affine groups}}{32}{section.3.1}
\contentsline {subsection}{\numberline {3.1.1}\leavevmode {\color {Chapter }IsomorphismRcwaGroup (for a group, over a given ring)}}{32}{subsection.3.1.1}
\contentsline {subsection}{\numberline {3.1.2}\leavevmode {\color {Chapter }DirectProduct (for rcwa groups over Z)}}{33}{subsection.3.1.2}
\contentsline {subsection}{\numberline {3.1.3}\leavevmode {\color {Chapter } WreathProduct (for an rcwa group over Z, with a permutation group or ({\ensuremath {\mathbb Z}},+)) }}{33}{subsection.3.1.3}
\contentsline {subsection}{\numberline {3.1.4}\leavevmode {\color {Chapter }MergerExtension (for finite permutation groups)}}{34}{subsection.3.1.4}
\contentsline {subsection}{\numberline {3.1.5}\leavevmode {\color {Chapter }GroupByResidueClasses (the group `permuting a given list of residue classes')}}{35}{subsection.3.1.5}
\contentsline {subsection}{\numberline {3.1.6}\leavevmode {\color {Chapter } Restriction (of an rcwa mapping or -group, by an injective rcwa mapping) }}{35}{subsection.3.1.6}
\contentsline {subsection}{\numberline {3.1.7}\leavevmode {\color {Chapter } Induction (of an rcwa mapping or -group, by an injective rcwa mapping) }}{36}{subsection.3.1.7}
\contentsline {subsection}{\numberline {3.1.8}\leavevmode {\color {Chapter }RCWA (the group formed by all rcwa permutations of a ring)}}{37}{subsection.3.1.8}
\contentsline {subsection}{\numberline {3.1.9}\leavevmode {\color {Chapter }CT (the group generated by all class transpositions of a ring)}}{37}{subsection.3.1.9}
\contentsline {section}{\numberline {3.2}\leavevmode {\color {Chapter } Basic routines for investigating residue-class-wise affine groups }}{38}{section.3.2}
\contentsline {subsection}{\numberline {3.2.1}\leavevmode {\color {Chapter }StructureDescription (for an rcwa group)}}{38}{subsection.3.2.1}
\contentsline {subsection}{\numberline {3.2.2}\leavevmode {\color {Chapter }EpimorphismFromFpGroup (for an rcwa group and a search radius)}}{42}{subsection.3.2.2}
\contentsline {subsection}{\numberline {3.2.3}\leavevmode {\color {Chapter }PreImagesRepresentative (for an epi. from a free group to an rcwa group)}}{42}{subsection.3.2.3}
\contentsline {section}{\numberline {3.3}\leavevmode {\color {Chapter } The natural action of an rcwa group on the underlying ring }}{43}{section.3.3}
\contentsline {subsection}{\numberline {3.3.1}\leavevmode {\color {Chapter } Orbit (for an rcwa group and either a point or a set) }}{45}{subsection.3.3.1}
\contentsline {subsection}{\numberline {3.3.2}\leavevmode {\color {Chapter }GrowthFunctionOfOrbit (for an rcwa group, a point and bounds on radius and sphere size)}}{46}{subsection.3.3.2}
\contentsline {subsection}{\numberline {3.3.3}\leavevmode {\color {Chapter }DrawOrbitPicture (G, p0, bound, h, w, colored, palette, filename)}}{47}{subsection.3.3.3}
\contentsline {subsection}{\numberline {3.3.4}\leavevmode {\color {Chapter } ShortOrbits (for rcwa groups) \& ShortCycles (for rcwa permutations) }}{47}{subsection.3.3.4}
\contentsline {subsection}{\numberline {3.3.5}\leavevmode {\color {Chapter } ShortResidueClassOrbits \& ShortResidueClassCycles }}{48}{subsection.3.3.5}
\contentsline {subsection}{\numberline {3.3.6}\leavevmode {\color {Chapter }ComputeCycleLength (for an rcwa permutation and a point)}}{49}{subsection.3.3.6}
\contentsline {subsection}{\numberline {3.3.7}\leavevmode {\color {Chapter }CycleRepresentativesAndLengths (for rcwa permutation and set of seed points)}}{50}{subsection.3.3.7}
\contentsline {subsection}{\numberline {3.3.8}\leavevmode {\color {Chapter }FixedResidueClasses (for rcwa mapping and bound on modulus)}}{50}{subsection.3.3.8}
\contentsline {subsection}{\numberline {3.3.9}\leavevmode {\color {Chapter } Ball (for group, element and radius or group, point, radius and action) }}{51}{subsection.3.3.9}
\contentsline {subsection}{\numberline {3.3.10}\leavevmode {\color {Chapter }RepresentativeAction (G, source, destination, action)}}{52}{subsection.3.3.10}
\contentsline {subsection}{\numberline {3.3.11}\leavevmode {\color {Chapter }ProjectionsToInvariantUnionsOfResidueClasses (for rcwa group and modulus)}}{53}{subsection.3.3.11}
\contentsline {subsection}{\numberline {3.3.12}\leavevmode {\color {Chapter }RepresentativeAction (for RCWA(R) and 2 partitions of R into residue classes)}}{53}{subsection.3.3.12}
\contentsline {subsection}{\numberline {3.3.13}\leavevmode {\color {Chapter }CollatzLikeMappingByOrbitTree (for rcwa group, root point and range of radii)}}{54}{subsection.3.3.13}
\contentsline {section}{\numberline {3.4}\leavevmode {\color {Chapter } Special attributes of tame residue-class-wise affine groups }}{55}{section.3.4}
\contentsline {subsection}{\numberline {3.4.1}\leavevmode {\color {Chapter } RespectedPartition (of a tame rcwa group or -permutation) }}{55}{subsection.3.4.1}
\contentsline {subsection}{\numberline {3.4.2}\leavevmode {\color {Chapter } ActionOnRespectedPartition \& KernelOfActionOnRespectedPartition }}{56}{subsection.3.4.2}
\contentsline {section}{\numberline {3.5}\leavevmode {\color {Chapter }Generating pseudo-random elements of RCWA(R) and CT(R)}}{57}{section.3.5}
\contentsline {section}{\numberline {3.6}\leavevmode {\color {Chapter }The categories of residue-class-wise affine groups}}{58}{section.3.6}
\contentsline {subsection}{\numberline {3.6.1}\leavevmode {\color {Chapter }IsRcwaGroup}}{58}{subsection.3.6.1}
\contentsline {chapter}{\numberline {4}\leavevmode {\color {Chapter }Residue-Class-Wise Affine Monoids}}{59}{chapter.4}
\contentsline {section}{\numberline {4.1}\leavevmode {\color {Chapter }Constructing residue-class-wise affine monoids}}{59}{section.4.1}
\contentsline {subsection}{\numberline {4.1.1}\leavevmode {\color {Chapter }Rcwa (the monoid formed by all rcwa mappings of a ring)}}{60}{subsection.4.1.1}
\contentsline {section}{\numberline {4.2}\leavevmode {\color {Chapter }Computing with residue-class-wise affine monoids}}{60}{section.4.2}
\contentsline {subsection}{\numberline {4.2.1}\leavevmode {\color {Chapter }ShortOrbits (for rcwa monoid, set of points and bound on length)}}{61}{subsection.4.2.1}
\contentsline {subsection}{\numberline {4.2.2}\leavevmode {\color {Chapter } Ball (for monoid, element and radius or monoid, point, radius and action) }}{62}{subsection.4.2.2}
\contentsline {chapter}{\numberline {5}\leavevmode {\color {Chapter } Residue-Class-Wise Affine Mappings, Groups and Monoids over ${\ensuremath {\mathbb Z}}^2$ }}{63}{chapter.5}
\contentsline {section}{\numberline {5.1}\leavevmode {\color {Chapter } The definition of residue-class-wise affine mappings of ${\ensuremath {\mathbb Z}}^d$ }}{63}{section.5.1}
\contentsline {section}{\numberline {5.2}\leavevmode {\color {Chapter } Entering residue-class-wise affine mappings of ${\ensuremath {\mathbb Z}}^2$ }}{64}{section.5.2}
\contentsline {subsection}{\numberline {5.2.1}\leavevmode {\color {Chapter } RcwaMapping (the general constructor; methods for ${\ensuremath {\mathbb Z}}^2$) }}{64}{subsection.5.2.1}
\contentsline {subsection}{\numberline {5.2.2}\leavevmode {\color {Chapter } ClassTransposition (for ${\ensuremath {\mathbb Z}}^2$) }}{66}{subsection.5.2.2}
\contentsline {subsection}{\numberline {5.2.3}\leavevmode {\color {Chapter } ClassRotation (for ${\ensuremath {\mathbb Z}}^2$) }}{67}{subsection.5.2.3}
\contentsline {subsection}{\numberline {5.2.4}\leavevmode {\color {Chapter } ClassShift (for ${\ensuremath {\mathbb Z}}^2$) }}{68}{subsection.5.2.4}
\contentsline {section}{\numberline {5.3}\leavevmode {\color {Chapter } Methods for residue-class-wise affine mappings of ${\ensuremath {\mathbb Z}}^2$ }}{68}{section.5.3}
\contentsline {subsection}{\numberline {5.3.1}\leavevmode {\color {Chapter }ProjectionsToCoordinates (for an rcwa mapping of Z x Z)}}{69}{subsection.5.3.1}
\contentsline {section}{\numberline {5.4}\leavevmode {\color {Chapter } Methods for residue-class-wise affine groups and -monoids over ${\ensuremath {\mathbb Z}}^2$ }}{70}{section.5.4}
\contentsline {subsection}{\numberline {5.4.1}\leavevmode {\color {Chapter } IsomorphismRcwaGroup (Embeddings of SL(2,{\ensuremath {\mathbb Z}}) and GL(2,{\ensuremath {\mathbb Z}})) }}{70}{subsection.5.4.1}
\contentsline {subsection}{\numberline {5.4.2}\leavevmode {\color {Chapter } DrawGrid }}{71}{subsection.5.4.2}
\contentsline {chapter}{\numberline {6}\leavevmode {\color {Chapter } Databases of Residue-Class-Wise Affine Groups and -Mappings }}{72}{chapter.6}
\contentsline {section}{\numberline {6.1}\leavevmode {\color {Chapter }The collection of examples}}{72}{section.6.1}
\contentsline {subsection}{\numberline {6.1.1}\leavevmode {\color {Chapter }LoadRCWAExamples}}{72}{subsection.6.1.1}
\contentsline {section}{\numberline {6.2}\leavevmode {\color {Chapter }Databases of rcwa groups}}{73}{section.6.2}
\contentsline {subsection}{\numberline {6.2.1}\leavevmode {\color {Chapter }LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions (small database)}}{73}{subsection.6.2.1}
\contentsline {subsection}{\numberline {6.2.2}\leavevmode {\color {Chapter }LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions (both databases)}}{76}{subsection.6.2.2}
\contentsline {subsection}{\numberline {6.2.3}\leavevmode {\color {Chapter }LoadDatabaseOfGroupsGeneratedBy4ClassTranspositions}}{77}{subsection.6.2.3}
\contentsline {section}{\numberline {6.3}\leavevmode {\color {Chapter }Databases of rcwa mappings}}{79}{section.6.3}
\contentsline {subsection}{\numberline {6.3.1}\leavevmode {\color {Chapter }LoadDatabaseOfProductsOf2ClassTranspositions}}{79}{subsection.6.3.1}
\contentsline {subsection}{\numberline {6.3.2}\leavevmode {\color {Chapter }LoadDatabaseOfNonbalancedProductsOfClassTranspositions}}{79}{subsection.6.3.2}
\contentsline {chapter}{\numberline {7}\leavevmode {\color {Chapter }Examples}}{81}{chapter.7}
\contentsline {section}{\numberline {7.1}\leavevmode {\color {Chapter } Thompson's group V }}{81}{section.7.1}
\contentsline {section}{\numberline {7.2}\leavevmode {\color {Chapter } Factoring Collatz' permutation of the integers }}{84}{section.7.2}
\contentsline {section}{\numberline {7.3}\leavevmode {\color {Chapter } The $3n+1$ group }}{86}{section.7.3}
\contentsline {section}{\numberline {7.4}\leavevmode {\color {Chapter } A group with huge finite orbits }}{93}{section.7.4}
\contentsline {section}{\numberline {7.5}\leavevmode {\color {Chapter } A group which acts 4-transitively on the positive integers }}{97}{section.7.5}
\contentsline {section}{\numberline {7.6}\leavevmode {\color {Chapter } A group which acts 3-transitively, but not 4-transitively on {\ensuremath {\mathbb Z}} }}{105}{section.7.6}
\contentsline {section}{\numberline {7.7}\leavevmode {\color {Chapter } An rcwa mapping which seems to be contracting, but very slow }}{108}{section.7.7}
\contentsline {section}{\numberline {7.8}\leavevmode {\color {Chapter }Checking a result by P. Andaloro}}{110}{section.7.8}
\contentsline {section}{\numberline {7.9}\leavevmode {\color {Chapter }Two examples by Matthews and Leigh}}{111}{section.7.9}
\contentsline {section}{\numberline {7.10}\leavevmode {\color {Chapter }Orders of commutators}}{113}{section.7.10}
\contentsline {section}{\numberline {7.11}\leavevmode {\color {Chapter } An infinite subgroup of CT(GF(2)[x]) with many torsion elements }}{114}{section.7.11}
\contentsline {section}{\numberline {7.12}\leavevmode {\color {Chapter }An abelian rcwa group over a polynomial ring}}{117}{section.7.12}
\contentsline {section}{\numberline {7.13}\leavevmode {\color {Chapter }Checking for solvability}}{118}{section.7.13}
\contentsline {section}{\numberline {7.14}\leavevmode {\color {Chapter }Some examples over (semi)localizations of the integers}}{119}{section.7.14}
\contentsline {section}{\numberline {7.15}\leavevmode {\color {Chapter } Twisting 257-cycles into an rcwa mapping with modulus 32 }}{122}{section.7.15}
\contentsline {section}{\numberline {7.16}\leavevmode {\color {Chapter } The behaviour of the moduli of powers }}{123}{section.7.16}
\contentsline {section}{\numberline {7.17}\leavevmode {\color {Chapter } Images and preimages under the Collatz mapping }}{125}{section.7.17}
\contentsline {section}{\numberline {7.18}\leavevmode {\color {Chapter } An extension of the Collatz mapping T to a permutation of ${\ensuremath {\mathbb Z}}^2$ }}{126}{section.7.18}
\contentsline {section}{\numberline {7.19}\leavevmode {\color {Chapter } Finite quotients of Grigorchuk groups }}{129}{section.7.19}
\contentsline {section}{\numberline {7.20}\leavevmode {\color {Chapter } Forward orbits of a monoid with 2 generators }}{131}{section.7.20}
\contentsline {section}{\numberline {7.21}\leavevmode {\color {Chapter } The free group of rank 2 and the modular group PSL(2,{\ensuremath {\mathbb Z}}) }}{132}{section.7.21}
\contentsline {chapter}{\numberline {8}\leavevmode {\color {Chapter }The Algorithms Implemented in RCWA}}{135}{chapter.8}
\contentsline {chapter}{\numberline {9}\leavevmode {\color {Chapter }Installation and Auxiliary Functions}}{150}{chapter.9}
\contentsline {section}{\numberline {9.1}\leavevmode {\color {Chapter }Requirements}}{150}{section.9.1}
\contentsline {section}{\numberline {9.2}\leavevmode {\color {Chapter }Installation}}{150}{section.9.2}
\contentsline {section}{\numberline {9.3}\leavevmode {\color {Chapter }Building the manual}}{150}{section.9.3}
\contentsline {subsection}{\numberline {9.3.1}\leavevmode {\color {Chapter }RCWABuildManual}}{150}{subsection.9.3.1}
\contentsline {section}{\numberline {9.4}\leavevmode {\color {Chapter }The testing routines}}{150}{section.9.4}
\contentsline {subsection}{\numberline {9.4.1}\leavevmode {\color {Chapter }RCWATestInstall}}{150}{subsection.9.4.1}
\contentsline {subsection}{\numberline {9.4.2}\leavevmode {\color {Chapter }RCWATestAll}}{151}{subsection.9.4.2}
\contentsline {subsection}{\numberline {9.4.3}\leavevmode {\color {Chapter }RCWATestExamples}}{151}{subsection.9.4.3}
\contentsline {section}{\numberline {9.5}\leavevmode {\color {Chapter }The Info class of the package}}{151}{section.9.5}
\contentsline {subsection}{\numberline {9.5.1}\leavevmode {\color {Chapter }InfoRCWA}}{151}{subsection.9.5.1}
\contentsline {chapter}{References}{153}{chapter*.5}
\contentsline {chapter}{Index}{154}{section*.6}