Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | 6 | Bib | Ind

### 2. Residue Class-Wise Affine Mappings

This chapter describes the functionality provided by this package for computing with residue class-wise affine mappings.

#### 2.1 Basic definitions

Let R be an infinite euclidean domain which is not a field and all of whose proper residue class rings are finite. A mapping f: R -> R is called residue class-wise affine, or in short an rcwa mapping, if there is an m in R \ 0 such that the restrictions of f to the residue classes r(m) in R/mR are affine. This means that for any residue class r(m) there are coefficients a_r(m), b_r(m), c_r(m) in R, such that the restriction of the mapping f to the set r(m) = r+km | k in R is given by

f|_r(m): r(m) -> R, n -> ( a_r(m) * n + b_r(m) ) / c_r(m).

The value m is called the modulus of f. It is understood 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 cannot divide by 0, the coefficients a_r(m), b_r(m) and c_r(m) can be any ring elements.

When talking about the product of some rcwa mappings, it is always meant their composition as mappings, and by the inverse of a bijective rcwa mapping it is meant its inverse mapping. Products are evaluated from the left to the right.

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). A subgroup of RCWA(R) is called a residue class-wise affine group, or in short an rcwa group.

#### 2.2 Entering rcwa mappings

In order to define an rcwa mapping, it is necessary to specify the underlying ring R, the modulus m and the coefficients a_r(m), b_r(m) and c_r(m) for r(m) running over the residue classes (mod m).

A coefficient list for an rcwa mapping with modulus m consists of |R/mR| coefficient triples `[ a_rm, b_rm, c_rm ]`. Their ordering is determined by the ordering of the representatives of the residue classes (mod m) in the sorted list returned by `AllResidues(R, m)`. For R = Z, this means that the coefficient triple for the residue class 0(m) comes first, then comes the one for 1(m), the one for 2(m) and so on.

The easiest way to enter a given rcwa mapping is by `RcwaMapping( [ R, m, ] coeffs )`. If the arguments R and m are omitted, they default to `Integers` resp. the length of the coefficient list coeffs. If the given coefficients would enforce a division by zero or images of elements of R outside R, an error message is printed and a break loop is entered. For example, the coefficient triple `[1,1,3]` at the first position is not allowed if R is the ring of integers. The reason for this is that not all integers congruent to 0 + 1 = 1 mod m are divisible by 3.

    gap> T := RcwaMapping([[1,0,2],[3,1,2]]); # The Collatz mapping.
    <rcwa mapping of Z with modulus 2>
    gap> SetName(T,"T"); Display(T);

    Rcwa mapping of Z with modulus 2

                    n mod 2                |                 n^T
    ---------------------------------------+--------------------------------------
      0                                    | n/2
      1                                    | (3n + 1)/2

In the sequel, a description of the general-purpose constructor for rcwa mappings is given. This might look a bit technical on a first glance. For getting started, the reader may find it easier to look first at the functions for constructing some kinds of particularly simple-structured bijective rcwa mappings of Z described afterwards.

##### 2.2-1 RcwaMapping

`> RcwaMapping`( R, m, coeffs ) | ( method )

`> RcwaMapping`( R, coeffs ) | ( method )

`> RcwaMapping`( coeffs ) | ( method )

`> RcwaMapping`( perm, range ) | ( method )

`> RcwaMapping`( m, values ) | ( method )

`> RcwaMapping`( pi, coeffs ) | ( method )

`> RcwaMapping`( q, m, coeffs ) | ( method )

`> RcwaMapping`( P1, P2 ) | ( method )

`> RcwaMapping`( cycles ) | ( method )

Returns: An rcwa mapping.

Construction of an rcwa mapping.

In all cases the argument R is the underlying ring, m is the modulus and coeffs is the coefficient list as described above. In case one or several of these arguments are omitted or replaced by other arguments, they are either derived from the latter or default values are taken. The meaning of the other arguments is defined in the detailed description of the particular methods given in the sequel. The above methods return the rcwa mapping

(a)

  of R with modulus modulus 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 the range range, resp.

(e)

  of R = Z with modulus modulus and values prescribed by the list val, which consists of 2*modulus pairs giving preimage and image for 2 points per residue class (mod modulus), resp.

(f)

  of Z_(pi) with modulus `Length(coeffs)` and coefficients coeffs (the set of primes pi denoting the underlying ring is given as argument pi), resp.

(g)

  of GF(q)[x] with modulus modulus and coefficients coeffs, resp.

(h)

  an arbitrary rcwa mapping which induces a bijection between the partitions P1 and P2 of R into disjoint single residue classes and which is affine on the elements of P1, resp.

(i)

  an arbitrary rcwa mapping with "residue class cycles" as given by cycles. The latter is a list of lists of disjoint residue classes which the mapping should permute cyclically, each.

