<!-- #################################################################### -->
<!-- ##                                                                ## -->
<!-- ##  rcwamap.xml          RCWA documentation          Stefan Kohl  ## -->
<!-- ##                                                                ## -->
<!-- ##  $Id: rcwamap.xml,v 1.112 2005/11/22 16:15:10 stefan Exp $     ## -->
<!-- ##                                                                ## -->
<!-- #################################################################### -->

<Chapter Label="ch:RcwaMappings">
<Heading>Residue Class-Wise Affine Mappings</Heading>

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

<!-- #################################################################### -->

<Section Label="sec:basicdefinitions">
<Heading>Basic definitions</Heading>

<Index Key="rcwa mapping" Subkey="definition"></Index> 
Let <M>R</M> be an infinite euclidean domain which is not a field and all
of whose proper residue class rings are finite. A mapping
<M>f: R \rightarrow R</M> is called <E>residue class-wise affine</E>, or in
short an <E>rcwa</E> mapping, if there is an <M>m \in R \setminus \{0\}</M>
such that the restrictions of <M>f</M> to the residue classes <M>r(m) \in
R/mR</M> are affine. This means that for any residue class <M>r(m)</M>
there are coefficients <M>a_{r(m)}, b_{r(m)}, c_{r(m)} \in R</M>, such that
the restriction of the mapping <M>f</M> to the set
<M>r(m) = \{ r+km | k \in R\}</M> is given by <P/>
<Alt Only="Text"> 
  <![CDATA[

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

  ]]>
</Alt>
<Alt Only="HTML">
  <![CDATA[
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    f|_r(m):&nbsp;&nbsp;&nbsp;&nbsp;r(m)&nbsp;->&nbsp;R,
    &nbsp;&nbsp;&nbsp;&nbsp;n&nbsp;->&nbsp;(&nbsp;a_r(m)&nbsp;*&nbsp;n
    &nbsp;+&nbsp;b_r(m)&nbsp;)&nbsp;/&nbsp;c_r(m).
  ]]>
</Alt>
<Alt Only="LaTeX">
  <Display>
    f|_{r(m)}: \ r(m) \rightarrow R, \ \ \
    n \ \mapsto \ \frac{a_{r(m)} \cdot n + b_{r(m)}}{c_{r(m)}} \ .
  </Display>
</Alt>
<Index Key="rcwa mapping" Subkey="modulus"></Index>
The value <M>m</M> is called the <E>modulus</E> of <M>f</M>.
It is understood that all fractions are reduced, i.e. that
<M>\gcd( a_{r(m)}, b_{r(m)}, c_{r(m)} ) = 1</M>, and that
<M>m</M> is chosen multiplicatively minimal. <P/>

Apart from the restrictions imposed by the condition that the image of any
residue class <M>r(m)</M> under <M>f</M> must be a subset of <M>R</M> and
that one cannot divide by&nbsp;0, the coefficients <M>a_{r(m)}</M>,
<M>b_{r(m)}</M> and <M>c_{r(m)}</M> can be any ring elements. <P/>

When talking about the <E>product</E> 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. <P/>

The set RCWA(<M>R</M>) <M>\ := \ </M> { <M>\{ \ g \in</M> Sym(<M>R</M>)
<M>\ | \ g</M> is residue class-wise affine <M>\}</M> } is closed under
multiplication and taking inverses (this can be verified easily), hence
forms a subgroup of Sym(<M>R</M>).
<Index Key="rcwa group" Subkey="definition"></Index>
A subgroup of RCWA(<M>R</M>) is called a <E>residue class-wise affine</E>
group, or in short an <E>rcwa</E> group. <P/>

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:EnteringRcwaMappings">
<Heading>Entering rcwa mappings</Heading>

In order to define an rcwa mapping, it is necessary to specify the underlying
ring&nbsp;<M>R</M>, the modulus&nbsp;<M>m</M> and the coefficients
<M>a_{r(m)}</M>, <M>b_{r(m)}</M> and&nbsp;<M>c_{r(m)}</M> for <M>r(m)</M>
running over the residue classes (mod&nbsp;<M>m</M>). <P/>

A coefficient list for an rcwa mapping with modulus <M>m</M> consists of
<M>|R/mR|</M> coefficient triples
<C>[&nbsp;a&uscore;rm,&nbsp;b&uscore;rm,&nbsp;c&uscore;rm&nbsp;]</C>.
Their ordering is determined by the ordering of the representatives of the
residue classes (mod&nbsp;<M>m</M>) in the sorted list returned by
<C>AllResidues(<A>R</A>, <A>m</A>)</C>. For <M>R = \mathbb{Z}</M>, this means
that the coefficient triple for the residue class <M>0(m)</M> comes first,
then comes the one for <M>1(m)</M>, the one for <M>2(m)</M> and so on. <P/>

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

