Quelle rcwamap.gd Sprache: Shell

#############################################################################
##
#W rcwamap.gd GAP4 Package `RCWA' Stefan Kohl
##
## This file contains declarations of functions, operations etc. for
## computing with rcwa mappings.
##
## Let R be an infinite euclidean ring which is not a field and all of whose
## proper residue class rings are finite.
## We call a mapping f: R -> R *residue-class-wise affine*, or for short
## an *rcwa* mapping, if there is a nonzero m in R such that f is affine on
## residue classes (mod m).
## This means that for any residue class r(m) in R/mR there are coeffi-
## cients a_r(m), b_r(m), c_r(m) in R such that the restriction of f to the
## set r(m) = { r + km | k in R } is given by
##
## a_r(m) * n + b_r(m)
## n |--> -------------------
## c_r(m) .
##
## We always assume that c_r(m) is normalized to a certain "standard asso-
## ciate" (e.g. for R = Z this means that c_r(m) > 0), that all fractions
## are reduced, i.e. that gcd( a_r(m), b_r(m), c_r(m) ) = 1, and that m is
## chosen multiplicatively minimal.
## Apart from the restrictions imposed by the condition that the image
## of any residue class r(m) under f must be a subset of R and that one can-
## not divide by 0, the coefficients a_r(m), b_r(m) and c_r(m) can be any
## ring elements.
## We call m the *modulus* of f. By *products* of rcwa mappings we al-
## ways mean their compositions as mappings, and by the *inverse* of a bi-
## jective rcwa mapping we mean its inverse mapping.
## The set Rcwa(R) of all rcwa mappings of R forms a monoid under multi-
## plication. We call a submonoid of Rcwa(R) a *residue-class-wise affine*
## monoid, or for short an *rcwa* monoid.
## The set RCWA(R) := { g in Sym(R) | g is residue-class-wise affine }
## is closed under multiplication and taking inverses (this can be verified
## easily), hence forms a subgroup of Sym(R). We call a subgroup of RCWA(R)
## a *residue-class-wise affine* group, or for short an *rcwa* group.
## While computing with infinite permutation groups in general is a very
## difficult task, the rcwa groups form a class of groups which are accessi-
## ble to computations.
##
## An rcwa mapping object stores the following data:
##
## - Underlying Ring: The source and range R of the mapping, hence its "un-
## derlying ring", is stored as the `UnderlyingRing' of
## the family the rcwa mapping object belongs to. It is
## also available as the value of the attribute `Source'.
##
## - Modulus: The modulus m is stored as a component <modulus> in
## any rcwa mapping object.
##
## - Coefficients: The coefficient list is stored as a component <coeffs>
## in any rcwa mapping object. The component <coeffs> is
## a list of |R/mR| lists of three elements of R, each,
## giving the coefficients a_r(m), b_r(m) and c_r(m) for
## r(m) running through all residue classes (mod m).
## The ordering of these triples is defined by the
## ordering of the residues r mod m in the sorted list
## `AllResidues( <R>, <m> )'.
##
## It is always taken care that the entries of the stored coefficient trip-
## les of an rcwa mapping are coprime, that the third entry of any coeffi-
## cient triple equals its standard conjugate and that the number of stored
## coefficient triples equals the number of residue classes modulo the modu-
## lus of the mapping. Given this, an rcwa mapping determines its internal
## representation uniquely. Thus testing rcwa mappings for equality is very
## cheap. The reduction of coefficient lists mentioned above prevents also
## unnecessary coefficient explosion.
##
## We use the notation for the modulus and the coefficients of an rcwa map-
## ping introduced above throughout this file.
##
## Algorithms and methods for computing with rcwa mappings and -groups are
## described in the author's article
##
## Algorithms for a Class of Infinite Permutation Groups.
## J. Symb. Comput. 43(2008), no. 8, 545-581, DOI: 10.1016/j.jsc.2007.12.001
##
#############################################################################

#############################################################################
##
#V InfoRCWA . . . . . . . . . . . . . . . . . . info class for RCWA package
#F RCWAInfo . . . . . . . . . . . . . . . . . . set info level of `RcwaInfo'
##
## This is the Info class of the RCWA package.
##
## For convenience: `RCWAInfo( <n> )' is a shorthand for
## `SetInfoLevel( RcwaInfo, <n> )'.
##
## See Section "Info Functions" in the GAP Reference Manual for
## a description of the Info mechanism.
##
DeclareInfoClass( "InfoRCWA" );
DeclareGlobalFunction( "RCWAInfo" );

#############################################################################
##
#S Rcwa mappings: Definitions. /////////////////////////////////////////////
##
#############################################################################

#############################################################################
##
#C IsRcwaMapping . . . . . . . . . . . . . . . . . . . . . all rcwa mappings
#C IsRcwaMonoid . . . . . . . . . . . . . . . . . . . . . all rcwa monoids
#C IsRcwaGroup . . . . . . . . . . . . . . . . . . . . . . . all rcwa groups
##
## The category of all rcwa mappings / -monoids / -groups.
##
DeclareCategory( "IsRcwaMapping", IsMapping and IsRingElement );
DeclareSynonym( "IsRcwaMonoid",
 CategoryCollections(IsRcwaMapping) and IsMonoid );
DeclareSynonym( "IsRcwaGroup",
 CategoryCollections(IsRcwaMapping) and IsGroup );

#############################################################################
##
#C IsRcwaMappingOfZ . . . . . . . . . . . . . . . . . . rcwa mappings of Z
#C IsRcwaMappingOfZxZ . . . . . . . . . . . . . . . . rcwa mappings of Z^2
#C IsRcwaMappingOfZ_pi . . . . . . . . . . . . . . . rcwa mappings of Z_(pi)
#C IsRcwaMappingOfGFqx . . . . . . . . . . . . . . rcwa mappings of GF(q)[x]
#C IsRcwaMappingOfZOrZ_pi . . . . . . . . . . rcwa mappings of Z or Z_(pi)
##
## The category of all rcwa mappings of the ring Z of integers, of Z^2, of
## (semi-) localizations of Z or of polynomial rings in one variable over a
## finite field, respectively. The category `IsRcwaMappingOfZOrZ_pi' is the
## union of the categories `IsRcwaMappingOfZ' and `IsRcwaMappingOfZ_pi'.
##
DeclareCategory( "IsRcwaMappingOfZOrZ_pi", IsRcwaMapping );
DeclareCategory( "IsRcwaMappingOfZ", IsRcwaMappingOfZOrZ_pi );
DeclareCategory( "IsRcwaMappingOfZxZ", IsRcwaMapping );
DeclareCategory( "IsRcwaMappingOfZ_pi", IsRcwaMappingOfZOrZ_pi );
DeclareCategory( "IsRcwaMappingOfGFqx", IsRcwaMapping );

#############################################################################
##
#F RcwaMappingsFamily( <R> ) . . . . family of rcwa mappings of the ring <R>
#F RcwaMappingsOfZ_piFamily( <pi> ) " " of the ring Z_(pi)
#F RcwaMappingsOfGFqxFamily( <R> ) " " of the ring R = GF(q)[x]
##
DeclareGlobalFunction( "RcwaMappingsFamily" );
DeclareGlobalFunction( "RcwaMappingsOfZ_piFamily" );
DeclareGlobalFunction( "RcwaMappingsOfGFqxFamily" );