The methods for the operation `RcwaMapping` perform a number of argument checks, which can be skipped by using `RcwaMappingNC` instead.

    gap> f := RcwaMapping([[1,1,1],[1,-1,1],[1,1,1],[1,-1,1]]);
    <rcwa mapping of Z with modulus 2>
    gap> f = RcwaMapping((2,3),[2..3]);
    true
    gap> g := RcwaMapping((1,2,3)(8,9),[4..20]);
    <rcwa mapping of Z with modulus 17>
    gap> Action(Group(g),[4..20]);
    Group([ (5,6) ])
    gap> T = RcwaMapping(2,[[1,2],[2,1],[3,5],[4,2]]);
    true
    gap> t := RcwaMapping(1,[[-1,1],[1,-1]]); # The involution n -> -n.
    Rcwa mapping of Z: n -> -n
    gap> d := RcwaMapping([2],[[1/3,0,1]]);
    Rcwa mapping of Z_( 2 ): n -> 1/3 n
    gap> RcwaMapping([2,3],ShallowCopy(Coefficients(T)));
    <rcwa mapping of Z_( 2, 3 ) with modulus 2>
    gap> u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);
    <rcwa mapping of Z with modulus 5>
    gap> x := Indeterminate(GF(2),1);; SetName(x,"x");
    gap> R := PolynomialRing(GF(2),1); z := Zero(R);; e := One(R);;
    GF(2)[x]
    gap> r := RcwaMapping( R, x^2 + e,
    >                      [ [ x^2 + x + e, z      , x^2 + e ],
    >                        [ x^2 + x + e, x      , x^2 + e ],
    >                        [ x^2 + x + e, x^2    , x^2 + e ],
    >                        [ x^2 + x + e, x^2 + x, x^2 + e ] ] );
    <rcwa mapping of GF(2)[x] with modulus x^2+Z(2)^0>
    gap> rc := function(r,m) return ResidueClass(DefaultRing(m),m,r); end;;
    gap> f1 := RcwaMapping([[rc(1,6),rc(0, 8)],[rc(5,6),rc(4, 8)]]);;
    gap> f2 := RcwaMapping([[rc(1,6),rc(0, 4)],[rc(5,6),rc(2, 4)]]);;
    gap> f3 := RcwaMapping([[rc(2,6),rc(1,12)],[rc(4,6),rc(7,12)]]);;
    gap> List([f1,f2,f3],Order);
    [ 2, 2, 2 ]
    gap> f := f1*f2*f3;
    <bijective rcwa mapping of Z with modulus 12>
    gap> Order(f);
    infinity
    gap> a := RcwaMapping([rc(0,2),rc(1,4),rc(3,4)],[rc(0,3),rc(1,3),rc(2,3)]);
    <rcwa mapping of Z with modulus 4>
    gap> [rc(0,2),rc(1,4),rc(3,4)]^a;
    [ 0(3), 1(3), 2(3) ]
    gap> Cycle(a,44);
    [ 44, 66, 99, 74, 111, 83, 62, 93, 70, 105, 79, 59 ]

Some kinds of very simple-structured rcwa mappings are of particular interest:

##### 2.2-2 ClassShift

`> ClassShift`( r, m ) | ( function )

Returns: The class shift nu_r(m).

The class shift nu_r(m) is the rcwa mapping of Z which maps n in r(m) to n + m and fixes Z \ r(m) pointwise. The residue class `ResidueClass(r,m)` itself can be given in place of the arguments r and m. Enclosing the argument list in list brackets is permitted.

    gap> Display(ClassShift(5,12));

    Tame bijective rcwa mapping of Z with modulus 12, of order infinity

                   n mod 12                |          n^ClassShift(5,12)
    ---------------------------------------+--------------------------------------
       0  1  2  3  4  6  7  8  9 10 11     | n
       5                                   | n + 12

##### 2.2-3 ClassReflection

`> ClassReflection`( r, m ) | ( function )

Returns: The class reflection varsigma_r(m).

The class reflection varsigma_r(m) is the rcwa mapping of Z which maps n in r(m) to -n + 2r and fixes Z \ r(m) pointwise. The residue class `ResidueClass(r,m)` itself can be given in place of the arguments r and m. Enclosing the argument list in list brackets is permitted.

    gap> Display(ClassReflection(5,9));

    Bijective rcwa mapping of Z with modulus 9, of order 2

                    n mod 9                |        n^ClassReflection(5,9)
    ---------------------------------------+--------------------------------------
      0 1 2 3 4 6 7 8                      | n
      5                                    | -n + 10

##### 2.2-4 ClassTransposition

`> ClassTransposition`( r1, m1, r2, m2 ) | ( function )

Returns: The class transposition tau_r_1(m_1),r_2(m_2).

The class transposition tau_r_1(m_1),r_2(m_2) is an rcwa mapping of Z of order 2 which interchanges the disjoint residue classes r_1(m_1) and r_2(m_2) of Z and fixes the complement of their union pointwise. The residue classes `ResidueClass(r1,m1)` and `ResidueClass(r2,m2)` themselves can be given in place of the arguments r1, m1, r2 and m2. Enclosing the argument list in list brackets is permitted.

    gap> Display(ClassTransposition(1,2,8,10));

    Bijective rcwa mapping of Z with modulus 10, of order 2

                   n mod 10                |    n^ClassTransposition(1,2,8,10)
    ---------------------------------------+--------------------------------------
       0  2  4  6                          | n
       1  3  5  7  9                       | 5n + 3
       8                                   | (n - 3)/5

##### 2.2-5 PrimeSwitch

`> PrimeSwitch`( p ) | ( function )

`> PrimeSwitch`( p, k ) | ( function )

Returns: In the one-argument form the prime switch sigma_p := 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), and in the two-argument form the restriction of sigma_p by n -> kn (cp. `Restriction` (3.7-1)).