<Example>
<![CDATA[
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

]]>
</Example>

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 <M>\mathbb{Z}</M> described afterwards.

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<ManSection>
  <Meth Name="RcwaMapping" Arg="R, m, coeffs"
        Label="R, m, coeffs"/>
  <Meth Name="RcwaMapping" Arg="R, coeffs"
        Label="R, coeffs"/>
  <Meth Name="RcwaMapping" Arg="coeffs"
        Label="coeffs"/>
  <Meth Name="RcwaMapping" Arg="perm, range"
        Label="perm, range"/>
  <Meth Name="RcwaMapping" Arg="m, values"
        Label="m, values"/>
  <Meth Name="RcwaMapping" Arg="pi, coeffs"
        Label="pi, coeffs"/>
  <Meth Name="RcwaMapping" Arg="q, m, coeffs"
        Label="q, m, coeffs"/>
  <Meth Name="RcwaMapping" Arg="P1, P2"
        Label="P1, P2"/>
  <Meth Name="RcwaMapping" Arg="cycles"
        Label="cycles"/>
  <Returns> An rcwa mapping. </Returns>
  <Description>
    Construction of an rcwa mapping. <P/>

    In all cases the argument&nbsp;<A>R</A> is the underlying ring,
    <A>m</A> is the modulus and <A>coeffs</A> 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
    <List>
      <Mark>(a)</Mark>
      <Item>
        of <A>R</A> with modulus <A>modulus</A> and coefficients
        <A>coeffs</A>, resp.
      </Item>
      <Mark>(b)</Mark>
      <Item>
        of <A>R</A> = <M>\mathbb{Z}</M> or <A>R</A> =
        <M>\mathbb{Z}_{(\pi)}</M> with modulus <C>Length(<A>coeffs</A>)</C>
        and coefficients <A>coeffs</A>, resp.
      </Item>
      <Mark>(c)</Mark>
      <Item>
        of <A>R</A> = <M>\mathbb{Z}</M> with modulus
        <C>Length(<A>coeffs</A>)</C> and coefficients <A>coeffs</A>, resp.
      </Item>
      <Mark>(d)</Mark>
      <Item>
        of <A>R</A> = <M>\mathbb{Z}</M>, acting on any set
        <C><A>range</A> + k*Length(<A>range</A>)</C> like the
        permutation <A>perm</A> on the range <A>range</A>, resp.
      </Item>
      <Mark>(e)</Mark>
      <Item>
        of <A>R</A> = <M>\mathbb{Z}</M> with modulus <A>modulus</A> and
        values prescribed by the list <A>val</A>, which consists of
        2<M>\cdot</M><A>modulus</A> pairs giving preimage and image for
        2 points per residue class (mod <A>modulus</A>), resp.
      </Item>
      <Mark>(f)</Mark>
      <Item>
        of <M>\Z_{(\pi)}</M> with modulus <C>Length(<A>coeffs</A>)</C>
        and coefficients <A>coeffs</A> (the set of primes <M>\pi</M> 
        denoting the underlying ring is given as argument <A>pi</A>), resp.
      </Item>
      <Mark>(g)</Mark>
      <Item>
        of GF(<A>q</A>)[<A>x</A>] with modulus
        <A>modulus</A> and coefficients <A>coeffs</A>, resp.
      </Item>
      <Mark>(h)</Mark>
      <Item>
        an arbitrary rcwa mapping which induces a bijection between
        the partitions <A>P1</A> and <A>P2</A> of <A>R</A> into disjoint
        single residue classes and which is affine on the elements
        of <A>P1</A>, resp.
      </Item>
      <Mark>(i)</Mark>
      <Item>
        an arbitrary rcwa mapping with <Q>residue class cycles</Q> as given
        by <A>cycles</A>. The latter is a list of lists of disjoint residue
        classes which the mapping should permute cyclically, each.
      </Item>
    </List>
    The methods for the operation <C>RcwaMapping</C> perform a number of
    argument checks, which can be skipped by using <C>RcwaMappingNC</C>
    instead.

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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 ]
]]>
</Example>
  </Description>
</ManSection>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Alt Only="LaTeX">\noindent</Alt>
Some kinds of very simple-structured rcwa mappings are of particular interest:

<ManSection>
  <Func Name="ClassShift" Arg="r, m" Label="r, m"/>
  <Returns> The <E>class shift</E> <M>\nu_{r(m)}</M>. </Returns>
  <Description>
    The <E>class shift</E> <M>\nu_{r(m)}</M> is the rcwa mapping of
    <M>\mathbb{Z}</M> which maps <M>n \in r(m)</M> to <M>n + m</M>
    and fixes <M>\mathbb{Z} \setminus r(m)</M> pointwise.
    The residue class <C>ResidueClass(<A>r</A>,<A>m</A>)</C> itself
    can be given in place of the arguments <A>r</A> and&nbsp;<A>m</A>.
    Enclosing the argument list in list brackets is permitted.