#############################################################################
##
#R IsRcwaMappingStandardRep . . . "standard" representation of rcwa mappings
##
## This is the representation of rcwa mappings by modulus <modulus>
## (in the following denoted by m (ring element) or L (lattice in Z^2),
## respectively) and coefficient list <coeffs>.
##
## Rcwa mappings of Z, Z_pi or GF(q)[x]:
##
## The component <coeffs> is a list of |R/mR| lists of three coprime ele-
## ments of the underlying ring R, each, containing the coefficients a_r(m),
## b_r(m) and c_r(m) for r(m) running through all residue classes (mod m).
##
## The ordering of these triples is defined by the ordering of the residues
## r mod m in the sorted list returned by `AllResidues( <R>, <m> )'.
##
## Rcwa mappings of Z^2:
##
## The matrix L whose rows span the lattice is always stored in Hermite
## normal form.
##
## The component <coeffs> is a list of det(L) coefficient triples
## ( a_r(m), b_r(m), c_r(m) ), each consisting of
##
## - an invertible 2x2 matrix a_r(m) with integer entries,
##
## - a vector b_r(m) in Z^2, and
##
## - a positive integer c_r(m),
##
## for r(m) running through all residue classes r(m) in Z^2/L.
##
## The ordering of these triples is defined by the ordering of the residues
## in the sorted list returned by `AllResidues( Integers^2, <L> )'.
##
DeclareRepresentation( "IsRcwaMappingStandardRep",
 IsComponentObjectRep and IsAttributeStoringRep,
 [ "modulus", "coeffs" ] );

#############################################################################
##
#R IsRcwaMappingSparseRep . . . . . 'sparse' representation of rcwa mappings
##
## This is the representation of rcwa mappings by a list <coeffs> of residue
## classes together with the coefficients of the affine partial mappings on
## these residue classes.
##
## The component <coeffs> is a list of 5-tuples
##
## [ r, m, a_r(m), b_r(m), c_r(m) ].
##
## There is such 5-tuple for every residue class in
##
## Set( Flat( List( LargestSourcesOfAffineMappings( <f> ),
## AsUnionOfFewClasses ) ) ),
## in this order.
##
## The representation `IsRcwaMappingSparseRep' is advantageous if and only
## if the rcwa mapping in question has relatively few distinct affine
## partial mappings, or more precisely, if the above list is short compared
## to the modulus of the mapping. Just as with `IsRcwaMappingStandardRep',
## the representation of an rcwa mapping in this representation is unique.
##
DeclareRepresentation( "IsRcwaMappingSparseRep",
 IsComponentObjectRep and IsAttributeStoringRep,
 [ "modulus", "coeffs" ] );

#############################################################################
##
## Construction of an rcwa mapping
##
#M RcwaMapping ( <R>, <m>, <coeffs> ) . . by ring, modulus and coefficients
#M RcwaMappingNC( <R>, <m>, <coeffs> )
#M RcwaMapping ( <R>, <coeffs> ) . . . . . . . . by ring and coefficients
#M RcwaMappingNC( <R>, <coeffs> )
#M RcwaMapping ( <coeffs> ) . . . . . . . . . . . . . . . . by coefficients
#M RcwaMappingNC( <coeffs> )
#M RcwaMapping ( <perm>, <range> ) . . . . . . . by permutation and range
#M RcwaMappingNC( <perm>, <range> )
#M RcwaMapping ( <m>, <values> ) . . . . . . . . . . by modulus and values
#M RcwaMappingNC( <m>, <values> )
#M RcwaMapping ( <pi>, <coeffs> ) by noninvertible primes and coefficients
#M RcwaMappingNC( <pi>, <coeffs> )
#M RcwaMapping ( <q>, <m>, <coeffs> ) . by field size, modulus and coeff's
#M RcwaMappingNC( <q>, <m>, <coeffs> )
#M RcwaMapping ( P1, P2 ) . . . . . . . . . . . . . by two class partitions
#M RcwaMappingNC( P1, P2 )
#M RcwaMapping ( <cycles> ) . . . . . . . . . . . . . . . . by class cycles
#M RcwaMappingNC( <cycles> )
##
## Construction of the rcwa mapping
##
## (a) of <R> with modulus <m> and coefficients <coeffs>, resp.
##
## (b) of <R> = Z or <R> = Z_(pi) with modulus Length( <coeffs> )
## and coefficients <coeffs>, resp.
##
## (c) of R = Z with modulus Length( <coeffs> ) and coefficients
## <coeffs>, resp.
##
## (d) of R = Z, acting on any set <range> + k * Length(<range>) like the
## permutation <perm> on <range>, resp.
##
## (e) of R = Z with modulus <m> and values given by a list <values> of
## 2 pairs [preimage,image] per residue class (mod <m>), resp.
##
## (f) of R = Z_(pi) with with modulus Length( <coeffs> ) and coefficients
## <coeffs>, resp.
##
## (g) of GF(q)[x] with modulus <m> and coefficients <coeffs>, resp.
##
## (h) a bijective rcwa mapping which induces a bijection between the
## partitions <P1> and <P2> of R into residue classes and which is
## affine on the elements of <P1>, resp.
##
## (i) a bijective rcwa mapping with "residue class cycles" as given by
## <cycles>. The latter is a list of lists of pairwise disjoint residue
## classes which the mapping should permute cyclically, each.
##
## The difference between `RcwaMapping' and `RcwaMappingNC' is that the
## former performs some argument checks which are omitted in the latter,
## where just anything may happen if wrong or inconsistent arguments
## are given.
##
DeclareOperation( "RcwaMapping", [ IsObject ] );
DeclareOperation( "RcwaMapping", [ IsObject, IsObject ] );
DeclareOperation( "RcwaMapping", [ IsObject, IsObject, IsObject ] );
DeclareOperation( "RcwaMappingNC", [ IsObject ] );
DeclareOperation( "RcwaMappingNC", [ IsObject, IsObject ] );
DeclareOperation( "RcwaMappingNC", [ IsObject, IsObject, IsObject ] );

#############################################################################
##
#F RcwaMappingsType( <R> )
##
DeclareGlobalFunction( "RcwaMappingsType" );

#############################################################################
##
#F LocalizedRcwaMapping( <f>, )
#F SemilocalizedRcwaMapping( <f>, <pi> )
##
## These functions return the rcwa mapping of Z_(p) resp. Z_(pi) with the
## same coefficients as <f>.
##
DeclareGlobalFunction( "LocalizedRcwaMapping" );
DeclareGlobalFunction( "SemilocalizedRcwaMapping" );

#############################################################################
##
#A ProjectionsToCoordinates( <f> )
##
## Projections of an rcwa mapping of Z^2 to the coordinates.
##
DeclareAttribute( "ProjectionsToCoordinates", IsRcwaMappingOfZxZ );

#############################################################################
##
#O Modulus( <f> ) . . . . . . . . . . . the modulus of the rcwa mapping <f>
#O Modulus( <M> ) . . . . . . . . . . . the modulus of the rcwa monoid <M>
##
## See also the attribute `ModulusOfRcwaMonoid'.
##
DeclareOperation( "Modulus", [ IsRcwaMapping ] );
DeclareOperation( "Modulus", [ IsRcwaMonoid ] );

#############################################################################
##
#O Coefficients( <f> ) . . . . . . the coefficients of the rcwa mapping <f>
##
DeclareOperation( "Coefficients", [ IsRcwaMapping ] );

#############################################################################
##
#A UnderlyingField( <f> ) . . . . . . coefficient field of the source of <f>
##
DeclareAttribute( "UnderlyingField", IsRcwaMappingOfGFqx );