For an odd prime p, the prime switch sigma_p is a bijective rcwa mapping of Z with modulus 4p, multiplier p (see `Multiplier` (2.6-1)) and divisor 2 (see `Divisor` (2.6-2)). The prime switches sigma_p play an important role in factoring non-balanced rcwa mappings into class shifts, class reflections and class transpositions (cp. `FactorizationIntoGenerators` (2.4-1)).

    gap> Display(PrimeSwitch(3));

    Wild bijective rcwa mapping of Z with modulus 12

                   n mod 12                |           n^PrimeSwitch(3)
    ---------------------------------------+--------------------------------------
       0                                   | n/2
       1  7                                | n + 1
       2  6 10                             | (3n + 4)/2
       3  9                                | n
       4                                   | n - 3
       5  8 11                             | n - 1

In most cases an rcwa mapping is not determined uniquely by the output of the `ViewObj` method -- in these cases the output is enclosed in brackets. There are methods installed for `Display`, `Print` and `String`. The `Print`ed representation of an rcwa mapping is GAP - readable if and only if the `Print`ed representation of the elements of the underlying ring is so. There is also a method for `LaTeXObj`:

##### 2.2-6 LaTeXObj

`> LaTeXObj`( f ) | ( method )

Returns: A LaTeX representation of the integral rcwa mapping f.

The output makes use of the LaTeX macro package amsmath. If the option Factorization is set, a factorization of f into class shifts, class reflections, class transpositions and prime switches is printed (cp. `FactorizationIntoGenerators` (2.4-1)). For rcwa mappings with modulus larger than 1, an indentation by Indentation characters can be specified by setting this option value accordingly.

    gap> Print(LaTeXObj(a));
    n \ \longmapsto \
    \begin{cases}
      \frac{3n}{2}     & \text{if} \ n \in 0(2), \\
      \frac{3n + 1}{4} & \text{if} \ n \in 1(4), \\
      \frac{3n - 1}{4} & \text{if} \ n \in 3(4).
    \end{cases}
    gap> Print(LaTeXObj(Comm(a,ClassShift(0,4)):Factorization));
          &\nu_{8(12)} \cdot \nu_{0(12)}^{-1}
     \cdot \tau_{0(12),6(12)} \cdot \tau_{0(12),4(12)}
     \cdot \tau_{0(12),8(12)}

The `Display` method recognizes the option xdvi. If this option is set, the given rcwa mapping is displayed in an xdvi window. For this purpose, the string returned by the `LaTeXObj` - method described above is inserted into a LaTeX template file. This file is LaTeX'ed, and the result is shown with xdvi. This works only on a UNIX system, and requires suitable installations of LaTeX and xdvi.

#### 2.3 Basic functionality for rcwa mappings

Checking whether two rcwa mappings are equal is cheap. Rcwa mappings can be multiplied, thus there is a method for `*`. Bijective rcwa mappings can also be inverted, thus there is a method for `Inverse`. The latter method is usually accessed by raising a mapping to some power with negative exponent. Multiplying, inverting and exponentiating tame rcwa mappings is cheap. Computing powers of wild mappings is usually expensive -- runtime and memory requirements normally grow approximately exponentially with the exponent. How expensive multiplying a couple of wild mappings is, varies very much. In any case, the amount of memory required for storing an rcwa mapping is proportional to its modulus. Whether a given mapping is tame or wild can be determined by the operation `IsTame`. There are methods for `Order`, which can not only compute a finite order, but are also suitable for detecting infinite order.

    gap> List([-6..6],k->Modulus(f^k)); Order(f);
    [ 324, 108, 108, 36, 36, 12, 1, 12, 24, 48, 96, 192, 384 ]
    infinity
    gap> List( [ a, u, f ], IsTame );
    [ false, false, false ]
    gap> f^2*u;
    <bijective rcwa mapping of Z with modulus 120>
    gap> f^2*u*a^2*f^-1;
    <bijective rcwa mapping of Z with modulus 3840>
    gap> Comm(f,ClassShift(6,12)*f)^1000;
    <bijective rcwa mapping of Z with modulus 18>

There are methods installed for `IsInjective`, `IsSurjective`, `IsBijective` and `Image`.

    gap> [ IsInjective(T), IsSurjective(T), IsBijective(u) ];
    [ false, true, true ]
    gap> Image(RcwaMapping([[-4,-8,1]]));
    0(4)

Images of elements, of finite sets of elements and of unions of finitely many residue classes of the source of an rcwa mapping can be computed with `^` (the same symbol as used for exponentiation and conjugation). The same works for partitions of the source into a finite number of residue classes.

    gap> [ 15^T, 7^d, (x^3+x^2+x+One(R))^r ];
    [ 23, 7/3, x^3+Z(2)^0 ]
    gap> A := ResidueClass(Integers,3,2);;
    gap> [ A^T, A^u ];
    [ 1(3) U 8(9), 1(9) U 3(9) U 14(27) U 20(27) U 26(27) ]
    gap> [rc(0,2),rc(1,4),rc(3,4)]^f;
    [ 0(6) U 1(6) U 5(6), 2(12) U 4(12) U 9(12), 3(12) U 8(12) U 10(12) ]