<Example>
<![CDATA[
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

]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Func Name="ClassReflection" Arg="r, m" Label="r, m"/>
  <Returns> The <E>class reflection</E> <M>\varsigma_{r(m)}</M>. </Returns>
  <Description>
    The <E>class reflection</E> <M>\varsigma_{r(m)}</M> is the rcwa mapping
    of <M>\mathbb{Z}</M> which maps <M>n \in r(m)</M> to <M>-n + 2r</M>
    and fixes <M>\mathbb{Z}&nbsp;\setminus&nbsp;r(m)</M> pointwise.
    The residue class <C>ResidueClass(<A>r</A>,<A>m</A>)</C> itself
    can be given in place of the arguments <A>r</A> and&nbsp;<A>m</A>.
    Enclosing the argument list in list brackets is permitted.
<Example>
<![CDATA[
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

]]>
</Example>
  </Description>
</ManSection>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<ManSection>
  <Func Name="ClassTransposition" Arg="r1, m1, r2, m2"
                                  Label="r1, m1, r2, m2"/>
  <Returns>
    The <E>class transposition</E> <M>\tau_{r_1(m_1),r_2(m_2)}</M>.
  </Returns>
  <Description>
    The <E>class transposition</E> <M>\tau_{r_1(m_1),r_2(m_2)}</M> is an
    rcwa mapping of <M>\mathbb{Z}</M> of order&nbsp;2 which interchanges
    the disjoint residue classes <M>r_1(m_1)</M> and <M>r_2(m_2)</M> of
    <M>\mathbb{\Z}</M> and fixes the complement of their union pointwise.
    The residue classes <C>ResidueClass(<A>r1</A>,<A>m1</A>)</C>
    and <C>ResidueClass(<A>r2</A>,<A>m2</A>)</C> themselves
    can be given in place of the arguments <A>r1</A>, <A>m1</A>,
    <A>r2</A> and <A>m2</A>. Enclosing the argument list in list brackets
    is permitted.
<Example>
<![CDATA[
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

]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Func Name="PrimeSwitch" Arg="p" Label="p"/>
  <Func Name="PrimeSwitch" Arg="p, k" Label="p, k"/>
  <Returns>
    In the one-argument form the <E>prime switch</E>
    <M>\sigma_p := \tau_{0(8),1(2p)} \cdot \tau_{4(8),-1(2p)} \cdot
    \tau_{0(4),1(2p)} \cdot \tau_{2(4),-1(2p)} \cdot \tau_{2(2p),1(4p)}
    \cdot \tau_{4(2p),2p+1(4p)}</M>, and in the two-argument form
    the restriction of <M>\sigma_p</M> by <M>n \mapsto kn</M>
    (cp.&nbsp;<Ref Oper="Restriction" Label = "g, f"/>).
  </Returns>
  <Description>
    For an odd prime <M>p</M>, the <E>prime switch</E> <M>\sigma_p</M>
    is a bijective rcwa mapping of <M>\Z</M> with modulus&nbsp;<M>4p</M>,
    multiplier&nbsp;<M>p</M> (see <Ref Attr="Multiplier" Label="f"/>) and
    divisor&nbsp;2 (see <Ref Attr="Divisor" Label="f"/>).
    The prime switches <M>\sigma_p</M> play an important role in factoring
    non-balanced rcwa mappings into class shifts, class reflections and
    class transpositions (cp. <Ref Attr="FactorizationIntoGenerators"
    Label="g"/>).
<Example>
<![CDATA[
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

]]>
</Example>
  </Description>
</ManSection>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

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

<ManSection>
  <Meth Name="LaTeXObj" Arg="f" Label="f"/>
  <Returns>
    A &LaTeX; representation of the integral rcwa mapping&nbsp;<A>f</A>.
  </Returns>
  <Description>
    The output makes use of the &LaTeX; macro package
    <Package>amsmath</Package>.
    If the option <A>Factorization</A> is set, a factorization of <A>f</A>
    into class shifts, class reflections, class transpositions and prime
    switches is printed (cp. <Ref Attr="FactorizationIntoGenerators"
    Label="g"/>).
    For rcwa mappings with modulus larger than&nbsp;1, an indentation by
    <A>Indentation</A> characters can be specified by setting this option
    value accordingly.
<Example>
<![CDATA[
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)}
]]>
</Example>
  </Description>
</ManSection>

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

</Section>

<!-- #################################################################### -->