#############################################################################
##
#V IdentityRcwaMappingOfZxZ . . . . . . . . . . identity rcwa mapping of Z^2
##
DeclareGlobalName( "IdentityRcwaMappingOfZxZ" );

#############################################################################
##
#F DisplayRcwaMapping( <f> )
##
DeclareGlobalFunction( "DisplayRcwaMapping" );

#############################################################################
##
#S Special types of rcwa permutations. /////////////////////////////////////
##
#############################################################################

#############################################################################
##
#F ClassShift( <R>, <r>, <m> ) . . . . . . . . . . . . . class shift nu_r(m)
#F ClassShift( <r>, <m> ) . . . . . . . . . . . . . . . . . . . . . (dito)
#F ClassShift( <R>, <cl> ) . . . . . . class shift nu_r(m), where cl = r(m)
#F ClassShift( <cl> ) . . . . . . . . . . . . . . . . . . . . . . . (dito)
#F ClassShift( <R> ) . . . . . . . . . . . . . class shift nu_R: n -> n + 1
#F ClassShiftOfZxZ( ... ) . . . . . . . . . . . . . . . class shift of Z^2
#P IsClassShift( <sigma> )
#P IsPowerOfClassShift( <sigma> )
##
## Returns the class shift nu_r(m).
##
## The *class shift* nu_r(m) is the rcwa permutation which maps n in r(m)
## to n + m and which fixes the complement of the residue class r(m)
## pointwise.
##
## Enclosing the argument list in list brackets is permitted.
##
DeclareGlobalFunction( "ClassShift" );
DeclareGlobalFunction( "ClassShiftOfZxZ" );
DeclareProperty( "IsClassShift", IsRcwaMapping );
DeclareProperty( "IsPowerOfClassShift", IsRcwaMapping );

#############################################################################
##
#F ClassReflection( <R>, <r>, <m> ) . . . . class reflection varsigma_r(m)
#F ClassReflection( <r>, <m> ) . . . . . . . . . . . . . . . . . . . (dito)
#F ClassReflection( <R>, <cl> ) . class reflection varsigma_r(m), cl = r(m)
#F ClassReflection( <cl> ) . . . . . . . . . . . . . . . . . . . . . (dito)
#F ClassReflection( <R> ) . . . . . . class reflection varsigma_R: n -> -n
#P IsClassReflection( <sigma> )
##
## Returns the class reflection varsigma_r(m).
##
## The *class reflection* varsigma_r(m) is the rcwa permutation which maps
## n in r(m) to -n + 2r and which fixes the complement of the residue class
## r(m) pointwise, where it is understood that 0 <= r < m in the ordering
## used by GAP.
##
## Enclosing the argument list in list brackets is permitted.
##
DeclareGlobalFunction( "ClassReflection" );
DeclareProperty( "IsClassReflection", IsRcwaMapping );

#############################################################################
##
#F ClassRotation( <R>, <r>, <m>, ) . . . . . class rotation rho_(r(m),u)
#F ClassRotation( <r>, <m>, ) . . . . . . . . . . . . . . . . . (dito)
#F ClassRotation( <R>, <cl>, ) . class rotation rho_(r(m),u), cl = r(m)
#F ClassRotation( <cl>, ) . . . . . . . . . . . . . . . . . . . (dito)
#F ClassRotation( <R>, ) . . . . . . . class rotation rho_(R,u): n -> un
#F ClassRotationOfZxZ( ... ) . . . . . . . . . . . . . class rotation of Z^2
#P IsClassRotation( <sigma> )
##
## Returns the class rotation rho_(r(m),u).
##
## The *class rotation* rho_(r(m),u) is the rcwa permutation which maps
## n in r(m) to un + r(1-u) and which fixes the complement of the residue
## class r(m) pointwise, where it is understood that 0 <= r < m in the
## ordering used by GAP. Class rotations generalize class reflections --
## we have varsigma_r(m) = rho_(r(m),-1).
##
## Enclosing the argument list in list brackets is permitted.
##
DeclareGlobalFunction( "ClassRotation" );
DeclareGlobalFunction( "ClassRotationOfZxZ" );
DeclareProperty( "IsClassRotation", IsRcwaMapping );
DeclareAttribute( "RotationFactor", IsRcwaMapping );

#############################################################################
##
#F ClassTransposition( <R>, <r1>, <m1>, <r2>, <m2> ) . . class transposition
#F ClassTransposition( <r1>, <m1>, <r2>, <m2> ) tau_r1(m1),r2(m2)
#F ClassTransposition( <R>, <cl1>, <cl2> ) . . . dito, cl1=r1(m1) cl2=r2(m2)
#F ClassTransposition( <cl1>, <cl2> ) . . . . . . . . . . . . . . . (dito)
#F ClassTranspositionOfZxZ( ... ) . . . . . . . . class transposition of Z^2
#F GeneralizedClassTransposition( ... ) . . allows ri < 0, ri > mi, mi < 0
#P IsClassTransposition( <sigma> )
#P IsGeneralizedClassTransposition( <sigma> )
#A TransposedClasses( <ct> )
##
## Returns the class transposition tau_(r1(m1),r2(m2)).
##
## Given two disjoint residue classes r1(m1) and r2(m2) of the base ring R,
## the *class transposition* tau_(r1(m1),r2(m2)) in RCWA(R) is defined by
##
## /
## | (m2*n + m1*r2 - m2*r1)/m1 if n in r1(m1),
## n |---> < (m1*n + m2*r1 - m1*r2)/m2 if n in r2(m2),
## | otherwise,
## \
##
## where it is understood that 0 <= r1 < m1 and 0 <= r2 < m2 in the ordering
## used by GAP. The class transposition tau_(r1(m1),r2(m2)) is an involution
## which interchanges the residue classes r1(m1) and r2(m2) and which fixes
## the complement of their union pointwise.
##
## Enclosing the argument list in list brackets is permitted.
##
DeclareGlobalFunction( "ClassTransposition" );
DeclareGlobalFunction( "ClassTranspositionOfZxZ" );
DeclareSynonym( "GeneralizedClassTransposition", ClassTransposition );
DeclareProperty( "IsClassTransposition", IsRcwaMapping );
DeclareProperty( "IsGeneralizedClassTransposition", IsRcwaMapping );
DeclareAttribute( "TransposedClasses", IsRcwaMapping );

#############################################################################
##
#O SplittedClassTransposition( <ct>, <k>, <cross> )
##
## Returns a decomposition of the class transposition <ct> into a product
## of <k> class transpositions.
##
## Class transpositions can be written as products of any given number <k>
## of class transpositions, as long as the underlying ring has a residue
## class ring of cardinality <k>.
##
DeclareOperation( "SplittedClassTransposition",
 [ IsRcwaMapping and IsClassTransposition, IsObject ] );
DeclareOperation( "SplittedClassTransposition",
 [ IsRcwaMapping and IsClassTransposition,
 IsObject, IsBool ] );