For computing preimages of elements under rcwa mappings, there are methods for `PreImageElm` and `PreImagesElm`. The preimage of a finite set of ring elements or of a union of finitely many residue classes under an rcwa mapping can be computed using `PreImage`.

    gap> [ PreImageElm(d,37/17), PreImagesElm(T,8), PreImagesElm(Zero(T),0) ];
    [ 111/17, [ 5, 16 ], Integers ]
    gap> PreImage(T,ResidueClass(Integers,3,2));
    1(2) U 4(6)
    gap> M := [1];; l := [1];;
    gap> while Length(M) < 10000 do M := PreImage(T,M); Add(l,Length(M)); od; l;
    [ 1, 1, 2, 2, 4, 5, 8, 10, 14, 18, 26, 36, 50, 67, 89, 117, 157, 208, 277,
      367, 488, 649, 869, 1154, 1534, 2039, 2721, 3629, 4843, 6458, 8608, 11472 ]

There is a method for the operation `MovedPoints` for computing the support of a bijective rcwa mapping, and there is a method for `RestrictedPerm` for computing the restriction of a bijective rcwa mapping to a union of residue classes it fixes setwisely.

    gap> [ MovedPoints(u), MovedPoints(u^2) ];
    [ Z \ [ -1, 0 ], Z \ [ -10, -6, -1, 0, 1, 2, 3, 5 ] ]
    gap> MovedPoints(r);
    GF(2)[x] \ [ 0*Z(2), Z(2)^0, x, x+Z(2)^0 ]
    gap> RestrictedPerm(f,ResidueClassUnion(Integers,36,[7,8]));
    <rcwa mapping of Z with modulus 36>

Rcwa mappings can be added and subtracted pointwisely. However, please note that the set of rcwa mappings of some ring does not form a ring under `+` and `*`.

    gap> a  := RcwaMapping([[3,0,2],[3,1,4],[3,0,2],[3,-1,4]]);;
    gap> b  := ClassShift(1,4) * a;;
    gap> [ Image((a + b)), Image((a - b)) ];
    [ 0(6) U 4(6) U 5(6), [ -3, 0 ] ]
    gap> d+d+d;
    IdentityMapping( Z_( 2 ) )

There are operations `Modulus` (abbreviated `Mod`) and `Coefficients` for extracting the modulus resp. the coefficient list of a given rcwa mapping. The meaning of the return values is as described in the previous section. General documentation for most operations mentioned in this section can be found in the GAP reference manual. For rcwa mappings of rings other than Z, not for all operations applicable methods are available.

#### 2.4 Factoring rcwa mappings

Factoring group elements into elements of some "nice" set of generators is often helpful. The following can be seen as an attempt towards getting a satisfactory solution to this problem for the group RCWA(Z):

##### 2.4-1 FactorizationIntoGenerators

`> FactorizationIntoGenerators`( g ) | ( attribute )

Returns: A factorization of the bijective rcwa mapping g into class shifts, class reflections and class transpositions, provided that such a factorization exists and the method finds it.

This may return `fail`, stop with an error message or run into an infinite loop. If it returns a result, this result is always correct. By default, prime switches are taken as one factor. If the option ExpandPrimeSwitches is set, they are each decomposed into the 6 class transpositions given in the definition (see `PrimeSwitch` (2.2-5)). By default, the factoring process begins with splitting off factors from the right. This can be changed by setting the option Direction to `"from the left"`. By default, the coarsest possible respected partition of the integral mapping occuring in the final stage of the algorithm is computed. This can be suppressed by setting the option ShortenPartition equal to `false`. By default, at the end it is checked whether the product of the determined factors indeed equals g. This check can be suppressed by setting the option NC.

The problem of obtaining a factorization as desired is algorithmically difficult, and this factorization routine is currently perhaps the most sophisticated part of the RCWA package. Information about the progress of the factorization process can be obtained by setting the info level of the Info class `InfoRCWA` (6.4-1) to 2.

    gap> FactorizationIntoGenerators(Comm(a,b));
    [ ClassShift(7,9), ClassShift(1,9)^-1, ClassTransposition(1,9,4,9),
      ClassTransposition(1,9,7,9), ClassTransposition(6,18,15,18),
      ClassTransposition(5,9,15,18), ClassTransposition(4,9,15,18),
      ClassTransposition(5,9,6,18), ClassTransposition(4,9,6,18) ]

For purposes of demonstrating the capabilities of the factorization routine, in Section 4.1 a permutation is factored which has already been mentioned by Lothar Collatz in 1932, and whose cycle structure is unknown so far.

#### 2.5 Determinant and sign

##### 2.5-1 Determinant

`> Determinant`( sigma ) | ( method )

`> Determinant`( sigma, S ) | ( method )

Returns: The determinant of the bijective rcwa mapping sigma.

The determinant of an affine mapping n -> (an+b)/c whose source is a residue class r(m) is defined by b/|a|m. This definition is extended additively to determinants of rcwa mappings and their restrictions to unions of residue classes.

Using the notation from the definition of an rcwa mapping, the determinant det(sigma) of an rcwa mapping sigma is given by (see LaTeX version of the manual).

In the author's thesis it is shown that the determinant mapping is an epimorphism from the group of all class-wise order-preserving bijective rcwa mappings of Z onto (Z,+) (see Theorem 2.11.9).

If a residue class union S is given as an additional argument, the method returns the determinant of the restriction of sigma to S.

    gap> nu := ClassShift(0,1);;
    gap> List( [ nu, a, b, u ], Determinant );
    [ 1, 0, 1, 0 ]
    gap> Determinant(u^2*b^-3);
    -3
    gap> Determinant(nu^7*a^2*nu^-1*b^-1*a^-3);
    5