<Section Label="sec:BasicFunctionalityForRcwaMappings">
<Heading>Basic functionality for rcwa mappings</Heading>

Checking whether two rcwa mappings are equal is cheap.
Rcwa mappings can be multiplied, thus there is a method for <C>*</C>.
Bijective rcwa mappings can also be inverted, thus there is a method for
<C>Inverse</C>. 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
<C>IsTame</C>. There are methods for <C>Order</C>, which can not only
compute a finite order, but are also suitable for detecting infinite order.
<P/>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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>
]]>
</Example>

There are methods installed for <C>IsInjective</C>, <C>IsSurjective</C>,
<C>IsBijective</C> and <C>Image</C>.

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

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
<C>&circum;</C> (the same symbol as used for exponentiation and conjugation).
The same works for partitions of the source into a finite number of
residue classes.

<Example>
<![CDATA[
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) ]
]]>
</Example>

For computing preimages of elements under rcwa mappings,
there are methods for <C>PreImageElm</C> and <C>PreImagesElm</C>.
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
<C>PreImage</C>.

<Example>
<![CDATA[
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 ]
]]>
</Example>

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

<Example>
<![CDATA[
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>
]]>
</Example>

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
<C>+</C> and <C>*</C>. <P/>

<Example>
<![CDATA[
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 ) )
]]>
</Example>

There are operations <C>Modulus</C> (abbreviated <C>Mod</C>) and
<C>Coefficients</C> 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 <M>\mathbb{Z}</M>, not for all operations applicable methods are
available. <P/>

</Section>

<!-- #################################################################### -->

<Section Label="sec:FactoringRcwaMappings">
<Heading>Factoring rcwa mappings</Heading>

Factoring group elements into elements of some <Q>nice</Q> 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(<M>\Z</M>):

<ManSection>
  <Attr Name="FactorizationIntoGenerators" Arg="g" Label="g"/>
  <Returns>
    A factorization of the bijective rcwa mapping&nbsp;<A>g</A> into
    class shifts, class reflections and class transpositions, provided
    that such a factorization exists and the method finds it.
  </Returns>
  <Description>
    This may return <C>fail</C>, 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 <A>ExpandPrimeSwitches</A> is set, they are each
    decomposed into the 6 class transpositions given in
    the definition (see <Ref Func="PrimeSwitch" Label="p"/>).
    By default, the factoring process begins with splitting off factors
    from the right. This can be changed by setting the option
    <A>Direction</A> to <C>"from the left"</C>. 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 <A>ShortenPartition</A>
    equal to <C>false</C>.
    By default, at the end it is checked whether the product of the
    determined factors indeed equals <A>g</A>. This check can be
    suppressed by setting the option <A>NC</A>.<P/>
    
    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 <Ref InfoClass="InfoRCWA"/> to&nbsp;2.
<Example>
<![CDATA[
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) ]
]]>
</Example>
  </Description>
</ManSection>

For purposes of demonstrating the capabilities of the factorization routine,
in Section&nbsp;<Ref Label="sec:FactoringTheCollatzPermutation"/>
a permutation is factored which has already been mentioned by Lothar Collatz
in&nbsp;1932, and whose cycle structure is unknown so far.

</Section>

<!-- #################################################################### -->

<Section Label="sec:DeterminantAndSign">
<Heading>Determinant and sign</Heading>

<ManSection>
  <Meth Name="Determinant" Arg="sigma" Label="sigma"/>
  <Meth Name="Determinant" Arg="sigma, S" Label="sigma, S"/>
  <Returns>
    The determinant of the bijective rcwa mapping&nbsp;<A>sigma</A>.
  </Returns>
  <Description>
    The <E>determinant</E> of an affine mapping <M>n \mapsto (an+b)/c</M>
    whose source is a residue class <M>r(m)</M> is defined by <M>b/|a|m</M>.
    This definition is extended additively to determinants of rcwa mappings
    and their restrictions to unions of residue classes. <P/>

    Using the notation from the definition of an rcwa mapping,
    the <E>determinant</E> det(<M>\sigma</M>) of an rcwa mapping
    <M>\sigma</M> is given by
    <Alt Not="LaTeX">
      (see LaTeX version of the manual).
    </Alt> 
    <Alt Only="LaTeX">
      <Display>
        \frac{1}{m}
        \left( \sum_{r(m) \in R/mR} \frac{b_{r(m)}}{|a_{r(m)}|} \right).
      </Display>
    </Alt>
    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 <M>\Z</M> onto <M>(\Z,+)</M> (see Theorem&nbsp;2.11.9).
    <P/>

    If a residue class union&nbsp;<A>S</A> is given as an additional
    argument, the method returns the determinant of the restriction
    of <A>sigma</A> to&nbsp;<A>S</A>.