#############################################################################
##
#F ClassPairs( <m> )
#F ClassPairs( <R>, <m> )
#F NumberClassPairs( <m> )
#F NrClassPairs( <m> )
#V CLASS_PAIRS
#V CLASS_PAIRS_LARGE
##
## In its one-argument form, the function `ClassPairs' returns a list of
## 4-tuples (r1,m1,r2,m2) of integers corresponding to the unordered pairs
## of disjoint residue classes r1(m1) and r2(m2) with m1, m2 <= <m>.
## In its two-argument form, it does basically "the same" for the ring <R>.
##
## The function `NumberClassPairs' returns the number of unordered pairs of
## disjoint residue classes r1(m1) and r2(m2) with m1, m2 <= <m>.
## While this is just Length(ClassPairs(m)), `NumberClassPairs' computes
## this number much faster, and without generating a list of all tuples.
## `NrClassPairs' is a synonym for `NumberClassPairs'.
##
## The variables `CLASS_PAIRS' and `CLASS_PAIRS_LARGE' are used to cache
## lists computed by `ClassPairs'. These caches are mainly used to generate
## random class transpositions.
##
DeclareGlobalFunction( "ClassPairs" );
DeclareGlobalFunction( "NumberClassPairs" );
DeclareSynonym( "NrClassPairs", NumberClassPairs );

#############################################################################
##
#M PrimeSwitch( ) . . product of ct's, with multiplier and divisor 2
#M PrimeSwitch( , <k> )
#M PrimeSwitch( , <r>, <m> )
#M PrimeSwitch( , <cl> )
#P IsPrimeSwitch( <g> )
##
## The first version returns the prime switch sigma_p as defined in
##
## A simple group generated by involutions interchanging residue classes
## of the integers. Math. Z. 264 (2010), no. 4, 927-938;
##
## for an odd prime p, the *prime switch* sigma_p is defined as the product
## tau_(0(8), 1(2p)) * tau_(4(8),-1(2p)) * tau_(0(4), 1(2p))
## * tau_(2(4),-1(2p)) * tau_(2(2p),1(4p)) * tau_(4(2p),2p+1(4p))
## of 6 class transpositions.
##
## The prime switch sigma_p is a bijective rcwa mapping of Z with
## modulus 4p, multiplier p and divisor 2.
##
## The second version returns the restriction of sigma_p by n -> kn.
##
## The third and the fourth version return a product g of 3 class trans-
## positions such that Mult(g) = 2p, Div(g) = 2 and Multpk(g,p,1) = r(m),
## respectively, Multpk(g,p,1) = cl. As above, p must be an odd prime.
## Further, m must be even and >=4.
##
DeclareOperation( "PrimeSwitch", [ IsRingElement ] );
DeclareOperation( "PrimeSwitch", [ IsRingElement, IsRingElement ] );
DeclareOperation( "PrimeSwitch", [ IsRingElement, IsRingElement,
 IsRingElement ] );
DeclareOperation( "PrimeSwitch", [ IsRingElement, IsResidueClassUnion ] );
DeclareProperty( "IsPrimeSwitch", IsRcwaMapping );

#############################################################################
##
#F mKnot( <m> ) . . . . . . . . . . rcwa mapping of Timothy P. Keller's type
##
## Given an odd integer <m>, this function returns the bijective rcwa
## mapping g_<m> as defined in
##
## Timothy P. Keller. Finite Cycles of Certain Periodically Linear
## Permutations. Missouri J. Math. Sci. 11(1999), no. 3, 152-157.
##
DeclareGlobalFunction( "mKnot" );

#############################################################################
##
#F ClassUnionShift( <S> ) . . shift of residue class union <S> by Mod( <S> )
##
## Returns the rcwa mapping which maps <S> to <S> + Modulus(<S>) and which
## fixes the complement of <S> pointwise.
##
DeclareGlobalFunction( "ClassUnionShift" );

#############################################################################
##
#O CTCSCRSplit( <g> )
##
## A factorization of the rcwa permutation <g> of Z into 3 factors r, s and
## t, where r fixes the nonnegative integers setwise, s is integral and
## class-wise order-preserving, and t is integral.
##
DeclareOperation( "CTCSCRSplit", [ IsRcwaMappingOfZ ] );

#############################################################################
##
#O Factorization( <g> )
#A FactorizationIntoCSCRCT( <g> )
#A FactorizationIntoElementaryCSCRCT( <g> )
##
## A factorization of an rcwa permutation into class shifts,
## class reflections and class transpositions. The latter operation
## decomposes into factors with particularly small moduli --
## for elements of CT_P(Z), where P is some finite set of odd primes,
## the factors are taken from a finite set of generators.
##
DeclareOperation( "Factorization", [ IsMultiplicativeElementWithInverse ] );
DeclareAttribute( "FactorizationIntoCSCRCT",
 IsMultiplicativeElementWithInverse );
DeclareAttribute( "FactorizationIntoElementaryCSCRCT",
 IsMultiplicativeElementWithInverse );
DeclareSynonym( "FactorizationIntoGenerators", FactorizationIntoCSCRCT );

#############################################################################
##
#S Attributes and properties derived from the coefficients. ////////////////
##
#############################################################################

#############################################################################
##
#A Multiplier( <f> ) . . . . . . . . the multiplier of the rcwa mapping <f>
#A Multiplier( <M> ) . . . . . . . . . the multiplier of the rcwa monoid <M>
#A Divisor( <f> ) . . . . . . . . . . . the divisor of the rcwa mapping <f>
#A Divisor( <M> ) . . . . . . . . . . . the divisor of the rcwa monoid <M>
#A PrimeSet( <f> ) . . . . . . . . . . the prime set of the rcwa mapping <f>
#A PrimeSet( <M> ) . . . . . . . . . . the prime set of the rcwa monoid <M>
#A MaximalShift( <f> ) . . . . maximum of the absolute values of the b_r(m)
#P IsBalanced( <f> ) . . indicates whether the rcwa mapping <f> is balanced
#P IsIntegral( <f> ) . . . . . indicates whether the divisor of <f> equals 1
#P IsIntegral( <M> ) . . indicates whether all elements of <M> are integral
#P IsClassWiseTranslating( <f> ) . indicates whether <f> is class-wise trs.
#P IsClassWiseTranslating( <M> ) indicates whether all elements of <M> are "
#P IsClassWiseOrderPreserving( <f> ) . . . . indicates whether <f> is cwop.
#P IsClassWiseOrderPreserving( <M> ) . . . . indicates whether <M> is cwop.
#P IsSignPreserving( <f> ) indicates whether the rcwa mapping <f> fixes N_0
#P IsSignPreserving( <M> ) . indicates whether the rcwa monoid <M> fixes N_0
##
## We define the *multiplier* of an rcwa mapping <f> by the least common
## multiple of the coefficients a_r(m), and we define its *divisor* by the
## least common multiple of the coefficients c_r(m).
##
## We define the *multiplier* / *divisor* of an rcwa group or -monoid by the
## lcm of the multipliers / divisors of its elements, if such an lcm exists,
## and by infinity otherwise.
##
## We define the *prime set* of an rcwa mapping <f> by the set of all primes
## dividing its modulus or its multiplier, and we define the *prime set* of
## an rcwa group or -monoid by the union of the prime sets of its elements.
##
## We define the *maximal shift* of an rcwa mapping <f> of Z as the maximum
## of the absolute values of the coefficients b_r(m).
##
## We say that an rcwa mapping is *balanced* if its multiplier and its
## divisor have the same prime divisors.
##
## We say that an rcwa mapping is *integral* if its divisor is 1, and we say
## that an rcwa group / -monoid is *integral* if all of its elements are so.
##
## We say that an rcwa mapping is *class-wise translating* if all of its
## affine partial mappings are translations. We say that an rcwa group
## or -monoid is *class-wise translating* if all of its elements are so.
##
## We say that an rcwa mapping of Z or Z_(pi) is *class-wise order-preser-
## ving* if all coefficients a_r(m) are positive, and we say that an rcwa
## group or -monoid is *class-wise order-preserving* if all of its elements
## are so.
##
## We say that an rcwa mapping of Z or Z_(pi) is *sign-preserving* if it
## does not map nonnegative integers to negative integers or vice versa.
##
DeclareAttribute( "Multiplier", IsRcwaMapping );
DeclareAttribute( "Multiplier", IsRcwaMonoid );
DeclareSynonym( "Mult", Multiplier );
DeclareAttribute( "Divisor", IsRcwaMapping );
DeclareAttribute( "Divisor", IsRcwaMonoid );
DeclareSynonym( "Div", Divisor );
DeclareAttribute( "PrimeSet", IsRcwaMapping );
DeclareAttribute( "PrimeSet", IsRcwaMonoid );
DeclareAttribute( "MaximalShift", IsRcwaMapping );
DeclareProperty( "IsBalanced", IsRcwaMapping );
DeclareProperty( "IsIntegral", IsRcwaMapping );
DeclareProperty( "IsIntegral", IsRcwaMonoid );
DeclareProperty( "IsClassWiseTranslating", IsRcwaMapping );
DeclareProperty( "IsClassWiseTranslating", IsRcwaMonoid );
DeclareProperty( "IsClassWiseOrderPreserving", IsRcwaMapping );
DeclareProperty( "IsClassWiseOrderPreserving", IsRcwaMonoid );
DeclareProperty( "IsSignPreserving", IsRcwaMapping );
DeclareProperty( "IsSignPreserving", IsRcwaMonoid );