##### 2.5-2 Sign

`> Sign`( sigma ) | ( attribute )

Returns: The sign of the bijective rcwa mapping sigma.

Using the notation from the definition of an rcwa mapping, the sign of a bijective rcwa mapping sigma of Z is defined by (see LaTeX version of the manual).

In the author's thesis it is shown that the sign mapping is an epimorphism from RCWA(Z) onto the group Z^times of units of Z (see Theorem 2.12.8). This means that the kernel of the sign mapping is a normal subgroup of RCWA(Z) of index 2.

    gap> List( [ nu, nu^2, nu^3 ], Sign );
    [ -1, 1, -1 ]
    gap> List( [ t, nu^3*t ], Sign );
    [ -1, 1 ]
    gap> List( [ a, a*b, (a*b)^2, Comm(a,b) ], Sign );
    [ 1, -1, 1, 1 ]

#### 2.6 Attributes and properties derived from the coefficients

##### 2.6-1 Multiplier

`> Multiplier`( f ) | ( attribute )

`> Mult`( f ) | ( attribute )

Returns: The multiplier of the rcwa mapping f.

In the notation used in the definition of an rcwa mapping, the multiplier is the lcm of the coefficients a_r(m) in the numerators.

    gap> List( [ g, u, T, d, r ], Multiplier );
    [ 1, 9, 3, 1, x^2+x+Z(2)^0 ]

##### 2.6-2 Divisor

`> Divisor`( f ) | ( attribute )

`> Div`( f ) | ( attribute )

Returns: The divisor of the rcwa mapping f.

In the notation used in the definition of an rcwa mapping, the divisor is the lcm of the coefficients c_r(m) in the denominators.

    gap> List( [ g, u, T, d, r ], Divisor );
    [ 1, 5, 2, 1, x^2+Z(2)^0 ]

##### 2.6-3 PrimeSet

`> PrimeSet`( f ) | ( operation )

Returns: The prime set of the rcwa mapping f.

The prime set of an rcwa mapping is the set of prime divisors of the product of its modulus, its multiplier and its divisor. See also `PrimeSet` (3.2-3) for rcwa groups.

    gap> PrimeSet(T);
    [ 2, 3 ]
    gap> List( [ u, T^u, T^(u^-1) ], PrimeSet );
    [ [ 3, 5 ], [ 2, 3 ], [ 2, 3, 5 ] ]
    gap> PrimeSet(r);
    [ x+Z(2)^0, x^2+x+Z(2)^0 ]

##### 2.6-4 IsIntegral

`> IsIntegral`( f ) | ( property )

Returns: `true` if the rcwa mapping f is integral and `false` otherwise.

An rcwa mapping is called integral if its divisor equals 1, thus "if no proper divisions occur". Computing with such mappings is particularly easy.

Be careful not to confuse this with the term integral rcwa mapping for rcwa mappings of the integers; normally it should be rather clear what is meant.

    gap> List( [ u, t, RcwaMapping([[2,0,1],[3,5,1]]) ], IsIntegral );
    [ false, true, true ]

##### 2.6-5 IsClassWiseOrderPreserving

`> IsClassWiseOrderPreserving`( f ) | ( property )

Returns: `true` if the rcwa mapping f is class-wise order-preserving and `false` otherwise.

The term class-wise order-preserving is defined only for rcwa mappings of ordered rings, e.g. Z.

    gap> List( [ g, u, T, t, d ], IsClassWiseOrderPreserving );
    [ true, true, true, false, true ]

#### 2.7 Functionality related to the affine partial mappings

##### 2.7-1 LargestSourcesOfAffineMappings

`> LargestSourcesOfAffineMappings`( f ) | ( attribute )

Returns: The coarsest partition of `Source(f)` on whose elements the rcwa mapping f is affine.

    gap> LargestSourcesOfAffineMappings(T);
    [ 0(2), 1(2) ]
    gap> List( [ u, u^-1 ], LargestSourcesOfAffineMappings );
    [ [ 0(5), 1(5), 2(5), 3(5), 4(5) ], [ 0(3), 1(3), 2(9), 5(9), 8(9) ] ]
    gap> LargestSourcesOfAffineMappings(t);
    [ Integers ]
    gap> kappa := RcwaMapping([[1,0,1],[1,0,1],[3,2,2],[1,-1,1],
    >                          [2,0,1],[1,0,1],[3,2,2],[1,-1,1],
    >                          [1,1,3],[1,0,1],[3,2,2],[2,-2,1]]);;
    gap> SetName(kappa,"kappa");
    gap> LargestSourcesOfAffineMappings(kappa);
    [ 2(4), 1(4) U 0(12), 3(12) U 7(12), 4(12), 8(12), 11(12) ]
    gap> LargestSourcesOfAffineMappings(r);
    [ 0*Z(2) ( mod x^2+Z(2)^0 ), Z(2)^0 ( mod x^2+Z(2)^0 ), x ( mod x^2+Z(2)^0 ),
      x+Z(2)^0 ( mod x^2+Z(2)^0 ) ]

##### 2.7-2 Multpk

`> Multpk`( f, p, k ) | ( operation )

