This chapter lists brief descriptions of the algorithms and methods implemented in this package. These descriptions are kept very informal and terse, and some of them provide only rudimentary information. They are listed in alphabetical order. The word "trivial" as a description means that essentially nothing is done except of performing I/O operations, storing or recalling one or several values or doing very basic computations, and "straightforward" means that no sophisticated algorithm is used. Note that "trivial" and "straightforward" are to be read as mathematically trivial respectively straightforward, and that the code of a function or method attributed in this way can still be reasonably long and complicated. Longer and better descriptions of some of the algorithms and methods can be found in [Koh08].
ActionOnRespectedPartition(G)
"Straightforward" after having computed a respected partition by RespectedPartition.
AllElementsOfCTZWithGivenModulus(m)
This function first determines a list of all unordered partitions \(\mathcal{P}\) of ℤ into m residue classes. Then for any such partition \(\mathcal{P}\) it runs a loop over the elements of the symmetric group of degree m. For any \(\sigma \in {\rm S}_m\) and any partition \(\mathcal{P}\) it constructs the element of \({\rm CT}(\mathbb{Z})\) with modulus dividing \(m\) which maps the ordered partition \(\{0(m), 1(m), \dots, m-1(m)\}\) to the ordered partition obtained from \(\mathcal{P}\) by permuting the residue classes with \(\sigma\). Finally it discards the elements whose modulus is a proper divisor of m, and returns the "rest".
Ball(G,g,r)
"Straightforward".
Ball(G,p,r,act)
"Straightforward".
ClassPairs(m)
Runs a loop over all 4-tuples of nonnegative integers less than m, and filters by congruence criteria and ordering of the entries.
ClassReflection(r,m)
"Trivial".
ClassRotation(r,m,u)
"Trivial".
ClassShift(r,m)
"Trivial".
ClassTransposition(r1,m1,r2,m2)
"Trivial".
ClassWiseOrderPreservingOn(f), etc.
Forms the union of the residue classes modulo the modulus of f in whose corresponding coefficient triple the first entry is positive, zero or negative, respectively.
Coefficients(f)
"Trivial".
CommonRightInverse(l,r)
See RightInverse.
CT(R)
Attributes and properties are set according to [Koh10].
CycleRepresentativesAndLengths(g,S)
"Straightforward".
CyclesOnFiniteOrbit(G,g,n)
"Straightforward".
DecreasingOn(f)
Forms the union of the residue classes which are determined by the coefficients as indicated.
DerivedSubgroup(G)
No genuine method -- GAP Library methods already work for tame groups.
Determinant(g)
Evaluation of the given expression. For the mathematical meaning (epimorphism!), see Theorem 2.11.9 in [Koh05].
DifferencesList(l)
"Trivial".
DirectProduct(G1,G2, ... )
Restricts the groups G1, G2, ... to disjoint residue classes. See Restriction and Corollary 2.3.3 in [Koh05].
Display(f)
"Trivial".
DistanceToNextSmallerPointInOrbit(G,n)
"Straightforward" -- computes balls of radius \(r\) about n for \(r = 1, 2, \dots\) until a point smaller than \(n\) is found.
Divisor(f)
Lcm of coefficients, as indicated.
DrawGrid(U,range_y,range_x,filename)
"Straightforward".
DrawOrbitPicture
Compute spheres of radius \(1, \dots, r\) around the given point(s). Choose the origin either in the lower left corner of the picture (if all points lie in the first quadrant) or in the middle of the picture (if they don't). Mark points of the ball with black pixels in case of a monochrome picture. Choose colors from the given palette depending on the distance from the starting points in case of a colored picture.
EpimorphismFromFpGroup(G,r)
Computes orders of elements in the ball of radius r about 1 in G, and uses the corresponding relations if they affect the abelian invariants of G, G', G'', etc..
Exponent(G)
Check whether G is finite. If it is, then use the GAP Library method, applied to Image(IsomorphismPermGroup(G)). Check whether G is tame. If yes, return infinity. If not, run a loop over G until finding an element of infinite order. Once one is found, return infinity.
The final loop to find a non-torsion element can be left away under the assumption that any finitely generated wild rcwa group has a wild element. It looks likely that this holds, but currently the author does not know a proof.
ExtRepOfObj(f)
"Trivial".
FactorizationIntoCSCRCT(g),
Factorization(g)
The method used here is rather sophisticated, and will likely some time be published elsewhere. At the moment termination is not guaranteed, but in case of termination the result is certain. The strategy is roughly first to make the mapping class-wise order-preserving and balanced, and then to remove all prime factors from multiplier and divisor one after the other in decreasing order by dividing by appropriate class transpositions. The remaining integral mapping can be factored in a similar way as a permutation of a finite set can be factored into transpositions.
FactorizationOnConnectedComponents(f,m)
Calls GRAPE to get the connected components of the transition graph, and then computes a partition of the suitably "blown up" coefficient list corresponding to the connected components.
FixedPointsOfAffinePartialMappings(f)
"Straightforward".
FixedResidueClasses(g,maxmod),
FixedResidueClasses(G,maxmod)
Runs a loop over all moduli \(m \leq\) maxmod and all residues \(r\) modulo these moduli, and selects those residue classes \(r(m)\) which are mapped to itself by g, respectively, by all generators of G.
FloatQuotientsList(l)
"Trivial".
GluckTaylorInvariant(a)
Evaluation of the given expression.
GroupByResidueClasses(classes)
Finds all pairs of residue classes in the list classes which are disjoint, forms the corresponding class transpositions and returns the group generated by them.
GuessedDivergence(f)
Numerical computation of the limit of some series, which seems to converge "often". Caution!!!
Image(f), Image(f,S)
"Straightforward" if one can compute images of residue classes under affine mappings and unite and intersect residue classes (Chinese Remainder Theorem). See Lemma 1.2.1 in [Koh05].
ImageDensity(f)
Evaluation of the given expression.
g in G (membership test for rcwa groups)
Test whether the mapping g or its inverse is in the list of generators of G. If it is, return true. Test whether its prime set is a subset of the prime set of G. If not, return false. Test whether the multiplier or the divisor of g has a prime factor which does not divide the multiplier of G. If yes, return false. Test if G is class-wise order-preserving, and g is not. If so, return false. Test if the sign of g is -1 and all generators of G have sign 1. If yes, return false. Test if G is class-wise order-preserving, all generators of G have determinant 0 and g has determinant \(\neq 0\). If yes, return false. Test whether the support of g is a subset of the support of G. If not, return false. Test whether G fixes the nonnegative integers setwise, but g does not. If yes, return false.
If G is tame, proceed as follows: Test whether the modulus of g divides the modulus of G. If not, return false. Test whether G is finite and g has infinite order. If so, return false. Test whether g is tame. If not, return false. Compute a respected partition P of G and the finite permutation group H induced by G on it (see RespectedPartition). Check whether g permutes P. If not, return false. Let h be the permutation induced by g on P. Check whether h lies in H. If not, return false. Compute an element g1 of G which acts on P like g. For this purpose, factor h into generators of H using PreImagesRepresentative, and compute the corresponding product of generators of G. Let k := g/g1. The mapping k is always integral. Compute the kernel K of the action of G on P using KernelOfActionOnRespectedPartition. Check whether k lies in K. This is done using the package Polycyclic [EHN13], and uses an isomorphism from a supergroup of K which is isomorphic to the |P|-fold direct product of the infinite dihedral group and which always contains k to a polycyclically presented group. If k lies in K, return true, otherwise return false.
If G is not tame, proceed as follows: Look for finite orbits of G. If some are found, test whether g acts on them, and whether the induced permutations lie in the permutation groups induced by G. If for one of the examined orbits one of the latter two questions has a negative answer, then return false. Look for a positive integer \(m\) such that g does not leave a partition of ℤ into unions of residue classes (mod \(m\)) invariant which is fixed by G. If successful, return false. If not, try to factor g into generators of G using PreImagesRepresentative. If successful, return true. If g is in G, this terminates after a finite number of steps. Both run time and memory requirements are exponential in the word length. If g is not in G at this stage, the method runs into an infinite loop.
f in M (membership test for rcwa monoids)
Test whether the mapping f is in the list of generators of G. If it is, return true. Test whether the multiplier of f is zero, but all generators of M have nonzero multiplier. If yes, return false. Test if neither f nor any generator of M has multiplier zero. If so, check whether the prime set of f is a subset of the prime set of M, and whether the set of prime factors of the multiplier of f is a subset of the union of the sets of prime factors of the multipliers of the generators of M. If one of these is not the case, return false. Check whether the set of prime factors of the divisor of f is a subset of the union of the sets of prime factors of the divisors of the generators of M. If not, return false. If the underlying ring is ℤ or a semilocalization thereof, then check whether f is not class-wise order-preserving, but M is. If so, return false.
If f is not injective, but all generators of M are, then return false. If f is not surjective, but all generators of M are, then return false. If the support of f is not a subset of the support of M, then return false. If f is not sign-preserving, but M is, then return false. Check whether M is tame. If so, then return false provided that one of the following three conditions hold: 1. The modulus of f does not divide the modulus of M. 2. f is not tame. 3. M is finite, and f is bijective and has infinite order. If membership has still not been decided, use ShortOrbits to look for finite orbits of M, and check whether f fixes all of them setwise. If a finite orbit is found which f does not map to itself, then return false.
Finally compute balls of increasing radius around 1 until f is found to lie in one of them. If that happens, return true. If f is an element of M, this will eventually terminate, but if at this stage f is not an element of M, this will run into an infinite loop.
point in orbit (membership test for orbits)
Uses the equality test for orbits: The orbit equality test computes balls of increasing radius around the orbit representatives until they intersect non-trivially. Once they do so, it returns true. If it finds that one or both of the orbits are finite, it makes use of that information, and returns false if appropriate. In between, i.e. after having computed balls to a certain extent depending on the properties of the group, it chooses a suitable modulus \(m\) and computes orbits (modulo \(m\)). If the representatives of the orbits to be compared belong to different orbits (mod \(m\)), it returns false. If this is not the case although the orbits are different, the equality test runs into an infinite loop.
IncreasingOn(f)
Forms the union of the residue classes which are determined by the coefficients as indicated.
Index(G,H)
In general, i.e. if the underlying ring is not ℤ, proceed as follows: If both groups G and H are finite, return the quotient of their orders. If G is infinite, but H is finite, return infinity. Otherwise return the number of right cosets of H in G, computed by the GAP Library function RightCosets.
If the underlying ring is ℤ, do additionally the following before attempting to compute the list of right cosets: If the group G is class-wise order-preserving, check whether one of its generators has nonzero determinant, and whether all generators of H have determinant zero. If so, then return infinity. Check whether H is tame, but G is not. If so, then return infinity. If G is tame, then check whether the rank of the largest free abelian subgroup of the kernel of the action of G on a respected partition is higher than the corresponding rank for H. For this check, use RankOfKernelOfActionOnRespectedPartition. If it is, then return infinity.
Induction(g,f)
Computes f * g * RightInverse(f).
Induction(G,f)
Gets a set of generators by applying Induction(g,f) to the generators g of G.
InjectiveAsMappingFrom(f)
The function starts with the entire source of f as "preimage" pre and the empty set as "image" im. It loops over the residue classes (mod Mod(f)). For any such residue class cl the following is done: Firstly, the image of cl under f is added to im. Secondly, the intersection of the preimage of the intersection of the image of cl under f and im under f and cl is subtracted from pre.
IntegralConjugate(f),
IntegralConjugate(G)
Uses the algorithm described in the proof of Theorem 2.5.14 in [Koh05].
IntegralizingConjugator(f),
IntegralizingConjugator(G)
Uses the algorithm described in the proof of Theorem 2.5.14 in [Koh05].
Inverse(f)
Essentially inversion of affine mappings. See Lemma 1.3.1, Part (b) in [Koh05].
IsBalanced(f)
Checks whether the sets of prime factors of the multiplier and the divisor of f are the same.
IsBijective(f)
"Trivial", respectively, see IsInjective and IsSurjective.
IsClassReflection(g)
Computes the support of g, and compares g with the corresponding class reflection.
IsClassRotation(g)
Computes the support of g, extracts the possible rotation factor from the coefficients and compares g with the corresponding class rotation.
IsClassShift(g)
Computes the support of g, and compares g with the corresponding class shift.
IsClassTransposition(g),
IsGeneralizedClassTransposition(g)
Computes the support of g, writes it as a disjoint union of two residue classes and compares g with the class transposition which interchanges them.
IsClassWiseOrderPreserving(f),
IsClassWiseTranslating(f)
"Trivial".
IsConjugate(RCWA(Integers),f,g)
Test whether f and g have the same order, and whether either both or none of them is tame. If not, return false.
If the mappings are wild, use ShortCycles to search for finite cycles not belonging to an infinite series, until their numbers for a particular length differ. This may run into an infinite loop. If it terminates, return false.
If the mappings are tame, use the method described in the proof of Theorem 2.5.14 in [Koh05] to construct integral conjugates of f and g. Then essentially use the algorithm described in the proof of Theorem 2.6.7 in [Koh05] to compute "standard representatives" of the conjugacy classes which the integral conjugates of f and g belong to. Finally compare these standard representatives, and return true if they are equal and false if not.
IsInjective(f)
See Image.
IsIntegral(f)
"Trivial".
IsNaturalCT(G),
IsNaturalRCWA(G)
Only checks a set flag.
IsomorphismMatrixGroup(G)
Uses the algorithm described in the proof of Theorem 2.6.3 in [Koh05].
IsomorphismPermGroup(G)
If the group G is finite and class-wise order-preserving, use ActionOnRespectedPartition. If G is finite, but not class-wise order-preserving, compute the action on the respected partition which is obtained by splitting any residue class \(r(m)\) in RespectedPartition(G) into three residue classes \(r(3m), r+m(3m), r+2m(3m)\). If G is infinite, there is no isomorphism to a finite permutation group, thus return fail.
IsomorphismRcwaGroup(G)
The method for finite groups uses RcwaMapping, Part (d).
The method for free products of finite groups uses the Table-Tennis Lemma (which is also known as Ping-Pong Lemma, cf. e.g. Section II.B. in [dlH00]). It uses regular permutation representations of the factors \(G_r\) (\(r = 0, \dots ,m-1\)) of the free product on residue classes modulo \(n_r := |G_r|\). The basic idea is that since point stabilizers in regular permutation groups are trivial, all non-identity elements map any of the permuted residue classes into their complements. To get into a situation where the Table-Tennis Lemma is applicable, the method computes conjugates of the images of the mentioned permutation representations under rcwa permutations \(\sigma_r\) which satisfy \(0(n_r)^{\sigma_r} = ℤ \setminus r(m)\).
The method for free groups uses an adaptation of the construction given on page 27 in [dlH00] from PSL(2,ℂ) to RCWA(ℤ). As an equivalent for the closed discs used there, the method takes the residue classes modulo two times the rank of the free group.
IsOne(f)
"Trivial".
IsPerfectGroup(G)
If the group G is trivial, then return true. Otherwise if it is abelian, then return false.
If the underlying ring is ℤ, then do the following: If one of the generators of G has sign -1, then return false. If G is class-wise order-preserving and one of the generators has nonzero determinant, then return false.
If G is wild, and perfectness has not been decided so far, then give up. If G is finite, then check the image of IsomorphismPermGroup(G) for perfectness, and return true or false accordingly.
If the group G is tame and if it acts transitively on its stored respected partition, then return true or false depending on whether the finite permutation group ActionOnRespectedPartition(G) is perfect or not. If G does not act transitively on its stored respected partition, then give up.
IsPrimeSwitch(g)
Checks whether the multiplier of g is an odd prime, and compares g with the corresponding prime switch.
IsSignPreserving(f)
If f is not class-wise order-preserving, then return false. Otherwise let \(c \geq 1\) be greater than or equal to the maximum of the absolute values of the coefficients \(b_{r(m)}\) of the affine partial mappings of f, and check whether the minimum of the image of \(\{0, \dots, c\}\) under f is nonnegative and whether the maximum of the image of \(\{-c, \dots, -1\}\) under f is negative. If both is the case, then return true, otherwise return false.
IsSolvableGroup(G)
If G is abelian, then return true. If G is tame, then return true or false depending on whether ActionOnRespectedPartition(G) is solvable or not. If G is wild, then give up.
IsSubset(G,H) (checking for a subgroup relation)
Check whether the set of stored generators of H is a subset of the set of stored generators of G. If so, return true. Check whether the prime set of H is a subset of the prime set of G. If not, return false. Check whether the support of H is a subset of the support of G. If not, return false. Check whether G is tame, but H is wild. If so, return false.
If G and H are both tame, then proceed as follows: If the multiplier of H does not divide the multiplier of G, then return false. If H does not respect the stored respected partition of G, then return false. Check whether the finite permutation group induced by H on RespectedPartition(G) is a subgroup of ActionOnRespectedPartition(G). If yes, return true. Check whether the order of H is greater than the order of G. If so, return false.
Finally use the membership test to check whether all generators of H lie in G, and return true or false accordingly.
IsSurjective(f)
See Image.
IsTame(G)
Checks whether the modulus of the group is nonzero.
IsTame(f)
Application of the criteria given in Corollary 2.5.10 and 2.5.12 and Theorem A.8 and A.11 in [Koh05], as well as of the criteria given in [Koh07a]. The criterion "surjective, but not injective means wild" (Theorem A.8 in [Koh05]) is the subject of [Koh07b]. The package GRAPE is needed for the application of the criterion which says that an rcwa permutation is wild if a transition graph has a weakly-connected component which is not strongly-connected (cf. Theorem A.11 in [Koh05]).
IsTransitive(G,Integers)
Look for finite orbits, using ShortOrbits on a couple of intervals. If a finite orbit is found, return false. Test if G is finite. If yes, return false.
Search for an element g and a residue class \(r(m)\) such that the restriction of g to \(r(m)\) is given by \(n \mapsto n + m\). Then the cyclic group generated by g acts transitively on \(r(m)\). The element g is searched among the generators of G, its powers, its commutators, powers of its commutators and products of few different generators. The search for such an element may run into an infinite loop, as there is no guarantee that the group has a suitable element.
If suitable g and \(r(m)\) are found, proceed as follows:
Put \(S := r(m)\). Put \(S := S \cup S^g\) for all generators \(g\) of G, and repeat this until \(S\) remains constant. This may run into an infinite loop.
If it terminates: If \(S = ℤ\), return true, otherwise return false.
IsTransitiveOnNonnegativeIntegersInSupport(G)
Computes balls about 1 with successively increasing radii, and checks whether the union of the sets where the elements of these balls are decreasing or shifting down equals the support of G. If a positive answer is found, transitivity on "small" points (nonnegative integers less than an explicit bound) is verified.
IsZero(f)
"Trivial".
KernelOfActionOnRespectedPartition(G)
First determine the abelian invariants of the kernel K. For this, compute sufficiently many quotients of orders of permutation groups induced by G on refinements of the stored respected partition P by the order of the permutation group induced by G on P itself. Then use a random walk through the group G. Compute powers of elements encountered along the way which fix P. Translate these kernel elements into elements of a polycyclically presented group isomorphic to the |P|-fold direct product of the infinite dihedral group (K certainly embeds into this group). Use Polycyclic [EHN13] to collect independent "nice" generators of K. Proceed until the permutation groups induced by K on the refined respected partitions all equal the initially stored quotients.
LargestSourcesOfAffineMappings(f)
Forms unions of residue classes modulo the modulus of the mapping, whose corresponding coefficient triples are equal.
LaTeXStringRcwaMapping(f),
LaTeXAndXDVI(f)
Collects residue classes those corresponding coefficient triples are equal.
LikelyContractionCentre(f,maxn,bound)
Computes trajectories with starting values from a given interval, until a cycle is reached. Aborts if the trajectory exceeds the prescribed bound. Form the union of the detected cycles.
LoadDatabaseOf...(), LoadRCWAExamples()
"Trivial". -- These functions do nothing more than reading in certain files.
LocalizedRcwaMapping(f,p)
"Trivial".
Log2HTML(logfilename)
Straightforward string operations.
Loops(f)
Runs over the residue classes modulo the modulus of f, and selects those of them which f does not map to themselves, but which intersect non-trivially with their images under f.
MaximalShift(f)
"Trivial".
MergerExtension(G,points,point)
As described in MergerExtension (3.1-4).
Mirrored(g), Mirrored(G)
Conjugates with \(n \mapsto -n - 1\), as indicated in the definition.
mKnot(m)
"Straightforward", following the definition given in [Kel99].
Modulus(G)
Searches for a wild element in the group. If unsuccessful, tries to construct a respected partition (see RespectedPartition).
Modulus(f)
"Trivial".
MovedPoints(G)
Needs only forming unions of residue classes and determining fixed points of affine mappings.
Multiplier(f)
Lcm of coefficients, as indicated.
Multpk(f,p,k)
Forms the union of the residue classes modulo the modulus of the mapping, which are determined by the given divisibility criteria for the coefficients of the corresponding affine mapping.
NrClassPairs(m)
Relatively straightforward. -- Practical for values of m ranging up into the hundreds and corresponding counts of $10^9$ and more.
NrConjugacyClassesOfCTZOfOrder(ord),
Evaluation of the expression Length(Filtered(Combinations(DivisorsInt(ord)), l -> l <> [] and Lcm(l) = ord)).
NrConjugacyClassesOfRCWAZOfOrder(ord)
The class numbers are taken from Corollary 2.7.1 in [Koh05].
ObjByExtRep(fam,l)
"Trivial".
One(f), One(G),
"Trivial".
Orbit(G,pnt,gens,acts,act)
Check if the orbit has length less than a certain bound. If so, then return it as a list. Otherwise test whether the group G is tame or wild.
If G is tame, then test whether G is finite. If yes, then compute the orbit by the GAP Library method. Otherwise proceed as follows: Compute a respected partition \(\mathcal{P}\) of G. Use \(\mathcal{P}\) to find a residue class \(r(m)\) which is a subset of the orbit to be computed. In general, \(r(m)\) will not be one of the residue classes in \(\mathcal{P}\), but a subset of one of them. Put \(\Omega := r(m)\). Unite the set \(\Omega\) with its images under all the generators of G and their inverses. Repeat that until \(\Omega\) does not change any more. Return \(\Omega\).
If G is wild, then return an orbit object which stores the group G, the representative rep and the action act.
OrbitsModulo(f,m)
Uses GRAPE to compute the connected components of the transition graph.
OrbitsModulo(G,m)
"Straightforward".
Order(f)
Test for IsTame. If the mapping is not tame, then return infinity. Otherwise use Corollary 2.5.10 in [Koh05].
PermutationOpNC(sigma,P,act)
Several different methods for different types of arguments, which either provide straightforward optimizations via computing with coefficients directly, or just delegate to PermutationOp.
PreImage(f,S)
See Image.
PreImagesRepresentative(phi,g),
PreImagesRepresentatives(phi,g)
As described in the documentation of these methods. The underlying idea to successively compute two balls around 1 and g until they intersect non-trivially is standard in computational group theory. For rcwa groups it would mean wasting both memory and run time to actually compute group elements. Thus only images of tuples of points are computed and stored.
PrimeSet(f),
PrimeSet(G)
"Straightforward".
PrimeSwitch(p)
Multiplication of rcwa mappings as indicated.
Print(f)
"Trivial".
f*g
Essentially composition of affine mappings. See Lemma 1.3.1, Part (a) in [Koh05].
ProjectionsToCoordinates(f)
Straightforward coefficient operations.
ProjectionsToInvariantUnionsOfResidueClasses(G,m)
Use OrbitsModulo to determine the supports of the images of the epimorphisms to be determined, and use RestrictedPerm to compute the images of the generators of G under these epimorphisms.
QuotientsList(l)
"Trivial".
Random(RCWA(Integers))
Computes a product of "randomly" chosen class shifts, class reflections and class transpositions. This seems to be suitable for generating reasonably good examples.
RankOfKernelOfActionOnRespectedPartition(G)
Performs the first part of the computations done by KernelOfActionOnRespectedPartition.
Rcwa(R)
"Trivial". -- Attributes and properties set can be derived easily or hold by definition.
RCWA(R)
Attributes and properties are set according to Theorem 2.1.1, Theorem 2.1.2, Corollary 2.1.6 and Theorem 2.12.8 in [Koh05].
RcwaGroupByPermGroup(G)
Uses RcwaMapping, Part (d).
RCWAInfo(n)
"Trivial".
RcwaMapping
(a)-(c): "trivial", (d): n^perm - n for determining the coefficients, (e): "affine mappings by values at two given points", (f) and (g): "trivial", (h) and (i): correspond to Lemma 2.1.4 in [Koh05], (j): uses a simple parser for the permitted expressions.
RCWATestAll(), RCWATestInstall()
Just read in files running / containing the tests.
RCWATestExamples()
Runs the example tester from the GAPDoc package.
RepresentativeAction(G,src,dest,act),
RepresentativeActionPreImage
As described in the documentation of these methods. The underlying idea to successively compute two balls around src and dest until they intersect non-trivially is standard in computational group theory. Words standing for products of generators of G are stored for every image of src or dest.
RepresentativeAction(RCWA(Integers),P1,P2)
Arbitrary mapping: see Lemma 2.1.4 in [Koh05]. Tame mapping: see proof of Theorem 2.8.9 in [Koh05]. The former is almost trivial, while the latter is a bit complicated and takes usually also much more time.
RepresentativeAction(RCWA(Integers),f,g)
The algorithm used by IsConjugate constructs actually also an element x such that f^x = g.
RespectedPartition(f),
RespectedPartition(G)
There are presently two sophisticated algorithms implemented for finding respected partitions. One of them has evolved from the algorithm described in the proof of Theorem 2.5.8 in [Koh05]. The other one starts with the coarsest partition of the base ring such that every generator of G is affine on every part. This partition is then refined successively until a respected partition is obtained. The refinement step is basically as follows: Take the images of the partition under all generators of G. This way one obtains as many further partitions of the base ring as there are generators of G. Then the "new" partition is the coarsest common refinement of all these partitions.
RespectsPartition(G,P)
"Straightforward".
RestrictedBall(G,g,r,modulusbound)
"Straightforward".
RestrictedPerm(g,S)
"Straightforward".
Restriction(g,f)
Computes the action of RightInverse(f) * g * f on the image of f.
Restriction(G,f)
Gets a set of generators by applying Restriction(g,f) to the generators g of G.
RightInverse(f)
"Straightforward" if one knows how to compute images of residue classes under affine mappings, and how to compute inverses of affine mappings.
Root(f,k)
If f is bijective, class-wise order-preserving and has finite order:
Find a conjugate of f which is a product of class transpositions. Slice cycles \(\prod_{i=2}^l \tau_{r_1(m_1),r_i(m_i)}\) of f a respected partition \(\mathcal{P}\) into cycles \(\prod_{i=1}^l \prod_{j=0}^{k-1} \tau_{r_1(km_1),r_i+jm_i(km_i)}\) of the k-fold length on the refined partition which one gets from \(\mathcal{P}\) by decomposing any \(r_i(m_i) \in \mathcal{P}\) into residue classes (mod \(km_i\)). Finally conjugate the resulting permutation back.
Other cases seem to be more difficult and are currently not covered.
RotationFactor(g)
"Trivial".
RunDemonstration(filename)
"Trivial" -- only I/O operations.
SemilocalizedRcwaMapping(f,pi)
"Trivial".
ShiftsDownOn(f), ShiftsUpOn(f)
Straightforward coefficient- and residue class operations.
ShortCycles(g,maxlng)
Looks for fixed points of affine partial mappings of powers of g.
ShortCycles(g,S,maxlng),
ShortCycles(g,S,maxlng,maxn)
"Straightforward".
ShortOrbits(G,S,maxlng),
ShortOrbits(G,S,maxlng,maxn)
"Straightforward".
ShortResidueClassCycles(g,modulusbound,maxlng)
Different methods -- see source code in pkg/rcwa/lib/rcwamap.gi.
ShortResidueClassOrbits(g,modulusbound,maxlng)
Different methods -- see source code in pkg/rcwa/lib/rcwagrp.gi.
Sign(g)
Evaluation of the given expression. For the mathematical meaning (epimorphism!), see Theorem 2.12.8 in [Koh05].
Sinks(f)
Computes the strongly connected components of the transition graph by the function STRONGLY_CONNECTED_COMPONENTS_DIGRAPH, and selects those which are proper subsets of their preimages and proper supersets of their images under f.
Size(G) (order of an rcwa group)
Test whether one of the generators of the group G has infinite order. If so, return infinity. Test whether the group G is tame. If not, return infinity. Test whether RankOfKernelOfActionOnRespectedPartition(G) is nonzero. If so, return infinity. Otherwise if G is class-wise order-preserving, return the size of the permutation group induced on the stored respected partition. If G is not class-wise order-preserving, return the size of the permutation group induced on the refinement of the stored respected partition which is obtained by splitting each residue class into three residue classes with equal moduli.
Size(M) (order of an rcwa monoid)
Check whether M is in fact an rcwa group. If so, use the method for rcwa groups instead. Check whether one of the generators of M is surjective, but not injective. If so, return infinity. Check whether for all generators \(f\) of M, the image of the union of the loops of \(f\) under \(f\) is finite. If not, return infinity. Check whether one of the generators of M is bijective and has infinite order. If so, return infinity. Check whether one of the generators of M is wild. If so, return infinity. Apply the above criteria to the elements of the ball of radius 2 around 1, and return infinity if appropriate. Finally attempt to compute the list of elements of M. If this is successful, return the length of the resulting list.
SmallGeneratingSet(G)
Eliminates generators \(g\) which can be found to be redundant easily, i.e. by checking whether the balls about 1 and \(g\) of some small radius \(r\) in the group generated by all generators of G except for \(g\) intersect nontrivially.
Sources(f)
Computes the strongly connected components of the transition graph by the function STRONGLY_CONNECTED_COMPONENTS_DIGRAPH, and selects those which are proper supersets of their preimages and proper subsets of their images under f.
SparseRep(f), StandardRep(f)
Straightforward coefficient operations.
SplittedClassTransposition(ct,k)
"Straightforward".
StructureDescription(G)
This method uses a combination of techniques to obtain some basic information on the structure of an rcwa group. The returned description reflects the way the group has been built (DirectProduct, WreathProduct, etc.).
f+g
Pointwise addition of affine mappings.
String(obj)
"Trivial".
Support(G)
"Straightforward".
Trajectory(f,n,...)
Iterated application of an rcwa mapping. In the methods computing "accumulated coefficients", additionally composition of affine mappings.
TransitionGraph(f,m)
"Straightforward" -- just check a sufficiently long interval.
TransitionMatrix(f,m)
Evaluation of the given expression.
TransposedClasses(g)
"Trivial".
View(f)
"Trivial".
WreathProduct(G,P)
Uses DirectProduct to embed the NrMovedPoints(P)th direct power of G, and RcwaMapping, Part (d) to embed the finite permutation group P.
WreathProduct(G,Z)
Restricts G to the residue class 3(4), and encodes the generator of Z as \(\tau_{0(2),1(2)} \cdot \tau_{0(2),1(4)}\). It is used that the images of 3(4) under powers of this mapping are pairwise disjoint residue classes.
Zero(f)
"Trivial".
generated by GAPDoc2HTML