#############################################################################
##
#A ClassWiseOrderPreservingOn( <f> )
#A ClassWiseOrderReversingOn( <f> )
#A ClassWiseConstantOn( <f> )
##
## The union of the residue classes r(m) for which a_r(m) > 0, a_r(m) < 0
## or a_r(m) = 0, respectively.
##
DeclareAttribute( "ClassWiseOrderPreservingOn", IsRcwaMapping );
DeclareAttribute( "ClassWiseOrderReversingOn", IsRcwaMapping );
DeclareAttribute( "ClassWiseConstantOn", IsRcwaMapping );

#############################################################################
##
#A IncreasingOn( <f> ) . . . . . . . . . . . set of n such that |n^f| >> |n|
#A DecreasingOn( <f> ) . . . . . . . . . . . set of n such that |n^f| << |n|
##
## The union of all residue classes r(m) such that |R/a_r(m)R|>|R/c_r(m)R|
## respectively |R/a_r(m)R|<|R/c_r(m)R|.
##
DeclareAttribute( "IncreasingOn", IsRcwaMapping );
DeclareAttribute( "DecreasingOn", IsRcwaMapping );

#############################################################################
##
#A ShiftsUpOn( <f> ) . . . union of residue classes S s.th. f|_S: n -> n + c
#A ShiftsDownOn( <f> ) . . union of residue classes S s.th. f|_S: n -> n - c
##
## Let f be an rcwa mapping of Z with modulus m.
##
## ShiftsUpOn(f) denotes the union of all residue classes r(m) such that
## the restriction f|_r(m) is given by n -> n + b_r(m) for positive b_r(m).
##
## ShiftsDownOn(f) denotes the union of all residue classes r(m) such that
## the restriction f|_r(m) is given by n -> n + b_r(m) for negative b_r(m).
##
DeclareAttribute( "ShiftsUpOn", IsRcwaMappingOfZ );
DeclareAttribute( "ShiftsDownOn", IsRcwaMappingOfZ );

#############################################################################
##
#O Multpk( <f>, , <k> ) the elements multiplied by a multiple of ^<k>
##
## Returns the union of the residue classes r(m) such that
##
## - p^k||a_r(m) if k > 0, resp.
## - p^-k||c_r(m) if k < 0, resp.
## - p \nmid a_r(m), c_r(m) if k = 0.
##
DeclareOperation( "Multpk", [ IsRcwaMapping, IsInt, IsInt ] );

#############################################################################
##
#A MultDivType( <f> ) . distribution of coeff's in numerators & denominators
##
DeclareAttribute( "MultDivType", IsRcwaMapping );

#############################################################################
##
#A FixedPointsOfAffinePartialMappings( <f> )
##
## The fixed points of the affine partial mappings of the rcwa mapping <f>
## in the quotient field of the source.
##
DeclareAttribute( "FixedPointsOfAffinePartialMappings", IsRcwaMapping );

#############################################################################
##
#A LargestSourcesOfAffineMappings( <f> ) . partition on which <f> is affine
##
## The coarsest partition of the base ring R on whose elements the rcwa
## mapping <f> is affine.
##
DeclareAttribute( "LargestSourcesOfAffineMappings", IsRcwaMapping );

#############################################################################
##
#A ImageDensity( <f> ) . . . . . . . . . . . . . . . . image density of <f>
##
## We define the *image density* of an rcwa mapping <f>
## by (sum_(r(m) in R/mR) |R/c_r(m)R|/|R/a_r(m)R|)/m.
##
## The image density of an rcwa mapping measures how "dense" its image is:
##
## An image density > 1 implies that there need to be "overlaps", i.e.
## that the mapping cannot be injective, while an image density < 1 implies
## that the images of the residue classes r(m) do not entirely cover R, i.e.
## that the mapping cannot be surjective.
##
## The image density of any bijective rcwa mapping is 1.
##
DeclareAttribute( "ImageDensity", IsRcwaMapping );

#############################################################################
##
#A DensityOfSupport( <f> )
#A DensityOfSetOfFixedPoints( <f> )
##
## The natural density of the support / set of fixed points of the rcwa
## mapping <f>.
##
DeclareAttribute( "DensityOfSupport", IsRcwaMappingOfZ );
DeclareAttribute( "DensityOfSetOfFixedPoints", IsRcwaMappingOfZ );

#############################################################################
##
#A MappedPartitions( <g> )
##
DeclareAttribute( "MappedPartitions", IsRcwaMapping );

#############################################################################
##
#O HashValueOfRcwaMapping( <f>, <m> )
##
## Returns a hash value for the rcwa mapping <f> in the range [1..<m>].
## The hash value has no mathematical meaning, but given <f> and <m>, it
## is always the same. Its purpose is to allow speeding up the search of
## rcwa mappings within algorithms.
##
DeclareOperation( "HashValueOfRcwaMapping", [ IsRcwaMapping, IsPosInt ] );

#############################################################################
##
#S The notion of tameness. /////////////////////////////////////////////////
##
#############################################################################

#############################################################################
##
#P IsTame( <f> ) . . . . indicates whether or not <f> is a tame rcwa mapping
#P IsTame( <M> ) . . . . indicates whether or not <M> is a tame rcwa monoid
##
## We say that an rcwa mapping <f> is *tame* if and only if the moduli
## of its powers are bounded, and *wild* otherwise. We say that an rcwa
## group or an rcwa monoid is *tame* if and only if the moduli of its
## elements are bounded.
##
DeclareProperty( "IsTame", IsRcwaMapping );
DeclareProperty( "IsTame", IsRcwaMonoid );