Returns: The union of the residue classes r(m) such that p^k||a_r(m) if k >= 0, and the union of the residue classes r(m) such that p^k||c_r(m) if k <= 0.

    gap> [ Multpk(T,2,-1), Multpk(T,3,1) ];
    [ Integers, 1(2) ]
    gap> [ Multpk(u,3,0), Multpk(u,3,1), Multpk(u,3,2), Multpk(u,5,-1) ];
    [ [  ], 0(5) U 2(5), 1(5) U 3(5) U 4(5), Integers ]
    gap> [ Multpk(kappa,2,1), Multpk(kappa,2,-1), Multpk(kappa,3,1),
    >      Multpk(kappa,3,-1) ];
    [ 4(12) U 11(12), 2(4), 2(4), 8(12) ]

##### 2.7-3 SetOnWhichMappingIsClassWiseOrderPreserving

`> SetOnWhichMappingIsClassWiseOrderPreserving`( f ) | ( attribute )

`> SetOnWhichMappingIsClassWiseConstant`( f ) | ( attribute )

`> SetOnWhichMappingIsClassWiseOrderReversing`( f ) | ( attribute )

Returns: The union of the residue classes (mod `Modulus(f)`) on which the rcwa mapping f is class-wise order-preserving, class-wise constant resp. class-wise order-reversing.

The source of the rcwa mapping f must be ordered.

    gap> List( [ T, u, t ], SetOnWhichMappingIsClassWiseOrderPreserving );
    [ Integers, Integers, [  ] ]
    gap> SetOnWhichMappingIsClassWiseConstant(RcwaMapping([[2,0,1],[0,4,1]]));
    1(2)

#### 2.8 Transition graphs and transition matrices

##### 2.8-1 TransitionGraph

`> TransitionGraph`( f, m ) | ( operation )

Returns: The transition graph for modulus m of the rcwa mapping f.

The transition graph Gamma_f,m of f for modulus m is defined as follows:

1. The vertices are the residue classes (mod m).

2. 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).

The assignment of the residue classes (mod m) to the vertices of the graph is given by the ordering of the residues in `AllResidues(Source(f),m)`. The result is returned as a GRAPE-graph.

    gap> TransitionGraph(a,Modulus(a));
    rec( isGraph := true, order := 4, group := Group(()),
      schreierVector := [ -1, -2, -3, -4 ],
      adjacencies := [ [ 1, 3 ], [ 1, 2, 3, 4 ], [ 2, 4 ], [ 1, 2, 3, 4 ] ],
      representatives := [ 1, 2, 3, 4 ], names := [ 1, 2, 3, 4 ] )

##### 2.8-2 OrbitsModulo

`> OrbitsModulo`( f, m ) | ( operation )

Returns: The partition of `AllResidues(Source(f),m)` corresponding to the weakly-connected components of the transition graph for modulus m of the rcwa mapping f.

See also `OrbitsModulo` (3.5-6) for rcwa groups.

    gap> OrbitsModulo(Comm(a,b),9);
    [ [ 0 ], [ 1, 4, 5, 6, 7 ], [ 2 ], [ 3 ], [ 8 ] ]

##### 2.8-3 FactorizationOnConnectedComponents

`> FactorizationOnConnectedComponents`( f, m ) | ( operation )

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 pairwisely disjoint supports, hence any two of them commute, and their product equals f.

    gap> sigma := RcwaMapping([[1, 0,1],[1, 1,1],[2,2,1],[3,-3,2],
    >                          [1, 0,1],[1,-2,3],[3,6,2],[1,-2,1],
    >                          [1, 0,1],[1, 1,1],[1,1,1],[1,-2,1],
    >                          [2, 0,1],[1, 1,1],[1,1,1],[3,-3,2],
    >                          [1, 0,1],[1, 1,1],[3,6,2],[1,-2,1],
    >                          [1, 0,1],[1, 1,1],[1,1,1],[2,-4,1],
    >                          [1,-3,3],[1, 1,1],[1,1,1],[3,-3,2],
    >                          [1, 0,1],[2, 2,1],[3,6,2],[1,-2,1],
    >                          [1, 0,1],[1, 1,1],[1,1,1],[1,-2,1]]);
    <rcwa mapping of Z with modulus 36>
    gap> fact := FactorizationOnConnectedComponents(sigma,36);
    [ <rcwa mapping of Z with modulus 36>, <rcwa mapping of Z with modulus 36>,
      <rcwa mapping of Z with modulus 36> ]
    gap> List(fact,MovedPoints);
    [ 33(36) U 34(36) U 35(36), 9(36) U 10(36) U 11(36),
      <union of 23 residue classes (mod 36)> \ [ -6, 3 ] ]

##### 2.8-4 TransitionMatrix

`> TransitionMatrix`( f, m ) | ( function )

Returns: The transition matrix of the rcwa mapping f for modulus m.

Let M be this matrix. Then for any two residue classes r_1(m), r_2(m) in R/mR, the entry M_r_1(m),r_2(m) is defined by

(See LaTeX version of the manual.) The assignment of the residue classes (mod m) to the rows and columns of the matrix is given by the ordering of the residues in `AllResidues(Source(f),m)`.

