In this manual, we only give short definitions of the most important terms in this context.
Let R be a commutative principal ideal domain without zero-divisors, such that for all non-zero ideals I of R, the quotient |R/I| is finite.
We call a mapping f from R to itself residue class-wise affine if there is a non-zero ideal I_f of R such that f is given on each residue class r + I_f in R/I_f by
n --> ( a_r * n + b_r ) / c_r
for some coefficients a_r, b_r, c_r in R. In this case, we say that f is an rcwa mapping.
We always assume that all fractions are reduced, i.e. that gcd( a_r, b_r, c_r ) = 1, and that I_f is the largest ideal having the described property.
We define the modulus Mod(f) of f as the (up to multiplication by units uniquely determined) element m_f generating the ideal I_f.
We define the multiplier Mult(f) of f as the standard associate of the least common multiple of the coefficients a_r in the numerators.
We define the divisor Div(f) of f as the standard associate of the least common multiple of the coefficients c_r in the denominators.
We say that an rcwa mapping is flat in case its multiplier and divisor are both equal to 1.
In case that the underlying ring R is the ring of integers, we call an rcwa mapping f an integral rcwa mapping, in case R = Z_pi for a set of primes pi we call f a semilocal integral rcwa mapping and in case R is a polynomial ring in one variable over a finite field we call f a modular rcwa mapping. Since integral and semilocal integral rcwa mappings share many important properties, we make use of the generic term rational-based rcwa mapping.
We call a rational-based rcwa mapping class-wise order-preserving if its restriction to any residue class modulo its modulus is order-preserving.
We define the graph G_f associated to an rcwa mapping f with modulus m as follows:
The vertices are the residue classes (mod m).
There is an edge from r_1(m) to r_2(m) if and only if there is some n_1 in r_1(m) such that n_1^f in r_2(m).
We define the transition matrix M of degree d of the integral rcwa mapping f by M_i+1,j+1 = 1 if there is an n = i (mod d) such that n^f = j (mod d), and 0 if not. Their rank (and in case it is invertible the absolute value of its determinant) does not depend on the particular assignment of the residue classes (mod d) to rows/columns, hence accordingly, we can define the transitional rank resp. the transitional determinant of f of degree d for any rcwa mapping.
We define the prime set of an rcwa mapping f as the set of all prime elements dividing the modulus of f or some coefficient a_r or c_r (in the notation used above).
We set RCWA(R) := { g in Sym(R) | g is residue class-wise affine }.
The set RCWA(R) is closed under multiplication and taking inverses (this can be verified easily), hence forms a subgroup of Sym(R). Since R contains no zero-divisors and the quotients R/I are all finite, this subgroup is proper.
We call a subgroup of RCWA(R) a residue class-wise affine group, or shortly, an rcwa group.
We call an rcwa group flat if all of its elements are.
We call an integral rcwa group class-wise order-preserving if all of its elements are.
We define the prime set of an rcwa group as the union of the prime sets of its elements.
We define the modulus of an rcwa group G as the least common multiple of the moduli of its elements in case this is finite, and zero otherwise.
We say that an R-rcwa mapping f is tame if and only if the moduli of its powers are bounded, and wild otherwise. Furthermore, we say that an R-rcwa group is tame if and only if its modulus is strictly positive, and wild otherwise.
We define an (R-) rcwa representation of a group G as an homomorphism from G to RCWA(R).
For an introduction to this topic, see [K02].
generated by GAPDoc2HTML