#############################################################################
##
#O CheckForWildness( <f> )
#O CheckForWildness( <G>, <maxlng>, <maxmod> )
##
## Performs checks for wildness, and sets `IsTame' to `false' if wildness
## can be established. It is not guaranteed that a wild mapping or group
## is always recognized as such.
## In the latter case, a random walk is done in the group (start point = 1,
## step = multiplication by a random generator):
## - if an element is found which has loops, `IsTame' is set to `false';
## - if the length of the random walk exceeds <maxlng> or the modulus of
## the product exceeds <maxmod>, the operation gives up.
##
DeclareOperation( "CheckForWildness", [ IsRcwaMapping ] );
DeclareOperation( "CheckForWildness", [ IsRcwaMonoid, IsPosInt,
 IsRingElement ] );

#############################################################################
##
#S Support, images, preimages and the action of an rcwa mapping on R. //////
##
#############################################################################

#############################################################################
##
#A Support( <f> ) . . . . . . . . . . . the support of the rcwa mapping <f>
#A Support( <M> ) . . . . . . . . . . . . the support of the rcwa monoid <M>
#A MovedPoints( <f> )
#A MovedPoints( <M> )
##
## For rcwa mappings, -groups and -monoids, `Support' and `MovedPoints' are
## synonyms.
##
DeclareAttribute( "Support", IsRcwaMapping );
DeclareAttribute( "Support", IsRcwaMonoid );
DeclareAttribute( "MovedPoints", IsRcwaMapping );
DeclareAttribute( "MovedPoints", IsRcwaMonoid );

#############################################################################
##
#O \^( <S>, <f> ) . . . . . . . . . image of <S> under the rcwa mapping <f>
##
DeclareOperation( "\^", [ IsListOrCollection, IsRcwaMapping ] );
if not CompareVersionNumbers(GAPInfo.BuildVersion,"4.10") then
 DeclareOperation( "PreImagesSet", [ IsRcwaMapping, IsList ] );
fi;

#############################################################################
##
#O PiecewiseMapping( <sources>, <maps> )
##
## Returns the mapping f composed from the mappings <maps> defined on
## <sources>. Here, <sources> and and <maps> must be lists of the same
## length, and for any i, <maps>[i] must be defined on <sources>[i] or
## on a superset thereof.
##
DeclareOperation( "PiecewiseMapping", [ IsList, IsList ] );

#############################################################################
##
#F InjectiveAsMappingFrom( <f> ) . . . . some set on which <f> is injective
##
## Returns some subset S of Source(<f>) such that the restriction of <f>
## to S is injective.
##
DeclareGlobalFunction( "InjectiveAsMappingFrom" );

#############################################################################
##
#O ShortCycles( <f>, <S>, <maxlng> ) . short cycles of the rcwa mapping <f>
#O ShortCycles( <f>, <S>, <maxlng>, <maxn> )
#O ShortCycles( <f>, <maxlng> )
##
## In the 3-argument case, `ShortCycles' returns a list of all finite cycles
## of the rcwa mapping <f> of length <= <maxlng> which intersect nontri-
## vially with the set <S>. In the 4-argument case, it does the same except
## that <f> must be an rcwa mapping of Z and that cycles exceeding <maxn>
## are dropped. In the 2-argument case, it returns a list of all "single"
## finite cycles of the rcwa mapping <f> of length <= <maxlng>.
##
DeclareOperation( "ShortCycles", [ IsRcwaMapping, IsListOrCollection,
 IsPosInt ] );
DeclareOperation( "ShortCycles", [ IsRcwaMapping, IsListOrCollection,
 IsPosInt, IsPosInt ] );
DeclareOperation( "ShortCycles", [ IsRcwaMapping, IsPosInt ] );

#############################################################################
##
#F ComputeCycleLength( <g>, <n> )
##
## Returns the length of the cycle of the rcwa permutation <g> which
## contains the point <n>, provided that this cycle is finite.
## If the cycle is infinite, the function will run into an infinite loop.
## Iterates are not stored, to save memory.
## The function interprets an option "notify", which defaults to 10000;
## every "notify" iterations, the number of binary digits of the latest
## iterate is printed.
##
DeclareGlobalFunction( "ComputeCycleLength" );

#############################################################################
##
#O ShortResidueClassCycles( <g>, <modulusbound>, <maxlng> )
##
## Returns a list of all cycles of residue classes of the rcwa
## permutation <g> which contain a residue class r(m) such that m divides
## <modulusbound>, and which are not longer than <maxlng>.
##
## Note that we are only talking about a cycle of residue classes
## of an rcwa permutation g if the restrictions of g to all contained
## residue classes are affine.
##
DeclareOperation( "ShortResidueClassCycles", [ IsRcwaMapping, IsRingElement,
 IsPosInt ] );

#############################################################################
##
#O ResidueClassCyclesThroughResidueClass( <g>, <cl>, <modulusbound> )
##
## Returns a list of all cycles of residue classes of the rcwa permutation
## <g> which contain a residue class r(m) which is a subset of the residue
## class <cl> and whose modulus m divides <modulusbound>.
##
## It is required that the restriction of <g> to <cl> is affine.
##
## Note that we are only talking about a cycle of residue classes
## of an rcwa permutation g if the restrictions of g to all contained
## residue classes are affine.
##
DeclareOperation( "ResidueClassCyclesThroughResidueClass",
 [ IsRcwaMapping, IsResidueClass, IsRingElement ] );

#############################################################################
##
#O DrawResidueClassCyclesThroughResidueClassPicture
#O ( <g>, <cl>, <modulusbound>, <edge>, <filename> )
##
## Draws a picture indicating by different colors the lengths of cycles of
## residue classes of the rcwa permutation <g> which contain a residue class
## r(m) which is a subset of the residue class <cl> and whose modulus m
## divides <modulusbound>.
##
## The picture is written in svg format to <filename>.
## If no full path is given, the path defaults to "/user/GAP/pictures/".
##
DeclareOperation( "DrawResidueClassCyclesThroughResidueClassPicture",
 [ IsRcwaMapping, IsResidueClass, IsRingElement,
 IsPosInt, IsString ] );

#############################################################################
##
#O CycleRepresentativesAndLengths( <g>, <S> )
##
## Returns a list of pairs (cycle representative, length of cycle) for all
## cycles of the rcwa permutation <g> which have a nontrivial intersection
## with the set <S>, where fixed points are omitted. The rcwa permutation
## <g> is assumed to have only finite cycles. If <g> has an infinite cycle
## which intersects nontrivially with <S>, this may cause an infinite loop.
##
DeclareOperation( "CycleRepresentativesAndLengths",
 [ IsRcwaMapping, IsListOrCollection ] );

#############################################################################
##
#O FixedResidueClasses( <g>, <maxmod> )
#O FixedResidueClasses( <G>, <maxmod> )
##
## Returns the set of residue classes with modulus greater than 1 and less
## than or equal to <maxmod> which the rcwa mapping <g>, respectively the
## rcwa group <G>, fixes setwise.
##
DeclareOperation( "FixedResidueClasses", [ IsRcwaMapping, IsRingElement ] );
DeclareOperation( "FixedResidueClasses", [ IsRcwaGroup, IsRingElement ] );

#############################################################################
##
#O RestrictedPerm( <g>, <S> ) . . . . . . . . . . restriction of <g> to <S>
#O PermutationOpNC( <g>, , <act> ) . . permutation induced by <g> on 
##
## Returns the restriction of the rcwa permutation <g> to the residue class
## union <S>, respectively the permutation induced by <g> on the partition
## of <R> into residue classes.
##
DeclareOperation( "RestrictedPerm", [ IsRcwaMapping, IsListOrCollection ] );
DeclareOperation( "PermutationOpNC",
 [ IsObject, IsListOrCollection, IsFunction ] );