<Example>
<![CDATA[
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
]]>
</Example>
  </Description>
</ManSection>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<ManSection>
  <Attr Name="Sign" Arg="sigma" Label="sigma"/>
  <Returns>
    The sign of the bijective rcwa mapping&nbsp;<A>sigma</A>.
  </Returns>
  <Description>
    Using the notation from the definition of an rcwa mapping,
    the <E>sign</E> of a bijective rcwa mapping&nbsp;<M>\sigma</M>
    of&nbsp;<M>\Z</M> is defined by
    <Alt Not="LaTeX">
      (see LaTeX version of the manual).
    </Alt> 
    <Alt Only="LaTeX">
      <Display>
        (-1)^{\displaystyle{{\rm det}(\sigma) + \frac{1}{m}
        \left(
          \sum_{r(m): \ a_{r(m)} &lt; 0} (m - 2r)
        \right)}}.
      </Display>
    </Alt>
    In the author's thesis it is shown that the sign mapping is an
    epimorphism from RCWA(<M>\Z</M>) onto the group <M>\Z^\times</M> of
    units of&nbsp;<M>\Z</M> (see Theorem&nbsp;2.12.8).
    This means that the kernel of the sign mapping is a normal subgroup
    of RCWA(<M>\Z</M>) of index&nbsp;2.
<Example>
<![CDATA[
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 ]
]]>
</Example>
  </Description>
</ManSection>

</Section>

<!-- #################################################################### -->

<Section Label="sec:PropertiesDerivedFromCoefficients">
<Heading>Attributes and properties derived from the coefficients</Heading>

<ManSection>
  <Attr Name="Multiplier" Arg="f" Label="f"/>
  <Attr Name="Mult"       Arg="f" Label="f"/>
  <Returns> The multiplier of the rcwa mapping&nbsp;<A>f</A>. </Returns>
  <Description>
    In the notation used in the definition of an rcwa mapping,
    the <E>multiplier</E> is the lcm of the coefficients <M>a_{r(m)}</M>
    in the numerators.