The transition matrix is a weighted adjacency matrix of the corresponding transition graph `TransitionGraph(f,m)`. The sums of the rows of a transition matrix are always equal to 1.

    gap> Display(TransitionMatrix(a,5));
    [ [  1/2,  1/4,    0,    0,  1/4 ],
      [    0,  1/4,    0,  1/4,  1/2 ],
      [  1/4,    0,    0,  3/4,    0 ],
      [  1/4,    0,  3/4,    0,    0 ],
      [    0,  1/2,  1/4,    0,  1/4 ] ]

    gap> Display(TransitionMatrix(T,19)*One(GF(7)));
     4 . . . . . . . . . 4 . . . . . . . .
     . . 4 . . . . . . . 4 . . . . . . . .
     . 4 . . . . . . . . . . . 4 . . . . .
     . . . . . 4 . . . . . 4 . . . . . . .
     . . 4 . . . . . . . . . . . . . 4 . .
     . . . . . . . . 4 . . . 4 . . . . . .
     4 . . 4 . . . . . . . . . . . . . . .
     . . . . . . . . . . . 4 . 4 . . . . .
     . . . 4 4 . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . 1 . . . .
     . . . . . 4 4 . . . . . . . . . . . .
     . . . . . . . . . . . . . . . 4 . 4 .
     . . . . . . 4 . . 4 . . . . . . . . .
     . 4 . . . . . . . . . . . . . . 4 . .
     . . . . . . . 4 . . . . 4 . . . . . .
     . . . . 4 . . . . . . . . . . . . 4 .
     . . . . . . . . 4 . . . . . . 4 . . .
     . . . . . . . 4 . . . . . . . . . . 4
     . . . . . . . . . 4 . . . . . . . . 4

#### 2.9 Trajectories

##### 2.9-1 Trajectory

`> Trajectory`( f, n, val, cond ) | ( function )

Returns: The trajectory of the ring element n under the rcwa mapping f.

Depending on whether `cond = "length"` or `cond = "stop"`, the parameter val either is the length of the sequence to be computed or is a "stopping set" such that the computation stops when some iterate `n^(f^k) in val` is reached. In place of the ring element n, a union of residue classes is permitted, also.

    gap> Trajectory(T,27,[1],"stop");
    [ 27, 41, 62, 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103, 155,
      233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283,
      425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051,
      3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46,
      23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1 ]
    gap> Trajectory(T,ResidueClass(Integers,3,0),Integers,"stop");
    [ 0(3), 0(3) U 5(9), 0(3) U 5(9) U 7(9) U 8(27),
      <union of 20 residue classes (mod 27)>, <union of 73 residue classes (mod
        81)>, <union of 79 residue classes (mod 81)>, Integers ]
    gap> Length(Trajectory(RcwaMapping([[1,0,2],[5,-1,2]]),19,[1],"stop"));
    307

##### 2.9-2 TrajectoryModulo

`> TrajectoryModulo`( f, n, m, lng ) | ( function )

`> TrajectoryModulo`( f, n, lng ) | ( function )

Returns: The sequence (n_i), i = 0, dots, lng-1 with n_i := n^(f^i) mod m as a list.

If m is not given it defaults to the modulus of f.

    gap> TrajectoryModulo(a,8,25);
    [ 0, 0, 2, 3, 0, 2, 1, 2, 3, 2, 1, 3, 0, 0, 0, 0, 2, 3, 2, 1, 1, 2, 3, 1, 2 ]
    gap> TrajectoryModulo(T,27,2,100);
    [ 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0,
      0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0,
      1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1,
      0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 ]

##### 2.9-3 CoefficientsOnTrajectory

`> CoefficientsOnTrajectory`( f, n, val, cond, all ) | ( function )

Returns: A list `c` of coefficient triples, such that for any `k` it holds that `n^(f^(k-1)) = (c[k][1]*n + c[k][2])/c[k][3]`, or its last entry.

The meaning of the arguments val and cond is the same as in `Trajectory` (2.9-1). If `all = true`, the whole sequence of coefficient triples is returned. Otherwise the result is only the last triple.

    gap> CoefficientsOnTrajectory(T,27,1,"stop",false);
    [ 36472996377170786403, 195820718533800070543, 1180591620717411303424 ]
    gap> (last[1]*27+last[2])/last[3];
    1
    gap> CoefficientsOnTrajectory(sigma,37,37,"stop",true);
    [ [ 1, 0, 1 ], [ 1, 1, 1 ], [ 2, 4, 1 ], [ 3, 9, 1 ], [ 6, 18, 1 ],
      [ 2, 5, 1 ], [ 2, 3, 1 ], [ 2, 1, 3 ], [ 2, 4, 3 ], [ 2, 7, 3 ],
      [ 1, 2, 1 ], [ 3, 3, 2 ], [ 3, 5, 2 ], [ 3, 7, 2 ], [ 3, 3, 1 ],
      [ 9, 15, 2 ], [ 27, 57, 4 ], [ 27, 57, 2 ], [ 9, 17, 2 ], [ 9, 13, 2 ],
      [ 9, 15, 1 ], [ 3, 4, 1 ], [ 3, 2, 1 ], [ 1, 0, 1 ] ]
    gap> List(last,c->(c[1]*37+c[2])/c[3]){[1..23]} = Cycle(sigma,37);
    true
    gap> CoefficientsOnTrajectory(r,x^3+x^2,x^3+x^2,"stop",true);
    [ [ Z(2)^0, 0*Z(2), Z(2)^0 ], [ x^2+x+Z(2)^0, x^2+x, x^2+Z(2)^0 ],
      [ x^4+x^2+Z(2)^0, x^4+x, x^4+Z(2)^0 ],
      [ x^6+x^5+x^3+x+Z(2)^0, x^6+x^4+x^3+x^2, x^6+x^4+x^2+Z(2)^0 ],
      [ x^8+x^4+Z(2)^0, x^7+x^6, x^8+Z(2)^0 ] ]