#############################################################################
##
#S Right inverses of injective rcwa mappings. //////////////////////////////
##
#############################################################################

#############################################################################
##
#A RightInverse( <f> ) . . . . . . . . . . . . . . . . right inverse of <f>
##
## The right inverse of <f>, i.e. a mapping g such that fg = 1.
## The mapping <f> must be injective.
##
DeclareAttribute( "RightInverse", IsRcwaMapping );

#############################################################################
##
#O CommonRightInverse( <l>, <r> ) . . . . . mapping d such that ld = rd = 1
##
## Returns a mapping d such that ld = rd = 1.
## The mappings <l> and <r> must be injective, and their images must form
## a partition of the underlying ring.
##
DeclareOperation( "CommonRightInverse", [ IsRcwaMapping, IsRcwaMapping ] );

#############################################################################
##
#S Transition graphs and transition matrices. //////////////////////////////
##
#############################################################################

#############################################################################
##
#O TransitionGraph( <f>, <m> ) . . transition graph of the rcwa mapping <f>
#O TransitionGraph( <f> )
##
## Returns the transition graph for modulus <m> of the rcwa mapping <f>.
##
## We define the *transition graph* Gamma_(f,m) for modulus m of an
## rcwa mapping f as follows:
##
## - The vertices are the residue classes (mod m).
##
## - There is an edge from r1(m) to r2(m) if and only if there is some
## n1 in r1(m) such that n1^f in r2(m).
##
## If the argument <m> is omitted, the vertices are taken to be the largest
## residue classes on which <f> is affine and which <f> does not fix
## pointwise.
##
DeclareOperation( "TransitionGraph", [ IsRcwaMapping, IsRingElement ] );
DeclareOperation( "TransitionGraph", [ IsRcwaMapping ] );

#############################################################################
##
#O TransitionMatrix( <f>, <m> ) . . transition matrix of <f> for modulus <m>
#O TransitionMatrix( <f> )
##
## Returns the *transition matrix* T of <f> for modulus <m>.
##
## The entry T_(i,j) is the "proportion" of the elements of the th
## residue class which are mapped to the <j>th residue class under <f>.
## The numbering of the residue classes is the same as in the corresponding
## return value of the function `AllResidues'.
##
## If the argument <m> is omitted, the vertices are taken to be the largest
## residue classes on which <f> is affine and which <f> does not fix
## pointwise.
##
DeclareOperation( "TransitionMatrix", [ IsRcwaMapping, IsRingElement ] );
DeclareOperation( "TransitionMatrix", [ IsRcwaMapping ] );

#############################################################################
##
#A Sources( <f> )
#A Sinks( <f> )
#A Loops( <f> )
##
## Let <f> be an rcwa mapping with modulus m.
## Then `Sources(<f>)' and `Sinks(<f>)' are lists of unions of residue
## classes (mod m), and `Loops(<f>)' is a list of residue classes (mod m).
##
## The list `Sources(<f>)' contains an entry for any strongly connected
## component of the transition graph of <f> for modulus m which has only
## outgoing edges. The list entry corresponding to a given such strongly
## connected component is just the union of its vertices. The description of
## the list `Sinks(<f>)' is obtained by replacing "outgoing" by "ingoing".
##
## The entries of the list `Loops(<f>)' are the residue classes (mod m)
## which <f> does not fix setwise, but which intersect nontrivially
## with their images under <f>.
##
DeclareAttribute( "Sources", IsRcwaMapping );
DeclareAttribute( "Sinks", IsRcwaMapping );
DeclareAttribute( "Loops", IsRcwaMapping );

#############################################################################
##
#O OrbitsModulo( <M>, <m>, <d> ) "orbit" partition of (R/<m>R)^<d> under <M>
#O OrbitsModulo( <M>, <m> ) . . . . . . . . . . . . . . . . . . case <d> = 1
#O OrbitsModulo( <f>, <m>, <d> ) . case <M> = Group(<f>) resp. Monoid(<f>)
#O OrbitsModulo( <f>, <m> ) . . . . . . . . . . . . . . . dito, case <d> = 1
##
## The definition given below is a generalization of the one given in the
## manual, and it should be taken with notable caution: it is not clear yet
## whether it makes sense in the given form, and it is likely to be changed
## or withdrawn.
##
## The operation `OrbitsModulo' returns a partition of (R/<m>R)^<d> into
## "orbits" under the action of the rcwa monoid <M>, in the sense that two
## tuples (a_1,...,a_<d>) and (b_1,...,b_<d>) of residues (mod <m>) lie in
## the same "orbit" if and only if there is an f in <M> such that one of the
## following hold:
##
## 1. ((a_1)^f mod <m>,...,(a_<d>)^f mod <m>)
## = ((b_1)^f mod <m>,...,(b_<d>)^f mod <m>).
## 2. ((b_1)^f mod <m>,...,(b_<d>)^f mod <m>)
## = ((a_1)^f mod <m>,...,(a_<d>)^f mod <m>).
##
## In case R = Z, the residues (mod <m>) are the integers 0,...,<m>-1.
## 1-tuples are represented by the ring element they contain.
##
## If the first argument is an rcwa mapping <f>, then <M> is the group
## generated by <f> if <f> is bijective, and the monoid generated by <f>
## otherwise. If <d> is not given, it defaults to 1.
##
## If the first argument is an rcwa mapping <f> and <d> = 1, then the
## return value as described above equals the set of the sets of vertices
## of the weakly-connected components of the transition graph
## Gamma_(<f>,<m>).
##
DeclareOperation( "OrbitsModulo", [ IsRcwaMonoid, IsRingElement ] );
DeclareOperation( "OrbitsModulo", [ IsRcwaMonoid, IsRingElement,
 IsPosInt ] );
DeclareOperation( "OrbitsModulo", [ IsRcwaMapping, IsRingElement ] );
DeclareOperation( "OrbitsModulo", [ IsRcwaMapping, IsRingElement,
 IsPosInt ] );

#############################################################################
##
#O FactorizationOnConnectedComponents( <f>, <m> )
##
## Returns the set of restrictions of the rcwa mapping <f> to the weakly-
## connected components of its transition graph Gamma_(<f>,<m>).
## These mappings have pairwise disjoint supports, hence any two of them
## commute, and their product equals <f>.
##
DeclareOperation( "FactorizationOnConnectedComponents",
 [ IsRcwaMapping, IsRingElement ] );

#############################################################################
##
#F TransitionSets( <f>, <m> ) . . . . . . . . . . . . set transition matrix
##
## Returns the *set transition matrix* <T> of <f> for modulus <m>.
##
## The entry T_(i,j) is the subset of the th residue class which is
## mapped to the <j>th residue class under <f>. The numbering of the residue
## classes is the same as in the corresponding return value of the function
## `AllResidues'.
##
DeclareGlobalFunction( "TransitionSets" );

#############################################################################
##
#S Trajectories. ///////////////////////////////////////////////////////////
##
#############################################################################