<Example>
<![CDATA[
gap> List( [ g, u, T, d, r ], Multiplier );
[ 1, 9, 3, 1, x^2+x+Z(2)^0 ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Attr Name="Divisor" Arg="f" Label="f"/>
  <Attr Name="Div"     Arg="f" Label="f"/>
  <Returns> The divisor of the rcwa mapping&nbsp;<A>f</A>. </Returns>
  <Description>
    In the notation used in the definition of an rcwa mapping,
    the <E>divisor</E> is the lcm of the coefficients <M>c_{r(m)}</M>
    in the denominators.
<Example>
<![CDATA[
gap> List( [ g, u, T, d, r ], Divisor );
[ 1, 5, 2, 1, x^2+Z(2)^0 ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Oper Name="PrimeSet" Arg="f" Label="f"/>
  <Returns> The prime set of the rcwa mapping&nbsp;<A>f</A>. </Returns>
  <Description>
    The <E>prime set</E> of an rcwa mapping is the set of prime divisors
    of the product of its modulus, its multiplier and its divisor.
    See also&nbsp;<Ref Oper="PrimeSet" Label="G"/> for rcwa groups.
<Example>
<![CDATA[
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 ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Prop Name="IsIntegral" Arg="f" Label="f"/>
  <Returns>
    <C>true</C> if the rcwa mapping&nbsp;<A>f</A> is integral and
    <C>false</C> otherwise.
  </Returns>
  <Description>
    An rcwa mapping is called <E>integral</E> if its divisor equals&nbsp;1,
    thus <Q>if no proper divisions occur</Q>. Computing with such mappings
    is particularly easy. <P/>

    Be careful not to confuse this with the term <E>integral rcwa mapping</E>
    for rcwa mappings of the integers; normally it should be rather clear
    what is meant.
<Example>
<![CDATA[
gap> List( [ u, t, RcwaMapping([[2,0,1],[3,5,1]]) ], IsIntegral );
[ false, true, true ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Prop Name="IsClassWiseOrderPreserving" Arg="f" Label="f"/>
  <Returns>
    <C>true</C> if the rcwa mapping&nbsp;<A>f</A> is class-wise
    order-preserving and <C>false</C> otherwise.
  </Returns>
  <Description>
    The term <E>class-wise order-preserving</E> is defined only
    for rcwa mappings of ordered rings, e.g.&nbsp;<M>\mathbb{Z}</M>.
<Example>
<![CDATA[
gap> List( [ g, u, T, t, d ], IsClassWiseOrderPreserving );
[ true, true, true, false, true ]
]]>
</Example>
  </Description>
</ManSection>

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:AffinePartialMappings">
<Heading>Functionality related to the affine partial mappings</Heading>

<ManSection>
  <Attr Name="LargestSourcesOfAffineMappings" Arg="f" Label="f"/>
  <Returns>
    The coarsest partition of <C>Source(<A>f</A>)</C> on whose
    elements the rcwa mapping&nbsp;<A>f</A> is affine.
  </Returns>
  <Description>
<Example>
<![CDATA[
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 ) ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Oper Name="Multpk" Arg="f, p, k" Label="f, p, k"/>
  <Returns>
    The union of the residue classes <M>r(m)</M> such that
    <M>p^k||a_{r(m)}</M> if <M>k \geq 0</M>, and the union of the residue
    classes <M>r(m)</M> such that <M>p^k||c_{r(m)}</M> if <M>k \leq 0</M>.
  </Returns>
  <Description>
<Example>
<![CDATA[
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) ]
]]>
</Example>
  </Description>
</ManSection>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<ManSection>
  <Attr Name="SetOnWhichMappingIsClassWiseOrderPreserving"
        Arg="f" Label="f"/>
  <Attr Name="SetOnWhichMappingIsClassWiseConstant"
        Arg="f" Label="f"/>
  <Attr Name="SetOnWhichMappingIsClassWiseOrderReversing"
        Arg="f" Label="f"/>
  <Returns>
    The union of the residue classes (mod&nbsp;<C>Modulus(<A>f</A>)</C>)
    on which the rcwa mapping&nbsp;<A>f</A> is class-wise order-preserving,
    class-wise constant resp. class-wise order-reversing.
  </Returns>
  <Description>
    The source of the rcwa mapping&nbsp;<A>f</A> must be ordered.
<Example>
<![CDATA[
gap> List( [ T, u, t ], SetOnWhichMappingIsClassWiseOrderPreserving );
[ Integers, Integers, [  ] ]
gap> SetOnWhichMappingIsClassWiseConstant(RcwaMapping([[2,0,1],[0,4,1]]));
1(2)
]]>
</Example>
  </Description>
</ManSection>

</Section>

<!-- #################################################################### -->

<Section Label="sec:TransGraphMat">
<Heading>Transition graphs and transition matrices</Heading>

<ManSection>
  <Oper Name="TransitionGraph" Arg="f, m" Label="f, m"/>
  <Returns>
    The transition graph for modulus&nbsp;<A>m</A>
    of the rcwa mapping&nbsp;<A>f</A>.
  </Returns>
  <Description>
    <Index Key="rcwa mapping" Subkey="transition graph"></Index>
    The <E>transition graph</E> <M>\Gamma_{f,m}</M> of&nbsp;<M>f</M> for
    modulus&nbsp;<M>m</M> is defined as follows:
    <Enum>
      <Item>
        The vertices are the residue classes (mod&nbsp;<M>m</M>).
      </Item>
      <Item>
        There is an edge from <M>r_1(m)</M> to <M>r_2(m)</M> if and only if
        there is some <M>n_1 \in r_1(m)</M> such that
        <M>n_1^f \in r_2(m)</M>.
      </Item>
    </Enum>
    The assignment of the residue classes (mod&nbsp;<M>m</M>) to the
    vertices of the graph is given by the ordering of the residues in
    <C>AllResidues(Source(<A>f</A>),<A>m</A>)</C>.
    The result is returned as a <Package>GRAPE</Package>-graph.
<Example>
<![CDATA[
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 ] )
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Oper Name="OrbitsModulo" Arg="f, m" Label="f, m"/>
  <Returns>
    The partition of <C>AllResidues(Source(<A>f</A>),<A>m</A>)</C>
    corresponding to the weakly-connected components of the transition
    graph for modulus&nbsp;<A>m</A> of the rcwa mapping&nbsp;<A>f</A>.
  </Returns>
  <Description>
    See also <Ref Meth="OrbitsModulo" Label="G, m"/> for rcwa groups.
<Example>
<![CDATA[
gap> OrbitsModulo(Comm(a,b),9);
[ [ 0 ], [ 1, 4, 5, 6, 7 ], [ 2 ], [ 3 ], [ 8 ] ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Oper Name ="FactorizationOnConnectedComponents"
        Arg = "f, m" Label="f, m"/>
  <Returns>
    The set of restrictions of the rcwa mapping&nbsp;<A>f</A> to the
    weakly-connected components of its transition graph <M>\Gamma_{f,m}</M>.
  </Returns>
  <Description>
    These mappings have pairwisely disjoint supports, hence any two
    of them commute, and their product equals&nbsp;<A>f</A>.
<Example>
<![CDATA[
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 ] ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Func Name="TransitionMatrix" Arg="f, m" Label="f, m"/>
  <Returns>
    The transition matrix of the rcwa mapping&nbsp;<A>f</A> for
    modulus&nbsp;<A>m</A>.
  </Returns>
  <Description>
    <Index Key="rcwa mapping" Subkey="transition matrix"></Index>
    Let <M>M</M> be this matrix. Then for any two residue classes <M>r_1(m),
    r_2(m) \in R/mR</M>, the entry <M>M_{r_1(m),r_2(m)}</M> is defined by
    <Alt Only="LaTeX">
      <Display>
        <![CDATA[
          M_{r_1(m),r_2(m)} \ := \ \displaystyle{\frac{|R/mR|}{|R/\hat{m}R|}}
          \cdot \left|\left\{r(\hat{m}) \in R/\hat{m}R | \ r \in r_1(m)
          \wedge r^f \in r_2(m)\right\}\right|,
        ]]>
      </Display>
      where <M>\hat{m}</M> is the product of <A>m</A> and the square of the
      modulus of&nbsp;<A>f</A>.
    </Alt>
    <Alt Not="LaTeX">
      (See LaTeX version of the manual.)
    </Alt>
    The assignment of the residue classes (mod&nbsp;<A>m</A>) to the rows and
    columns of the matrix is given by the ordering of the residues in
    <C>AllResidues(Source(<A>f</A>),<A>m</A>)</C>. <P/>

    The transition matrix is a weighted adjacency matrix of the corresponding
    transition graph <C>TransitionGraph(<A>f</A>,<A>m</A>)</C>.
    The sums of the rows of a transition matrix are always equal to&nbsp;1.
<Example>
<![CDATA[
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 ] ]
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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
]]>
</Example>
  </Description>
</ManSection>

</Section>

<!-- #################################################################### -->

<Section Label="sec:Trajectories">
<Heading>Trajectories</Heading>

<ManSection>
  <Func Name="Trajectory" Arg="f, n, val, cond" Label="f, n, val, cond"/>
  <Returns>
    The trajectory of the ring element&nbsp;<A>n</A>
    under the rcwa mapping&nbsp;<A>f</A>.
  </Returns>
  <Description>
    Depending on whether <C><A>cond</A> = "length"</C> or
    <C><A>cond</A> = "stop"</C>, the parameter <A>val</A> either is the
    length of the sequence to be computed or is a <Q>stopping set</Q> such
    that the computation stops when some iterate
    <C><A>n</A>&circum;(<A>f</A>&circum;k) in <A>val</A></C> is reached.
    In place of the ring element&nbsp;<A>n</A>, a union of residue
    classes is permitted, also.
<Example>
<![CDATA[
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
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Func Name="TrajectoryModulo" Arg="f, n, m, lng" Label="f, n, m, lng"/>
  <Func Name="TrajectoryModulo" Arg="f, n, lng" Label="f, n, lng"/>
  <Returns>
    The sequence <M>(n_i), i = 0, \dots, lng-1</M> with
    <M>n_i := n^{(f^i)}</M>&nbsp;mod&nbsp;<A>m</A> as a list.
  </Returns>
  <Description>
    If <A>m</A> is not given it defaults to the modulus of&nbsp;<A>f</A>.
<Example>
<![CDATA[
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 ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Func Name="CoefficientsOnTrajectory"
        Arg="f, n, val, cond, all" Label="f, n, val, cond, all"/>
  <Returns>
    A list <C>c</C> of coefficient triples, such that for any&nbsp;<C>k</C>
    it holds that <C><A>n</A>&circum;(<A>f</A>&circum;(k-1)) =
    (c[k][1]*<A>n</A> + c[k][2])/c[k][3]</C>, or its last entry.
  </Returns>
  <Description>
    The meaning of the arguments <A>val</A> and <A>cond</A> is the same as
    in <Ref Func="Trajectory" Label="f, n, val, cond"/>.
    If <C><A>all</A> = true</C>, the whole sequence of coefficient triples
    is returned. Otherwise the result is only the last triple.
<Example>
<![CDATA[
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 ] ]
]]>
</Example>
  </Description>
</ManSection>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<ManSection>
  <Func Name="IncreasingOn" Arg="f" Label="f"/>
  <Func Name="DecreasingOn" Arg="f" Label="f"/>
  <Returns>
    The union of all residue classes <M>r(m)</M> such that
    <M>|R/a_{r(m)}R| &gt; |R/c_{r(m)}R|</M> resp.
    <M>|R/a_{r(m)}R| &lt; |R/c_{r(m)}R|</M>, where <M>R</M> denotes the
    source, <M>m</M> the modulus and <M>a_{r(m)}</M>, <M>b_{r(m)}</M>
    and <M>c_{r(m)}</M> the coefficients of&nbsp;<A>f</A> as
    introduced in the definition of an rcwa mapping.
  </Returns>
  <Description>
<Example>
<![CDATA[
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) ]
]]>
</Example>
  </Description>
</ManSection>

</Section>

<!-- #################################################################### -->

<Section Label="sec:NonBijectiveMappings">
<Heading>
  Special functions for non-bijective mappings and miscellanea
</Heading>

<ManSection>
  <Oper Name="LikelyContractionCentre"
        Arg="f, maxn, bound" Label="f, maxn, bound"/>
  <Returns> A list of ring elements -- see below. </Returns>
  <Description>
    Tries to compute the <E>contraction centre</E> of an rcwa mapping -
    assuming its existence this is the uniquely-defined finite subset
    <M>S_0</M> of the base ring&nbsp;<M>R</M> which is mapped bijectively
    onto itself under&nbsp;<A>f</A> and where for any <M>x</M>
    in&nbsp;<M>R</M> there is an integer&nbsp;<M>k</M> such that the image
    of <M>x</M> under the <M>k</M>-th power of <M>f</M> lies in <M>S_0</M>.
    The mapping&nbsp;<A>f</A> is assumed to be <E>contracting</E>, i.e.
    to have such a contraction centre.
    As this problem seems to be computationally undecidable methods will be
    probabilistic. The argument <A>maxn</A> is a bound on the starting
    value and <A>bound</A> is a bound on the elements of the sequences
    to be searched.
    If the limit <A>bound</A> is exceeded, an Info message on some Info
    level of <C>InfoRCWA</C> is given.
<Example>
<![CDATA[
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 ]
]]>
</Example>
  </Description>
</ManSection>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<ManSection>
  <Oper Name="GuessedDivergence" Arg="f" Label="f"/>
  <Returns>
    A floating point value, which should be a rough guess on how fast
    the trajectories of the rcwa mapping&nbsp;<A>f</A> diverge (return value
    greater than&nbsp;1) or converge (return value smaller than&nbsp;1).
  </Returns>
  <Description>
    Nothing particular is guaranteed.
<Example>
<![CDATA[
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 ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Attr Name="ImageDensity" Arg="f" Label="f"/>
  <Returns>
    The <E>image density</E> of the rcwa mapping&nbsp;<A>f</A>.
  </Returns>
  <Description>
    In the notation introduced in the definition of an rcwa mapping,
    the <E>image density</E> of <M>f</M> is defined by
    <M>\frac{1}{m} \sum_{r(m) \in R/mR} |R/c_{r(m)}R|/|R/a_{r(m)}R|</M>.
    Injective rcwa mappings have an image density of at most&nbsp;1, and
    the image density of a surjective rcwa mapping is at least&nbsp;1
    (this can be seen easily) -- thus in particular the image density of
    a bijective mapping equals&nbsp;1.
<Example>
<![CDATA[
gap> List( [ T, a, RcwaMapping([[2,0,1]]) ], ImageDensity );
[ 4/3, 1, 1/2 ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Attr Name ="RightInverse" Arg="f" Label = "f"/>
  <Returns>
    A right inverse of the injective rcwa mapping&nbsp;<A>f</A>,
    i.e. a mapping <M>g</M> such that <A>f</A><M>g</M>&nbsp;=&nbsp;1.
  </Returns>
  <Description>
<Example>
<![CDATA[
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

]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Oper Name="CommonRightInverse" Arg="l, r" Label="l, r"/>
  <Returns>
    A mapping <M>d</M> such that <A>l</A><M>d</M> = <A>r</A><M>d</M> = 1.
  </Returns>
  <Description>
    The mappings <A>l</A> and <A>r</A> must be injective, and their images
    must form a partition of the underlying ring.
<Example>
<![CDATA[
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

]]>
</Example>
  </Description>
</ManSection>

</Section>

<!-- #################################################################### -->

<Section Label="sec:CategoriesOfRcwaMappings">
<Heading>The categories and families of rcwa mappings</Heading>

<ManSection>
  <Filt Name="IsRcwaMapping" Arg="f" Label="f"/>
  <Filt Name="IsIntegralRcwaMapping" Arg="f" Label="f"/>
  <Filt Name="IsSemilocalIntegralRcwaMapping" Arg="f" Label="f"/>
  <Filt Name="IsModularRcwaMapping" Arg="f" Label="f"/>
  <Returns>
    <C>true</C> if <A>f</A> 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 <C>false</C> otherwise.
  </Returns>
</ManSection>

<ManSection>
  <Func Name="RcwaMappingsFamily" Arg="R" Label="R"/>
  <Returns>
    The family of rcwa mappings of the ring&nbsp;<A>R</A>.
  </Returns>
</ManSection>

</Section>

<!-- #################################################################### -->

</Chapter>

<!-- #################################################################### -->