##### 2.9-4 IncreasingOn

`> IncreasingOn`( f ) | ( function )

`> DecreasingOn`( f ) | ( function )

Returns: The union of all residue classes r(m) such that |R/a_r(m)R| > |R/c_r(m)R| resp. |R/a_r(m)R| < |R/c_r(m)R|, where R denotes the source, m the modulus and a_r(m), b_r(m) and c_r(m) the coefficients of f as introduced in the definition of an rcwa mapping.

    gap> List([1..3],k->IncreasingOn(T^k));
    [ 1(2), 3(4), 3(4) U 1(8) U 6(8) ]
    gap> List([1..3],k->DecreasingOn(T^k));
    [ 0(2), 0(2) U 1(4), 0(4) U 2(8) U 5(8) ]
    gap> List([1..3],k->IncreasingOn(a^k));
    [ 0(2), 0(2) U 3(8) U 5(8), 0(4) U 2(16) U 5(16) U 11(16) U 14(16) ]

#### 2.10 Special functions for non-bijective mappings and miscellanea

##### 2.10-1 LikelyContractionCentre

`> LikelyContractionCentre`( f, maxn, bound ) | ( operation )

Returns: A list of ring elements -- see below.

Tries to compute the contraction centre of an rcwa mapping - assuming its existence this is the uniquely-defined finite subset S_0 of the base ring R which is mapped bijectively onto itself under f and where for any x in R there is an integer k such that the image of x under the k-th power of f lies in S_0. The mapping f is assumed to be contracting, i.e. to have such a contraction centre. As this problem seems to be computationally undecidable methods will be probabilistic. The argument maxn is a bound on the starting value and bound is a bound on the elements of the sequences to be searched. If the limit bound is exceeded, an Info message on some Info level of `InfoRCWA` is given.

    gap> S0 := LikelyContractionCentre(T,100,1000);
    #I  Warning: `LikelyContractionCentre' is highly probabilistic.
    The returned result can only be regarded as a rough guess.
    See ?LikelyContractionCentre for information on how to improve this guess.
    [ -136, -91, -82, -68, -61, -55, -41, -37, -34, -25, -17, -10, -7, -5, -1, 0,
      1, 2 ]

##### 2.10-2 GuessedDivergence

`> GuessedDivergence`( f ) | ( operation )

Returns: A floating point value, which should be a rough guess on how fast the trajectories of the rcwa mapping f diverge (return value greater than 1) or converge (return value smaller than 1).

Nothing particular is guaranteed.

    gap> List( [ T, a ], GuessedDivergence );
    #I  Warning: GuessedDivergence: no particular return value is guaranteed.
    #I  Warning: GuessedDivergence: no particular return value is guaranteed.
    [ 0.866025, 1.06066 ]

##### 2.10-3 ImageDensity

`> ImageDensity`( f ) | ( attribute )

Returns: The image density of the rcwa mapping f.

In the notation introduced in the definition of an rcwa mapping, the image density of f is defined by frac1m sum_r(m) in R/mR |R/c_r(m)R|/|R/a_r(m)R|. Injective rcwa mappings have an image density of at most 1, and the image density of a surjective rcwa mapping is at least 1 (this can be seen easily) -- thus in particular the image density of a bijective mapping equals 1.

    gap> List( [ T, a, RcwaMapping([[2,0,1]]) ], ImageDensity );
    [ 4/3, 1, 1/2 ]

##### 2.10-4 RightInverse

`> RightInverse`( f ) | ( attribute )

Returns: A right inverse of the injective rcwa mapping f, i.e. a mapping g such that fg = 1.

    gap> RcwaMapping([[2,0,1]]);
    Rcwa mapping of Z: n -> 2n
    gap> Display(RightInverse(last));

    Rcwa mapping of Z with modulus 2

                    n mod 2                |                 n^f
    ---------------------------------------+--------------------------------------
      0                                    | n/2
      1                                    | n

##### 2.10-5 CommonRightInverse

`> CommonRightInverse`( l, r ) | ( operation )

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.

    gap> Display(CommonRightInverse(RcwaMapping([[2,0,1]]),
    >                               RcwaMapping([[2,1,1]])));

    Rcwa mapping of Z with modulus 2

                    n mod 2                |                 n^f
    ---------------------------------------+--------------------------------------
      0                                    | n/2
      1                                    | (n - 1)/2

#### 2.11 The categories and families of rcwa mappings

##### 2.11-1 IsRcwaMapping

`> IsRcwaMapping`( f ) | ( filter )

`> IsIntegralRcwaMapping`( f ) | ( filter )

`> IsSemilocalIntegralRcwaMapping`( f ) | ( filter )

`> IsModularRcwaMapping`( f ) | ( filter )

Returns: `true` if f is an rcwa mapping resp. an rcwa mapping of the ring of integers resp. an rcwa mapping of a semilocalization of the ring of integers resp. an rcwa mapping of a polynomial ring in one variable over a finite field, and `false` otherwise.

##### 2.11-2 RcwaMappingsFamily

`> RcwaMappingsFamily`( R ) | ( function )

Returns: The family of rcwa mappings of the ring R.

Top of Book | Previous Chapter | Next Chapter

Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | 6 | Bib | Ind

generated by GAPDoc2HTML