#############################################################################
##
#O Trajectory( <f>, <n>, <length> ) . . . trajectory of <f> starting at <n>
#O Trajectory( <f>, <n>, <length>, <m> )
#O Trajectory( <f>, <n>, <length>, <whichcoeffs> )
#O Trajectory( <f>, <n>, <terminal> )
#O Trajectory( <f>, <n>, <terminal>, <m> )
#O Trajectory( <f>, <n>, <terminal>, <whichcoeffs> )
##
## In the first case, this operation returns a list of the first <length>
## iterates in the trajectory of the rcwa mapping <f> starting at <n>.
## In the forth case it returns the initial part of the trajectory of <f>
## starting at <n> which ends at the first occurence of an iterate in the
## set <terminal>.
## In place of the ring element <n>, a finite set of ring elements or a
## union of residue classes can be given. In the second and fifth case the
## iterates are reduced (mod <m>) to save memory.
##
## In the third and sixth case the operation returns a list of "accumulated
## coefficients" on the trajectory of <n> under the rcwa mapping <f>.
## The term "accumulated coefficients" denotes the list c of coefficient
## triples such that for any k we have <n>^(<f>^(k-1)) = (c[k][1]*<n> +
## c[k][2])/c[k][3]. The argument <whichcoeffs> can either be "AllCoeffs" or
## "LastCoeffs", and determines whether the entire list of triples or only
## the last triple is computed.
##
DeclareOperation( "Trajectory", [ IsRcwaMapping, IsObject, IsObject ] );
DeclareOperation( "Trajectory", [ IsRcwaMapping, IsObject, IsObject,
 IsObject ] );

#############################################################################
##
#F GluckTaylorInvariant( <l> ) . . Gluck-Taylor invariant of trajectory <l>
##
## Returns the Gluck-Taylor invariant of the list <l> of integers,
## interpreted as the trajectory of an rcwa mapping. See
##
## David Gluck and Brian D. Taylor: A New Statistic for the 3x+1 Problem,
## Proc. Amer. Math. Soc. 130 (2002), 1293-1301.
##
DeclareGlobalFunction( "GluckTaylorInvariant" );

#############################################################################
##
#F TraceTrajectoriesOfClasses( <f>, <S>, <maxlength> )
##
## Traces the trajectories of the residue classes in the residue class union
## <S> under the mapping <f>. All iterates are written as a list of single
## residue classes. This list is computed using the function
## `AsUnionOfFewClasses' from the `ResClasses' package.
##
## The function stops once it detects a cycle, once the list of iterates
## reaches length <maxlength> or once it detects that a timeout given as
## option "timeout" has expired.
##
## The resulting list of lists of residue classes is returned.
##
## Caution: All classes are traced separately, thus a cycle in the
## trajectory usually does only cause a cycle in the list of
## *unions* of the returned sets of residue classes!
##
DeclareGlobalFunction( "TraceTrajectoriesOfClasses" );

#############################################################################
##
#S Further attributes of rcwa mappings. ////////////////////////////////////
##
#############################################################################

#############################################################################
##
#A SmallestRoot( <f> ) . . . . . . . . smallest root of the rcwa mapping <f>
#A PowerOverSmallestRoot( <f> )
#A BaseRoot( <f> )
#A PowerOverBaseRoot( <f> )
##
## We say that g is a *smallest root* of f if for some k we have f = g^k,
## but h^l = g implies that l is coprime to the order of g. Smallest roots
## are in general obviously not unique, and also do not need to exist.
## The second-mentioned attribute stores the value of k.
## The third- and fourth-mentioned attributes are technical "equivalents"
## where no minimality is guaranteed.
##
DeclareAttribute( "SmallestRoot", IsRcwaMapping );
DeclareAttribute( "PowerOverSmallestRoot", IsRcwaMapping );
DeclareAttribute( "BaseRoot", IsRcwaMapping );
DeclareAttribute( "PowerOverBaseRoot", IsRcwaMapping );

#############################################################################
##
#S Probabilistic guesses. //////////////////////////////////////////////////
##
#############################################################################

#############################################################################
##
#O LikelyContractionCentre( <f>, <maxn>, <bound> ) likely contraction centre
##
## Returns a guess of what the *contraction centre* of the rcwa mapping <f>
## might be.
##
## Assuming its existence, the *contraction centre* is the unique finite
## subset S_0 of the base ring R which <f> maps bijectively to itself and
## which intersects nontrivially with any trajectory of <f>.
##
## The mapping <f> is assumed to be contracting.
##
## As in general contraction centres are likely not computable, methods
## will be probabilistic. The argument <maxn> is a bound on the starting
## value and <bound> is a bound on the elements of the sequence to be
## searched. If the limit <bound> is exceeded, an Info message on Info
## level 3 of InfoRCWA is given.
##
DeclareOperation( "LikelyContractionCentre",
 [ IsRcwaMapping, IsRingElement, IsPosInt ] );
DeclareSynonym( "LikelyContractionCenter", LikelyContractionCentre );

#############################################################################
##
#O GuessedDivergence( <f> ) . . . . . . . . . . . guessed divergence of <f>
##
## Returns a guess of what one might call the "divergence" of the rcwa
## mapping <f>. This should give a rough hint on how fast the rcwa mapping
## <f> contracts (if its divergence is smaller than 1) or how fast its
## trajectories diverge (if its divergence is larger than 1).
## Nothing particular is guaranteed, and no mathematical conclusions can
## be made from the return values.
##
DeclareOperation( "GuessedDivergence", [ IsRcwaMapping ] );

#############################################################################
##
#S LaTeX output. ///////////////////////////////////////////////////////////
##
#############################################################################

#############################################################################
##
#A LaTeXString( <obj> ) . . . . . . . . . . . LaTeX string for object <obj>
##
DeclareAttribute( "LaTeXString", IsObject );

#############################################################################
##
#O LaTeXStringRcwaMapping( <f> )
#O LaTeXStringRcwaGroup( <G> )
##
## Returns a LaTeX string for an rcwa mapping <f>, resp. an rcwa group <G>.
## Methods for `LaTeXStringRcwaMapping' recognize options "Factorization",
## "Indentation", "German" and "VarName" / "VarNames".
##
DeclareOperation( "LaTeXStringRcwaMapping", [ IsRcwaMapping ] );
DeclareOperation( "LaTeXStringRcwaGroup", [ IsRcwaGroup ] );

#############################################################################
##
#O LaTeXAndXDVI( <obj> ) . write LaTeX string to file, LaTeX & show by xdvi
##
DeclareOperation( "LaTeXAndXDVI", [ IsObject ] );

#############################################################################
##
#S Attributes and properties which do not depend on the representation. ////
##
#############################################################################

BindGlobal( "RCWA_REP_INDEPENDENT_ATTRIBUTES",
 [ "Source", "Range", "Support", "MovedPoints", "Order",
 "Multiplier", "Divisor", "PrimeSet", "MaximalShift",
 "IncreasingOn", "DecreasingOn", "ImageDensity",
 "Sources", "Sinks", "Loops", "TransposedClasses",
 "RotationFactor", "LargestSourcesOfAffineMappings" ] );

BindGlobal( "RCWA_REP_INDEPENDENT_PROPERTIES",
 [ "IsInjective", "IsSurjective", "IsBalanced", "IsIntegral",
 "IsClassWiseTranslating", "IsClassWiseOrderPreserving",
 "IsSignPreserving", "IsTame",
 "IsClassShift", "IsPowerOfClassShift",
 "IsClassReflection", "IsClassRotation",
 "IsClassTransposition",
 "IsGeneralizedClassTransposition", "IsPrimeSwitch" ] );

#############################################################################
##
#E rcwamap.gd . . . . . . . . . . . . . . . . . . . . . . . . . . ends here

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.24 Sekunden ¤

Normalansicht

Suchen

PVS Prover

Isabelle Prover

NIST Cobol Testsuite

Cephes Mathematical Library

Vienna Development Method

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.